【正文】 需將S＞top減1， ①S＞top0表示空棧②下溢現(xiàn)象當(dāng)?？諘r(shí)，做退棧運(yùn)算產(chǎn)生的溢出現(xiàn)象。顯然，順序表的存儲(chǔ)密度是1，鏈表的存儲(chǔ)密度肯定小于1。與單鏈表上的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時(shí)修改兩個(gè)方向上的指針。 free(p)。 ppriornext=pnext。②帶頭結(jié)點(diǎn)的雙鏈表的某些運(yùn)算變得方便。在單鏈表中，從一已知結(jié)點(diǎn)出發(fā)，只能訪問(wèn)到該結(jié)點(diǎn)及其后續(xù)結(jié)點(diǎn)，無(wú)法找到該結(jié)點(diǎn)之前的其它結(jié)點(diǎn)。//④//②B表的開(kāi)始結(jié)點(diǎn)鏈接到A表尾具體算法：LinkList Connect(LinkList A,LinkList B)而表的操作常常是在表的首尾位置上進(jìn)行，因此，實(shí)用中多采用尾指針表示單循環(huán)鏈表。鏈表上實(shí)現(xiàn)的插入和刪除運(yùn)算，無(wú)須移動(dòng)結(jié)點(diǎn)，僅需修改指針。r=pnext。 ② sdata=x。 p=pnext。pdata!=key)//直到p為NULL或pdata為key為止//找到了第i個(gè)結(jié)點(diǎn) while(pnextamp。：（帶頭結(jié)點(diǎn)）（1）按結(jié)點(diǎn)序號(hào)查找：序號(hào)為0的是頭結(jié)點(diǎn)。 r=s。 s=(ListNode *)malloc(sizeof(ListNode))。while((ch=getchar())!=39。在有的應(yīng)用中可用于存放表長(zhǎng)等附加信息。④//尾指針指向新表尾（3） 尾插法建帶頭結(jié)點(diǎn)的單鏈表：頭結(jié)點(diǎn)及作用：頭結(jié)點(diǎn)是在鏈表的開(kāi)始結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)。else rearnext=p。pdata=ch。③ head=p。pdata=ch。①生成結(jié)點(diǎn)變量的標(biāo)準(zhǔn)函數(shù) p=( ListNode *)malloc(sizeof(ListNode))； //函數(shù)malloc分配一個(gè)類型為L(zhǎng)istNode的結(jié)點(diǎn)變量的空間,并將其首地址放入指針變量p中②釋放結(jié)點(diǎn)變量空間的標(biāo)準(zhǔn)函數(shù) free(p)；//釋放p所指的結(jié)點(diǎn)變量空間 ③結(jié)點(diǎn)分量的訪問(wèn) 1≤i≤n，：（1）插入：該算法的平均時(shí)間復(fù)雜度是O(n)，即在順序表上進(jìn)行插入運(yùn)算，平均要移動(dòng)一半結(jié)點(diǎn)（n/2）。順序表（Sequential List）：用順序存儲(chǔ)方法存儲(chǔ)的線性表稱為順序表。若L中沒(méi)有元素的值為x ，則返回0值。:(1)置空表InitList（L） 構(gòu)造一個(gè)空的線性表L。：常數(shù)階0(1)、對(duì)數(shù)階0(log2n)、線性階0(n)、線性對(duì)數(shù)階0(nlog2n)、平方階0(n2)立方階0(n3)、…、k次方階0(nk)、指數(shù)階0(2n)和階乘階0(n!)。：算法的正確性是首先要考慮的。（4）散列存儲(chǔ)：該方法的基本思想是：根據(jù)元素的關(guān)鍵字直接計(jì)算出該元素的存儲(chǔ)地址。: 順序存儲(chǔ)、鏈接存儲(chǔ)、索引存儲(chǔ)、散列存儲(chǔ)（1）順序存儲(chǔ)：通常借助程序設(shè)計(jì)語(yǔ)言的數(shù)組描述。②數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)內(nèi)的存儲(chǔ)方式，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）。數(shù)據(jù)的邏輯結(jié)構(gòu)分類: 線性結(jié)構(gòu)和非線性結(jié)構(gòu)。一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。算法是對(duì)數(shù)據(jù)運(yùn)算的描述，而數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。由此可見(jiàn)，程序設(shè)計(jì)的實(shí)質(zhì)是針對(duì)實(shí)際問(wèn)題選擇一種好的數(shù)據(jù)結(jié)構(gòu)和設(shè)計(jì)一個(gè)好的算法，而好的算法在很大程度上取決于描述實(shí)際問(wèn)題的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)對(duì)象是具有相同性質(zhì)的數(shù)據(jù)元素的集合。線性表是一個(gè)典型的線性結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)，它依賴于計(jì)算機(jī)語(yǔ)言。（2）鏈接存儲(chǔ)：通常借助于程序語(yǔ)言的指針來(lái)描述。：輸入，0個(gè)或多個(gè)數(shù)據(jù)作為輸入；輸出，產(chǎn)生一個(gè)或多個(gè)輸出；有窮性，算法執(zhí)行有限步后結(jié)束；確定性，每一條指令的含義都明確；可行性，算法是可行的。此外，主要考慮如下三點(diǎn)：① 執(zhí)行算法所耗費(fèi)的時(shí)間，即時(shí)間復(fù)雜性；② 執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間，主要是輔助空間，即空間復(fù)雜性；③ 算法應(yīng)易于理解、易于編程，易于調(diào)試等，即可讀性和可操作性。(n)定義為該算法所耗費(fèi)的存儲(chǔ)空間，它是問(wèn)題規(guī)模n的函數(shù),它包括存儲(chǔ)算法本身所占的存儲(chǔ)空間、算法的輸入輸出數(shù)據(jù)所占的存儲(chǔ)空間和算法在運(yùn)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間。(2)求表長(zhǎng)ListLength（L）求線性表L中的結(jié)點(diǎn)個(gè)數(shù)，即求表長(zhǎng)。(5)InsertList（L，i，x）在線性表L的第i個(gè)元素之前插入一個(gè)值為x 的新元素，表L的長(zhǎng)度加1。順序表是一種隨機(jī)存取結(jié)構(gòu),順序表的特點(diǎn)是邏輯上相鄰的結(jié)點(diǎn)其物理位置亦相鄰。在第i個(gè)位置插入一個(gè)結(jié)點(diǎn)的移動(dòng)次數(shù)為ni+1（2）刪除：順序表上做刪除運(yùn)算，平均要移動(dòng)表中約一半的結(jié)點(diǎn)（n1）/2，平均時(shí)間復(fù)雜度也是O(n)。方法二：p﹥data和p﹥next④指針變量p和結(jié)點(diǎn)變量*p的關(guān)系: 指針變量p的值——結(jié)點(diǎn)地址, 結(jié)點(diǎn)變量*p的值——結(jié)點(diǎn)內(nèi)容: （1） 頭插法建表：算法： p=(ListNode *)malloc(sizeof(ListNode))。② //將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中④（2） 尾插法建表：算法： p=(ListNode *)malloc(sizeof(ListNode))。if (head==NULL) head=p。③//將新結(jié)點(diǎn)插到*r之后它具有兩個(gè)優(yōu)點(diǎn):具體算法：r=head。\n39。//生成新結(jié)點(diǎn) //將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中}算法：p=head。amp。 j++。 else return NULL。時(shí)間復(fù)雜度：在等概率假設(shè)下，平均時(shí)間復(fù)雜度為：為n/2=O(n)（2）按結(jié)點(diǎn)值查找：具體算法：ListNode *p=headnext。//掃描下一結(jié)點(diǎn) return p。③ snext=pnext。②//使r指向被刪除的結(jié)點(diǎn)ai pnext=rnext③?！趩捂湵碇?，將終端結(jié)點(diǎn)的指針域NULL改為指向表頭結(jié)點(diǎn)或開(kāi)始結(jié)點(diǎn)即可。判斷空鏈表的條件為rear==rearnext。 {//假設(shè)A，B為非空循環(huán)鏈表的尾指針LinkList p=Anext。 free(Bnext)。 return B。而在單循環(huán)鏈表中，從任一結(jié)點(diǎn)出發(fā)都可訪問(wèn)到表中所有結(jié)點(diǎn)，這一優(yōu)點(diǎn)使某些運(yùn)算在單循環(huán)鏈表上易于實(shí)現(xiàn)。③將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來(lái)，為雙（向）循環(huán)鏈表。 DListNode *s=malloc(sizeof(DListNode))。 sdata=x。 sprior=pprior。 snext=p。 ppriornext=s。 pprior=s。//① }//③上述兩個(gè)算法的時(shí)間復(fù)雜度均為O(1)。第三章 棧和隊(duì)列（Last In First Out）的線性表，簡(jiǎn)稱為L(zhǎng)IFO表。當(dāng)一個(gè)棧中的元素較多而棧使用的空間超過(guò)共享空間的一半時(shí)，只要另一個(gè)棧的元素不多，那么前者就可以占用后者的部分存儲(chǔ)空間。棧頂指針就是鏈表的頭指針。 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列，順序隊(duì)列實(shí)際上是一個(gè)受限的線性表。在非空隊(duì)列里，頭指針始終指向隊(duì)頭元素，而隊(duì)尾指針始終指向隊(duì)尾元素的下一位置。只不過(guò)當(dāng)頭尾指針指向向量上界（QueueSize1）時(shí)，其加1操作的結(jié)果是指向向量的下界0。 if(i+1==QueueSize) i=0。 else i++。 i=(i+1)%QueueSize；循環(huán)隊(duì)列中，由于入隊(duì)時(shí)尾指針向前追趕頭指針；出隊(duì)時(shí)頭指針向前追趕尾指針，造成隊(duì)空和隊(duì)滿時(shí)頭尾指針均相等。約定入隊(duì)前，測(cè)試尾指針在循環(huán)意義下加1后是否等于頭指針。④ 入隊(duì) Qdata[Qrear]=x。 Qfront=(Qfront+1)%QueueSize。⑥取隊(duì)頭元素 return Qdata[Qfront]。鏈隊(duì)列的基本運(yùn)算:（帶頭結(jié)點(diǎn)）（1） 構(gòu)造空隊(duì)：Qrear=Qfront；Qrearnext=NULL。 //*p鏈到原隊(duì)尾結(jié)點(diǎn)后 //隊(duì)尾指針指向新的尾（4） 出隊(duì)：當(dāng)隊(duì)列長(zhǎng)度大于1時(shí)，只需修改頭結(jié)點(diǎn)指針，尾指針不變s=Qfrontnext。 return x。x=sdata。 因?yàn)橛蓄^結(jié)點(diǎn)，所以用了next①和鏈棧類似，無(wú)須考慮判隊(duì)滿的運(yùn)算及上溢。第四章 多維數(shù)組和廣義表:一般采用順序存儲(chǔ)方法表示數(shù)組。 a11,a12,…,a1n,a21,a22,…,a2n,……，am1,am2,…，amn（2）列優(yōu)先順序按行優(yōu)先順序存儲(chǔ)的二維數(shù)組Amn地址計(jì)算公式LOC(aij)=LOC(a11)+[(i1)n+j1]d (注：此公式下界為1，如下界為0，則公式變?yōu)閇in+j])按列優(yōu)先順序存儲(chǔ)的二維數(shù)組Amn地址計(jì)算公式LOC(aij)=LOC(a11)+[(j1)m+i1]d(注：此公式下界為1，如下界為0，則公式變?yōu)閇jm+i])按行優(yōu)先順序存儲(chǔ)的三維數(shù)組Amnp地址計(jì)算公式LOC(aijk)=LOC(a111)+[(i1)np+(j1)p+k1]d (注：此公式下界為1，如下界為0，則公式變?yōu)閇inp+jp+k])，可以對(duì)矩陣中有許多值相同或值為零的元素的矩陣，采用壓縮存儲(chǔ)。矩陣元素aij和數(shù)組元素sa【k】之間的關(guān)系是k=i(i+1)/2+j i≥j 0≤kn(n+1)/21 k=j(j+1)/2+i i＜j 0≤kn(n+1)/21對(duì)稱矩陣的地址計(jì)算公式：LOC(aij)=LOC(sa[0])+[I(I+1)/2+J]d，其中I=max(i,j)，J=min(i,j)（2）三角矩陣：以主對(duì)角線劃分，三角矩陣有上三角和下三角兩種。①上三角矩陣中aij和sa[k]之間的對(duì)應(yīng)關(guān)系k=i(2ni+1)/2+ji 當(dāng)i≤j k=n(n+1)/2 當(dāng)i＞j②下三角矩陣中aij和sa[k]之間的對(duì)應(yīng)關(guān)系k=i(i+1)/2+j 當(dāng)i≥j k=n(n+1)/2 當(dāng)i＜j三角矩陣的壓縮存儲(chǔ)結(jié)構(gòu)是隨機(jī)存取結(jié)構(gòu)。稀疏矩陣進(jìn)行壓縮存儲(chǔ)通常有兩類方法：順序存儲(chǔ)(三元組表)和鏈?zhǔn)酱鎯?chǔ)(十字