哈工大數據結構1

1、第第2章章 線性表線性表 2.1 線性表的定義與運算線性表的定義與運算非空的線性表非空的線性表 (n0) 記作：記作：（ a1,a2, ai, an）1.線性表的定義線性表的定義 線性表是由線性表是由 n (n=0)個數據元素（結點）個數據元素（結點）a1,a2, ai, an組成的有限序列。組成的有限序列。其中：其中： n為數據元素的個數，也稱為表的長度。為數據元素的個數，也稱為表的長度。當當n=0 時，稱為空表。時，稱為空表。（4） ai 是屬于某個數據對象的元素，是屬于某個數據對象的元素， 它可以是它可以是 一個數字、一個字母或一個記錄。一個數字、一個字母或一個記錄。（a1,a2, ai

2、-1, ai, ai+1, an）2. 線性表的邏輯結構線性表的邏輯結構（1）有且僅有一個開始結點）有且僅有一個開始結點a1，它沒有直接前驅。，它沒有直接前驅。（2）有且僅有一個終端結點）有且僅有一個終端結點an，它沒有直接后繼。，它沒有直接后繼。（3）其余的結點）其余的結點ai (1in) 都都有且僅有有且僅有一個直接一個直接 前驅前驅 ai-1 和一個直接后繼和一個直接后繼 ai+1 3.線性表的特性線性表的特性（3）數據元素在線性表中的位置只取決于它的序號。）數據元素在線性表中的位置只取決于它的序號。（1）結點間的邏輯關系是線性的。）結點間的邏輯關系是線性的。（2）線性表中所有數據元素的

3、數據類型是一致的。）線性表中所有數據元素的數據類型是一致的。例：例： 26個英文字母組成的字母表個英文字母組成的字母表（A，B，C、Z）例：例： 某校從某校從1978年到年到1983年各種型號的計算機擁有量的年各種型號的計算機擁有量的 變化情況。變化情況。（6，17，28，50，92，188）姓姓 名名學學 號號性性 別別年齡年齡 健康情況健康情況王小林王小林790631 男男 18 健康健康陳陳 紅紅790632 女女 20 一般一般劉建平劉建平790633 男男 21 健康健康張立立張立立790634 男男 17 健康健康 . . .例例2_3 學生健康情況登記表學生健康情況登記表 4.

4、線性表的運算線性表的運算（1）存?。┐嫒。?）插入）插入（3）刪除）刪除（4）查找）查找（5）合并）合并（6）分解）分解（7）排序）排序（8）求線性表的長度）求線性表的長度 數據的運算是定義在邏輯結構上的。數據的運算是定義在邏輯結構上的。 具體的實現則在存儲結構上進行。具體的實現則在存儲結構上進行。 運算分為運算分為: 加工型加工型：改變結構的運算。：改變結構的運算。 例：初始化線性表。插入、刪除某個結點。例：初始化線性表。插入、刪除某個結點。 引用型引用型：不改變結構的運算。：不改變結構的運算。 例：在線性表上的查找運算。例：在線性表上的查找運算。2.2 線性表的順序表示和實現線性表的順序表

5、示和實現 1. 順序表的定義順序表的定義 用一組連續(xù)的存儲單元（地址連續(xù)）依次存放線性表用一組連續(xù)的存儲單元（地址連續(xù)）依次存放線性表的各個數據元素。的各個數據元素。 即：在順序表中邏輯結構上相鄰的數據元素，其物理即：在順序表中邏輯結構上相鄰的數據元素，其物理位置也是相鄰的。位置也是相鄰的。 2. 順序表中數據元素的存儲地址順序表中數據元素的存儲地址a1a2.ai.an線性表的順序存儲示意圖線性表的順序存儲示意圖數組的下標last 存儲地址data01i-1n-1loc(a 1)=BB+dB+(i-1)*dB+(n-1)*dMAXLEN-1 只要知道順序表基地址和每個數據元素所占字節(jié)數，即可只

6、要知道順序表基地址和每個數據元素所占字節(jié)數，即可求出第求出第 i 個數據元素的存儲地址。個數據元素的存儲地址。 所以順序表具有所以順序表具有按數據元素序號按數據元素序號隨機存取的特點。隨機存取的特點。 若每個數據元素占用若每個數據元素占用 d 個字節(jié)，則第個字節(jié)，則第 i 個數據元素的存儲地個數據元素的存儲地址為：址為： loc( ai ) = loc( a1 ) + (i-1)*d (1=i=n) = B + (i-1)*d 其中：其中：loc(a1)為第為第 1 個數據元素的存儲地址，稱為基地址。個數據元素的存儲地址，稱為基地址。 3. 順序表的描述（靜態(tài)）順序表的描述（靜態(tài)） 在在C語言

7、中，一維數組在內存中占用一組連續(xù)的存儲區(qū)域。語言中，一維數組在內存中占用一組連續(xù)的存儲區(qū)域?？捎靡痪S數組來表示順序表的數據存儲?？捎靡痪S數組來表示順序表的數據存儲。typedef int datatype;datatype dataMAXLEN;int last; 線性表的數據元素線性表的數據元素 a1,a2, ai, an 可依次存入數組元素可依次存入數組元素data0, data1, datai-1.,datan-1中。中。 其中：其中： MAXLEN 是一個根據實際問題定義的足夠大的整是一個根據實際問題定義的足夠大的整數。數。 變量變量 last 用來記錄當前線性表中最后一個元素用來記錄

8、當前線性表中最后一個元素在數組中在數組中的位置的位置，起到了指針的作用，始終，起到了指針的作用，始終指向線性表中的最后一個指向線性表中的最后一個元素元素。 數據元素分別存放在數據元素分別存放在data0到到datalast中中 從從datalast+1 到到dataMAXLEN-1為空閑區(qū)為空閑區(qū) 表長為表長為last+1，即為，即為 n 當當last0時，表示表為空。時，表示表為空。從結構性考慮，通常將一個順序表封裝成一個結構（靜態(tài)）：從結構性考慮，通常將一個順序表封裝成一個結構（靜態(tài)）：typedef int datatype;typedef struct datatype dataMAX

9、LEN; int last; SeqList; / 定義定義SeqList為此種結構類型為此種結構類型Seqlist L; / 定義一個順序表定義一個順序表 （a1,a2,ai-1,x,ai,an） （a1,a2,ai-1,ai,an）（1）插入運算）插入運算 在線性表的第在線性表的第 i ( 1=ilast=MAXLEN-1) printf(“順序表已滿順序表已滿”); / 最后一個結點的位置是最后一個結點的位置是 MAXLEN-1 / 表明順序表表明順序表 已滿，不能插入。已滿，不能插入。 return( -1 ); if( iL-last+2 ) / i1 即即 ilast=n-1 L-

10、last+2=n-1+2=n+1 / i L-last+2 即即 i n+1 即即 i = n+2 / 檢查空表及插入位置合法性檢查空表及插入位置合法性 printf(“位置出錯位置出錯”); return( 0 ); / 以下處理以下處理 i 的有效范圍的有效范圍 1=ilast; j=i-1; j-) L-dataj+1=L-dataj ; / 結點依次向后移動結點依次向后移動 / 當當 i=n+1 時，時，j= L-last=n-1, i-1=n+1-1=n / 不滿足不滿足j=i-1 所以不做此循環(huán)即不移動結點所以不做此循環(huán)即不移動結點L-datai-1=x ; / 新元素插入新元素插

11、入 將將 x 放在原來放在原來 ai 的位置的位置 / 當當 i=n+1時，時， datai-1= datan= x / 將將 x 直接作為直接作為an+1 放在線性表的最后放在線性表的最后L-last+; / last仍指向最后的元素仍指向最后的元素 return( 1 )插入算法時間性能分析：插入算法時間性能分析： 順序表的插入運算，時間主要消耗在數據的移動上，在第順序表的插入運算，時間主要消耗在數據的移動上，在第 i 個位置上插入個位置上插入 x，從，從 an 到到 ai 都要向后移動一個位置，共需移都要向后移動一個位置，共需移 動動 n-i+1 個元素。個元素。 而而 i 的取值范圍為

12、：的取值范圍為： 1=i=n+1 即：有即：有 n+1 個位置可以插入。個位置可以插入。 設在第設在第 i 個位置上作插入的概率為個位置上作插入的概率為 pi 則平均移動結點的次數：則平均移動結點的次數：)1(11inPEniiI按等概率考慮：按等概率考慮： 可能插入的位置為可能插入的位置為 i=1,2,n,n+1 共共 n+1 個，個，則則 pi=1/(n+1) 所以：所以：1111)1(11)1(niniiIinninPE2)1(2)1)1()1111nnnnnn（得出：得出： 順序表插入算法平均約需移動一半結點。順序表插入算法平均約需移動一半結點。 時間復雜度為時間復雜度為O(n) （線

13、性階）（線性階） 。（a1,a2,ai-1,ai+1,an）（2）刪除運算）刪除運算 （a1,a2,ai-1,ai,ai+1,an） 將線性表的第將線性表的第 i（1=i=n)個結點刪除，使得長度為個結點刪除，使得長度為 n 的的線性表變?yōu)殚L度為線性表變?yōu)殚L度為 n-1 的線性表。的線性表。若若i=n，只需刪除終端結點，不用移動結點。，只需刪除終端結點，不用移動結點。當當1=in時，將時，將ai+1-an之間的結點依次向前移動。之間的結點依次向前移動。（共需移動（共需移動 n-i 個結點）。個結點）。修改修改 last 指針（相當于修改表長）使之仍指向最后一個指針（相當于修改表長）使之仍指向最

14、后一個結點。結點。刪除算法思想：刪除算法思想：刪除算法：刪除算法：int DelList( SeqList *L, int i ) int j; if( iL-last+1 ) / iL-last+1 即即in n為原表長為原表長 / 檢查空表及刪除位置合法性檢查空表及刪除位置合法性 printf(“不存在第不存在第 i 個結點個結點”) ; return( 0 ) ; /以下處理以下處理 i 的有效范圍的有效范圍 1=i=n for( j=i; jlast; j+ ) L-dataj-1=L-dataj ; / j=i ai+1 移到了移到了ai 的位置的位置 / j=L-last an 移

15、到了移到了 an-1 的位置的位置 / 當當 i=n 時，時，j=n 不滿足此循環(huán)條件不滿足此循環(huán)條件 L-last- ; / 當當 i=n 時，不用移動結點，表長直接減時，不用移動結點，表長直接減1 return( 1 ) ; 與插入運算相同，時間主要消耗在移動表中結點上。刪除與插入運算相同，時間主要消耗在移動表中結點上。刪除第第 i 個結點，其后面的結點個結點，其后面的結點 ai+1-an 都要向前移動一個位置，共都要向前移動一個位置，共移動移動 n-i 個結點。個結點。 若若 i=1, 最壞：最壞：O(n) 若若 i=n, 無需移動結點，直接刪除即可。最好：無需移動結點，直接刪除即可。最

16、好：O(1)i)(nPEn1iid 刪除算法時間性能分析：刪除算法時間性能分析：移動結點的平均次數：移動結點的平均次數：按等概率考慮：按等概率考慮：可能刪除的位置為可能刪除的位置為 i=1,2,n 共共 n 個，則個，則 pi=1/n 所以：所以： niniiIinninPE11)(1)(212)1(111 nnnnnninnnni得出：順序表刪除算法平均約需移動一半結點。得出：順序表刪除算法平均約需移動一半結點。 時間復雜度為時間復雜度為O(n) （線性階）。（線性階）。（3）按值查找）按值查找按值查找是指在線性表中查找與給定值按值查找是指在線性表中查找與給定值 x 相等的結點。相等的結點。

17、查找算法思想：查找算法思想：從第一個結點從第一個結點 a1 起依次和起依次和 x 比較，直到找到一個與比較，直到找到一個與 x 相等的相等的結點，則返回它的序號或在順序表中的存儲下標結點，則返回它的序號或在順序表中的存儲下標 。 若查遍整個線性表都沒有找到與若查遍整個線性表都沒有找到與 x 相等的結點，則返回相等的結點，則返回 -1。查找算法：查找算法：int LocationSeqList( SeqList *L, datatype x) int i=0 ; while ( ilast & L-datai!=x ) i+ ; if ( iL-last ) return -1 ; /

18、當當 iL-last 時肯定沒找著時肯定沒找著 else return i ; / 返回的是存儲位置返回的是存儲位置 即數組元素的下標即數組元素的下標查找算法時間性能分析：查找算法時間性能分析：查找算法的主要運算是比較。查找算法的主要運算是比較。比較次數與比較次數與 x 在表中的位置及表的長度有關。在表中的位置及表的長度有關。當當 a1=x 時，比較時，比較 1 次成功。次成功。當當 an=x 時，比較時，比較 n 次成功。次成功。平均比較次數為平均比較次數為 (n+1)/2 。時間復雜度為時間復雜度為O(n)，即線性階。即線性階。5. 順序表其他基本運算順序表其他基本運算 (動態(tài)分配順序存儲

19、結構動態(tài)分配順序存儲結構)約定約定:Data0=a1(1)初始化初始化-構造一個空的線性表構造一個空的線性表 L void InitList ( SeqList & L ) L.data = ( ListData * ) malloc ( ListSize * sizeof ( ListData ) ); if ( L.data = = NULL ) printf ( “存儲分配失敗存儲分配失敗!n” ); exit (overflow); L.length = 0; L.listsize=ListSize (2)(2)順序表的插入順序表的插入( (動態(tài)分配順序存儲結構動態(tài)分配順序存儲

20、結構) )int Insert ( SeqList &L, ListData x, int i ) /在表中第在表中第 i 個位置之前插入新元素個位置之前插入新元素 x if (i L.length +1) return error; if( L.length = = L.listSize) newbase=( ListData * ) realloc(L.date, ( listSize +listadd)* sizeof ( ListData ) ); if(!newbase) exit(overflow); L.Data=newbase; L.listsize+=listadd;

21、 q=&(L.Datai-1); /q為插入位置為插入位置 for ( p =&( L.DataL.length-1); p=q; -p) *(p+1)=*p; *q=x; L.length+; return 1; /插入成功插入成功 找找x x在表中的位置，若查找成功，返回在表中的位置，若查找成功，返回x x元素第一次出現在表元素第一次出現在表 中的位序，否則返回中的位序，否則返回-1-1int Locate-sq ( SeqList *L, ListData x ) int i = 1; /按序列下標按序列下標 while ( i = L.length & L.da

22、tai-1 != x ) i+; if ( i = 0 & i L.length ) return L.datai-1; else printf ( “參數參數 i 不合理不合理！n” ); int Length ( SeqList L ) return L.length; (4) 求表的長度求表的長度(5) 提取提取函數函數(1) (1) 集合的集合的“并并”運算運算void Union ( SeqList &A, SeqList B ) int n = Length ( A ); int m = Length ( B ); for ( int i = 0; i m; i+

23、) int x = GetData ( B, i ); /在在B中取一元素中取一元素 int k = Locate-sq (A, x); /在在A中查找它中查找它 if ( k = - -1 ) /若未找到插入它若未找到插入它 Insert ( A, x, +n ); n+; n n先先+再傳再傳參數參數6. 順序表的應用順序表的應用 void Intersection ( SeqList &A, SeqList &B ) int n = Length ( A ); int m = Length ( B ); int i = 0; while ( i data P-next結點

24、結點 node p 為指向鏈表中某一結點的指針變量。為指向鏈表中某一結點的指針變量。 *p 表示表示 指針指針 p 所指向的結點所指向的結點 。 (*p).data 或或 p-data 表示表示 p 所指向結點的數據域所指向結點的數據域 。 (*p).next 或或 p-next 表示表示 p 所指向結點的指針域所指向結點的指針域 。p=(node*)malloc(sizeof(node) =(linklist)malloc(sizeof(node) 對指針對指針 p 賦值使其指向某一新結點賦值使其指向某一新結點（按需生成一個（按需生成一個node結點類型的新結點，動態(tài)申請空間）結點類型的新結

25、點，動態(tài)申請空間）其中：其中： (node*) 進行類型轉換。進行類型轉換。sizeof(node) 求結點需占用的字節(jié)數。求結點需占用的字節(jié)數。malloc(size) 在內存中分配在內存中分配 size 個個連續(xù)可用字節(jié)連續(xù)可用字節(jié)的空間的空間結點的申請與釋放：結點的申請與釋放：free(p)系統回收系統回收 p 結點結點，即，即動態(tài)動態(tài)釋放釋放 p 指向的結點的空間指向的結點的空間 單鏈表上的基本運算：單鏈表上的基本運算：（1）建立單鏈表）建立單鏈表B A C HeadHead S 頭插法頭插法建表（在鏈表的頭部插入結點建立線性鏈表）：建表（在鏈表的頭部插入結點建立線性鏈表）： 思想：從

26、一個空表開始，重復讀入數據，生成新結點：將讀思想：從一個空表開始，重復讀入數據，生成新結點：將讀入數據存放在新結點的數據域中，然后將新結點插入到當前入數據存放在新結點的數據域中，然后將新結點插入到當前鏈表的表頭上，直到讀入結束標志為止。鏈表的表頭上，直到讀入結束標志為止。 DB A C HeadHead S 頭插法頭插法建表（在鏈表的頭部插入結點建立線性鏈表）：建表（在鏈表的頭部插入結點建立線性鏈表）： 思想：從一個空表開始，重復讀入數據，生成新結點，將讀思想：從一個空表開始，重復讀入數據，生成新結點，將讀入數據存放在新結點的數據域中，然后將新結點插入到當前入數據存放在新結點的數據域中，然后將

27、新結點插入到當前鏈表的表頭上，直到讀入結束標志為止。鏈表的表頭上，直到讀入結束標志為止。 DB A C HeadHead S 頭插法頭插法建表（在鏈表的頭部插入結點建立線性鏈表）：建表（在鏈表的頭部插入結點建立線性鏈表）： 思想：從一個空表開始，重復讀入數據，生成新結點，將讀思想：從一個空表開始，重復讀入數據，生成新結點，將讀入數據存放在新結點的數據域中，然后將新結點插入到當前入數據存放在新結點的數據域中，然后將新結點插入到當前鏈表的表頭上，直到讀入結束標志為止。鏈表的表頭上，直到讀入結束標志為止。 DB A C HeadHead S注：頭插法生成的鏈注：頭插法生成的鏈表中結點的次序和輸表中結

28、點的次序和輸入的順序相反。入的順序相反。 頭插法頭插法建表（在鏈表的頭部插入結點建立線性鏈表）：建表（在鏈表的頭部插入結點建立線性鏈表）： 思想：從一個空表開始，重復讀入數據，生成新結點，將讀思想：從一個空表開始，重復讀入數據，生成新結點，將讀入數據存放在新結點的數據域中，然后將新結點插入到當前入數據存放在新結點的數據域中，然后將新結點插入到當前鏈表的表頭上，直到讀入結束標志為止。鏈表的表頭上，直到讀入結束標志為止。 Dvoid CREATELISTF( )char x; / 逐個插入字符，以逐個插入字符，以x為結束符為結束符 node *head, *s; int n=0; / n 為鏈表表

29、長為鏈表表長 head=NULL; / 鏈表開始為空鏈表開始為空 x=getchar( ); / 讀入第讀入第1個結點的值個結點的值 while(x!=x) s=（node *）malloc(sizeof(node); / 生成新結點生成新結點 s-data=x; / 將將 x 的值存入新結點的數據域中的值存入新結點的數據域中 s-next=head; /第第1個結點鏈域為空個結點鏈域為空head=s; n+; /表長加表長加1 x=getchar(); 頭插法建表頭插法建表: : 尾插法建表：尾插法建表：尾插建表可使生尾插建表可使生成的結點次序和成的結點次序和輸入的順序相同輸入的順序相同算法

30、思想：算法思想： 將新結點插入到當前鏈表的表尾上。將新結點插入到當前鏈表的表尾上。 可增加一個尾指針可增加一個尾指針 r r ，使其始終指向鏈表的尾結點。，使其始終指向鏈表的尾結點。A C B 尾插法建表：尾插法建表：head r S rD 尾插建表可使生尾插建表可使生成的結點次序和成的結點次序和輸入的順序相同輸入的順序相同void CREATLISTR( ) char x; / 逐個插入字符，以逐個插入字符，以 x 為為 結束結束符符 node *head, *s, *r; head=NULL; / 鏈表開始為空鏈表開始為空 r=NULL; / 尾指針初值為空尾指針初值為空 int n=0;

31、 / n 為鏈表表長為鏈表表長 x=getchar(); / 讀入第讀入第1個結點的值個結點的值 while(x!=x) / x為輸入結束符為輸入結束符 s=( node * ) malloc(sizeof(node); / 生成新結點生成新結點s-data=x; / 將將x 的值存入新結點的數據域中的值存入新結點的數據域中 if (head=NULL) head=s;else r-next=s;r=s; / r 始終指向鏈表的尾結點始終指向鏈表的尾結點n+; / 表長加表長加1 x=getchar(); if(r!=NULL) r-next=NULL; / 保證尾結點的鏈域為空保證尾結點的鏈

32、域為空尾插法建表：尾插法建表：尾插法建表分析：尾插法建表分析： 上述尾插法建表由于沒有設頭結點（附加），因此上述尾插法建表由于沒有設頭結點（附加），因此開始結點和其它結點的插入處理并不一樣。開始結點和其它結點的插入處理并不一樣。算法思想：算法思想： 設設頭結點頭結點，使第一個結點和其余結點的插入操作一致。，使第一個結點和其余結點的插入操作一致。 尾插法建表的改進算法尾插法建表的改進算法增加頭結點：增加頭結點： 頭結點的數據域：可有可無頭結點的數據域：可有可無 頭結點的指針域：為指向第一個結點的指針。頭結點的指針域：為指向第一個結點的指針。改進的尾插法建表算法：改進的尾插法建表算法：帶頭結點的單

33、鏈表：帶頭結點的單鏈表：特點：特點：無論鏈表是否為空，其頭指針是指向頭結點的非空指針。無論鏈表是否為空，其頭指針是指向頭結點的非空指針。所以對于尾插法建表，表的第所以對于尾插法建表，表的第 1 個結點和其它結點的操作一致。個結點和其它結點的操作一致。heada1 an 頭結點頭結點開始結點開始結點非空表：除頭結點外還有其他結點非空表：除頭結點外還有其他結點終端結點終端結點空表：只有空表：只有1個頭結點個頭結點head頭結點頭結點void CREATLISTR1( ) / 帶頭結點的尾插法建立單鏈表帶頭結點的尾插法建立單鏈表char x; int n=0; node *head, *s, *r;

34、 head=(node*)malloc(sizeof(node); / 生成頭結點生成頭結點 r=head; /尾指針初值指向頭結點尾指針初值指向頭結點 x=getchar(); while(x!=x) / x為輸入結束符為輸入結束符 s=（node *）malloc(sizeof(node); / 生成新結點生成新結點 n+; / 表長加表長加1 s-data=x;r-next=s; / 新結點插入表尾新結點插入表尾 r=s; / 尾指針尾指針 r 指向新的表尾指向新的表尾x=getchar(); / 讀下一結點讀下一結點 r-next=NULL;改進的改進的尾插建表算法尾插建表算法: :v

35、oid createlist()node *p,*s; char x; int z=1;n=0; head=(node*)malloc(sizeof(node); p=head; printf(ntt建立一個線性表建立一個線性表); printf(“ntt請逐個輸入字符，請逐個輸入字符， 結束標記為結束標記為xn); while(z)printf(tt輸入：輸入：); scanf(%c,&x); getchar();if(x!=x) s=(node*)malloc(sizeof(node); n+; s-data=x; p-next=s; s-next=NULL; p=s;else z

36、=0;帶頭結點的帶頭結點的尾插建表算法（尾插建表算法（p總指向尾結點）：（不講）總指向尾結點）：（不講）（2）查找運算）查找運算設單鏈表的長度為設單鏈表的長度為 n n ，要查找表中第，要查找表中第 i i 個結點。個結點。算法思想：算法思想：從頭結點開始順鏈掃描。從頭結點開始順鏈掃描。用指針用指針 p p 指向當前掃描到的結點。指向當前掃描到的結點。用用 j j 作統計已掃描結點數的計數器。作統計已掃描結點數的計數器。p p 的的初值指向頭結點，初值指向頭結點，j j 的初值為的初值為 0 0 。當當 p p 掃描下一個結點時，掃描下一個結點時，j j 自動加自動加 1 1 。 當當 j=i

37、j=i時，指針時，指針 p p 所指的結點就是第所指的結點就是第 i i 個結點。個結點。按序號查找按序號查找node * searchlist1( linklist L, int i ) / L接收已存在的鏈表的頭指針接收已存在的鏈表的頭指針/ i 接收要查找的結點的位置接收要查找的結點的位置 node *p; int j=0; p=L; while( p-next!=NULL & jnext; j+; if(j= =i) return p; else return NULL;i 的合法位置為：的合法位置為：1=i=n帶頭結點，則可：帶頭結點，則可：0=inext=NULL) / 鏈

38、表只有頭結點鏈表只有頭結點 printf(tt線性表為空！線性表為空！); return; p=L-next; / 從除頭結點外的第從除頭結點外的第 1 個結點開始個結點開始while( p!=NULL & p-data!=x ) p=p-next; i+; if( p!=NULL ) return p; printf(tt 在第在第%d位上找到值為位上找到值為%d的結點！的結點！, i, x ); else / p為空，肯定將最后一個結點的鏈域給了為空，肯定將最后一個結點的鏈域給了p，即沒找到，即沒找到 printf(tt 未找到值為未找到值為%c的結點！的結點！n, x ); re

39、turn NULL; 設設 指針指針 p 指向單鏈表的某一結點。指向單鏈表的某一結點。設設 指針指針 s 指向等待插入的、值為指向等待插入的、值為 x 的新結點。的新結點。實現方法（兩種）：實現方法（兩種）： 后插：將新結點后插：將新結點 * *s s 插在結點插在結點 * *p p 之后。之后。 前插：將新結點前插：將新結點 * *s s 插在結點插在結點 * *p p 之前。之前。（3）插入運算）插入運算算法思想：算法思想： 取一新結點，將其數據域置為新結點，再修改有關結點的取一新結點，將其數據域置為新結點，再修改有關結點的鏈域：鏈域： 把原把原 p 結點的直接后繼結點作為結點的直接后繼結

40、點作為 s 結點的直接后繼；結點的直接后繼； s 結點作為結點作為 p 結點的直接后繼。結點的直接后繼。 后插操作后插操作X S PINSERTAFTER( p，x ) / 將值為將值為 x 的新結點插在的新結點插在*P 之后之后 node *p; datatype x; s=( node *)malloc(sizeof(node); / 生成新結點生成新結點 s-data=x; s-next=p-next; / p-next=s; / 將將 *s 插在插在 *p 之后之后后插算法：后插算法：后插算法時間復雜度：后插算法時間復雜度：O（1）先找到先找到 p 結點的前驅結點（單鏈表無前驅指針）；

41、結點的前驅結點（單鏈表無前驅指針）；然后修改此前驅結點的鏈域，使其指向等待插入的然后修改此前驅結點的鏈域，使其指向等待插入的 s 結點結點 ；然后將然后將 s 結點的鏈域指向結點的鏈域指向 p 結點結點 。 前插操作：前插操作：X S q p INSERTBEFORE（p, x） / 在帶頭結點的單鏈表在帶頭結點的單鏈表 head 中中,將值為將值為 x 的新結點插在的新結點插在 *P 之前之前 node *p; datatype x; node *q; q=head; / 從頭指針開始從頭指針開始 if( q= =NULL ) printf(“error!”); else s=（node*）

42、malloc(sizeof(node); / 生成新結點生成新結點 s-data=x; while(q-next!=p) q=q-next; / 找找 *p 的前驅結點的前驅結點 s-next=p; / q-next=s; / 將將 *s 插在插在 *p 之之 前前,插在插在 *q 之后之后 前插算法前插算法：前插算法的平均時間復雜度為：前插算法的平均時間復雜度為：O（n） 改進的前插算法改進的前插算法算法思想：算法思想：后插算法為后插算法為 O(1) ，而前插算法為，而前插算法為O(n) 。可在可在 *p 之后插入新結點之后插入新結點 *s ，然后，然后交換交換 *s 和和 *p 的的值值。

43、交換后實際上就是前插。交換后實際上就是前插。pA X s插入前：插入前：后插：后插：A X ps交換調整：交換調整：x A p sINSERTBEFORE2( p，x) / 將值為將值為 x 的新結點插在的新結點插在 *p 之后之后 node *p; datatype x, y; s=（node *）malloc(sizeof(node); / 生成新結點生成新結點 s-data=x; s-next=p-next; p-next=s; / 將將 *s 插在插在 *p 之后之后 y=s-data ; / 交換交換 *s 和和 *p 的值的值 s-data=p-data ; p-data=y ;

44、p=s ;算法描述：算法描述：算法思想：算法思想：先求出第先求出第 i-1 個結點，個結點，然后在第然后在第 i-1 個結點之后插入結點個結點之后插入結點 x。 插入運算插入運算 inslist（i,x ) )（不講）（不講）void inslist(int i,char x) /i 的合法位置為：的合法位置為：1=i=n node *s,*p; int j; if(idata=x; s-next=p-next; p-next=s; else printf( tt 未找到前驅結點未找到前驅結點!n); （4）刪除運算）刪除運算刪除單鏈表中刪除單鏈表中 *p 的后繼結點。的后繼結點。算法描述：算

45、法描述：DeleteA( p ) / 刪除刪除 *p 的后繼結點的后繼結點 *r, 設設 *r 存在存在 node *p; node *r; if(p-next!=NULL) / 說明其后繼結點存在說明其后繼結點存在 r=p-next; / 將后繼結點存到將后繼結點存到 r 中，便于釋放中，便于釋放 p-next=r-next; / 將將 p 的鏈域指向其后繼結點的后繼的鏈域指向其后繼結點的后繼 free(r); 存儲池p r例：在單鏈表上刪除序號為例：在單鏈表上刪除序號為 i 的結點的結點 Delete( L, i ) （按序號刪除結點）（按序號刪除結點）算法思想：算法思想：（1）找到被刪結

46、點（第）找到被刪結點（第 i 個結點）的前驅結點（第個結點）的前驅結點（第 i-1個個結結點點）（2）用指針）用指針 p 指向該前驅結點；指向該前驅結點；（3）刪除）刪除 *p 的后繼結點即第的后繼結點即第 i 個結點。個結點。思考：思考：（1）如何刪除單鏈表中）如何刪除單鏈表中 p 結點本身？結點本身？ （找前驅結點）（找前驅結點）（2）如何刪除單鏈表中）如何刪除單鏈表中 p 結點的前驅結點？結點的前驅結點？ （找前驅的前驅）（找前驅的前驅）DELETE(L,i)node *L;int i; node*p; int j; j=i-1; p=searchlist1(L,j)；/ 找到第找到第i

47、-1個結點個結點*p if (p!=NULL)&(p-next!=NULL) DeleteA(p); else printf(“errorn”)算法實現：算法實現：例：刪除線性表例：刪除線性表 head 中數據域為中數據域為 x 的結點。的結點。 （按值刪除結點）（按值刪除結點）算法思想：算法思想： （1）若鏈表為空，返回；）若鏈表為空，返回； （2）查找值為）查找值為 x 的結點及其前驅結點；的結點及其前驅結點； （3）將）將 x 結點刪除。結點刪除。 void dellist( char x ) node *p,*q; / 始終用始終用 q 指向指向 *p 的前驅的前驅 if(he

48、ad=NULL) / 為空表為空表 printf(tt鏈表下溢！鏈表下溢！n); return; if(head-next=NULL) /表只有頭結點表只有頭結點 printf(tt線性表為空！線性表為空！); return; q=head; p=head-next;算法實現：算法實現：while(p!=NULL&p-data!=x) / 始終用始終用 q 指向指向 *p 的前驅的前驅 q=p; p=p-next; if ( p!=NULL ) / p!=NULL說明說明 p 不是尾結點，不是尾結點，p還在表內還在表內 ，說明找到了值為，說明找到了值為x的結點，就是的結點，就是p q-

49、next=p-next; free(p); printf(tt %c 已經被刪除！已經被刪除！,x); else printf(tt 未找到！未找到！n);3. 單單循環(huán)鏈表循環(huán)鏈表 整個鏈表形成一個環(huán)，從表中任一結點出發(fā)均可找到整個鏈表形成一個環(huán)，從表中任一結點出發(fā)均可找到表中其它結點。表中其它結點。a1 an .(非空表）非空表） h(空表）空表）h特點：特點：（1）表中最后一個結點的指針域指向第一個結點或）表中最后一個結點的指針域指向第一個結點或表頭結點（如果有表頭結點）。表頭結點（如果有表頭結點）。（2）循環(huán)鏈表的運算與單鏈表基本一致。但兩者判斷是否）循環(huán)鏈表的運算與單鏈表基本一致。但

50、兩者判斷是否到表尾的條件不同：到表尾的條件不同：單鏈表：判斷某結點的鏈域是否為空。單鏈表：判斷某結點的鏈域是否為空。循環(huán)鏈表：判斷某結點的鏈域值是否等于頭指針。循環(huán)鏈表：判斷某結點的鏈域值是否等于頭指針。（3）用只有頭指針表示的單循環(huán)鏈表查找結點：）用只有頭指針表示的單循環(huán)鏈表查找結點： 找找 a1(開始結點開始結點) O(1) 找找 an 需要遍歷表需要遍歷表 O(n) 由于在實際問題中，對表的操作常在表的首尾位置進行，因由于在實際問題中，對表的操作常在表的首尾位置進行，因此可增加一個尾指針此可增加一個尾指針(rear)，則：，則： 找找a1(開始結點開始結點) ：rear-next-nex

51、t O(1) 找找an ： rear O(1) 實用中多用實用中多用尾指針尾指針表示表示單循環(huán)鏈表單循環(huán)鏈表。尾指針表示的單循環(huán)鏈表：尾指針表示的單循環(huán)鏈表：headhead非空表非空表空表空表rearrear例：表的合并例：表的合并 在鏈表上實現將兩個線性表在鏈表上實現將兩個線性表(a1,a2,.,an)和和(b1,b2bm)鏈接成鏈接成一個線性表一個線性表(a1,a2,.,an,b1,b2,.,bm)的的運算。運算。分析：分析： 若在若在單鏈表單鏈表或或只有頭指針表示的單循環(huán)鏈表只有頭指針表示的單循環(huán)鏈表上做這種鏈接上做這種鏈接運算，運算， 都要遍歷第一個鏈表找到結點都要遍歷第一個鏈表找到

52、結點 an ， 然后將結點然后將結點 b1 鏈接鏈接到到 an 的后面的后面，其執(zhí)行時間為其執(zhí)行時間為 O(n) 。算法思想：算法思想： 在尾指針表示的單循環(huán)鏈表上實現，則只需修改指針，無在尾指針表示的單循環(huán)鏈表上實現，則只需修改指針，無需遍歷，需遍歷，其執(zhí)行時間為其執(zhí)行時間為O(1) 。兩個單循環(huán)鏈表（用尾指針表示）的鏈接示意圖：兩個單循環(huán)鏈表（用尾指針表示）的鏈接示意圖：rarbp 兩個單循環(huán)鏈表（用尾指針表示）的鏈接示意圖：兩個單循環(huán)鏈表（用尾指針表示）的鏈接示意圖：rarbnode *CONNECT(ra,rb)node *ra,*rb; node*p;p=ra-next;/ 保存鏈表

53、保存鏈表ra的頭結點地址的頭結點地址 ra-next=rb-next-next; / 將表將表rb的開始結點鏈接到表的開始結點鏈接到表ra的終端結點之后的終端結點之后 free(rb-next);/ 釋放鏈表釋放鏈表rb的頭結點的頭結點 rb-next=p；/ 鏈表鏈表ra的頭結點鏈到鏈表的頭結點鏈到鏈表rb的終端結點之后的終端結點之后 return rb ;/返回新循環(huán)鏈表的尾指針返回新循環(huán)鏈表的尾指針4 .雙向鏈表（雙向鏈表（Double linked list)查找某個結點：查找某個結點： 單鏈表只能順鏈向后（順著直接后繼指針）查找。單鏈表只能順鏈向后（順著直接后繼指針）查找。查找某個結

54、點的前驅結點：查找某個結點的前驅結點： 單鏈表：從頭順鏈找。單鏈表：從頭順鏈找。O(n) 單循環(huán)鏈表：可從任一已知結點出發(fā)進行查找。單循環(huán)鏈表：可從任一已知結點出發(fā)進行查找。O(n)雙向鏈表（雙向鏈表（Double linked list)： 單鏈表的每個結點再增加一個指向其前驅的指針域單鏈表的每個結點再增加一個指向其前驅的指針域 prior，這樣形成的鏈表有兩條不同方向的鏈，稱之為雙向鏈表。這樣形成的鏈表有兩條不同方向的鏈，稱之為雙向鏈表。特點：特點：雙鏈表一般也由頭指針雙鏈表一般也由頭指針 head 唯一確定。唯一確定。每一結點均有：每一結點均有： 數據域數據域 （data ） 左鏈域左鏈

55、域 （prior） 指向前驅結點。指向前驅結點。 右鏈域右鏈域 （next ） 指向后繼結點。指向后繼結點。是一種對稱結構（既有左鏈域，又有右鏈域）。是一種對稱結構（既有左鏈域，又有右鏈域）。（1）雙向鏈表的分類：）雙向鏈表的分類： 非循環(huán)雙向鏈表非循環(huán)雙向鏈表 循環(huán)雙向鏈表循環(huán)雙向鏈表 為了運算方便，還可添加一個表頭結點。為了運算方便，還可添加一個表頭結點。（2）雙鏈表的結點類型描述）雙鏈表的結點類型描述typedef struct dnode datatype data; struct dnode *prior,*next;dlinknode;dlinknode *head;(3)結點結構

56、示意圖結點結構示意圖headheadhead結點結構示意圖結點結構示意圖帶頭結點的雙循環(huán)帶頭結點的雙循環(huán)空空鏈表鏈表帶頭結點的雙循環(huán)鏈表帶頭結點的雙循環(huán)鏈表 p-prior-next=p-next-prior=p 即：即： 結點結點*p 的存儲位置的存儲位置 ： 既存放在其前驅結點既存放在其前驅結點( * p-prior )的后繼指針域中；的后繼指針域中； 也存放在其后繼結點也存放在其后繼結點( * p-next ) 的前驅指針域中。的前驅指針域中。(4)雙鏈表結構對稱性描述：雙鏈表結構對稱性描述：插入；插入；刪除；刪除；查找；查找；在單鏈表中：在單鏈表中：前插不如后插方便；前插不如后插方便；

57、刪除某結點自身不如刪除該結點的后繼方便。刪除某結點自身不如刪除該結點的后繼方便。而在雙向鏈表中，上述運算均十分方便。而在雙向鏈表中，上述運算均十分方便。雙鏈表的基本運算：雙鏈表的基本運算：/在帶頭結點的雙鏈表中，將值為在帶頭結點的雙鏈表中，將值為 x 的新結點插在的新結點插在 *p 之前之前 void dinsert(p,x)dlinknode *p;datatype x; dlinknode *s; s= (dlinknode*) malloc(sizeof(dlinknode); s-data=x; s-prior=p-prior; s-next=p; p-prior-next=s; p-

58、prior=s; （1）前插操作（將結點）前插操作（將結點 x 插在插在 *p 之前）之前）spax注意：注意：5，6步的順序不能顛倒步的順序不能顛倒如果是后插，則注意如果是后插，則注意5，6步的順序步的順序spxa p-next-prior=s; p-next=s;Ddelete(p)dlinknode *p; p-prior-next=p-next; p-next-prior=p-prior; free(p);pxa（2）刪除操作（在雙向鏈表中刪除）刪除操作（在雙向鏈表中刪除 p 結點）結點）算法思想：算法思想： 從第一個結點開始（從第一個結點開始（頭結點的后繼頭結點的后繼）依次比較每個結

59、點）依次比較每個結點的數據域的值，若找到結點的數據域的值，若找到結點 x，則，則返回指向該結點的指針返回指向該結點的指針； 否則：若又回到頭結點，說明表中不存在結點否則：若又回到頭結點，說明表中不存在結點 x，則，則返回返回空指針空指針。（3）查找（在帶頭結點的雙向循環(huán)鏈表中查找結點）查找（在帶頭結點的雙向循環(huán)鏈表中查找結點 x ）算法描述：算法描述：( 自己完成）自己完成）5. 靜態(tài)鏈表靜態(tài)鏈表 靜態(tài)鏈表可以借助一維數組來描述：靜態(tài)鏈表可以借助一維數組來描述： #define MAXSIZE 1000 typedef struct ElemType data; int cur; compon

60、ent, SlinkListMAXSIZE; 為了便于在不設指針類型的高級程序設計語言中使用為了便于在不設指針類型的高級程序設計語言中使用鏈表結構，引入靜態(tài)鏈表。鏈表結構，引入靜態(tài)鏈表。 靜態(tài)鏈表和前面的動態(tài)鏈表一樣，便于插入和刪除操靜態(tài)鏈表和前面的動態(tài)鏈表一樣，便于插入和刪除操作：插入和刪除同樣不需要移動元素。作：插入和刪除同樣不需要移動元素。 設設 S S 為為 SlinkList SlinkList 型變量，則型變量，則 S0.cur S0.cur 指示第一個結點在指示第一個結點在數組中的位置，設數組中的位置，設 i=s0.curi=s0.cur，則，則 si.datasi.data存放線性表的第一存放線性表的第一個元素，且個元素，且 si.cur si.cur 指示第二個結點在數組中位置。指示第二個結點在數組中位置。 一