1、第二章 線性表2.1 線性表及其基本運算2.2 線性表的順序存儲結構2.3 線性表的鏈式存儲結構線性表的邏輯結構、物理結構，以及它們之間的相互關系；定義與之相適應的運算；設計相應的算法；分析算法的效率。線性結構特點：在數據元素的非空有限集中n存在存在唯一唯一的一個被稱作的一個被稱作“第一個第一個”的數據元的數據元素素n存在存在唯一唯一的一個被稱作的一個被稱作“最后一個最后一個”的數據的數據元素元素n除第一個外，集合中的每個數據元素均除第一個外，集合中的每個數據元素均只有只有一個前驅一個前驅n除最后一個外，集合中的每個數據元素均除最后一個外，集合中的每個數據元素均只只有一個后繼有一個后繼2.1

2、線性表及其基本運算例 英文字母表（A,B,C,.Z)是一個線性表例學號姓名年齡001張三18002李四19數據元素一、線性表（linear_list） 線性表是n個數據元素的有限序列,記為： L=（a1， a2，an）線性表的特點 同一性：同一性：線性表由線性表由同類同類數據元素組成，每一個數據元素組成，每一個ai必必須屬于須屬于同一同一數據對象數據對象,且不能出現缺項。且不能出現缺項。 有窮性：有窮性：線性表由線性表由有限個有限個數據元素組成，表長度數據元素組成，表長度就是表中數據元素的個數就是表中數據元素的個數n,當當n=0時為時為空表空表。 有序性：有序性：線性表中相鄰數據元素之間存在線

3、性表中相鄰數據元素之間存在著序偶關系著序偶關系。1in時時ai的直接前驅是的直接前驅是ai-1，a1無直接前驅無直接前驅ai的直接后繼是的直接后繼是ai+1，an無直接后繼無直接后繼二、線性表的抽象數據類型定義抽象數據類型定義抽象數據類型定義 ：ADT LinearList數據元素數據元素：D=ai| aiD0, i=1,2,，n n0 ，D0為某一數據對象 關系關系： | ai, ai+1D0，i=1,2, ,n-1 基本操作基本操作： （1）InitList（L） 操作前提：L為未初始化線性表。 操作結果：將L初始化為空表。 （2）DestroyList(L) 操作前提：線性表L已存在。

4、操作結果：將L銷毀。 （3）ClearList(L) 操作前提：線性表L已存在 。 操作結果：將表L置為空表。 ADT LinearList2.2 線性表的順序存儲結構2.2.1 線性表的順序存儲結構 2.2.2 線性表順序存儲結構上的基本運算 n順序表：n定義：是指用一組地址連續的存儲單元依次存儲線性表中的各個元素，使得線性表中在邏輯結構上相鄰的數據元素存儲在相鄰的物理存儲單元中。n元素地址計算方法：nLoc(ai)=Loc(a1)+(i-1)*knLoc(ai+1)=Loc(ai)+ kn其中：nk一個元素占用的存儲單元個數nLoc(ai)線性表第i個元素的地址2.2.1 線性表的順序存儲

5、結構n特點：n實現邏輯上相鄰物理地址相鄰n實現隨機存取n實現：可用C語言的一維數組實現a1a2an01n-112n內存V數組下標元素序號M-1typedef int DATATYPE; #define M 1000DATATYPE dataM;例 typedef struct card int num; char name20; char author10; char publisher30; float price;DATATYPE;DATATYPE libraryM; 備用空間數據元素不是簡單類型時,可定義結構體數組或動態申請和釋放內存DATATYPE *pData = (DATATYPE

6、 *)malloc(M*sizeof(DATATYPE);free(pData); . .loc(aloc(a1 1)+(maxlen-1)k )+(maxlen-1)k n n a an n loc(aloc(a1 1)+(n-1)k )+(n-1)k i ia ai i loc(aloc(a1 1)+(i-1)k )+(i-1)k 2 2a a2 2 Loc(aLoc(a1 1)+(2-1)k )+(2-1)k 1 1 a a1 1Loc(aLoc(a1 1) ) 邏輯地址邏輯地址 內存空間狀態內存空間狀態 存儲地址存儲地址 順序存儲結構示意圖順序存儲結構示意圖空閑空閑順序存儲結構示意圖順

7、序存儲結構的C語言定義#definemaxsize=線性表可能達到的最大長度；typedef struct ElemType elemmaxsize； /* 線性表占用的數組空間*/ int last； /*記錄線性表中最后一個元素在數組elem 中的位置（下標值），空表置為-1*/ SeqList；注意區分元素的序號和數組的下標，如a1的序號為1，而其對應的數組下標為0。 2.2.2 線性表順序存儲結構的基本運算n線性表的基本運算：1.查找操作 2.插入操作 3.刪除操作4.順序表合并算法n線性表順序存儲結構的優缺點分析1.查找操作線性表的兩種基本查找運算u按序號查找按序號查找GetData

8、(L,i)：要求查找線性表L中第i個數據元素，其結果是L.elemi-1或L-elemi-1。u按內容查找按內容查找Locate（L,e）: : 要求查找線性表L中與給定值e相等的數據元素，其結果是：若在表L中找到與e相等的元素，則返回該元素在表中的序號；若找不到，則返回一個“空序號”，如-1。 線性表的查找運算算法描述為：線性表的查找運算 int Locate(SeqList L，ElemType e) i=0 ; /*i為掃描計數器，初值為0，即從第一個元素開始比較*/ while (i=L.last)&(L.elemi!=e) ) i+; /*順序掃描表，直到找到值為key的元素,或掃描

9、到表尾而沒找到*/ if (i=L.last) return(i); /*若找到值為e的元素，則返回其序號*/ else return(-1); /*若沒找到，則返回空序號*/2.插入操作 線性表的插入運算是指在表的第i (1in+1)個位置，插入一個新元素e，使長度為n的線性表 (e1，ei-1，ei，en) 變成長度為n+1的線性表（e1，,ei-1，e e，ei，en）。 線性表的插入運算算法插入算法示意圖已知：已知：線性表 (4,9,15,28,30,30,42,51,62)，需在第4個元素之前插入一個元素“21”。則需要將第9個位置到第4個位置的元素依次后移一個位置，然后將“21”插

10、入到第4個位置，序號移動元素插入元素1234567810949152830304251624915283030426251491521283030426251內存a1a2aiai+1an01i-1V數組下標n-1in12i元素序號i+1nn+1內存a1a2aiai+1an01i-1V數組下標n-1in12i元素序號i+1nn+1an-1x插入運算int InsList(SeqList *L,int i,ElemType e) int k; if( (iL-last+2) ) /*首先判斷插入位置是否合法*/ printf(“插入位置i值不合法”)；return(ERROR); if(L-las

11、t=maxsize-1) printf(“表已滿無法插入”)； return(ERROR); for(k=L-last;k=i-1;k-) /*為插入元素而移動位置*/ L-elemk+1=L-elemk; L-elemi-1=e; /*在C語言中數組第i個元素的下標為i-1*/ L-last+; return(OK); 設Pi是在第i個元素之前插入一個元素的概率，則在長度為n的線性表中插入一個元素時，所需移動的元素次數的平均次數為：11)1(niiinPEis nOnTninnEisnPnii112)1(1111則若認為插入運算算法時間復雜度T(n)3.刪除操作線性表的刪除運算是指將表的第i

12、(1in)個元素刪去，使長度為n的線性表 (e1，,ei-1，ei，ei+1，en)，變成長度為n-1的線性表(e1，,ei-1， ei+1，en)。 算法思路示意 算法實現刪除算法示意將線性表(4,9,15,21,28,30,30,42,51,62)中的第5個元素刪除。 序號123456781094915212830304262514915213030425162刪除28后內存a1a2aiai+1an01i-1V數組下標n-1in12i元素序號i+1nn+1內存a1a2ai+1V數組下標01i-1n-2in-112i元素序號i+1n-1nanai+2刪除算法 int DelList(SeqL

13、ist *L,int i,ElemType *e)/*在順序表L中刪除第i個數據元素，并用指針參數e返回其值*/ int k; if(iL-last+1) printf(“刪除位置不合法！”)； return(ERROR)； *e= L-elemi-1; /* 將刪除的元素存放到e所指向的變量中*/ for(k=i;ilast;k+) L-elemk-1= L-elemk; /*將后面的元素依次前移*/ L-last-; return(OK); 設Qi是刪除第i個元素的概率，則在長度為n的線性表中刪除一個元素所需移動的元素次數的平均次數為：niideinQE1)( nOnTninnEnQnid

14、ei121)(11則若認為故在順序表中插入或刪除一個元素時，平均移動表的一半元素，當n很大時，效率很低。刪除運算算法時間復雜度T(n)4.合并算法n已知 ：有兩個順序表LA和LB，其元素均為非遞減有序排列，編寫一個算法，將它們合并成一個順序表LC，要求LC也是非遞減有序排列。 n算法思想算法思想 ：設表LC是一個空表，為使LC也是非遞減有序排列，可設兩個指針i、j分別指向表LA和LB中的元素，若LA.elemiLB.elemj，則當前先將LB.elemj插入到表LC中，若LA.elemiLB.elemj ，當前先將LA.elemi插入到表LC中，如此進行下去，直到其中一個表被掃描完畢，然后再將

15、未掃描完的表中剩余的所有元素放到表LC中。n算法實現順序表合并算法實現void merge(SeqList *LA, SeqList *LB, SeqList *LC) i=0;j=0;k=0; while(ilast&jlast) if(LA-elemielemj) LC-elemk= LA-elemi; i+; k+; else LC-elemk=LB-elemj; j+; k+; while(ilast)/*當表LA長則將表LA余下的元素賦給表LC*/ LC-elemk= LA-elemi; i+; k+; while(jlast) /*當表LB長則將表LB余下的元素賦給表LC*/ LC

16、-elemk= LB-elemj; j+; k+; LC-last=LA-last+LB-last; 順序存儲結構的優點和缺點優點：1.無需為表示結點間的邏輯關系而增加額外的存儲空間； 2.可方便地隨機存取表中的任一元素。 缺點：1.插入或刪除運算不方便，除表尾的位置外，在表的其它位置上進行插入或刪除操作都必須移動大量的結點，其效率較低； 2.由于順序表要求占用連續的存儲空間，存儲分配只能預先進行靜態分配。因此當表長變化較大時，難以確定合適的存儲規模。定義：采用鏈式存儲結構的線性表稱為鏈表 。特點： 用一組任意的存儲單元存儲線性表的數據元素 利用指針實現了用不相鄰的存儲單元存放邏輯上相鄰的元素

17、 每個數據元素ai，除存儲本身信息外，還需存儲其直接后繼的信息數據域 指針域結點2.3 線性表的鏈式存儲結構結點（node） 數據域：元素本身信息指針域：指示直接后繼的存儲位置ZHAOQIANSUNLIZHOUWUZHENGWANGH例 線性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925數據域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲地址1713192531374331H頭指針我們從兩個角度來討論鏈表：1.從實現角度看，鏈表可分為動態鏈表和靜態鏈表；2.從鏈接方式的角度看，鏈表可分為單鏈表、循環鏈表和雙鏈表

18、。2.3.1 單鏈表 2.3.2 單鏈表上的基本運算 2.3.3 循環鏈表 2.3.4 雙向鏈表 *2.3.5 靜態鏈表 2.3.6 順序表和鏈表的比較鏈表鏈表n單鏈表n定義：每個結點中只含一個指針域的鏈表，也叫線性鏈表。n單鏈表包括兩個域：數據域用來存儲結點的值；指針域用來存儲數據元素的直接后繼的地址（或位置）。n頭指針頭指針 ：指向鏈表頭結點的指針。2.3.1 單鏈表單鏈表的示例圖頭指針H存儲地址數據域指針域1 D 437 B 1313 C 119 H NULL25 F 3731 A 737 G 1943 E 2531單鏈表的存儲結構描述typedef struct node / * 結點

19、類型定義 * / elemtype data； struct node * next；node, *linklist； /* linklist為結構指針類型*/ 生成一個linklist型新結點：p=(linklist *)malloc(sizeof(node); 系統回收p結點：free(p);單鏈表結點關系data nextdata nextdata next指針域數據域前驅后繼P-nextP P PP-pre(*p)表示p所指向的結點(*p).datap-data表示p指向結點的數據域(*p).nextp-next表示p指向結點的指針域帶頭結點的單鏈表示意圖有時為了操作的方便，還可以在單

20、鏈表的第一個結點之前附設一個頭結點。n帶頭結點的空單鏈表 n帶頭結點的單鏈表 Ha1a2Han 2.3.2 單鏈表上的基本運算n線性表的基本運算：1.建立單鏈表 2.單鏈表查找 3.單鏈表插入 4.單鏈表刪除 n算法應用示例：1.求單鏈表的長度 2.求兩個集合的差 建立單鏈表n頭插法建表算法描述：算法描述：從一個空表開始，重復讀入數據，生成新結點，將讀入數據存放到新結點的數據域中，然后將新結點插入到當前鏈表的表頭結點之后，直至讀入結束標志為止。c1 sLL ci-1 c2 c1 ci sc1 建立單鏈表 c1 H S指向新申請的結點指向新申請的結點S-data=c1H-next=ss c1 H

21、 s頭插法建表 H c2s H-next=SH-next c1 頭插法建表 H c2s S -next =H-nextH-next c1 H-next=S H c2 c1 頭插法建表H c2c1 H cici-1c1 注：頭插法得到的單鏈表的邏輯順序與輸入元素順序相反，即為逆序建表。頭插法建表算法Linklist CreateFromHead() LinkList L; Node *s; int flag=1; /* 設置一個標志，初值為1，當輸入“$”時，flag為0，建表結束*/ L=(Linklist)malloc(sizeof(Node)；/*為頭結點分配存儲空間*/ L-next=N

22、ULL; while(flag) c=getchar(); if(c!=$) /*為讀入的字符分配存儲空間*/ s=(Node*)malloc(sizeof(Node); s-data=c; s-next=L-next; L-next=s; elseflag=0; 尾插法建表（建表及插入第一個結點） H r-next=S c1r r=SS指向新申請的結點指向新申請的結點S-data=c1s尾插法建表（插入第二個結點） H c2 r-next=S c1r r=Ss尾插法建表H c2c1r s注：尾插法得到的單鏈表的邏輯順序與輸入元素順序相同，即為順序建表。 H c1c2ci r s尾插法建表算法

23、Linklist CreateFromTail() /*將新增的字符追加到鏈表的末尾*/ LinkList L; Node *r, *s; int flag =1; L=(Node * )malloc(sizeof(Node);/*為頭結點分配存儲空間*/ L-next=NULL; r=L; /*r指針始終動態指向鏈表的當前表尾*/ while(flag)/*標志，初值為1。輸入“$”時flag為0，建表結束*/ c=getchar(); if(c!=$) s=(Node*)malloc(sizeof(Node); s-data=c; r-next=s; r=s else flag=0; r-

24、next=NULL; 單鏈表查找n按序號查找 算法描述：算法描述：設帶頭結點的單鏈表的長度為n，要查找表中第i個結點，則需要從單鏈表的頭指針L出發，從頭結點（L-next）開始順著鏈域掃描，用指針p指向當前掃描到的結點,初值指向頭結點（pL-next），用j做記數器，累計當前掃描過的結點數（初值為0），當j = i 時，指針p所指的結點就是要找的第i個結點 。算法實現，算法演示。按序號查找算法實現/ * 在帶頭結點的單鏈表L中查找第i個結點，若找到(1in)，則返回該結點的存儲位置; 否則返回NULL * /Node * Get(LinkList L, int i) Node *p； p=L；

25、j=0； / * 從頭結點開始掃描 * / while (p-next!=NULL)&(jnext； j+； / * 掃描下一結點 * / / * 已掃描結點計數器 * / if（i= =j）return p； / * 找到了第i個結點 * / else return NULL； / * 找不到，i0或in * /n 按值查找算法描述：算法描述：按值查找是指在單鏈表中查找是否有結點值等于e的結點，若有的話，則返回首次找到的其值為e的結點的存儲位置，否則返回NULL。查找過程從單鏈表的頭指針指向的頭結點出發，順著鏈逐個將結點的值和給定值e作比較。算法實現，算法演示。單鏈表查找按值查找算法實現/

26、* 在帶頭結點的單鏈表L中查找其結點值等于key的結點，若找到則返回該結點的位置p，否則返回NULL * /Node *Locate( LinkList L,ElemType key) Node *p; p=L-next; / * 從表中第一個結點比較 * / while (p!=NULL) if (p-data!=key) p=p-next; else break; / * 找到結點key，退出循環 * / return p;單鏈表插入操作n算法描述： 要在帶頭結點的單鏈表L中第i個數據元素之前插入一個數據元素e，需要首先在單鏈表中找到第i-1個結點并由指針pre指示，然后申請一個新的結點并

27、由指針s指示，其數據域的值為e，并修改第i-1個結點的指針使其指向s，然后使s結點的指針域指向第i個結點。esa1an ai-1aiespreLa1an preai-1ai單鏈表插入 H a1aian sai-1 epre與ai鏈接S-next=pre-next ai-1與ai斷鏈插入epre-next=s單鏈表插入操作算法實現void InsList(LinkList L,int i,ElemType e) /*在帶頭結點的單鏈表L中第i個結點之前插入值為e的新結點。 */ Node *pre,*s; pre=L; int k=0; while(pre!=NULL&knext;k=k+1;

28、if(k!=i-1) printf(“插入位置不合理！”)； return; s=(Node*)malloc(sizeof(Node); /*為e申請一個新的結點*/ s-data=e; /*將待插入結點的值e賦給s的數據域*/ s-next=pre-next; pre-next=s; 單鏈表最后一個元素怎么查找？ H a1aian ai-1preWhile（ ? ） pre=pre-next; pre!=null插入位置1im+1單鏈表刪除n算法描述：欲在帶頭結點的單鏈表L中刪除第i個結點，則首先要通過計數方式找到第i-1個結點并使p指向第i-1個結點，而后刪除第i個結點并釋放結點空間。 p

29、a1ai-1aian pa1Lan ai-1aiai+1rL單鏈表刪除 H ai+1aian rai-1p r=p-next p-next= p-next-next free（r）這個節點用指針p怎么表示？p-next-next單鏈表刪除 H an-1aian ai-1pWhile（ ? ） pre=pre-next; P- next!=null刪除位置1impp單鏈表刪除算法實現void DelList(LinkList L,int i,ElemType *e)/*在帶頭結點的單鏈表L中刪除第i個元素，并保存其值到變量*e中*/ Node *p,*r; p=L; int k =0;while

30、(p-next!=NULL&knext; k=k+1; if(k!=i-1) /* 即while循環是因為p-next=NULL而跳出的*/ printf(“刪除結點的位置i不合理！”); return ERROR; r=p-next; p-next=p-next-next /*刪除結點r*/free(r); /*釋放被刪除的結點所占的內存空間*/求單鏈表的長度算法描述：算法描述：可以采用“數”結點的方法來求出單鏈表的長度，用指針p依次指向各個結點,從第一個元素開始“數”，一直“數”到最后一個結點（p-next=NULL）。intListLength(LinkList L) /*L為帶頭結點的

31、單鏈表*/ Node *p; p=L-next; j=0; /*用來存放單鏈表的長度*/ while(p!=NULL) p=p-next; j +; return j; 求兩個集合的差n已知：已知：以單鏈表表示集合，假設集合A用單鏈表LA表示，集合B用單鏈表LB表示，設計算法求兩個集合的差，即A-B。n算法思想：算法思想：由集合運算的規則可知，集合的差A-B中包含所有屬于集合A而不屬于集合B的元素。具體做法是，對于集合A中的每個元素e，在集合B的鏈表LB中進行查找，若存在與e相同的元素，則從LA中將其刪除。n算法實現n算法演示鏈接求兩個集合的差算法實現void Difference (Link

32、List LA,LinkList LB) /*此算法求兩個集合的差集*/ Node *pre;*p, *r; pre=LA; p=LA-next; /*p向表中的某一結點，pre始終指向p的前驅*/ while(p!=NULL) q=LB-next; /*掃描LB中的結點，尋找與LA中*P結點相同的結點*/ while (q!=NULL&q-data!=p-data) q=q-next; if (q!=NULL) r=p; pre-next=p-next; p=p-next; free(r); else pre=p; p=p-next; 2.3.3 循環鏈表循環鏈表循環鏈表(Circular

33、Linked List) 是一個首尾相接的鏈表。 特點特點：將單鏈表最后一個結點的指針域由NULL改為指向頭結點或線性表中的第一個結點，就得到了單鏈形式的循環鏈表，并稱為循環單鏈表。在循環單鏈表中，表中所有結點被鏈在一個環上。 帶頭結點循環單鏈表示意圖。循環鏈表 L aianai-1帶頭結點的循環單鏈表示意圖 L(a) 空鏈表 a1ai-1aian L（b）帶頭結點的循環單鏈表的一般形式 帶頭結點的循環單鏈表示意圖a1ai-1aian *(rear-next)*rear(c)采用尾指針的循環單鏈表尾指針的循環單鏈表的一般形式 rear循環單鏈表合并為一個循環單鏈表已知已知：有兩個帶頭結點的循環

34、單鏈表LA、LB，編寫一個算法，將兩個循環單鏈表合并為一個循環單鏈表，其頭指針為LA。算法思想算法思想：先找到兩個鏈表的尾，并分別由指針p、q指向它們，然后將第一個鏈表的尾與第二個表的第一個結點鏈接起來，并修改第二個表的尾Q，使它的鏈域指向第一個表的頭結點。循環單鏈表合并為一個循環單鏈表a1ai-1aian b1bi-1bibn pqLALB循環單鏈表合并算法實現LinkList merge_1(LinkList LA,LinkList LB)/*此算法將兩個鏈表的首尾連接起來*/ Node *p, *q; p=LA; q=LB; while (p-next!=LA) p=p-next;/*找

35、到表LA的表尾*/ while (q-next!=LB) q=q-next;/*找到表LB的表尾*/ q-next=LA;/*修改表LB 的尾指針，使之指向表LA 的頭結點*/ p-next=LB-next;/*修改表LA的尾指針，使之指向表LB 中的第一個結點*/free(LB); return(LA);2.3.4 雙向鏈表 雙向鏈表：雙向鏈表：在單鏈表的每個結點里再增加一個指向其前趨的指針域prior。這樣形成的鏈表中就有兩條方向不同的鏈，我們稱之為雙雙 ( 向向) 鏈表鏈表 (Double Linked List)。雙向鏈表的結構定義：typedef struct Dnode ElemT

36、ype data； struct DNode *prior，*next； DNode,* DoubleList；雙鏈表的結構定義n雙鏈表的結點結構 后繼指針域prior data next前驅指針域數據域雙向循環鏈表示意圖 a1 a2 a3LL空的雙向循環鏈表 非空的雙向循環鏈表 雙向鏈表的前插操作n算法描述：欲在雙向鏈表第i個結點之前插入一個的新的結點，則指針的變化情況如圖所示。 es bp a p-priors-prior = p-priorp-prior -next = ss -next = pp-prior = s雙向鏈表的前插操作算法實現void DlinkIns(DoubleLis

37、t L,int i,ElemType e) DNode *s,*p; /*首先檢查待插入的位置i是否合法*/ /*若位置i合法，則讓指針p指向它*/ s=(DNode*)malloc(sizeof(DNode); if (s) s-data=e; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; return TRUE; else return FALSE; 雙向鏈表的刪除操作n算法描述：欲刪除雙向鏈表中的第i個結點，則指針的變化情況如圖所示。 a b cp c a p-prior-next = p next p- next -prio

38、r = p prior p nextp priorp prior-nextp next-prior雙向鏈表的刪除操作算法實現intDlinkDel(DoubleList L,int i,ElemType *e)DNode *p; /*首先檢查待插入的位置i是否合法*/ /*若位置i合法，則讓指針p指向它*/ *e=p-data; p-prior-next=p-next; p-next-prior=p-prior; free(p); return TRUE; 雙向鏈表應用舉例已知已知：設一個循環雙鏈表L=（a,b,c,d）編寫一個算法將鏈表轉換為L=（b,a,c,d）。算法思想：算法思想：實際上

39、是交換表中前兩個元素的次序。算法實現算法實現：voidswap(DLinkList L) DNode * p,*q,*h; h=L-next; /* h指向表中的第一個結點，即a */ p=h-next; /* p指向b結點 */ q=h-prior; /* 保存a 結點的前驅 */ h-next=p-next; p-next-prior=h; /*變換指針指向*/ p-prior=q; p-next=h; L-next=p; h-prior=p; *2.3.5 靜態鏈表靜態鏈表n基本概念：游標實現鏈表的方法游標實現鏈表的方法：定義一個較大的結構數組作為備用結點空間（即存儲池）。當申請結點時，

40、每個結點應含有兩個域：data域和next域。data域存放結點的數據信息，next域為游標指示器，指示后繼結點在結構數組中的相對位置（即數組下標）。數組的第0個分量可以設計成表的頭結點，頭結點的next域指示了表中第一個結點的位置，為0表示靜態單鏈表的結束。我們把這種用游標指示器實現的單鏈表叫做靜態單鏈表靜態單鏈表(Static Linked List)。靜態鏈表的結構定義，靜態鏈表的插入和刪除操作示例。 n基本操作：初始化、分配結點與結點回收、前插操作、刪除。 靜態鏈表的結構定義#define Maxsize= 鏈表可能達到的最大長度typedef struct ElemType data

41、; int cursor; Component, StaticListMaxsize; 靜態鏈表的插入和刪除操作示例已知已知：線性表 a，b，c，d，f，g，h，i），Maxsize=11 0123456789100123456789101a 2b 3c 4d 9f 6g 8h 8i 0e 51a 2b 3c 4d 9f 6g 7h 8i 0e 51a 2b 3c 4d 5f 6g 7h 8i 0012345678910(a)初始化(b)插入e后 (c)刪除h后 靜態鏈表初始化算法描述算法描述：初始化操作是指將這個靜態單鏈表初始化為一個備用靜態單鏈表。設space為靜態單鏈表的名字，av為備用

42、單鏈表的頭指針，其算法如下：void initial(StaticList space,int *av) int k; space0-cursor=0;/*設置靜態單鏈表的頭指針指向位置0*/ for(k=0;kcursor=k+1; /*連鏈*/ spaceMaxsize-1=0; /*標記鏈尾*/ *av=1; /*設置備用鏈表頭指針初值*/ 靜態鏈表分配結點與結點回收n分配結點分配結點int getnode(int *av)/*從備用鏈表摘下一個結點空間，分配給待插入靜態鏈表中的元素*/ int i=*av; *av=space*av.cur; return i; n結點回收結點回收 v

43、oid freenode(int *av,int k) /*將下標為 k的空閑結點插入到備用鏈表*/ spacek.cursor=*av; *av=k; 靜態鏈表前插操作算法描述算法描述：1、先從備用單鏈表上取一個可用的結點；2、將其插入到已用靜態單鏈表第i個元素之前。void insbefore(StaticList space,int i,int *av) j=*av ;/*j為從備用表中取到的可用結點空間的下標*/ av=spaceav-cursor;/*修改備用表的頭指針*/ spacej-data=x; k=space0-cursor;/*k為已用靜態單鏈表的第一個元素的下標值*/

44、for(m=1;mcursor; spacej-cursor=spacek-cursor; /*修改游標域*/ spacek-cursor=j; 靜態鏈表刪除算法描述：算法描述：首先尋找第i -1個元素的位置，之后通過修改相應的游標域進行刪除；在將被刪除的結點空間鏈到可用靜態單鏈表中，實現回收。void delete(StaticList space;int i;int *av ) k=space0-cursor; for(m=1,mcursor ; j=spacek-cursor ; spacek-cursor=spacej-cursor;/*從刪除第i個元素*/ spacej-cursor

45、=*av;/*將第i 個元素占據的空間回收*/ av=j ; /*置備用表頭指針以新值*/2.3.6 順序表和鏈表的比較順序表和鏈表的比較 1基于空間的考慮 2基于時間的考慮 l 順序表的特點是邏輯位置相鄰的數據元素其物理位順序表的特點是邏輯位置相鄰的數據元素其物理位置也相鄰，因此可以進行隨機存儲，是一種隨機存儲置也相鄰，因此可以進行隨機存儲，是一種隨機存儲結構。其插入和刪除操作的時間復雜度均為結構。其插入和刪除操作的時間復雜度均為O(n)。l 鏈表中的數據元素使用一組任意的存儲單元存儲，鏈表中的數據元素使用一組任意的存儲單元存儲，不要求邏輯位置相鄰的數據元素物理位置也相鄰，而不要求邏輯位置相

46、鄰的數據元素物理位置也相鄰，而是采用附加的指針表示元素之間的邏輯關系。鏈表的是采用附加的指針表示元素之間的邏輯關系。鏈表的插入和刪除結點均不需要移動其他結點，但是，其查插入和刪除結點均不需要移動其他結點，但是，其查找運算必須從頭指針開始順序查找，其時間復雜度為找運算必須從頭指針開始順序查找，其時間復雜度為O(n)。2.4 一元多項式的表示及相加 一個一元多項式Pn(x)可按升冪的形式寫成：Pn(x)=p0+p1x+p2x2+p3x3+ +pnxn 在計算機內，可以用一個線性表P來表示： P=（p0，p1，p2， ，pn） 用單鏈表存儲多項式的結點結構如下： typedef struct Pol

47、ynode int coef; int exp; Polynode *next; Polynode , * Polylist; coefexpnext建立多項式鏈表l算法描述算法描述：輸入多項式的系數和指數，用尾插法建立一元多項式的鏈表。Polylist polycreate() Polynode *head, *rear, *s; int c,e; rear=head =(Polynode *)malloc(sizeof(Polynode); /*建立多項式的頭結點， rear 始終指向單鏈表的尾*/ scanf(“%d,%d”,&c,&e);/*鍵入多項式的系數和指數項*/ while(c

48、!=0)/*若c=0，則代表多項式的輸入結束*/ s=(Polynode*)malloc(sizeof(Polynode);/*申請新的結點*/ s-coef=c ; s-exp=e ;rear-next=s ;/*在當前表尾做插入*/ rear=s; scanf(“%d,%d”,&c,&e); rear-next=NULL;/*將表的最后一個結點的next置NULL，以示表結束*/ return(head);多項式的單鏈表表示示意圖說明：圖示分別為多項式A(x)=7+3x+9x8+5x17B(x)=8x+22x7-9x8 -17 03 15 17 9 88 1 -122 7 -9 8 設p,

49、q分別指向A,B中某一結點，p,q初值是第一結點比較p-exp與q-expp-exp exp: p結點是和多項式中的一項 p后移,q不動p-exp q-exp: q結點是和多項式中的一項 將q插在p之前,q后移,p不動p-exp = q-exp: 系數相加0：從A表中刪去p, 釋放p,q，p,q后移0：修改p系數域, 釋放q，p,q后移直到p或q為NULL 若q=NULL，結束 若p=NULL，將B中剩余部分連到A上即可n運算規則兩個多項式中所有指數相同的項的對應系數相加，若和不為零，則構成“和多項式”中的一項；所有指數不相同的項均復抄到“和多項式”中。兩個多項式相加兩個多項式相加算法實現vo

50、id polyadd(Polylist polya;Polylist polyb) /* p和q分別指向polya和polyb鏈表中的當前計算結點*/ /* pre指向和多項式鏈表中的尾結點*/ while p!=NULL & q!=NULL） if （p-expexp） /*將p結點加入到和多項式中*/ else if ( p-exp= =q-exp） /*若指數相等，則相應的系數相加。若系數為0則刪除p，q節點*/ else /*將q結點加入到和多項式中*/ ./*將多項式polya或polyb中剩余的結點加入到和多項式中*/q-1pa7 0 3 1 9 8 5 17 -1pb8 1 22

51、 7 -9 8 ppreq-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre q-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre-1pa7 0 11 1 22 7 5 17 復習1、順序表的插入2、順序表的刪除3、單鏈表的插入4、單鏈表的刪除5、循環鏈表的合并6、雙向鏈表的插入7、雙向鏈表的刪除 . .loc(aloc(a1 1)+(maxlen-1)k )+(maxlen-1)k n n a an n loc(aloc(a1 1)+(n-1)k )+(n-1)