數(shù)據(jù)結(jié)構(gòu)課件教材

1、第二章 線性表2.1 線性表及其基本運算2.2 線性表的順序存儲結(jié)構(gòu)2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)，以及它們之間的相互關(guān)系；定義與之相適應(yīng)的運算；設(shè)計相應(yīng)的算法；分析算法的效率。線性結(jié)構(gòu)特點：在數(shù)據(jù)元素的非空有限集中n存在存在唯一唯一的一個被稱作的一個被稱作“第一個第一個”的數(shù)據(jù)元的數(shù)據(jù)元素素n存在存在唯一唯一的一個被稱作的一個被稱作“最后一個最后一個”的數(shù)據(jù)的數(shù)據(jù)元素元素n除第一個外，集合中的每個數(shù)據(jù)元素均除第一個外，集合中的每個數(shù)據(jù)元素均只有只有一個前驅(qū)一個前驅(qū)n除最后一個外，集合中的每個數(shù)據(jù)元素均除最后一個外，集合中的每個數(shù)據(jù)元素均只只有一個后繼有一個后繼2.1

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

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

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

5、結(jié)構(gòu)n特點：n實現(xiàn)邏輯上相鄰物理地址相鄰n實現(xiàn)隨機存取n實現(xiàn)：可用C語言的一維數(shù)組實現(xiàn)a1a2an01n-112n內(nèi)存V數(shù)組下標(biāo)元素序號M-1typedef int DATATYPE; #define M 1000DATATYPE dataM;例 typedef struct card int num; char name20; char author10; char publisher30; float price;DATATYPE;DATATYPE libraryM; 備用空間數(shù)據(jù)元素不是簡單類型時,可定義結(jié)構(gòu)體數(shù)組或動態(tài)申請和釋放內(nèi)存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) ) 邏輯地址邏輯地址 內(nèi)存空間狀態(tài)內(nèi)存空間狀態(tài) 存儲地址存儲地址 順序存儲結(jié)構(gòu)示意圖順序存儲結(jié)構(gòu)示意圖空閑空閑順序存儲結(jié)構(gòu)示意圖順

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

8、(L,i)：要求查找線性表L中第i個數(shù)據(jù)元素，其結(jié)果是L.elemi-1或L-elemi-1。u按內(nèi)容查找按內(nèi)容查找Locate（L,e）: : 要求查找線性表L中與給定值e相等的數(shù)據(jù)元素，其結(jié)果是：若在表L中找到與e相等的元素，則返回該元素在表中的序號；若找不到，則返回一個“空序號”，如-1。 線性表的查找運算算法描述為：線性表的查找運算 int Locate(SeqList L，ElemType e) i=0 ; /*i為掃描計數(shù)器，初值為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內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號i+1nn+1內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)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語言中數(shù)組第i個元素的下標(biāo)為i-1*/ L-last+; return(OK); 設(shè)Pi是在第i個元素之前插入一個元素的概率，則在長度為n的線性表中插入一個元素時，所需移動的元素次數(shù)的平均次數(shù)為：11)1(niiinPEis nOnTninnEisnPnii112)1(1111則若認(rèn)為插入運算算法時間復(fù)雜度T(n)3.刪除操作線性表的刪除運算是指將表的第i

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

13、ist *L,int i,ElemType *e)/*在順序表L中刪除第i個數(shù)據(jù)元素，并用指針參數(shù)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); 設(shè)Qi是刪除第i個元素的概率，則在長度為n的線性表中刪除一個元素所需移動的元素次數(shù)的平均次數(shù)為：niideinQE1)( nOnTninnEnQnid

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

15、未掃描完的表中剩余的所有元素放到表LC中。n算法實現(xiàn)順序表合并算法實現(xià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)/*當(dāng)表LA長則將表LA余下的元素賦給表LC*/ LC-elemk= LA-elemi; i+; k+; while(jlast) /*當(dāng)表LB長則將表LB余下的元素賦給表LC*/ LC

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

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

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

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

20、鏈表的第一個結(jié)點之前附設(shè)一個頭結(jié)點。n帶頭結(jié)點的空單鏈表 n帶頭結(jié)點的單鏈表 Ha1a2Han 2.3.2 單鏈表上的基本運算n線性表的基本運算：1.建立單鏈表 2.單鏈表查找 3.單鏈表插入 4.單鏈表刪除 n算法應(yīng)用示例：1.求單鏈表的長度 2.求兩個集合的差 建立單鏈表n頭插法建表算法描述：算法描述：從一個空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點，將讀入數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中，然后將新結(jié)點插入到當(dāng)前鏈表的表頭結(jié)點之后，直至讀入結(jié)束標(biāo)志為止。c1 sLL ci-1 c2 c1 ci sc1 建立單鏈表 c1 H S指向新申請的結(jié)點指向新申請的結(jié)點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; /* 設(shè)置一個標(biāo)志，初值為1，當(dāng)輸入“$”時，flag為0，建表結(jié)束*/ L=(Linklist)malloc(sizeof(Node)；/*為頭結(jié)點分配存儲空間*/ 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; 尾插法建表（建表及插入第一個結(jié)點） H r-next=S c1r r=SS指向新申請的結(jié)點指向新申請的結(jié)點S-data=c1s尾插法建表（插入第二個結(jié)點） 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);/*為頭結(jié)點分配存儲空間*/ L-next=NULL; r=L; /*r指針始終動態(tài)指向鏈表的當(dāng)前表尾*/ while(flag)/*標(biāo)志，初值為1。輸入“$”時flag為0，建表結(jié)束*/ 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按序號查找 算法描述：算法描述：設(shè)帶頭結(jié)點的單鏈表的長度為n，要查找表中第i個結(jié)點，則需要從單鏈表的頭指針L出發(fā)，從頭結(jié)點（L-next）開始順著鏈域掃描，用指針p指向當(dāng)前掃描到的結(jié)點,初值指向頭結(jié)點（pL-next），用j做記數(shù)器，累計當(dāng)前掃描過的結(jié)點數(shù)（初值為0），當(dāng)j = i 時，指針p所指的結(jié)點就是要找的第i個結(jié)點 。算法實現(xiàn)，算法演示。按序號查找算法實現(xiàn)/ * 在帶頭結(jié)點的單鏈表L中查找第i個結(jié)點，若找到(1in)，則返回該結(jié)點的存儲位置; 否則返回NULL * /Node * Get(LinkList L, int i) Node *p； p=L；

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

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

27、由指針s指示，其數(shù)據(jù)域的值為e，并修改第i-1個結(jié)點的指針使其指向s，然后使s結(jié)點的指針域指向第i個結(jié)點。esa1an ai-1aiespreLa1an preai-1ai單鏈表插入 H a1aian sai-1 epre與ai鏈接S-next=pre-next ai-1與ai斷鏈插入epre-next=s單鏈表插入操作算法實現(xiàn)void InsList(LinkList L,int i,ElemType e) /*在帶頭結(jié)點的單鏈表L中第i個結(jié)點之前插入值為e的新結(jié)點。 */ 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申請一個新的結(jié)點*/ s-data=e; /*將待插入結(jié)點的值e賦給s的數(shù)據(jù)域*/ s-next=pre-next; pre-next=s; 單鏈表最后一個元素怎么查找？ H a1aian ai-1preWhile（ ? ） pre=pre-next; pre!=null插入位置1im+1單鏈表刪除n算法描述：欲在帶頭結(jié)點的單鏈表L中刪除第i個結(jié)點，則首先要通過計數(shù)方式找到第i-1個結(jié)點并使p指向第i-1個結(jié)點，而后刪除第i個結(jié)點并釋放結(jié)點空間。 p

29、a1ai-1aian pa1Lan ai-1aiai+1rL單鏈表刪除 H ai+1aian rai-1p r=p-next p-next= p-next-next free（r）這個節(jié)點用指針p怎么表示？p-next-next單鏈表刪除 H an-1aian ai-1pWhile（ ? ） pre=pre-next; P- next!=null刪除位置1impp單鏈表刪除算法實現(xiàn)void DelList(LinkList L,int i,ElemType *e)/*在帶頭結(jié)點的單鏈表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循環(huán)是因為p-next=NULL而跳出的*/ printf(“刪除結(jié)點的位置i不合理！”); return ERROR; r=p-next; p-next=p-next-next /*刪除結(jié)點r*/free(r); /*釋放被刪除的結(jié)點所占的內(nèi)存空間*/求單鏈表的長度算法描述：算法描述：可以采用“數(shù)”結(jié)點的方法來求出單鏈表的長度，用指針p依次指向各個結(jié)點,從第一個元素開始“數(shù)”，一直“數(shù)”到最后一個結(jié)點（p-next=NULL）。intListLength(LinkList L) /*L為帶頭結(jié)點的

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

32、List LA,LinkList LB) /*此算法求兩個集合的差集*/ Node *pre;*p, *r; pre=LA; p=LA-next; /*p向表中的某一結(jié)點，pre始終指向p的前驅(qū)*/ while(p!=NULL) q=LB-next; /*掃描LB中的結(jié)點，尋找與LA中*P結(jié)點相同的結(jié)點*/ 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 循環(huán)鏈表循環(huán)鏈表循環(huán)鏈表(Circular

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

34、單鏈表LA、LB，編寫一個算法，將兩個循環(huán)單鏈表合并為一個循環(huán)單鏈表，其頭指針為LA。算法思想算法思想：先找到兩個鏈表的尾，并分別由指針p、q指向它們，然后將第一個鏈表的尾與第二個表的第一個結(jié)點鏈接起來，并修改第二個表的尾Q，使它的鏈域指向第一個表的頭結(jié)點。循環(huán)單鏈表合并為一個循環(huán)單鏈表a1ai-1aian b1bi-1bibn pqLALB循環(huán)單鏈表合并算法實現(xiàn)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 的頭結(jié)點*/ p-next=LB-next;/*修改表LA的尾指針，使之指向表LB 中的第一個結(jié)點*/free(LB); return(LA);2.3.4 雙向鏈表 雙向鏈表：雙向鏈表：在單鏈表的每個結(jié)點里再增加一個指向其前趨的指針域prior。這樣形成的鏈表中就有兩條方向不同的鏈，我們稱之為雙雙 ( 向向) 鏈表鏈表 (Double Linked List)。雙向鏈表的結(jié)構(gòu)定義：typedef struct Dnode ElemT

36、ype data； struct DNode *prior，*next； DNode,* DoubleList；雙鏈表的結(jié)構(gòu)定義n雙鏈表的結(jié)點結(jié)構(gòu) 后繼指針域prior data next前驅(qū)指針域數(shù)據(jù)域雙向循環(huán)鏈表示意圖 a1 a2 a3LL空的雙向循環(huán)鏈表 非空的雙向循環(huán)鏈表 雙向鏈表的前插操作n算法描述：欲在雙向鏈表第i個結(jié)點之前插入一個的新的結(jié)點，則指針的變化情況如圖所示。 es bp a p-priors-prior = p-priorp-prior -next = ss -next = pp-prior = s雙向鏈表的前插操作算法實現(xiàn)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個結(jié)點，則指針的變化情況如圖所示。 a b cp c a p-prior-next = p next p- next -prio

38、r = p prior p nextp priorp prior-nextp next-prior雙向鏈表的刪除操作算法實現(xiàn)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; 雙向鏈表應(yīng)用舉例已知已知：設(shè)一個循環(huán)雙鏈表L=（a,b,c,d）編寫一個算法將鏈表轉(zhuǎn)換為L=（b,a,c,d）。算法思想：算法思想：實際上

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

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

41、; int cursor; Component, StaticListMaxsize; 靜態(tài)鏈表的插入和刪除操作示例已知已知：線性表 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后 靜態(tài)鏈表初始化算法描述算法描述：初始化操作是指將這個靜態(tài)單鏈表初始化為一個備用靜態(tài)單鏈表。設(shè)space為靜態(tài)單鏈表的名字，av為備用

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

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

44、for(m=1;mcursor; spacej-cursor=spacek-cursor; /*修改游標(biāo)域*/ spacek-cursor=j; 靜態(tài)鏈表刪除算法描述：算法描述：首先尋找第i -1個元素的位置，之后通過修改相應(yīng)的游標(biāo)域進(jìn)行刪除；在將被刪除的結(jié)點空間鏈到可用靜態(tài)單鏈表中，實現(xiàn)回收。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 個元素占據(jù)的空間回收*/ av=j ; /*置備用表頭指針以新值*/2.3.6 順序表和鏈表的比較順序表和鏈表的比較 1基于空間的考慮 2基于時間的考慮 l 順序表的特點是邏輯位置相鄰的數(shù)據(jù)元素其物理位順序表的特點是邏輯位置相鄰的數(shù)據(jù)元素其物理位置也相鄰，因此可以進(jìn)行隨機存儲，是一種隨機存儲置也相鄰，因此可以進(jìn)行隨機存儲，是一種隨機存儲結(jié)構(gòu)。其插入和刪除操作的時間復(fù)雜度均為結(jié)構(gòu)。其插入和刪除操作的時間復(fù)雜度均為O(n)。l 鏈表中的數(shù)據(jù)元素使用一組任意的存儲單元存儲，鏈表中的數(shù)據(jù)元素使用一組任意的存儲單元存儲，不要求邏輯位置相鄰的數(shù)據(jù)元素物理位置也相鄰，而不要求邏輯位置相

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

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

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

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

50、id polyadd(Polylist polya;Polylist polyb) /* p和q分別指向polya和polyb鏈表中的當(dāng)前計算結(jié)點*/ /* pre指向和多項式鏈表中的尾結(jié)點*/ while p!=NULL & q!=NULL） if （p-expexp） /*將p結(jié)點加入到和多項式中*/ else if ( p-exp= =q-exp） /*若指數(shù)相等，則相應(yīng)的系數(shù)相加。若系數(shù)為0則刪除p，q節(jié)點*/ else /*將q結(jié)點加入到和多項式中*/ ./*將多項式polya或polyb中剩余的結(jié)點加入到和多項式中*/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 復(fù)習(xí)1、順序表的插入2、順序表的刪除3、單鏈表的插入4、單鏈表的刪除5、循環(huán)鏈表的合并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)