第二章線性表簡(jiǎn)介：最簡(jiǎn)單、最常用的數(shù)據(jù)結(jié)構(gòu)，線性表的順序表示和實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線性表的應(yīng)用實(shí)例---

一元多項(xiàng)式的表示和運(yùn)算重點(diǎn)：線性表的基本概念和術(shù)語(yǔ)線性表的順序表示和鏈?zhǔn)奖硎痉椒捌渖系幕静僮飨嚓P(guān)算法的時(shí)間復(fù)雜度分析難點(diǎn)：線性表的鏈?zhǔn)奖硎竞突静僮?/p>

線性結(jié)構(gòu)的特點(diǎn)存在唯一的一個(gè)被稱作"第一個(gè)"的數(shù)據(jù)元素；存在唯一的一個(gè)被稱作"最后一個(gè)"的數(shù)據(jù)元素；相鄰數(shù)據(jù)元素之間存在序偶關(guān)系，若將線性表記為（a1,a2,…,ai-1,ai,ai+1,…,an）表中ai-1領(lǐng)先于ai,稱ai-1

是ai的直接前驅(qū)元素；

ai+1

是ai的直接后繼元素。除第一個(gè)之外，線性表中的每個(gè)數(shù)據(jù)元素均只有一個(gè)直接前驅(qū)；除最后一個(gè)之外，線性表中每個(gè)數(shù)據(jù)元素均只有一個(gè)直接后繼；2.1線性表類型定義線性表(LinearList):n個(gè)數(shù)據(jù)元素的有限序列。表長(zhǎng)空表位序記錄文件如:學(xué)生健康情況表：總之：線性表的數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)組成。同一線性表中的元素必定具有相同特性姓名學(xué)號(hào)性別年齡數(shù)學(xué)王小林790631男1898陳紅790632女2078……..……..…….…….….關(guān)非790632女2078線性表的操作：例2-1需求：線性表LA和LB分別表示集合A和B，求A=A∪B。解決方案：把存在于LB且不存在于LA的元素插入LA。算法描述：

voidunion(List&La，ListLb) {La_len=ListLength(La);Lb_len=ListLength(Lb); for(i=1;i<=lb_len;i++) {

//①?gòu)腖b中依次取得每一個(gè)元素

//②與La的每一個(gè)元素比較

//③如不存在，則插入之

}}//union

voidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=lb_len;i++){

GetElem(Lb,i,e)

if(!LocateElem(La,e,equal);

ListInsert(La,++La_len,e);}}//union時(shí)間復(fù)雜度為O(ListLength(LA)×ListLength(LB))無序線性表合并的算法需求：線性表LA和LB的數(shù)據(jù)元素按值非遞減有序，歸并LA和LB為L(zhǎng)C，LC元素仍按值非遞減有序排列。解決方案:設(shè)指針i和j分別指向LA和LB的元素，比較i和j所指當(dāng)前元素ai和bj，選min(ai,bj)插入為L(zhǎng)C的元素算法框架：

voidMergeList(ListLa，ListLb，List&Lc){InitList(Lc);

La_len=ListLength(La);Lb_len=ListLength(Lb);while((i<=la_len)&&(j<=lb_len)){//①分別獲取LA和LB的元素比較，將值小的插入LC}//②將LA或LB的剩余數(shù)據(jù)元素，插入LC中。

}//MergeList線性表應(yīng)用：例2-2有序線性表合并的算法

voidMergeList(ListLa，ListLb，List&Lc){InitList(Lc);

La_len=ListLength(La);Lb_len=ListLength(Lb);while((i<=la_len)&&(j<=lb_len)){GetElem(La,i,ai);GetElem(Lb,j,bj);

if(ai<=bj)//La中當(dāng)前指針?biāo)冈刂递^小

{ListInsert(Lc,++k,ai);++i;}//將La中當(dāng)前指針?biāo)冈夭迦隠c，指針后移一個(gè)位置

else{ListInsert(Lc,++k,bj);++j;}//將Lb中當(dāng)前指針?biāo)冈夭迦隠c，指針后移一個(gè)位置

}while(i<=La_len)//如果當(dāng)前La中有剩余元素

{GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}//獲取La中元素直接插入Lcwhile(j<=Lb_len)

//如果當(dāng)前Lb中有剩余元素

{GetElem(Lb,i++,bj);ListInsert(Lb,++k,bj);}

//獲取Lb中元素直接插入Lc}//MergeList時(shí)間復(fù)雜度：O(ListLength(LA)+ListLength(LB))；2.2線性表的順序表示和實(shí)現(xiàn)線性表的順序表示：用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。特點(diǎn):邏輯上相鄰的數(shù)據(jù)元素在物理位置上相鄰。線性表順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu) 設(shè)線性表的每個(gè)元素占l個(gè)存儲(chǔ)單元，LOC(a1)為線性表的起始地址，bb+l……b+(i-1)*l……b+(n-1)*l存儲(chǔ)地址12…i…n位序內(nèi)存狀態(tài)an……ai……a2a1線性表順序表示的實(shí)現(xiàn)線性表的順序?qū)崿F(xiàn)：動(dòng)態(tài)分配的一維數(shù)組線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)#defineLIST_INIT_SIZE100//線性表存儲(chǔ)空間的初始分配量#defineLISTINCREMENT10//線性表存儲(chǔ)空間的分配增量typedef

struct{Elemtype*elem;//存儲(chǔ)空間的基地址。

intlength;//當(dāng)前長(zhǎng)度

int

listsize;

//當(dāng)前分配的存儲(chǔ)容量}Sqlist;基本操作的實(shí)現(xiàn)舉例：InitList_Sq(Sqlist&L)順序表的基本操作—插入線性表的插入操作：原線性表:(a1,…ai-1,ai,…,an)插入后:(a1,…ai-1,x,ai,…,an)

插入的情況有兩種：

a、不移動(dòng)元素：在表尾插入（i=n+1）

b、移動(dòng)元素：在第i(1≤i≤n+1）個(gè)數(shù)據(jù)元素前插入需將第n個(gè)到第i個(gè)數(shù)據(jù)元素共

個(gè)依次向后移動(dòng)一個(gè)位置。操作演示

1、在表中任意位置插入新的數(shù)據(jù)元素

2、表滿情況下，在表尾插入新的數(shù)據(jù)元素n-i+1順序表插入操作的時(shí)間復(fù)雜度分析在順序表中某個(gè)位置插入元素的時(shí)間耗費(fèi)移動(dòng)元素移動(dòng)元素的個(gè)數(shù)取決于插入元素位置。設(shè)pi是在第i個(gè)元素之前插入一個(gè)元素的概率，不失一般性，假定在線性表的任何位置上插入元素都是等概率的

在長(zhǎng)度是n的線性表中插入一個(gè)元素時(shí)所需移動(dòng)元素次數(shù)的數(shù)學(xué)期望值(平均次數(shù))為

pi=1/(n+1)

線性表的插入算法的時(shí)間復(fù)雜度為O(n)

Eis=∑pi×(n-i+1)=n/2n+1i=1順序表的基本操作—?jiǎng)h除線性表的刪除操作:刪除前:(a1,…ai-1,ai,ai+1,…,an)刪除后:(a1,…ai-1,ai+1,…,an)。刪除的情況有兩種：

a、不移動(dòng)元素：在表尾刪除i=nb、移動(dòng)元素：刪除第i（1≤i≤n）個(gè)數(shù)據(jù)元素需將第i+1到第n個(gè)數(shù)據(jù)元素共

個(gè)依次向前移動(dòng)一個(gè)位置。操作演示

1、在非表尾刪除n-i順序表刪除操作的時(shí)間復(fù)雜度分析

在順序表中某個(gè)位置刪除元素的時(shí)間耗費(fèi)移動(dòng)元素移動(dòng)元素的個(gè)數(shù)取決于刪除元素的位置。假設(shè)qi是刪除第i個(gè)元素的概率，不失一般性，假定在線性表的任何位置上刪除元素都是等概率的qi=1/n

在長(zhǎng)度為n的線性表中刪除一個(gè)元素時(shí)所需移動(dòng)元素次數(shù)的數(shù)學(xué)期望值

線性表的刪除算法的時(shí)間復(fù)雜度為O(n)。Edl=∑qi×(n-i)=(n-1)/2n+1i=1順序表的歸并無序順序表歸并算法：類似于算法2.1時(shí)間復(fù)雜度：O(ListLength(LA)×ListLength(LB))有序順序表的歸并算法：算法2.7時(shí)間復(fù)雜度：O(ListLength(LA)+ListLength(LB))總之，以線性表表示集合并進(jìn)行集合的各種運(yùn)算，應(yīng)先對(duì)表中元素進(jìn)行排序。順序表小結(jié)特點(diǎn)：邏輯關(guān)系上相鄰的兩個(gè)元素在物理位置上也相鄰優(yōu)點(diǎn)：可以隨機(jī)存取表中任一元素，它的存儲(chǔ)位置可用一個(gè)簡(jiǎn)單、直觀的公式表示。缺點(diǎn)：線性表在作插入和刪除操作時(shí)，需要移動(dòng)大量元素,浪費(fèi)大量時(shí)間。線性表的順序表示:動(dòng)態(tài)分配的一維數(shù)組思考題：設(shè)順序表va中數(shù)據(jù)元素遞增有序，試寫一算法，將x插入到順序表中的適當(dāng)位置，以保持該表的有序性。針對(duì)一個(gè)具體應(yīng)用如何寫程序認(rèn)清具體問題的邏輯結(jié)構(gòu)選定其存儲(chǔ)結(jié)構(gòu)具體實(shí)現(xiàn)聲明你自定義的數(shù)據(jù)類型初始化一段存儲(chǔ)空間用于存放你的數(shù)據(jù)對(duì)象構(gòu)造一個(gè)有真實(shí)數(shù)據(jù)元素存在的寫出針對(duì)問題的操作的具體實(shí)現(xiàn)寫出主程序檢查語(yǔ)法錯(cuò)誤，編譯、鏈接、執(zhí)行、看結(jié)果修改程序的邏輯錯(cuò)誤2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線性表鏈?zhǔn)奖硎荆ㄦ湵恚┑奶攸c(diǎn)鏈表的結(jié)點(diǎn)結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)鏈表的基本操作取元素插入一個(gè)元素刪除一個(gè)元素線性表的鏈?zhǔn)奖硎镜奶攸c(diǎn)特點(diǎn)：用一組任意的存儲(chǔ)單元（可連續(xù)可不連續(xù)）存儲(chǔ)線性表中的數(shù)據(jù)元素。線性表（a1，a2，a3，a4）(a)一段可用空間(b)經(jīng)過一段運(yùn)行的順序表a1a2a3a4(c)經(jīng)過一段運(yùn)行的鏈表a3a2a4a1＾鏈表的結(jié)點(diǎn)結(jié)構(gòu)線性單鏈表存儲(chǔ)結(jié)構(gòu)(C語(yǔ)言中結(jié)構(gòu)指針來描述)typedef

struct

LNode{

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

Struct

LNode*next;//指針域}LNode,*LinkList;線性表的鏈?zhǔn)奖硎镜慕Y(jié)點(diǎn)結(jié)構(gòu)數(shù)據(jù)域指針域線性單鏈表線性單鏈表：n個(gè)結(jié)點(diǎn)(每個(gè)結(jié)點(diǎn)只包含一個(gè)指針域)鏈構(gòu)成的鏈表。不帶頭結(jié)點(diǎn)的線性單鏈表a1a4^a2a3頭指針LL判空條件：Ｌ==NULL首元結(jié)點(diǎn)尾元結(jié)點(diǎn)指示鏈表首元結(jié)點(diǎn)的存儲(chǔ)位置線性單鏈表線性單鏈表：n個(gè)結(jié)點(diǎn)(每個(gè)結(jié)點(diǎn)只包含一個(gè)指針域)鏈構(gòu)成的鏈表。帶頭結(jié)點(diǎn)的線性單鏈表a1a4^a2a3頭指針L判空條件：Ｌnext==NULL首元結(jié)點(diǎn)尾元結(jié)點(diǎn)4^L指示鏈表頭結(jié)點(diǎn)的存儲(chǔ)位置頭結(jié)點(diǎn)線性鏈表示例線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)ZHAO^線性鏈表的邏輯狀態(tài)QIANSUNLIZHOU存儲(chǔ)地址數(shù)據(jù)域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU2531頭指針HWUZHENGWANG^H在單鏈表中任何兩個(gè)元素的存儲(chǔ)位置沒有固定的聯(lián)系每個(gè)元素的存儲(chǔ)位置可由其直接前驅(qū)結(jié)點(diǎn)的指針指出

GetElem_L(LinkList

L,int

i,ElemType&e)線性單鏈表的基本操作-取值a1pan^…nLaiai+1…在單鏈表中獲取第i個(gè)數(shù)據(jù)元素必須從頭指針出發(fā)，沿指針鏈依次向后查找。因此，單鏈表是順序存取的存儲(chǔ)結(jié)構(gòu)。線性單鏈表的基本操作—插入插入前的表L：（a1,…,ai-1,ai,…,an)ListInsert(&L,i,e)GetElem(L,i-1,e)插入后的表L：（a1,…,ai-1,e,ai,…,an)

實(shí)現(xiàn)步驟：用指針p定位到第i-1個(gè)元素所在的結(jié)點(diǎn)生成一個(gè)數(shù)據(jù)域?yàn)閑的結(jié)點(diǎn)，用指針s指向它將s所指結(jié)點(diǎn)插入到單鏈表中線性單鏈表的基本操作—插入用指針p定位到第i-1個(gè)元素所在的結(jié)點(diǎn)生成一個(gè)數(shù)據(jù)域?yàn)閑的結(jié)點(diǎn)，用指針s指向它將s所指結(jié)點(diǎn)插入到單鏈表中a1an^ai-1aiL……線性單鏈表的基本操作—插入用指針p定位到第i-1個(gè)元素所在的結(jié)點(diǎn)生成一個(gè)數(shù)據(jù)域?yàn)閑的結(jié)點(diǎn)，用指針s指向它將s所指結(jié)點(diǎn)插入到單鏈表中a1an^ai-1aiL……p線性單鏈表的基本操作—插入用指針p定位到第i-1個(gè)元素所在的結(jié)點(diǎn)生成一個(gè)數(shù)據(jù)域?yàn)閑的結(jié)點(diǎn)，用指針s指向它將s所指結(jié)點(diǎn)插入到單鏈表中a1an^ai-1aiL……pes線性單鏈表的基本操作—插入用指針p定位到第i-1個(gè)元素所在的結(jié)點(diǎn)生成一個(gè)數(shù)據(jù)域?yàn)閑的結(jié)點(diǎn)，用指針s指向它將s所指結(jié)點(diǎn)插入到單鏈表中a1an^ai-1aiL……pes①①s->next=p->next;線性單鏈表的基本操作—插入用指針p定位到第i-1個(gè)元素所在的結(jié)點(diǎn)生成一個(gè)數(shù)據(jù)域?yàn)閑的結(jié)點(diǎn)，用指針s指向它將s所指結(jié)點(diǎn)插入到單鏈表中a1an^ai-1aiL……pes①s->next=p->next;②p->next=s;

②①線性單鏈表的基本操作—插入用指針p定位到第i-1個(gè)元素所在的結(jié)點(diǎn)生成一個(gè)數(shù)據(jù)域?yàn)閑的結(jié)點(diǎn)，用指針s指向它將s所指結(jié)點(diǎn)插入到單鏈表中a1an^ai-1aiL……e①s->next=p->next;②p->next=s;

線性單鏈表的基本操作—?jiǎng)h除刪除前的表L：（a1,…,ai-1,ai,ai+1…,an)ListDelete(&L,i,&e)GetElem(L,i-1,e)刪除后的表L：（a1,…,ai-1,ai+1,…,an)

實(shí)現(xiàn)步驟：用指針p定位到第i-1個(gè)元素所在的結(jié)點(diǎn)用指針q指向被刪除結(jié)點(diǎn)修改p所指結(jié)點(diǎn)的指針域?yàn)槠渲苯雍罄^的直接后繼釋放被刪結(jié)點(diǎn)所占空間用指針p定位到第i-1個(gè)元素所在的結(jié)點(diǎn)用指針q指向被刪除結(jié)點(diǎn)修改p所指結(jié)點(diǎn)的指針域?yàn)槠渲苯雍罄^的直接后繼釋放被刪結(jié)點(diǎn)所占空間線性單鏈表的基本操作—?jiǎng)h除a1an^ai-1aiL……ai+1用指針p定位到第i-1個(gè)元素所在的結(jié)點(diǎn)用指針q指向被刪除結(jié)點(diǎn)修改p所指結(jié)點(diǎn)的指針域?yàn)槠渲苯雍罄^的直接后繼釋放被刪結(jié)點(diǎn)所占空間線性單鏈表的基本操作—?jiǎng)h除pa1an^ai-1aiL……ai+1用指針p定位到第i-1個(gè)元素所在的結(jié)點(diǎn)用指針q指向被刪除結(jié)點(diǎn)修改p所指結(jié)點(diǎn)的指針域?yàn)槠渲苯雍罄^的直接后繼釋放被刪結(jié)點(diǎn)所占空間線性單鏈表的基本操作—?jiǎng)h除pqa1an^ai-1aiL……ai+1①q=p->next;①用指針p定位到第i-1個(gè)元素所在的結(jié)點(diǎn)用指針q指向被刪除結(jié)點(diǎn)修改p所指結(jié)點(diǎn)的指針域?yàn)槠渲苯雍罄^的直接后繼釋放被刪結(jié)點(diǎn)所占空間線性單鏈表的基本操作—?jiǎng)h除pq②p->next=q->next;②a1an^ai-1aiL……ai+1①q=p->next;①用指針p定位到第i-1個(gè)元素所在的結(jié)點(diǎn)用指針q指向被刪除結(jié)點(diǎn)修改p所指結(jié)點(diǎn)的指針域?yàn)槠渲苯雍罄^的直接后繼釋放被刪結(jié)點(diǎn)所占空間線性單鏈表的基本操作—?jiǎng)h除p③free(q);a1an^ai-1L……ai+1②p->next=q->next;①q=p->next;②用指針p定位到第i-1個(gè)元素所在的結(jié)點(diǎn)用指針q指向被刪除結(jié)點(diǎn)修改p所指結(jié)點(diǎn)的指針域?yàn)槠渲苯雍罄^的直接后繼釋放被刪結(jié)點(diǎn)所占空間線性單鏈表的基本操作—?jiǎng)h除a1an^ai-1L……ai+1p③free(q);②p->next=q->next;①q=p->next;逆位序創(chuàng)建線性單鏈表特點(diǎn)：簡(jiǎn)單，生成的鏈表中結(jié)點(diǎn)的數(shù)據(jù)元素值次序和輸入數(shù)據(jù)的順序相反。實(shí)現(xiàn)：從空表開始，依次建立各元素結(jié)點(diǎn)，逐個(gè)插入單鏈表的頭結(jié)點(diǎn)后。操作演示時(shí)間復(fù)雜度分析線性表的鏈?zhǔn)奖硎拘〗Y(jié)特點(diǎn)：用一組任意的存儲(chǔ)單元（可以連續(xù)也可以不連續(xù)）存儲(chǔ)線性表的數(shù)據(jù)元素。優(yōu)點(diǎn)：實(shí)現(xiàn)插入和刪除運(yùn)算無須移動(dòng)結(jié)點(diǎn)，僅需修改指針。缺點(diǎn)：由于是非隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，某些操作如GetElem(&L,i,&e)、LocateElem(L,e,compare())等算法的復(fù)雜度較大。適用場(chǎng)合：頻繁插入和刪除，存儲(chǔ)空間需求不定的應(yīng)用。2.3.2循環(huán)鏈表循環(huán)鏈表(CircularLinkedList)：特點(diǎn)：將單鏈表的最后一個(gè)結(jié)點(diǎn)指針指向鏈表的表頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。優(yōu)點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)都可找到表中其他結(jié)點(diǎn)。操作：和線性鏈表基本一致，差別僅在于判空條件(b)循環(huán)鏈表的一般形式Lp(a)循環(huán)鏈表的空表形式p->next==L…Lpa0a1an2.3.2循環(huán)鏈表在帶頭結(jié)點(diǎn)的循環(huán)鏈表中設(shè)置頭指針查找首元結(jié)點(diǎn)的時(shí)間復(fù)雜度是，由head指出查找尾元結(jié)點(diǎn)需從頭遍歷整個(gè)鏈表，時(shí)間復(fù)雜度是在帶頭結(jié)點(diǎn)的循環(huán)鏈表中設(shè)置尾指針查找首元結(jié)點(diǎn)的時(shí)間復(fù)雜度是查找尾元結(jié)點(diǎn)的時(shí)間復(fù)雜度是應(yīng)用：兩個(gè)循環(huán)鏈表合并rear->next->nextrear…h(huán)eada0a1an…reara0a1anO(1)O(n)O(1)O(1)合并后的循環(huán)鏈表p=A->next;A->next=B->next->next;B->next=p;僅設(shè)尾指針的循環(huán)鏈表…Aa0a1an…Ba0a1anA…a0a1an…Ba0a1an循環(huán)鏈表的合并2.3.3雙向鏈表線性單鏈表和循環(huán)鏈表的缺點(diǎn)尋找結(jié)點(diǎn)的直接后繼，NextElem()的復(fù)雜度是O(1)。尋找結(jié)點(diǎn)的直接前驅(qū)，PriorElem()的復(fù)雜度是O(n)。雙向鏈表:在單鏈表的每個(gè)結(jié)點(diǎn)里增加一個(gè)指向其直接前趨的指針域prior。雙向鏈表C語(yǔ)言描述為：typedef

struct

DulNode{

ElemTypedata;

Struct

DulNode*prior;//指向其直接前驅(qū)的指針域

Struct

DulNode*next;//指向其直接后繼的指針域}DulNode,*DuLinkList;雙向鏈表結(jié)點(diǎn)結(jié)構(gòu)和示意圖結(jié)點(diǎn)結(jié)構(gòu)：設(shè)指針p指向某一結(jié)點(diǎn)，則雙向鏈表結(jié)構(gòu)的對(duì)稱性：

在雙向鏈表中某些操作算法與線性單鏈表的操作相同；插入、刪除等操作需同時(shí)修改兩個(gè)方向的指針^^priornextL(a)空雙向鏈表^a0a1……

an-1

^

L(b)非空的雙向鏈表priordatanext(p—>prior)—>next=p=(p—>next)—>prior雙向鏈表的基本操作舉例在雙向鏈表中插入一個(gè)結(jié)點(diǎn)生成一個(gè)結(jié)點(diǎn)空間，為數(shù)據(jù)域賦值完成插入在雙向鏈表中刪除一個(gè)結(jié)點(diǎn)找到被刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)刪除結(jié)點(diǎn)釋放空間線性表實(shí)現(xiàn)方法的比較一、存儲(chǔ)空間的分配方面：順序存儲(chǔ)開辟連續(xù)的，固定長(zhǎng)度的存儲(chǔ)空間。出現(xiàn)溢出情況時(shí)，不能動(dòng)態(tài)擴(kuò)充。鏈?zhǔn)酱鎯?chǔ)中，結(jié)點(diǎn)的存儲(chǔ)空間是通過malloc函數(shù)來動(dòng)態(tài)分配，可以不連續(xù)，不存在溢出情況。

結(jié)論：事先能確定線性表的大致長(zhǎng)度，應(yīng)選擇順序存儲(chǔ)方式，否則為了避免造成分配空間過大或過小，宜采用鏈?zhǔn)酱鎯?chǔ)方式。線性表實(shí)現(xiàn)方法的比較二、操作方面：順序存儲(chǔ)，可以隨機(jī)訪問，經(jīng)常訪問線性表中元素的操作非常方便。但要進(jìn)行插入和刪除操作每次都會(huì)出現(xiàn)元素的大量移動(dòng)。鏈?zhǔn)酱鎯?chǔ)，只能順序訪問，訪問鏈表中的任意元素時(shí)，必須都從第一個(gè)結(jié)點(diǎn)開始順序查找。要進(jìn)行插入和刪除操作時(shí)，只需修改結(jié)點(diǎn)的指針域。

結(jié)論：如果線性表頻繁地進(jìn)行插入和刪除操作，宜采用鏈?zhǔn)酱鎯?chǔ)；若頻繁訪問線性表中元素，宜采用順序存儲(chǔ)。在實(shí)際中怎樣選取存儲(chǔ)結(jié)構(gòu)的幾點(diǎn)考慮：(1)基于存儲(chǔ)的考慮

順序表的存儲(chǔ)空間是靜態(tài)分配的，在程序執(zhí)行之前必須明確規(guī)定“MAXSIZE”大小，估計(jì)過大，造成浪費(fèi)，過小造成溢出。

鏈表不用事先估計(jì)存儲(chǔ)規(guī)模，但鏈表的存儲(chǔ)密度較低。

存儲(chǔ)密度是指一個(gè)結(jié)點(diǎn)中數(shù)據(jù)元素所占的存儲(chǔ)單元數(shù)和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)單元之比。顯然順序表的存儲(chǔ)密度為1，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)密度小于１。在實(shí)際中怎樣選取存儲(chǔ)結(jié)構(gòu)的幾點(diǎn)考慮：(2)基于運(yùn)算的考慮

如果對(duì)線性表的主要操作是查找，適宜采用順序表結(jié)構(gòu)。對(duì)于頻繁進(jìn)行插入和刪除操作的線性表，適宜采用鏈表結(jié)構(gòu)。(3)基于環(huán)境的考慮

順序表的實(shí)現(xiàn)基于數(shù)組類型，鏈表的操作是基于指針。2.4一元多項(xiàng)式的表示一元多項(xiàng)式在計(jì)算機(jī)的表示：采取順序存儲(chǔ)結(jié)構(gòu)，例：Pn(x)=p0+p1x+p2x2……+pnxn

可表示成P=(p0,p1,…,pn)

抽象數(shù)據(jù)類型一元多項(xiàng)式的定義和實(shí)現(xiàn)書40-42頁(yè)優(yōu)點(diǎn)：算法簡(jiǎn)潔缺點(diǎn)：在實(shí)現(xiàn)某些基本操作時(shí)不夠方便，且浪費(fèi)空間解決辦法：用數(shù)據(jù)元素為(系數(shù)項(xiàng)，指數(shù)項(xiàng))的線性表來表示一元多項(xiàng)式，稱為多項(xiàng)式的非零項(xiàng)系數(shù)-指數(shù)對(duì)。例如:S(x)=1+3x109-5x231+6x354

可用((1,0),(3,109),(-5,231),(6,354))表示。

2.4一元多項(xiàng)式的實(shí)現(xiàn)一元多項(xiàng)式在計(jì)算機(jī)的實(shí)現(xiàn)：采取鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)typedef

struct

{floatcoef;

int

expn;}term,ElemType;typedef

LinkListpolynomial;

一元多項(xiàng)式的相加兩個(gè)多項(xiàng)式相加的運(yùn)算規(guī)則（算法策略）：和多項(xiàng)式中結(jié)點(diǎn)從兩個(gè)多項(xiàng)式鏈表中摘取，無須另生成。所有指數(shù)不同的項(xiàng)分別復(fù)抄到和多項(xiàng)式中。指數(shù)相同，對(duì)應(yīng)系數(shù)相加，若和不為0則構(gòu)成和多項(xiàng)式中一項(xiàng)兩個(gè)多項(xiàng)式相加的算法：設(shè)qa和qb分別指向多項(xiàng)式A、B中當(dāng)前進(jìn)行比較的結(jié)點(diǎn)，則比較兩個(gè)結(jié)點(diǎn)中指數(shù)項(xiàng)有三種情況：

①qa.expn<qb.expn，取qa所指結(jié)點(diǎn)插入和多項(xiàng)式鏈表。

②qa.expn=qb.expn，系數(shù)相加，若和為0，刪除結(jié)點(diǎn)，釋放qa和qb，若和不為0，修改qa系數(shù)值，釋放qb③qa.expn>qb.expn，取qb所指結(jié)點(diǎn)插入和多項(xiàng)式鏈表中。算法2.23多項(xiàng)式加法:Pa=Pa+Pb的框架voidAddPolyn(polynomail&Pa,polynomail&Pb){ha=Pa;hb=Pb;qa=ha->next;qb=hb->next;

while(qa&&qb){ switch(cmp(qa->data.expn,qb->data.expn)){case–1:qa指針后移//(qa->expn<qb->expn)case0://(qa->expn==qb->expn) {if(qa->data.coef+qb->data.coef!=0)

qa->data.coef+=qb->data.coef; else//當(dāng)系數(shù)和為0時(shí)

刪除qa所指結(jié)點(diǎn);}//if

刪除qb所指結(jié)點(diǎn)，qa,qb指針均后移

case1:將qb所指結(jié)點(diǎn)插入Pa，qb指針后移

}}

if(qb)所指結(jié)點(diǎn)鏈入Pa;

free(Pb)}//addpolyn第二章知識(shí)結(jié)構(gòu)圖鏈表特點(diǎn)和實(shí)現(xiàn)插入和刪除特點(diǎn)和實(shí)現(xiàn)線性表抽象類型定義順序表應(yīng)用歸并逆置歸并插入刪除插入刪除多項(xiàng)式相加多項(xiàng)式相乘單鏈表循環(huán)鏈表雙鏈表歸并第二章的類型題一、順序及鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的概念及特點(diǎn)二、插入、刪除算法性能分析三、單、雙向鏈表的基本算法（插入/刪除/判空）四、單鏈表逆置五、兩個(gè)有序或無序線性表歸并六、鏈表相鄰結(jié)點(diǎn)交換算法應(yīng)掌握的知識(shí)點(diǎn)類型題一、順序及鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的概念及特點(diǎn)。1順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。(對(duì)/錯(cuò)）2線性表是具有n個(gè)

的有限序列。3向長(zhǎng)度為n的線性表中的第i個(gè)元素（1≤i≤n〉之前，插入一個(gè)元素時(shí)，需向后移動(dòng)

個(gè)元素，刪除第i個(gè)元素時(shí)，需向前移動(dòng)

個(gè)元素。4表長(zhǎng)為n的順序存儲(chǔ)的線性表，當(dāng)在任何位置插入和刪除一個(gè)元素概率相等時(shí)，插入一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為

，刪除一個(gè)元素需移動(dòng)元素的平均個(gè)數(shù)為

。5順序查找法適用于存儲(chǔ)結(jié)構(gòu)為順序或鏈?zhǔn)酱鎯?chǔ)的線性表。（對(duì)/錯(cuò)）應(yīng)掌握的知識(shí)點(diǎn)類型題7線性表采用鏈表存儲(chǔ)時(shí)結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以不連續(xù)。(正確/錯(cuò)誤)8若頻繁地對(duì)一個(gè)線性表進(jìn)行插入和刪除操作，該線性表宜采用何種存儲(chǔ)結(jié)構(gòu)？為什么？二、算法性能分析2.1若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i（1≤i≤n+1）個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為

。三、單鏈表及雙向鏈表的基本算法（插入、刪除、判空）3.1將s所指結(jié)點(diǎn)加到p所指結(jié)點(diǎn)后，語(yǔ)句是

。應(yīng)掌握的知識(shí)點(diǎn)類型題四、單鏈表逆置（原地、可構(gòu)造新表、遞歸）4.1寫一算法，在原鏈表上實(shí)現(xiàn)逆置。五、兩個(gè)有序或無序線性表歸并5.1將兩個(gè)各有n個(gè)元素的有序表歸并為一個(gè)有序表，其最少的比較次數(shù)為

。

5.2設(shè)兩個(gè)按值遞增的有序線性表A和B，編寫算法將A和B歸并成一個(gè)按元素值遞減有序排列的線性表C，要求利用原表的結(jié)點(diǎn)空間存放C。六、鏈表相鄰結(jié)點(diǎn)交換算法6.1有一個(gè)由正整數(shù)組成的無序單鏈表，編寫算法完成：①找出最小值結(jié)點(diǎn)，打印它②若該數(shù)值是奇數(shù)，將它與直接后繼結(jié)點(diǎn)的數(shù)值交換，若是偶數(shù)，將其直接后繼結(jié)點(diǎn)刪除③交換該結(jié)點(diǎn)（不是鏈表最后的結(jié)點(diǎn)）和其直接后繼結(jié)點(diǎn)

……L…qpvoidChangeListNode(LinkList

L,LNode*p){

r=p->next; ①q->next=r; ②p->next=r->next; ③r->next=p; }六、鏈表相鄰結(jié)點(diǎn)交換

……L…qprvoidChangeListNode(LinkList

L,LNode*p){

r=p->next; ①q->next=r; ②p->next=r->next; ③r->next=p; }六、鏈表相鄰結(jié)點(diǎn)交換

……L…qpr①voidChangeListNode(LinkList

L,LNode*p){

r=p->next;

①q->next=r; ②p->next=r->next; ③r->next=p; }六、鏈表相鄰結(jié)點(diǎn)交換

……L…qpr①②voidChangeListNode(LinkList

L,LNode*p){

r=p->next; ①q->next=r;

②p->next=r->next; ③r->next=p; }六、鏈表相鄰結(jié)點(diǎn)交換

……L…qpr①②③voidChangeListNode(LinkList

L,LNode*p){

r=p->next; ①q->next=r; ②p->next=r->next;

③r->next=p;

}六、鏈表相鄰結(jié)點(diǎn)交換上機(jī)語(yǔ)法錯(cuò)誤上機(jī)調(diào)試邏輯錯(cuò)誤正確結(jié)果成功=1%錯(cuò)誤結(jié)果對(duì)象沒有返回死循環(huán)無錯(cuò)誤具體應(yīng)用算法模型數(shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu)非線性結(jié)構(gòu)存儲(chǔ)表示順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)加法、乘法比較、移動(dòng)定位（查找）寫程序rundebugtoggleabreakpointaddwatchgotocursorstepintodeclarationsytaxerror、argumentlisterrortypemismatch、unexpectedfileend第二章作業(yè)講評(píng)基本習(xí)題：2.1,2.2,2.3,2.4,2.5,2.6,2.7,2.8,2.9上機(jī)習(xí)題：2.11,2.19,2.22,2.24算法設(shè)計(jì)：2.11,2.12,2.19,2.21,2.22,2.242.11將x插入到遞增有序的順序表L中，插入后L仍然遞增有序intInsertOrderList1(Sqlist&L,intx){if(L.length>=L.listsize){newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));if(!newbase) exit(OVERFLOW);

//分配不成功

L.elem=newbase;L.listsize+=LISTINCREMENT;}

p=&(L.elem[L.length-1]);//指向表尾元素位置

while(p>=&(L.elem[0])&&*p>x){*(p+1)=*p;--p;}*(p+1)=x; ++L.length;//完成插入，線性表長(zhǎng)度增1returnOK;}InsertOrderList12.11將x插入到遞增有序的順序表L并保持L有序intInsertOrderList2(SqList&L,intx){

inti;

i=1;//數(shù)組下標(biāo)從1開始

while((i<=L.length)&&(x>L.elem[i]))

i++;//查找i是插入位置

ListInsert_Sq(L,i,x);//插在第i個(gè)元素之前

returnOK;}//InsertOrderList22.12設(shè)A=（a1,……,am）,B=（b1,……,bn）均為順序表，A’和B’分別是A和B中除去最大共同前綴后的子表，若A’和B’都是空表則A=B，若A’是空表，B’不空，或兩者均不為空，且A’的首元小于B’的首元?jiǎng)tA<B，否則A>B，寫一個(gè)比較A、B大小的算法，注意在算法中不要破壞原表A和B，也不必求得A’,B’才進(jìn)行比較。A=(x,y,y,z,x,z)B=(x,y,y,z,y,x,x,z)2.12

int

Compare_List(Sqlista,Sqlistb){//若a<b，返回-1；a=b，返回0；a>b，返回1while((i<=a.length-1)&&(i<=b.length-1)&&a.elem[i]==b.elem[i])){++i;}if(a.length==i&&b.length==i){ printf("A=B"); return0; }elseif((i==a.length&&i<=b.length-1)||(i<=a.length-1&&i<=b.length-1&&a.elem[i]<b.elem[i])){ printf("A<B"); return-1; }else{ printf("A>B"); return1; }}2.21順序表的就地逆置算法思想：依靠下標(biāo)變換來實(shí)現(xiàn)voidreverse1(Sqlist&A){

inttemp,i,j;for(i=0,j=A.length-1;i<=j;i++,j--) {

}}//reverse1temp=A.elem[i];A.elem[i]=A.elem[j];A.elem[j]=temp;2.21順序表的就地逆置voidreverse2(Sqlist&A){

inttemp,i;for(i=0;i<=(A.length-1)/2;i++){

}}//reverse2temp=A.elem[i];A.elem[i]=A.elem[A.length-1-i];A.elem[A.length-1-i]=temp;2.19算法框架LinkList

DeleteBetween(LinkList*L,int

mink,int

maxk){//刪除大于mink小于maxk的元素并釋放結(jié)點(diǎn)空間。

if(mink>maxk)returnERROR; q=L->next;

while(q->data<=mink)//當(dāng)結(jié)點(diǎn)值小于等于mink時(shí)

while(q->data<maxk) //當(dāng)結(jié)點(diǎn)值小于maxk時(shí)

returnL;}

La0a1an-1a2…pq指針后移；刪除該結(jié)點(diǎn)；2.19算法實(shí)現(xiàn)LinkList

DeleteBetween(LinkList

L,int

mink,int

maxk){ if(mink>maxk)//判斷輸入的邊界值是否合法

{

printf("the

Llue

iswrong");exit(OVERFLOW);} q=L->next; p=L; while(q->data<=mink) {//尋找要?jiǎng)h除結(jié)點(diǎn)所在的下邊界位置

}while(q&&q->data<maxk)

{//尋找要?jiǎng)h除結(jié)點(diǎn)所在的上邊界位置

} returnL;}

p=q;q=p->next;

p->next=p->next->next;free(q);q=p->next;算法思想：在頭結(jié)點(diǎn)和首元結(jié)點(diǎn)之間插入后繼結(jié)點(diǎn)int

InvertLinkList(LinkListL){//