數(shù)據(jù)結構課件：02、第二章 線性表

1、第二章第二章 線性表、堆棧和隊列線性表、堆棧和隊列 2.1 線性表的定義和基本操作線性表的定義和基本操作2.2 線性表的順序存儲結構線性表的順序存儲結構2.3 線性表的鏈接存儲結構線性表的鏈接存儲結構2.4 復雜性分析復雜性分析2.5 堆棧堆棧2.6 隊列隊列 用（用（a a0 0，a a1 1，a an-1n-1）來表示一個線性表。當來表示一個線性表。當n0n0時，時，a a0 0稱為表的稱為表的，a an-1n-1稱為表的稱為表的，a ai i為為a ai+1i+1的的，a ai+1i+1為為a ai i的的；當；當n=0n=0時，線性表中有零個結點，稱為時，線性表中有零個結點，稱為。 2

2、.22.2 線性表的存儲結構線性表的存儲結構 2.2.1 2.2.1 順序存儲結構順序存儲結構 順序存儲：順序存儲：用一組用一組連續(xù)連續(xù)的存儲空間的存儲空間依次依次存存儲線性表的元素。儲線性表的元素。 實現(xiàn)順序存儲的最有效方法是使用一維實現(xiàn)順序存儲的最有效方法是使用一維數(shù)組。數(shù)組。 順序存儲的線性表的基本運算順序存儲的線性表的基本運算 1、插入、插入 例例 在順序表（在順序表（12,13,21,24,28,30,42,77） 中，插入元素中，插入元素 25。 問題：此時，線性表的邏輯結構問題：此時，線性表的邏輯結構 發(fā)生什么變化？發(fā)生什么變化？ 位置關系發(fā)生變化位置關系發(fā)生變化 長度增長度增1

3、 2 23 30 04 41 16 67 75 5121213132121242428283030424277772 23 30 04 41 16 67 75 51212131325252121242428283030424277778 8/采用采用ADL算法描述語言描述算法算法描述語言描述算法算法算法 Insert(A, k, item) /* 在下標為在下標為 k 的結點后插入值為的結點后插入值為 item 的結點的結點 */I1. 插入合法？插入合法？ IF ( k 0 OR k length-1 OR length=MaxSize) THEN (PRINT“插入不合法插入不合法”. R

4、ETURN).I2.插入插入 FOR i length-1 TO k 1 STEP -1 DO Ai 1Ai. Ak 1 item. length length 1. 時間復雜性分析：時間復雜性分析：插入操作的基本運算是：插入操作的基本運算是：元素移動元素移動Dn中有多少種可能的輸入？中有多少種可能的輸入？ n種（種（n個位置可以發(fā)生插入）個位置可以發(fā)生插入）設每種輸入發(fā)生的頻率相等：設每種輸入發(fā)生的頻率相等：1/n則期望復雜性為：則期望復雜性為：E(n)=(n-1) + +1+0) /n =(n-1)/2如果考慮表頭插入的情況，算法改寫為：如果考慮表頭插入的情況，算法改寫為：算法算法 Ins

5、ert(A, k, item) /* 在下標為在下標為 k 的結點后插入值為的結點后插入值為 item 的結點的結點 */I1. 插入合法？插入合法？ IF ( k -1 OR k length-1 OR length=MaxSize) THEN (PRINT“插入不合法插入不合法”. RETURN).I2.插入插入 FOR i length-1 TO k 1 STEP -1 DO Ai 1Ai. Ak 1 item. length length 1. 12時間復雜性分析時間復雜性分析 （考慮表頭插入（考慮表頭插入）插入操作的基本運算是：插入操作的基本運算是：元素移動元素移動Dn中有多少種可能

6、的輸入呢？中有多少種可能的輸入呢？ n+1種種(n+1個位置可以發(fā)生插入個位置可以發(fā)生插入)設插入成功且插入到各位置的頻率相同：設插入成功且插入到各位置的頻率相同：1/(n+1)則期望復雜性為：則期望復雜性為：E(n)=(n+(n-1)+ +1+0) /(n+1) = n/2 2 2、刪除、刪除 例例 在順序表（在順序表（12,13,21,12,13,21,2424,28,30,42,77,28,30,42,77） 中，刪除元素中，刪除元素 2424。問題：此時，線性表的邏輯結構問題：此時，線性表的邏輯結構 發(fā)生什么變化？發(fā)生什么變化？ 位置關系發(fā)生變化位置關系發(fā)生變化 長度減長度減1 12

7、23 30 04 41 16 67 75 5121213132121242428283030424277772 23 30 04 41 16 65 51212131321212828303042427777算法算法 Delete(A, k) /* 刪除順序表刪除順序表 A中下標為中下標為 k 的的結點結點 */D1.k合法合法? IF (k 0 OR k length-1 OR length 0) THEN (PRINT“k不合法不合法”. RETURN).D2.刪除刪除 FOR i k 1 TO length-1 DO Ai-1Ai. length length-1. 時間復雜性分析：時間復

8、雜性分析： 刪除操作的基本運算是：刪除操作的基本運算是：元素移動元素移動 Dn中有多少種可能的輸入？中有多少種可能的輸入？ n 種（種（n個位置可以發(fā)生刪除）個位置可以發(fā)生刪除） 設每種輸入發(fā)生的頻率相等：設每種輸入發(fā)生的頻率相等：1/n 則期望復雜性為：則期望復雜性為： E(n)=(n-1) /n +1/ n +0/ n=（n-1）/2 結論結論： 線性表的順序存儲結構線性表的順序存儲結構優(yōu)點優(yōu)點：易于實現(xiàn)，：易于實現(xiàn)，隨機存取隨機存取速度速度快?？臁?缺點缺點：插入和刪除結點時間復雜性高（需移動元素：插入和刪除結點時間復雜性高（需移動元素,調調整一批結點的地址）整一批結點的地址） 空間利用

9、率低空間利用率低 問題：問題：由于線性表中元素數(shù)目可變，定義數(shù)組時要需要由于線性表中元素數(shù)目可變，定義數(shù)組時要需要考慮什么？考慮什么？ 定義足夠大的靜態(tài)數(shù)組。定義足夠大的靜態(tài)數(shù)組。 使用動態(tài)數(shù)組。使用動態(tài)數(shù)組。第二章第二章 線性表、堆棧和隊列線性表、堆棧和隊列 2.1 線性表的定義和基本操作線性表的定義和基本操作2.2 線性表的順序存儲結構線性表的順序存儲結構2.3 線性表的鏈接存儲結構線性表的鏈接存儲結構2.4 復雜性分析復雜性分析2.5 堆棧堆棧2.6 隊列隊列 n 鏈接存儲：鏈接存儲：用用任意任意一組存儲單元存儲線性一組存儲單元存儲線性表，一個存儲單元除包含結點數(shù)據(jù)表，一個存儲單元除包含

10、結點數(shù)據(jù)(或信息或信息)字字段的值，還必須存放其邏輯相鄰結點段的值，還必須存放其邏輯相鄰結點(前驅或前驅或后繼結點后繼結點)的地址信息，即指針字段。的地址信息，即指針字段。n 隨結點指針域的不同，鏈表主要有三種實隨結點指針域的不同，鏈表主要有三種實現(xiàn)方式：現(xiàn)方式：單鏈表、循環(huán)鏈表和雙向鏈表單鏈表、循環(huán)鏈表和雙向鏈表。 20 2.3.1 線性表的鏈接存儲結構線性表的鏈接存儲結構 單鏈表單鏈表 u鏈表的第一個結點被稱為鏈表的第一個結點被稱為頭結點頭結點(也稱為也稱為表頭表頭)，指，指向頭結點的指針被稱為向頭結點的指針被稱為頭指針頭指針(head). u鏈表的最后一個結點被稱為鏈表的最后一個結點被稱

11、為尾結點尾結點(也稱為表尾也稱為表尾)，指向尾結點的指針被稱為指向尾結點的指針被稱為尾指針尾指針(tail). w 為了對表頭結點插入、刪除等操作的方便，為了對表頭結點插入、刪除等操作的方便，通常在表的前端增加一個特殊的表頭結點，通常在表的前端增加一個特殊的表頭結點，稱其為稱其為哨位結點哨位結點 2.3.1 線性表的鏈接存儲結構線性表的鏈接存儲結構 單鏈表單鏈表 (a)可用存儲空間可用存儲空間free a0 a2 a1 a3 firstlast (b)執(zhí)行建單鏈表操作后執(zhí)行建單鏈表操作后單鏈表的存儲映像單鏈表的存儲映像特點特點: :邏輯上相鄰的節(jié)點在物理上不必相鄰邏輯上相鄰的節(jié)點在物理上不必相

12、鄰25 插入：插入：next(s) next(p) next(p) s 刪除：刪除： q next (p). next (p) next (q) . AVAIL q . 單鏈表的特性：單鏈表的特性： 利用利用鏈接域鏈接域實現(xiàn)線性表元素的邏輯關系。實現(xiàn)線性表元素的邏輯關系。 單鏈表有單鏈表有頭結點、尾結點、頭指針頭結點、尾結點、頭指針。28a a5 5a a3 3a a4 4 單鏈表的優(yōu)點：單鏈表的優(yōu)點： 插入、刪除方便；插入、刪除方便； 空間利用率高：空間利用率高：結點可不連續(xù)存儲，易于擴充結點可不連續(xù)存儲，易于擴充 1、單鏈表結點結構、單鏈表結點結構SLNode（Singly-linked

13、list node）template struct SLNode T data; / 數(shù)據(jù)域數(shù)據(jù)域 SLNode *next ; / 指針域指針域 SLNode ( SLNode* nextNode=NULL ) next = nextNode ; ; / 構造函數(shù)構造函數(shù) SLNode ( const T& item, SLNode* nextNode = NULL ) data=item ; next=nextNode; / 構造函數(shù)構造函數(shù) ;2、單鏈表類、單鏈表類SLList（singly-linked list）的類定義）的類定義template class SLList priva

14、te:SLNode *head ; / 表頭指針表頭指針public:SLList ( void ) head = new SLNode() ; / 構造函數(shù)，構造一個只有哨位結點的空表構造函數(shù)，構造一個只有哨位結點的空表SLList ( T & item ) ；/ 構造函數(shù)構造函數(shù)SLList ( void ) ; / 析構函數(shù)析構函數(shù)bool IsEmpty ( void ) const return headnext = = NULL ; ; / 判斷鏈表是否為空判斷鏈表是否為空int length ( void ) const ; / 返回表的長度返回表的長度bool Find ( i

15、nt k, T & item ) const ; /存取：將存?。簩㈡湵碇械阪湵碇械趉個結點的字段值賦給個結點的字段值賦給itemint Search ( const T & item ) const ; /查找：在查找：在鏈表中查找字段值為鏈表中查找字段值為item的結點并返回其表的結點并返回其表中位置中位置void Delete ( int k, T & item ) ; / 刪除：刪除：刪除刪除鏈表中第鏈表中第k個結點個結點并將其字段值賦給并將其字段值賦給itemvoid Insert ( int k, const T & item ) ; / 插入：插入：在鏈表中第在鏈表中第k個結點個

16、結點后插入字段值為后插入字段值為item的結的結點點;3、單鏈表類、單鏈表類SLList（singly-linked list）的實現(xiàn)）的實現(xiàn)算法算法 Find ( k. item) / 將鏈表中第將鏈表中第k個結點的字段值賦個結點的字段值賦給給item F1. k合法？合法？ / IF ( k 1) THEN (PRINT “存取位置不合法存取位置不合法”. RETURN.)F2. 初始化初始化 phead . i0. /令指針令指針p指向哨位結點，計數(shù)器初始值為指向哨位結點，計數(shù)器初始值為0F3. 找第找第k個結點個結點WHILE (pNULL AND ik) DO( pnext(p) .

17、 ii 1. ) / 若找到第若找到第k個結點或已到達表尾，個結點或已到達表尾，則循環(huán)終止則循環(huán)終止 IF p = NULL THEN ( PRINT“無此結點無此結點”. RETURN. ) itemdata(p). w 算法算法Find，關鍵運算為，關鍵運算為pnext(p)，最好情況最好情況下執(zhí)行下執(zhí)行0次；最壞情況下執(zhí)行次；最壞情況下執(zhí)行n+1次；次；w 平均情況下，假設平均情況下，假設kn的概的概率相同，即每種情況的發(fā)生頻率為率相同，即每種情況的發(fā)生頻率為1/(n+2) ，則，則WHILE循環(huán)的執(zhí)行次數(shù)平均為循環(huán)的執(zhí)行次數(shù)平均為w 因此，存取算法的時間復雜度為因此，存取算法的時間復雜

18、度為O(n).0 1 .1122(1)(2)1( )22n nnnnnnO n 算法算法 int Search (item) / 在鏈表中查找字段值為在鏈表中查找字段值為item的的結點并返回其在表中的位置結點并返回其在表中的位置S1. 初始化初始化 pnext(head) . i1. / 令指針令指針p指向哨位結點的后指向哨位結點的后繼結點，計數(shù)器初始值為繼結點，計數(shù)器初始值為1S2. 遍歷遍歷 WHILE (p NULL AND data(p) item) DO( pnext(p) . ii 1. ) / 令指針令指針p指向下一個結點，指向下一個結點，且計數(shù)器加且計數(shù)器加1 IF p NU

19、LL THEN RETURN i . PRINT “無此結點無此結點”. RETURN 1. w Search算法最好情況下的時間復雜度為算法最好情況下的時間復雜度為O(1)，最壞，最壞情況和平均情況下的時間復雜度皆為情況和平均情況下的時間復雜度皆為O(n). 算法算法Delete ( k. item ) / 刪除鏈表中第刪除鏈表中第k個結點個結點并將其字段值賦并將其字段值賦給給item D1. k合法？合法？ IF ( k 1) THEN (PRINT“刪除不合法刪除不合法”. RETURN.)D2. 初始化初始化 phead . i0. / 令指針令指針p指向哨位結點，計數(shù)器初始值為指向哨

20、位結點，計數(shù)器初始值為0D3. 找第找第k 1結點結點WHILE (p NULL AND ik 1) DO( pnext(p) . ii 1. ) IF p NULL or next(p) = NULL THEN ( PRINT “無此結點無此結點”. RETURN. )D4. 刪除第刪除第k個節(jié)點個節(jié)點qnext(p). next(p) next(q). / 修改修改p的的next指針指針itemdata(q). AVAILq. /存取存取q的字段值并釋放其存儲的字段值并釋放其存儲空間空間 算法算法Insert ( k, item ) / 在鏈表中第在鏈表中第k個結點個結點后插入字段值為后插

21、入字段值為item的結點的結點I1. k合法？合法？ IF ( k 0) THEN (PRINT“插入不合法插入不合法”. RETURN.)I2. 初始化初始化 phead . i0. /令指針令指針p指向哨位結點，計數(shù)器初始值為指向哨位結點，計數(shù)器初始值為0I3. p指向第指向第k結點結點WHILE (p NULL AND ik) DO( pnext(p) . ii 1. ) IF p NULL THEN ( PRINT “插入不合法插入不合法”. RETURN. )I4. 插入插入sAVAIL. data(s) item. next(s) next(p). / 生成新結點生成新結點s，其其

22、next指針指向指針指向p的后繼結點的后繼結點next(p) s. / 修改修改p的的next指針，令其指向新插入結點指針，令其指向新插入結點s 插入、刪除操作的時間復雜性分析插入、刪除操作的時間復雜性分析w插入、刪除操作的最好情況的時間復雜插入、刪除操作的最好情況的時間復雜度為度為O(1)；w插入、刪除操作最壞情況下的時間復雜插入、刪除操作最壞情況下的時間復雜度為度為O(n)；w平均情況下，時間復雜度也是平均情況下，時間復雜度也是O(n)。 2.3 線性表的鏈接存儲結構線性表的鏈接存儲結構w 把鏈接結構把鏈接結構“循環(huán)化循環(huán)化”，即把表尾，即把表尾結點的結點的next域存放指向哨位結點的域存

23、放指向哨位結點的指針，而不是存放空指針指針，而不是存放空指針NULL（即（即 ），這樣的單鏈表被稱為），這樣的單鏈表被稱為循環(huán)鏈表循環(huán)鏈表。w 循環(huán)鏈表使我們可從鏈表的任何位循環(huán)鏈表使我們可從鏈表的任何位置開始，訪問鏈表中的任一結點。置開始，訪問鏈表中的任一結點。 判斷空表的的條件判斷空表的的條件: 單鏈表單鏈表：head=NULL 循環(huán)鏈表：循環(huán)鏈表：next(head) = headhead 2.3 線性表的鏈接存儲結構線性表的鏈接存儲結構w 雙向鏈表雙向鏈表（Double-Linked List）w 又被稱為又被稱為雙重鏈表雙重鏈表。 w 每個節(jié)點有兩個指針域每個節(jié)點有兩個指針域 左指針

24、指向其前驅，右指針指向其后繼；左指針指向其前驅，右指針指向其后繼； 頭節(jié)點頭節(jié)點LEFT和尾節(jié)點和尾節(jié)點RIGHT的指針域特的指針域特殊（均為殊（均為NULL）；）； 優(yōu)點：方便找到節(jié)點的前驅節(jié)點。優(yōu)點：方便找到節(jié)點的前驅節(jié)點。雙向鏈表結點（雙向鏈表結點（Double-Linked List Node）DLNode的結構定義的結構定義template Struct DLNode T data; DLNode *left, *right ; DLNode ( ) left = right = NULL ; ; / 構造函數(shù)構造函數(shù) DLNode ( const T& item, SLNode *

25、 L = NULL, SLNode * R = NULL ) data = item ; left = L; right = R ; / 構造函數(shù)構造函數(shù) ;44 結點插入：在結點結點插入：在結點s之后插入結點之后插入結點 p 1. 1. 4321 sq算法算法DLInsert（s , p）/ 在結點在結點s的右邊插入結點的右邊插入結點p DLI1. right (s) / 若結點若結點s是尾結點是尾結點 IF right (s) THEN ( ( right (p) . left (p) s. right (s)p. RETURN. )DLI2. 插入插入 right (p) right (

26、s). left (p) s. left (right (s) p . right (s) p . 刪除結點刪除結點right(left(s) right(s)left(right(s) left(s) 算法算法DeleteNode（s）/ 刪除結點刪除結點s DN1.left (s) right (s) / 雙向鏈表中只有雙向鏈表中只有一個結點一個結點 IF left (s) right (s) THEN (打印打印“刪除結點以后，鏈表為空刪除結點以后，鏈表為空”. GOTO DN6.). DN2. left (s) / 當前結點是頭結點當前結點是頭結點 IF left (s) THEN (

27、left (right (s) . LEFT right (s) . GOTO DN6. ) . DN3. right (s) / 當前結點是尾結點當前結點是尾結點 IF right (s) THEN (right (left (s) . RIGHT left (s) . GOTO DN6.) DN4. 當前結點是中間結點當前結點是中間結點 (right (left (s) right (s) . left (right (s) left (s). ) DN5. 釋放空間釋放空間 AVAIL s.第二章第二章 線性表、堆棧和隊列線性表、堆棧和隊列 2.1 線性表的定義和基本操作線性表的定義和基本操作2.2 線性表的順序存儲結構線性表的順序存儲結構2.3 線性表的鏈接存儲結構線性表的鏈接存儲結構2.4 復雜性分析復雜性分析2.5 堆棧堆棧2.6 隊列隊列2.4 順序存儲和鏈式存儲的復雜性分析順序存儲和鏈式存儲的復雜性分析1、空間效率的比較、空間效率的比較 順序表所占用的空間來自于申請的數(shù)組空間，數(shù)組順序表所占用的空間來自于申請的數(shù)組空間，數(shù)組大小是大小是事先確定事先確定的，當表中的元素較少時，順序表