1.教學(xué)目標(biāo)

通過(guò)線性表的學(xué)習(xí)，熟悉本書(shū)對(duì)每種數(shù)據(jù)結(jié)構(gòu)的描述方法，掌握線性表的定義、特點(diǎn)、典型算法及實(shí)際中的實(shí)用。2.教學(xué)要求①了解線性表的邏輯結(jié)構(gòu)特性。②熟練掌握線性表的兩種存儲(chǔ)結(jié)構(gòu)的描述方法。③熟練掌握線性表在順序存儲(chǔ)結(jié)構(gòu)上基本操作的實(shí)現(xiàn)④熟練掌握線性表在各種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上基本操作的實(shí)現(xiàn)；⑤能夠從時(shí)間和空間復(fù)雜度的角度比較線性表兩種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)第二章線性表3．教學(xué)重點(diǎn)：①線性表順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及基本操作。②線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)及基本操作。4．教學(xué)難點(diǎn)：①鏈表的概念。②鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上算法的實(shí)現(xiàn)。2.1線性表的定義及邏輯結(jié)構(gòu)

2.1.1線性表的定義線性表

——是n個(gè)相同類型數(shù)據(jù)元素組成的有限序列。記作：（a1,a2,…，ai-1，ai，ai+1，…，an）

其中a1稱作起始結(jié)點(diǎn)，

an稱作終端結(jié)點(diǎn)。i稱為ai在線性表中的位置或序號(hào)。

n為表長(zhǎng)，n=0時(shí)，稱為空表。十二屬相歌：“小老鼠打頭來(lái)，牛把蹄兒抬；老虎回頭一聲吼，兔兒跳得快；龍和蛇尾巴甩，馬羊步兒邁；小猴機(jī)靈蹦又跳，雞唱天下白；狗兒跳豬兒叫，請(qǐng)把順序排!”例1、26個(gè)英文字母組成的字母表

（A，B，C、…、Z）

例2、某學(xué)院從2008年到2013年擁有的學(xué)生人數(shù)的變化情況表：

(800，1000，2000，3600，3800，4500)

例3、

在校學(xué)生的健康信息表是一個(gè)線性表，表中每個(gè)學(xué)生的信息由學(xué)號(hào)、姓名、性別、年齡、班級(jí)和健康狀況等組成舉例學(xué)號(hào)姓名性別年齡班級(jí)健康狀況1204101錢小明男19計(jì)科12健康1204108周維男18計(jì)科12一般1204111楊麗女20計(jì)科12健康1204112趙武男23計(jì)科12差………………1204135張麗女17計(jì)科12一般線性表

——是n個(gè)相同類型數(shù)據(jù)元素組成的有限序列。記作：（a1,a2,…，ai-1，ai，ai+1，…，an）

其中a1稱作起始結(jié)點(diǎn)，

an稱作終端結(jié)點(diǎn)。i稱為ai在線性表中的位置或序號(hào)。

n為表長(zhǎng)，n=0時(shí)，稱為空表。表中相鄰元素間存在著順序關(guān)系，對(duì)于任一對(duì)相鄰結(jié)點(diǎn)<ai，ai+1

>ai稱為ai+1的前驅(qū)，ai+1稱為ai的后繼線性表的特點(diǎn)：線性表由同一類型的數(shù)據(jù)元素組成，每個(gè)ai必須屬于同一數(shù)據(jù)類型。線性表中的數(shù)據(jù)元素個(gè)數(shù)是有限的，表長(zhǎng)就是表中數(shù)據(jù)元素的個(gè)數(shù)。存在唯一的“第一個(gè)”數(shù)據(jù)元素；存在唯一的“最后一個(gè)”數(shù)據(jù)元素。除第一個(gè)數(shù)據(jù)元素外，每個(gè)數(shù)據(jù)元素均有且只有一個(gè)前驅(qū)元素。除最后一個(gè)數(shù)據(jù)元素外，每個(gè)數(shù)據(jù)元素均有且只有一個(gè)后繼元素。2.1.2線性表的基本操作

(1)初始化InitList(L)

(2)線性表判空EmptyList(L)

(3)求長(zhǎng)度LengthList(L)

(4)取元素函數(shù)GetList(L,i)

(5)按值查找LocatList(L,x)

(6)插入操作InsertList(L,i,x)

(7)刪除操作DeleteList(L,i)2.2線性表的順序存儲(chǔ)結(jié)構(gòu)2.2.1順序表

線性表的順序存儲(chǔ)結(jié)構(gòu)是指在計(jì)算機(jī)中用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的各個(gè)數(shù)據(jù)元素，元素之間的邏輯關(guān)系通過(guò)存儲(chǔ)位置來(lái)反映，用這種存儲(chǔ)形式存儲(chǔ)的線性表稱其為順序表。設(shè)a1的存儲(chǔ)地址為L(zhǎng)oc(a1)，每個(gè)數(shù)據(jù)元素占L個(gè)存儲(chǔ)單元，則第i個(gè)數(shù)據(jù)元素的地址為：Loc(ai)=Loc(a1)+(i-1)×L1≤i≤n

按數(shù)據(jù)元素的序號(hào)隨機(jī)存取線性表的順序存儲(chǔ)結(jié)構(gòu)可用C語(yǔ)言定義如下：#defineMAXSIZE100typedefstructLinear_list{datatypeelem[MAXSIZE];

intlast;}

SeqList;

SeqList

L;線性表中最后一個(gè)元素在數(shù)組中的位置存放數(shù)據(jù)元素

順序存儲(chǔ)結(jié)構(gòu)三個(gè)重要屬性：存儲(chǔ)數(shù)據(jù)元素的空間：數(shù)組elem，用于存放數(shù)據(jù)元素。線性表的最大容量：MAXSIZE。線性表當(dāng)前長(zhǎng)度：由last+1確定，last：最后一個(gè)數(shù)據(jù)元素在數(shù)組中的下標(biāo)。強(qiáng)調(diào)兩個(gè)問(wèn)題：“數(shù)組的長(zhǎng)度”和“線性表的長(zhǎng)度”兩個(gè)概念。注意區(qū)分?jǐn)?shù)據(jù)元素的位序和數(shù)組的下標(biāo)。SeqList*L

；SeqList

L;表長(zhǎng)：L.last+1數(shù)據(jù)元素：L.elem[0]~L.elem[L.last]。表長(zhǎng)：（*L）.last+1或L->last+1數(shù)據(jù)元素：L->elem[0]~L->elem[L->last]2.2.2順序表上插入與刪除操作的實(shí)現(xiàn)1初始化SeqList*InitList(){SeqList*L;L=(SeqList*)malloc(sizeof(SeqList));L->last=-1;returnL;}主函數(shù)對(duì)初始化函數(shù)的調(diào)用如下：main(){SeqList*L;L=InitList();……}本算法的主要運(yùn)算是比較。2按值查找intLocatList(SeqList*L,datatypex){inti=0;

while(i<=L->last&&L->elem[i]!=x)i++;

if(i>L->last)return-1;elsereturni;/*返回的是存儲(chǔ)位置*/

}平均比較次數(shù)為(n+1)/2，時(shí)間復(fù)雜度為O(n)。3插入運(yùn)算線性表的插入是指在表的第i個(gè)位置上插入一個(gè)值為x的新元素,i的取值范圍為1≤i≤n+1。③修改last指針（相當(dāng)于修改表長(zhǎng)），使之仍指向最后一個(gè)元素。步驟：①將ai～an

順序向下移動(dòng)，為新元素讓出位置；②將x置入空出的第i個(gè)位置；1intInsertList(SeqList*Lp,inti,datatypex)2{intj;3if(Lp->last==MAXSIZE-1)4{printf(″表滿″);5return(-1);6}if(i<1||i>Lp->last+2) {printf(″位置錯(cuò)″);9return(0);10}for(j=Lp->last;j>=i-1;j--) Lp->elem[j+1]=Lp->elem[j];13Lp->elem[i-1]=x; /*新元素插入*/14Lp->last++; /*last仍指向最后元素*/15return(1); /*插入成功，返回*/16}算法實(shí)現(xiàn)：算法設(shè)計(jì)時(shí)請(qǐng)注意：注意數(shù)據(jù)的移動(dòng)方向檢驗(yàn)插入位置的有效性：1≤i≤n+1在表滿的情況下不能再做插入時(shí)間復(fù)雜度為：O（n）

時(shí)間性能分析：

在順序表中插入一個(gè)數(shù)據(jù)元素時(shí)，其時(shí)間主要耗費(fèi)在移動(dòng)數(shù)據(jù)元素上。在第i個(gè)位置上插入x，從ai

到an都要向下移動(dòng)一個(gè)位置，共需要移動(dòng)n-i+1個(gè)元素，而i的取值范圍為1≤i≤n+1，即有n+1個(gè)位置可以插入。設(shè)在第i個(gè)位置上插入元素的概率為Pi，則平均移動(dòng)數(shù)據(jù)元素的次數(shù)為說(shuō)明在順序表上作插入運(yùn)算平均需要移動(dòng)表中一半的數(shù)據(jù)元素假設(shè)在每個(gè)位置插入元素的概率相等，即Pi?=?1/(n+1)，則①將ai+1～an順序向上移動(dòng)。4.刪除操作指將表中第i個(gè)元素從線性表中去掉,i的取值范圍為:1≤i≤n步驟：②修改last指針使之仍指向最后一個(gè)元素。①當(dāng)表空時(shí)不能做刪除，否則產(chǎn)生下溢錯(cuò)誤。②要檢查刪除位置的有效性1≤i≤n。③刪除ai

之后，該數(shù)據(jù)已不存在，如果需要，先取出ai

，再做刪除。④注意數(shù)據(jù)的移動(dòng)方向。注意：算法如下：1intDeleteList(SeqList*Lp,inti)2{intj;if(i<1||i>Lp->last+1){printf(″不存在第i個(gè)元素″);5return(0);6}7for(j=i;j<=Lp->last;j++)Lp->elem[j-1]=Lp->elem[j]; Lp->last--;10return(1); /*刪除成功*/11}/*檢查刪除位置的合法性*//*向上移動(dòng)*//*刪除成功*/

刪除算法的時(shí)間性能分析：與插入運(yùn)算相同，其時(shí)間主要消耗在移動(dòng)表中元素上，刪除第i個(gè)元素時(shí)，其后面的元素ai+1～an都要向上移動(dòng)一個(gè)位置，共移動(dòng)了n-i個(gè)元素，所以平均移動(dòng)數(shù)據(jù)元素的次數(shù)：時(shí)間復(fù)雜度為：O（n）等概率情況下，Ｐi＝

1/n算法性能分析：則平均移動(dòng)數(shù)據(jù)元素的次數(shù)為線性表順序表示的優(yōu)缺點(diǎn)對(duì)比優(yōu)點(diǎn)缺點(diǎn)無(wú)需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間可方便地隨機(jī)存取表中的任一元素插入或刪除需要移動(dòng)大量的數(shù)據(jù)元素當(dāng)線性表長(zhǎng)度變化較大時(shí)難以確定存儲(chǔ)空間的容量造成存儲(chǔ)空間浪費(fèi)2.2.3順序表應(yīng)用舉例

例2-4利用兩個(gè)線性表La和Lb分別表示兩個(gè)集合A和B，現(xiàn)要求一個(gè)新的集合A?=?A∪B。假設(shè)集合中的數(shù)據(jù)元素屬于整型數(shù)據(jù)。算法思路：擴(kuò)大線性表La，將存在于線性表Lb中而不在La中的數(shù)據(jù)元素加入到線性表La中。逐一取出Lb中的元素，判斷是否在La中，若不在，則插入。由于La是集合，數(shù)據(jù)元素之間沒(méi)有順序關(guān)系，所以插入時(shí)，可以插入到La的最后一個(gè)元素后面，這樣，就不用移動(dòng)大量數(shù)據(jù)元素。A=(23,45,78,91,55)B=(47,23,8,55)A∪B=(23,45,78,91,55,47,8)存儲(chǔ)結(jié)構(gòu)即為2.2.1節(jié)中的SeqList；其中datatype定義為int。算法如下：1voidunin(SeqList*La,SeqListLb)2{inti,j,La_len,Lb_len;3datatypee;4La_len=La->last;5Lb_len=Lb->last;6for(i=0;i<=Lb_len;i++)7{e=lb.elem[i];8j=0;9while(j<=La_len&&e!=la->elem[j])j++;

10if(j>La_len) 11if(La_len<MAXSIZE-1) /*存儲(chǔ)空間足夠*/12La->elem[++(la->last)]=e; /*插入到La的最后*/13}14}union在la中查找e元素la中不存在和e相同的元素，則插入之語(yǔ)句6循環(huán)次數(shù)是Lb的表長(zhǎng)，語(yǔ)句9循環(huán)次數(shù)最多是La的表長(zhǎng)，所以，此算法的時(shí)間復(fù)雜度為O(ListLength(La)?×?ListLength(Lb))。例2-5有順序表A和B，其元素均按從小到大的升序排列，編寫一個(gè)算法將它們合并成一個(gè)順序表C，要求C的元素也是從小到大的升序排列。例如A?=?(2,2,3),B?=?(1,3,3,4)，則C?=?(1,2,2,3,3,3,4)。算法思路：依次掃描A和B的元素，比較當(dāng)前的元素的值，將較小值的元素賦給C，如此直到一個(gè)線性表掃描完畢，然后將未完的那個(gè)順序表中余下部分賦給C即可。C的容量要能夠容納A、B兩個(gè)線性表。設(shè)表C是一個(gè)空表，設(shè)兩個(gè)指針i、j分別指向表A和B中的元素，若A.elem[i]?>?B.elem[j]，則將B.elem[j]插入到表C中；若A.elem[i]≤B.elem[j]，則當(dāng)前先將A.elem[i]插入到表C中，如此進(jìn)行下去，直到其中一個(gè)表被掃描完畢，然后再將未掃描完的表中剩余的所有元素放到表C中。1voidmerge(SeqListA,SeqListB,SeqList*C)

2{inti,j,k;

3i=0;j=0;k=0;

4while(i<=A.last&&j<=B.last) /*A表、B表都不為空*/

5if(A.elem[i]<=B.elem[j])

6C->elem[k++]=A.elem[i++];/*將A表中i指針指向記錄插入到C中*/

7else

8C->elem[k++]=B.elem[j++];/*將B表中i指針指向記錄插入到C中*/

9while(i<=A.last) /*將A表剩余部分插入到C中*/

10C->elem[k++]=A.elem[i++];

11while(j<=B.last) /*將B表剩余部分插入到C中*/

12C->elem[k++]=B.elem[j++];

13C->last=k-1;

14}包含有三個(gè)并列的循環(huán)，語(yǔ)句4～語(yǔ)句8循環(huán)次數(shù)為表A的長(zhǎng)度或者表B的長(zhǎng)度，語(yǔ)句9～語(yǔ)句12是兩個(gè)并列的循環(huán)，這兩個(gè)中只有可能做一個(gè)，循環(huán)次數(shù)為表A或表B剩余的部分。因此，該算法的時(shí)間復(fù)雜度是O(A.last?+?B.last)。習(xí)題：將順序表(a1，a2，...，an)重新排列為以a1為界的兩部分：a1前面的值均比a1小，a1后面的值均比a1大（這里假設(shè)數(shù)據(jù)元素的類型具有可比性，不妨設(shè)為整型）。這一操作稱為劃分，a1也稱為基準(zhǔn)。

劃分前23456103576185620劃分后20186102376355645線性表順序表示的優(yōu)點(diǎn)：①

無(wú)需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間（因?yàn)檫壿嬌舷噜彽脑仄浯鎯?chǔ)的物理位置也是相鄰的）；

線性表順序表示的缺點(diǎn)：②由于順序表要求占用連續(xù)的存儲(chǔ)空間，存儲(chǔ)分配只能預(yù)先進(jìn)行靜態(tài)分配，因此當(dāng)表長(zhǎng)變化較大時(shí)，難以確定合適的存儲(chǔ)規(guī)模。

②可方便地隨機(jī)存取表中的任一元素。

①

插入或刪除運(yùn)算不方便，除表尾位置外，在其它位置上進(jìn)行插入或刪除操作都必須移動(dòng)大量的數(shù)據(jù)元素，其效率較低；2.3線性表的鏈?zhǔn)酱鎯?chǔ)2.3.1單鏈表（a1,a2,…，ai-1，ai，ai+1，…，an）數(shù)據(jù)域——用來(lái)存儲(chǔ)結(jié)點(diǎn)的值；指針域——用來(lái)存儲(chǔ)數(shù)據(jù)元素的直接后繼的地址;用一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)線性表中的數(shù)據(jù)元素。

datanext指針域數(shù)據(jù)域通常，我們關(guān)心的是結(jié)點(diǎn)間的邏輯結(jié)構(gòu)，而對(duì)每個(gè)結(jié)點(diǎn)的實(shí)際地址并不關(guān)心，所以通常單鏈表用下圖所示的形式表示。1)鏈表每個(gè)結(jié)點(diǎn)只有一個(gè)指針域，這種鏈表又稱為單鏈表。2)

單鏈表第一個(gè)結(jié)點(diǎn)無(wú)前趨，設(shè)一個(gè)頭指針H指向第一個(gè)結(jié)點(diǎn)。3)

表中最后一個(gè)結(jié)點(diǎn)沒(méi)有直接后繼，則最后一個(gè)結(jié)點(diǎn)的指針域?yàn)椤翱铡保∟ULL）。a1a2an^…H單鏈表的存儲(chǔ)結(jié)構(gòu)描述用C語(yǔ)言如下：typedefstructnode{

datatypedata;structnode*next;

}LNode，*LinkList；

定義結(jié)構(gòu)體變量：LinkListH；H是一個(gè)結(jié)構(gòu)體指針，即單鏈表的頭指針通常在線性鏈表的第一結(jié)點(diǎn)之前附設(shè)一個(gè)稱為頭結(jié)點(diǎn)的結(jié)點(diǎn)。

H->next==NULL（帶頭結(jié)點(diǎn)）對(duì)于帶頭結(jié)點(diǎn)的單鏈表H∧若定義

LinkListp;

且p=H->next那么p->data=a1p->next->data=a2

其余依此類推。通常我們用頭指針來(lái)標(biāo)識(shí)一個(gè)單鏈表，如單鏈表L、單鏈表H等，是指某鏈表的第一個(gè)結(jié)點(diǎn)的地址放在了指針變量L或H中，頭指針為NULL，則表示一個(gè)空表，即H==NULL為真。a1a2an∧…H頭指針和頭結(jié)點(diǎn)的異同頭指針頭結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn)的指針，若鏈表有頭結(jié)點(diǎn)，則是指向頭結(jié)點(diǎn)的指針具有標(biāo)示作用，常用頭指針作為鏈表的名字放在第一個(gè)元素之前，其數(shù)據(jù)域一般無(wú)意義(也可以放鏈表的長(zhǎng)度)有了頭結(jié)點(diǎn)，在第一個(gè)元素結(jié)點(diǎn)之前插入和刪除第一個(gè)結(jié)點(diǎn)，其操作與其他結(jié)點(diǎn)的操作就統(tǒng)一了造成存儲(chǔ)空間浪費(fèi)

不帶頭結(jié)點(diǎn)的鏈表和帶頭結(jié)點(diǎn)的鏈表的區(qū)別不帶頭結(jié)點(diǎn)帶頭結(jié)點(diǎn)鏈表為空：L==NULL為真鏈表的第一個(gè)數(shù)據(jù)元素由L指向在第一個(gè)元素之前插入一個(gè)元素和刪除第一個(gè)元素要單獨(dú)處理，和在其他位置插入、刪除操作不同鏈表為空：L->next==NULL為真鏈表的第一個(gè)數(shù)據(jù)元素由L->next指向插入、刪除操作統(tǒng)一2.3.2單鏈表上的基本運(yùn)算LinkListInitList(LinkList*h){if(

(*h=(LinkList)malloc(sizeof(LNode)))==NULL

)return(0);(*h)->next=NULL;return(1);}1.初始化初始化操作即建立一個(gè)空表。H∧1建立單鏈表

建立過(guò)程是一個(gè)動(dòng)態(tài)生成的過(guò)程，即從“空表”起，依次建立結(jié)點(diǎn)，并逐個(gè)插入鏈表１頭插法２尾插法逆序創(chuàng)建鏈表順序創(chuàng)建鏈表2.3.2單鏈表上的基本運(yùn)算1）用頭插法建立單鏈表的算法Step0:

Step1:Step2:Step3:在鏈表的頭部插入，讀入數(shù)據(jù)的順序和線性表的邏輯順序是相反的申請(qǐng)一塊空間，s指向?qū)->next的值賦給s->next

將L->next的值改為s建立只有頭結(jié)點(diǎn)的單鏈表1LinklistCreateFromHead()2{LinkListL;3LNode*s;4charc;5intflag=1;/*設(shè)置一個(gè)標(biāo)識(shí)變量flag，初值為1，當(dāng)輸入“$”時(shí)，將flag置為0，建表結(jié)束*/6L=(Linklist)malloc(sizeof(LNode)); /*為頭結(jié)點(diǎn)分配存儲(chǔ)空間*/7L->next=NULL;8while(flag)9{c=getchar();10if(c!='$')11{s=(Linklist)malloc(sizeof(LNode));/*為讀入的字符分配存儲(chǔ)空間*/12s->data=c; /*數(shù)據(jù)域賦值*/13s->next=L->next;/*將s插入到鏈表中第一個(gè)數(shù)據(jù)元素之前*/14L->next=s;15}16else17flag=0;/*讀入符號(hào)為“$”，修改結(jié)束標(biāo)識(shí)*/

18}19returnL;20}2）尾插法建表算法中必須維持一個(gè)始終指向已建立的鏈表表尾的指針。1LinklistCreateFromHead()2{LinkListL;3LNode*s;4charc;5intflag=1;6L=(Linklist)malloc(sizeof(LNode)); /*為頭結(jié)點(diǎn)分配存儲(chǔ)空間*/7L->next=NULL; /*建帶頭結(jié)點(diǎn)的空鏈表*/8r=L; /*尾指針r指向表尾*/9while(flag)10{c=getchar();11if(c!='$')12{s=(Linklist)malloc(sizeof(LNode));/*為讀入的字符分配存儲(chǔ)空間*/13s->data=c; /*數(shù)據(jù)域賦值*/14r->next=s; /*插入到表尾*/15r=s;16}17else18{flag=0;19r->next=NULL;20}21}22returnL;23}２.求鏈表長(zhǎng)度的操作intListLength(LinkListL){3LinkListp;4p=L;j=0;while(p->next!=NULL)7{8p=p->next;9j++;10}11returnj;12}

求單鏈表的長(zhǎng)度可以采用“數(shù)”結(jié)點(diǎn)的方法，從第一個(gè)元素開(kāi)始“數(shù)”，一直“數(shù)”到最后一個(gè)結(jié)點(diǎn)(p->next=NULL)，就可求得單鏈表的長(zhǎng)度。３.查找1)按序號(hào)查找要查找表中第i個(gè)結(jié)點(diǎn)，該如何做？（求線性表中的第ｉ個(gè)元素的運(yùn)算）需要從單鏈表的頭指針L出發(fā)，開(kāi)始順著鏈域，一個(gè)接一個(gè)找，直到找到第ｉ個(gè)結(jié)點(diǎn)。提問(wèn)：?jiǎn)捂湵硐耥樞虮砟菢訉?shí)現(xiàn)隨機(jī)存取嗎？算法實(shí)現(xiàn)如下：這個(gè)算法的基本操作是移動(dòng)指針，移動(dòng)的次數(shù)最大值和線性表的表長(zhǎng)相當(dāng)。時(shí)間復(fù)雜度：O(n)從頭結(jié)點(diǎn)開(kāi)始掃描計(jì)數(shù)器找到了第i個(gè)結(jié)點(diǎn)LinkListGetlist(LinkListL,inti){intj；

LNode*p；

p=L；j=0；

while(p->next!=NULL&&j<i){p=p->next；

j++；}

if（i==j）returnp；

elsereturnNULL；}2)按值查找

算法描述：查找過(guò)程從單鏈表的頭指針指向的頭結(jié)點(diǎn)出發(fā)，順著鏈表逐個(gè)將結(jié)點(diǎn)的值和給定值e作比較。若找到，返回找到的值為e的結(jié)點(diǎn)的存儲(chǔ)位置，否則，返回空。要查找結(jié)點(diǎn)值等于給定值的結(jié)點(diǎn)1LinkListLocate(LinkListL,chare)2{LinkListp;3p=L->next;/*從表中第一個(gè)結(jié)點(diǎn)比較*/4while(p!=NULL&&p->data!=e)

5p=p->next;6returnp;7}算法實(shí)現(xiàn)如下：由于線性鏈表失去了隨機(jī)存取的特性，所以按序號(hào)查找算法、按值查找算法的時(shí)間復(fù)雜度均為O(n)。４.單鏈表插入操作算法描述：首先在單鏈表中找到第i-1個(gè)結(jié)點(diǎn)，然后申請(qǐng)一個(gè)新的結(jié)點(diǎn)，使它的指針域指向原第i個(gè)結(jié)點(diǎn)。

分析：當(dāng)用指針指示后繼元素時(shí)，實(shí)現(xiàn)關(guān)系的改變只需要修改指針即可s=(LinkList)malloc(sizeof(Node));s->data=e;s->next=p->next;p->next=s;1intInsList(LinkListL,inti,chare)

2{/*在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)位置插入值為e的新結(jié)點(diǎn)*/3LinkListpre,s;4intk;5pre=L;k=0;6while(pre!=NULL&&k<i-1)/*找到第i-1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置*/7{pre=pre->next;8k=k+1;9}10if(k!=i-1) /*插入位置不合理*/11{printf(″插入位置不合理!″);12returnERROR;13}14s=(LinkList)malloc(sizeof(LNode));/*為e申請(qǐng)一個(gè)新的結(jié)點(diǎn)并由s指向它*/15s->data=e; /*將待插入結(jié)點(diǎn)的值e賦給s的數(shù)據(jù)域*/16s->next=pre->next; /*完成插入操作*/17pre->next=s;18returnOK;19}５.刪除和插入類似，刪除操作改變了元素之間的關(guān)系，因此需要修改元素所在結(jié)點(diǎn)的指針?；舅枷肱c插入相同，需要找到前驅(qū)結(jié)點(diǎn)。r=p->next;p->next=p->next->next;*e=r->data;free(r);注意：刪除的是前驅(qū)結(jié)點(diǎn)的next結(jié)點(diǎn)，因此不僅要求結(jié)點(diǎn)的前驅(qū)存在，而且要求被刪除的結(jié)點(diǎn)在鏈表中確實(shí)存在1intDelList(LinkListL,inti,char*e)2{/*在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個(gè)元素*/3LinkListp,r;4intk;5pre=L;k=0;6while(pre->next!=NULL&&k<i-1)/*尋找被刪除結(jié)點(diǎn)i的前驅(qū)結(jié)點(diǎn)i-1*/7{pre=pre->next;8k=k+1;9}10if(k!=i-1)/*while循環(huán)是因?yàn)閜->next=NULL或i<1而跳出的*/11{printf(″刪除結(jié)點(diǎn)的位置i不合理!″);12returnERROR;13}14r=pre->next;15pre->next=pre->next->next; /*刪除結(jié)點(diǎn)r*/16*e=r->data;17free(r); /*釋放被刪除的結(jié)點(diǎn)所占的內(nèi)存空間*/18returnOK;19}

刪除算法中的循環(huán)條件(pre->next!?=?NULL&&k?<?i-1)前插算法中的循環(huán)條件(pre!?=?NULL&&k?<?i-1)因?yàn)榍安鍟r(shí)的插入位置有n+1個(gè)(n為當(dāng)前單鏈表中數(shù)據(jù)元素的個(gè)數(shù))。i=n+1是指在第n+1個(gè)位置前插入，即在單鏈表的末尾插入。而刪除操作中刪除的合法位置只有n個(gè)，若使用與前插操作相同的循環(huán)條件，則會(huì)出現(xiàn)指針指空的情況，使刪除操作失敗。在線性鏈表中插入、刪除元素雖然不需要移動(dòng)數(shù)據(jù)元素，但需要查找插入、刪除的位置，所以時(shí)間復(fù)雜度仍然是Ｏ(n)。通過(guò)上面的基本操作我們得知：①在單鏈表上插入、刪除一個(gè)結(jié)點(diǎn)，必須知道其前驅(qū)結(jié)點(diǎn)。②單鏈表不具有按序號(hào)隨機(jī)訪問(wèn)的特點(diǎn)，插入位置的查找只能從頭指針開(kāi)始一個(gè)一個(gè)順序進(jìn)行。

說(shuō)明：總結(jié)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)在于？2單鏈表不具有按序號(hào)隨機(jī)訪問(wèn)的特點(diǎn)，順序存取元素。1

動(dòng)態(tài)分配存儲(chǔ)空間，不需要事先估計(jì)表的長(zhǎng)度。3插入、刪除操作不需要移動(dòng)數(shù)據(jù)元素，只需修改指針域。必須知道其前驅(qū)結(jié)點(diǎn)。從上述操作可以看到：鏈表中結(jié)點(diǎn)所占的空間，是?動(dòng)態(tài)分配2.3.3循環(huán)單鏈表

將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域由NULL改為指向頭結(jié)點(diǎn)或線性表中的第一個(gè)結(jié)點(diǎn)，就得到了單鏈形式的循環(huán)鏈表，并稱為循環(huán)鏈表。

為了使某些操作實(shí)現(xiàn)起來(lái)方便，在循環(huán)單鏈表中也可設(shè)置一個(gè)頭結(jié)點(diǎn)。這樣，空循環(huán)鏈表僅由一個(gè)自成循環(huán)的頭結(jié)點(diǎn)表示。

LLa1a2ai…an…假設(shè)P指向鏈表最后一個(gè)結(jié)點(diǎn)。單鏈表：p->next==NULL為真。循環(huán)單鏈表：p->next==?L為真。判斷鏈表是否為空的條件：?jiǎn)捂湵恚簆!?=?L循環(huán)單鏈表：p->next!?=?L。對(duì)于單鏈表只能從頭結(jié)點(diǎn)開(kāi)始遍歷整個(gè)鏈表，而對(duì)于循環(huán)單鏈表則可以從表中任意結(jié)點(diǎn)開(kāi)始遍歷整個(gè)鏈表。對(duì)鏈表常做的操作是在表尾、表頭進(jìn)行時(shí)，用一個(gè)指向尾結(jié)點(diǎn)的指針R來(lái)標(biāo)識(shí)，可以提高操作效率。例：有兩個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表LA、LB，編寫一個(gè)算法，將兩個(gè)循環(huán)單鏈表合并為一個(gè)循環(huán)單鏈表，其頭指針為L(zhǎng)A。3

修改第二個(gè)表的尾Q，使它的鏈域指向第一個(gè)表的頭結(jié)點(diǎn)。算法步驟：p=LA;q=LB;while(p->next!=LA)p=p->next;while(q->next!=LB)q=q->next;1

找到兩個(gè)鏈表的尾，并分別由指針p、q指向它們2

將第一個(gè)鏈表的尾與第二個(gè)表的第一個(gè)結(jié)點(diǎn)鏈接起來(lái)q->next=LA;p->next=LB->next;free(LB);LinkListmerge--1(LinkListLA,LinkListLB){

LNode*p,*q;p=LA;q=LB;

while(p->next!=LA)p=p->next;while(q->next!=LB)q=q->next;q->next=LA;p->next=LB->next;free(LB);return(LA);}算法實(shí)現(xiàn)如下：采用上面的方法，需要遍歷鏈表，找到表尾，其執(zhí)行時(shí)間是O(n)。兩個(gè)用尾指針標(biāo)識(shí)的循環(huán)單鏈表的連接1LinkListmerge2(LinkListR1,LinkListR2)2{

3Node*p;4p=R1->next;5R1->next=R2->next->next; 6free(R2->next);7R2->next=p;8returnR1;9}若在尾指針表示的單循環(huán)鏈表上實(shí)現(xiàn)，則只需要修改指針，無(wú)需遍歷，其執(zhí)行時(shí)間是O(1)。

借用一維數(shù)組來(lái)存儲(chǔ)線性鏈表。定義一個(gè)較大的結(jié)構(gòu)數(shù)組作為備用結(jié)點(diǎn)空間(即存儲(chǔ)池)，每個(gè)結(jié)點(diǎn)應(yīng)包含兩個(gè)域data域和next域，data域用來(lái)存放結(jié)點(diǎn)的數(shù)據(jù)信息，而next域不再是指針而是指示其后繼結(jié)點(diǎn)在結(jié)構(gòu)數(shù)組中的相對(duì)位置(即數(shù)組下標(biāo))，通常稱為游標(biāo)。我們把用這種方式實(shí)現(xiàn)的單鏈表叫做靜態(tài)鏈表(StaticLinkedList)。2.3.4靜態(tài)鏈表＃defineMaxsize=鏈表可能達(dá)到的最大長(zhǎng)度

typedefstruct{datatypedata;intnext;}Component,StaticList[Maxsize];StaticListS;intSL,AV; /*兩個(gè)頭指針變量*/1.初始化設(shè)space為靜態(tài)單鏈表的備用結(jié)點(diǎn)空間(即存儲(chǔ)池)。

StaticListspace;1voidinitial(int*AV)2{3intk;4for(k=0;k<Maxsize-1;k++)5space[k].next=k+1; /*連鏈*/6space[Maxsize-1].next=-1; /*標(biāo)記鏈尾*/7*AV=0; /*設(shè)置備用鏈表頭指針初值*/8}

2.分配結(jié)點(diǎn)分配結(jié)點(diǎn)是從備用鏈表摘下一個(gè)結(jié)點(diǎn)空間分配給待插入靜態(tài)鏈表中的元素。1intgetnode(int*AV)2{inti;3i=*AV;4*AV=space[*AV].next;5returni;6}3.結(jié)點(diǎn)回收結(jié)點(diǎn)回收是將下標(biāo)為k的空閑結(jié)點(diǎn)插入到備用鏈表AV中。1voidfreenode(int*AV,intk)2{space[k].next=*AV;3*AV=k;4}4.前插操作算法描述：

(1)先從備用單鏈表上取一個(gè)可用的結(jié)點(diǎn)；

(2)尋找第i-1個(gè)元素的位置。

(3)修改游標(biāo)域，實(shí)現(xiàn)插入。算法如下：1voidinsbefore(inti,intSL,datatypex,int*AV)2{/*AV為備用表*/3intj,k,m;4if(i<1||i>ListLength(SL)+1) /*插入位置不合理*/5{printf(″插入位置不合理!″);6returnERROR;7}8else9{j=getnode(AV);/*j為從備用表中取到的可用結(jié)點(diǎn)空間的下標(biāo)*/10space[j].data=x;11k=space[SL].next;/*k為靜態(tài)單鏈表的第一個(gè)元素的下標(biāo)值*/12for(m=1;m<i-1;m++) /*尋找第i-1個(gè)元素的位置k*/13k=space[k.].next;14space[j].next=space[k].next; /*修改游標(biāo)域，實(shí)現(xiàn)插入操作*/15space[k].next=j;16}17}5.刪除

(1)尋找第i-1個(gè)元素的位置，然后通過(guò)修改相應(yīng)的游標(biāo)域進(jìn)行刪除；

(2)將被刪除的結(jié)點(diǎn)空間連到可用靜態(tài)單鏈表中，實(shí)現(xiàn)回收。算法如下：1voiddelete(inti,int*Av,intSL)2{intj,k,m;3if(i<1||i>ListLength(SL))/*刪除位置不合理*/4{printf(″刪除位置不合理!″);5returnERROR;6}7else8{k=space[SL]->next; /*k為靜態(tài)單鏈表的第一個(gè)元素的下標(biāo)值*/9for(m=1,m<i-1;m++) /*尋找第i-1個(gè)元素的位置k*/10k=space[k]->next;11j=space[k]->next;12space[k]->next=space[j]->next;/*從靜態(tài)單鏈表中刪除第i個(gè)元素*/13freenode(AV,j) /*將第i個(gè)元素占據(jù)的空間回收，即將其連入備用表*/14}15}

在單鏈表的每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其前驅(qū)的指針域prior。這樣形成的鏈表中就有兩條方向不同的鏈，我們可稱之為雙(向)鏈表(DoubleLinkedList)。typedefstructDLnode{datatypedata;structDLnode*prior,*next;}DLNode,*DLinkList;2.3.5雙向鏈表雙鏈表的結(jié)構(gòu)定義如下:proirdatanext前驅(qū)指針域后繼指針域數(shù)據(jù)域p->prior->next=p=p->next->prior設(shè)指針p指向雙鏈表中某一結(jié)點(diǎn)，則有下式成立：由于在雙向鏈表中既有前向鏈又有后向鏈，尋找任一個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)變得非常方便。ai-1aiai+1P如圖所示：1.雙向鏈表的插入操作圖2.16雙向鏈表插入操作aiai+1PeSs->next=p->next;p->next->prior=s;p->next=s;s->prior=p;

intDlinkIns(DoubleListL,inti,ElemTypee)

算法實(shí)現(xiàn)：{…………

DNode*s,*p;s=(DNode*)malloc(sizeof(DNode));

if(s){s->data=e;s->next=p->next;p->next=s;s->next->prior=s;s->prior=p;return1;}

elsereturn0;

}

先檢查待插入的位置i是否合法，若位置i合法，則讓指針p指向它

2.雙向鏈表的刪除操作圖2.17雙向鏈表的刪除操作算法描述：ai-1aiai+1Pr

*e=p->data;p->next=r->next;r->next->prior=p;free(r);intDlinkDel(DoubleListL,inti,ElemType*e)【算法2.16雙向鏈表的刪除操作】算法實(shí)現(xiàn)：{

…………DNode*r=p->next;

*e=p->data;p->next=r->next;r->next->prior=p;

free(p);return1;}先檢查待插入的位置i是否合法，若位置i合法，則讓指針p指向它

設(shè)雙鏈表L=（a,b,c,d）,編寫一個(gè)算法,將鏈表轉(zhuǎn)換為L(zhǎng)=（b,a,c,d）。voidswap(DLinkListL){

DNode*p,*q,*h;h=L->next; p=h->next; q=h->prior;

h->next=p->next; p->next->prior=h;

____________________________________________________}Lhpqp->prior=q;p->next=h;h->proir=p;L->next=p;bc2.3.6

鏈表應(yīng)用舉例補(bǔ)充例1

已知單鏈表H，寫一算法將其倒置。算法思路：依次取原鏈表中的每個(gè)結(jié)點(diǎn)，采用頭插法插入到新鏈表中。voidreverse(LinklistH){

Linklistp;

p=H->next;

H->next=NULL;

while(p){q=p;p=p->next;q->next=H->next;H->next=q;}}

該算法只是對(duì)鏈表中順序掃描一邊即完成了倒置，所以時(shí)間性能為O(n)。算法實(shí)現(xiàn)如下:

補(bǔ)充例2

已知單鏈表L，寫一算法，刪除其重復(fù)結(jié)點(diǎn)。算法步驟：1p指向第一個(gè)結(jié)點(diǎn)2

從p的后繼開(kāi)始找重復(fù)結(jié)點(diǎn)3

找到重復(fù)結(jié)點(diǎn)，用r指向，刪除r4p指向下一個(gè)結(jié)點(diǎn)，重復(fù)步驟2，3voidpur_LinkList(LinkListH){LNode*p,*q,*r;p=H->next;if(p==NULL)return;

while(p->next){q=p;while(q->next){if(q->next->data==p->data){r=q->next;q->next=r->next;free(r);}elseq=q->next;}

p=p->next;

}}該算法的時(shí)間性能為O(n2)算法實(shí)現(xiàn)：利用A、B兩表有序的特點(diǎn)，依次進(jìn)行比較，將當(dāng)前值較小者摘下，插入到C表的頭部，得到的C表則為遞減有序的。補(bǔ)充例3

設(shè)有兩個(gè)單鏈表A、B，其中元素遞增有序，編寫算法將A、B歸并成一個(gè)按元素值遞減（允許有相同值）有序的鏈表C，要求用A、B中的原結(jié)點(diǎn)形成，不能重新申請(qǐng)結(jié)點(diǎn)。算法思路：1