【導(dǎo)讀】存儲(chǔ)結(jié)構(gòu)，以及線性表的基本運(yùn)算以及實(shí)現(xiàn)算法。線性表由一組具有相同屬性的數(shù)據(jù)元素構(gòu)成。義廣泛，在不同的具體情況下，可以有不同的含義。，an組成的有限序列，其中序列中元素的個(gè)數(shù)n稱為線性表。例2、從1978年到1983年各種型號(hào)的計(jì)算機(jī)擁有量的變化情況。前趨，而僅有一個(gè)直接后繼a2；讀取線性表L第i個(gè)數(shù)據(jù)元素，要求滿足1≤i≤Getlen。數(shù)據(jù)元素，返回一特殊值（例如0），表示查找失敗。n+1，要求1≤i≤Getlen+1，插入后原表長(zhǎng)增1。在線性表L中刪除序號(hào)為i的數(shù)據(jù)元素，刪除后使序號(hào)為i+1,刪除后表長(zhǎng)減１。素在存儲(chǔ)器中占用的空間（字節(jié)數(shù)）相同。據(jù)元素在內(nèi)存所占字節(jié)的大小，就可求出第i個(gè)數(shù)據(jù)元素的地址。這樣，一個(gè)線性表的順序存儲(chǔ)結(jié)構(gòu)需要兩個(gè)分量。data和length之間的內(nèi)在聯(lián)系，通常將它們定義在一個(gè)結(jié)構(gòu)類型中。算，并討論各算法時(shí)間復(fù)雜度?，F(xiàn)建空表的功能。于等于1和小于等于線性表的實(shí)際長(zhǎng)度。

　　

【正文】 空間表 ， 可用于管理結(jié)點(diǎn)的分配和回收 。 當(dāng)用戶需要結(jié)點(diǎn)時(shí) ， 就從 AV為頭指針的鏈中摘下第一個(gè)結(jié)點(diǎn)分配出去 ，并通過(guò)指針 p指示它；頭指針 AV移動(dòng)到可利用空間表的第二個(gè)結(jié)點(diǎn) ， 該指針實(shí)際指示的是下一次可分配的結(jié)點(diǎn)地址 ，用語(yǔ)句可表示為： 2020/11/23 64 if (AV!=1) { p=AV。 AV=st[AV].next。 } 當(dāng)用戶不再需要某個(gè)結(jié)點(diǎn)時(shí)，只需把它鏈入 AV所指示的鏈表的最前端，并讓 AV指示它即可，用語(yǔ)句表示為： st[p]=AV。 AV=p。 012345678123456781data nextheadAVAVAV未用空間 創(chuàng)建頭結(jié)點(diǎn) 插入鏈表 插入多個(gè)后鏈表狀態(tài)(a) (b) (c) (d)30 3060782586123255012345678123456781data nextAV012345678113456781data nexthead012345678623871415data nexthead822386圖 220 靜態(tài)鏈表結(jié)構(gòu) 從圖 220中可以看出 ， 表頭結(jié)點(diǎn)一般在第 0個(gè)位置 。 它的 next指針指向鏈表中第一個(gè)結(jié)點(diǎn) 。 鏈表中最后一個(gè)結(jié)點(diǎn)的 next指針為 1， 表示鏈表結(jié)束 。 2020/11/23 65 線性表的應(yīng)用 —— 一元多項(xiàng)式計(jì)算 一元多項(xiàng)式表示 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的 典型應(yīng)用之一是 在高等數(shù)學(xué)的 多項(xiàng)式方面。本節(jié)主要討論采用鏈表結(jié)構(gòu)表示的一元多項(xiàng)式的操作處理。在數(shù)學(xué)上，一個(gè)一元多項(xiàng)式 Pn(x) 可以表示為 ： Pn(x)=a0+a1x+a2x2+… +anxn (最多有 n+1項(xiàng) ) aixi是多項(xiàng)式的第 i項(xiàng) （ 0≤i≤n） 。 其中 ai為系數(shù) ， x為自變量 ， i為指數(shù) 。 多項(xiàng)式中有 n+1個(gè)系數(shù) ， 而且是線性排列 。 一個(gè)多項(xiàng)式由多個(gè) aixi (1≤ i≤ m)項(xiàng)組成 ， 每個(gè)多項(xiàng)式項(xiàng)采用以下結(jié)點(diǎn)存儲(chǔ)： coef expn next2020/11/23 66 coef expn next 其中 ， coef數(shù)據(jù)域存放序數(shù) ci； expn數(shù)據(jù)域存放指數(shù) ei；next域是一個(gè)鏈域 ， 指向下一個(gè)結(jié)點(diǎn) 。 由此 ， 一個(gè)多項(xiàng)式可以表示成由這些結(jié)點(diǎn)鏈接而成的單鏈表 (假設(shè)該單鏈表是帶頭結(jié)點(diǎn)的單鏈表 )。 在計(jì)算機(jī)中，多項(xiàng)式可用一個(gè)線性表 listP來(lái)表示： listP=（p0， p1， p2… ， pn）。 但這種表示無(wú)法分清每一項(xiàng)的系數(shù)和指數(shù)。所以可以采用另一種表示一元多項(xiàng)式的方法： listP={（ a0， e0）， (a1， e1)， (a2， e2)， … ， (an， en) }。 在這種線性表描述中，各個(gè)結(jié)點(diǎn)包括兩個(gè)數(shù)據(jù)域，對(duì)應(yīng)的類型描述為： 2020/11/23 67 typedef struct node { double coef。 //系數(shù)為雙精度型 int expn。 //指數(shù)為正整型 struct node *next。 //指針域 }polynode。 在順序存儲(chǔ)結(jié)構(gòu)中，采用基類型為 polynode的數(shù)組表示多項(xiàng)式中的各項(xiàng)。如 p[i].coef和 p[i].expn分別表示多項(xiàng)式中第 i項(xiàng)的系數(shù)和指數(shù)。但多項(xiàng)式中，其中一些項(xiàng)的系數(shù)會(huì)為 0。如多項(xiàng)式A(x)=a0+a1x+a2x2+ a6x6+ a9x9+a15x15 中包括 16項(xiàng)，其中只有 6項(xiàng)系數(shù)不為 0。順序存儲(chǔ)結(jié)構(gòu)可以使多項(xiàng)式相加算法變得簡(jiǎn)單。但是，當(dāng)多項(xiàng)式中存在大量的零系數(shù)時(shí)，這種表示方式就會(huì)浪費(fèi)大量的存儲(chǔ)空間。為了有效利用存儲(chǔ)空間，可用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示多項(xiàng)式。 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，多項(xiàng)式中每一個(gè)非零項(xiàng)構(gòu)成鏈表中的一個(gè)結(jié)點(diǎn)，而對(duì)于系數(shù)為零的項(xiàng)則不需要表示。 （注意：表示多項(xiàng)式的鏈表應(yīng)該是有序鏈表） 2020/11/23 68 一元多項(xiàng)式相加 假設(shè)用單鏈表表示多項(xiàng)式： A(x)=12+7x+8x10+5x17 ，B(x)=8x+15x76x10， 頭指針 Ah與 Bh分別指向這兩個(gè)鏈表，如圖 221所示： 對(duì)兩個(gè)多項(xiàng)式進(jìn)行相加運(yùn)算 ， 其結(jié)果為 C(x)= 12+15x+15 x7+2x10+5x17。 如圖 222所示 。 12 0 7 1 8 10 5 17Ah8 1 15 7 6 0Bh ∧∧圖 221 合并以前的鏈表 15 1 15 7 2 10 5 17 ∧012Ch 圖 222 合并以后的鏈表 2020/11/23 69 對(duì)兩個(gè)一元多項(xiàng)式進(jìn)行相加操作的運(yùn)算規(guī)則是：假設(shè)指針 qa和 qb分別指向多項(xiàng)式 A(x)和 B(x)中當(dāng)前進(jìn)行比較的某個(gè)結(jié)點(diǎn) ，則需比較兩個(gè)結(jié)點(diǎn)數(shù)據(jù)域的指數(shù)項(xiàng) ， 有三種情況： (1) 指針 qa所指結(jié)點(diǎn)的指數(shù)值＜指針 qb所指結(jié)點(diǎn)的指數(shù)值時(shí) ， 則保留 qa指針?biāo)赶虻慕Y(jié)點(diǎn) ， qa指針后移； (2) 指針 qa所指結(jié)點(diǎn)的指數(shù)值＞指針 qb所指結(jié)點(diǎn)的指數(shù)值時(shí) ， 則將qb指針?biāo)赶虻慕Y(jié)點(diǎn)插入到 qa所指結(jié)點(diǎn)前 ， qb指針后移； (3) 指針 qa所指結(jié)點(diǎn)的指數(shù)值＝指針 qb所指結(jié)點(diǎn)的指數(shù)值時(shí) ， 將兩個(gè)結(jié)點(diǎn)中的系數(shù)相加 。 若和不為零 ， 則修改 qa所指結(jié)點(diǎn)的系數(shù)值 ， 同時(shí)釋放 qb所指結(jié)點(diǎn)；反之 ， 從多項(xiàng)式 A (x)的鏈表中刪除相應(yīng)結(jié)點(diǎn) ， 并釋放指針 qa和 qb所指結(jié)點(diǎn) 。 2020/11/23 70 多項(xiàng)式相加算法： struct polynode *add_poly(struct polynode *Ah,struct polynode *Bh) { struct polynode *qa,*qb,*s,*r,*Ch。 qa=Ahnext。qb=Bhnext。 //qa和 qb分別指向兩個(gè)鏈表的第一結(jié)點(diǎn) r=qa。Ch=Ah。 //將鏈表 Ah作為相加后的結(jié)果鏈表 while(qa!=NULLamp。amp。qb!=NULL) //兩鏈表均非空 { if(qaexp==qbexp) //兩者指數(shù)值相等 { x=qacoef+qbcoef。 if(x!=0) { qacoef=x。rnext=qa。r=qa。 s=qb++。free(s)。qa++。 } //相加后系數(shù)不為零時(shí) else{s=qa++。free(s)。s=qb++。free(s)。} } //相加后系數(shù)為零時(shí) else if(qaexpqbexp) { rnext=qa。r=qa。qa++。} //多項(xiàng)式 Ah的指數(shù)值小 else{rnext=qb。r=qb。qb++。}//多項(xiàng)式 Bh的指數(shù)值小 } 2020/11/23 71 if(qa==NULL) rnext=qb。 else rnext=qa。 //鏈接 Ah或 Bh中的剩余結(jié)點(diǎn) return (Ch)。 } 上述算法的時(shí)間復(fù)雜性為 O(n)。 采用相同的方法還可以完成多項(xiàng)式的其他運(yùn)算。 2020/11/23 72 順序表和鏈表的比較 本章介紹了線性表的邏輯結(jié)構(gòu)及它的兩種存儲(chǔ)結(jié)構(gòu)：順序表和鏈表 。 這兩種表各有短長(zhǎng) ， 在實(shí)際應(yīng)用中應(yīng)根據(jù)問(wèn)題的要求和性質(zhì)來(lái)選擇使用 。 通過(guò)前面的討論可知：順序存儲(chǔ)有三個(gè)優(yōu)點(diǎn)： (1) 方法簡(jiǎn)單 ， 各種高級(jí)語(yǔ)言中都有數(shù)組 ， 容易實(shí)現(xiàn)； (2) 不用為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)開(kāi)銷； (3) 具有按元素序號(hào)隨機(jī)訪問(wèn)的特點(diǎn) 。 但它也有兩大缺點(diǎn)： (1) 在順序表中做插入 /刪除操作時(shí) ， 平均移動(dòng)大約表中一半的元素 ， 因此當(dāng) n較大時(shí)順序表的操作效率低 。 (2) 需要預(yù)先分配足夠大的存儲(chǔ)空間 。 若估計(jì)過(guò)大 ， 容易導(dǎo)致順序表后部大量閑置；預(yù)先分配過(guò)小 ， 又會(huì)造成溢出 。 鏈表的優(yōu)缺點(diǎn)恰好與順序表相反 。 在實(shí)際中究竟怎樣選取合適的存儲(chǔ)結(jié)構(gòu) ？ 通?？煽紤]以下幾點(diǎn)： 2020/11/23 73 1． 基于空間的考慮 順序表的存儲(chǔ)空間是靜態(tài)分配的，在程序執(zhí)行前必須明確規(guī)定它的存儲(chǔ)規(guī)模。若線性表長(zhǎng)度 n變化較大，則存儲(chǔ)規(guī)模很難預(yù)先正確估計(jì)。估計(jì)太大將造成空間浪費(fèi)，估計(jì)太小又將使空間溢出機(jī)會(huì)增多。所以當(dāng)對(duì)線性表的長(zhǎng)度或存儲(chǔ)規(guī)模難以估計(jì)時(shí)，不宜采用順序存儲(chǔ)結(jié)構(gòu)。順序表的存儲(chǔ)密度為 1。 鏈表不用事先估計(jì)存儲(chǔ)規(guī)模，是動(dòng)態(tài)分配。只要內(nèi)存空間尚有空閑，就不會(huì)產(chǎn)生溢出。因此，當(dāng)線性表的長(zhǎng)度變化較大，難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，以采用動(dòng)態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu)為好。但鏈表的存儲(chǔ)密度較低。存儲(chǔ)密度是指一個(gè)結(jié)點(diǎn)中數(shù)據(jù)元素所占的存儲(chǔ)單元和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)單元之比。顯然鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)密度是小于 1的。 2020/11/23 74 2． 基于時(shí)間的考慮 隨機(jī)存取結(jié)構(gòu)，就是對(duì)表中任一結(jié)點(diǎn)都可在 O(1)時(shí)間內(nèi)直接取得。若對(duì)線性表主要做查找，很少做插入和刪除操作時(shí)，采用順序存儲(chǔ)結(jié)構(gòu)為宜；而在鏈表中按序號(hào)訪問(wèn)的時(shí)間性能為 O(n)。 所以，如果經(jīng)常做的運(yùn)算是按序號(hào)訪問(wèn)數(shù)據(jù)元素，顯然順序表優(yōu)于鏈表。 而在順序表中做插入、刪除操作時(shí)，要平均移動(dòng)表中一半的元素；尤其是當(dāng)每個(gè)結(jié)點(diǎn)的信息量較大時(shí)，移動(dòng)結(jié)點(diǎn)的時(shí)間開(kāi)銷就相當(dāng)可觀，這一點(diǎn)不應(yīng)忽視。在鏈表中的任何位置上進(jìn)行插入和刪除，都只需要修改指針。對(duì)于頻繁進(jìn)行插入和刪除的線性表，宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。若表的插入和刪除主要發(fā)生在表的首尾兩端，則宜采用尾指針表示的單循環(huán)鏈表。 2020/11/23 75 3．基于環(huán)境的考慮 順序表容易實(shí)現(xiàn)，任何高級(jí)語(yǔ)言中都有數(shù)組類型；鏈表的操作是基于指針的，其使用受語(yǔ)言環(huán)境的限制，這也是用戶應(yīng)該考慮的因素之一。 總之，兩種存儲(chǔ)結(jié)構(gòu)各有特點(diǎn)。選擇哪種結(jié)構(gòu)根據(jù)實(shí)際使用的主要因素決定。通常 “ 較穩(wěn)定 ” 的線性表選擇順序存儲(chǔ)結(jié)構(gòu)；而插 /刪頻繁 “ 動(dòng)態(tài)性 “ 較強(qiáng)的線性表宜選擇鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 2020/11/23 76 本章小結(jié) 本章主要介紹的基本概念是 ： 線性表 ：一個(gè)線性表是 n≥0個(gè)數(shù)據(jù)元素 a0， a1， a2， … ， an1的有限序列。 線性表的 順序 存儲(chǔ)結(jié)構(gòu)：在計(jì)算機(jī)中用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的各個(gè)數(shù)據(jù)元素，稱作線性表的順序存儲(chǔ)結(jié)構(gòu)。 線性表的 鏈?zhǔn)?存儲(chǔ)結(jié)構(gòu)：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)就是用一組任意的存儲(chǔ)單元 ——結(jié)點(diǎn)（可以是不連續(xù)的）存儲(chǔ)線性表的數(shù)據(jù)元素。表中每一個(gè)數(shù)據(jù)元素都由存放數(shù)據(jù)元素值的數(shù)據(jù)域和存放直接前驅(qū)或直接后繼的地址 ——指針域組成。 2020/11/23 77 循環(huán)鏈表 ：循環(huán)鏈表 (Circular Linked List)是將單鏈表的最后一個(gè)結(jié)點(diǎn)的指針指向鏈表的表頭結(jié)點(diǎn)，使整個(gè)鏈表形成環(huán)，從表中任一結(jié)點(diǎn)出發(fā)都可找到表中其它結(jié)點(diǎn)。 雙向鏈表 ：雙向鏈表中的每一個(gè)結(jié)點(diǎn)除了數(shù)據(jù)域外，還包含兩個(gè)指針域：一個(gè)指針（ next） 指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)，另一個(gè)指針（ prior） 指向它的前驅(qū)結(jié)點(diǎn)。 除基本概念以外，本章還介紹了：線性表的基本操作（初始化、插入、刪除、存取、復(fù)制、合并）、線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的表示、一元多項(xiàng)式 Pn(x)等。通過(guò)本章學(xué)習(xí)，要求讀者不僅要了解基本概念，還要掌握順序存儲(chǔ)結(jié)構(gòu)（初始化、插入操作、刪除操作）、單鏈表（單鏈表的初始化、單鏈表的插入、單鏈表的刪除）等操作。