數(shù)據(jù)結(jié)構(gòu)第三版（陳元春）　線性表

1、第2章線性表2021年5月11日星期三1第 2 章 線 性 表 知 識 點(diǎn) 線性數(shù)據(jù)結(jié)構(gòu)的定義與存儲 單鏈表的根本運(yùn)算和算法 循環(huán)鏈表的根本特點(diǎn) 雙鏈表的結(jié)點(diǎn)形式和特點(diǎn) 雙鏈表的插入和刪除運(yùn)算 難 點(diǎn) 雙鏈表插入、刪除運(yùn)算的算法 利用鏈表結(jié)構(gòu)的特點(diǎn)設(shè)計(jì)算法 要 求 熟練掌握以下內(nèi)容: 順序表存儲地址的計(jì)算 單鏈表的結(jié)構(gòu)特點(diǎn)和根本運(yùn)算 第 2 章 目 錄2-1 線性表的定義與運(yùn)算2-2 線性表的順序存儲 2-3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)小 結(jié)驗(yàn)證性實(shí)驗(yàn)2 線性表子系統(tǒng)自主設(shè)計(jì)實(shí)驗(yàn)多項(xiàng)式求和實(shí)驗(yàn)室完成，要求寫實(shí)驗(yàn)報(bào)告作業(yè)與預(yù)習(xí)題 線性結(jié)構(gòu)的根本特征:1集合中必存在唯一的一個“第一元素；2集合中必存在唯

2、一的一個 “最后元素;3除最后元素在外，均有 唯一的后繼；4除第一元素之外，均有 唯一的前驅(qū)。線性結(jié)構(gòu) 是 一個數(shù)據(jù)元素的有序次序集52-1 線性表的定義與運(yùn)算2-1-1 線性表的定義1線性表的定義 線性表是具有相同數(shù)據(jù)類型的nn=0個數(shù)據(jù)元素的有限序列，通常記為： (a1，a2， ai-1，ai，ai+1，an) 其中n為表長， n0 時稱為空表。 在線性表中相鄰元素之間存在著順序關(guān)系。對于元素ai 而言，ai-1 稱為 ai 的直接前趨，ai+1 稱為 ai 的直接后繼。即：2線性表舉例1簡單的線性表 例如一年12個月： 1，2，3，4，5，6，7，8，9，10，11，12 在C或C+ +

3、語言中我們可以把它們定義為數(shù)值型。 又例如26個英文字母表： a，b，c，d，e，f，g，x，y，z 在C或C+ +語言中我們可以把它們定義為字符型。2復(fù)雜的線性表 例如我們曾經(jīng)在緒論中引用的一個學(xué)生入學(xué)情況表表2-1可以是用戶自定義的學(xué)生類型如C語言中的結(jié)構(gòu)體或數(shù)據(jù)庫管理系統(tǒng)中的記錄。 由于表格中各記錄之間存在“一對一的關(guān)系，所以它也是一種線性表。3線性表的二元組表示： Linearity =D，R 數(shù)據(jù)對象：D=ai 1=i=0 數(shù)據(jù)關(guān)系： ai-1, aiD，2=i=n 稱 i 為 ai 在線性表中的位序。關(guān)系中是一個序偶的集合，它表示線性表中數(shù)據(jù)元素的相鄰關(guān)系，即 ai-1領(lǐng)先ai ，

4、ai領(lǐng)先 ai+1。2-1-2 線性表的根本操作 線性表上的根本操作有： 創(chuàng)立線性表：CreateList() 初始條件：表不存在 操作結(jié)果：構(gòu)造一個空的線性表 求線性表的長度：LengthList(L) 初始條件：表L存在 操作結(jié)果：返回線性表中的所含元素的個數(shù)(3) 按值查找：SearchList(L,x)，是給定的一個數(shù)據(jù)元素。 初始條件：線性表L存在 操作結(jié)果：在表L中查找值為的數(shù)據(jù)元素，其結(jié)果返回在L中首次出現(xiàn)的值為的那個元素的序號或地址，稱為查找成功； 否那么，在L中未找到值為的數(shù)據(jù)元素，返回一個特殊值表示查找失敗。(4) 插入操作：InsList(L,i,x) 初始條件：線性表L

5、存在，插入位置正確 (1=i=n+1,為插入前的表長)。 操作結(jié)果：在線性表L的第 i 個位置上插入一個值為 x 的新元素，這樣使原序號為 i , i+1, . , n 的數(shù)據(jù)元素的序號變?yōu)?i+1,i+2, . , n+1，插入后表長=原表長+1。(5) 刪除操作：DelList(L,i) 初始條件：線性表L存在，1=i=n。 操作結(jié)果：在線性表L中刪除序號為i的數(shù)據(jù)元素，刪除后使序號為 i+1, i+2,., n 的元素變?yōu)樾蛱枮?i, i+1,.,n-1，新表長原表長-。(6) 顯示操作：ShowList(L) 初始條件：線性表L存在，且非空。 操作結(jié)果：顯示線性表L中的所有元素。其他可

6、根據(jù)實(shí)際需要設(shè)計(jì)2-2-1 順序表 線性表的順序存儲是指在用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，我們把用這種存儲形式存儲的線性表稱為順序表。順序表的邏輯順序和物理順序是一致的。如圖2-1 所示。 設(shè) a 1 的存儲地址LOC(a 1)為首地址B，每個數(shù)據(jù)元素占d個存儲單元，那么第i個數(shù)據(jù)元素的地址為： LOC(ai)=LOC(a 1)+(i-1)*d (1=i=n) 即： LOC(ai)=B+(i-1)*d (1=ilast=-1; / 初始化順序表為空 return Lq;/ 返回指向順序表的指針Lq 此時，順序表只有一個指針Lq指向，該順序表空間并無名字。 如果順序表在主函數(shù)中

7、作了如下定義，那么順序表L的空間分配在內(nèi)存區(qū)。void main() SeqList L; / 這里的L是順序表類型的結(jié)構(gòu)體變量，而非指針 InitList(&L); / 調(diào)用InitList()函數(shù)初始化順序表L 由于順序表L在內(nèi)存區(qū)已分配空間，初始化函數(shù)只需設(shè)置好last指示標(biāo)志的初值即可，代碼如下：void InitSeqList(SeqList *Lq) Lq-last=-1; / 初始化順序表為空2插入運(yùn)算 線性表的插入是指在表的第i個位置上插入一個值為 x 的新元素，插入后使原表長為 n的表，成為表長為 n+1 的表。 順序表插入結(jié)點(diǎn)運(yùn)算的步驟如下： (1) 將anai 之間的所有

8、結(jié)點(diǎn)依次后移，為新元素讓出第i個位置； (2) 將新結(jié)點(diǎn)x插入到第i個位置； (3) 修改 last 指針相當(dāng)于修改表長，使之仍指向最后一個元素。 算法如下： int InsList(SeqList *L，int i，datatype x) int j; if (L-last=MAXLEN-1) printf (“順序表已滿！); return(-1); / 表滿，不能插入 if (iL-last+2) / 檢查給定的插入位置的正確性 printf (“位置出錯！); return(0); for(j=L-last;j=i-1;j-) / 結(jié)點(diǎn)移動 L-dataj+1=L-dataj; L-d

9、atai-1=x; / 新元素插入 L-last+; / last仍指向最后元素 return (1); / 插入成功，返回 動畫演示要注意的問題是： 1 順序表中數(shù)據(jù)區(qū)域有MAXLEN個存儲單元，所以在插入時先檢查順序表是否已滿，在表滿的情況下不能再做插入，否那么產(chǎn)生溢出錯誤。2檢驗(yàn)插入位置的有效性，這里 i 的有效范圍是：1=i=n+1，其中 n 為原表長。3 注意數(shù)據(jù)的移動方向，必須從原線性表最后一個結(jié)點(diǎn)(an)起往后移動，如圖2-3所示。 插入算法的時間性能分析如下： 順序表上的插入運(yùn)算，時間主要消耗在數(shù)據(jù)的移動上，在第i個位置上插入x，從an到ai都要向下移動一個位置，共需要移動ni

10、1個元素，而i的取值范圍為：1in1，即有n1個位置可以插入。 設(shè)在第i個位置上作插入的概率為Pi，那么平均移動數(shù)據(jù)元素的次數(shù)： 設(shè)Pi=1(n1)，即在等概率情況下，那么： 這說明：在順序表上做插入操作需移動表中一半的數(shù)據(jù)元素。顯然時間復(fù)雜度為O(n)。3 刪除運(yùn)算 線性表的刪除運(yùn)算是指將表中第 i 個元素從線性表中去掉，刪除后使原表長為 n 的線性表： (a1，a2，. ，ai-1，ai，ai+1，.，an)變?yōu)楸黹L為 n1 的線性表： (a1，a2，. ，ai-1， ai+1，. ，an-1)。 i 的取值范圍為：1=i=n 。 順序表刪除結(jié)點(diǎn)運(yùn)算的步驟如下： (1) 將ai+1an 之

11、間的結(jié)點(diǎn)依次順序向前移動。 (2) 修改last指針相當(dāng)于修改表長使之仍指向最后一個元素。 順序表中的刪除元素ai前后的情況如圖2- 4所示。 刪除算法如下：int DeleteList (SeqList *Lq;int i) int j; if(iLq-last+1) / 檢查空表及刪除位置的合法性 printf (不存在第i個元素); return (0); for(j=i;jlast;j+) / 向上移動 Lq-dataj-1=Lq-dataj; Lq-last-; / last仍指向最后元素 return(1); / 刪除成功 動畫演示 本算法請注意以下問題： 1首先要檢查刪除位置的有

12、效性，刪除第i個元素，i的取值為： 1=ilast的值為-1，條件iL-last+1也包括了對表空的檢查。 3刪除 ai 之后，該數(shù)據(jù)那么已不存在，如果需要，必須先取出 ai 后，再將其刪除。 刪除算法的時間復(fù)雜度分析： 與插入運(yùn)算相同，其時間主要消耗在了移動表中的元素上，刪除第i個元素時，其后面的元素ai1an都要向前移動一個位置，共移動了ni個元素，所以平均移動數(shù)據(jù)元素的次數(shù)： 在等概率情況下，pi1n，那么：這說明在順序表上作刪除運(yùn)算時大約需要移動表中一半的元素，顯然該算法的時間復(fù)雜度為O(n)。 4 按值查找 線性表中的按值查找是指在線性表中查找與給定值x相等的數(shù)據(jù)元素。算法如下：in

13、t LocationSeqList(SeqList *L, datatype x) int i=0; while(idatai!= x) i+; if (iL-last) return -1; else return i; / 返回的是存儲位置 上述算法的主要運(yùn)算是比較。顯然比較的次數(shù)與x在表中的位置和表的長度MAXLEN有關(guān)。當(dāng)a1x時，比較一次成功；當(dāng)anx時比較n次成功。平均比較次數(shù)為 (n1)/2，時間復(fù)雜度為O(n)。預(yù)習(xí)題鏈表的存儲結(jié)構(gòu)有何特點(diǎn)？在進(jìn)行鏈表的插入與刪除元素操作時應(yīng)該特別注意什么操作？什么是頭結(jié)點(diǎn)？它有什么作用？循環(huán)鏈表的結(jié)構(gòu)特點(diǎn)是什么？雙向鏈表的結(jié)構(gòu)特點(diǎn)是什么？鏈表

14、和順序表各根本操作各有什么特點(diǎn)？用一組 地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。修改指針語句的次序。鏈表的第一結(jié)點(diǎn)之前附設(shè)的一個結(jié)點(diǎn)。統(tǒng)一空表和非空表的操作。表中最后一個結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)。結(jié)點(diǎn)有兩個指針域，其一指向前驅(qū)，另一指向后繼。2-3 線性表的鏈?zhǔn)酱鎯?順序存儲的優(yōu)點(diǎn)： 可以隨機(jī)存取表中任意一個元素； 存儲位置可以用公式：B+(i-1)*d 計(jì)算； 節(jié)約存儲空間。2順序存儲的缺點(diǎn)： 對順序表作插入、刪除時需要通過移動大量的數(shù)據(jù)元素，影響了運(yùn)行效率。 線性表預(yù)先分配空間時，必須按最大空間分配，存儲空間得不到充分的利用。 表的容量難以擴(kuò)充對有些高級語言而言。2-3-1 線性鏈表1.

15、線性鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)1用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素。2單鏈表的每個結(jié)點(diǎn)由一個數(shù)據(jù)域和一個指針域組成： 結(jié)點(diǎn)中存放數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域；存放其后繼地址的域稱為指針域。3單鏈表的存取必須從頭指針開始 如線性表a1,a2,a3,a4,a5,a6,a7,a8對應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)如圖2-6所示。 Ha1 a2 an 圖2-7 單鏈表示意圖 首先必須將第一個結(jié)點(diǎn)的地址1000放到一個頭指針變量如H中，最后一個結(jié)點(diǎn)沒有后繼，其指針域必需置空，說明此表到此結(jié)束。這樣就可以從第一個結(jié)點(diǎn)的地址開始，順著指針依次找到每個結(jié)點(diǎn)。 作為線性表的一種存儲結(jié)構(gòu)，我們考慮的是結(jié)點(diǎn)間的邏輯結(jié)構(gòu)，而對每個結(jié)點(diǎn)的

16、實(shí)際地址并不關(guān)心，所以通常的線性鏈表用圖2-7的形式表示。2. 關(guān)于頭指針、頭結(jié)點(diǎn)和開始結(jié)點(diǎn)1頭指針指向鏈表中第一個結(jié)點(diǎn)頭結(jié)點(diǎn)或無頭結(jié)點(diǎn)時的開始結(jié)點(diǎn)的指針。2頭結(jié)點(diǎn)在開始結(jié)點(diǎn)之前附加的一個結(jié)點(diǎn)。3開始結(jié)點(diǎn)在鏈表中，存儲第一個數(shù)據(jù)元素a1的結(jié)點(diǎn)。頭結(jié)點(diǎn)有何作用？3. 結(jié)點(diǎn)的描述 單向鏈表由一個個結(jié)點(diǎn)構(gòu)成，在C或C+中可以用“結(jié)構(gòu)體指針來描述。typedef struct linknode / 定義結(jié)點(diǎn)的結(jié)構(gòu)體 datatype data; struct linknode *next; LinkNode，*LinkList; / 定義結(jié)點(diǎn)類型LinkNode， / 定義結(jié)點(diǎn)指針類型LinkList

17、 上面定義的LinkNode是結(jié)點(diǎn)的類型，LinkList是指向LinkNode類型結(jié)點(diǎn)的指針類型。為了增強(qiáng)程序的可讀性，通常將標(biāo)識一個鏈表的頭指針說明為LinkList類型的變量，如LinkList L。當(dāng)L有定義時，值要么為NULL，那么表示一個空表；要么為第一個結(jié)點(diǎn)的地址，即鏈表的頭指針；將操作中用到指向某結(jié)點(diǎn)的指針變量說明為LinkNode *類型，如LinkNode *p；那么語句： p=new LinkNode;完成了申請一塊LinkNode類型的存儲單元的操作，并將其地址賦值給變量p，如圖2-8所示。2-3-2 線性表上根本運(yùn)算的實(shí)現(xiàn)1.建立線性鏈表1在鏈表的頭部建立線性表的算法

18、：圖2-9 在頭部插入建立單鏈表圖LinkNode *CreateLinkList()/ 頭插法建立線性鏈表 LinkNode *head,*p,*s; int x; int z=1,n=0; / n用來記錄表長 head=NULL; / 初始化頭指針為空 printf(ntt建立一個線性表); printf(ntt說明：請逐個輸入整數(shù)，結(jié)束標(biāo)記為-1！n); while(z) printf(tt輸入：); scanf(%d,&x); if (x!=-1)/ 輸入-1完成建立 s=new LinkNode; n+; / 插入一個結(jié)點(diǎn)，結(jié)點(diǎn)數(shù)n增加1 s-data=x; s-next=head;

19、 head=s; else z=0; / 輸入循環(huán)結(jié)束 return head;/返回創(chuàng)立鏈表的頭指針 動畫演示2在鏈表的尾插入結(jié)點(diǎn)建立線性表LinkNode *CreateLinkList()/尾插法建立線性鏈表 LinkNode *head,*p,*s; int x, z=1,n=0;/ n用來存儲表長 head=NULL; p=head; printf(ntt建立一個線性表); printf(ntt說明：請逐個輸入整數(shù)，結(jié)束標(biāo)記為-1！n); while(z) printf(tt輸入：); scanf(%d,&x); if(x!=-1)/ 輸入數(shù)據(jù)不等于-1那么構(gòu)造結(jié)點(diǎn)并插入 s=new

20、 LinkNode;/ 給新結(jié)點(diǎn)開辟空間 s-data=x;/ 構(gòu)造新結(jié)點(diǎn) s-next=NULL; if(!head) head=s; / 將構(gòu)造好的結(jié)點(diǎn)插入鏈表尾部 else p-next=s; p=s; n+; / 表長加1 else z=0;/ 輸入-1那么循環(huán)結(jié)束 return head;/ 返回建立好的單鏈表頭指針 為了方便操作，有時在鏈表的頭部參加一個“頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的類型與數(shù)據(jù)結(jié)點(diǎn)一致，標(biāo)識鏈表的頭指針變量L中存放該結(jié)點(diǎn)的地址，這樣即使是空表，頭指針變量L也不為空。頭結(jié)點(diǎn)的參加使得上述問題不再存在。 頭結(jié)點(diǎn)的參加完全是為了運(yùn)算的方便，統(tǒng)一了空表和非空表的操作，它的數(shù)據(jù)域無定義，

21、指針域中存放的是第一個數(shù)據(jù)結(jié)點(diǎn)的地址，空表時為空，如圖2-11(a)所示；非空線性鏈表如圖2-11b。 圖2-11b 帶頭結(jié)點(diǎn)非空線性鏈表H a1 a2 an 2. 求表長 算法思路：設(shè)一個移動指針和計(jì)數(shù)器n，初始化后，所指結(jié)點(diǎn)后面假設(shè)還有結(jié)點(diǎn)，向后移動，計(jì)數(shù)器加1。(1) 設(shè)L是帶頭結(jié)點(diǎn)的線性鏈表(線性表的長度不包括頭結(jié)點(diǎn)) 算法如下：int LenList1 (LinkList L) Node * p=L; / p指向頭結(jié)點(diǎn) int n=0; while (p-next) p=p-next; n+ / p所指的是第 n 個結(jié)點(diǎn) return n; 2 設(shè)L是不帶頭結(jié)點(diǎn)的線性鏈表，算法如下：

22、int LenList2 (LinkList L) Node * p=L; int n; if (p=NULL) return 0; / 空表的情況 n=1; / 在非空表的情況下，p所指的是第一個結(jié)點(diǎn); while (p-next ) p=p-next; n+ return n; 上述算法的時間復(fù)雜度均為O(n)。 很明顯，帶頭結(jié)點(diǎn)的鏈表的算法更簡潔，邏輯更清楚，因此在以后的算法中不加說明那么認(rèn)為線性鏈表是帶頭結(jié)點(diǎn)的。 指針的小結(jié) 假設(shè)p是一個pointer類型，應(yīng)正確區(qū)分指針型變量、指針、指針?biāo)傅慕Y(jié)點(diǎn)和結(jié)點(diǎn)的內(nèi)容這四個密切相關(guān)的不同概念：p的值如果有的話是一個指針，即是一個所指結(jié)點(diǎn)的地址

23、 。該指針假設(shè)不是NULL指向的某個node型結(jié)點(diǎn)用*p來標(biāo)識。結(jié)點(diǎn) *p是由兩個域組成的記錄，這兩個域分別用pdata域和pnext域來標(biāo)識，它們各有自己的值，pdata的值是一個數(shù)據(jù)元素，pnext的值是一個指針。 3查找操作1序號查找 SearchList1(L,i) 算法思路：從鏈表的第一個元素結(jié)點(diǎn)開始，判斷當(dāng)前結(jié)點(diǎn)是否是第i個，假設(shè)是，那么返回該結(jié)點(diǎn)的指針，否那么繼續(xù)下一個，直到鏈表結(jié)束。假設(shè)沒有第個結(jié)點(diǎn)那么返回空。 LinkNode *SearchList1(LinkList L,int i)/ 在帶頭結(jié)點(diǎn)的線性鏈表L中查找第i個元素結(jié)點(diǎn)，找到后返回其 /指針，否那么返回空 Lin

24、kNode *p=L; int j=0; while(p-next!=NULL&jnext; j+; if(j=i) return p; else return NULL; 2按值查找 SearchList2(L,x) 算法思路：從鏈表的第一個元素結(jié)點(diǎn)開始，判斷當(dāng)前結(jié)點(diǎn)其值是否等于 x，假設(shè)是，返回該結(jié)點(diǎn)的指針，否那么繼續(xù)下一個，直到鏈表結(jié)束。假設(shè)找不到那么返回空。算法如下：以上兩個算法的時間復(fù)雜度均為O(n)。LinkNode *SearchList2(LinkList L,datatype x) /在帶頭結(jié)點(diǎn)的線性鏈表L中查找值為x的結(jié)點(diǎn)，找到后返回其 /指針，否那么返回空 LinkNod

25、e *p=L-next; while(p!=NULL&p-data!=x) p=p-next; if(p-data=x) return p; else return NULL; 4插入1后插結(jié)點(diǎn)：設(shè)p指向線性鏈表中某結(jié)點(diǎn)，s指向待插入的值為x的新結(jié)點(diǎn)，將*s插入到*p的后面，插入示意圖如圖2-12。插入結(jié)點(diǎn)操作： s-next=p-next; p-next=s; / 兩個指針的操作順序不能交換動畫演示 圖2-13 在*p之 前插*s2前插結(jié)點(diǎn)：設(shè)p指向鏈表中某結(jié)點(diǎn)，s指向待插入的值為x的新結(jié)點(diǎn)，將*s插入到*p的前面，插入示意圖如圖2-13所示，與后插不同的是：首先要找到*p的前驅(qū)*q，然后再

26、完成在*q之后插入*s，設(shè)線性鏈表頭指針為L，操作如下： x head p q 132 與后插不同的是：首先要找到*p的前驅(qū)*q，然后再完成在*q之后插入*s，設(shè)線性鏈表頭指針為L，操作如下:q=L;while (q-next!=p) q=q-next; / 找*p的直接前驅(qū)s-next=q-next; q-next=s; 后插操作的時間復(fù)雜性為O(1)，前插操作因?yàn)橐?*p 的前驅(qū)，時間性能為O(n)； 能否優(yōu)化算法，使時間性能為O(1)呢？其實(shí)我們更關(guān)心的是數(shù)據(jù)元素之間的邏輯關(guān)系，所以仍然可以將 *s 插入到 *p 的后面，然后將-data與s-data交換即可，這樣即滿足了邏輯關(guān)系，也

27、能使得時間復(fù)雜性為O(1)。插入結(jié)點(diǎn)操作： s-next=p-next; p-next=s; / 兩個指針的操作順序不能交換 t=p-data; / 交換-data與s-data p-data=s-data; s-data=t; 3插入運(yùn)算 InsList(L,i,x) 算法思路 找到第i個結(jié)點(diǎn)，假設(shè)不存在那么結(jié)束，假設(shè)存在繼續(xù)下一步； 申請一個新結(jié)點(diǎn)，并賦值； 將新結(jié)點(diǎn)插入。void InsertList(LinkList head,int i,char x) / 插入結(jié)點(diǎn)元素 LinkNode *s,*p; p=head; int j=0; while(p!=NULL & jnext; /

28、 后移指針 if (p!=NULL) s=new LinkNode; s-data=x; / 插入結(jié)點(diǎn) s-next=p-next; / 修改指針 p-next=s; n+; / 表的長度加1 else printf(ntt線性表為空或插入位置超出! n); 這個算法的時間復(fù)雜度為O(n)。 5刪除 1刪除結(jié)點(diǎn)：設(shè)p指向線性鏈表中某結(jié)點(diǎn)，刪除*p。操作示意圖如圖2-14所示。 圖2-14 刪除*P 通過示意圖可見，要實(shí)現(xiàn)對結(jié)點(diǎn)*p的刪除，首先要找到*p的前驅(qū)結(jié)點(diǎn)*q，然后完成指針的操作即可。指針的操作由以下語句實(shí)現(xiàn)： q-next=p-next; delete (p);動畫演示 顯然找*p前驅(qū)

29、的時間復(fù)雜性為O(n)。假設(shè)要刪除*p的后繼結(jié)點(diǎn)(假設(shè)存在)，那么可以直接完成： s=p-next; p-next=s-next; delete(s); 該操作的 時間復(fù)雜性為O(1) 。2刪除運(yùn)算思路 如果鏈表為空，那么不能進(jìn)行刪除操作； 查找值為x的結(jié)點(diǎn)，并得到其先驅(qū)結(jié)點(diǎn)； 將值為x的結(jié)點(diǎn)從鏈表中刪除。算法如下： LinkList DeleteList(LinkList head,char x) LinkNode *p,*q; if (head=NULL) printf(tt單鏈表為空！n); return head; if (head-next=NULL) if (head-data!=

30、x)/ 只有一個結(jié)點(diǎn)，并且不是待刪結(jié)點(diǎn) printf(tt未找到待刪除的結(jié)點(diǎn)！); return head; else / 只有一個結(jié)點(diǎn)，并且是待刪結(jié)點(diǎn) delete head; / 釋放被刪除結(jié)點(diǎn)的空間 return NULL; q=head; p=head-next; while(p!=NULL&p-data!=x)/ 查找待刪除結(jié)點(diǎn) q=p; p=p-next; if (p!=NULL) q-next=p-next; delete p; n-; printf(tt %c已經(jīng)被刪除！,x); else printf(tt未找到待刪除的結(jié)點(diǎn)！n); 算法的時間復(fù)雜度為O(n)。通過上面的學(xué)習(xí)

31、我們可知： ( 1 ) 在線性鏈表上插入、刪除一個結(jié)點(diǎn)，必須知道其前驅(qū)結(jié)點(diǎn)。 ( 2 ) 線性鏈表不具有按序號隨機(jī)訪問的特點(diǎn)，只能從頭指針開始一個個順序進(jìn)行。2-3-3 循環(huán)鏈表1特點(diǎn) 將線性單鏈表中最后一個結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個鏈表頭尾結(jié)點(diǎn)相連形成一個環(huán)就構(gòu)成了單循環(huán)鏈表。如圖2-15所示。2-15 帶頭結(jié)點(diǎn)的單循環(huán)鏈表a非空表b空表HanHa12在循環(huán)鏈表上的操作 循環(huán)鏈表上的操作和非循環(huán)鏈表上的操作根本相同，差異在于算法中循環(huán)條件不是判斷指針是否為空P-NEXT=NULL，而是判斷指針是否為頭指針： P-NEXT=head;3在循環(huán)鏈表中設(shè)尾指針可以簡化某些操作 線性鏈表只能從頭結(jié)

32、點(diǎn)開始遍歷整個鏈表，而對于單循環(huán)鏈表那么可以從表中任意結(jié)點(diǎn)開始遍歷整個鏈表，不僅如此，有時對鏈表常做的操作是在表尾、表頭進(jìn)行，此時可以改變一下鏈表的標(biāo)識方法，不用頭指針而用一個指向尾結(jié)點(diǎn)的指針T來標(biāo)識，可以使得操作效率得以提高。當(dāng)知道其尾指針T后，其另一端的頭指針是T-next-next表中代頭結(jié)點(diǎn)，僅改變兩個指針值即可，其運(yùn)算時間復(fù)雜度為O(1)。 例如：對兩個單循環(huán)鏈表H1 、H2的連接操作，是將H2的第一個數(shù)據(jù)結(jié)點(diǎn)接到H1的尾結(jié)點(diǎn)，如用頭指針標(biāo)識，那么需要找到第一個鏈表的尾結(jié)點(diǎn)，其時間復(fù)雜性為O(n)，而鏈表假設(shè)用尾指針T1 、T2來標(biāo)識，那么時間性能為O(1)。操作如下： p= T1

33、next; /保存T1 的頭結(jié)點(diǎn)指針 T1-next=T2-next-next; / 頭尾連接 free(T2-next); / 釋放第二個表的頭結(jié)點(diǎn) T2-next=p; / 組成循環(huán)鏈表圖2-16 兩個用尾指針標(biāo)識的單循環(huán)鏈表的連接4. 關(guān)于存儲密度1存儲密度是指結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲空間和整個結(jié)點(diǎn)結(jié)構(gòu)所占的存儲空間之比。即： 順序表的存儲密度等于1，而鏈表的存儲密度小于1。2采用鏈?zhǔn)酱鎯Ρ炔捎庙樞虼鎯φ加酶嗟拇鎯臻g，是因?yàn)殒準(zhǔn)酱鎯Y(jié)構(gòu)增加了存儲其后繼結(jié)點(diǎn)地址的指針域。3存儲空間完全被結(jié)點(diǎn)值占用的存儲方式稱為緊湊存儲；否那么稱為非緊湊存儲。顯然，順序存儲是緊湊存儲，而鏈?zhǔn)酱鎯κ欠蔷o湊存

34、儲。存儲密度d值越大，表示數(shù)據(jù)結(jié)構(gòu)所占的存儲空間越少。整個結(jié)點(diǎn)實(shí)際分配的存儲位結(jié)點(diǎn)數(shù)據(jù)占的存儲位存儲密度=d2-3-4 雙向鏈表1單向鏈表的缺點(diǎn) 單向鏈表只能順指針往后尋找其它結(jié)點(diǎn)。假設(shè)要尋找結(jié)點(diǎn)的前驅(qū)，那么需要從表頭指針出發(fā)?？朔鲜鋈秉c(diǎn)可以采用雙向鏈表。2雙向鏈表 雙向鏈表由一個數(shù)據(jù)域和兩個指針域組成。1結(jié)點(diǎn)的結(jié)構(gòu)如圖2-17所示。圖2-17 雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)2空的雙向循環(huán)鏈表如圖2-18所示。ABCDhead3非空雙向循環(huán)鏈表如圖2-19所示。 圖2-19 非空雙向循環(huán)鏈表3雙鏈表的C或C+語言描述 struct cdlist datatype data;/結(jié)點(diǎn)數(shù)據(jù) struct cd

35、list *front;/指向先前結(jié)點(diǎn)的指針 struct cdlist *rear; /指向后繼結(jié)點(diǎn)的指針4雙鏈表的操作1刪除結(jié)點(diǎn)具體操作描述： p-front-rear=p-rear;p-rear-front=p-front;delete p;2插入結(jié)點(diǎn)具體操作描述：p-frony=q;p-rear=q-rear; q-rear-front=p;q-rear=p; q P1線性表是一種最簡單的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素之間存在著一對一的關(guān)系。其存儲方法通常采用順序存儲和鏈?zhǔn)酱鎯Α?線性表的順序存儲可以采用結(jié)構(gòu)體的形式，它含有兩個域。一個整型的長度域，用以存放表中元素的個數(shù)；另一個數(shù)組域，用來存放元素，其類型可以根據(jù)需要而定。順序存儲的最大優(yōu)點(diǎn)是可以隨機(jī)存取，且存儲空間比較節(jié)約，而缺點(diǎn)是表的擴(kuò)充困難，插入、刪除要做大量的元素移動。3線性表的鏈?zhǔn)酱鎯κ峭ㄟ^結(jié)點(diǎn)之間的鏈接而得到的。根據(jù)鏈接方式又可以分為：單鏈表、雙鏈表和循環(huán)鏈表等。 小 結(jié)4單鏈表有一個數(shù)據(jù)域data和一個指針域