《線性表(數(shù)據(jù)結(jié)構(gòu)重難點(diǎn)講解)》由會員分享，可在線閱讀，更多相關(guān)《線性表(數(shù)據(jù)結(jié)構(gòu)重難點(diǎn)講解)(104頁珍藏版)》請?jiān)谌巳宋膸炀W(wǎng)上搜索。

1、線性表(數(shù)據(jù)結(jié)構(gòu)重難點(diǎn)講解)導(dǎo)讀：就愛閱讀網(wǎng)友為您分享以下“線性表(數(shù)據(jù)結(jié)構(gòu)重難點(diǎn)講解)”資訊，希望對您有所幫助，感謝您對92to.com的支持!第二章 線性表線性結(jié)構(gòu)特點(diǎn)：在數(shù)據(jù)元素的非空有限集中存在唯一的一個被稱作“第一個”的數(shù)據(jù)元素 存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素 除第一個外，集合中的每個數(shù)據(jù)元素均只有一個 前驅(qū) 除最后一個外，集合中的每個數(shù)據(jù)元素均只有一 個后繼12.1 線性表的邏輯結(jié)構(gòu)定義：一個線性表是n個數(shù)據(jù)元素的有限序列如 (a 1 , a 2 ,L L , a i , L L a n)例 英文字母表(A,B,C,.Z)是一個線性表例學(xué)號 001 002 姓名 張三 。

2、李四 年齡 18 19 數(shù)據(jù)元素【注】數(shù)據(jù)項(xiàng)、記錄、文件；2特征：v元素個數(shù)n 表長度，n=0 空表 v在一個非空表 (a1，a2，ai，an-1，an) 中的每個數(shù)據(jù)元素都有一個確定的位置， ai是 第i個數(shù)據(jù)元素，稱i為數(shù)據(jù)元素ai在線性表中的 位序。 v1in時lai的直接前驅(qū)是ai1 ，a1無直接前驅(qū) lai的直接后繼是ai1 ，an無直接后繼v元素同構(gòu)，且不能出現(xiàn)缺項(xiàng)3抽象數(shù)據(jù)類型線性表的定義：ADT List 數(shù)據(jù)對象： D= ai| aiElemtype，i=1，2，n，n=0 數(shù)據(jù)關(guān)系： R= ai-1，ai| ai-1，aiD，i=2，3，n 基本操作： InitList(&。

3、L) 操作結(jié)果：創(chuàng)建一個空的線性表L。 DestroyList(&L) 初始條件：線性表L已存在。 操作結(jié)果：銷毀線性表。 ClearList(&L) 初始條件：線性表L已存在。 操作結(jié)果：將L重置為空表。4ListEmpty(L) 初始條件：線性表L已存在。 操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE。 ListLength(L) 初始條件：線性表L已存在。 操作結(jié)果：返回L中數(shù)據(jù)元素個數(shù)。 GetElem(L,i,&e) 初始條件：線性表L已存在，1iListLength(L)。 操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值。 LocateElem(L,e,compare( ) 。

4、初始條件：線性表L已存在，compare()是數(shù)據(jù)元素判定函數(shù)。 操作結(jié)果：返回L中第1個與e滿足關(guān)系compare()的數(shù)據(jù)元素 的位序。若這樣的數(shù)據(jù)元素不存在，則返回值為0。5PriorElem(L,cur_e,&pre_e) 初始條件：線性表L已存在。 操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是第一，則用 pre_e返回它的前驅(qū)，否則操作失敗，pre_e無定義。 NextElem(L,cur_e,&next_e) 初始條件：線性表L已存在。 操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個，則 用next_e返回它的后繼，否則操作失敗， next_e無定義。 ListInsert(。

5、&L,i,e) 初始條件：線性表L已存在，1iListLength(L)+1。 操作結(jié)果：在L中第i個位置之前插入新的數(shù)據(jù)元素e，L 的長度加1。6ListDelete(&L,i,&e) 初始條件：線性表L已存在且非空，1iListLength(L)。 操作結(jié)果：刪除L的第i個數(shù)據(jù)元素，并用e返回其值，L的 長度減1。 ListTraverse(L,visit( ) 初始條件：線性表L已存在。 操作結(jié)果：依： O( ListLength(La) + ListLength(Lb)152.2 線性表的順序存儲結(jié)構(gòu)順序表：v定義：用一組地址連續(xù)的存儲單元依次存放線 性表的數(shù)據(jù)元素。 v元素地址計(jì)算方。

6、法：lLOC(ai)=LOC(a1)+(i-1)*L lLOC(ai+1)=LOC(ai)+Ll其中： uL 一個元素占用的存儲單元個數(shù) uLOC(ai) 線性表第i個元素的地址 uLOC(a1) 線性表的第一個數(shù)據(jù)元素的 存儲位置，稱為線性表的起始位置或基地址。16v特點(diǎn)：l實(shí)現(xiàn)邏輯上相鄰物理地址相鄰 l實(shí)現(xiàn)隨機(jī)存取 v實(shí)現(xiàn)：可用C語言的一維數(shù)組實(shí)現(xiàn)17存儲地址 b b+l內(nèi)存元素序號 1 2 typedef int ElemType; #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10a1a2b+(i-1)*l b+(n-1)*l b+n。

7、*lai ani ntypedef struct ElemType *elem;/存儲空 備 用 空 間間基址int length; /當(dāng)前長度 int listsize; /當(dāng)前分配的存儲容量b+(maxlen-1)*lSqList;數(shù)據(jù)元素不是簡單類型時,可定義結(jié)構(gòu)體數(shù)組18初始化v(生成大小為LISTINITSIZE的線性表)Status InitList_Sq(Sqlist &L) /構(gòu)造一個空的線性表LL.elem=(ElemType *)malloc(LIST_INIT-SIZE*sizeof(ElemType);If (！L.elem) exit(OVERFLOW); /存儲分配。

8、失敗；L.length=0;L.listsize=LIST_INIT-SIZE; return OK; / InitList_Sq;/空表長度為0；/ 初始存儲容量；19動態(tài)申請和釋放內(nèi)存 ( #includestdlib.h )ELEMTYPE *p=(ELEMTYPE *)malloc(M*sizeof(ELEMTYPE); / 分配size字節(jié)的存儲區(qū)，函數(shù)返回所分配的內(nèi)存起始地址，如 內(nèi)存不足，則返回0；free( p );/ 釋放p所指的內(nèi)存區(qū)，無函數(shù)返回值； ELEMTYPE *p=(ELEMTYPE *) realloc (ELEMTYPE *p, unsigned size);。

9、 /將p所指的已分配內(nèi)存區(qū)的大小改為size，size可比原來分配的 空間大或小。函數(shù)返回指向該內(nèi)存區(qū)的指針。20插入v定義：線性表的插入是指在第i(1i n+1) 個元素之前插入一個新的數(shù)據(jù)元素x，使長度 為n的線性表變?yōu)閚+1(a(a11, a 2 ,L L , a i - 1 , a i , L L a n)變成長度為n+1的線性表, a 2 ,L L , a i - 1 , x , a i , L L a n需將第i至第n共(n-i+1)個元素后移21數(shù)組下標(biāo) 0內(nèi)存 元素序號a1數(shù)組下標(biāo) 0 1內(nèi)存 元素序號a1 a2 1 21 21a2i-1 iai ai+1i i+1i-1 ix。

10、ai ai+1i i+1n-1 nannn-1 nan-1 annn+1n+122v算法status ListInsert_Sq(SqList &L, int i, ElemType e) /在順序線性表L中第i個位置之前插入新元素e， / i的合法位置為1=i=ListLength_Sq(L)+1; if (i1|iL.length+1) return ERROR; /i值不合法 if(L.length=L.listsize) /空間不夠 newbase=(ElemType * ) realloc ( L.elem,(L.listsize+LISTINCREMENT)*sizeof( Ele。

11、mType ) );if (!newbase) exit(OVERFLOW); / 存儲分配失敗 L.elem=newbase; / 新基址 L.listsize+=LISTINCREMENT; / 增加存儲容量 23q=&L.elemi-1; / q為插入位置，數(shù)組下標(biāo)默認(rèn)從0開始 for( p=&L.elemL.length-1 ; p=q ; p-) *(p+1)=*p; /插入位置及之后元素右移 *q=e; /插入e +L.length; /表長增加1 return OK; / ListInsert_Sq24v算法時間復(fù)雜度T(n)l設(shè)Pi是在第i個元素之前插入一個元素的概率， 則在長。

12、度為n的線性表中插入一個元素時，所需 移動的元素次數(shù)的平均次數(shù)為：Eis =n +1Pi ( n - i + 1 )i =1若認(rèn)為 Pi = 則 Eis = n 11 n +1n +1+1( n - i + 1) =n 2i =1 T (n ) = O (n )25刪除v定義：線性表的刪除是指將第i(1i n)個元 素刪除，使長度為n的線性表(a(a1, a 2 ,L L , a i - 1 , a i , L L a n)變成長度為n-1的線性表1, a 2 ,L L , a i - 1 , a i + 1 , L L a n需將第i+1至第n共(n-i)個元素前移26數(shù)組下標(biāo) 0 1內(nèi)存 。

13、元素序號a1 a2 1 2數(shù)組下標(biāo) 0 1內(nèi)存 元素序號a1 a2 1 2i-1 iai ai+1i i+1i-1 iai+1ai+2i i+1n-1 nann n+1n-2 n-1ann-1n27v 算法Status ListDelete_sq( Sqlist & L, int i, ElemType &e) /在順序線性表L中刪除第i個位置元素e， / i的合法位置為 1= i =Listlength_sq(L); if (i1|iL.length) return ERROR; / I 值不合法 p=&L.elemi-1; /p為被刪除的元素位置 e=*p; /被刪除元素值賦給e q=&L。

14、.elemL.length-1; /表尾元素位置 for(+p;p=q;+p) *(p-1)=*p; /被刪除元素之后的元素右移 - -L.length; /表長減1 return OK; / ListDelete_sq28v算法評價 l設(shè)Qi是刪除第i個元素的概率，則在長度為n的線 性表中刪除一個元素所需移動的元素次數(shù)的平均 n 次數(shù)為：E de =Q i (n - i)i =1若認(rèn)為 Q i = 則 E de = 1 n1 n (n - i) = n -1 2ni =1 T (n ) = O (n )故在順序表中插入或刪除一個元素時，平均移 動表的一半元素，當(dāng)n很大時，效率很低29順序存儲。

15、結(jié)構(gòu)的優(yōu)缺點(diǎn)v優(yōu)點(diǎn) l邏輯相鄰，物理相鄰 l可隨機(jī)存取任一元素 l存儲空間使用緊湊 v缺點(diǎn) l插入、刪除操作需要移動大量的元素 l預(yù)先分配空間需按最大空間分配，利用不 充分 l表容量難以擴(kuò)充30部分操作在順序存儲結(jié)構(gòu)的線性表中的實(shí) 現(xiàn)和時間復(fù)雜度的分析求順序表的表長 L.length，時間復(fù)雜度O(1) 取第i個數(shù)據(jù)元素 L.elemi-1，時間復(fù)雜度O(1) 查找函數(shù)LocateElem 具體實(shí)現(xiàn)，時間復(fù)雜度O(L.length)31int LocateElem_Sq(Sqlist L, ElemType e, Status (* compare)(ElemType, ElemType) /。

16、在順序線性表L中查找第1個值與e滿足 compare()的元素的位序 /若找到，則返回其在L中的位序，否則返回0 i=1; / i的初值為第1個元素的位序 p=L.elem; / p的初值為第1個元素的位序 while(i=L.length & !(*compare)(*p+,e) +i; if(i=L.length) return i; else return 0; / LocateElem_Sq32順序表的合并算法Void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) /已知線性表La和Lb中的數(shù)據(jù)元素按值非遞減排列。 /歸并La和Lb得到新。

17、的線性表Lc，Lc的數(shù)據(jù)元素也按 值非遞減排列。 pa=La.elem; pb=Lb.elem; Lc.listsize=Lc.length=La.length+ Lb.length; pc=Lc.elem=(ElemType *) malloc( Lc.listsize* sizeof(ElemType); if(!Lc.elem) exit(OVERFLOW); /存儲分配失敗 pa_last=La.elem+La.length-1;33pb_last=Lb.elem+Lb.length-1;while(pa=pa_last & pb=pb_last) /歸并 if(*pa=*pb) *p。

18、c+=*pa+; else *pc+=*pb+; while(pa=pa_last) *pc+=*pa+; /插入La的剩余元素 while(pb=pb_last) *pc+=*pb+; /插入Lb的剩余元素 /MergeList_Sq34合并算法MergeList_Sq的時間復(fù)雜度 O(La.length+ Lb.length) union算法的時間復(fù)雜度 O(La.length Lb.length) MergeList_Sq算法做如下改進(jìn)：添加 當(dāng)*pa=*pb時，將兩者中之一插入Lc中 則算法功能等價于union算法，但時間復(fù)雜度不同。 產(chǎn)生不同時間復(fù)雜度的原因，見P26 兩個因素。35。

19、2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)特點(diǎn)：v用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素 v利用指針實(shí)現(xiàn)了用不相鄰的存儲單元存放邏輯 上相鄰的元素 v每個數(shù)據(jù)元素ai，除存儲本身信息外，還需存 儲其直接后繼的信息 v結(jié)點(diǎn)l數(shù)據(jù)域：元素本身信息 l指針域：指示直接后繼的存儲位置結(jié)點(diǎn) 數(shù)據(jù)域 指針域36例 線性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)存儲地址頭指針H 31 1 7 13 19 25 31 37 43數(shù)據(jù)域LI QIAN SUN*linklist;38Lnode *h, *p; data p next 結(jié)點(diǎn)(*p)其中： (*p) 表示p所指向的結(jié)點(diǎn) (*p。

20、).data p-data表示p指向結(jié)點(diǎn)的數(shù)據(jù)域 (*p).next p-next表示p指向結(jié)點(diǎn)的指針域 生成一個Lnode型新結(jié)點(diǎn)： p=(Lnode *) malloc ( sizeof ( Lnode ) ); 系統(tǒng)回收p結(jié)點(diǎn)：free(p)39頭結(jié)點(diǎn)：在單鏈表第一個結(jié)點(diǎn)前附設(shè)一個結(jié)點(diǎn)叫頭結(jié) 點(diǎn) 頭CreateList(&L, n) / 生成含 n 個數(shù)據(jù)元素的鏈表41線性表的操作 GetElem(L, i, &e) 在單鏈表中的實(shí)現(xiàn):L 21p18p j 1 3 230p754256 42單鏈表是一種順序存取的結(jié)構(gòu)，為找第 i 個 數(shù)據(jù)元素，必須先找到第 i-1 個數(shù)據(jù)元素。因此，查找。

21、第 i 個數(shù)據(jù)元素的基本操作為：移動指針，比較 j 和 I 。令指針 p 始終指向線性表中第 j 個 數(shù)據(jù)元素。43v算法描述Status GetElem-L( LinkList L, int i , ElemType &e) /L為帶頭結(jié)點(diǎn)的單鏈表的頭指針 /當(dāng)?shù)趇個元素存在時，其值賦給e并返回OK，否則 返回ERROR p= L-next ; j=1; /初始化，p指向第一個結(jié)點(diǎn)，j為 計(jì)數(shù)器 while( p & ji) p=p-next; j+; if( !p | ji ) return ERROR; /第i個元素不存在 e=p-data; /取第i個元素 return OK; / G。

22、etElem-L44u 算法評價(時間復(fù)雜度)若找到值為e結(jié)點(diǎn)，p指向該結(jié)點(diǎn) While循環(huán)中語句頻度為 否則，為表長n T (n ) = O (n )45u插入：在帶頭結(jié)點(diǎn)的單鏈表L中第i個位置之前插入元素ep a b ep-next=s;ss-next=p-next;可見，在鏈表中插入結(jié)點(diǎn)只需要修改指針。因此，在單鏈表中第 i 個結(jié)點(diǎn)之前進(jìn)行插入的基本操作為:找到線性表中第i-1個結(jié)點(diǎn)，然后修改其指向后繼的指針。46u算法描述Status ListInsert-L(LinkList &L,int i,ElemType e) /在帶頭結(jié)點(diǎn)的單鏈表L中第i個位置之前插入元素e p=L; j=0。

23、; while(p&ji-1) p=p-next; j+; /尋找第i-1個結(jié)點(diǎn) if(!p | ji-1) return ERROR; /i小于1或大于表長 s=(LinkList)malloc(sizeof(Lnode); /生成新結(jié)點(diǎn) s-data=e; s-next=p-next; /插入L中 p-next=s; return OK; /LinstInsert_Lu算法評價(時間復(fù)雜度)T (n ) = O (n )47刪除：在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個元素 在單鏈表中刪除第 i 個結(jié)點(diǎn)的基本操作為:找 到線性表中第i-1個結(jié)點(diǎn)，修改其指向后繼的指針。 q = p-next; e 。

24、= q-data; p-next = q-next; free(q);p ai-148q ai ai+1算法描述Status ListDelete-L(LinkList &L, int i, ElemType &e) /在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個元素，并由e返回其值 p=L; j=0; while(p-next&ji-1) /尋找第i個結(jié)點(diǎn)，并令p指向其前驅(qū) p=p-next; j+; if(!(p-next) | (ji-1) return ERROR; /刪除位置不合理 q=p-next; p-next=q-next; /刪除并釋放結(jié)點(diǎn) e=q-data; free(q); retu。

25、rn OK; /ListDelete-L算法評價49T (n ) = O (n )操作 ClearList(&L) 在鏈表中的實(shí)現(xiàn): void ClearList(&L) / 將單鏈表重新置為一個空表 while (L-next) p=L-next; L-next=p-next; free(p); / ClearList算法時間復(fù)雜度： T ( n ) = O ( n )50如何從線性表得到單鏈表？鏈表是一個動態(tài)的結(jié)構(gòu)，它不需要給予分配 空間，因此生成鏈表的過程是一個結(jié)點(diǎn)“逐 個插入” 的過程。51例如：逆位序輸入 n 個數(shù)據(jù)元素的值， 建立帶頭結(jié)點(diǎn)的單鏈表。操作步驟：一、建立一個“空表”； 。

26、二、輸入數(shù)據(jù)元素an，建立結(jié)點(diǎn)并插入(sizeof(Lnode); L-next=NULL; /先建立一個帶頭結(jié)點(diǎn)的單鏈表 for(i=n;i0;i-) p=(LinkList)malloc(sizeof(Lnode); /生成新結(jié)點(diǎn) scanf(&p-data); /輸入元素值 p-next=L-next; L-next=p; /插入新元素 /CreateList-Lu 算法評價54T (n ) = O (n )l歸并兩個有序單鏈表 算法思想同前MergeList算法。 l 算法描述 /已知單鏈線性表La和Lb的元素按值非遞減排列。 / 歸并La和Lb得到新的單鏈線性表Lc，Lc的元素也按值。

27、非遞 減排列 pa=La-next; Lc=pc=La; while( pa & pb ) if( pa-data = pb-data )55void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc)pb=Lb-next; /用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn) pc-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next; pc-next=pa？pa:pb; free( Lb ); /插入剩余段 /釋放Lb的頭結(jié)點(diǎn) / MergeList_L56采用單鏈表數(shù)據(jù)結(jié)構(gòu)的合并算。

28、法與采用線性 表結(jié)構(gòu)的合并算法的區(qū)別時間復(fù)雜度相同 O( ListLength(La) + ListLength(Lb) 空間復(fù)雜度不同 采用單鏈表數(shù)據(jù)結(jié)構(gòu)，不需要另建新表的結(jié)點(diǎn) 空間，而只需將原來兩個鏈表中結(jié)點(diǎn)之間的關(guān)系 解除，重新鏈接。57v單鏈表特點(diǎn)l它是一種動態(tài)結(jié)構(gòu)，整個存儲空間為多個 鏈表共用 l不需預(yù)先分配空間 l指針占用額外存儲空間 l不能隨機(jī)存取，查找速度慢 用單鏈表實(shí)現(xiàn)線性表的操作時，存在的問題： 在鏈表中，元素的“位序”概念淡化，結(jié)點(diǎn)的“位 置”概念加強(qiáng)。改進(jìn)：將基本操作中的“位序 i ”改變?yōu)椤爸羔?p ”。58靜態(tài)鏈表利用數(shù)組描述鏈表。/-線性表的靜態(tài)單鏈表存儲結(jié)構(gòu)-#。

29、define MAXSIZE 1000 /鏈表的最大長度 typedef struct ElemType data; int cur; component, SLinkListMAXSIZE;v說明：假設(shè)S為SLinkList型變量，lS0.cur 指示第一個結(jié)點(diǎn)在數(shù)組中的位置； lSi.cur 指示下一個(i+1)結(jié)點(diǎn)的位置； l整型游標(biāo)i類似動態(tài)指針p，即i=Si.cur 等價于 指針后 移 p = p-next;59v靜態(tài)鏈表操作l定位函數(shù)LocateElemvoid LocateElem_SL(SLinkList S, ElemType e) /在靜態(tài)單鏈線性表L中查找第1個值為e的元。

30、素 /若找到，則返回它在L中的位序，否則返回0 i=S0.cur; / i指示表中第一個結(jié)點(diǎn)while( i & Si.data !=e) i=Si.cur; /在表中順鏈查找 return i; / LocateElem_SL60l插入和刪除操作 同單鏈表的插入和刪除操作(見算法2.9、2.10) 不同點(diǎn)：用戶自己實(shí)現(xiàn)malloc和free函數(shù) 為了辯明數(shù)組中哪些分量未被使用，將所有未被使 用過以及被刪除的分量用游標(biāo)鏈成一個備用的鏈 表，每當(dāng)進(jìn)行插入時便從備用鏈表上取得第一個 結(jié)點(diǎn)作為待插入的新結(jié)點(diǎn)；反之，在刪除時將從 鏈表中刪除下來的結(jié)點(diǎn)鏈接到備用鏈表上。61示例：靜態(tài)鏈表例：集合運(yùn)算(A。

31、-B)U(B-A)。假設(shè)由終端輸入集合元 素，先建立表示集合A的靜態(tài)鏈表S，而后再輸入 集合B的元素的同時查找S表，若存在和B相同的 元素，則從S表中刪除，否則將此元素插入S表。 算法思路：設(shè)3個過程：(1)將整個數(shù)組空間初始化成一個鏈表, InitSpace_SL；(2)從備用空間取得一個結(jié)點(diǎn), Malloc_SL；(3)將空閑結(jié)點(diǎn)鏈接到備用鏈表上, Free_SL；62void InitSpace_SL(SLinkList &Space) /將一維數(shù)組space中各分量鏈成一個備用鏈表， space0.cur為頭指針，“0”表示空指針 for(i=0;iMAXSIZE-1;+i) spac。

32、ei.cur=i+1; spaceMAXSIZE-1.cur=0; / InitSpace_SL int Malloc_SL(SLinkList &space) /若備用空間鏈表非空，則返回分配的結(jié)點(diǎn)下標(biāo)，否則返回0ispace0.cur; if(space0.cur) space0.cur=spacei.cur; return i;63 /Malloc_SLvoid Free_SL(SLinkList &Space, int k) / 將下標(biāo)為k的空閑結(jié)點(diǎn)回收到備用鏈表 spacek.cur = space0.cur; space0.cur=k; / Free_SL void differe。

33、nce(SLinkList &Space, int &S) / 依次輸入集合A和B的元素，在一維數(shù)組space中建立表 示集合(A-B)U(B-A)的靜態(tài)鏈表，S為其頭指針。假設(shè)備用 空間足夠大， space0.cur為其頭指針。 InitSpace_SL(space); /初始化備用空間 S=Malloc_SL(space); /生成S的頭結(jié)點(diǎn) r=S; /r指向S的當(dāng)前最后結(jié)點(diǎn) scanf(m,n); /輸入A和B的元素個數(shù)64for(j=1; j=m;+j ) /建立集合A的鏈表 iMalloc_SL(space); /分配結(jié)點(diǎn) scanf(spacei.data); /輸入A的元素值 。

34、spacer.cur=i; r=i; /插入到表尾 / for spacer.cur=0; / 尾結(jié)點(diǎn)的指針為空 for(j=1; j=n; +j ) /依次輸入B的元素，若不在當(dāng)前 /表中，則插入，否則刪除 scanf(b); p=S; k=spaceS.cur /k指向集合A中的第一 /個結(jié)點(diǎn) while(k!=spacer.cur & spacek.data!=b) /在當(dāng)前表中查找 p=k; k=spacek.cur; /while65if(k=spacer.cur) /當(dāng)前表中不存在該元素，插入在r所 / 指結(jié)點(diǎn)之后，且r的當(dāng)前位置不變66i=Malloc_SL(space); sp。

35、acei.data=b; spacei.cur=spacer.cur; spacer.cur=i; /if else /該元素已在表中，刪除之 spacep.cur=spacek.cur; Free_SL(space,k); if(r=k) r=p; /若刪除的是r所指結(jié)點(diǎn)，則需修改尾指針 /else / for /differencespace(0:11)算法執(zhí)行流程示例 假設(shè)集合A=c,b,e,g,f,d， B=a,b,n,f ，圖(a)表示輸 入集合A的元素之后建成 的鏈表S和備用空間鏈表 的狀況。0S11 2 3 456 7 8 9c b e g f d圖(a) 表示A的鏈表S6710。

36、118 2 3 4 5 6 7 0 9 10 11 0space(0:11) 0 S 1 12 34 567 8 9 10 11c b e g f d a9 8 2 3 4 5 6 7 8 0 9 0 10 11 0插入元素a的過程： 在A中查找，不存在，則(1)i=Malloc_SL(space); / i=8 (2) spacei.data=b; spacei.cur=spacer.cur; (3)spacer.cur=i;68圖(b) 插入aspace(0:11) 0 S 1 12 34 567 8 9 10 11c b e g f d a3 9 2 3 4 4 9 5 6 7 8 0 。

37、10 11 0刪除元素b的過程： 在A中查找，存在(p=2,k=3)，則(1) spacep.cur=spacek.cur; (2) Free_SL(space,k);(3) if(r=k) r=p; /若刪除的 是r所指結(jié)點(diǎn)，則需修改尾指針69圖(c) 刪除bspace(0:11) 0 S 1 12 34 567 8 9 10 11c b n e g f d a9 3 2 4 9 8 5 6 7 3 8 0 10 11 0插入元素n 的過程： 在A中查找，不存在，則(1)i=Malloc_SL(space); / i=3 (2) spacei.data=b; spacei.cur=space。

38、r.cur; (3)spacer.cur=i;70圖(d) 插入nspace(0:11) 0 S 1 12 34 567 8 9 10 11c n e g f d a6 9 2 4 8 5 6 7 7 9 3 0 10 11 0刪除元素f 的過程： 在A中查找，存在(p=5,k=6)，則(1) spacep.cur=spacek.cur; (2) Free_SL(space,k);(3) if(r=k) r=p; /若刪除的 是r所指結(jié)點(diǎn)，則需修改尾指針71圖(e) 刪除f循環(huán)鏈表(circular linked list)v循環(huán)鏈表是表中最后一個結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)， 使鏈表構(gòu)成環(huán)狀 v特點(diǎn)。

39、：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié) 點(diǎn)，提高查找效率 v操作與單鏈表基本一致,判別鏈表中最后一個結(jié)點(diǎn) 的條件不同 l單鏈表 h-next=NULL /后繼是否為空 l循環(huán)鏈表 h-next=h /后繼是否為頭結(jié)點(diǎn)h h 空表72雙向鏈表(double linked list)單鏈表具有單向性的缺點(diǎn)，在查找某節(jié)點(diǎn)的 直接前趨的時間復(fù)雜度將達(dá)到O(n)。 v結(jié)點(diǎn)定義typedef struct Dulnode ElemType data ; struct Dulnode *prior ; struct Dulnode *next ; Dulnode, *Dulinklist ;prior da。

40、ta next73空雙向循環(huán)鏈表：L 非空雙向循環(huán)鏈表：L A Bab pcp-prior-next = p = p-next-proir;74雙向鏈表的操作特點(diǎn)： “查詢” 和單鏈表相同?！安迦搿?和“刪除”時需要同時修改 兩個方向上的指針。75v 刪除p-prior-next=p-next; a b Pcp-next-prior=p-prior;76l 算法描述Status ListDelete_Dul(Dullinklist&L, int i,ElemType &e) /刪除帶頭結(jié)點(diǎn)的雙向循環(huán)線性表L的第i個元素，/ i的合法值為1=i=表長。if (!(p=GetElemp_Dul(L。

41、,i)位置指針p/在L中確定第i個元素的return ERROR; /p=NULL,既第i個元素不存在 e=p-data; p-prior-next=p-next; p-next-prior=p-prior; free(p); return OK; / ListDelete_Dul77v插入Pa S x b s-next=p; s-prior = p-prior ; p-prior-next=s; p-prior=s;78l算法描述Status ListInsert_Dul(Dullinklist&L, int i,ElemType e) /在帶頭結(jié)點(diǎn)的雙向循環(huán)線性表L的第i個位置之前插入元素。

42、e， i的合法值為1=i=表長+1。if (!(p=GetElemp_Dul(L,i) /在L中確定第i個元素的位置指針p79return ERROR; /p=NULL,既第i個元素不存在 if (!(s=(Dulinklist) malloc(sizeof(Dulnode) return ERROR; s-data=e; s-prior=p-prior ; p-prior-next=s; s-next=p; p-prior=s; return OK; / ListInsert_Dul帶頭結(jié)點(diǎn)的線性鏈表類型定義typedef struct Lnode /結(jié)點(diǎn)類型 ElemType date; 。

43、struct LNode *next ; *Link, *Position;Status MakeNode( Link &p, ElemType e ); / 分配由 p 指向的值為e的結(jié)點(diǎn)，并返回OK， / 若分配失敗，則返回 ERRORvoid FreeNode( Link &p ); / 釋放 p 所指結(jié)點(diǎn)80typedef struct /鏈表類型 Link head,tail; /分別指向線性表中的頭結(jié)點(diǎn) 和最后一個結(jié)點(diǎn) int len; / 指示線性鏈表中數(shù)據(jù)元素的個數(shù) LinkList; 相關(guān)操作 見P3781鏈表的基本操作:結(jié)構(gòu)初始化和銷毀結(jié)構(gòu) Status InitList(。

44、 LinkList &L ); / 構(gòu)造一個空的線性鏈表 L / 表長為零。 Status DestroyList( LinkList &L ); / 銷毀線性鏈表 L，L不再存在。O(1)O(n)82引用型操作Status ListEmpty ( LinkList L ); /判表空 int ListLength( LinkList L );/ 求表長O(1) O(1) O(n)Status PriorPos( LinkList L, Link p );/ p指向線性表L中的一個結(jié)點(diǎn)，返回p所指結(jié)點(diǎn)的直接前驅(qū) /的位置。若無前驅(qū)，則返回NULLStatus NextPos ( LinkLis。

45、t L , Link p );O(1)/ p指向線性表L中的一個結(jié)點(diǎn)，返回p所指結(jié)點(diǎn)的直接后繼 /的位置。若無后繼，則返回NULLO(1) ElemType GetCurElem ( LinkList p ); / p指向線性表L中的一個結(jié)點(diǎn)，返回p所指數(shù)據(jù)元的值83加工型操作Status ClearList ( LinkList &L ); / 重置 L 為空表 O(n) O(1)Status SetCurElem(Link &p, ElemType e ); / 更新當(dāng)前指針?biāo)笖?shù)據(jù)元素Status Append ( LinkList &L, Link s ); / 在表尾結(jié)點(diǎn)之后鏈接一串。

46、結(jié)點(diǎn) O(s)Status InsAfter ( LinkList &L, Link p;Elemtype e ); O(1) / 將元素 e 插入在當(dāng)前指針p之后 Status DelAfter ( LinkList &L, Link p; ElemType& e ); / 刪除當(dāng)前指針p之后的結(jié)點(diǎn) O(1)84示例 Status ListInsert_L( LinkList &L, int i, ElemType e) / 在帶頭結(jié)點(diǎn)的單鏈線性表L的第i個元素之前插入元 素e if(!LocatePos(L,i-1,h) return ERROR; /i值不合法 if(!MakeNode(。

47、s,e) return ERROR; /結(jié)點(diǎn)存儲分配 失敗 InsFirst(h,s); /對于從第i個結(jié)點(diǎn)開始的鏈表，第i-1 個結(jié)點(diǎn)是它的頭結(jié)點(diǎn) return OK; / ListInsert_L85Status MergeList_L( LinkList &La, LinkList &Lb, LinkList &Lc, int (*compare)(ElemType, ElemType) /已知單鏈線性表La和Lb的元素按值非遞減排序 /歸并La和Lb得到新的單鏈線性表Lc，Lc的元素也按值非遞減 排列 if(! InitList(Lc) return ERROR; /存儲空間分配失敗 。

48、ha=GetHead(La); hb= GetHead(Lb); /ha和hb分別指向La和Lb的頭結(jié)點(diǎn)pa=NextPos(La,ha); pb=NextPos(Lb,hb); /pa和pb分別指向La和Lb中當(dāng)前結(jié)點(diǎn)while(pa & pb) /La和Lb均非空 a=GetCurElem(pa); b=GetCurElem(pb); /a和b為兩表中當(dāng)前比較元素86if(*compare)(a,b)=0) /a=b DelFirst(ha,q); Append(Lc,q); pa=NextPos(La,ha); else /ab DelFirst(hb,q); Append(Lc,q);。

49、 pa=NextPos(Lb,hb); / while if(pa) Append(Lc,pa); /鏈接La中剩余結(jié)點(diǎn) else Append(Lc,pb); /鏈接Lb中剩余結(jié)點(diǎn) FreeNode(ha); FreeNode(hb); /釋放La和Lb的頭結(jié)點(diǎn) return OK; / MergeList_L872.4 線性表的應(yīng)用舉例一元多項(xiàng)式的表示及相加 一元多項(xiàng)式的表示：Pn ( x ) = P0 + P1 x + P2 x2+ L L + Pn xn可用線性表P表示P = ( P0 , P1 , P2 , L L , Pn )1000 20000 + 2x 但對S(x)這樣的多項(xiàng)式。

50、浪費(fèi)空間 S ( x ) = 1 + 3 x一般 Pn ( x )= P1 xe1+ P2 xe2+ L L + Pm xem其中 0 e1 e 2 L L em ( Pi 為非零系數(shù)) 用數(shù)據(jù)域含兩個數(shù)據(jù)項(xiàng)的線性表表示 ( P1， e1 )，P2， e 2 )， L ( Pm ， em ) ( L 其存儲結(jié)構(gòu)可以用順序存儲結(jié)構(gòu)，也可以用單鏈表88單鏈表的結(jié)點(diǎn)定義typedef struct node int coef; int exp; struct node *next; JD;coefexpnext89基本操作： CreatPolyn ( &P, m )操作結(jié)果：輸入 m 項(xiàng)的系數(shù)和指數(shù)。

51、， 建立一元多項(xiàng)式 P。DestroyPolyn ( &P )初始條件：一元多項(xiàng)式 P 已存在。 操作結(jié)果：銷毀一元多項(xiàng)式 P。PrintPolyn ( &P )初始條件：一元多項(xiàng)式 P 已存在。 操作結(jié)果：打印輸出一元多項(xiàng)式 P。90PolynLength( P )初始條件：一元多項(xiàng)式 P 已存在。 操作結(jié)果：返回一元多項(xiàng)式 P 中的項(xiàng)數(shù)。AddPolyn ( &Pa, &Pb )初始條件：一元多項(xiàng)式 Pa 和 Pb 已存在。 操作結(jié)果：完成多項(xiàng)式相加運(yùn)算，即： Pa = PaPb，并銷毀一元多項(xiàng)式 Pb。SubtractPolyn ( &Pa, &Pb ) ADT P算法實(shí)現(xiàn)： p43 算。

52、法2.2294Status CreatPolyn ( polynomail &P, int m ) / 輸入m項(xiàng)的系數(shù)和指數(shù)，建立表示一元多項(xiàng)式的有序鏈表PInitList (P); h=GetHead(P); e.coef = 0.0; e.expn = -1; SetCurElem (h, e); / 設(shè)置頭結(jié)點(diǎn)的數(shù)據(jù)元素 for ( i=1; i=m; +i ) / 依次輸入 m 個非零項(xiàng) scanf (e.coef, e.expn);if (!LocateElem ( P, e, (*cmp)() ) /當(dāng)前鏈表中不存在該指數(shù)項(xiàng) return OK; / CreatPolyn95if 。

53、( MakeNode(s,e)InsAfter ( P, s );注意: 1.輸入次序不限;2.指數(shù)相同的項(xiàng)只能輸入一次。Status AddPolyn (polynomial &Pa, polynomial &Pb) / 利用兩個多項(xiàng)式的結(jié)點(diǎn)構(gòu)成“和多項(xiàng)式” Pa = PaPbha=GetHead(Pa); hb=GetHead(Pb);/ha和hb分別指向Pa和Pb的頭結(jié)點(diǎn)qa=NextPos(Pa,ha); qb=NextPos(Pb,hb);/qa和qb分別指向Pa和Pb中當(dāng)前結(jié)點(diǎn)while(qa & qb) /qa和qb均非空 a=GetCurElem(qa); b=GetCurEl。

54、em(qb);/a和b為兩表中當(dāng)前比較元素9697switch (*cmp(a, b) case -1: / 多項(xiàng)式PA中當(dāng)前結(jié)點(diǎn)的指數(shù)值小 ha=qa; qa=NextPos(Pa,qa); break; case 0: / 兩者的指數(shù)值相等 sum = a.coef + b.coef ; if ( sum != 0.0 ) /修改多項(xiàng)式PA中當(dāng)前結(jié)點(diǎn)的系數(shù)值 SetCurElem(qa, sum); ha=qa; else /刪除多項(xiàng)式PA中當(dāng)前結(jié)點(diǎn) DelFirst(ha,qa); FreeNode(qa); DelFirst(hb,qb); FreeNode(qb); qb=NextP。

55、os(Pb,hb); qa=NextPos(Pa,ha); break; case 1: /多項(xiàng)式PB中當(dāng)前結(jié)點(diǎn)的指數(shù)值小 DelFirst(hb,qb); InsFirst(ha,qb); qb=NextPos(Pb,hb); ha=NextPos(Pa,ha); break; / switch / whileif(! ListEmpty(Pb) Append(Pa, qb);/鏈接Pb中剩余結(jié)點(diǎn) FreeNode(hb); /釋放Pb的頭結(jié)點(diǎn) / AddPolyn98本章小結(jié)1.了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在 著線性關(guān)系，在計(jì)算機(jī)中表示這種關(guān)系的兩類不同 的存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。用前 者表示的線性表簡稱為順序表，用后者表示的線性表簡稱為鏈表。 2.熟練掌握這兩類存儲結(jié)構(gòu)的描述方法，以及線性表的各種基本操作的實(shí)現(xiàn)。 3.能夠從時間和空間復(fù)雜度的角度綜合比較線性表兩種 存儲結(jié)構(gòu)的不同特點(diǎn)及其適用場合。99百度搜索“就愛閱讀”,專業(yè)資料,生活學(xué)習(xí),盡在就愛閱讀網(wǎng)92to.com,您的在線圖書館 104。

總結(jié)

以上是生活随笔為你收集整理的线性表C语言locate和ETget,线性表(数据结构重难点讲解)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。