第2次課第2章線性表.ppt

1、2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,1,2.1 線性表的邏輯結(jié)構(gòu) 2.2 線性表的順序存儲 2.3 線性表的鏈式存儲 2.4 順序表和鏈表的比較,第二章 線性表,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,2,2.1 線性表的邏輯結(jié)構(gòu),2.1.1 線性表的定義 2.1.2 線性表的基本運算,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,3,2.1.1 線性表的定義 線性表是線性結(jié)構(gòu)的一般形式.是最簡單且最常用的一種數(shù)據(jù)結(jié)構(gòu)。 線性結(jié)構(gòu)的特點是數(shù)據(jù)元素之間是一種線性關(guān)系，數(shù)據(jù)元素“一個接一個的排列”。在一個線性表中數(shù)據(jù)元素的類型是相同的，或者說線性表是由同一類型的數(shù)據(jù)元素構(gòu)成的線性結(jié)構(gòu)。 線性表是具有相同數(shù)據(jù)類型的n(

2、n=0)個數(shù)據(jù)元素的有限序列，通常記為： (a1，a2， ai-1，ai，ai+1，an),2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,4,(a1，a2， ai-1，ai，ai+1，an) 其中n為表長， n0 時稱為空表。表中相鄰元素之間存在著順序關(guān)系。將 ai-1 稱為 ai 的直接前趨，ai+1 稱為 ai 的直接后繼。就是說：對于ai，當 i=2，.，n 時，有且僅有一個直接前趨ai-1，當i=1，2，.，n-1 時，有且僅有一個直接后繼ai+1，而 a1是表中第一個元素，它沒有前趨，an是最后一個元素無后繼。 需要說明的是：ai為序號為i的數(shù)據(jù)元素（i=1,2,n），通常我們將它的數(shù)據(jù)類型抽象

3、為datatype，datatype根據(jù)具體問題而定。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,5,例1 分析26 個英文字母組成的英文表,（ A, B, C, D, , Z）,例2 分析學生情況登記表,數(shù)據(jù)元素都是記錄; 元素間關(guān)系是線性,數(shù)據(jù)元素都是字母; 元素間關(guān)系是線性,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,6,2.1.2 線性表的基本運算, 線性表初始化：Init_List(L) 求線性表的長度：Length_List(L) 取表元：Get_List(L,i) 按值查找：Locate_List(L,x) 插入操作：Insert_List(L,i,x) 刪除操作：Delete_List(L,i)

4、,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,7,線性表基本運算應(yīng)用舉例,已知兩個集合A和B，求新的集合A = AB。 算法思路 利用兩個線性表LA和LB分別表示兩個集合A和B。 對線性表作如下操作：擴大線性表LA，將存在于LB而不存在于LA的元素插入到LA中。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,8,線性表基本運算應(yīng)用舉例,void union(List ,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,9,2.2 線性表的順序存儲,2.2.1 順序表 2.2.2 順序表上基本運算的實現(xiàn) 2.2.3 順序表應(yīng)用舉例,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,10,2.2.1 順序表的表示,用一組地址連續(xù)的存儲單元依次存儲線性

5、表的元素，可通過數(shù)組Vn來實現(xiàn)。,把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中的存儲結(jié)構(gòu)。,線性表的順序表示又稱為順序存儲結(jié)構(gòu)或順序映像。,順序存儲定義：,順序存儲方法：,簡言之，邏輯上相鄰，物理上也相鄰,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,11,線性表順序存儲特點：,1. 邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰； 2. 若已知表中首元素在存儲器中的位置，則其他元素存放位置亦可求出。計算方法是： 設(shè)首元素a1的存放地址為LOC(a1)（稱為首地址）， 設(shè)每個元素占用存儲空間（地址長度）為L字節(jié)， 則表中任一數(shù)據(jù)元素的存放地址為： LOC(ai) = LOC(a1) + L *（i-1）,注意

6、：C語言中的數(shù)組的下標從0開始， 即：Vn的有效范圍是V0Vn-1,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,12,線性表的長度是可變的，因此，數(shù)組的容量需設(shè)計的足夠大。 #define MAXSIZE /*足夠大的整數(shù)*/ datatype dataMAXSIZE; 線性表中的數(shù)據(jù)從data0 開始依次存放，但當前線性表中的實際元素個數(shù)可能未達到MAXSIZE多個，因此需用一個變量:int last來記錄當前線性表中最后一個元素在數(shù)組中的位置，即 last 起一個指針的作用，始終指向線性表中最后一個元素。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,13,從結(jié)構(gòu)性上考慮，通常將 data 和 last 封裝成

7、一個結(jié)構(gòu): typedef struct datatype dataMAXSIZE; int last; SeqList; 定義一個順序表的存儲變量： SeqList L;,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,14,通常用一個指向SeqList 類型的指針對實現(xiàn)順序表的操作更為方便： SeqList *L; L是一個指針變量，通過“L=(SeqList )malloc(sizeof (SeqList);”操作來獲得順序表的存儲空間，L中存放的是順序 表的地址。 線性表的表長表示為：(*L).last1，記為： Llast+1 線性表中數(shù)據(jù)元素順序存儲的基址為：Ldata 線性表中數(shù)據(jù)元素的存儲或

8、表示為： Ldata0 LdataLlast,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,15,typedef struct datatype DataMaxsize; int last SeqList , *L,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,16,2.2.2 順序表上基本運算的實現(xiàn), 順序表的初始化 順序表的初始化即構(gòu)造一個空表，對表是一個加工型的運算，因此，將 L設(shè)為指針參數(shù)，首先動態(tài)分配存儲空間，然后，將表中 last 指針置為1，表示表中沒有數(shù)據(jù)元素。,【算法2-1】順序表初始化 SeqList *init_SeqList( ) SeqList *L; L= (SeqList *)mallo

9、c(sizeof(SeqList); /*申請順序表的存儲空間*/ if (L) L-last=-1; return L; /*返回順序表的存儲地址*/ else return 1; /*申請不成功，返回錯誤代碼-1 */ ,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,17,設(shè)調(diào)用函數(shù)為主函數(shù)，主函數(shù)對初始化函數(shù)的調(diào)用如下： main() SeqList *L; L=Init_SeqList(); ,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,18,插入運算 (1) 運算說明： 線性表的插入是指在表的第i個位置上插入一個值為 x 的新元素。,插入前：(a1, a2, . , ai-1, ai , ai+1 , .

10、 , an) 插入后：(a1, a2, . , ai-1, x, ai, ai+1 , . , an ) 其中：1in+1，n是原來的表長。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,19,順序表的插入：,這是我的地方，我要住這兒！,行，我們這就給你倒地兒！,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,20,(2)運算實現(xiàn) 【算法2-2】 順序表的插入算法 int Insert_SeqList(SeqList *L,int i,DataType x) int j; if (L-last=MAXSIZE-1) printf(表滿); return -1; /*表空間已滿，不能插入，返回錯誤代碼-1*/ if (i

11、L-last+2) /*檢查插入位置的正確性*/ printf(位置錯) ; return 0; /*插入位置參數(shù)錯，返回錯誤代碼0 */ for (j=L-last;j=i-1;j-) L-dataj+1=L-dataj; /*結(jié)點移動 */ L-datai-1=x; /*新元素插入*/ L-last+; /*last指向新的最后元素*/ return 1; /*插入成功，返回成功代碼1 */ ,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,21,(3) 本算法中注意以下問題： 順序表中數(shù)據(jù)區(qū)域有MAXSIZE個存儲單元，所以在向順序表中做插入時先檢查表空間是否滿了，在表滿的情況下不能再做插入，否則產(chǎn)生

12、溢出錯誤。 要檢驗插入位置的有效性，這里 i 的有效范圍是：1in+1，其中 n 為原表長。 注意數(shù)據(jù)的移動方向。 表長的修改。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,22,(4) 插入算法的時間性能分析:,順序表上的插入運算，時間主要消耗在了數(shù)據(jù)的移動上，在第i個位置上插入 x ，從 ai 到 an 都要向下移動一個位置，共需要移動 ni1個元素，而 i 的取值范圍為 ：1 i n+1，即有 n1個位置可以插入。設(shè)在第i個位置上作插入的概率為Pi，則平均移動數(shù)據(jù)元素的次數(shù)： 設(shè)：Pi=1/ (n+1) ，即為等概率情況，則： 這說明：在順序表上做插入操作需移動表中一半的數(shù)據(jù)元素。顯然時間復雜度為

13、(n)。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,23,刪除運算 (1) 運算說明： 線性表的刪除運算是指將表中第 i 個元素從線性表中去掉。,刪除前：(a1, a2, . , ai-1, ai , ai+1 , . , an) 刪除后：(a1, a2, . , ai-1, ai+1 , . , an ) 其中：1in，n是原來的表長。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,24,(2)運算實現(xiàn) 【算法 2-3】 順序表的刪除算法 int Delete_SeqList(SeqList *L,int i) int j; if (iL-last+1) /*檢查空表及刪除位置的合法性*/ printf (不存

14、在第i個元素); return 0; /*不能刪除，返回錯誤代碼0*/ for (j=i;jlast;j+) L-dataj-1=L-dataj; /*數(shù)據(jù)元素向前移動*/ L-last-; /* last指向新的最后元素*/ return 1; /*刪除成功，返回成功代碼1*/ ,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,25,(3)本算法中注意以下問題： 刪除第i個元素，i的取值為 1in ,否則第i個元素不存在，因此，要檢查刪除位置的有效性。 當表空時不能做刪除，因表空時 Llast的值為-1，條件（iLlast+1）也包括了對表空的檢查。 刪除ai 之后，該數(shù)據(jù)已不存在，如果需要，先取出，再做

15、刪除。 修改表長。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,26,(4) 刪除算法的時間性能分析: 與插入運算相同，其時間主要消耗在了移動表中元素上，刪除第i個元素時，其后面的元素 ai+1an 都要向上移動一個位置，共移動了 n-i 個元素，所以平均移動數(shù)據(jù)元素的次數(shù)： 在等概率情況下，pi =1/ n，則： 結(jié)論：順序表上作刪除運算時大約需要移動表中一半的元素。算法的時間復雜度為(n)。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,27,按值查找,(1) 運算說明： 線性表中的按值查找是指在線性表中查找與給定值x相等的數(shù)據(jù)元素。,(2) 運算實現(xiàn)： 【算法2-4】 順序表的按值查找算法 int Locat

16、ion_SeqList(SeqList *L,DataType x) int i; i=0; while (ilast /查找成功，返回數(shù)據(jù)元素在順序表中的存儲位置 ,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,28,(3)按值查找算法的時間性能分析: 本算法的主要運算是給定值x與表中元素的比較。 顯然比較的次數(shù)與x在表中的位置有關(guān)，也與表長有關(guān)。 當a1=x 時，比較一次成功。 當an=x時，比較n次成功。等概率情況下，查找成功的平均比較次數(shù)為：,即：平均比較次數(shù)為（n+1）/2，時間性能為O(n)。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,29,2.2.3 順序表應(yīng)用舉例,例2-1 將順序表(a1，a2，

17、. ，an)重新排列為以a1為界的兩部分：a1 前面的值均比 a1 小，a1 后面的值都比a1大。 劃分的方法有多種，下面介紹的劃分算法其思路簡單，性能較差。 基本思路： 從第二個元素開始到最后一個元素，逐一向后掃描： 當前數(shù)據(jù)元素 aI 比 a1 大時，表明它已經(jīng)在 a1 的后面，不必改變它與 a1 之間的位置，繼續(xù)比較下一個。 當前結(jié)點若比 a1 小，說明它應(yīng)該在 a1 的前面，此時將它上面的元素都依次向下移動一個位置，然后將它置入最上方。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,30,總的移動次數(shù)為 ： 即最壞情況下移動數(shù)據(jù)時間性能為()。,【算法2-5】 順序表劃分算法 void part(

18、SeqList *L) int i,j; datatype x,y; x=L-data0; /*將基準數(shù)據(jù)元素置入 x 中*/ for (i=1;ilast;i+) if (L-dataidatai; for (j=i-1;j=0;j-) /*前面所有數(shù)據(jù)元素向后移動*/ Ldataj+1=L-dataj; L-data0=y; /*將當前元素置入最前面位置*/ ,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,31,例2-2 有順序表A和B，其元素均按從小到大的升序排列，編寫一個算法將它們合并成一個順序表C，要求C的元素也是從小到大的升序排列。 算法思路： 依次掃描通過A和B的元素，比較當前的元素的值，將

19、較小值的元素賦給C，如此直到一個線性表掃描完畢，然后將未完的那個順序表中余下部分賦給C即可。C的容量要能夠容納A、B兩個線性表相加的長度。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,32,【算法2-6】順序表的合并 void merge(SeqList *A, SeqList *B, SeqList *C) int i,j,k; i=0; j=0; k=0; while ( ilast ,算法的時間性能是O(m+n)，其中m是A的表長，n是B的表長。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,33,例2-3 比較兩個線性表的大小。兩個線性表的比較依據(jù)下列方法：設(shè)A、B是兩個線性表，均用向量表示，表長分別為m和

20、n。 A和B分別為 A 和 B 中除去最大共同前綴后的子表。 例如A=(x,y,y,z,x,z)， B=(x,y,y,z,y,x,x,z)，兩表最大共同前綴為 (x,y,y,z) 。則A=（x,z），B=（y,x,x,z），若A= B= 空表，則A=B；若A=空表且B空表，或兩者均不空且A首元素小于B首元素，則AB。,算法思路： 首先找出A、B的最大共同前綴；然后求出A和B，之后在按比較規(guī)則進行比較，AB 函數(shù)返回1；A=B返回0；AB返回-1。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,34,【算法2-7】兩個順序表的比較 int compare( int A , int B , int m, in

21、t n) int i=0, j, ms=0, ns=0; /* ms、ns為A、B的長度*/ while (i0 | ms0 ,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,35,2.1 線性表的邏輯結(jié)構(gòu) 2.1.1 線性表的定義 2.1.2 線性表的基本運算 2.2 線性表的順序存儲 2.2.1 順序表 2.2.2 順序表上基本運算的實現(xiàn) 2.2.3 順序表應(yīng)用舉例,上節(jié)課回顧,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,36,2.3 線性表的鏈式存儲,2.3.1 單鏈表 2.3.2 單鏈表上基本運算的實現(xiàn) 2.3.3 循環(huán)鏈表 2.3.4 雙向鏈表 2.3.5 靜態(tài)鏈表 2.3.6 鏈表應(yīng)用舉例,2020年8月

22、9日,數(shù)據(jù)結(jié)構(gòu)講義,37,2.3.1 單鏈表 鏈表是通過一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素的，那么怎樣表示出數(shù)據(jù)元素之間的線性關(guān)系呢？ 為建立起數(shù)據(jù)元素之間的線性關(guān)系，對每個數(shù)據(jù)元素ai，除了存放數(shù)據(jù)元素的自身的信息ai之外，還需要和ai一起存放其后繼元素ai+1所在的存儲單元的地址，這兩部分信息組成一個“結(jié)點” 。,因此，n個元素的線性表可以通過每個結(jié)點的指針域拉成了一個“鏈”，稱之為鏈表。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,38,結(jié)點定義如下： typedef struct node datatype data; struct node *next; LNode，*LinkList

23、； 定義頭指針變量： LinkList H；,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,39,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,40,(1) 在鏈表的頭部插入結(jié)點建立單鏈表,2.3.2 單鏈表上基本運算的實現(xiàn)建立單鏈表,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,41,【算法2-8】在表頭插入結(jié)點，建立線性表的鏈式存儲,linklist creat_ linklist() linklist L=null; LNode *s; int x; scanf(“%d”,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,42,1.創(chuàng)立單鏈表(在表頭添加),linklist creat_ linklist() linklist L=nul

24、l; LNode *s; int x; scanf(“%d”,x=10,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,43,1.創(chuàng)立單鏈表(在表頭添加),linklist creat_ linklist() linklist L=null; LNode *s; int x; scanf(“%d”,x=20,L,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,44,linklist creat_ linklist() linklist L=null; LNode *s; int x; scanf(“%d”,x=30,1.創(chuàng)立單鏈表(在表頭添加),2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,45,linklist creat_ li

25、nklist() linklist L=null; LNode *s; int x; scanf(“%d”,x=40,1.創(chuàng)立單鏈表(在表頭添加),2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,46,(2) 在單鏈表的尾部插入結(jié)點建立單鏈表,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,47,linklist creat_ linklist() linklist L=null; Lnode *s,*r=null; int x; scanf(“%d”,【算法2-9】在表尾插入結(jié)點，建立線性表的鏈式存儲,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,48,L,r,linklist creat_ linklist() linklist

26、 L=null; Lnode *s,*r=null; int x; scanf(“%d”,x=10,1.創(chuàng)立單鏈表(在表尾添加),2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,49,linklist creat_ linklist() linklist L=null; Lnode *s,*r=null; int x; scanf(“%d”,x=20,1.創(chuàng)立單鏈表(在表尾添加),2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,50,linklist creat_ linklist() linklist L=null; Lnode *s,*r=null; int x; scanf(“%d”,x=30,1.創(chuàng)立單鏈表(在表

27、尾添加),2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,51,linklist creat_ linklist() linklist L=null; Lnode *s,*r=null; int x; scanf(“%d”,x=40,1.創(chuàng)立單鏈表(在表尾添加),2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,52,linklist creat_ linklist() linklist L=null; Lnode *s,*r=null; int x; scanf(“%d”,x = -1,null,1.創(chuàng)立單鏈表(在表尾添加),2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,53,頭結(jié)點問題的說明： 頭結(jié)點的加入完全是為了運算的方便，它

28、的數(shù)據(jù)域無定義，指針域中存放的是第一個數(shù)據(jù)結(jié)點的地址，空表時為空。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,54,求表長,(1) 設(shè)L是帶頭結(jié)點的單鏈表 【算法2-10(a)】求帶頭結(jié)點的單鏈表表長 int Length_LinkList1 (LinkList L) LNode *p=L; /*p指向頭結(jié)點*/ int j=0; while (pnext) p=pnext; j+; /*p所指的是第 j 個結(jié)點*/ return j; (2) 設(shè)L是不帶頭結(jié)點的單鏈表。 【算法2-10(b)】求單鏈表表長 int Length_LinkList2 (LinkList L) LNode *p=L; /

29、*非空表情況下，p所指的是第一個結(jié)點*/ int j=0; while (p) j+; p=pnext; return j; ,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,55,查找操作,【算法2-11(a)】單鏈表中的按序號查找 LNode *Get_LinkList(LinkList L, int i) /*在單鏈表L中查找第i個元素結(jié)點，找到返回其指針，否則返回空*/ LNode *p=L; int j=0; while (pnext!=NULL ,(1)按序號查找 Get_Linklist(L,i) 算法思路：從鏈表的第一個元素結(jié)點起，判斷當前結(jié)點是否是第i個，若是，則返回該結(jié)點的指針，否則繼續(xù)

30、后一個，表結(jié)束為止。沒有第個結(jié)點時返回空指針。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,56,(2)按值查找即定位 Locate_LinkList(L,x) 算法思路：從鏈表的第一個元素結(jié)點起，判斷當前結(jié)點值是否等于x，若是，返回該結(jié)點的指針，否則繼續(xù)后一個，表結(jié)束為止。找不到時返回空指針。,【算法2-11(b)】單鏈表中的按值查找 LNode *Locate_LinkList( LinkList L, datatype x) /*在單鏈表L中查找值為x的結(jié)點，找到后返回其指針，否則返回空*/ LNode *p=Lnext; while (p!=NULL 算法2-11(a)、(b)的時間復雜度均為O

31、(n)。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,57,插入操作,(1)后插結(jié)點：設(shè)p指向單鏈表中某結(jié)點，s指向待插入的值為x的新結(jié)點，將*s插入到*p的后面。 操作如下： s-next=p-next; p-next=s; 注意：兩個指針的操作順序不能交換。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,58,(2) 前插結(jié)點：設(shè)指向鏈表中某結(jié)點，指向待插入的值為x的新結(jié)點，將*s插入到*p的前面。與后插不同的是：首先要找到*p的前驅(qū)*q，然后再完成在*q之后插入*s，設(shè)單鏈表頭指針為L，操作如下： q=L; while (q-next!=p) q=q-next; /*找*p的直接前驅(qū)*/ s-next=q-n

32、ext; q-next=s;,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,59,(3) 插入運算 Insert_LinkList(L,i,x) 算法思路： 找到第i-1個結(jié)點；若存在繼續(xù)2，否則結(jié)束； 申請、填裝新結(jié)點； 將新結(jié)點插入，結(jié)束。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,60,【算法2-12】單鏈表中的插入算法 int Insert_LinkList( LinkList L, int i, datatype x) /*在單鏈表L的第i個位置上插入值為x的元素*/ LNode *p,*s; p=Get_LinkList(L, i-1); /*查找第i-1個結(jié)點*/ if (p=NULL) print

33、f(參數(shù)i錯誤); return 0; /*第i-1個不存在不能插入*/ else s=(LNode *)malloc(sizeof(LNode); /*申請、填裝結(jié)點*/ sdata=x; snext=pnext; /*新結(jié)點插入在第i-1個結(jié)點的后面*/ pnext=s; return 1; 算法2-12的時間復雜度為O(n)。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,61,刪除操作,(1) 刪除結(jié)點： 設(shè)p指向單鏈表中某結(jié)點，刪除*p。要實現(xiàn)對結(jié)點*p的刪除，首先要找到*p的前驅(qū)結(jié)點*q，然后完成指針的操作即可。指針的操作由下列語句實現(xiàn)： q-next=p-next; free(p); 顯然找

34、*p前驅(qū)的時間復雜性為O(n)。 若要刪除*p的后繼結(jié)點(假設(shè)存在)，則可以直接完成： s=p-next; p-next=s-next; free(s); 該操作的時間復雜性為O(1) 。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,62,(2) 刪除運算 Del_LinkList(L,i) 算法思路： 找到第i-1個結(jié)點；若存在繼續(xù)2，否則結(jié)束； 若存在第i個結(jié)點則繼續(xù)3，否則結(jié)束； 刪除第i個結(jié)點，結(jié)束。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,63,【算法2-13】單鏈表中的刪除算法 int Del_LinkList(LinkList L，int i) /*刪除單鏈表L上的第i個數(shù)據(jù)結(jié)點 LinkLis

35、t p,s; p=Get_LinkList(L,i-1); /*查找第i-1個結(jié)點*/ if (p=NULL) printf(第i-1個結(jié)點不存在); return -1; else if (pnext=NULL) printf(第i個結(jié)點不存在); return 0; else s=pnext; /*s指向第i個結(jié)點*/ pnext=snext; /*從鏈表中刪除*/ free(s); /*釋放*s */ return 1; ,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,64,上節(jié)課回顧,單鏈表 單鏈表的基本運算 建立 求表長 查找 插入 刪除 頭結(jié)點,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,65,(2)

36、R-data=P-data;,練習,對以下單鏈表分別執(zhí)行下列各程序段,并畫出結(jié)果示意圖.,(1) L=P-next;,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,66,(3) R-data=P-next-data;,練習,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,67,(4) P-next-next-next-data=P-data;,練習,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,68,(5) T=P; while(T!=NULL) T-data=(T-data)*2; T=T-next; ,練習,(6) T=P; while(T-next!=NULL) T-data=(T-data)*2; T=T-next; ,2

37、020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,69,(5) T=P; while(T!=NULL) T-data=(T-data)*2; T=T-next; ,練習,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,70,(6) T=P; while(T-next!=NULL) T-data=(T-data)*2; T=T-next; ,練習,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,71,(7) P=(Lnode*)malloc(sizeof(Lnode); P-data=10; R-next=P; P-next=S;,練習,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,72,P,練習,(7) P=(Lnode*)malloc(sizeof

38、(Lnode); P-data=10; R-next=P; P-next=S;,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,73,P,10,練習,(7) P=(Lnode*)malloc(sizeof(Lnode); P-data=10; R-next=P; P-next=S;,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,74,P,10,練習,(7) P=(Lnode*)malloc(sizeof(Lnode); P-data=10; R-next=P; P-next=S;,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,75,P,10,練習,(7) P=(Lnode*)malloc(sizeof(Lnode); P-data

39、=10; R-next=P; P-next=S;,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,76,(8) T=L; T-next=P-next; free(P);,練習,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,77,2.3.3 循環(huán)鏈表,對于單鏈表而言，最后一個結(jié)點的指針域是空指針，如果將該鏈表頭指針置入該指針域，則使得鏈表頭尾結(jié)點相連，就構(gòu)成了單循環(huán)鏈表。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,78,在單循環(huán)鏈表上的操作基本上與非循環(huán)鏈表相同，只是將原來判斷指針是否為NULL變?yōu)槭欠袷穷^指針而已，沒有其它較大的變化。 對于單循環(huán)鏈表則可以從表中任意結(jié)點開始遍歷整個鏈表；另外，有時對鏈表常做的操作是在表尾、表頭

40、進行，此時可以改變一下鏈表的標識方法，不用頭指針而用一個指向尾結(jié)點的指針R來標識，可以使得操作效率提高。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,79,例：對兩個單循環(huán)鏈表H1 、H2的連接操作，是將H2的第一個數(shù)據(jù)結(jié)點接到H1的尾結(jié)點，如用頭指針標識，則需要找到第一個鏈表的尾結(jié)點，其時間復雜性為O(n)，而鏈表若用尾指針R、R2來標識，則時間性能為O(1)。操作如下： P= Rnext; /*保存第一個表的頭結(jié)點指針*/ R-next=R2-next-next; /*頭尾連接*/ free(R2-next); /*釋放第二個表的頭結(jié)點*/ R2-next=P; /*組成循環(huán)鏈表*/,2020年8月

41、9日,數(shù)據(jù)結(jié)構(gòu)講義,80,2.3.4 雙向鏈表,單鏈表的結(jié)點中只有一個指向其后繼結(jié)點的指針域next，找后繼的時間性能是O(1)，找前驅(qū)的時間性能是O(n)；可以付出空間的代價使得找前驅(qū)的時間性達到O(1)：每個結(jié)點再加一個指向前驅(qū)的指針域。 用這種結(jié)點組成的鏈表稱為雙向鏈表。 結(jié)點形式如下：,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,81,(2) 和單鏈表類似，雙向鏈表通常也是用頭指針標識，也可以帶頭結(jié)點和做成循環(huán)結(jié)構(gòu)。,(1) 雙向鏈表的結(jié)點定義如下： typedef struct dlnode datatype data; struct dlnode *prior,*next; DLNode,*

42、DLinkList;,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,82,(3) 在雙向鏈表中，通過某結(jié)點的指針p既可以直接得到它的后繼結(jié)點的指針p-next，也可以直接得到它的前驅(qū)結(jié)點的的指針p-prior。 p-prior-next = p = p-next-prior,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,83,(4) 在雙向鏈表中插入一個結(jié)點： 設(shè)p指向雙向鏈表中某結(jié)點，s指向待插入的值為x的新結(jié)點，將*s插入到*p的前面。操作如下： s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; 上面指針操作的順序不是唯一的，但也不是任意的，操作必須要放到

43、操作的前面完成，否則*p的前驅(qū)結(jié)點的指針就丟掉了。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,84,(5) 在雙向鏈表中刪除指定結(jié)點： 設(shè)p指向雙向鏈表中某結(jié)點，刪除*p。 操作如下：p-prior-next=p-next; p-next-prior=p-prior; free(p);,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,85,順序表和鏈表的比較,順序存儲有3個優(yōu)點： (1) 方法簡單，各種高級語言中都有數(shù)組，容易實現(xiàn)。 (2) 不用為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲開銷。 (3) 順序表具有按元素序號隨機訪問的特點。 順序存儲兩個缺點： 在順序表中做插入刪除操作時，平均移動大約表中一半的元素，因此

44、對n較大的順序表效率低。 需要預(yù)先分配足夠大的存儲空間，估計過大，可能會導致順序表后部大量閑置；預(yù)先分配過小，又會造成溢出。 鏈表的優(yōu)缺點恰好與順序表相反。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,86,在實際中怎樣選取存儲結(jié)構(gòu)呢？通常有以下幾點考慮： 基于存儲的考慮 對線性表的長度或存儲規(guī)模難以估計時，不宜采用順序表；鏈表不用事先估計存儲規(guī)模，但鏈表的存儲密度較低。 基于運算的考慮 如果經(jīng)常做的運算是按序號訪問數(shù)據(jù)元素，順序表優(yōu)于鏈表； 在順序表中做插入、刪除操作時平均移動表中一半的元素，在鏈表中作插入、刪除操作，雖然也要找插入位置，但操作主要是比較操作，從這個角度考慮后者優(yōu)于前者。 基于環(huán)境的考

45、慮 順序表容易實現(xiàn)，任何高級語言中都有數(shù)組類型，鏈表的操作是基于指針的，相對來講前者簡單些，也是用戶考慮的一個因素。 總之，兩種存儲結(jié)構(gòu)各有長短，選擇那一種由實際問題中的主要因素決定。通?！拜^穩(wěn)定”的線性表選擇順序存儲，而頻繁做插入刪除的即動態(tài)性較強的線性表宜選擇鏈式存儲。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,87,2.3.6 單鏈表應(yīng)用舉例,【例2-5】已知單鏈表H如下圖所示，寫一算法將其逆置。,算法思路： 依次取原鏈表中的每個結(jié)點，將其作為第一個結(jié)點插入到新鏈表中去，指針p用來指向原表中當前結(jié)點，p為空時結(jié)束。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,88,【算法2-15】單鏈表逆置 void r

46、everse (Linklist H) LNode *p; p=Hnext; /*p指向第一個數(shù)據(jù)結(jié)點*/ Hnext=NULL; /*將原鏈表置為空表H*/ while (p) q=p; p=pnext; qnext=Hnext; /*將當前結(jié)點插到頭結(jié)點的后面*/ Hnext=q; 該算法只是對鏈表中順序掃描一遍即完成了逆置，所以時間性能為O(n)。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,89,【例2-6】 已知單鏈表H如下圖所示，寫一算法，刪除其重復結(jié)點，即實現(xiàn)如下圖所示的操作。,算法思路： 用指針p指向第一個數(shù)據(jù)元素結(jié)點，從它的后繼結(jié)點開始到表的結(jié)束，查找與其值相同的結(jié)點并刪除之；p指向下

47、一個結(jié)點；依此類推，p指向最后結(jié)點時算法結(jié)束。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,90,【算法2-16】單鏈表中刪除重復結(jié)點 void pur_LinkList(LinkList H) LNode *p,*q,*r; p=Hnext; /*p指向第一個結(jié)點*/ if(p=NULL) return; while (p-next) q=p; while (qnext) /*從*p的后繼開始找重復結(jié)點*/ if (qnextdata=pdata) r=qnext; /*找到重復結(jié)點，用r指向，刪除*r */ qnext=rnext; free(r); /*if*/ else q=q-next; /*

48、while(q-next)*/ p=pnext; /*p指向下一個，繼續(xù)*/ /*while(pnext)*/ 該算法的時間性能為O(n2)。,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,91,void pur_LinkList(LinkList H) LNode *p,*q,*r; p=Hnext; /*p指向第一個結(jié)點*/ if(p=NULL) return; while (p-next) q=p; while (qnext) /*從*p的后繼開始找重復結(jié)點*/ if (qnextdata=pdata) r=qnext; /*找到重復結(jié)點，用r指向，刪除*r */ qnext=rnext; free

49、(r); /*if*/ else q=q-next; /*while(q-next)*/ p=pnext; /*p指向下一個，繼續(xù)*/ /*while(pnext)*/ ,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,92,void pur_LinkList(LinkList H) LNode *p,*q,*r; p=Hnext; /*p指向第一個結(jié)點*/ if(p=NULL) return; while (p-next) q=p; while (qnext) /*從*p的后繼開始找重復結(jié)點*/ if (qnextdata=pdata) r=qnext; /*找到重復結(jié)點，用r指向，刪除*r */ qne

50、xt=rnext; free(r); /*if*/ else q=q-next; /*while(q-next)*/ p=pnext; /*p指向下一個，繼續(xù)*/ /*while(pnext)*/ ,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)講義,93,void pur_LinkList(LinkList H) LNode *p,*q,*r; p=Hnext; /*p指向第一個結(jié)點*/ if(p=NULL) return; while (p-next) q=p; while (qnext) /*從*p的后繼開始找重復結(jié)點*/ if (qnextdata=pdata) r=qnext; /*找到重復結(jié)點，用r指向，刪除*r */ qnext=rnext; free(r); /*if*/ else q=q-next; /*while(q-next)*/ p=pnext; /*p指向下一個，繼續(xù)*/ /*while(pnext)*/ ,2020年8月9日,數(shù)據(jù)結(jié)構(gòu)