DS03_線性結(jié)構(gòu)a__陳越主編_數(shù)據(jù)結(jié)構(gòu)

1、第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) 1/253.1 引子引子【分析分析】多項(xiàng)式的關(guān)鍵數(shù)據(jù)是：多項(xiàng)式項(xiàng)數(shù)多項(xiàng)式的關(guān)鍵數(shù)據(jù)是：多項(xiàng)式項(xiàng)數(shù)n 、每一項(xiàng)的、每一項(xiàng)的系數(shù)系數(shù)ai （及相應(yīng)指數(shù)（及相應(yīng)指數(shù) i）。有）。有3種不同的方法。種不同的方法。一元多項(xiàng)式一元多項(xiàng)式 ：主要運(yùn)算：多項(xiàng)式相加、相減、相乘等主要運(yùn)算：多項(xiàng)式相加、相減、相乘等nnnnxaxaxaaxf1110)(方法方法1：采用順序存儲(chǔ)結(jié)構(gòu)直接表示：采用順序存儲(chǔ)結(jié)構(gòu)直接表示例例3.1 一元多項(xiàng)式及其運(yùn)算。134)(25xxxf例如：例如：下標(biāo)下標(biāo)i012345ai103004表示成：表示成：在數(shù)據(jù)的在數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)中中,一種常見而且簡(jiǎn)單

2、的結(jié)構(gòu)是一種常見而且簡(jiǎn)單的結(jié)構(gòu)是線性結(jié)構(gòu)線性結(jié)構(gòu)，即數(shù)據(jù)元素之間構(gòu)成一個(gè)有序的序列。即數(shù)據(jù)元素之間構(gòu)成一個(gè)有序的序列。方法方法2：采用：采用順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)表示多項(xiàng)式的表示多項(xiàng)式的非零項(xiàng)非零項(xiàng)。第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) 3.1 引子引子每個(gè)非零項(xiàng)每個(gè)非零項(xiàng) 涉及兩個(gè)信息：指數(shù)涉及兩個(gè)信息：指數(shù) 和系數(shù)和系數(shù) ，可以將一個(gè)多項(xiàng)式看成是一個(gè)可以將一個(gè)多項(xiàng)式看成是一個(gè) ( ， ) 二元組的集合二元組的集合。iixaiiaiai281213159)(xxxxP例如：例如： 和和 8213426)(68192xxxxP表示成：表示成：數(shù)組下標(biāo)i012數(shù)組下標(biāo)i0123系數(shù)9153系數(shù)2641

3、382指數(shù)1282指數(shù)19860P1(x)(b) P2(x) 相加過程：相加過程： 比較（比較（9, 12）和（）和（26，19），將（），將（26, 19）移到結(jié)果多項(xiàng)式；）移到結(jié)果多項(xiàng)式； 繼續(xù)比較（繼續(xù)比較（9, 12）和（）和（4，8），將（），將（9, 12）移到結(jié)果多項(xiàng)式；）移到結(jié)果多項(xiàng)式； 比較（比較（15, 8）和（）和（4，8），），15+（4）=11，不為，不為0，將新的一項(xiàng)（，將新的一項(xiàng)（11,8）增加到結(jié)果多項(xiàng)式；增加到結(jié)果多項(xiàng)式； 比較（比較（3,2）和（）和（13,6）, 將（將（13,6）移到結(jié)果多項(xiàng)式；）移到結(jié)果多項(xiàng)式； 比較（比較（3,2）和（）和（82,0）

4、, 將（將（3,2）移到結(jié)果多項(xiàng)式；）移到結(jié)果多項(xiàng)式； 將（將（82,0）直接移到結(jié)果多項(xiàng)式。）直接移到結(jié)果多項(xiàng)式。最后得到的結(jié)果多項(xiàng)式是：最后得到的結(jié)果多項(xiàng)式是：( (26,19), (9,12), (11,8), (13,6), (3,2), (82,0) ) 8231311926)(26812192xxxxxxP2/25方法方法3：采用：采用鏈表結(jié)構(gòu)鏈表結(jié)構(gòu)來存儲(chǔ)多項(xiàng)式的來存儲(chǔ)多項(xiàng)式的非零項(xiàng)非零項(xiàng)。每個(gè)鏈表每個(gè)鏈表結(jié)點(diǎn)結(jié)點(diǎn)存儲(chǔ)多項(xiàng)式中的一個(gè)存儲(chǔ)多項(xiàng)式中的一個(gè)非零項(xiàng)非零項(xiàng)，包括，包括系數(shù)和指數(shù)系數(shù)和指數(shù)兩個(gè)數(shù)據(jù)域以及一個(gè)兩個(gè)數(shù)據(jù)域以及一個(gè)指針域指針域，表示為：，表示為：coefexponl

5、inktypedef struct PolyNode *Polynomial;typedef struct PolyNode int coef;int expon;Polynomial link;例如例如:281213159)(xxxxP8213426)(68192xxxxP鏈表存儲(chǔ)形式為：鏈表存儲(chǔ)形式為：第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) 3.1 引子引子9 12 P1P215 8 3 2 NULL26 19 4 8 13 682 0 NULL3/25例例3.2 二元多項(xiàng)式又該如何表示？二元多項(xiàng)式又該如何表示？比如，給定二元多項(xiàng)式：比如，給定二元多項(xiàng)式： 【分析分析】 可以將上述二元多項(xiàng)式看成關(guān)于

6、可以將上述二元多項(xiàng)式看成關(guān)于x 的一元多項(xiàng)式的一元多項(xiàng)式 28381221231549),(xyxyxxyxyxP2831223)15()49(),(xxyyxyyxP所以，上述二元多項(xiàng)式可以用所以，上述二元多項(xiàng)式可以用“復(fù)雜復(fù)雜”鏈表鏈表表示為：表示為：第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) 3.1 引子引子圖圖3.4 二元多項(xiàng)式非零項(xiàng)的鏈表表示二元多項(xiàng)式非零項(xiàng)的鏈表表示 12 P 8 3 2 NULL9 2 4 0 NULL15 31 1 NULL4/25我們可以研究更一般的有序?qū)ο笮蛄械慕M織與管理方法，我們可以研究更一般的有序?qū)ο笮蛄械慕M織與管理方法，下一節(jié)將引出下一節(jié)將引出線性表線性表的抽象定義

7、，分別討論基于的抽象定義，分別討論基于順序存儲(chǔ)順序存儲(chǔ)和和鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)的線性表實(shí)現(xiàn)方法；并探討線性表的基本操作的線性表實(shí)現(xiàn)方法；并探討線性表的基本操作插入元素插入元素和和刪除元素刪除元素。第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) 3.1 引子引子4/25第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) 5/253.2 線性表的定義與實(shí)現(xiàn)線性表的定義與實(shí)現(xiàn)【定義定義】“線性表線性表(Linear List)”是由同一類型的是由同一類型的數(shù)據(jù)元素?cái)?shù)據(jù)元素構(gòu)成的構(gòu)成的有序有序序列序列的線性結(jié)構(gòu)。的線性結(jié)構(gòu)。 線性表中元素的個(gè)數(shù)稱為線性表的線性表中元素的個(gè)數(shù)稱為線性表的長(zhǎng)度長(zhǎng)度； 當(dāng)一個(gè)線性表中沒有元素（長(zhǎng)度為當(dāng)一個(gè)線性表中沒有

8、元素（長(zhǎng)度為0）時(shí)，稱為）時(shí)，稱為空表空表； 表的起始位置稱表的起始位置稱表頭表頭，表的結(jié)束位置稱，表的結(jié)束位置稱表尾表尾。, 類型名稱：類型名稱：線性表（線性表（List）數(shù)據(jù)對(duì)象集：數(shù)據(jù)對(duì)象集：線性表是線性表是 n (0)個(gè)元素構(gòu)成的有序序列個(gè)元素構(gòu)成的有序序列( a1, a2, ,an ) ； ai+1稱為稱為 ai的直接后繼，的直接后繼， ai-1為為 ai的直接前驅(qū)；直接前驅(qū)和直接后繼反映了元素之間的直接前驅(qū)；直接前驅(qū)和直接后繼反映了元素之間一對(duì)一的鄰接邏輯關(guān)系。一對(duì)一的鄰接邏輯關(guān)系。操作集：操作集：對(duì)于一個(gè)具體的線性表對(duì)于一個(gè)具體的線性表L List，一個(gè)表示位置的整數(shù)，一個(gè)表示位

9、置的整數(shù)i，一個(gè)元素，一個(gè)元素X ElementType，線性表的基本操作主要有：，線性表的基本操作主要有：1、List MakeEmpty()：初始化一個(gè)新的空線性表初始化一個(gè)新的空線性表L；2、ElementType FindKth( int K, List L )：根據(jù)指定的位序：根據(jù)指定的位序K，返回相應(yīng)元素，返回相應(yīng)元素 ；3、int Find( ElementType X, List L )：已知：已知X，返回線性表，返回線性表L中與中與X相同的第一相同的第一個(gè)元素的相應(yīng)位序個(gè)元素的相應(yīng)位序i；若不存在則返回空；若不存在則返回空；4、void Insert( ElementType

10、 X, int i, List L)：指定位序：指定位序i前插入一個(gè)新元素前插入一個(gè)新元素X；5、void Delete( int i, List L )：刪除指定位序：刪除指定位序i的元素；的元素；6、int Length( List L )：返回線性表：返回線性表L的長(zhǎng)度的長(zhǎng)度n。 線性表的順序存儲(chǔ)實(shí)現(xiàn)線性表的順序存儲(chǔ)實(shí)現(xiàn)第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) 3.2.1 線性表的線性表的順序存儲(chǔ)實(shí)現(xiàn)順序存儲(chǔ)實(shí)現(xiàn)在內(nèi)存中用在內(nèi)存中用地址連續(xù)的一塊存儲(chǔ)空間順序存放地址連續(xù)的一塊存儲(chǔ)空間順序存放線性表的各元線性表的各元素。素。一維數(shù)組一維數(shù)組在內(nèi)存中占用的存儲(chǔ)空間就是一組連續(xù)的存儲(chǔ)區(qū)域在內(nèi)存中占用的存儲(chǔ)

11、空間就是一組連續(xù)的存儲(chǔ)區(qū)域。typedef struct ElementType DataMAXSIZE; int Last; /*當(dāng)前的最后一個(gè)元素的下標(biāo)當(dāng)前的最后一個(gè)元素的下標(biāo)*/ List; List L, *PtrL;下標(biāo)下標(biāo)i01i-1in-1MAXSIZE-1Dataa1a2aiai+1an-Last訪問下標(biāo)為訪問下標(biāo)為 i 的元素：的元素：L.Datai 或或 PtrL-Datai線性表的長(zhǎng)度：線性表的長(zhǎng)度：L.Last+1 或或 PtrL-Last+16/251. 初始化（建立空的順序表）初始化（建立空的順序表）第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) 主要操作的主要操作的實(shí)現(xiàn)實(shí)現(xiàn)List

12、 *MakeEmpty( ) List *PtrL; PtrL = (List *)malloc( sizeof(List) ); PtrL-Last = -1; return PtrL;2. 查找查找int Find( ElementType X, List *PtrL ) int i = 0; while( i Last & PtrL-Datai!= X ) i+; if (i PtrL-Last) return -1; /* 如果沒找到，返如果沒找到，返回回-1 */ else return i; /* 找到后返回的是存儲(chǔ)位置找到后返回的是存儲(chǔ)位置 */查找成功的平均比較次數(shù)為查

13、找成功的平均比較次數(shù)為(n +1)/2，平均時(shí)間性能為，平均時(shí)間性能為 O(n)。3.2.1 線性表的線性表的順序存儲(chǔ)實(shí)現(xiàn)順序存儲(chǔ)實(shí)現(xiàn)7/25第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) 下標(biāo)下標(biāo)i01i-1in-1MAXSIZE-1Dataa1a2aiai+1an-Last下標(biāo)下標(biāo)i01i-1ii+1nSIZE-1Dataa1a2aiai+1an-Last3. 插入插入（第（第 i (1in+1)個(gè)位置上插入一個(gè)值為個(gè)位置上插入一個(gè)值為X的新元素的新元素)先移動(dòng)，再插入先移動(dòng)，再插入X3.2.1 線性表的線性表的順序存儲(chǔ)實(shí)現(xiàn)順序存儲(chǔ)實(shí)現(xiàn)8/25 插入算法插入算法第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) void Ins

14、ert( ElementType X, int i, List *PtrL ) int j; if ( PtrL-Last = MAXSIZE-1 ) /* 表空間已滿，不能插入表空間已滿，不能插入*/ printf(表滿表滿); return; if ( i PtrL-Last+2) /*檢查插入位置的合法性檢查插入位置的合法性*/ printf(位置不合法位置不合法); return; for ( j = PtrL-Last; j = i-1; j- ) PtrL-Dataj+1 = PtrL-Dataj; /*將將 ai an倒序向后移動(dòng)倒序向后移動(dòng)*/ PtrL-Datai-1 = X

15、; /*新元素插入新元素插入*/ PtrL-Last+; /*Last仍指向最后元素仍指向最后元素*/ return; 平均移動(dòng)次數(shù)為平均移動(dòng)次數(shù)為 n /2，平均，平均時(shí)間性能為時(shí)間性能為 O(n)。3.2.1 線性表的線性表的順序存儲(chǔ)實(shí)現(xiàn)順序存儲(chǔ)實(shí)現(xiàn)9/25第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) 下標(biāo)下標(biāo)i01i-1in-1MAXSIZE-1Dataa1a2aiai+1an-Last下標(biāo)下標(biāo)i01i-1n-2n-1MAXSIZE-1Dataa1a2ai+1anan-Last4. 刪除刪除（刪除表的第（刪除表的第 i (1in)個(gè)位置上的元素個(gè)位置上的元素)后面的元素依次前移后面的元素依次前移3.2.

16、1 線性表的線性表的順序存儲(chǔ)實(shí)現(xiàn)順序存儲(chǔ)實(shí)現(xiàn)10/25 刪除刪除算法算法第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) void Delete( int i, List *PtrL ) int j; if( i PtrL-Last+1 ) /*檢查空表及刪除位置的合法性檢查空表及刪除位置的合法性*/ printf (“不存在第不存在第%d個(gè)元素個(gè)元素”, i ); return ; for ( j = i; j Last; j+ ) PtrL-Dataj-1 = PtrL-Dataj; /*將將 ai+1 an順序向前移動(dòng)順序向前移動(dòng)*/ PtrL-Last-; /*Last仍指向最后元素仍指向最后元素*/ r

17、eturn; 平均移動(dòng)次數(shù)為平均移動(dòng)次數(shù)為 (n-1) /2，平均時(shí)間性能為平均時(shí)間性能為 O(n)。3.2.1 線性表的線性表的順序存儲(chǔ)實(shí)現(xiàn)順序存儲(chǔ)實(shí)現(xiàn)11/25 線性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)線性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) 不要求邏輯上相鄰的兩個(gè)數(shù)據(jù)元素物理上也相鄰不要求邏輯上相鄰的兩個(gè)數(shù)據(jù)元素物理上也相鄰，它是通過，它是通過“鏈鏈”建立起數(shù)據(jù)元素之間的邏輯關(guān)系。建立起數(shù)據(jù)元素之間的邏輯關(guān)系。因此對(duì)線性表的插入、因此對(duì)線性表的插入、刪除刪除不需要移動(dòng)數(shù)據(jù)元素不需要移動(dòng)數(shù)據(jù)元素，只需要修改，只需要修改“鏈鏈”。typedef struct Node ElementType Data;

18、 struct Node *Next; List; List L, *PtrL;訪問序號(hào)為訪問序號(hào)為 i 的元素？的元素？求線性表的長(zhǎng)度？求線性表的長(zhǎng)度？3.2.3 線性表的鏈?zhǔn)骄€性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)存儲(chǔ)實(shí)現(xiàn)12/251.求表長(zhǎng)求表長(zhǎng)第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) 主要操作的主要操作的實(shí)現(xiàn)實(shí)現(xiàn)int Length ( List *PtrL ) List *p = PtrL; /* p指向表的第一個(gè)結(jié)點(diǎn)指向表的第一個(gè)結(jié)點(diǎn)*/ int j = 0; while ( p ) p = p-Next; j+; /* 當(dāng)前當(dāng)前p指向的是第指向的是第 j 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)*/ return j;時(shí)間性能為時(shí)間性能為

19、 O(n)。3.2.3 線性表的鏈?zhǔn)骄€性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)存儲(chǔ)實(shí)現(xiàn)13/25第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) 2. 查找查找List *FindKth( int K, List *PtrL ) List *p = PtrL; int i = 1; while (p !=NULL & i Next; i+; if ( i = K ) return p; /* 找到第找到第K個(gè)，返回指針個(gè)，返回指針 */ else return NULL; /* 否則返回空否則返回空 */List *Find( ElementType X, List *PtrL ) List *p = PtrL; while

20、( p!=NULL & p-Data != X ) p = p-Next; return p;（1）按序號(hào)查找）按序號(hào)查找: FindKth; （2）按值查找）按值查找: Find平均時(shí)間性能為平均時(shí)間性能為 O(n)。3.2.3 線性表的鏈?zhǔn)骄€性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)存儲(chǔ)實(shí)現(xiàn)14/25第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) 3. 插入插入（在鏈表的第（在鏈表的第 i-1(1in+1)個(gè)結(jié)點(diǎn)后插入一個(gè)值為個(gè)結(jié)點(diǎn)后插入一個(gè)值為X的的新結(jié)點(diǎn)新結(jié)點(diǎn))（1）先構(gòu)造一個(gè)）先構(gòu)造一個(gè)新結(jié)點(diǎn)新結(jié)點(diǎn)，用，用s指向；指向；（2）再找到鏈表的第）再找到鏈表的第 i-1個(gè)結(jié)點(diǎn)，用個(gè)結(jié)點(diǎn)，用p指向；指向；（3）然后修改指針，

21、插入結(jié)點(diǎn)）然后修改指針，插入結(jié)點(diǎn) ( p之后插入新結(jié)點(diǎn)之后插入新結(jié)點(diǎn)是是 s)headpss-Next = p-Next;p-Next = s; 3.2.3 線性表的鏈?zhǔn)骄€性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)存儲(chǔ)實(shí)現(xiàn)思考思考: 修改指針的兩個(gè)步驟如果交換一下，將會(huì)發(fā)生什么修改指針的兩個(gè)步驟如果交換一下，將會(huì)發(fā)生什么?15/25 插入算法插入算法第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) List *Insert( ElementType X, int i, List *PtrL ) List *p, *s; if ( i = 1 ) /* 新結(jié)點(diǎn)插入在表頭新結(jié)點(diǎn)插入在表頭 */ s = (List *)malloc(size

22、of(List); /*申請(qǐng)、填裝結(jié)點(diǎn)申請(qǐng)、填裝結(jié)點(diǎn)*/ s-Data = X; s-Next = PtrL; return s; /*返回新表頭指針返回新表頭指針*/ p = FindKth( i-1, PtrL ); /* 查找第查找第i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) */ if ( p = NULL ) /* 第第i-1個(gè)不存在，不能插入個(gè)不存在，不能插入 */ printf(參數(shù)參數(shù)i錯(cuò)錯(cuò)); return NULL; else s = (List *)malloc(sizeof(List); /*申請(qǐng)、填裝結(jié)點(diǎn)申請(qǐng)、填裝結(jié)點(diǎn)*/ s-Data = X; s-Next = p-Next; /*新結(jié)點(diǎn)

23、插入在第新結(jié)點(diǎn)插入在第i-1個(gè)結(jié)點(diǎn)的后面?zhèn)€結(jié)點(diǎn)的后面*/ p-Next = s; return PtrL; 平均查找次數(shù)為平均查找次數(shù)為 n /2，平均，平均時(shí)間性能為時(shí)間性能為 O(n)?？毡頃r(shí)的插入要作為空表時(shí)的插入要作為特例特例，除非單鏈表帶除非單鏈表帶虛頭結(jié)點(diǎn)虛頭結(jié)點(diǎn)。3.2.3 線性表的鏈?zhǔn)骄€性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)存儲(chǔ)實(shí)現(xiàn)16/25第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) （1）先找到鏈表的第）先找到鏈表的第 i-1個(gè)結(jié)點(diǎn)，用個(gè)結(jié)點(diǎn)，用p指向；指向；（2）再用指針）再用指針s指向要被刪除的結(jié)點(diǎn)（指向要被刪除的結(jié)點(diǎn)（p的下一個(gè)結(jié)點(diǎn)）的下一個(gè)結(jié)點(diǎn)）;headps = p-Next;4. 刪除刪除（刪除鏈

24、表的第（刪除鏈表的第 i (1in)個(gè)位置上的結(jié)點(diǎn)個(gè)位置上的結(jié)點(diǎn))（3）然后修改指針，刪除）然后修改指針，刪除s所指結(jié)點(diǎn)所指結(jié)點(diǎn);（4）最后釋放）最后釋放s所指結(jié)點(diǎn)的空間。所指結(jié)點(diǎn)的空間。p-Next = s-next; free（s）;3.2.3 線性表的鏈?zhǔn)骄€性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)存儲(chǔ)實(shí)現(xiàn)思考思考: 操作指針的幾個(gè)步驟如果隨意改變，將會(huì)發(fā)生什么操作指針的幾個(gè)步驟如果隨意改變，將會(huì)發(fā)生什么?17/25 刪除刪除算法算法第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) List *Delete( int i, List *PtrL ) List *p, *s; if ( i = 1 ) /* 若要?jiǎng)h除的是表的第一個(gè)結(jié)

25、點(diǎn)若要?jiǎng)h除的是表的第一個(gè)結(jié)點(diǎn) */ s = PtrL; /*s指向第指向第1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)*/ PtrL = PtrL-Next; /*從鏈表中刪除從鏈表中刪除*/ free(s); /*釋放被刪除結(jié)點(diǎn)釋放被刪除結(jié)點(diǎn) */ return PtrL; p = FindKth( i-1, PtrL ); /*查找第查找第i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)*/ if ( p = NULL ) printf(“第第%d個(gè)結(jié)點(diǎn)不存在個(gè)結(jié)點(diǎn)不存在”, i-1); return NULL; else if ( p-Next = NULL ) printf(“第第%d個(gè)結(jié)點(diǎn)不存在個(gè)結(jié)點(diǎn)不存在”, i); return NULL

26、; else s = p-Next; /*s指向第指向第i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)*/ p-Next = s-Next; /*從鏈表中刪除從鏈表中刪除*/ free(s); /*釋放被刪除結(jié)點(diǎn)釋放被刪除結(jié)點(diǎn) */ return PtrL; 平均查找次數(shù)為平均查找次數(shù)為 n /2，平均時(shí)間性能為平均時(shí)間性能為 O(n)。第一個(gè)結(jié)點(diǎn)的刪除要作為第一個(gè)結(jié)點(diǎn)的刪除要作為特特例例，除非單鏈表帶，除非單鏈表帶虛頭結(jié)點(diǎn)虛頭結(jié)點(diǎn)。3.2.3 線性表的鏈?zhǔn)骄€性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)存儲(chǔ)實(shí)現(xiàn)18/25 廣義表廣義表【例例】如何表示一個(gè)單位的人員情況。一種簡(jiǎn)單的表示方法是用一個(gè)如何表示一個(gè)單位的人員情況。一種簡(jiǎn)單的表示方法是用一個(gè)線

27、性表來表示，其先后順序按照進(jìn)單位的時(shí)間順序排列：線性表來表示，其先后順序按照進(jìn)單位的時(shí)間順序排列：（張三，李四，王五，錢六，孫七，（張三，李四，王五，錢六，孫七，） 如何體現(xiàn)三個(gè)不同部門？比如辦公室、生產(chǎn)部、銷售部。同一個(gè)部如何體現(xiàn)三個(gè)不同部門？比如辦公室、生產(chǎn)部、銷售部。同一個(gè)部門放在一起。那么可以用三個(gè)有序序列的子表構(gòu)成的線性表來表示：門放在一起。那么可以用三個(gè)有序序列的子表構(gòu)成的線性表來表示：（張三，（張三，），（李四，孫七，），（李四，孫七，），（王五，錢六，），（王五，錢六，） 如果想表示這個(gè)單位的負(fù)責(zé)人是誰，可將負(fù)責(zé)人作為表的第一元素：如果想表示這個(gè)單位的負(fù)責(zé)人是誰，可將負(fù)責(zé)人作為

28、表的第一元素： （丁一，（張三，（丁一，（張三，），（李四，孫七，），（李四，孫七，），（王五，錢），（王五，錢六，六，）【定義定義】上述這類表就是一種上述這類表就是一種“廣義表廣義表(Generalized List)”。 廣義表是廣義表是線性表的推廣線性表的推廣。 廣義表與線性表一樣，也是廣義表與線性表一樣，也是 由由n個(gè)元素組成的個(gè)元素組成的有序序列有序序列。 不同點(diǎn)在于，對(duì)于線性表而言，不同點(diǎn)在于，對(duì)于線性表而言， n個(gè)元素都是基本的個(gè)元素都是基本的單元素單元素。 而在廣義表中，這些元素不僅可以是單元素也可以是而在廣義表中，這些元素不僅可以是單元素也可以是另一個(gè)廣義表另一個(gè)廣義表。第第

29、3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) 3.2.4 廣義表與多重鏈表廣義表與多重鏈表19/25 廣義表的數(shù)據(jù)結(jié)構(gòu)可以定義如下：廣義表的數(shù)據(jù)結(jié)構(gòu)可以定義如下：第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) typedef struct GNode int Tag; /*標(biāo)志域：標(biāo)志域：0表示該結(jié)點(diǎn)是單元素，表示該結(jié)點(diǎn)是單元素，1表示該結(jié)點(diǎn)是廣義表表示該結(jié)點(diǎn)是廣義表 */ union /* 子表指針域子表指針域Sublist與單元素?cái)?shù)據(jù)域與單元素?cái)?shù)據(jù)域Data復(fù)用，即共用存儲(chǔ)空間復(fù)用，即共用存儲(chǔ)空間 */ ElementType Data; struct GNode *SubList; URegion; struct GNode

30、 *Next; /* 指向后繼結(jié)點(diǎn)指向后繼結(jié)點(diǎn) */ GList;圖圖3.7 廣義表廣義表結(jié)構(gòu)結(jié)構(gòu)TagDataNextSubList0 丁一丁一0 張三張三0 李四李四0 孫七孫七0 錢六錢六0 王五王五111NULLHeader3.2.4 廣義表與多重鏈表廣義表與多重鏈表20/25 多重鏈表多重鏈表第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) 【定義定義】在圖在圖.7的例子中，廣義表采用鏈表存儲(chǔ)的方式實(shí)現(xiàn)。的例子中，廣義表采用鏈表存儲(chǔ)的方式實(shí)現(xiàn)。像這種像這種鏈表，其元素可能還是另一個(gè)子鏈表的起點(diǎn)指針，鏈表，其元素可能還是另一個(gè)子鏈表的起點(diǎn)指針，叫叫“多重鏈表多重鏈表”。 一般來說，多重鏈表中每個(gè)結(jié)點(diǎn)的一般

31、來說，多重鏈表中每個(gè)結(jié)點(diǎn)的指針域會(huì)有多個(gè)指針域會(huì)有多個(gè)，如前面的例，如前面的例子包含了子包含了Next和和SubList兩個(gè)指針域。兩個(gè)指針域。 但包含兩個(gè)指針域的鏈表并不一定是多重鏈表，比如但包含兩個(gè)指針域的鏈表并不一定是多重鏈表，比如雙向鏈表不雙向鏈表不是多重鏈表是多重鏈表。 多重鏈表在數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)中有廣泛的用途，基本上如多重鏈表在數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)中有廣泛的用途，基本上如樹、圖樹、圖這樣這樣相對(duì)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)都相對(duì)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)都可以采用多重鏈表可以采用多重鏈表的方式實(shí)現(xiàn)存儲(chǔ)。的方式實(shí)現(xiàn)存儲(chǔ)。3.2.4 廣義表與多重鏈表廣義表與多重鏈表21/25例例3.3 矩陣可以用二維數(shù)組表示，但二維數(shù)組表

32、示有兩個(gè)缺陷：矩陣可以用二維數(shù)組表示，但二維數(shù)組表示有兩個(gè)缺陷： 一是數(shù)組的一是數(shù)組的大小需要事先確定大小需要事先確定， 另一個(gè)是當(dāng)矩陣包含許多另一個(gè)是當(dāng)矩陣包含許多0元素時(shí)，將造成大量的元素時(shí)，將造成大量的存儲(chǔ)空間浪費(fèi)存儲(chǔ)空間浪費(fèi)。例如，對(duì)于下面例如，對(duì)于下面A和和B這樣的這樣的“稀疏矩陣稀疏矩陣 ”最好是最好是只存儲(chǔ)非只存儲(chǔ)非0元素元素。如何用多重鏈表方式實(shí)現(xiàn)存儲(chǔ)？如何用多重鏈表方式實(shí)現(xiàn)存儲(chǔ)？【分析分析】 采用一種典型的多重鏈表采用一種典型的多重鏈表十字鏈表十字鏈表來存儲(chǔ)稀疏矩陣。來存儲(chǔ)稀疏矩陣。 鏈表中用于存放矩陣非鏈表中用于存放矩陣非0元素的每個(gè)結(jié)點(diǎn)有元素的每個(gè)結(jié)點(diǎn)有兩個(gè)指針域兩個(gè)指針

33、域：一個(gè)是行指針一個(gè)是行指針(或稱為向右指針或稱為向右指針)Right，另一個(gè)是列指針（或稱為向下指針）另一個(gè)是列指針（或稱為向下指針）Down。 結(jié)點(diǎn)的結(jié)點(diǎn)的數(shù)據(jù)域數(shù)據(jù)域存放元素的行坐標(biāo)存放元素的行坐標(biāo)Row、列坐標(biāo)、列坐標(biāo)Col和數(shù)值和數(shù)值Value。第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) 3.2.4 廣義表與多重鏈表廣義表與多重鏈表120012304000000270020018A005006710002001390000001430001120B22/25 用用一個(gè)標(biāo)識(shí)域一個(gè)標(biāo)識(shí)域Tag來來區(qū)分頭結(jié)點(diǎn)和非區(qū)分頭結(jié)點(diǎn)和非0元素結(jié)點(diǎn)元素結(jié)點(diǎn)：頭節(jié)點(diǎn)的標(biāo)識(shí)值為頭節(jié)點(diǎn)的標(biāo)識(shí)值為“Head”，矩陣非，矩陣非0元素結(jié)點(diǎn)的標(biāo)識(shí)值為元素結(jié)點(diǎn)的標(biāo)識(shí)值為“Term”。第第3章章 線性結(jié)構(gòu)線性結(jié)構(gòu) (a) 結(jié)點(diǎn)的總體結(jié)構(gòu)結(jié)點(diǎn)的總體結(jié)構(gòu)(b