數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計（第二版）課件 第2章 線性表

第二章線性表西安科技大學(xué)計算機學(xué)院張小艷數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計第一章復(fù)習(xí)1.教學(xué)目標(biāo)

通過線性表的學(xué)習(xí)，熟悉本書對每種數(shù)據(jù)結(jié)構(gòu)的描述方法，掌握線性表的定義、特點、典型算法及實際中的實用。2.教學(xué)要求①了解線性表的邏輯結(jié)構(gòu)特性。②熟練掌握線性表的兩種存儲結(jié)構(gòu)的描述方法。③熟練掌握線性表在順序存儲結(jié)構(gòu)上基本操作的實現(xiàn)④熟練掌握線性表在各種鏈?zhǔn)酱鎯Y(jié)構(gòu)上基本操作的實現(xiàn)；⑤能夠從時間和空間復(fù)雜度的角度比較線性表兩種存儲結(jié)構(gòu)的特點第二章線性表3．教學(xué)重點：①線性表順序存儲結(jié)構(gòu)的特點及基本操作。②線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點及基本操作。4．教學(xué)難點：①鏈表的概念。②鏈?zhǔn)酱鎯Y(jié)構(gòu)上算法的實現(xiàn)。第二章線性表2.1線性表的定義及邏輯結(jié)構(gòu)2.1.1線性表的定義例2-1中華傳統(tǒng)文化經(jīng)典:二十四節(jié)氣。二十四節(jié)氣蘊含著中華民族悠久的文化內(nèi)涵和歷史積淀。在漫長的農(nóng)耕社會中，二十四節(jié)氣發(fā)揮著重要作用，擁有豐富的文化內(nèi)涵。2.1線性表的定義及邏輯結(jié)構(gòu)2.1.1線性表的定義例2-1中華傳統(tǒng)文化經(jīng)典:二十四節(jié)氣。二十四節(jié)氣歌訣：

立春雨水漸，驚蟄蟲不眠，春分近清明，采茶谷雨前；

立夏小滿足，芒種大開鐮，夏至才小暑，大暑三伏天；

立秋處暑去，白露南飛雁，秋分寒露至，霜降紅葉染；

立冬小雪飄，大雪兆豐年，冬至數(shù)九日，小寒又大寒。

節(jié)氣歌唱出了節(jié)氣的順序。一年中的節(jié)氣羅列出來如下：【立春

雨水

驚蟄

春分

清明

谷雨

立夏

小滿

芒種

夏至

小暑

大暑

立秋

處暑

白露

秋分寒露霜降立冬小雪大雪冬至小寒大寒】2.1線性表的定義及邏輯結(jié)構(gòu)2.1.1線性表的定義線性表——是n個相同類型數(shù)據(jù)元素組成的有限序列。記作：（a1,a2,…，ai-1，ai，ai+1，…，an）

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

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

n為表長，n=0時，稱為空表。2.1線性表的定義及邏輯結(jié)構(gòu)

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

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

（a1,a2,…，ai-1，ai，ai+1，…，an）

從數(shù)據(jù)可以看到，我們學(xué)院在迅速發(fā)展。例2-3、

在校學(xué)生的健康信息表是一個線性表，表中每個學(xué)生的信息由學(xué)號、姓名、性別、年齡、班級和健康狀況等組成學(xué)號姓名性別年齡班級健康狀況1204101錢小明男19計科12健康1204108周維男18計科12一般1204111楊麗女20計科12健康1204112趙武男23計科12差………………1204135張麗女17計科12一般2.1線性表的定義及邏輯結(jié)構(gòu)

數(shù)據(jù)元素ai(1≤i≤n)只是一個抽象的符號，其具體含義在不同的情況下可以不同，可以是一個節(jié)氣，可以是一個數(shù)字，可以是一個學(xué)生信息。共同的特點就是：一個線性表中的數(shù)據(jù)元素必須屬于同一數(shù)據(jù)對象。（a1,a2,…，ai-1，ai，ai+1，…，an）

2.1線性表的定義及邏輯結(jié)構(gòu)

線性表是由n(n≥0)個數(shù)據(jù)類型相同的數(shù)據(jù)元素a1，a2，…，ai-1，ai，ai+1，…，an組成的有限序列，通常記為：表中相鄰元素間存在著順序關(guān)系，對于任一對相鄰結(jié)點

<ai，ai+1

>ai稱為ai+1的前驅(qū)，ai+1稱為ai的后繼對于ai，當(dāng)i=2,…,n時，有且僅有一個直接前趨ai-1；當(dāng)i=1,2,…,n-1時，有且僅有一個直接后繼ai+1；而a1是表中第一個元素，它沒有直接前趨；an是表中最后一個元素，它沒有直接后繼。（a1,a2,…，ai-1，ai，ai+1，…，an）

2.1線性表的定義及邏輯結(jié)構(gòu)

線性表是由n(n≥0)個數(shù)據(jù)類型相同的數(shù)據(jù)元素組成的有限序列，通常記為：<ai，ai+1

>ai稱為ai+1的前驅(qū)，ai+1稱為ai的后繼（a1,a2,…，ai-1，ai，ai+1，…，an）

2.1線性表的定義及邏輯結(jié)構(gòu)

“二十四節(jié)氣”中節(jié)氣的時間<ai，ai+1

>ai稱為ai+1的前驅(qū)，ai+1稱為ai的后繼（a1,a2,…，ai-1，ai，ai+1，…，an）

2.1線性表的定義及邏輯結(jié)構(gòu)

“每年學(xué)生人數(shù)”位置計算機學(xué)院學(xué)院從2008年到2013年擁有的學(xué)生人數(shù)的變化情況表：

(800，1000，2000，3600，3800，4500)<ai，ai+1

>ai稱為ai+1的前驅(qū)，ai+1稱為ai的后繼（a1,a2,…，ai-1，ai，ai+1，…，an）

2.1線性表的定義及邏輯結(jié)構(gòu)

“每個學(xué)生信息”表中數(shù)值順序很重要，也不能隨意變換。這是線性表的基本要求，就如同國家有法律，學(xué)校有規(guī)章制度，家庭有規(guī)則，我們必須遵守規(guī)則、遵紀(jì)守法。學(xué)號姓名性別年齡班級健康狀況1204101錢小明男19計科12健康1204108周維男18計科12一般1204111楊麗女20計科12健康1204112趙武男23計科12差………………1204135張麗女17計科12一般線性表的特點：線性表由同一類型的數(shù)據(jù)元素組成，每個ai必須屬于同一數(shù)據(jù)類型。線性表中的數(shù)據(jù)元素個數(shù)是有限的，表長就是表中數(shù)據(jù)元素的個數(shù)。存在唯一的“第一個”數(shù)據(jù)元素；存在唯一的“最后一個”數(shù)據(jù)元素。除第一個數(shù)據(jù)元素外，每個數(shù)據(jù)元素均有且只有一個前驅(qū)元素。除最后一個數(shù)據(jù)元素外，每個數(shù)據(jù)元素均有且只有一個后繼元素。（a1,a2,…，ai-1，ai，ai+1，…，an）

2.1線性表的定義及邏輯結(jié)構(gòu)

2.1.2線性表的基本操作

(1)初始化InitList(L)

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

(3)求長度LengthList(L)

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

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

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

(7)刪除操作DeleteList(L,i)2.1線性表的定義及邏輯結(jié)構(gòu)

（a1,a2,…，ai-1，ai，ai+1，…，an）

2.2線性表的順序存儲結(jié)構(gòu)2.2.1順序表

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

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

intlast;}

SeqList;

SeqList

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

順序存儲結(jié)構(gòu)三個重要屬性：存儲數(shù)據(jù)元素的空間：數(shù)組elem，用于存放數(shù)據(jù)元素。線性表的最大容量：MAXSIZE。線性表當(dāng)前長度：由last+1確定，last：最后一個數(shù)據(jù)元素在數(shù)組中的下標(biāo)。2.2線性表的順序存儲結(jié)構(gòu)細(xì)節(jié)決定成?。。?！線性表的順序存儲結(jié)構(gòu)可用C語言定義如下：#defineMAXSIZE100typedefstructLinear_list{datatypeelem[MAXSIZE];

intlast;}

SeqList;

SeqList

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

2.2線性表的順序存儲結(jié)構(gòu)細(xì)節(jié)決定成敗?。?！強調(diào)兩個問題：“數(shù)組的長度”和“線性表的長度”兩個概念。注意區(qū)分?jǐn)?shù)據(jù)元素的位序和數(shù)組的下標(biāo)。SeqList*L

；SeqList

L;表長：L.last+1數(shù)據(jù)元素：L.elem[0]~L.elem[L.last]表長：（*L）.last+1或L->last+1數(shù)據(jù)元素：L->elem[0]~L->elem[L->last]2.2線性表的順序存儲結(jié)構(gòu)#defineMAXSIZE100typedefstructLinear_list{datatypeelem[MAXSIZE];intlast;}

SeqList;

細(xì)節(jié)決定成?。。?！2.2.2順序表上插入與刪除操作的實現(xiàn)1初始化main(){inti,len;SeqListL;L.last=-1;scanf(“%d”,&len);for(i=0,i<len,i++){scanf(“%d”,&L.elem[i]);

L.last++;}………}2.2線性表的順序存儲結(jié)構(gòu)#defineMAXSIZE20typedefstructLinear_list{intelem[MAXSIZE];

intlast;}

SeqList;

2.2.2順序表上插入與刪除操作的實現(xiàn)1初始化main(){inti,len;SeqList*L;L.last=-1;scanf(“%d”,&len);for(i=0,i<len,i++){scanf(“%d”,&L->elem[i]);

L->last++;}………}2.2線性表的順序存儲結(jié)構(gòu)#defineMAXSIZE20typedefstructLinear_list{intelem[MAXSIZE];

intlast;}

SeqList;

2.2.2順序表上插入與刪除操作的實現(xiàn)1初始化SeqList*InitList(){SeqList*L;L=(SeqList*)malloc(sizeof(SeqList));L->last=-1;returnL;}主函數(shù)對初始化函數(shù)的調(diào)用：main(){inti,len;SeqList*L;L=InitList();scanf(“%d”,&len);for(i=0,i<len,i++){scanf(“%d”,&L->elem[i]);

L->last++;}……………}2.2線性表的順序存儲結(jié)構(gòu)本算法的主要運算是比較。2按值查找intLocatList(SeqList*L,datatypex){inti=0;

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

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

}平均時間復(fù)雜度：

假設(shè)查找每個元素的概率相等：1/n;查找第i個的比較次數(shù)：i平均比較次數(shù)為:

(1+2+3+4+…+n)/n=(n+1)/2，時間復(fù)雜度為O(n)。2.2線性表的順序存儲結(jié)構(gòu)最好的比較次數(shù)為1次，最差的是比較n次。3插入運算線性表的插入是指在表的第i個位置上插入一個值為x的新元素,i的取值范圍為1≤i≤n+1。③修改last指針（相當(dāng)于修改表長），

使之仍指向最后一個元素。步驟：①將ai～an

順序向下移動，

為新元素讓出位置；②將x置入空出的第i個位置；2.2線性表的順序存儲結(jié)構(gòu)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(″位置錯″);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}算法實現(xiàn)：算法設(shè)計時請注意：注意數(shù)據(jù)的移動方向檢驗插入位置的有效性：1≤i≤n+1在表滿的情況下不能再做插入2.2線性表的順序存儲結(jié)構(gòu)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(″位置錯″);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}算法實現(xiàn)：時間復(fù)雜度分析：2.2線性表的順序存儲結(jié)構(gòu)插入位置i，從ai

到an都要向下移動一個位置，共需要移動n-i+1個元素，而i的取值范圍為1≤i≤n+1，即有n+1個位置可以插入。設(shè)在第i個位置上插入元素的概率為Pi，則平均移動數(shù)據(jù)元素的次數(shù)為假設(shè)在每個位置插入元素的概率相等，Pi?=?1/(n+1)時間復(fù)雜度為：O（n）

時間性能分析：

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

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

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

，再做刪除。④注意數(shù)據(jù)的移動方向。算法如下：1intDeleteList(SeqList*Lp,inti)2{intj;if(i<1||i>Lp->last+1){printf(″不存在第i個元素″);5return(0);6}7for(j=i;j<=Lp->last;j++)Lp->elem[j-1]=Lp->elem[j];Lp->last--;10return(1); /*刪除成功*/11}/*檢查刪除位置的合法性*//*向上移動*//*刪除成功*/2.2線性表的順序存儲結(jié)構(gòu)1intDeleteList(SeqList*Lp,inti)2{intj;if(i<1||i>Lp->last+1){printf(″不存在第i個元素″);5return(0);6}7for(j=i;j<=Lp->last;j++)Lp->elem[j-1]=Lp->elem[j];Lp->last--;10return(1); /*刪除成功*/11}2.2線性表的順序存儲結(jié)構(gòu)算法性能分析：時間主要消耗在移動表中元素上刪除第i個元素時，其后面的元素ai+1～an都要向上移動一個位置，共移動了n-i個元素，所以平均移動數(shù)據(jù)元素的次數(shù)：等概率情況下，Ｐi＝

1/n則平均移動數(shù)據(jù)元素的次數(shù)為時間復(fù)雜度為：O（n）2.2線性表的順序存儲結(jié)構(gòu)線性表順序表示的優(yōu)缺點對比優(yōu)點缺點無需為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲空間可方便地隨機存取表中的任一元素插入或刪除需要移動大量的數(shù)據(jù)元素當(dāng)線性表長度變化較大時難以確定存儲空間的容量造成存儲空間浪費2.2.3順序表應(yīng)用舉例例2-4利用兩個線性表La和Lb分別表示兩個集合A和B，現(xiàn)要求一個新的集合A?=?A∪B。假設(shè)集合中的數(shù)據(jù)元素屬于整型數(shù)據(jù)。

算法思路：擴大線性表La，將存在于線性表Lb中而不在La中的數(shù)據(jù)元素加入到線性表La中。逐一取出Lb中的元素，判斷是否在La中，若不在，則插入。由于La是集合，數(shù)據(jù)元素之間沒有順序關(guān)系，所以插入時，可以插入到La的最后一個元素后面，這樣，就不用移動大量數(shù)據(jù)元素。A=(23,45,78,91,55)B=(47,23,8,55)A∪B=(23,45,78,91,55,47,8)2.2線性表的順序存儲結(jié)構(gòu)2.2.3順序表應(yīng)用舉例A=(23,45,78,91,55)B=(47,23,8,55)A∪B=(23,45,78,91,55,47,8)2.2線性表的順序存儲結(jié)構(gòu)#defineMAXSIZE20typedefstructLinear_list{intelem[MAXSIZE];

intlast;}

SeqList;

2.2.3順序表應(yīng)用舉例A=(23,45,78,91,55)B=(47,23,8,55)A∪B=(23,45,78,91,55,47,8)2.2線性表的順序存儲結(jié)構(gòu)#defineMAXSIZE20typedefstructLinear_list{intelem[MAXSIZE];

intlast;}

SeqList;

472.2.3順序表應(yīng)用舉例A=(23,45,78,91,55)B=(47,23,8,55)A∪B=(23,45,78,91,55,47,8)2.2線性表的順序存儲結(jié)構(gòu)#defineMAXSIZE20typedefstructLinear_list{intelem[MAXSIZE];

intlast;}

SeqList;

847算法如下：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)/*存儲空間足夠*/12La->elem[++(La->last)]=e;/*插入到La的最后*/13}14}語句6循環(huán)次數(shù)是Lb的表長，語句9循環(huán)次數(shù)最多是La的表長，此算法的時間復(fù)雜度為O(ListLength(La)?×?ListLength(Lb))。2.2線性表的順序存儲結(jié)構(gòu)例2-5有順序表A和B，其元素均按從小到大的升序排列，編寫一個算法將它們合并成一個順序表C，要求C的元素也是從小到大的升序排列。例如A?=?(2,2,3),B?=?(1,3,3,4)，則C?=?(1,2,2,3,3,3,4)。

算法思路：依次掃描A和B的元素，比較當(dāng)前的元素的值，將較小值的元素賦給C，如此直到一個線性表掃描完畢，然后將未完的那個順序表中余下部分賦給C即可。C的容量要能夠容納A、B兩個線性表。設(shè)表C是一個空表，設(shè)兩個指針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)行下去，直到其中一個表被掃描完畢，然后再將未掃描完的表中剩余的所有元素放到表C中。2.2線性表的順序存儲結(jié)構(gòu)例2-5有順序表A和B，其元素均按從小到大的升序排列，編寫一個算法將它們合并成一個順序表C，要求C的元素也是從小到大的升序排列。A?=?(2,2,3),B?=?(1,3,3,4)，則C?=?(1,2,2,3,3,3,4)。

初始狀態(tài)：C為空表；i=0;j=0;k=0;A-lastB-lastijk2.2線性表的順序存儲結(jié)構(gòu)例2-5有順序表A和B，其元素均按從小到大的升序排列，編寫一個算法將它們合并成一個順序表C，要求C的元素也是從小到大的升序排列。A?=?(2,2,3),B?=?(1,3,3,4)，則C?=?(1,2,2,3,3,3,4)。初始狀態(tài)：C為空表；i=0;j=0;k=0;A-lastB-lastijk2.2線性表的順序存儲結(jié)構(gòu)若A.elem[i]?>?B.elem[j]，則將B.elem[j]插入到表C中；若A.elem[i]≤B.elem[j]，則將A.elem[i]插入到表C中；C->last++

如此進(jìn)行下去，直到其中一個表被掃描完畢，然后再將未掃描完

的表中剩余的所有元素放到表C中。1例2-5有順序表A和B，其元素均按從小到大的升序排列，編寫一個算法將它們合并成一個順序表C，要求C的元素也是從小到大的升序排列。A?=?(2,2,3),B?=?(1,3,3,4)，則C?=?(1,2,2,3,3,3,4)。初始狀態(tài)：C為空表；i=0;j=0;k=0;A-lastB-lastijk2.2線性表的順序存儲結(jié)構(gòu)1223333344若A.elem[i]?>?B.elem[j]，則將B.elem[j]插入到表C中；若A.elem[i]≤B.elem[j]，則將A.elem[i]插入到表C中；C->last++

如此進(jìn)行下去，直到其中一個表被掃描完畢，然后再將未掃描完

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

劃分前23456103576185620劃分后201810623453576562.2線性表的順序存儲結(jié)構(gòu)線性表順序表示的優(yōu)點：①

無需為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲空間（因為邏輯上相鄰的元素其存儲的物理位置也是相鄰的）；

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

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

①

插入或刪除運算不方便，除表尾位置外，在其它位置上進(jìn)行插入或刪除操作都必須移動大量的數(shù)據(jù)元素，其效率較低；2.2線性表的順序存儲結(jié)構(gòu)

線性表的順序存儲結(jié)構(gòu)的特點是邏輯關(guān)系上相鄰的兩個元素在物理位置上也相鄰，因此可以隨機存取表中任一元素，它的存儲位置可用一個簡單、直觀的公式來表示。然而，對順序表進(jìn)行插入、刪除操作時需要通過移動數(shù)據(jù)元素來實現(xiàn)，影響了運行效率。

我們就要尋求更好的存儲方式，就像我們平時在解決問題時需要學(xué)會變通，不能一條道兒走到黑，如果犯了錯誤，改正就好，常言道：“知錯就改，善莫大焉”。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)用一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素。

這組存儲單元連續(xù)不連續(xù)都可以。為了表示數(shù)據(jù)元素ai和其直接后繼ai+1之間的邏輯關(guān)系還需要存儲一個指示其后繼的信息。指針域數(shù)據(jù)域結(jié)點在順序表中，只需要存儲數(shù)據(jù)元素，其邏輯關(guān)系-物理位置相鄰就能體現(xiàn)在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，除了存儲數(shù)據(jù)元素。單鏈表2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表(a1,a2,a3,a4,a5,a6,a7,a8)對應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)0500a1a1的地址為：05002.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)a202000510a2的存儲地址通過a1的指針域next獲得（0200）2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)051005100900a3的存儲地址通過a2的指針域next獲得（0510）2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)090009000910a4的存儲地址可以通過a3的指針域next獲得（0900）2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)把鏈表中第一個元素的地址存放在一個指針變量中，我們稱這個指針變量為鏈表的頭指針。頭指針H05002.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)為了表示數(shù)據(jù)元素ai和其直接后繼ai+1之間的邏輯關(guān)系還需要存儲一個指示其后繼的信息。指針域數(shù)據(jù)域在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，除了存儲數(shù)據(jù)元素。含有n個數(shù)據(jù)元素的線性表通過每個結(jié)點的指針域拉成了一個“鏈子”，稱之為單鏈表?！瓎捂湵?.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)H作為線性表的一種存儲結(jié)構(gòu)，我們關(guān)心的是結(jié)點間的邏輯結(jié)構(gòu)，而對每個結(jié)點的實際地址并不關(guān)心，所以通常的單鏈表可以抽象的表示成這樣一種形式：…………H∧2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

指針域數(shù)據(jù)域LNode是結(jié)構(gòu)體結(jié)點類型；LinkList是結(jié)構(gòu)體結(jié)點指針類型。用頭指針來標(biāo)識一個單鏈表，如單鏈表L、單鏈表H。H…………H單鏈表-存儲結(jié)構(gòu)C語言描述2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)LinkListH；H是一個結(jié)構(gòu)體指針，即單鏈表的頭指針。typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

H==NULL為真。

單鏈表-存儲結(jié)構(gòu)C語言描述2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)頭結(jié)點的數(shù)據(jù)域可以不存放任何數(shù)據(jù)，也可以存放鏈表的結(jié)點個數(shù)的信息頭指針H指向頭結(jié)點的存儲位置。這樣的單鏈表我們稱之為帶頭結(jié)點的單鏈表。在線性鏈表的第一結(jié)點之前附設(shè)一個結(jié)點，稱為頭結(jié)點?！璈頭結(jié)點頭指針2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)一個帶頭結(jié)點的空鏈表

H->next==NULL

單鏈表H不是空表，可以通過頭指針訪問表中所有結(jié)點。假設(shè)p=H->nextp->data=a1p->next->data=a2H頭結(jié)點頭指針…………Hpp->next2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)假設(shè)q是指向線性表中第i個結(jié)點的指針，……H那么q->next是指向第i+1個數(shù)據(jù)元素(結(jié)點ai+1)的指針。qq->next2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

單鏈表是一種動態(tài)存儲結(jié)構(gòu)在C語言中，可以利用malloc函數(shù)向系統(tǒng)申請存儲空間，這個函數(shù)返回存儲區(qū)的首地址。p=(LinkList)malloc(sizeof(LNode));free(p)p2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

1LinkListGetlist(LinkListL,inti)2{intj；3LNode*p；4p=L；j=0；

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

7j++；}8if（i==j）returnp；

9else10returnNULL；

11}取第i個數(shù)據(jù)元素操作采用“數(shù)”結(jié)點的方法，從第一個開始“數(shù)”，一直“數(shù)”到第i個?！璈pj=02.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)1LinkListGetlist(LinkListL,inti)2{intj；3LNode*p；4p=L；j=0；

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

7j++；}8if（i==j）returnp；

9else10returnNULL；

11}取第i個數(shù)據(jù)元素操作采用“數(shù)”結(jié)點的方法，從第一個開始“數(shù)”，一直“數(shù)”到第i個。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)……Hpj=0--------------------------------------------------------------p=p->nextj++pj=ip……Hpj=i2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)1LinkListGetlist(LinkListL,inti)2{intj；3LNode*p；4p=L；j=0；

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

7j++；}8if（i==j）returnp；

9else10returnNULL；

11}typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)1LinkListGetlist(LinkListL,inti)2{intj；3LNode*p；4p=L；j=0；

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

7j++；}8if（i==j）returnp；

9else10returnNULL；

11}……Hj=0--------------p=p->nextj++j=1pp1LinkListGetlist(LinkListL,inti)2{intj；3LNode*p；4p=L；j=0；

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

7j++；}8if（i==j）returnp；

9else10returnNULL；

11}……Hj=0------------------------------------------------------------------------------------------------------------p=p->nextj++j=npp2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)從第一個元素開始“數(shù)”，一直“數(shù)”到最后一個結(jié)點(p->next=NULL)。(1)設(shè)一個臨時變量p指向頭結(jié)點，計數(shù)器j等于0。(2)當(dāng)p->next!=NULL時，循環(huán)：指針p后移，指向它的直接后繼結(jié)點，計數(shù)器j加1.循環(huán)停止時返回J就是鏈表長度?！璈j=0------------------------------------------------------------------------------------------------------------p=p->nextj++j=np單鏈表-求單鏈表長度2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)單鏈表的存儲結(jié)構(gòu)描述用C語言如下：typedefstructnode{

datatypedata;structnode*next;

}LNode，*LinkList；

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

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

LinkListp;

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

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

不帶頭結(jié)點的鏈表和帶頭結(jié)點的鏈表的區(qū)別不帶頭結(jié)點帶頭結(jié)點鏈表為空：L==NULL為真鏈表的第一個數(shù)據(jù)元素由L指向在第一個元素之前插入一個元素和刪除第一個元素要單獨處理，和在其他位置插入、刪除操作不同鏈表為空：L->next==NULL為真鏈表的第一個數(shù)據(jù)元素由L->next指向插入、刪除操作統(tǒng)一2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.2單鏈表上的基本運算intInitList(LinkList*h){if(

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

)return(0);(*h)->next=NULL;return(1);}1.初始化初始化操作即建立一個空表。H∧2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)typedefstructnode{

datatypedata;structnode*next;

}LNode，*LinkList；

1建立單鏈表

建立過程是一個動態(tài)生成的過程，即從“空表”起，依次建立結(jié)點，并逐個插入鏈表１頭插法２尾插法逆序創(chuàng)建鏈表順序創(chuàng)建鏈表2.3.2單鏈表上的基本運算typedefstructnode{

datatypedata;structnode*next;

}LNode，*LinkList；

2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)1）用頭插法建立單鏈表的算法Step0:

Step1:Step2:Step3:在鏈表的頭部插入，讀入數(shù)據(jù)的順序和線性表的邏輯順序是相反的申請一塊空間，S指向，讀入S->data;將L->next的值賦給S->next

將L->next的值改為S建立只有頭結(jié)點的單鏈表LS10L∧∧L=(Linklist)malloc(sizeof(LNode));L->next=NULL;s=(Linklist)malloc(sizeof(Lnode))s->data=c;s->next=L->next;L->next=s;輸入數(shù)據(jù)：10,9,8,7,6,5,4,3,2,12.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)1）用頭插法建立單鏈表的算法Step0:

Step1:Step2:Step3:在鏈表的頭部插入，讀入數(shù)據(jù)的順序和線性表的邏輯順序是相反的申請一塊空間，S指向，讀入S->data;將L->next的值賦給S->next

將L->next的值改為S建立只有頭結(jié)點的單鏈表L10L∧∧S9s=(Linklist)malloc(sizeof(Lnode))s->data=c;s->next=L->next;L->next=s;2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)1）用頭插法建立單鏈表的算法Step0:

Step1:Step2:Step3:在鏈表的頭部插入，讀入數(shù)據(jù)的順序和線性表的邏輯順序是相反的申請一塊空間，S指向，讀入S->data;將L->next的值賦給S->next

將L->next的值改為S建立只有頭結(jié)點的單鏈表L10L∧∧91210

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

18}19returnL;20}2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2）尾插法建表算法中必須維持一個始終指向已建立的鏈表表尾的指針。L=(Linklist)malloc(sizeof(LNode));L->next=NULL;r->next=s;r=s;s=(Linklist)malloc(sizeof(LNode));s->data=c;2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)1LinklistCreateFromHead()2{LinkListL;3LNode*s;4charc;5intflag=1;6L=(Linklist)malloc(sizeof(LNode)); /*為頭結(jié)點分配存儲空間*/7L->next=NULL; /*建帶頭結(jié)點的空鏈表*/8r=L; /*尾指針r指向表尾*/9while(flag)10{c=getchar();11if(c!='$')12{s=(Linklist)malloc(sizeof(LNode));/*為讀入的字符分配存儲空間*/13s->data=c; /*數(shù)據(jù)域賦值*/14r->next=s; /*插入到表尾*/15r=s;16}17else18{flag=0;19r->next=NULL;20}21}22returnL;23}2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2)按值查找

算法描述：查找過程從單鏈表的頭指針指向的頭結(jié)點出發(fā)，順著鏈表逐個將結(jié)點的值和給定值e作比較。若找到，返回找到的值為e的結(jié)點的存儲位置，否則，返回空。要查找結(jié)點值等于給定值的結(jié)點1210

∧…L2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)1LinkListLocate(LinkListL,chare)2{LinkListp;3p=L->next;/*從表中第一個結(jié)點比較*/4while(p!=NULL&&p->data!=e)

5p=p->next;6returnp;7}算法實現(xiàn)如下：由于線性鏈表失去了隨機存取的特性，所以按序號查找算法、按值查找算法的時間復(fù)雜度均為O(n)。1210

∧…L2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

a1aiai-1…an∧…

Lpreess->next=pre->nextpre->next=s根本不用驚動其他結(jié)點，這兩句的順序可不可以交換？單鏈表—插入操作typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

press->next=pre->nextpre->next=s一定要注意：這兩句的順序不能反。a1aiai-1…an∧…e單鏈表—插入操作typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

插入操作是要完成：在單鏈表L中第i個位置之前插入一個數(shù)據(jù)元素e。這里是在單鏈表的第i個位置之前插入，單鏈表中每個結(jié)點只有指向后繼的指針，所以要找到指向第i-1個結(jié)點的指針。a1aiai-1…an∧…

Lpreess->next=pre->nextpre->next=s單鏈表—插入操作typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

首先：在單鏈表中找到第i-1個結(jié)點并由指針pre指向。然后：申請一個新的結(jié)點并由指針s指向，將e賦給s的數(shù)據(jù)域；最后：修改指針、插入。也就是：s->next=pre->next；pre->next=s。a1aiai-1…an∧…

Lpreess->next=pre->nextpre->next=s單鏈表—插入操作typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

1intInsList(LinkListL,inti,chare)2{3LinkListpre,s;4intk;5pre=L;k=0;6while(pre!=NULL&&k<i-1)7{pre=pre->next;8k=k+1;9}10if(k!=i-1)11{printf(″插入位置不合理!″);12returnERROR;13}14s=(LinkList)malloc(sizeof(LNode));15s->data=e;16s->next=pre->next;17pre->next=s;18returnOK;19}∧……a1ai-1aiai+1anL

k=0

prep-p->nextk=k+1

prek=i-1

preks

e單鏈表—插入操作typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

1intInsList(LinkListL,inti,chare)2{3LinkListpre,s;4intk;5pre=L;k=0;6while(pre!=NULL&&k<i-1)7{pre=pre->next;8k=k+1;9}10if(k!=i-1)11{printf(″插入位置不合理!″);12returnERROR;13}14s=(LinkList)malloc(sizeof(LNode));15s->data=e;16s->next=pre->next;17pre->next=s;18returnOK;19}單鏈表—插入操作

pres

ek=i-1∧a1ai-1aiai+1anL……typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

插入操作是要完成：在單鏈表L中第i個位置之前插入一個數(shù)據(jù)元素e。這里是在單鏈表的第i個位置之前插入，單鏈表中每個結(jié)點只有指向后繼的指針，所以要找到指向第i-1個結(jié)點的指針。a1aiai-1…an∧…

Lpreess->next=pre->nextpre->next=s單鏈表—插入操作（不帶頭結(jié)點）s=(LinkList)malloc(sizeof(LNode));s->data=e;typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

插入操作是要完成：在單鏈表L中第i個位置之前插入一個數(shù)據(jù)元素e。i=1a1aiai-1…an∧…

Less->next=LL=s單鏈表—插入操作（不帶頭結(jié)點）s=(LinkList)malloc(sizeof(LNode));s->data=e;typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

a1aiai-1…an∧…

Lai+1一個單鏈表L，pre指向其中一個結(jié)點。先記下來待刪結(jié)點，q=pre->next;修改指針：pre->next=q->next;如果后面還需要用刪除結(jié)點的數(shù)據(jù)信息，可以將q->data返回。最后要將q結(jié)點釋放。

preqpre->next=q->next單鏈表—刪除操作typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

a1aiai-1…an∧…

Lai+1首先：需要在單鏈表中找到第i-1個結(jié)點，并由指針pre指向。然后：用q指針指向待刪結(jié)點:q=pre->next，如果要用q的數(shù)據(jù)域，可記錄下來：e=q->data。修改指針刪除結(jié)點q,pre->next=q->next。

preqpre->next=q->next刪除操作是要完成：在單鏈表L中，刪除第i個數(shù)據(jù)元素。最后：釋放q結(jié)點。e=q->data單鏈表—刪除操作typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

1intDelList(LinkListL,inti,char*e)2{3LinkListpre,q;4intk;5pre=L;k=0;6while(pre->next!=NULL&&k<i-1)7{pre=pre->next;8k=k+1;9}10if(k!=i-1)11{printf(″刪除結(jié)點的位置i不合理!″);12returnERROR;13}14q=pre->next;15pre->next=q->next; 16*e=q->data;17free(q);18returnOK;19}∧……a1ai-1aiai+1an

L

k=0

prep-p->nextk=k+1

prek=i-1

prekqpre->next=q->nexte=q->data單鏈表—刪除操作typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

a1aiai-1…an∧…

Lai+1首先：需要在單鏈表中找到第i-1個結(jié)點，并由指針pre指向。然后：用q指針指向待刪結(jié)點:q=pre->next，如果要用q的數(shù)據(jù)域，可記錄下來：e=q->data。修改指針刪除結(jié)點q,pre->next=q->next。

preqpre->next=q->next刪除操作是要完成：在單鏈表L中，刪除第i個數(shù)據(jù)元素。最后：釋放q結(jié)點。e=q->data單鏈表—刪除操作(不帶頭結(jié)點）typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

a1aiai-1…an∧…

Lai+1i=1L=L->next刪除操作是要完成：在單鏈表L中，刪除第i個數(shù)據(jù)元素。e=L->data單鏈表—刪除操作(不帶頭結(jié)點）頭指針H指向鏈表附加頭結(jié)點的存儲位置，付出一個頭結(jié)點的存儲空間來簡化插入、刪除操作。這就如同蘇心所說“哪有什么歲月靜好，不過是有人替你負(fù)重前行”一樣啊。typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

插入刪除算法分析：

刪除算法中的循環(huán)條件(pre->next!?=?NULL&&k?<?i-1)前插算法中的循環(huán)條件(pre!?=?NULL&&k?<?i-1)因為前插時的插入位置有n+1個(n為當(dāng)前單鏈表中數(shù)據(jù)元素的個數(shù))。i=n+1是指在第n+1個位置前插入，即在單鏈表的末尾插入。

而刪除操作中刪除的合法位置只有n個，若使用與前插操作相同的循環(huán)條件，則會出現(xiàn)指針指空的情況，使刪除操作失敗。在線性鏈表中插入、刪除元素雖然不需要移動數(shù)據(jù)元素，但需要查找插入、刪除的位置，所以時間復(fù)雜度仍然是Ｏ(n)。1intInsList(LinkListL,inti,chare)2{3LinkListpre,s;4intk;5pre=L;k=0;6while(pre!=NULL&&k<i-1)7{p