數據結構Chapter02線性表

1、算法與數據結構12013.9-2013.12主講教師：張翠肖聯系方式：算法與數據結構2 數據的邏輯結構數據的邏輯結構 數據的存儲結構數據的存儲結構 線性結構線性結構 非線性結構非線性結構順序存儲順序存儲鏈式存儲鏈式存儲 線性表線性表棧棧隊列隊列樹樹圖圖數據結構數據結構( (物理結構物理結構) )數據結構：是相互之間存在一種或多數據結構：是相互之間存在一種或多種特定關系的數據元素的集合。種特定關系的數據元素的集合。 邏輯結構：結構定義中的邏輯結構：結構定義中的“關系關系”描述的是數據描述的是數據元素之間的邏輯關系，因此稱為數據的邏輯結構元素之間的邏輯關系，因此稱為數據的邏輯結構。 存儲結構：是數

2、據結構在計算機中的表示（又稱映像）。存儲結構：是數據結構在計算機中的表示（又稱映像）。(2)算法與數據結構3 第第2 2章章 線性表線性表 第第3 3章章 棧和隊列棧和隊列 第第4 4章章 串、數組和廣串、數組和廣義表義表 線性結構線性結構若結構是非空有限集，則有且僅有一個開始結若結構是非空有限集，則有且僅有一個開始結點和一個終端結點，并且所有結點都最多只有一個點和一個終端結點，并且所有結點都最多只有一個直接前趨和一個直接后繼。直接前趨和一個直接后繼?？杀硎緸榭杀硎緸椋海ǎ海╝ a1 1 , a, a2 2 , , , a, an n） （邏輯、存儲（邏輯、存儲和運算）和運算）算法與數據結構4

3、 只有一個首結點和尾結點；只有一個首結點和尾結點； 除首尾結點外，其他結點只有一個直接前驅和一除首尾結點外，其他結點只有一個直接前驅和一個直接后繼。個直接后繼。線性結構表達式：（線性結構表達式：（a a1 1 , a, a2 2 , , , a, an n） 線性結構包括線性表、堆棧、隊列、字符串、數線性結構包括線性表、堆棧、隊列、字符串、數組等等，其中，最典型、最常用的是組等等，其中，最典型、最常用的是線性表線性表簡言之，線性結構反映結點間的邏輯關系是簡言之，線性結構反映結點間的邏輯關系是 一對一一對一 的的算法與數據結構5第第2 2章章線性表線性表1. 了解線性結構的特點了解線性結構的特點

4、2.2.掌握順序表的定義、查找、插入和刪除掌握順序表的定義、查找、插入和刪除 3.3.掌握鏈表的定義、查找、插入和刪除掌握鏈表的定義、查找、插入和刪除 4.4.能夠從時間和空間復雜度的角度比較兩種能夠從時間和空間復雜度的角度比較兩種存儲結構的不同特點及其適用場合存儲結構的不同特點及其適用場合 教學目標教學目標算法與數據結構62.1 線性表的類型定義線性表的類型定義2.2 線性表的順序表示和實現線性表的順序表示和實現2.3 線性表的鏈式表示和實現線性表的鏈式表示和實現2.4 線性表的應用線性表的應用教學內容教學內容算法與數據結構7（a1, a2, ai-1，ai, ai1 ，, an）線性表的定

5、義：線性表的定義：用數據元素的有限序列表示用數據元素的有限序列表示n=0n=0時稱為時稱為數據元素數據元素線性起點線性起點a ai i的直接前趨的直接前趨a ai i的直接后繼的直接后繼下標下標，是元素的是元素的序號，表示元素序號，表示元素在表中的位置在表中的位置n n為元素總個為元素總個數，即表長數，即表長空表空表線性終點線性終點2.1 2.1 線性表的類型定義線性表的類型定義算法與數據結構8 （ A, B, C, D, , Z）學號學號姓名姓名性別性別年齡年齡班級班級041810205041810205于春梅于春梅女女 18 180404級計算機級計算機1 1班班0418102600418

6、10260何仕鵬何仕鵬男男 20 200404級計算機級計算機2 2班班041810284041810284王王 爽爽女女 19 190404級計算機級計算機3 3班班041810360041810360王亞武王亞武男男 18 180404級計算機級計算機4 4班班： ：數據元素都是記錄數據元素都是記錄; 元素間關系是線性元素間關系是線性數據元素都是字母數據元素都是字母; 元素間關系是線性元素間關系是線性同一線性表中的元素必定具有相同特性同一線性表中的元素必定具有相同特性抽象數據類型線性表線性表的定義如下：ADT List 數據對象數據對象：D ai | ai ElemSet, i=1,2,.

7、,n, n0 稱 n 為線性表的表長表長; 稱 n=0 時的線性表為空表空表。數據關系數據關系：R1 |ai-1 ,aiD, i=2,.,n 設線性表為 (a1，a2, . . . ，ai，. . . ，an), 稱 i 為 ai 在線性表中的位序位序。算法與數據結構10 基本操作：基本操作： 結構初始化操作結構初始化操作結構銷毀操作結構銷毀操作 引用型操作引用型操作 加工型操作加工型操作 ADT List算法與數據結構11 InitList( &L )操作結果：操作結果：構造一個空的線性表L。初始化操作初始化操作算法與數據結構12 結構銷毀操作結構銷毀操作DestroyList( &

8、amp;L )初始條件：操作結果：線性表 L 已存在。銷毀線性表 L。算法與數據結構13ListEmpty( L )ListLength( L )PriorElem( L, cur_e, &pre_e )NextElem( L, cur_e, &next_e ) GetElem( L, i, &e )LocateElem( L, e)引用型操作引用型操作: :算法與數據結構14 ListEmpty( L )初始條件：操作結果：線性表L已存在。若L為空表，則返回TRUE，否則FALSE。（線性表判空）算法與數據結構15ListLength( L )初始條件：操作結果：線性

9、表L已存在。返回L中元素個數。（求線性表的長度）算法與數據結構16 PriorElem( L, cur_e, &pre_e )初始條件：操作結果：線性表L已存在。若cur_e是L的元素，但不是第一個，則用pre_e 返回它的前驅，否則操作失敗，pre_e無定義。（求數據元素的前驅）算法與數據結構17NextElem( L, cur_e, &next_e )初始條件：操作結果：線性表L已存在。若cur_e是L的元素，但不是最后一個，則用next_e返回它的后繼，否則操作失敗，next_e無定義。（求數據元素的后繼）算法與數據結構18GetElem( L, i, &e )

10、初始條件： 操作結果：線性表L已存在，且 1iLengthList(L)。用 e 返回L中第 i 個元素的值。（求線性表中某個數據元素）算法與數據結構19LocateElem( L, e)初始條件：操作結果：線性表L已存在，e為給定值返回L中第中第1個個與e相等相等的元素的位序。若這樣的元素不存在，則返回值為0。（定位函數）算法與數據結構20加工型操作加工型操作 ClearList( &L )ListInsert( &L, i, e )ListDelete(&L, i, &e) 算法與數據結構21ClearList( &L )初始條件：操作結果：線性表L

11、已存在。將L重置為空表。（線性表置空）算法與數據結構22 ListInsert( &L, i, e )初始條件：操作結果：線性表L已存在， 且 1iLengthList(L)+1 。在L的第i個元素之前插入插入新的元素e，L的長度增1。（插入數據元素）算法與數據結構23ListDelete(&L, i, &e)初始條件：操作結果：線性表L已存在且非空， 1iLengthList(L) 。刪除L的第i個元素，并用e返回其值，L的長度減1。（刪除數據元素）算法與數據結構242.2 2.2 線性表的順序表示和實現線性表的順序表示和實現線性表的順序表示又稱為線性表的順序表示又稱

12、為順序存儲結構順序存儲結構或或順序映像順序映像。簡言之，邏輯上相鄰，物理上也相鄰簡言之，邏輯上相鄰，物理上也相鄰順序存儲方法：順序存儲方法：用用一組地址連續(xù)一組地址連續(xù)的存儲單元依次存儲的存儲單元依次存儲線性表的元素，可通過線性表的元素，可通過數組數組VnVn來實現。來實現。順序存儲定義：順序存儲定義：把邏輯上相鄰的數據元素存儲在物理把邏輯上相鄰的數據元素存儲在物理上相鄰的存儲單元中的存儲結構。上相鄰的存儲單元中的存儲結構。算法與數據結構25元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲地址存儲內容存儲內容Loc(元

13、素元素i)=Lo+（i-1)*m順序存儲順序存儲算法與數據結構26#define MAXSIZE 100 /#define MAXSIZE 100 /最大長度最大長度typedef struct typedef struct ElemType ElemType * *elem; /elem; /指向數據元素的基地址指向數據元素的基地址 int length; /int length; /線性表的當前長度線性表的當前長度 SqListSqList；順序表的類型定義順序表的類型定義數據結構基本運算操作有：數據結構基本運算操作有：查找、插入、刪除查找、插入、刪除算法與數據結構27malloc(mal

14、loc(m m) )：開辟：開辟m m字節(jié)長度的地址空間，字節(jié)長度的地址空間，并返回這段空間的首地址并返回這段空間的首地址sizeof(sizeof(x x) )：計算變量：計算變量x x的長度的長度free(free(p p) )：釋放指針：釋放指針p p所指變量的存儲空間所指變量的存儲空間，即徹底刪除一個變量，即徹底刪除一個變量補充：補充：C C語言的動態(tài)分配函數（語言的動態(tài)分配函數（ ）算法與數據結構28new new 類型名類型名T T（初值列表）（初值列表）功能：功能：申請用于存放申請用于存放T T類型對象的內存空間，并依初值列表賦以初值類型對象的內存空間，并依初值列表賦以初值結果值

15、：結果值：成功：成功：T T類型的指針，指向新分配的內存類型的指針，指向新分配的內存失?。菏。? 0（NULLNULL）int *p1= new int;或或 int *p1 = new int(10);delete delete 指針指針P P功能：功能：釋放指針釋放指針P P所指向的內存。所指向的內存。P P必須是必須是newnew操作的返回值操作的返回值delete p1;補充：補充：C+C+的動態(tài)存儲分配的動態(tài)存儲分配算法與數據結構29n函數調用時傳送給形參表的實參必須與形參在類函數調用時傳送給形參表的實參必須與形參在類型、個數、順序上保持一致型、個數、順序上保持一致n參數傳遞有兩種

16、方式參數傳遞有兩種方式n傳值方式傳值方式（參數為整型、實型、字符型等）（參數為整型、實型、字符型等）n傳地址傳地址參數為指針變量參數為指針變量參數為引用類型參數為引用類型參數為數組名參數為數組名補充：補充：C+C+中的參數傳遞中的參數傳遞算法與數據結構30void main()float a,b; cinab; swap(a,b);coutaendlbendl;#include void swap(float m,float n)float temp; temp=m; m=n; n=temp;傳值傳值方式方式把實參的值傳送給函數局部工作區(qū)相應的副把實參的值傳送給函數局部工作區(qū)相應的副本中本中，

17、函數使用這個副本執(zhí)行必要的功能。，函數使用這個副本執(zhí)行必要的功能。函數修改的是函數修改的是副本的值副本的值，實參的值不變實參的值不變算法與數據結構31傳地址傳地址方式方式指針變量作參數指針變量作參數void main()float a,b,*p1,*p2; cinab; p1=&a; p2=&b; swap(p1, p2);coutaendlbendl;#include void swap(float *m,float *n)float t; t=*m; *m=*n; *n=t;形參變化影響實參形參變化影響實參算法與數據結構32傳地址傳地址方式方式引用類型作參數引用類型作參數引

18、用：它用來給一個對象提供一個替代的名字。引用：它用來給一個對象提供一個替代的名字。#includevoid main()int i=5;int &j=i;i=7;couti=i j=ab; swap(a,b);coutaendlbendl;#include void swap(float m,float n)float temp; temp=m; m=n; n=temp;傳地址傳地址方式方式引用類型作參數引用類型作參數算法與數據結構34（1 1）傳遞引用給函數與傳遞指針的效果是一）傳遞引用給函數與傳遞指針的效果是一樣的，樣的，形參變化實參也發(fā)生變化形參變化實參也發(fā)生變化。（2 2）引用

19、類型作形參，在內存中并沒有產生）引用類型作形參，在內存中并沒有產生實參的副本，它實參的副本，它直接對實參操作直接對實參操作；而一般變；而一般變量作參數，形參與實參就占用不同的存儲單量作參數，形參與實參就占用不同的存儲單元，所以形參變量的值是實參變量的副本。元，所以形參變量的值是實參變量的副本。因此，當因此，當參數傳遞的數據量較大參數傳遞的數據量較大時，用引用時，用引用比用一般變量傳遞參數的時間和空間效率都比用一般變量傳遞參數的時間和空間效率都好。好。引用類型作形參的三點說明引用類型作形參的三點說明算法與數據結構35（3）指針參數雖然也能達到與使用引用的效）指針參數雖然也能達到與使用引用的效果，

20、但在被調函數中需要重復使用果，但在被調函數中需要重復使用“* *指針指針變量名變量名”的形式進行運算，這很容易產生錯的形式進行運算，這很容易產生錯誤且程序的閱讀性較差；另一方面，在主調誤且程序的閱讀性較差；另一方面，在主調函數的調用點處，必須用函數的調用點處，必須用變量的地址作為實變量的地址作為實參參。引用類型作形參的三點說明引用類型作形參的三點說明算法與數據結構36傳地址傳地址方式方式數組名作參數數組名作參數#includevoid sub(char);void main（void ） char a10=“hello”; sub(a); coutaendl;void sub(char b )

21、 b =“world”;傳遞的是數組的首地址傳遞的是數組的首地址對形參數組所做的任何改變都將反映到實參數組中對形參數組所做的任何改變都將反映到實參數組中算法與數據結構37 20:27 #include #define N 10int max(int a);void main ( ) int a10;int i,m;for(i=0;iai;m=max(a);coutthe max number is:m;int max(int b) int i,n; n=b0; for(i=1;iN;i+)if(nbi) n=bi; return n;用數組作函數的參數，求用數組作函數的參數，求10個整數的最大

22、數個整數的最大數算法與數據結構38練習：練習：用數組作為函數的參數，將數組中用數組作為函數的參數，將數組中n個整數按相反的順序存?zhèn)€整數按相反的順序存放，要求輸入和輸出在主函數中完成放，要求輸入和輸出在主函數中完成#include #define N 10void sub(int b )int i,j,temp,m;m=N/2;for(i=0;im;i+) j=N-1-i; temp=bi; bi= bj; bj=temp;return ;void main ( ) int a10,i;for(i=0;iai;sub(a);for(i=0;iN;i+)cout elem=new ElemType

23、MAXSIZE; /為順序表分配空間為順序表分配空間 if(! L- elem) exit(OVERFLOW); /存儲分配失敗存儲分配失敗 L- length=0; /空表長度為空表長度為0 return OK;算法與數據結構422. 2. 銷毀線性表銷毀線性表L Lvoid DestroyList(SqList &L)void DestroyList(SqList &L) if (L.elem) deleteL.elem; / if (L.elem) deleteL.elem; /釋放存儲空間釋放存儲空間 3. 3. 清空線性表清空線性表L Lvoid ClearList(

24、SqList &L) L.length=0; /將線性表的長度置為將線性表的長度置為0算法與數據結構434.4. 求線性表求線性表L L的長度的長度int GetLength(SqList L) return (L.length); 5.5.判斷線性表判斷線性表L L是否為空是否為空int IsEmpty(SqList L) if (L.length=0) return 1; else return 0;算法與數據結構446. 6. 獲取線性表獲取線性表L L中的某個數據元素的內容中的某個數據元素的內容/根據指定位置，獲取相應位置數據元素的內容根據指定位置，獲取相應位置數據元素的內容i

25、nt GetElem(SqList L,int int GetElem(SqList L,int i,ElemType &ei,ElemType &e) ) if (iL.length) return ERROR; if (iL.length) return ERROR; / /判斷判斷i i值是否合理，若不合理，返回值是否合理，若不合理，返回ERRORERROR e=L.elemi-1;e=L.elemi-1; / /第第i-1i-1的單元存儲著第的單元存儲著第i i個數據個數據 return OK;return OK; 算法與數據結構45查找查找（根據指定數據查找，返回數據

26、所在的位置）（根據指定數據查找，返回數據所在的位置）25 34 57 16 48 09 0 1 2 3 4 5 data查找查找 16 i25 34 57 16 48 09 i25 34 57 16 48 09 i25 34 57 16 48 09 i查找成功查找成功算法與數據結構4625 34 57 16 48 0 1 2 3 4data查找 50i25 34 57 16 48 i25 34 57 16 48 i25 34 57 16 48 i25 34 57 16 48 i查找失敗查找失敗算法與數據結構47例如：順序表23 75 41 38 54 62 17L.elemL.lengthL.

27、listsizee =38pppppi 1 2 3 4 1 850p可見，基本操作是：將順序表中的元素逐個和給定值 e 相比較。算法與數據結構48查找算法時間效率分析查找算法時間效率分析7. 7. 在線性表在線性表L L中查找值為中查找值為e e的數據元素的數據元素int LocateELem(SqList L,ElemType e) for (i=0;i L.length;i+) if (L.elemi=e) return i+1; return 0;算法與數據結構49niniicp 1=ACN212)(11)2(111=1nnnnnninni ACN查找算法時間效率分析查找算法時間效率分析

28、算法與數據結構50 O( n )查找算法查找算法的的時間復雜度時間復雜度為為： O( ListLength(L) )算法與數據結構51線性表操作 ListInsert(&L, i, e)的實現：首先分析首先分析:插入元素時，線性表的邏輯結構邏輯結構發(fā)生什么變化發(fā)生什么變化？算法與數據結構52 (a1, , ai-1, ai, , an) 改變?yōu)?(a1, , ai-1, e, ai, , an)a1 a2 ai-1 ai ana1 a2 ai-1 ai ean, 表的長度增加算法與數據結構53算法算法1：在線性表中指定位置前插入一個元素：在線性表中指定位置前插入一個元素 插入元素時，線

29、性表的邏輯結構由插入元素時，線性表的邏輯結構由(a1, , ai-1, ai, , an)改變?yōu)楦淖優(yōu)?a1, , ai-1, b, ai, , an),在第在第i-1個數個數據元素和第據元素和第i個數據元素之間插入新的數據元素。個數據元素之間插入新的數據元素。 變成長度為n+1的線性表niiaaeaaa,1,21 需將第i至第n共（n-i+1)個元素后移niiaaaaa,1,21內存a1a2aiai+1an01i-1V數組下標n-1in12i元素序號i+1nn+1內存a1a2aiai+1an01i-1V數組下標n-1in12i元素序號i+1nn+1an-1e, 算法與數據結構551 1 2

30、1 1 2 2 1 3 2 1 3 3 2 1 3 2 1 4 2 4 4 2 4 5 2 8 5 2 5 6 3 0 6 2 8 7 4 2 7 3 0 8 7 7 8 4 2 9 7 7 圖圖 線性表插入前后的狀況線性表插入前后的狀況(a)(a)插入前插入前n=8; (b)n=8; (b)插入后插入后n=9n=9插入插入2525算法與數據結構562512478936141234567892512479989361499插入插入251247893614251247893614251247893614插第插第 4 4 個結點之前，移動個結點之前，移動 6 64+14+1 次次插在第插在第 i

31、i 個結點之前，移動個結點之前，移動 n-i+1n-i+1 次次插入插入（插在第（插在第 i i 個結點之前）個結點之前）算法與數據結構57（1 1）判斷）判斷插入位置插入位置i i 是否合法是否合法。（2 2）判斷順序表的）判斷順序表的存儲空間是否已滿存儲空間是否已滿。 （3 3）將第）將第n n至第至第i i 位的元素依次位的元素依次向后移動一個位置向后移動一個位置，空，空出第出第i i個位置。個位置。（4 4）將要插入的新元素）將要插入的新元素e e放入第放入第i i個位置個位置。（5 5）表長加表長加1 1，插入成功返回，插入成功返回OKOK?！舅惴ㄋ枷胨惴ㄋ枷搿克惴ㄅc數據結構588.

32、 8. 在線性表在線性表L L中第中第i i個數據元素之前插入數據元素個數據元素之前插入數據元素e e Status ListInsert_Sq(SqList &L,int i ,ElemType e) if(iL.length+1) return ERROR; /i值不合法值不合法 if(L.length=MAXSIZE) return ERROR; /當前存儲空間已滿當前存儲空間已滿 for(j=L.length-1;j=i-1;j-) L.elemj+1=L.elemj; /插入位置及之后的元素后移插入位置及之后的元素后移 L.elemi-1=e; /將新元素將新元素e放入第放入

33、第i個位置個位置 +L.length; /表長增表長增1 return OK;【算法描述算法描述】算法與數據結構59若插入在尾結點之后，則根本無需移動（特別快）；若插入在尾結點之后，則根本無需移動（特別快）；若插入在首結點之前，則表中元素全部后移（特別慢）；若插入在首結點之前，則表中元素全部后移（特別慢）；若要考慮在各種位置插入（共若要考慮在各種位置插入（共n+1n+1種可能）的平均移動次種可能）的平均移動次數，該如何計算？數，該如何計算？算法時間主要耗費在移動元素的操作上算法時間主要耗費在移動元素的操作上【算法分析算法分析】考慮移動元素的平均情況考慮移動元素的平均情況: : 假設在第 i 個

34、元素之前插入的概率為 ， 則在長度為n 的線性表中插入一個元素所需插入一個元素所需移動元素次數的期望值移動元素次數的期望值為：ip11) 1(niiisinpE11) 1(11niisinnE2n 若假定假定在線性表中任何一個位置上進行插入插入的概率的概率都是相等相等的，則移動元素的期望值移動元素的期望值為：算法與數據結構61插入插入 算法時間復雜度算法時間復雜度為為: :O( ListLength(L) ) O( n )算法與數據結構62線性表操作 ListDelete(&L, i, &e)的實現：首先分析：刪除元素時，線性表的邏輯結構發(fā)生什么變化？算法與數據結構63 (a1

35、, , ai-1, ai, ai+1, , an) 改變?yōu)?(a1, , ai-1, ai+1, , an)ai+1 an, 表的長度減少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 算法與數據結構64251247893614123456789251247361425124736142512473614刪除刪除刪除刪除（刪除第（刪除第 i i 個結點）個結點）刪除第刪除第 4 4 個結點，移動個結點，移動 6 64 4 次次刪除第刪除第 i i 個結點，移動個結點，移動 n-in-i 次次算法與數據結構65（1 1）判斷）判斷刪除位置刪除位置i i 是否合法是否合法（合法值為

36、（合法值為1in1in）。）。（2 2）將欲刪除的元素保留在）將欲刪除的元素保留在e e中。中。 （3 3）將第）將第i+1i+1至第至第n n 位的元素依次位的元素依次向前移動一個位置向前移動一個位置。（4 4）表長減表長減1 1，刪除成功返回，刪除成功返回OKOK?！舅惴ㄋ枷胨惴ㄋ枷搿克惴ㄅc數據結構669. 9. 將線性表將線性表L L中第中第i i個數據元素刪除個數據元素刪除Status ListDelete_Sq(SqList &L,int i,ElemType &e) if(iL.length) return ERROR; /i值不合法值不合法 e=L.elemi-1

37、; /將欲刪除的元素保留在將欲刪除的元素保留在e中中 for (j=i;jdata=ai, 則則p-next-data=ai+1 a1a2an.L算法與數據結構931. 1. 初始化線性表初始化線性表L InitList(L) L InitList(L) 2. 2. 銷毀線性表銷毀線性表L DestoryList(L) L DestoryList(L) 3. 3. 清空線性表清空線性表L ClearList(L) L ClearList(L) 4. 4. 求線性表求線性表L L的長度的長度 ListLength(L)ListLength(L)5. 5. 判斷線性表判斷線性表L L是否為空是否為

38、空 IsEmpty(L) IsEmpty(L) 6. 6. 獲取線性表獲取線性表L L中的某個數據元素內容中的某個數據元素內容 GetElem(L,i,e) GetElem(L,i,e) 7. 7. 檢索值為檢索值為e e的數據元素的數據元素 LocateELem(L,e)LocateELem(L,e) 8. 8. 在線性表在線性表L L中插入一個數據元素中插入一個數據元素 ListInsert(L,i,e)ListInsert(L,i,e)9. 9. 刪除線性表刪除線性表L L中第中第i i個數據元素個數據元素 ListDelete(L,i,e)ListDelete(L,i,e)2.3.2

39、2.3.2 單鏈表基本操作的實現單鏈表基本操作的實現算法與數據結構941.1.初始化初始化( (構造一個空表構造一個空表 )【算法思想算法思想】（1）生成新結點作頭結點，用頭指針）生成新結點作頭結點，用頭指針L指向頭結點。指向頭結點。（2）頭結點的指針域置空。）頭結點的指針域置空。L【算法描述算法描述】Status InitList_L(LinkList &L) L=new LNode; L-next=NULL; return OK; 算法與數據結構952.2.銷毀銷毀Status DestroyList_L(LinkList &L) LinkList p; while(L)

40、p=L; L=L-next; delete p; return OK; 算法與數據結構963.3.清空清空Status ClearList(LinkList & & L) / / 將將L L重置為空表重置為空表 LinkList p,q; p=L-next; /p/p指向第一個結點指向第一個結點 while(p) /沒到表尾沒到表尾 q=p-next; delete p; p=q; L-next=NULL; /頭結點指針域為空頭結點指針域為空 return OK; 算法與數據結構974.4.求表長求表長int ListLength_L(LinkList L)/返回返回L L中數

41、據元素個數中數據元素個數 LinkList p; p=L-next; /p/p指向第一個結點指向第一個結點 i=0; while(p) /遍歷單鏈表遍歷單鏈表, ,統(tǒng)計結點數統(tǒng)計結點數 i+; p=p-next; return i; 算法與數據結構985. 5. 判斷表是否為空判斷表是否為空int ListEmpty(LinkList L) /若若L L為空表，則返回為空表，則返回1 1，否則返回，否則返回0 0 if(L-next) /非空非空 return 0; else return 1; 算法與數據結構99 按序號查找按序號查找 按值查找按值查找查找查找算法與數據結構100 思考：順序

42、表里如何找到第思考：順序表里如何找到第i i個元素？個元素？ 鏈表的查找：要從鏈表的頭指針出發(fā)，鏈表的查找：要從鏈表的頭指針出發(fā)，順著鏈域順著鏈域nextnext逐個結點往下搜索，直至逐個結點往下搜索，直至搜索到第搜索到第i i個結點為止。因此，鏈表不是個結點為止。因此，鏈表不是隨機存取結構隨機存取結構按序號查找按序號查找算法與數據結構101L 線性表的操作 GetElem(L, i, &e)在單鏈表中的實現:211830754256pppj1 2 3算法與數據結構102從第從第1 1個結點（個結點（L-nextL-next）順鏈掃描，用指針）順鏈掃描，用指針p p指向指向當前掃描到的

43、結點，當前掃描到的結點，p p初值初值p p = = L-nextL-next。用用j j做計數器，累計當前掃描過的結點數，做計數器，累計當前掃描過的結點數，j j初值為初值為1 1。當當p p指向掃描到的下一結點時，計數器指向掃描到的下一結點時，計數器j j加加1 1。當當j j= = i i時，時，p p所指的結點就是要找的第所指的結點就是要找的第i i個結點。個結點?！舅惴ㄋ枷胨惴ㄋ枷搿堪葱蛱柌檎野葱蛱柌檎宜惴ㄅc數據結構1036.6.獲取線性表獲取線性表L L中的某個數據元素的內容中的某個數據元素的內容Status GetElem_L(LinkList L,int i,ElemType

44、&e) p=L-next; j=1; /初始化初始化 while(p&jnext; +j; if(!p | ji)return ERROR; /第第i個元素不存在個元素不存在 e=p-data; /取第取第i個元素個元素 return OK; /GetElem_L 按序號查找按序號查找【算法描述算法描述】算法與數據結構104復雜度分析復雜度分析 查找第查找第 i 個數據元素的基本操作為：個數據元素的基本操作為：移動移動指針，比較指針，比較 j 和和 i 若若1i n,頻度為頻度為i-1. 若若in,頻度為頻度為n O(n)算法與數據結構105從第一個結點起，依次和從第一個結點起

45、，依次和e e相比較。相比較。如果找到一個其值與如果找到一個其值與e e相等的數據元素，則返回其相等的數據元素，則返回其在鏈表中的在鏈表中的“位置位置”；如果查遍整個鏈表都沒有找到其值和如果查遍整個鏈表都沒有找到其值和e e相等的元素相等的元素，則返回，則返回“NULLNULL”?！舅惴ㄋ枷胨惴ㄋ枷搿堪粗挡檎野粗挡檎宜惴ㄅc數據結構1067.7.在線性表在線性表L L中查找值為中查找值為e e的數據元素的數據元素LNode *LocateELem_L (LinkList L，Elemtype e) p=L-next; while(p &p-data!=e) p=p-next; retur

46、n p; /返回返回L中值為中值為e的數據元素的位置，查找失敗返回的數據元素的位置，查找失敗返回NULL 按值查找按值查找【算法描述算法描述】O(n)算法與數據結構107ai-1 線性表的操作 ListInsert(&L, i, e) 在單鏈表中的實現： 有序對有序對 改變?yōu)楦淖優(yōu)?和和 eaiai-1算法與數據結構108 因此，在單鏈表中第因此，在單鏈表中第 i 個結點之前進個結點之前進行插入的基本操作為行插入的基本操作為: 找到線性表中第找到線性表中第i-1i-1個結點，然后修改個結點，然后修改其指向后繼的指針。其指向后繼的指針。 可見，在鏈表中插入結點只需要修改可見，在鏈表中插入

47、結點只需要修改指針。但同時，若要在第指針。但同時，若要在第 i 個結點之前個結點之前插入元素，修改的是第插入元素，修改的是第 i-1 個結點的指個結點的指針。針。算法與數據結構109 將值為將值為x x的新結點插入到表的第的新結點插入到表的第i i個結點的位個結點的位置上，即插入到置上，即插入到a ai-1i-1與與a ai i之間之間插入插入（插在第（插在第 i i 個結點之前）個結點之前）s-next=p-next; p-next=s思考：步驟思考：步驟1 1和和2 2能互換么？能互換么？算法與數據結構110 20:27 【算法思想算法思想】（1 1）找到）找到a ai-1i-1存儲位置存

48、儲位置p p（2 2）生成一個新結點）生成一個新結點* *s s（3 3）將新結點）將新結點* *s s的數據域置為的數據域置為x x（4 4）新結點）新結點* *s s的指針域指向結點的指針域指向結點a ai i（5 5）令結點）令結點* *p p的指針域指向新結點的指針域指向新結點* *s s算法與數據結構1118.8.在在L L中第中第i i個元素之前插入數據元素個元素之前插入數據元素e e Status ListInsert_L(LinkList &L,int i,ElemType e) p=L;j=0; while(p&jnext;+j;/尋找第尋找第i1個結點個結點

49、 if(!p|ji1)return ERROR;/i大于表長大于表長 + 1或者小于或者小于1 s=new LNode;/生成新結點生成新結點s s-data=e; /將結點將結點s的數據域置為的數據域置為e s-next=p-next; /將結點將結點s插入插入L中中 p-next=s; return OK; /ListInsert_L 【算法描述算法描述】 eai-1aiai-1sp算法的算法的時間復雜度時間復雜度為:O(ListLength(L)算法與數據結構112線性表的操作ListDelete (&L, i, &e)在鏈表中的實現:有序對有序對 和和 改變?yōu)楦淖優(yōu)?a

50、i-1aiai+1ai-1算法與數據結構113 在單鏈表中刪除第刪除第 i i 個結點個結點的基本基本操作操作為:找到線性表中第找到線性表中第i-1i-1個結點，修個結點，修改其指向后繼的指針。改其指向后繼的指針。ai-1aiai+1ai-1q = p-next; p-next = q-next; e = q-data; free(q);pq算法與數據結構114 將表的第將表的第i i個結點刪去個結點刪去 步驟：步驟：（1 1）找到）找到a ai-1i-1存儲位置存儲位置p p（2 2）保存要刪除的結點的值）保存要刪除的結點的值（3 3）令）令p-p-nextnext指向指向a ai i的直接

51、后繼結點的直接后繼結點（4 4）釋放結點）釋放結點a ai i的空間的空間刪除刪除（刪除第（刪除第 i i 個結點）個結點）算法與數據結構115刪除刪除（刪除第（刪除第 i i 個結點）個結點）算法與數據結構116刪除刪除（刪除第（刪除第 i i 個結點）個結點）p-next = p-next-next ?ai-1ai-1aiaiai+1ai+1pq刪除前刪除前刪除后刪除后算法與數據結構117【算法思想算法思想】（1 1）找到）找到a ai-1i-1存儲位置存儲位置p p（2 2）臨時保存結點）臨時保存結點a ai i的地址在的地址在q q中，以備釋放中，以備釋放（3 3）令）令p-nextp

52、-next指向指向a ai i的直接后繼結點的直接后繼結點（4 4）將）將a ai i的值保留在的值保留在e e中中（5 5）釋放）釋放a ai i的空間的空間算法與數據結構118 20:27 9.9.將線性表將線性表L L中第中第i i個數據元素刪除個數據元素刪除 Status ListDelete_L(LinkList &L,int i,ElemType &e) p=L;j=0; while(p-next &jnext; +j; if(!(p-next)|ji-1) return ERROR; /刪除位置不合理刪除位置不合理 q=p-next; /臨時保存被刪結點的

53、地址以備釋放臨時保存被刪結點的地址以備釋放 p-next=q-next; /改變刪除結點前驅結點的指針域改變刪除結點前驅結點的指針域 e=q-data; /保存刪除結點的數據域保存刪除結點的數據域 delete q; /釋放刪除結點的空間釋放刪除結點的空間 return OK; /ListDelete_L 【算法描述算法描述】算法與數據結構1191. 查找查找: 因線性鏈表只能順序存取，即在查找時要因線性鏈表只能順序存取，即在查找時要從頭指針找起，查找的時間復雜度為從頭指針找起，查找的時間復雜度為 O(n)。2. 插入和刪除插入和刪除: 因線性鏈表不需要移動元素，只要因線性鏈表不需要移動元素，

54、只要修改指針，一般情況下時間復雜度為修改指針，一般情況下時間復雜度為 O(1)。 但是，如果要在單鏈表中進行前插或刪除操作，但是，如果要在單鏈表中進行前插或刪除操作，由于要從頭查找前驅結點，所耗時間復雜度為由于要從頭查找前驅結點，所耗時間復雜度為 O(n) 。鏈表的運算時間效率分析鏈表的運算時間效率分析算法與數據結構120如何從線性表得到單鏈表？如何從線性表得到單鏈表？ (創(chuàng)建單鏈表創(chuàng)建單鏈表)鏈表是一個動態(tài)的結構，它不需要鏈表是一個動態(tài)的結構，它不需要予分配空間，因此予分配空間，因此生成鏈表的過程生成鏈表的過程是一個結點是一個結點“逐個插入逐個插入” ” 的過程。的過程。算法與數據結構121

55、n從一個空表開始，重復讀入數據：從一個空表開始，重復讀入數據：u生成新結點生成新結點u將讀入數據存放到新結點的數據域中將讀入數據存放到新結點的數據域中u將該新結點插入到鏈表的前端將該新結點插入到鏈表的前端單鏈表的建立（前插法）單鏈表的建立（前插法） L L L L L e e a b L d c e d e b c d e c d 算法與數據結構122LpLanan-1anLp單鏈表的建立（前插法）單鏈表的建立（前插法）算法與數據結構123void CreateList_F(LinkList &L,int n) L=new LNode; L-next=NULL; /先建立一個帶頭結點的

56、單鏈表先建立一個帶頭結點的單鏈表 for(i=n;i0;-i) p=new LNode; /生成新結點生成新結點 cinp-data; /輸入元素值輸入元素值 p-next=L-next;L-next=p; /插入到表頭插入到表頭 /CreateList_F 【算法描述算法描述】算法與數據結構124n從一個空表從一個空表L開始，將新結點逐個插入到鏈表的尾部，尾指開始，將新結點逐個插入到鏈表的尾部，尾指針針r指向鏈表的尾結點。指向鏈表的尾結點。n初始時，初始時，r同同L均指向頭結點。每讀入一個數據元素則申請一均指向頭結點。每讀入一個數據元素則申請一個新結點，將新結點插入到尾結點后，個新結點，將新

57、結點插入到尾結點后，r指向新結點。指向新結點。單鏈表的建立（尾插法）單鏈表的建立（尾插法） L L L L L L a r r a b r a c r b a e r b c d a d r b c 算法與數據結構125void CreateList_L(LinkList &L,int n) /正位序輸入正位序輸入n個元素的值，建立帶表頭結點的單鏈表個元素的值，建立帶表頭結點的單鏈表L L=new LNode; L-next=NULL; r=L; /尾指針尾指針r指向頭結點指向頭結點 for(i=0;ip-data; /輸入元素值輸入元素值 p-next=NULL; r-next=p;

58、 /插入到表尾插入到表尾 r=p; /r指向新的尾結點指向新的尾結點 /CreateList_L 【算法描述算法描述】算法與數據結構126思考思考 鏈表的輸出算法與數據結構127不帶頭結點的單鏈表不帶頭結點的單鏈表( (自學自學) )算法與數據結構1281 建立單鏈表建立單鏈表: 設成員數據域為字符型（1）頭插法建表頭插法建表：依次插入新結點，并置于表頭 a head b a head b c a head b c 規(guī)律：新增加的結點指針域指向原h(huán)ead指向的結點，然后將原h(huán)ead指向新結點算法與數據結構129頭插法建立單鏈表頭插法建立單鏈表head 建立新節(jié)點 向新節(jié)點中添入內容 使新節(jié)點指

59、向鏈首 改變頭指針s算法與數據結構130頭插法建立單鏈表頭插法建立單鏈表linklist *CREATELIST() char ch; linklist *head,*s;headNULL; chgetchar(); while (ch!=$) smalloc(sizeof(linklist); s-datach; s-nexthead; heads; chgetchar(); return(head);head從鍵盤輸入 o產生一個指針變量s1s1的數據域為ohead指向s1再輸入k產生指針變量s2s2的數據域為ks2的指針域為s1head指向s2算法與數據結構131(2) 尾插法建表尾插法

60、建表：插入的新結點置于表尾 產生一個新結點； 新結點的數據域為插入字符； 原尾結點（由尾指針指定）的指針域為新結點； 尾指針指向新結點； 新結點的指針域為空 a head a head b a head b c tailtailtail算法與數據結構132尾插法建立單鏈表尾插法建立單鏈表head 建立新節(jié)點 向新節(jié)點中添入內容 將新節(jié)點鏈入鏈尾 改變尾指針s算法與數據結構133linklist *CREATELISTR() char ch; linklist *head,*s,*r; headNULL; rNULL; chgetchar(); while(ch!=$) smalloc(sizeof(linklist); s-datach; if (head=NULL) heads; else r-nexts; rs; chgetchar(); 尾插法建立單鏈表尾插法建立單鏈表 if (r!=NULL) r-nextNULL; return head;算法與數據結構134 算法與數據結構135算法與數據結構136 單鏈表特點單鏈表特點它是一種動態(tài)結構，整個