《數(shù)據(jù)結(jié)構(gòu)課件之線性表 .pptx》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)課件之線性表 .pptx（85頁珍藏版）》請?jiān)趨R文網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)課件數(shù)據(jù)結(jié)構(gòu)課件西北大學(xué)計(jì)算機(jī)系本演示文稿可能包含觀眾討論和即本演示文稿可能包含觀眾討論和即席反應(yīng)。使用席反應(yīng)。使用 PowerPoint 可以可以跟蹤演示時(shí)的即席反應(yīng)，跟蹤演示時(shí)的即席反應(yīng)，在幻燈片放映中，右鍵單擊鼠標(biāo)在幻燈片放映中，右鍵單擊鼠標(biāo)請選擇請選擇“會議記錄會議記錄”選擇選擇“即席反應(yīng)即席反應(yīng)”選項(xiàng)卡選項(xiàng)卡必要時(shí)輸入即席反應(yīng)必要時(shí)輸入即席反應(yīng)單擊單擊“確定確定”撤消此框撤消此框此動作將自動在演示文稿末尾創(chuàng)建此動作將自動在演示文稿末尾創(chuàng)建一張即席反應(yīng)幻燈片，包括您的一張即席反應(yīng)幻燈片，包括您的觀點(diǎn)。觀點(diǎn)。10/1/20231第第2章章 線性表線性表 l2.1 線性表的概念及運(yùn)

2、算 l2.2 線性表的順序存儲 l2.3 線性表的鏈?zhǔn)酱鎯?l2.4 一元多項(xiàng)式的表示及相加10/1/202322.1 2.1 線性表的概念及運(yùn)算線性表的概念及運(yùn)算l2.1.1 2.1.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu) l2.1.2 2.1.2 線性表的抽象數(shù)據(jù)類型定義線性表的抽象數(shù)據(jù)類型定義 10/1/20233線性表的定義線線性性表表(Linear List)是由n(n0)個類型相同的數(shù)據(jù)元素a1,a2,，an組成的有限序列，記做（a1,a2,，ai-1，ai，ai+1，an）。數(shù)據(jù)元素之間是一對一的關(guān)系，即每個數(shù)據(jù)元素最多有一個直接前驅(qū)和一個直接后繼。線性表的邏輯結(jié)構(gòu)圖為：10/1/

3、20234線性表的特點(diǎn)線性表的特點(diǎn)同一性：線性表由同類數(shù)據(jù)元素組成，每一個ai必須屬于同一數(shù)據(jù)對象。有窮性：線性表由有限個數(shù)據(jù)元素組成，表長度就是表中數(shù)據(jù)元素的個數(shù)。有序性：線性表中相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系。10/1/202352.1.2 線性表的抽象數(shù)據(jù)類型定義l抽象數(shù)據(jù)類型定義抽象數(shù)據(jù)類型定義：ADT LinearList數(shù)據(jù)元素?cái)?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

4、(L)操作前提：線性表L已存在。操作結(jié)果：將L銷毀。（3）ClearList(L)操作前提：線性表L已存在。操作結(jié)果：將表L置為空表。ADTLinearList10/1/202362.2 2.2 線性表的順序存儲線性表的順序存儲l2.2.1 線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)l2.2.2 線性表順序存儲結(jié)構(gòu)上的基本運(yùn)算線性表順序存儲結(jié)構(gòu)上的基本運(yùn)算10/1/20237順序存儲結(jié)構(gòu)的定義 線性表的順序存儲是指用一組地址連續(xù)的存儲單元依次存儲線性表中的各個元素，使得線性表中在邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲在相鄰的物理存儲單元中，即通過數(shù)據(jù)元素物理存儲的相鄰關(guān)系來反映數(shù)據(jù)元素之間邏輯上的相鄰關(guān)系

5、。采用順序存儲結(jié)構(gòu)的線性表通常稱為順序表順序表。假設(shè)線性表中每個元素占k個單元，第一個元素的地址為loc(a1)，則第k個元素的地址為：loc(ai)=loc(a1)+(i-1)k 10/1/20238順序存儲結(jié)構(gòu)示意圖順序存儲結(jié)構(gòu)示意圖存儲地址內(nèi)存空間狀態(tài)邏輯地址Loc(a1)a11Loc(a1)+(2-1)ka22loc(a1)+(i-1)kaiiloc(a1)+(n-1)kann.loc(a1)+(maxlen-1)k 空閑10/1/20239順序存儲結(jié)構(gòu)的順序存儲結(jié)構(gòu)的C語言定義語言定義#definemaxsize=線性表可能達(dá)到的最大長度；typedefstructElemTypee

6、lemmaxsize；/*線性表占用的數(shù)組空間*/intlast；/*記錄線性表中最后一個元素在數(shù)組elem 中的位置（下標(biāo)值），空表置為-1*/SeqList；注意區(qū)分元素的序號和數(shù)組的下標(biāo)，如a1的序號為1，而其對應(yīng)的數(shù)組下標(biāo)為0。10/1/2023102.2.2線性表順序存儲結(jié)構(gòu)的基本運(yùn)算l線性表的基本運(yùn)算：1.查找操作2.插入操作3.刪除操作4.順序表合并算法l線性表順序存儲結(jié)構(gòu)的優(yōu)缺點(diǎn)分析10/1/202311查找操作查找操作線性表的兩種基本查找運(yùn)算1.1.按序號查找按序號查找GetData(L,i)：要求查找線性表L中第i個數(shù)據(jù)元素，其結(jié)果是L.elemi-1或L-elemi-1。

7、2.2.按內(nèi)容查找按內(nèi)容查找Locate（L,e）:要求查找線性表L中與給定值e相等的數(shù)據(jù)元素，其結(jié)果是：若在表L中找到與e相等的元素，則返回該元素在表中的序號；若找不到，則返回一個“空序號”，如-1。3.線性表的查找運(yùn)算算法描述為：10/1/202312線性表的查找運(yùn)算線性表的查找運(yùn)算 int Locate(SeqListL，ElemTypee)i=0;/*i為掃描計(jì)數(shù)器，初值為0，即從第一個元素開始比較*/while(i=L.last)&(L.elemi!=e)i+;/*順序掃描表，直到找到值為key的元素,或掃描到表尾而沒找到*/if(i=L.last)return(i);/*若找到值為

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

9、123456781094915283030425162491528303042625149152128303042625110/1/202315插入運(yùn)算插入運(yùn)算intInsList(SeqList*L,inti,ElemTypee)intk;if(iL-last+2)/*首先判斷插入位置是否合法*/printf(“插入位置i值不合法”)；return(ERROR);if(L-last=maxsize-1)printf(“表已滿無法插入”)；return(ERROR);for(k=L-last;k=i-1;k-)/*為插入元素而移動位置*/L-elemk+1=L-elemk;L-elemi-1=

10、e;/*在C語言中數(shù)組第i個元素的下標(biāo)為i-1*/L-last+;return(OK);算法演示（此處連接算法演示程序）。10/1/202316刪除操作刪除操作線性表的刪除運(yùn)算是指將表的第i(1in)個元素刪去，使長度為n的線性表(e1，,ei-1，ei，ei+1，en)，變成長度為n-1的線性表(e1，,ei-1，ei+1，en)。算法思路示意算法實(shí)現(xiàn)10/1/202317刪除刪除算法示意算法示意將線性表(4,9,15,21,28,30,30,42,51,62)中的第5個元素刪除。序號123456781094915212830304262514915213030425162刪除28后10/1

11、/202318刪除刪除算法算法intDelList(SeqList*L,inti,ElemType*e)/*在順序表L中刪除第i個數(shù)據(jù)元素，并用指針參數(shù)e返回其值*/intk;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);10/1/202319合并算法合并算法l已知：有兩個順序表LA和LB，其元素均為非遞減有序排列，編寫一個算法，將它們合并成一個順

12、序表LC，要求LC也是非遞減有序排列。l算法思想算法思想：設(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)行下去，直到其中一個表被掃描完畢，然后再將未掃描完的表中剩余的所有元素放到表LC中。l算法實(shí)現(xiàn)l此處連接算法演示10/1/202320順序表順序表合并算法實(shí)現(xiàn)合并算法實(shí)現(xiàn)voidmerge(SeqList*LA,SeqList*LB,SeqList*LC)i=0;j=0;k=0;whi

13、le(ilast&jlast)if(LA-elemielemj)LC-elemk=LA-elemi;i+;k+;elseLC-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-elemk=LB-elemj;j+;k+;LC-last=LA-last+LB-last;10/1/202321順序存儲結(jié)構(gòu)的優(yōu)點(diǎn)和缺點(diǎn)順序存儲結(jié)構(gòu)的優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)：1.無需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲空間；2.可方便地隨機(jī)

14、存取表中的任一元素。缺點(diǎn)：1.插入或刪除運(yùn)算不方便，除表尾的位置外，在表的其它位置上進(jìn)行插入或刪除操作都必須移動大量的結(jié)點(diǎn)，其效率較低；2.由于順序表要求占用連續(xù)的存儲空間，存儲分配只能預(yù)先進(jìn)行靜態(tài)分配。因此當(dāng)表長變化較大時(shí)，難以確定合適的存儲規(guī)模。10/1/2023222.3 2.3 線性表的鏈?zhǔn)酱鎯€性表的鏈?zhǔn)酱鎯鏈表定義：鏈表定義：采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表稱為鏈表。現(xiàn)在我們從兩個角度來討論鏈表：1.從實(shí)現(xiàn)角度看，鏈表可分為動態(tài)鏈表和靜態(tài)鏈表；2.從鏈接方式的角度看，鏈表可分為單鏈表、循環(huán)鏈表和雙鏈表。10/1/202323l2.3.1 單鏈表單鏈表l2.3.2 單鏈表上的基本運(yùn)算單鏈表

15、上的基本運(yùn)算l2.3.3 循環(huán)鏈表循環(huán)鏈表l2.3.4 雙向鏈表雙向鏈表l*2.3.5 靜態(tài)鏈表靜態(tài)鏈表l2.3.6 順序表和鏈表的比較順序表和鏈表的比較鏈表鏈表10/1/2023242.3.1單鏈表 結(jié)點(diǎn)（結(jié)點(diǎn)（Node）為了正確地表示結(jié)點(diǎn)間的邏輯關(guān)系，必須在存儲線性表的每個數(shù)據(jù)元素值的同時(shí)，存儲指示其后繼結(jié)點(diǎn)的地址（或位置）信息，這兩部分信息組成的存儲映象叫做結(jié)點(diǎn)（結(jié)點(diǎn)（Node）。單鏈表：鏈表中的每個結(jié)點(diǎn)只有一個指針域，我們將這種鏈表稱為單鏈表。單鏈表包括兩個域：數(shù)據(jù)域用來存儲結(jié)點(diǎn)的值；指針域用來存儲數(shù)據(jù)元素的直接后繼的地址（或位置）。頭指針頭指針：指向鏈表頭結(jié)點(diǎn)的指針。10/1/202

16、325單鏈表的示例圖單鏈表的示例圖頭指針H存儲地址數(shù)據(jù)域指針域1 D 437 B 1313 C 119 H NULL25 F 3731 A 737 G 1943 E 253110/1/202326帶頭結(jié)點(diǎn)的單鏈表示意圖帶頭結(jié)點(diǎn)的單鏈表示意圖有時(shí)為了操作的方便，還可以在單鏈表的第一個結(jié)點(diǎn)之前附設(shè)一個頭結(jié)點(diǎn)。l帶頭結(jié)點(diǎn)的空單鏈表l帶頭結(jié)點(diǎn)的單鏈表Ha1a2Han 10/1/202327單鏈表的存儲結(jié)構(gòu)描述單鏈表的存儲結(jié)構(gòu)描述typedef struct Node /*結(jié)點(diǎn)類型定義*/ElemType data；struct Node *next；Node,*LinkList；/*LinkList為

17、結(jié)構(gòu)指針類型*/10/1/2023282.3.2單鏈表上的基本運(yùn)算l線性表的基本運(yùn)算：1.建立單鏈表2.單鏈表查找3.單鏈表插入操作4.單鏈表刪除l算法應(yīng)用示例：1.求單鏈表的長度2.求兩個集合的差10/1/202329建立單鏈表建立單鏈表l頭插法建表算法描述：算法描述：從一個空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭結(jié)點(diǎn)之后，直至讀入結(jié)束標(biāo)志為止。c1 sLL ci-1 c2 c1 ci sc1 10/1/202330頭插法建表算法頭插法建表算法Linklist CreateFromHead()LinkList L;Node *s;

18、int flag=1;/*設(shè)置一個標(biāo)志，初值為1，當(dāng)輸入“$”時(shí)，flag為0，建表結(jié)束*/L=(Linklist)malloc(sizeof(Node)；/*為頭結(jié)點(diǎn)分配存儲空間*/L-next=NULL;while(flag)c=getchar();if(c!=$)/*為讀入的字符分配存儲空間*/s=(Node*)malloc(sizeof(Node);s-data=c;s-next=L-next;L-next=s;elseflag=0;10/1/202331尾插法建表尾插法建表C1 srLc1 rsc2 Lc1 rsL10/1/202332尾插法建表算法尾插法建表算法Linklist C

19、reateFromTail()/*將新增的字符追加到鏈表的末尾*/LinkList L;Node*r,*s;int flag=1;L=(Node*)malloc(sizeof(Node);/*為頭結(jié)點(diǎn)分配存儲空間*/L-next=NULL;r=L;/*r指針始終動態(tài)指向鏈表的當(dāng)前表尾*/while(flag)/*標(biāo)志，初值為1。輸入“$”時(shí)flag為0，建表結(jié)束*/c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node);s-data=c;r-next=s;r=s else flag=0;r-next=NULL;10/1/202333單鏈表查找單鏈表查找

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

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

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

23、第i-1個結(jié)點(diǎn)的指針使其指向s，然后使s結(jié)點(diǎn)的指針域指向第i個結(jié)點(diǎn)。esa1an ai-1aiespreLa1an preai-1ai10/1/202338單鏈表插入操作算法實(shí)現(xiàn)單鏈表插入操作算法實(shí)現(xiàn)void InsList(LinkList L,int i,ElemType e)/*在帶頭結(jié)點(diǎn)的單鏈表L中第i個結(jié)點(diǎn)之前插入值為e的新結(jié)點(diǎn)。*/Node*pre,*s;pre=L;int k=0;while(pre!=NULL&knext;k=k+1;if(k!=i-1)printf(“插入位置不合理！”)；return;s=(Node*)malloc(sizeof(Node);/*為e申請一個

24、新的結(jié)點(diǎn)*/s-data=e;/*將待插入結(jié)點(diǎn)的值e賦給s的數(shù)據(jù)域*/s-next=pre-next;pre-next=s;10/1/202339單鏈表刪除單鏈表刪除l算法描述：欲在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個結(jié)點(diǎn)，則首先要通過計(jì)數(shù)方式找到第i-1個結(jié)點(diǎn)并使p指向第i-1個結(jié)點(diǎn)，而后刪除第i個結(jié)點(diǎn)并釋放結(jié)點(diǎn)空間。pa1ai-1aian pa1Lan ai-1aiai+1rL10/1/202340單鏈表刪除算法實(shí)現(xiàn)單鏈表刪除算法實(shí)現(xiàn)void DelList(LinkList L,int i,ElemType*e)/*在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個元素，并保存其值到變量*e中*/Node*p,

25、*r;p=L;int k=0;while(p-next!=NULL&knext;k=k+1;if(k!=i-1)/*即while循環(huán)是因?yàn)閜-next=NULL而跳出的*/printf(“刪除結(jié)點(diǎn)的位置i不合理！”);return ERROR;r=p-next;p-next=p-next-next /*刪除結(jié)點(diǎn)r*/free(r);/*釋放被刪除的結(jié)點(diǎn)所占的內(nèi)存空間*/10/1/202341求單鏈表的長度求單鏈表的長度算法描述：算法描述：可以采用“數(shù)”結(jié)點(diǎn)的方法來求出單鏈表的長度，用指針p依次指向各個結(jié)點(diǎn),從第一個元素開始“數(shù)”，一直“數(shù)”到最后一個結(jié)點(diǎn)（p-next=NULL）。int Li

26、stLength(LinkList L)/*L為帶頭結(jié)點(diǎn)的單鏈表*/Node*p;p=L-next;j=0;/*用來存放單鏈表的長度*/while(p!=NULL)p=p-next;j+;return j;算法演示鏈接。10/1/202342兩個有序單鏈表的合并兩個有序單鏈表的合并l有兩個單鏈表LA和LB，其元素均為非遞減有序排列，編寫一個算法，將它們合并成一個單鏈表LC，要求LC也是非遞減有序排列。要求：利用新表LC利用現(xiàn)有的表LA和LB中的元素結(jié)點(diǎn)空間，而不需要額外申請結(jié)點(diǎn)空間。例如LA=(2,2,3),LB=(1,3,3,4),則LC=(1,2,2,3,3,3,4)?！舅惴枋觥俊舅惴?/p>

27、述】要求利用現(xiàn)有的表LA和LB中的結(jié)點(diǎn)空間來建立新表LC,可通過更改結(jié)點(diǎn)的next域來重建新的元素之間的線性關(guān)系，為保證新表仍然遞增有序，可以利用尾插入法建立單鏈表的方法，只是新建表中的結(jié)點(diǎn)不用malloc，而只需要從表LA和LB中選擇合適的點(diǎn)插入到新表LC中即可。10/1/20234310/1/202344兩個有序單鏈表的合并的算法實(shí)現(xiàn)兩個有序單鏈表的合并的算法實(shí)現(xiàn)LinkListMergeLinkList(LinkListLA,LinkListLB)/*將遞增有序的單鏈表LA和LB合并成一個遞增有序的單鏈表LC*/Node*pa,*pb;LinkListLC；/*將LC初始置空表。pa和p

28、b分別指向兩個單鏈表LA和LB中的第一個結(jié)點(diǎn),r初值為LC*/pa=LA-next;pb=LB-next;LC=LA;LC-next=NULL；r=LC;/*初始化操作*/10/1/202345兩個有序單鏈表的合并的算法實(shí)現(xiàn)（續(xù)）兩個有序單鏈表的合并的算法實(shí)現(xiàn)（續(xù)）/*當(dāng)兩個表中均未處理完時(shí)，比較選擇將較小值結(jié)點(diǎn)插入到新表LC中。*/while(pa!=NULL&pb!=NULL)if(pa-datadata)r-next=pa;r=pa;pa=pa-next;elser-next=pb;r=pb;pb=pb-next;if(pa)/*若表LA未完，將表LA中后續(xù)元素鏈到新表LC表尾*/r-n

29、ext=pa;else/*否則將表LB中后續(xù)元素鏈到新表LC表尾*/r-next=pb;free(LB);return(LC);/*MergeLinkList*/10/1/2023462.3.3循環(huán)鏈表循環(huán)鏈表循環(huán)鏈表(CircularLinkedList)是一個首尾相接的鏈表。特點(diǎn)特點(diǎn)：將單鏈表最后一個結(jié)點(diǎn)的指針域由NULL改為指向頭結(jié)點(diǎn)或線性表中的第一個結(jié)點(diǎn)，就得到了單鏈形式的循環(huán)鏈表，并稱為循環(huán)單鏈表。在循環(huán)單鏈表中，表中所有結(jié)點(diǎn)被鏈在一個環(huán)上。帶頭結(jié)點(diǎn)循環(huán)單鏈表示意圖。10/1/202347帶頭結(jié)點(diǎn)的循環(huán)單鏈表示意圖帶頭結(jié)點(diǎn)的循環(huán)單鏈表示意圖 La1ai-1aian La1ai-1ai

30、an rear*(rear-next)*rear空鏈表帶頭頭結(jié)點(diǎn)的一般形式 帶尾尾結(jié)點(diǎn)的一般形式 10/1/202348循環(huán)單鏈表合并為一個循環(huán)單鏈表循環(huán)單鏈表合并為一個循環(huán)單鏈表已知已知：有兩個帶頭結(jié)點(diǎn)的循環(huán)單鏈表LA、LB，編寫一個算法，將兩個循環(huán)單鏈表合并為一個循環(huán)單鏈表，其頭指針為LA。算法思想算法思想：先找到兩個鏈表的尾，并分別由指針p、q指向它們，然后將第一個鏈表的尾與第二個表的第一個結(jié)點(diǎn)鏈接起來，并修改第二個表的尾Q，使它的鏈域指向第一個表的頭結(jié)點(diǎn)。10/1/202349循環(huán)單鏈表合并算法實(shí)現(xiàn)循環(huán)單鏈表合并算法實(shí)現(xiàn)LinkList merge_1(LinkList LA,Link

31、List LB)/*此算法將兩個鏈表的首尾連接起來*/Node*p,*q;p=LA;q=LB;while(p-next!=LA)p=p-next;/*找到表LA的表尾*/while(q-next!=LB)q=q-next;/*找到表LB的表尾*/q-next=LA;/*修改表LB 的尾指針，使之指向表LA 的頭結(jié)點(diǎn)*/p-next=LB-next;/*修改表LA的尾指針，使之指向表LB 中的第一個結(jié)點(diǎn)*/free(LB);return(LA);10/1/2023502.3.4雙向鏈表 雙向鏈表：雙向鏈表：在單鏈表的每個結(jié)點(diǎn)里再增加一個指向其前趨的指針域prior。這樣形成的鏈表中就有兩條方向不

32、同的鏈，我們稱之為雙雙(向向)鏈表鏈表(DoubleLinkedList)。雙向鏈表的結(jié)構(gòu)定義：typedef struct Dnode ElemType data；struct DNode*prior，*next；DNode,*DoubleList；10/1/202351雙鏈表的結(jié)構(gòu)定義雙鏈表的結(jié)構(gòu)定義l雙鏈表的結(jié)點(diǎn)結(jié)構(gòu) 后繼指針域prior data next前驅(qū)指針域數(shù)據(jù)域10/1/202352雙向循環(huán)鏈表示意圖雙向循環(huán)鏈表示意圖 a1 a2 a3LL空的雙向循環(huán)鏈表 非空的雙向循環(huán)鏈表 10/1/202353雙向鏈表的前插操作雙向鏈表的前插操作l算法描述：欲在雙向鏈表第i個結(jié)點(diǎn)之前插入

33、一個的新的結(jié)點(diǎn)，則指針的變化情況如圖所示。es bp a 10/1/202354雙向鏈表的前插操作算法實(shí)現(xiàn)雙向鏈表的前插操作算法實(shí)現(xiàn)void DlinkIns(DoubleList 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;算法演示連接。10/1/202355雙向鏈表的刪除操作雙向鏈表的刪除操作l算法描述：欲刪除雙向鏈表中的第i個結(jié)點(diǎn)，則指針的變化情況如圖所示。a b cp10/1/202356雙向鏈表的刪除操作算法實(shí)現(xiàn)雙向鏈表的刪除操作算法實(shí)現(xiàn)int