上傳人：2***

認(rèn)證信息

認(rèn)證類型：個人認(rèn)證

認(rèn)證主體：王**（實名認(rèn)證）

IP屬地：湖北

IP屬地：湖北 上傳時間：2023-02-01 格式：PPT 頁數(shù)：41 大?。?03KB 積分：28 舉報 版權(quán)申訴

第3章線性表的鏈?zhǔn)酱鎯χ饕R點：●線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)?！矜湵碇杏嘘P(guān)概念的含義，如頭結(jié)點、頭指針，首元結(jié)點、尾元結(jié)點的區(qū)別，以及循環(huán)鏈表、雙向鏈表的區(qū)別等?！窀鞣N鏈表上實現(xiàn)線性表各種操作的方法即有關(guān)算法的設(shè)計?！窠⒗脭?shù)據(jù)結(jié)構(gòu)知識進(jìn)行程序設(shè)計的思考方式。教學(xué)重點與難點重點：單鏈表結(jié)構(gòu)的各種基本算法，以及相關(guān)的時間性能分析。難點：設(shè)計鏈表結(jié)構(gòu)算法解決線性表相關(guān)實際問題。

思考問題：1、線性表鏈?zhǔn)浇Y(jié)構(gòu)特點2、如何利用線性表鏈?zhǔn)浇Y(jié)構(gòu)的知識解決實際問題，確定線性表鏈?zhǔn)浇Y(jié)構(gòu)的應(yīng)用題目。課程任務(wù)：線性表鏈?zhǔn)浇Y(jié)構(gòu)案例理解，完成課程任務(wù)設(shè)計。1、考核方式：課程報告和程序設(shè)計2、作業(yè)題目：依據(jù)選定的線性表結(jié)構(gòu)實用案例題目，設(shè)計完成課程任務(wù)。例如：課程任務(wù)實例“飲食中心訂餐管理系統(tǒng)”。3、作業(yè)要求：分析案例實現(xiàn)方法，結(jié)合案例設(shè)計自己的作業(yè)任務(wù)。3.1線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)3.1.1為什么要使用鏈?zhǔn)酱鎯Y(jié)構(gòu)【案例】：物流配送貨單管理。

圖3.1物流配送信息20087711劉佳佳哈爾濱20087707鄧玉瑩齊齊哈爾20087714魏秀婷牡丹江需求分析：1、不需要事先準(zhǔn)備一張足夠大的紙；2、每張小紙條寫完以后，把這張紙條排列到正確位置時，不會影響到其他的紙條；3、配送顧客完成后，把記錄該顧客信息的紙條抽出來銷毀（或存檔）。4、數(shù)據(jù)元素之間的邏輯關(guān)系為線性關(guān)系。3.1線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)問題思考：1、采用順序表存儲結(jié)構(gòu)存在的問題。

2、考慮采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的解決。3.1.2單鏈表的數(shù)據(jù)定義鏈表的存儲特點：

1、用一組任意的存儲單元來存放線性表的結(jié)點（這組存儲單元既可以是連續(xù)的，也可以是不連續(xù)的），例如三個配送顧客的配送數(shù)據(jù)信息的存儲空間是可以定義在任意的存儲區(qū)域。

2、鏈表中結(jié)點的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點間的邏輯關(guān)系，在存儲每個結(jié)點值的同時，還必須存儲指示其后繼結(jié)點的地址（或位置）信息，三個配送顧客的配送數(shù)據(jù)的邏輯次序與物理存儲次序不相同。200030001000劉佳佳配送信息3000鄧玉瑩配送信息1000魏秀婷配送信息0000Head(a)劉佳佳配送信息鄧玉瑩配送信息魏秀婷配送信息^Head2000(b)問題思考：總結(jié)鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點數(shù)據(jù)域指針域結(jié)點結(jié)構(gòu):數(shù)據(jù)域：存放結(jié)點數(shù)據(jù)信息值，例如配送顧客數(shù)據(jù)信息。

指針域：存放結(jié)點的直接后繼的地址（位置）。

注意：

（1）、鏈表通過每個結(jié)點的鏈域?qū)⒕€性表的n個結(jié)點按其邏輯順序鏈接在一起的。

（2）、每個結(jié)點只有一個鏈域的鏈表稱為單鏈表（SingleLinkedList）。

單鏈表定義的一般形式：由分別表示a1,a2,…,an,的n個結(jié)點依次相鏈構(gòu)成的鏈表，稱為線性表的鏈?zhǔn)酱鎯Ρ硎荆捎诖祟愭湵淼拿總€結(jié)點中只包含一個指針域，故稱為單鏈表或線性鏈表。3.1.2單鏈表的數(shù)據(jù)定義任務(wù)1：舉例說明為什么要使用鏈?zhǔn)酱鎯Y(jié)構(gòu)。3.1.3靜態(tài)鏈的實現(xiàn)

靜態(tài)鏈表特點：

●用數(shù)組來存儲元素的值和地址?！癯绦蜻\(yùn)算過程中，數(shù)組元素的個數(shù)固定不變。例3-1：物流配送貨單管理靜態(tài)鏈表存儲結(jié)構(gòu)設(shè)計（1）存儲結(jié)構(gòu)分析序號數(shù)據(jù)域指針域0鄧玉瑩配送信息11魏秀婷配送信息-12劉佳佳配送信息0………Head

2（2）存儲結(jié)構(gòu)C語言定義如下：定義顧客信息數(shù)據(jù)類型:typedefstruct{chardelivery_number[10];charname[10]; /*姓名*/charadress[20];/*地址*/}ElemType;

定義結(jié)點類型:typedefstructnode{ElemTypedata;/*數(shù)據(jù)域*/intnext;/*指針域*/}SLNode;

定義靜態(tài)單鏈表：SLNodeletter[100]；任務(wù)2：靜態(tài)鏈表存儲結(jié)構(gòu)舉例并采用C語言定義序號數(shù)據(jù)域指針域0鄧玉瑩配送信息11魏秀婷配送信息-12劉佳佳配送信息0………Head

2

使用鏈表的原因：第一，如果系統(tǒng)不能提供足夠大的地址連續(xù)的內(nèi)存空間時，可以考慮使用鏈表；第二，需要對線性表頻繁地進(jìn)行插入和刪除操作時，也考慮使用鏈表。3.1.4動態(tài)鏈表的實現(xiàn)動態(tài)鏈表結(jié)點定義一般形式：typedefstructnode{ElemTypedata;/*數(shù)據(jù)域*/structnode*next;/*指針域*/}LNode，*LinkList;劉佳佳配送信息鄧玉瑩配送信息魏秀婷配送信息^Head劉佳佳配送信息鄧玉瑩配送信息^Head劉佳佳配送信息^Headtypedefstructnode{ElemTypedata;/*數(shù)據(jù)域*/structnode*next;/*指針域*/}LNode，*LinkList;（1）.定義元素數(shù)據(jù)類型typedefstruct{charnumber[7];/*序號*/chardelivery_number[10];/*配送編號*/charname[10];/*姓名*/charaddress[20];/*地址*/}ElemType;3.1.4動態(tài)鏈表的實現(xiàn)例3-2：物流配送貨單管理動態(tài)鏈表存儲結(jié)構(gòu)設(shè)計1．存儲結(jié)構(gòu)分析：在C語言程序設(shè)計中，可以用malloc函數(shù)申請動態(tài)變量（存儲空間），用free釋放變量（存儲空間）。動態(tài)鏈表中的結(jié)點是以變量形式申請或者釋放的。2.顧客信息的動態(tài)鏈類型：typedefstructnode{ElemTypedata;/*數(shù)據(jù)域*/structnode*next;/*指針域*/}LNode，*LinkList;3.1.4動態(tài)鏈表的實現(xiàn)C語言知識回顧：typedefstructnodeLNode;typedefstructnode*LinkList;等價于Structnode{ElemTypedata;/*數(shù)據(jù)域*/structnode*next;/*指針域*/};定義變量：Structnodex,*Head;/*結(jié)點變量x，結(jié)點指針變量Head

*/或LNodex,*Head;/*結(jié)點變量x，結(jié)點指針變量Head

*/或LinkListHead;/*結(jié)點指針變量Head

*/（1）.定義元素數(shù)據(jù)類型typedefstruct{charnumber[7];/*序號*/chardelivery_number[10];/*配送編號*/charname[10];/*姓名*/charaddress[10];/*地址*/}ElemType;劉佳佳配送信息鄧玉瑩配送信息魏秀婷配送信息^Headtypedefstructnode

{ElemTypedata;/*數(shù)據(jù)域*/

structnode*next;/*指針域*/

}LNode,*LinkList;3.C語言描述說明

（1）LinkList和LNode*是不同名字的同一個指針類型（命名的不同是為了概念上更明確）。

（2）LinkList類型的指針變量head表示它是單鏈表的頭指針。

（3）LNode*類型的指針變量p表示它是指向某一結(jié)點的指針。

為了便于描述，下面給出有關(guān)鏈表的術(shù)語。在一個鏈表中稱表頭結(jié)點指針為頭指針。由于從頭指針出發(fā)可以搜索到鏈表中各結(jié)點，因而常用頭指針作為鏈表的名稱。4.定義鏈表變量兩種定義形式：（1）LinkListHead；（2）LNode*Head；（2）.定義鏈表及結(jié)點類型【知識拓展】：指針變量和結(jié)點變量的關(guān)系（1）生成結(jié)點變量的標(biāo)準(zhǔn)函數(shù)

p=(LNode*)malloc(sizeof(LNode))；

//函數(shù)malloc分配一個類型為ListNode的結(jié)點變量的空間,并將其首地址放入指針變量p中。

（2）釋放結(jié)點變量空間的標(biāo)準(zhǔn)函數(shù)

free(p)；//釋放p所指的結(jié)點變量空間。

（3）結(jié)點分量的訪問

利用結(jié)點變量的名字*p訪問結(jié)點分量

方法一：(*p).data和(*p).next

方法二：p-﹥data和p-﹥next

（4）指針變量p和結(jié)點變量*p的關(guān)系

指針變量p的值——結(jié)點地址

結(jié)點變量*p的值——結(jié)點內(nèi)容

(*p).data的值——p指針?biāo)附Y(jié)點的data域的值

(*p).next的值——*p后繼結(jié)點的地址

*((*p).next)——*p后繼結(jié)點頭結(jié)點及作用：頭結(jié)點是在鏈表的開始結(jié)點之前附加一個結(jié)點。它具有兩個優(yōu)點:

（1）由于開始結(jié)點的位置被存放在頭結(jié)點的指針域中,所以在鏈表的第一個位置上的操作就和在表的其它位置上操作一致,無須進(jìn)行特殊處理;

（2）無論鏈表是否為空，其頭指針都是指向頭結(jié)點的非空指針（空表中頭結(jié)點的指針域空），因此空表和非空表的處理也就統(tǒng)一了。注意：

頭結(jié)點數(shù)據(jù)域的陰影表示該部分不存儲信息。在有的應(yīng)用中可用于存放表長等附加信息。3.2基于單鏈表的算法實現(xiàn)【例3-3】：以“物流配送貨單管理”任務(wù)為例，采用帶頭結(jié)點的動態(tài)鏈表設(shè)計數(shù)據(jù)結(jié)構(gòu)。單鏈表類型定義：（1）定義元素數(shù)據(jù)類型typedefstruct{charnumber[7];/*序號*/chardelivery_number[10];/*配送編號*/charname[10];/*姓名*/charaddress[20];/*地址*/}ElemType;（2）定義鏈表及結(jié)點類型typedefstructnode{ElemTypedata;/*數(shù)據(jù)域*/structnode*next;/*指針域*/}LNode,*LinkList;3.2基于單鏈表的算法實現(xiàn)3.2.1單鏈表的基本算法實現(xiàn)1．構(gòu)造一個空表

intInit_LinkList(LinkListHead)/*構(gòu)造一個空表*/{LinkListp;p=(LinkList)malloc(sizeof(LNode));/*分配一個結(jié)點*/if(p==NULL)returnOverFlow;/*分配失敗*/Head=p;/*頭指針指向新結(jié)點*/returnOK;/*構(gòu)造成功，返回*/}子函數(shù)參數(shù)說明：typedefstructnode{ElemTypedata;/*數(shù)據(jù)域*/structnode*next;/*指針域*/}LNode，*LinkList

intInsertL_i(LinkListHead,ElemTypex,inti)/*在第i個結(jié)點后面插入*/{LNode*p,*q;intk=0;p=(LinkList)malloc(sizeof(Node));/*分配一個結(jié)點*/

if(p==NULL)returnOverFlow;/*分配失敗*//*數(shù)據(jù)域賦值*/strcpy(p->data.number,x.number);/*輸入序號*/strcpy(p->data.number,x.deliery_number);/*輸入配送編號*/strcpy(p->,);/*輸入姓名*/ strcpy(p->data.time,x.address);/*輸入地址*/ q=Head;while(q!=NULL&&k!=i-1)/*q指向第一個元素*/{q=q->next;k++;/*q取后繼元素的指針*/}if(q==NULL)printf(“序號錯/n”);else{p->next=q->next;/*設(shè)置新結(jié)點的指針指向第i個結(jié)點的后繼結(jié)點*/q->next=p;/*設(shè)置第i個結(jié)點的指針域指向新結(jié)點*/returnOK;/*插入成功，返回*/}returnError;/*插入未成功*/}【算法3.3】查找指定元素x（查找姓名字段，類型為字符數(shù)組）。

LNode*Location_LLinkList(LinkListHead,char*name)/*查找指定關(guān)鍵字信息*/{Node*p;p=Head->next;while(p!=NULL)/*未到鏈尾*/{/*關(guān)鍵字姓名相等*/if(strcmp(p->,name)==0)returnp;/*找到返回指針*/elsep=p->next;/*p取后繼結(jié)點的地址*/}returnNULL;/*未找到，返回空指針*/}【問題思考】（1）查找指定位置的元素如何設(shè)計。（2）結(jié)合實際應(yīng)用設(shè)計關(guān)鍵字字段。4.刪除指定元素刪除運(yùn)算是將表值為x的元素結(jié)點刪去。具體步驟是，找到ai-1的存儲位置q（因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai-1的指針域next中）,令p-＞next指向ai的直接后繼結(jié)點（即把a(bǔ)i從鏈上摘下）,釋放結(jié)點ai的空間，將其歸還給"存儲池"?！舅惴?.4】刪除線性表中值為x的元素（刪除姓名字段，類型為字符數(shù)組）。

intDelete_LLinkList(LinkListHead,char*name){Node*p,*q;q=Head;/*q指向頭結(jié)點*/p=q->next;/*p取其后繼結(jié)點的地址*/while(p!=NULL)/*p不為空*/{if(strcmp(p->,name)==0)/*找到被刪除元素*/{q->next=p->next;/*q所指結(jié)點的指針設(shè)置為p所指結(jié)點的指針*/free(p);/*釋放p所指結(jié)點*/returnOK;/*刪除成功*/}q=p;p=p->next;/*q取p的值，p取其后繼結(jié)點的地址*/}returnError;/*刪除失敗*/}【問題思考】（1）刪除結(jié)點的關(guān)鍵字設(shè)計。（2）刪除指定位置的元素如何設(shè)計。5.遍歷帶表頭結(jié)點的單循環(huán)鏈表【算法3.5】遍歷帶表頭結(jié)點的單循環(huán)鏈表

voidShow_LLinkList(LinkListHead)/*遍歷線性表*/{LNode*p;printf("\n");p=Head->next;/*p指向第一個結(jié)點（非頭結(jié)點）*/if(p==NULL)printf("\n空表！NULL");while(p!=NULL)/*未結(jié)束遍歷*/{printf("%s%s%s%s\n",p->data.number,p->data.deliery_number,p->,p->address);/*輸出數(shù)據(jù)*/p=p->next;/*p取后繼結(jié)點的地址*/}}

說明：顯示結(jié)點數(shù)據(jù)為分別輸出數(shù)據(jù)域各個成員項的值。6.清空帶表頭結(jié)點的單循環(huán)鏈表【算法3.6】清空帶表頭結(jié)點的單循環(huán)鏈表。

voidSetNull_LLinkList(LinkListHead)/*清空線性表*/{LNode*p,*q;q=Head;p=q->next;/*p取頭指針*/while(p!=NULL){q=p;/*q指向p的前驅(qū)結(jié)點*/p=p->next;/*p指向其后繼結(jié)點*/free(q);}Head->next=NULL;/*設(shè)置頭結(jié)點/*/}

7.計算帶表頭結(jié)點的單循環(huán)鏈表的長度【算法3.7】計算帶表頭結(jié)點的單循環(huán)鏈表的長度。

intLength_LLinkList(LinkListHead)/*計算線性表的長度*/{LNode*p;intsum=0;p=Head->next;/*p取頭指針的后繼*/while(p!=NULL)/*p與Head不相等*/{sum++;/*累加器加1*/p=p->next;/*p指向其后繼結(jié)點*/}returnsum;}3.2.2單鏈表中插入運(yùn)算的進(jìn)一步討論1.尾插【算法3.8】插入一個元素（在最后一個結(jié)點之后插入，帶表頭結(jié)點的單鏈表）

intInsertL_Last(LinkListHead,ElemTypex)/*在最后一個結(jié)點后面插入*/{LNode*p,*q;intk=0;p=(LinkList)malloc(sizeof(Node));/*分配一個結(jié)點*/if(p==NULL)returnOverFlow;/*分配失敗*//*數(shù)據(jù)域賦值*/strcpy(p->data.number,x.number);/*輸入序號*/strcpy(p->data.number,x.deliery_number);/*輸入配送編號*/strcpy(p->,);/*輸入姓名*/ strcpy(p->data.time,x.address);/*輸入地址*/p->next=NULL；

q=Head;while(q!=NULL)/*q指向最后一個元素*/q=q->next;/*q取后繼元素的指針*/q->next=p;/*設(shè)置第i個結(jié)點的指針域指向新結(jié)點*/returnOK;}2.頭插【算法3.9】插入一個元素（在頭結(jié)點之后插入，帶表頭結(jié)點的單鏈表）

intInsertL_First(LinkListHead,ElemTypex)/*在頭結(jié)點后面插入*/{LNode*p;p=(LinkList)malloc(sizeof(Node));/*分配一個結(jié)點*/if(p==NULL)returnOverFlow;/*分配失敗*//*數(shù)據(jù)域賦值*/strcpy(p->data.number,x.number);/*輸入序號*/strcpy(p->data.number,x.deliery_number);/*輸入配送編號*/strcpy(p->,);/*輸入姓名*/ strcpy(p->data.time,x.address);/*輸入地址*/p->next=Head->next;Head->next=p;returnOK;}【例3-3】“物流貨單配送管理”的實現(xiàn)問題描述物流公司根據(jù)配貨單配送給顧客。功能主要包括插入配貨信息、退訂某人貨單、瀏覽全部貨單、統(tǒng)計全部貨單數(shù)量等功能。3.2.3帶表頭結(jié)點的單鏈表應(yīng)用舉例基本要求由于每天配送顧客數(shù)量不確定，并且隨時都有退單的可能性，存在頻繁的插入與刪除操作。因此采用帶有頭結(jié)點的單鏈表數(shù)據(jù)結(jié)構(gòu)。模塊劃分①建立帶頭結(jié)點的單鏈表Init_LLinkList，該模塊完成初始化功能。②插入貨單配送信息服務(wù)InsertL_Last,該模塊將新的配送信息插入到單鏈表的尾部。③退訂貨單服務(wù)Delete_LLinkList,該模塊根據(jù)輸入配送顧客的姓名，首先在鏈表中進(jìn)行查找，若找到相應(yīng)結(jié)點，則將其從物流配貨單鏈表中摘下。若沒有找到相應(yīng)結(jié)點，則給出不存在該顧客配送信息。④查找某人的貨單信息Location_LinkList，找出指定姓名的顧客配送信息。⑤顯示物流貨單配送信息服務(wù)Show_LinkList，該模塊將單鏈表中所有的結(jié)點元素數(shù)據(jù)信息顯示出來。⑥統(tǒng)計配送顧客數(shù)量Length_LinkList，該模塊計算單鏈表結(jié)點數(shù)量。⑦清除單鏈表模塊SetNull_LinkList，將所使用的單鏈表歸還系統(tǒng)。⑧主函數(shù)main，構(gòu)造僅有頭結(jié)點的物流配送貨單單鏈表，調(diào)用Init_LLinkList建立貨單配送信息，顯示貨單顧客配送信息、退訂貨單配送、統(tǒng)計全部預(yù)定數(shù)量、退出菜單等功能。據(jù)（對菜單的）相應(yīng)選擇調(diào)用模塊或終止程序運(yùn)行。程序設(shè)計#include"stdio.h“#defineMaxSize20#defineOverFlow-1#defineOK1#defineError-1typedefstruct/*定義元素數(shù)據(jù)類型*/{charnumber[7];/*序號*/chardeliery_number;/*配送編號*/charname[10]; /*姓名*/charaddress[20];/*時間*/}ElemType;typedefstructnode/*定義鏈表及結(jié)點類型*/{ElemTypedata;/*數(shù)據(jù)域*/structnode*next;/*指針域*/}LNode,*LinkList;voidmain(){LinkListHead;inti; LNode*loca;ElemTypex;charname_x[10];Init_LinkList(Head);do{printf("\n");printf(“1---登記一個配送數(shù)據(jù)(Insert)\n");printf(“2---查詢指定配送數(shù)據(jù)(Locate)\n");printf(“3---刪除一個配送數(shù)據(jù)(Delete\n");printf(“4---顯示所有配送數(shù)據(jù)(Show)\n");printf(“5---統(tǒng)計配送數(shù)量(Length)\n");printf("6---退出\n");scanf("%d",&i);switch(i){case1:printf("Pleaseenternumber:");/*輸入序號*/scanf("%s",x.number);printf(“Pleaseenterdeliery_number:”);/*輸入配送編號*/scanf("%s",x.deliery_number);printf("Pleaseentername:");/*輸入姓名*/scanf("%s",);printf(“Pleaseenteraddress:”);/*輸入地址*/scanf("%s",x.time);if(Insert_Last(Head,x)!=OK)printf("插入失敗\n");break;case2:printf(“請輸入要查詢的配送顧客姓名research：\n");printf("Pleaseentername:");/*輸入姓名*/scanf("%s",name_x);loca=Location_LinkList(Head,name_x);if(loca!=NULL)printf(“查找成功(Found)!");elseprintf(“查找失敗!Fault，該顧客不存在！");break;case3:printf(“請輸入要退單的信息delete\n");printf("Pleaseentername:");/*輸入姓名*/scanf("%s",name_x);if(Delete_LinkList(Head,name_x)==OK)printf(“撤銷配送\n");elseprintf(“沒有找到制定顧客配送信息Fault\n");break;case4:Show_LinkList(Head);break;case5:printf(“貨單數(shù)量是amount%d!\n",Length_LinkList(Head));break;case6:break;default:printf("錯誤選擇！Error請重選");break;}}while(i!=6);SetNull_LinkList(Head);/*清空線性表*/}3.3鏈?zhǔn)酱鎯Φ钠渌椒?/p>

3.3.1鏈?zhǔn)酱鎯Y(jié)構(gòu)循環(huán)鏈表特點:是表中最后一個結(jié)點的指針不再是空，而是指向頭結(jié)點（帶頭結(jié)點的單鏈表）或第一個結(jié)點（不帶頭結(jié)點的單鏈表），整個鏈表形成一個環(huán)，這樣從表中任一結(jié)點出發(fā)都可找到其它的結(jié)點。注意：判斷空鏈表的條件是head==head->next;a1a2…an帶頭結(jié)點的循環(huán)單鏈表(a)空循環(huán)鏈表(b)非空循環(huán)鏈表headhead【例3-4】在鏈表上實現(xiàn)將兩個線性表（a1，a2，…，an）和（b1，b2，…，bm）連接成一個線性表（a1，…，an，b1，…bm）的運(yùn)算。

分析：若在單鏈表或頭指針表示的單循環(huán)表上做這種鏈接操作，都需要遍歷第一個鏈表，找到結(jié)點an，然后將結(jié)點b1鏈到an的后面，其執(zhí)行時間是O(n)。若在尾指針表示的單循環(huán)鏈表上實現(xiàn)，則只需修改指針，無須遍歷，其執(zhí)行時間是O(1)。算法設(shè)計：

LinkListConnect(LinkListA,LinkListB)

{//假設(shè)A，B為非空循環(huán)鏈表的尾指針

LinkListp=A->next;//①保存A表的頭結(jié)點位置

A->next=B->next->next;//②B表的開始結(jié)點鏈接到A表尾

free(B->next);//③釋放B表的頭結(jié)點

B->next=p;//④

returnB;//返回新循環(huán)鏈表的尾指針

}

1、雙向鏈表（DoubleLinkedList）雙（向）鏈表中有兩條方向不同的鏈，即每個結(jié)點中除next域存放后繼結(jié)點地址外，還增加一個指向其直接前趨的指針域prior。

注意：

①雙鏈表由頭指針head惟一確定的。

②帶頭結(jié)點的雙鏈表的某些運(yùn)算變得方便。

③將頭結(jié)點和尾結(jié)點鏈接起來，為雙（向）循環(huán)鏈表。3.3.2鏈?zhǔn)酱鎯Y(jié)構(gòu)雙鏈表2、雙向鏈表的結(jié)點結(jié)構(gòu)和C語言形式描述

①結(jié)點結(jié)構(gòu)②形式描述

typedefstructdlistnode{

DataTypedata;

structdlistnode*prior,*next;

}DListNode;

typedefDListNode*DLinkList;

DLinkList