《線性表(數據結構重難點講解)》由會員分享，可在線閱讀，更多相關《線性表(數據結構重難點講解)(104頁珍藏版)》請在人人文庫網上搜索。

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

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

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

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

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

6、法：lLOC(ai)=LOC(a1)+(i-1)*L lLOC(ai+1)=LOC(ai)+Ll其中： uL 一個元素占用的存儲單元個數 uLOC(ai) 線性表第i個元素的地址 uLOC(a1) 線性表的第一個數據元素的 存儲位置，稱為線性表的起始位置或基地址。16v特點：l實現邏輯上相鄰物理地址相鄰 l實現隨機存取 v實現：可用C語言的一維數組實現17存儲地址 b b+l內存元素序號 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; /當前長度 int listsize; /當前分配的存儲容量b+(maxlen-1)*lSqList;數據元素不是簡單類型時,可定義結構體數組18初始化v(生成大小為LISTINITSIZE的線性表)Status InitList_Sq(Sqlist &L) /構造一個空的線性表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動態申請和釋放內存 ( #includestdlib.h )ELEMTYPE *p=(ELEMTYPE *)malloc(M*sizeof(ELEMTYPE); / 分配size字節的存儲區，函數返回所分配的內存起始地址，如 內存不足，則返回0；free( p );/ 釋放p所指的內存區，無函數返回值； ELEMTYPE *p=(ELEMTYPE *) realloc (ELEMTYPE *p, unsigned size);。

9、 /將p所指的已分配內存區的大小改為size，size可比原來分配的 空間大或小。函數返回指向該內存區的指針。20插入v定義：線性表的插入是指在第i(1i n+1) 個元素之前插入一個新的數據元素x，使長度 為n的線性表變為n+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數組下標 0內存 元素序號a1數組下標 0 1內存 元素序號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為插入位置，數組下標默認從0開始 for( p=&L.elemL.length-1 ; p=q ; p-) *(p+1)=*p; /插入位置及之后元素右移 *q=e; /插入e +L.length; /表長增加1 return OK; / ListInsert_Sq24v算法時間復雜度T(n)l設Pi是在第i個元素之前插入一個元素的概率， 則在長。

12、度為n的線性表中插入一個元素時，所需 移動的元素次數的平均次數為：Eis =n +1Pi ( n - i + 1 )i =1若認為 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數組下標 0 1內存 。

13、元素序號a1 a2 1 2數組下標 0 1內存 元素序號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設Qi是刪除第i個元素的概率，則在長度為n的線 性表中刪除一個元素所需移動的元素次數的平均 n 次數為：E de =Q i (n - i)i =1若認為 Q i = 則 E de = 1 n1 n (n - i) = n -1 2ni =1 T (n ) = O (n )故在順序表中插入或刪除一個元素時，平均移 動表的一半元素，當n很大時，效率很低29順序存儲。

15、結構的優缺點v優點 l邏輯相鄰，物理相鄰 l可隨機存取任一元素 l存儲空間使用緊湊 v缺點 l插入、刪除操作需要移動大量的元素 l預先分配空間需按最大空間分配，利用不 充分 l表容量難以擴充30部分操作在順序存儲結構的線性表中的實 現和時間復雜度的分析求順序表的表長 L.length，時間復雜度O(1) 取第i個數據元素 L.elemi-1，時間復雜度O(1) 查找函數LocateElem 具體實現，時間復雜度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中的數據元素按值非遞減排列。 /歸并La和Lb得到新。

17、的線性表Lc，Lc的數據元素也按 值非遞減排列。 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的時間復雜度 O(La.length+ Lb.length) union算法的時間復雜度 O(La.length Lb.length) MergeList_Sq算法做如下改進：添加 當*pa=*pb時，將兩者中之一插入Lc中 則算法功能等價于union算法，但時間復雜度不同。 產生不同時間復雜度的原因，見P26 兩個因素。35。

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

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

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

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

23、; while(p&ji-1) p=p-next; j+; /尋找第i-1個結點 if(!p | ji-1) return ERROR; /i小于1或大于表長 s=(LinkList)malloc(sizeof(Lnode); /生成新結點 s-data=e; s-next=p-next; /插入L中 p-next=s; return OK; /LinstInsert_Lu算法評價(時間復雜度)T (n ) = O (n )47刪除：在帶頭結點的單鏈表L中刪除第i個元素 在單鏈表中刪除第 i 個結點的基本操作為:找 到線性表中第i-1個結點，修改其指向后繼的指針。 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) /在帶頭結點的單鏈表L中刪除第i個元素，并由e返回其值 p=L; j=0; while(p-next&ji-1) /尋找第i個結點，并令p指向其前驅 p=p-next; j+; if(!(p-next) | (ji-1) return ERROR; /刪除位置不合理 q=p-next; p-next=q-next; /刪除并釋放結點 e=q-data; free(q); retu。

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

26、二、輸入數據元素an，建立結點并插入(sizeof(Lnode); L-next=NULL; /先建立一個帶頭結點的單鏈表 for(i=n;i0;i-) p=(LinkList)malloc(sizeof(Lnode); /生成新結點 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的頭結點作為Lc的頭結點 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的頭結點 / MergeList_L56采用單鏈表數據結構的合并算。

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

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

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

31、-B)U(B-A)。假設由終端輸入集合元 素，先建立表示集合A的靜態鏈表S，而后再輸入 集合B的元素的同時查找S表，若存在和B相同的 元素，則從S表中刪除，否則將此元素插入S表。 算法思路：設3個過程：(1)將整個數組空間初始化成一個鏈表, InitSpace_SL；(2)從備用空間取得一個結點, Malloc_SL；(3)將空閑結點鏈接到備用鏈表上, Free_SL；62void InitSpace_SL(SLinkList &Space) /將一維數組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) /若備用空間鏈表非空，則返回分配的結點下標，否則返回0ispace0.cur; if(space0.cur) space0.cur=spacei.cur; return i;63 /Malloc_SLvoid Free_SL(SLinkList &Space, int k) / 將下標為k的空閑結點回收到備用鏈表 spacek.cur = space0.cur; space0.cur=k; / Free_SL void differe。

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

34、spacer.cur=i; r=i; /插入到表尾 / for spacer.cur=0; / 尾結點的指針為空 for(j=1; j=n; +j ) /依次輸入B的元素，若不在當前 /表中，則插入，否則刪除 scanf(b); p=S; k=spaceS.cur /k指向集合A中的第一 /個結點 while(k!=spacer.cur & spacek.data!=b) /在當前表中查找 p=k; k=spacek.cur; /while65if(k=spacer.cur) /當前表中不存在該元素，插入在r所 / 指結點之后，且r的當前位置不變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所指結點，則需修改尾指針 /else / for /differencespace(0:11)算法執行流程示例 假設集合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所指結點，則需修改尾指針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所指結點，則需修改尾指針71圖(e) 刪除f循環鏈表(circular linked list)v循環鏈表是表中最后一個結點的指針指向頭結點， 使鏈表構成環狀 v特點。

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

40、ta next73空雙向循環鏈表：L 非空雙向循環鏈表：L A Bab pcp-prior-next = p = p-next-proir;74雙向鏈表的操作特點： “查詢” 和單鏈表相同。“插入” 和“刪除”時需要同時修改 兩個方向上的指針。75v 刪除p-prior-next=p-next; a b Pcp-next-prior=p-prior;76l 算法描述Status ListDelete_Dul(Dullinklist&L, int i,ElemType &e) /刪除帶頭結點的雙向循環線性表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) /在帶頭結點的雙向循環線性表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帶頭結點的線性鏈表類型定義typedef struct Lnode /結點類型 ElemType date; 。

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

44、 LinkList &L ); / 構造一個空的線性鏈表 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中的一個結點，返回p所指結點的直接前驅 /的位置。若無前驅，則返回NULLStatus NextPos ( LinkLis。

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

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

47、s,e) return ERROR; /結點存儲分配 失敗 InsFirst(h,s); /對于從第i個結點開始的鏈表，第i-1 個結點是它的頭結點 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的頭結點pa=NextPos(La,ha); pb=NextPos(Lb,hb); /pa和pb分別指向La和Lb中當前結點while(pa & pb) /La和Lb均非空 a=GetCurElem(pa); b=GetCurElem(pb); /a和b為兩表中當前比較元素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中剩余結點 else Append(Lc,pb); /鏈接Lb中剩余結點 FreeNode(ha); FreeNode(hb); /釋放La和Lb的頭結點 return OK; / MergeList_L872.4 線性表的應用舉例一元多項式的表示及相加 一元多項式的表示：Pn ( x ) = P0 + P1 x + P2 x2+ L L + Pn xn可用線性表P表示P = ( P0 , P1 , P2 , L L , Pn )1000 20000 + 2x 但對S(x)這樣的多項式。

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

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

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

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

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

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

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。