《數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（C語言版）》課件第2章 線性表

第2章線性表本章主要介紹下列內(nèi)容線性表的定義和基本操作線性表的順序存儲結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表的應(yīng)用舉例本章目錄2.1線性表的基本概念1

2.2順序表2

2.3鏈表32.4線性表的應(yīng)用舉例4

2.5本章小結(jié)5結(jié)束2.1線性表的基本概念2.1.1線性表的定義2.1.2線性表的基本操作返回到總目錄2.1.1

線性表的定義1.線性表的定義線性表是具有相同數(shù)據(jù)類型的n（n>=0）個(gè)數(shù)據(jù)元素的有限序列，通常記為：（a1，a2，…ai-1，ai，ai+1，…an）

其中n為表長，當(dāng)n=0時(shí)稱為空表。

在線性表中相鄰元素之間存在著順序關(guān)系。如對于元素ai

而言，ai-1

稱為

ai

的直接前驅(qū)，ai+1

稱為

ai

的直接后繼。返回到本節(jié)目錄2.線性表的特點(diǎn)（1）有且僅有一個(gè)開始結(jié)點(diǎn)（a1），它沒有直接前驅(qū)；（2）有且僅有一個(gè)終端結(jié)點(diǎn)（an），它沒有直接后繼；（3）除了開始結(jié)點(diǎn)和終端結(jié)點(diǎn)以外，其余的結(jié)點(diǎn)都有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼。2.1.1

線性表的定義返回到本節(jié)目錄2.1.2

線性表的基本操作數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是定義在邏輯結(jié)構(gòu)層次上的，而運(yùn)算的具體實(shí)現(xiàn)是建立在存儲結(jié)構(gòu)上的。下面定義的線性表的基本操作僅是定義在邏輯結(jié)構(gòu)上的，每一個(gè)操作的具體實(shí)現(xiàn)只有在確定了線性表的存儲結(jié)構(gòu)之后才能完成。線性表的基本操作有：（1）初始化線性表InitList(L)。其作用是建立一個(gè)空表L（即建立線性表的構(gòu)架，但不包含任何數(shù)據(jù)元素）。返回到本節(jié)目錄（2）求線性表的長度GetLength(L)。其作用是返回線性表L的長度（即所含數(shù)據(jù)元素的個(gè)數(shù)）。（3）求線性表中第i個(gè)元素GetElem(L,i,x)。其作用是在1≤i≤GetLength(L)返回成功，并用x存儲線性表L的第i個(gè)元素的值。（4）按值查找操作Locate(L,x)。在線性表L查找一個(gè)與給定值x相等的數(shù)據(jù)元素，其作用是若存在一個(gè)或多個(gè)與x相等的數(shù)據(jù)元素，則返回的元素所在位置的最小值或地址值；否則返回0或NULL值。2.1.2

線性表的基本操作返回到本節(jié)目錄（5）插入操作InsElem(L,i,x)。其作用是在線性表L的第i個(gè)位置上插入一個(gè)值為

x的新元素，使線性表L由（a1，a2，…ai-1，ai，ai+1，…an）變?yōu)椋╝1，a2，…ai-1，x，ai，ai+1，…an）。其中1≤i≤GetLength(L)+1。（6）刪除操作DelElem(L,i,x)。其作用是刪除線性表L的第i個(gè)位置的數(shù)據(jù)元素并用x將其存儲，使線性表L由（a1，a2，…ai-1，ai，ai+1，…an）變?yōu)椋╝1，a2，…ai-1，ai+1，…an）。其中1≤i≤GetLength(L)。（7）輸出元素值DispList(L)。其作用是依次掃描線性表L，并輸出各元素的值。2.1.2

線性表的基本操作返回到本節(jié)目錄2.2順序表2.2.1順序表2.2.2順序表的基本操作實(shí)現(xiàn)返回到總目錄1.順序表的定義數(shù)據(jù)結(jié)構(gòu)在內(nèi)存中的表示通常有兩種形式，即順序存儲表示和鏈?zhǔn)酱鎯Ρ硎?。線性表的順序存儲表示又稱為順序表。線性表的順序存儲是指用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，我們把用這種存儲形式存儲的線性表稱為順序表。假設(shè)順序表(a1，a2，…ai-1，ai，ai+1，…an)，每個(gè)數(shù)據(jù)元素占用d個(gè)存儲單元，則元素ai的存儲位置為：Loc(ai)=Loc(a1)+(i-1)×d1≤i≤n2.2.1順序表返回到本節(jié)目錄其中，Loc(a1)是順序表第一個(gè)元素a1的存儲位置，通稱為順序表的起始地址。順序存儲結(jié)構(gòu)示意圖如圖2-1所示。順序表的存儲特點(diǎn)：（1）順序表的邏輯順序和物理順序是一致的。（2）順序表中任意一個(gè)數(shù)據(jù)元素都可以隨機(jī)存取，所以順序表是一種隨機(jī)存取的存儲結(jié)構(gòu)。2.2.1順序表返回到本節(jié)目錄2.順序表的類型定義#defineMAXLEN100/*定義常量MAXLEN為100表示存儲空間總量*/#defineOK/*定義常量OK為1表示成功*/#defineERROR0/*定義常量ERROR為0表示失敗*/#defineOVER-1/*定義常量OVER為-1表示結(jié)束*/typedefintElemType;/*定義ElemType為int類型*/typedefstruct/*順序表存儲類型*/{ElemTypedata[MAXLEN];/*存放線性表的數(shù)組*/intLength;/*Length是順序表的長度*/}SeqList;2.2.1順序表返回到本節(jié)目錄2.2.2順序表的基本操作實(shí)現(xiàn)1．順序表的初始化順序表的初始化即構(gòu)造一個(gè)空順序表L，將表L的實(shí)際長度置0，算法描述見算法2.1。算法2.1

voidInitList(SeqList*L)

{L->Length=0;

/*初始的化順序表為空*/}返回到本節(jié)目錄2．順序表的建立初始化順序表后向表中輸入n個(gè)元素建立表L，算法描述見算法2.2。算法2.2voidCreateList(SeqList*L,intn){inti;printf("請輸入各個(gè)元素值：\n");for(i=0;i<n;i++)scanf("%d",&L->data[i]);L->Length=i;}2.2.2順序表的基本操作實(shí)現(xiàn)返回到本節(jié)目錄3．求順序表的長度操作返回順序表L的Length值，算法描述見算法2.3。算法2.3intGetLength(SeqList*L){returnL->Length;}

4．查找操作順序表的查找分為按值與按序號查找，下面將分別介紹這兩種方法的實(shí)現(xiàn)，讀者可根據(jù)具體的問題相應(yīng)選擇所需的查找方法。2.2.2順序表的基本操作實(shí)現(xiàn)返回到本節(jié)目錄（1）按號查找查找順序表中第i個(gè)元素的值，在i無效時(shí)返回出錯(cuò)，有效時(shí)返回成功，并用x存儲第i個(gè)元素的值，算法描述見算法2.4。算法2.4intGetElem(SeqList*L,inti,ElemType*x){if(i<1||i>L->Length)returnERROR;else{*x=L->data[i-1];returnOK;}}2.2.2順序表的基本操作實(shí)現(xiàn)返回到本節(jié)目錄2）按值查找操作順序表中的按值查找是指在順序表中查找與給定值x相等的數(shù)據(jù)元素的所在位置，算法描述見算法2.5。算法2.5intLocate(SeqList*L,ElemTypex){

inti=0;while(i<=L->Length&&L->data[i]!=x)i++;if(i>L->Length)

returnERROR;elsereturni+1;

/*返回的是元素位置*/}2.2.2順序表的基本操作實(shí)現(xiàn)返回到本節(jié)目錄2.2.2順序表的基本操作實(shí)現(xiàn)5．插入操作線性表的插入是指在表的第i個(gè)位置上插入一個(gè)值為x的新元素，插入后使原表長增1，原順序表如圖2-2所示。返回到本節(jié)目錄5．插入操作步驟如下：

(1)將an～ai之間的所有結(jié)點(diǎn)依次后移，為新元素讓出第i個(gè)位置，如圖2-3所示。返回到本節(jié)目錄5．插入操作步驟如下：(2)將新結(jié)點(diǎn)x插入到第i個(gè)位置，如圖2-4所示。(3)順序表的長度增1，插入成功，并返回，算法描述見算法2.6。返回到本節(jié)目錄5．插入操作算法2.6int

InsElem(SeqList*L,inti,ElemTypex){intj;

if(L->Length>=MAXLEN){printf("順序表已滿！");returnOVER;

/*表滿，不能插入*/}if(i<1||i>L->Length+1)

/*檢查給定的插入位置的正確性*/{printf("插入位置出錯(cuò)！");returnERROR;}if(i==L->Length+1){L->data[i-1]=x;L->Length++;returnOK;/*插入的位置為表尾，則不需移動直接插入即可*/}for(j=L->Length-1;j>=i-1;j--)

/*結(jié)點(diǎn)移動*/L->data[j+1]=L->data[j];L->data[i-1]=x;/*新元素插入*/L->Length++;/*順序表長度增1*/returnOK;

/*插入成功，返回*/}返回到本節(jié)目錄5．插入操作插入算法的時(shí)間性能分析：順序表插入操作大約需移動表中一半數(shù)據(jù)元素，其時(shí)間復(fù)雜度為Ｏ(n)。返回到本節(jié)目錄2.2.2順序表的基本操作實(shí)現(xiàn)6.刪除操作

線性表的刪除操作是指將第i個(gè)元素從順序表中去掉，刪除后順序表表長減1，原順序表如圖2-5所示。返回到本節(jié)目錄6.刪除操作步驟如下：(1)將要?jiǎng)h除的元素值賦給指針變量*x，如圖2-6所示返回到本節(jié)目錄6.刪除操作步驟如下：(2)將ai+1～an之間的結(jié)點(diǎn)依次順序向前移動，如圖2-7所示。(3)順序表的長度減1，刪除成功，并返回，算法描述見算法2.7。返回到本節(jié)目錄6.刪除操作算法2.7intDelElem(SeqList*L,inti,ElemType*x)

{int

j;if(L->Length==0){printf("順序表為空！");returnERROR;

/*表空，不能刪除*/}if(i<1||i>L->Length)

/*檢查是否空表及刪除位置的合法性*/{printf("不存在第i個(gè)元素");returnERROR;}*x=L->data[i-1];/*用指針變量*x返回刪除的元素值*/for(j=i;j<=L->Length-1;j++)

/*結(jié)點(diǎn)移動*/L->data[j-1]=L->data[j];L->Length--;

/*順序表長度減1*/returnOK;

/*刪除成功，返回*/}返回到本節(jié)目錄6.刪除操作刪除算法的時(shí)間性能分析：與插入操作相同，其時(shí)間主要消耗在了移動表中元素上，（大約需要移動表中一半的元素），顯然該算法的時(shí)間復(fù)雜度為Ｏ(n)。返回到本節(jié)目錄2.2.2順序表的基本操作實(shí)現(xiàn)7．順序表的輸出操作掃描順序表L，輸出各元素的值，算法描述見算法2.8。算法2.8voidDispList(SeqList*L){inti;for(i=0;i<L->Length;i++)printf("%5d",L->data[i]);}返回到本節(jié)目錄2.3鏈表2.3.1單鏈表2.3.2單鏈表的基本操作實(shí)現(xiàn)2.3.3鏈表的變形返回到總目錄2.3.1單鏈表1.單鏈表的定義線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指用一組任意的存儲單元（可以連續(xù)，也可以不連續(xù)）存儲線性表中的數(shù)據(jù)元素。為了反映數(shù)據(jù)元素之間的邏輯關(guān)系，對于每個(gè)數(shù)據(jù)元素不僅要表示它的具體內(nèi)容，還要附加一個(gè)表示它的直接后繼元素存儲位置的信息，這樣構(gòu)成的鏈表稱為線性單向鏈接表，簡稱單鏈表，其結(jié)點(diǎn)結(jié)構(gòu)如圖2-8所示。數(shù)據(jù)域后繼指針域datanext圖2-8單鏈表的結(jié)點(diǎn)示意圖其中，data部分稱為數(shù)據(jù)域，用于存儲一個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)Node）的信息。next部分稱為指針域，用于存儲其直接后繼的存儲地址的信息。返回到本節(jié)目錄2.3.1單鏈表單鏈表分為帶頭結(jié)點(diǎn)（其next域指向鏈表第一個(gè)結(jié)點(diǎn)的存儲地址）和不帶頭結(jié)點(diǎn)兩種類型。在許多情況下，帶頭結(jié)點(diǎn)的鏈表中每個(gè)結(jié)點(diǎn)的存儲地址均放在其前驅(qū)結(jié)點(diǎn)中，這樣算法對所有的結(jié)點(diǎn)處理可一致化，因此，本節(jié)討論的單鏈表均指帶頭結(jié)點(diǎn)的單鏈表。帶頭結(jié)點(diǎn)的單鏈表如圖2-9所示。

圖2-9帶頭結(jié)點(diǎn)的單鏈表其中，頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲任何信息，也可以存放特殊的信息；頭結(jié)點(diǎn)的指針域存儲鏈表中第一個(gè)結(jié)點(diǎn)的地址。當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭眨碞ULL或用∧表示），則此表為空表。在非空表中，當(dāng)某個(gè)結(jié)點(diǎn)的指針域?yàn)榭?，表示它為鏈表的最后一個(gè)結(jié)點(diǎn)。返回到本節(jié)目錄2.3.1單鏈表鏈?zhǔn)酱鎯μ攸c(diǎn)：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過指針來表示元素之間的邏輯關(guān)系，不再有邏輯順序與物理存儲順序一致的特點(diǎn)，是非順序存儲結(jié)構(gòu)。返回到本節(jié)目錄2.3.1單鏈表2.單鏈表的類型定義#defineOK1#defineERROR0#defineOVER-1typedefcharElemType;/*定義ElemType為char類型*/typedefstructnode/*單鏈表存儲類型*/{ElemTypedata;/*定義結(jié)點(diǎn)的數(shù)據(jù)域*/structnode*next;/*定義結(jié)點(diǎn)的指針域*/}LinkList;返回到本節(jié)目錄2.3.2單鏈表的基本操作實(shí)現(xiàn)1.單鏈表的初始化單鏈表的初始化即構(gòu)造一個(gè)僅包含頭結(jié)點(diǎn)的空單鏈表L，算法描述見算法2.9。算法2.9

LinkList*InitList(){/*申請一塊LinkList類型的存儲單元的操作，并將其地址賦值給頭指針變量L*/LinkList*L;

L=(LinkList*)malloc(sizeof(LinkList));L->next=NULL;returnL;/*頭結(jié)點(diǎn)L指針域?yàn)榭?，表示空鏈?/}返回到本節(jié)目錄2.3.2單鏈表的基本操作實(shí)現(xiàn)2．單鏈表的建立（1）頭插法建表在初始化鏈表后，每讀取有效的數(shù)據(jù)都為其生成新結(jié)點(diǎn)s，并將讀取的數(shù)據(jù)存放到新結(jié)點(diǎn)s的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表L的表頭上，直到循環(huán)結(jié)束為止，算法描述見算法2.10。算法2.10voidCreateList(LinkList*L){LinkList*s;charch;while((ch=getchar())!='#')/*判斷輸入數(shù)據(jù)是否有效*/{s=(LinkList*)malloc(sizeof(LinkList));/*生成新結(jié)點(diǎn)*/s->data=ch;/*將數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域*/s->next=L->next;/*將新結(jié)點(diǎn)的指針域存放頭結(jié)點(diǎn)的指針域*/L->next=s;/*將新結(jié)點(diǎn)插入頭結(jié)點(diǎn)之后*/}}返回到本節(jié)目錄2.3.2單鏈表的基本操作實(shí)現(xiàn)（2）尾插法建表頭插法建立鏈表雖然算法簡單易理解，但生成的鏈表中結(jié)點(diǎn)的次序和原輸入的次序相反。而尾插法建立鏈表可實(shí)現(xiàn)次序的一致，該算法依舊在初始化鏈表后，但需增加一個(gè)尾指針last，使其指向當(dāng)前鏈表的尾結(jié)點(diǎn)，算法描述見算法2.11。算法2.11voidCreateList(LinkList*L){LinkList*s,*last;charch;last=L;/*last始終指向尾結(jié)點(diǎn)，開始時(shí)指向頭結(jié)點(diǎn)*/while((ch=getchar())!='#')/*判斷輸入數(shù)據(jù)是否有效*/{s=(LinkList*)malloc(sizeof(LinkList));/*生成新結(jié)點(diǎn)*/s->data=ch;/*將數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域*/s->next=NULL;/*將新結(jié)點(diǎn)的指針域?yàn)榭?/last->next=s;/*將新結(jié)點(diǎn)插入表尾*/last=s;/*將last指針指向表尾結(jié)點(diǎn)*/}}返回到本節(jié)目錄2.3.2單鏈表的基本操作實(shí)現(xiàn)3．求單鏈表的長度求長度就是求單鏈表中數(shù)據(jù)元素的個(gè)數(shù)。求帶頭結(jié)點(diǎn)的單鏈表L的長度需設(shè)一個(gè)動態(tài)指針p指向頭結(jié)點(diǎn)，計(jì)數(shù)器j初始值為0，p指針?biāo)附Y(jié)點(diǎn)后面若還有結(jié)點(diǎn)，p就向后移動，每次移動一次，計(jì)數(shù)器j值增1，直到p所指結(jié)點(diǎn)后面為空結(jié)束，則計(jì)數(shù)器j的值即為表的長度，算法描述見算法2.12。算法2.12intGetLength(LinkList*L){LinkList*p;intj=0;p=L;/*p指向鏈表的頭結(jié)點(diǎn)*/while(p->next!=NULL)/*判斷p所指結(jié)點(diǎn)后面是否為空*/{p=p->next;/*p向所指結(jié)點(diǎn)的后面移動*/j++;/*計(jì)數(shù)器值增1*/}returnj;/*計(jì)數(shù)器j的值為表長度*/}返回到本節(jié)目錄2.3.2單鏈表的基本操作實(shí)現(xiàn)4．查找操作單鏈表的查找分為按值與按序號查找，下面將分別介紹這兩種方法的實(shí)現(xiàn)，讀者可根據(jù)具體的問題相應(yīng)選擇所需的查找方法。（1）按值查找算法思路：從鏈表的第一個(gè)元素結(jié)點(diǎn)開始，由前向后依次比較單鏈表中各結(jié)點(diǎn)數(shù)據(jù)域中的值，若某結(jié)點(diǎn)數(shù)據(jù)域中的值與給定的值x相等，則返回該結(jié)點(diǎn)的指針值p；否則繼續(xù)向后比較直到表結(jié)束。若整個(gè)單鏈表中沒有這樣的結(jié)點(diǎn)，則返回空NULL值，算法描述見算法2.13。算法2.13LinkList*Locate(LinkList*L,ElemTypex){LinkList*p;p=L->next;/*p指向鏈表的第一個(gè)結(jié)點(diǎn)*/while(p!=NULL&&p->data!=x)p=p->next;returnp;}返回到本節(jié)目錄2.3.2單鏈表的基本操作實(shí)現(xiàn)（2）按序號查找算法思路：從鏈表的頭結(jié)點(diǎn)開始，判斷當(dāng)前結(jié)點(diǎn)序號是否是第i個(gè)，若是，則返回該結(jié)點(diǎn)指針值p；否則繼續(xù)向后查找直到表結(jié)束。若沒有第i個(gè)結(jié)點(diǎn)，則返回空NULL值，算法描述見算法2.14。算法2.14LinkList*GetList(LinkList*L,inti){LinkList*p;intj=0;p=L;/*p指向鏈表的頭結(jié)點(diǎn)*/while(p->next!=NULL&&j<i){p=p->next;j++;}if(j==i)/*判斷與給定的序號是否相等*/returnp;elsereturnNULL;}返回到本節(jié)目錄2.3.2單鏈表的基本操作實(shí)現(xiàn)5．插入操作順序表的插入操作需要移動大量的數(shù)據(jù)元素，而鏈表的插入只需修改指針而無需移動原表元素，那鏈表的插入操作是如何實(shí)現(xiàn)呢？（1）在已知結(jié)點(diǎn)p之后插入一新結(jié)點(diǎn)s已知結(jié)點(diǎn)p為鏈表中任意結(jié)點(diǎn)，先創(chuàng)建一個(gè)以x為值的新結(jié)點(diǎn)s，則插入操作步驟如下：先將結(jié)點(diǎn)s的指針域指向結(jié)點(diǎn)p的下一個(gè)結(jié)點(diǎn)（執(zhí)行語句s->next=p->next）。再將結(jié)點(diǎn)p的指針域改為指向新結(jié)點(diǎn)s（執(zhí)行語句p->next=s）。返回到本節(jié)目錄5．插入操作插入結(jié)點(diǎn)的過程如圖2-10所示，算法描述見算法2.15。注：插入操作的①與②語句執(zhí)行順序不能顛倒，否則原p指針其后的鏈表將丟失。算法2.15voidIns_Elem(LinkList*p,ElemTypex){LinkList*s;s=(LinkList*)malloc(sizeof(LinkList));/*生成新結(jié)點(diǎn)s*/s->data=x;/*將數(shù)據(jù)x放入新結(jié)點(diǎn)的數(shù)據(jù)域*/s->next=p->next;/*將新結(jié)點(diǎn)s的指針域與p結(jié)點(diǎn)后面元素相連*/p->next=s;/*將p與新結(jié)點(diǎn)s鏈接*/}返回到本節(jié)目錄5．插入操作（2）在第i個(gè)位置插入新結(jié)點(diǎn)s由于單鏈表的結(jié)點(diǎn)結(jié)構(gòu)是單向后指的，因此要完成此操作需要找到第i結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)即第i－1結(jié)點(diǎn)的指針p，此時(shí)可調(diào)用按序號查找GetList()函數(shù)求出p指針地址，然后在調(diào)用在已知結(jié)點(diǎn)p后方插入新結(jié)點(diǎn)Ins_Elem()函數(shù)操作即可，算法描述見算法2.16。算法2.16intInsElem(LinkList*L,inti,ElemTypex){LinkList*p;p=GetList(L,i-1);/*調(diào)用按序號查找函數(shù)GetList()，求出第i-1個(gè)元素地址p*/if(p!=NULL)/*判斷查找的元素地址p是否存在*/{Ins_Elem(p,x);/*調(diào)用在已知結(jié)點(diǎn)p后插入結(jié)點(diǎn)函數(shù)Ins_Elem()*/returnOK;}elsereturnERROR;}返回到本節(jié)目錄5．插入操作插入算法的時(shí)間性能分析：鏈表插入操作主要時(shí)間耗費(fèi)在查找操作上，其時(shí)間復(fù)雜度為Ｏ(n)。返回到本節(jié)目錄2.3.2單鏈表的基本操作實(shí)現(xiàn)6．刪除操作順序表的刪除操作同樣需要移動大量的數(shù)據(jù)元素，而鏈表的刪除只需修改指針而無需移動原表元素，那鏈表的刪除操作是如何實(shí)現(xiàn)呢？（1）刪除已知結(jié)點(diǎn)p之后結(jié)點(diǎn)s已知結(jié)點(diǎn)p為鏈表中除終端結(jié)點(diǎn)以外的任意結(jié)點(diǎn)，先將結(jié)點(diǎn)s中的數(shù)據(jù)域中的值賦給指針變量*x，則刪除操作步驟如下：結(jié)點(diǎn)p指針域指向結(jié)點(diǎn)s下一個(gè)結(jié)點(diǎn)（執(zhí)行語句p->next=s->next）。②釋放s結(jié)點(diǎn)空間（執(zhí)行語句free(s)）。返回到本節(jié)目錄6．刪除操作刪除結(jié)點(diǎn)的過程如圖2-11所示，算法描述見算法2.17。

圖2-11在結(jié)點(diǎn)p之后刪除結(jié)點(diǎn)s算法2.17voidDel_Elem(LinkList*p,ElemType*x){LinkList*s;s=p->next;/*s為要?jiǎng)h除結(jié)點(diǎn)*/*x=s->data;/*將要?jiǎng)h除的數(shù)據(jù)放入指針變量*x中*/p->next=s->next;/*將p結(jié)點(diǎn)的指針域與s結(jié)點(diǎn)后面元素相連*/free(s);/*釋放結(jié)點(diǎn)s*/}返回到本節(jié)目錄6．刪除操作（2）刪除未知結(jié)點(diǎn)（如第i個(gè)結(jié)點(diǎn)）s首先求出第i結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)（第i-1結(jié)點(diǎn)）p的地址，可調(diào)用按序號查找GetList()函數(shù)求出p指針地址，然后再調(diào)用刪除已知結(jié)點(diǎn)p之后結(jié)點(diǎn)s的DelList()函數(shù)操作即可。算法中注意if(p!=NULL&&p->next!=NULL)語句,只有當(dāng)?shù)趇-1結(jié)點(diǎn)存在即（p!=NULL）而又不是終端結(jié)點(diǎn)即（p->next!=NULL）時(shí)，才能確定被刪除結(jié)點(diǎn)存在，算法描述見算法2.18。算法2.18intDelElem(LinkList*L,inti,ElemType*x){LinkList*p;p=GetList(L,i-1);/*調(diào)用按序號查找第i-1個(gè)元素地址p函數(shù)*/if(p!=NULL&&p->next!=NULL){Del_Elem(p,x);/*調(diào)用刪除已知結(jié)點(diǎn)p之后結(jié)點(diǎn)函數(shù)*/returnOK;}elsereturnERROR;}返回到本節(jié)目錄6．刪除操作刪除算法的時(shí)間性能分析：鏈表刪除操作也主要時(shí)間耗費(fèi)在查找操作上，其時(shí)間復(fù)雜度為Ｏ(n)。返回到本節(jié)目錄2.3.2單鏈表的基本操作實(shí)現(xiàn)7．單鏈表的輸出操作掃描單鏈表L，輸出各元素的值，算法描述見算法2.19。算法2.19voidDispList(LinkList*L){LinkList*p;p=L->next;while(p!=NULL){printf("%c",p->data);p=p->next;}}返回到本節(jié)目錄2.3.3鏈表的變形1．循環(huán)單鏈表循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)。對于單鏈表而言，最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭?，如果將該鏈表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)，就構(gòu)成了循環(huán)單鏈表，如圖2-12所示。由此，從表中的任意結(jié)點(diǎn)出發(fā)均可找到表中的其他結(jié)點(diǎn)。在循環(huán)單鏈表上的操作基本上與非循環(huán)的單鏈表相同，只是將原來判斷指針是否為NULL，改為是否是頭指針L即可。圖2-12帶頭結(jié)點(diǎn)的循環(huán)單鏈表返回到本節(jié)目錄2.3.3鏈表的變形2．雙鏈表（1）雙鏈表的定義在單鏈表結(jié)點(diǎn)中只有一個(gè)指向直接后繼的指針域next，這樣從某個(gè)結(jié)點(diǎn)出發(fā)只能順指針方向?qū)ふ宜暮罄^結(jié)點(diǎn)。若要尋找結(jié)點(diǎn)的直接前驅(qū)，則需從頭指針出發(fā)查找前驅(qū)。若希望能夠快速查找一個(gè)結(jié)點(diǎn)的直接前驅(qū)，則可以再增加一個(gè)指向其直接前驅(qū)的指針域prior，這樣就構(gòu)成了雙向鏈接表，簡稱雙鏈表，其結(jié)點(diǎn)結(jié)構(gòu)如圖2-13所示。圖2-13雙鏈表的結(jié)點(diǎn)示意圖其中，data部分稱為數(shù)據(jù)域，用于存儲一個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)Node）的信息。prior部分稱為前驅(qū)指針域，用于存儲其直接前驅(qū)的存儲地址的信息。next部分稱為后繼指針域，用于存儲其直接后繼的存儲地址的信息。前驅(qū)指針域數(shù)據(jù)域后繼指針域priordatanext返回到本節(jié)目錄2．雙鏈表（2）雙鏈表的類型定義typedefcharElemType;/*定義ElemType為char類型*/typedefstructdunode/*雙鏈表存儲類型*/{ElemTypedata;/*定義結(jié)點(diǎn)的數(shù)據(jù)域*/structdunode*prior;/*定義結(jié)點(diǎn)的前驅(qū)指針域*/structdunode*next;/*定義結(jié)點(diǎn)的后繼指針域*/}DuLinkList;返回到本節(jié)目錄2．雙鏈表為了算法對所有的結(jié)點(diǎn)處理可一致化，與單鏈表一樣，本章討論的雙鏈表均指帶頭結(jié)點(diǎn)的雙鏈表。帶頭結(jié)點(diǎn)的雙鏈表如圖2-14所示。其中，頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲任何信息，也可以存放特殊的信息，頭結(jié)點(diǎn)的前驅(qū)指針域?yàn)榭眨碞ULL或用∧表示），后繼指針域存儲鏈表中第一個(gè)結(jié)點(diǎn)的地址。當(dāng)頭結(jié)點(diǎn)的后繼指針域?yàn)榭眨碞ULL或用∧表示），則此表為空表。在非空表中，當(dāng)某個(gè)結(jié)點(diǎn)的后繼指針域?yàn)榭眨硎舅鼮殒湵淼淖詈笠粋€(gè)結(jié)點(diǎn)。返回到本節(jié)目錄2．雙鏈表（3）雙鏈表的基本運(yùn)算在雙鏈表中，有些操作（如求鏈表的長度、查找某個(gè)結(jié)點(diǎn)等）僅涉及一個(gè)方向的指針，其算法與單鏈表的操作相同，但在插入和刪除操作時(shí)卻有很大的區(qū)別。①在雙鏈表中p指針指向的結(jié)點(diǎn)前插入新結(jié)點(diǎn)s操作先創(chuàng)建一個(gè)以x為值的新結(jié)點(diǎn)s，在p結(jié)點(diǎn)之前插入結(jié)點(diǎn)s，則插入操作步驟如下：將結(jié)點(diǎn)s的prior域指向結(jié)點(diǎn)p的前一個(gè)結(jié)點(diǎn)（執(zhí)行語句s->prior=p->prior）。將結(jié)點(diǎn)p的前一個(gè)結(jié)點(diǎn)的next域指向結(jié)點(diǎn)s（執(zhí)行語句p->prior->next=s）。將結(jié)點(diǎn)s的next域指向p結(jié)點(diǎn)（執(zhí)行語句s->next=p）。將結(jié)點(diǎn)p的prior域指向結(jié)點(diǎn)s。（執(zhí)行語句p->prior=s）。返回到本節(jié)目錄2．雙鏈表插入結(jié)點(diǎn)的過程如圖2-15所示，算法描述見算法2.20。注：以上操作的步驟的順序不是唯一的，但a操作步驟必須放在d操作步驟的前面完成，否則結(jié)點(diǎn)p的前驅(qū)結(jié)點(diǎn)的指針將丟失。返回到本節(jié)目錄2．雙鏈表算法2.20voidDuIns_Elem(DuLinkList*p,ElemTypex){DuLinkList*s;s=(DuLinkList*)malloc(sizeof(DuLinkList));/*生成新結(jié)點(diǎn)s*/s->data=x;s->prior=p->prior;/*對應(yīng)圖2-15中的a*/p->prior->next=s;/*對應(yīng)圖2-15中的b*/s->next=p;/*對應(yīng)圖2-15中的c*/p->prior=s;/*對應(yīng)圖2-15中的d*/}返回到本節(jié)目錄2．雙鏈表②在雙鏈表中刪除p指針指向的結(jié)點(diǎn)操作先保證刪除位置的正確性。在雙鏈表上找到刪除位置結(jié)點(diǎn)地址，由p指向，先將結(jié)點(diǎn)p中的數(shù)據(jù)域中的值賦給指針變量*x，則刪除操作步驟如下：將結(jié)點(diǎn)p前一個(gè)結(jié)點(diǎn)的next域指向結(jié)點(diǎn)p的next域（執(zhí)行語句p->prior->next=p->next）。將結(jié)點(diǎn)p后一個(gè)結(jié)點(diǎn)的prior域指向結(jié)點(diǎn)p的prior域（執(zhí)行語句p->next->prior=p->prior）。釋放結(jié)點(diǎn)p空間。(執(zhí)行語句free(p)）。返回到本節(jié)目錄2．雙鏈表刪除結(jié)點(diǎn)的過程如圖2-16所示，算法描述見算法2.21。算法2.21voidDuDel_Elem(DuLinkList*p,ElemType*x){*x=p->data;p->prior->next=p->next;/*對應(yīng)圖2-16中的a*/p->next->prior=p->prior;/*對應(yīng)圖2-16中的b*/free(p);}返回到本節(jié)目錄2.3.3鏈表的變形3．循環(huán)雙鏈表與循環(huán)單鏈表一樣，也可以使用循環(huán)雙鏈表。對于雙鏈表而言，頭結(jié)點(diǎn)的前驅(qū)指針域與最后一個(gè)結(jié)點(diǎn)的后繼指針域均為空。如果將該鏈表中最后一個(gè)結(jié)點(diǎn)的后繼指針域指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的前驅(qū)指針域指向最后一個(gè)結(jié)點(diǎn)，整個(gè)鏈表形成兩個(gè)環(huán)，就構(gòu)成了循環(huán)雙鏈表，如圖2-17所示帶頭結(jié)點(diǎn)的循環(huán)雙鏈表。在循環(huán)雙鏈表上的操作基本與雙鏈表相同。圖2-17帶頭結(jié)點(diǎn)的循環(huán)雙鏈表

在循環(huán)雙鏈表中，若p為指向表中某一個(gè)結(jié)點(diǎn)的指針，則有：p->prior->next=p=p->next->prior返回到本節(jié)目錄2.4線性表的應(yīng)用舉例

【例2.1】建立一個(gè)對線性表操作的綜合程序。在該程序中，包括順序表的建立、插入、刪除、查找等各種操作。并在主函數(shù)內(nèi)設(shè)計(jì)一個(gè)菜單，實(shí)現(xiàn)反復(fù)操作，完整程序算法描述見算法2.22。算法2.22/**************各種常量及結(jié)構(gòu)體類型定義*********************/#defineMAXLEN100/*順序表存儲空間的總分配量*/#defineOK1#defineERROR0#defineOVER-1typedefintElemType;/*定義ElemType為int類型*/typedefstruct/*存儲類型*/{ElemTypedata[MAXLEN];/*存放線性表的數(shù)組*/intLength;/*Lengthgth是順序表的長度*/}SeqList;返回到總目錄2.4線性表的應(yīng)用舉例/********************建立線性表函數(shù)************************/voidcreate(SeqList*L,intn){inti;printf("請輸入各個(gè)元素值：\n");for(i=0;i<n;i++)scanf("%d",&L->data[i]);L->Length=i;}/********************顯示輸出表中信息函數(shù)********************/voidDispList(SeqList*L){inti;for(i=0;i<L->Length;i++)printf("%5d",L->data[i]);}返回到本節(jié)目錄2.4線性表的應(yīng)用舉例/********************插入元素函數(shù)***********************/intInsElem(SeqList*L,inti,ElemTypex){intj;if(L->Length>=MAXLEN){printf("表已滿！");returnOVER;/*表滿，不能插入*/}if(i<1||i>L->Length+1)/*檢查給定的插入位置的正確性*/{printf("插入位置出錯(cuò)！");returnERROR;}if(i==L->Length+1){L->data[i-1]=x;L->Length++;returnOK;/*插入的位置為表尾，則不需移動直接插入即可*/}for(j=L->Length-1;j>=i-1;j--)/*結(jié)點(diǎn)移動*/L->data[j+1]=L->data[j];L->data[i-1]=x;/*新元素插入*/L->Length++;/*表長度增1*/returnOK;/*插入成功，返回*/}返回到本節(jié)目錄2.4線性表的應(yīng)用舉例/**********************刪除元素函數(shù)**********************/intDelElem(SeqList*L,inti,ElemType*x){intj;if(L->Length==0){printf("順序表為空！");returnERROR;/*表空，不能刪除*/}if(i<1||i>L->Length)/*檢查空表及刪除位置的合法性*/{printf("不存在第%d個(gè)元素",i);returnERROR;}*x=L->data[i-1];/*用指針變量x返回刪除的元素值*/for(j=i;j<=L->Length-1;j++)/*結(jié)點(diǎn)移動*/L->data[j-1]=L->data[j];L->Length--;/*順序表長度減1*/returnOK;/*刪除成功，返回*/}返回到本節(jié)目錄2.4線性表的應(yīng)用舉例/*********************在表中按值查找函數(shù)*******************/intLocate(SeqList*L