線性表的鏈?zhǔn)酱鎯?chǔ)

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

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

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

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

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

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

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

注意：

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

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

單鏈表定義的一般形式：由分別表示a1,a2,…,an,的n個(gè)結(jié)點(diǎn)依次相鏈構(gòu)成的鏈表，稱為線性表的鏈?zhǔn)酱鎯?chǔ)表示，由于此類鏈表的每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，故稱為單鏈表或線性鏈表。3.1.2單鏈表的數(shù)據(jù)定義任務(wù)1：舉例說明為什么要使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3.1.3靜態(tài)鏈的實(shí)現(xiàn)

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

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

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

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

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

2

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

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

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

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

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

structnode*next;/*指針域*/

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

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

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

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

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

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

//函數(shù)malloc分配一個(gè)類型為L(zhǎng)istNode的結(jié)點(diǎn)變量的空間,并將其首地址放入指針變量p中。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

if(p==NULL)returnOverFlow;/*分配失敗*//*數(shù)據(jù)域賦值*/strcpy(p->data.number,x.number);/*輸入序號(hào)*/strcpy(p->data.number,x.deliery_number);/*輸入配送編號(hào)*/strcpy(p->,);/*輸入姓名*/ strcpy(p->data.time,x.address);/*輸入地址*/ q=Head;while(q!=NULL&&k!=i-1)/*q指向第一個(gè)元素*/{q=q->next;k++;/*q取后繼元素的指針*/}if(q==NULL)printf(“序號(hào)錯(cuò)/n”);else{p->next=q->next;/*設(shè)置新結(jié)點(diǎn)的指針指向第i個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)*/q->next=p;/*設(shè)置第i個(gè)結(jié)點(diǎn)的指針域指向新結(jié)點(diǎn)*/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é)點(diǎn)的地址*/}returnNULL;/*未找到，返回空指針*/}【問題思考】（1）查找指定位置的元素如何設(shè)計(jì)。（2）結(jié)合實(shí)際應(yīng)用設(shè)計(jì)關(guān)鍵字字段。4.刪除指定元素刪除運(yùn)算是將表值為x的元素結(jié)點(diǎn)刪去。具體步驟是，找到ai-1的存儲(chǔ)位置q（因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)ai的存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn)ai-1的指針域next中）,令p-＞next指向ai的直接后繼結(jié)點(diǎn)（即把a(bǔ)i從鏈上摘下）,釋放結(jié)點(diǎn)ai的空間，將其歸還給"存儲(chǔ)池"。【算法3.4】刪除線性表中值為x的元素（刪除姓名字段，類型為字符數(shù)組）。

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

voidShow_LLinkList(LinkListHead)/*遍歷線性表*/{LNode*p;printf("\n");p=Head->next;/*p指向第一個(gè)結(jié)點(diǎn)（非頭結(jié)點(diǎn)）*/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é)點(diǎn)的地址*/}}

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

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

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

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

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

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

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

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

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

LinkListConnect(LinkListA,LinkListB)

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

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

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

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

B->next=p;//④

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

}

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

注意：

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

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

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

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

typedefstructdlistnode{

DataTypedata;

structdlistnode*prior,*next;

}DListNode;

typedefDListNode*DLinkList;

DLinkList