《數(shù)據(jù)結(jié)構(gòu)》課件1第2章 線性表

2.1

線性表的類型定義2.3線性表類型的實(shí)現(xiàn)

鏈?zhǔn)接诚?.4一元多項(xiàng)式的表示及相加2.2線性表類型的實(shí)現(xiàn)

順序映象知識(shí)點(diǎn)：重點(diǎn)：難點(diǎn)：●線性表、順序表、鏈表、有序表●順序表與鏈表的描述方法；●在兩種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)線性表的基本運(yùn)算的算法?！窬€性表在兩種存儲(chǔ)結(jié)構(gòu)上的插入、刪除算法及動(dòng)態(tài)鏈表的建立和查找算法。課前思考：●抽象數(shù)據(jù)類型的定義由哪幾部分組成？●按數(shù)據(jù)元素之間的邏輯關(guān)系不同，數(shù)據(jù)結(jié)構(gòu)有哪幾類？●你能舉出幾個(gè)你熟悉的"序列"的例子來嗎？數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系和基本操作三部分。線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖狀結(jié)構(gòu)和集合四類。如："0，1，2，…，9","A，B，C，…，Z"。1、線性表的定義：

一個(gè)線性表（LinearList）是由n(n≥0)個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)）所構(gòu)成的有限序列。線性表邏輯地表示為：（a1,a2,…,an)。其中，n為線性表的長度，n=0時(shí)為空表。稱i為ai在線性表中的位序。2、線性表的結(jié)構(gòu)（邏輯結(jié)構(gòu)）特點(diǎn)：a.它由n個(gè)同類型的元素組成；（一般）

b.有且僅有一個(gè)第一個(gè)元素和最后一個(gè)元素；

c.每個(gè)元素除第一個(gè)元素和最后一個(gè)元素之外,有僅只有一個(gè)前驅(qū)和一個(gè)后繼。2.1線性表的類型定義3、抽象數(shù)據(jù)類型線性表的定義：ADTList{

數(shù)據(jù)對(duì)象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

基本操作：……}ADTList

InitList(&L)1）初始化操作：4、線性表的基本操作：2）結(jié)構(gòu)銷毀操作：DestroyList(&L)

ListEmpty(L)3）線性表判空操作：

ListLength(L)4）求線性表的長度：PriorElem(L,cur_e,&pre_e)5）求數(shù)據(jù)元素的前驅(qū)：NextElem(L,cur_e,&next_e)6）求數(shù)據(jù)元素的后繼：GetElem(L,i,&e)7）取線性表中某個(gè)數(shù)據(jù)元素：LocateElem(L,e,compare())8）定位操作：ListTraverse(L,visit())9）遍歷線性表：ClearList(&L)ListInsert(&L,i,e)ListDelete(&L,i,&e)10）線性表置空操作：11）插入操作：12）刪除操作：

假設(shè)上述基本操作已經(jīng)實(shí)現(xiàn)，則可以利用上述定義的線性表基本操作，來實(shí)現(xiàn)其它更復(fù)雜的操作例

2-2例

2-1注：這是P20-21頁的部分的內(nèi)容，先跳過。略

用一組地址連續(xù)的存儲(chǔ)單元依次存放

線性表中的數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)線性表的起始地址稱作線性表的基地址

a1a2

…ai-1ai

…an一.概念順序存儲(chǔ)：順序表：

用順序存儲(chǔ)的線性表就稱為順序表n為表的長度2.2線性表類型的實(shí)現(xiàn)-順序映象以“存儲(chǔ)位置相鄰”表示有序?qū)?lt;ai-1，ai>即：LOC(ai)=LOC(ai-1)+C

一個(gè)數(shù)據(jù)元素所占存儲(chǔ)量↑

所有數(shù)據(jù)元素的存儲(chǔ)位置均取決于第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置

LOC(ai)=LOC(a1)+(i-1)×C

↑基地址三、地址計(jì)算公式存儲(chǔ)地址

內(nèi)在狀態(tài)

數(shù)據(jù)元素在線性表的位序a1a2aian………b(基地址）b+Cb+(i-1)*cb+(n-1)*cb+(maxlen-1)*c12in空閑二.特點(diǎn)：1.邏輯上相鄰的數(shù)據(jù)元素，賦以相鄰的存儲(chǔ)位置；2.存儲(chǔ)密度高；存儲(chǔ)密度：數(shù)據(jù)元素的值所需的存儲(chǔ)空間d=

該元素實(shí)際所需的存儲(chǔ)空間3.便于隨機(jī)存??；4.不便于插入、刪除操作。

（會(huì)引起大量結(jié)點(diǎn)的移動(dòng)）例如四.線性表的靜態(tài)順序存儲(chǔ)結(jié)構(gòu)的C語言描述(補(bǔ)充內(nèi)容）#defineMAXLEN80//線性表的最大長度typedefstruct{ElemTypeelem[MAXLEN];intlength;}SqListtp;//俗稱靜態(tài)順序表C語言中用一維數(shù)組來描述：

說明一個(gè)靜態(tài)順序表L：SqlisttpL;(1)查找：在順序表L中查找第i個(gè)元素。

(2)求長度：求順序表L中元素的個(gè)數(shù)。

(3)插入：在順序表L中第i個(gè)元素前插入元素b。

五.基本操作在靜態(tài)順序表上的實(shí)現(xiàn)L.elem[i-1]L.lengthfor(j=L.length-1;j>=i-1;j--)L.elem[j+1]=L.elem[j];//第i及其之后的所有元素后移一位,以空出插入位置

L.elem[i-1]=b;//插入

L.length++;//表長加1（4）刪除：在順序表L中刪除第i個(gè)元素。for(j=i;j<=L.length-1;j++)L.elem[j-1]=L.elem[j];//將第i元素之后的所有元素前移一位

L.length--;六.線性表的動(dòng)態(tài)順序存儲(chǔ)結(jié)構(gòu)的C語言描述typedefstruct{

}SqList;//俗稱動(dòng)態(tài)順序表#defineLIST_INIT_SIZE80//線性表存儲(chǔ)空間的初始分配量#defineLISTINCREMENT10//線性表存儲(chǔ)空間的分配增量Elemtype*elem;//存儲(chǔ)空間基址int

length;//當(dāng)前長度int

listsize;//當(dāng)前分配的存儲(chǔ)容量

//(以sizeof(ElemType)為單位)P22InitList(&L)//構(gòu)造一個(gè)空表LocateElem(L,e,compare())//查找ListInsert(&L,i,e)//插入元素ListDelete(&L,i)//刪除元素七、基本操作在動(dòng)態(tài)順序表上的實(shí)現(xiàn)1.構(gòu)造一個(gè)空線性表：

InitList(&L)1）申請(qǐng)分配“足夠應(yīng)用”的線性表的存儲(chǔ)空間2）若分配失敗，則結(jié)束函數(shù)的執(zhí)行3）若分配成功，則置：

a)表的當(dāng)前長度為0b)當(dāng)前分配的存儲(chǔ)容量為預(yù)分配空間的大小L.elem=(Elemtype*)malloc(LIST_INIT_SIZE*sizeof(Elemtype))if(!L.elem)exit(OVERFLOW)L.length=0L.listsize=LIST_INIT_SIZEP23/算法2.3StatusInitList_Sq(SqList&L){//構(gòu)造一個(gè)空的線性表

}//InitList_Sq算法時(shí)間復(fù)雜度：O(1)L.elem=(ElemType*)malloc

(LIST_INIT_SIZE

sizeof

(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZEreturnOK;P23/算法2.3例如：順序表23754138546217L.elemL.lengthL.listsizee=38pppppi12341850p可見，基本操作是：將順序表中的元素逐個(gè)和給定值e相比較。2.定位操作：

LocateElem(L,e,compare())P25/算法2.6

intLocateElem_Sq(SqListL,ElemTypee,

Status(*compare)(ElemType,ElemType)){

//

在順序表中查詢第一個(gè)滿足判定條件的數(shù)據(jù)元素，

//若存在，則返回它的位序，否則返回0}//LocateElem_Sq

O(ListLength(L))算法的時(shí)間復(fù)雜度為：i=1;//i的初值為第1元素的位序p=L.elem;

//p的初值為第1元素的存儲(chǔ)位置while

(i<=L.length&&!(*compare)(*p++,e))++i;if(i<=L.length)returni;elsereturn0;*p++!=e;P25/算法2.63.插入操作

ListInsert(&L,i,e)的實(shí)現(xiàn)：首先分析:1）要求：

在第i個(gè)元素之前插入一個(gè)值為e的元素

問題：

插入元素時(shí)，線性表的

邏輯結(jié)構(gòu)發(fā)生什么變化？P24/算法2.4

(a1,…,ai-1,ai,…,an)改變?yōu)?/p>

(a1,…,ai-1,e,ai,…,an)a1a2

…ai-1ai

…ana1a2

…ai-1

…aiean<ai-1,ai><ai-1,e>,<e,ai>表的長度增加2118307542568721183075例如：ListInsert_Sq(&L,5,66)L.length-10pppq87564266pL.length-1011…………for（;p>=q;--p)q=&(L.elem[i-1]);//q指示插入位置p=&(L.elem[L.length-1])*(p+1)=*p;//后移*q=e;//將e插入到q所指示的位置L.elem

a.[檢測參數(shù)i是否合法及空間是否足夠]

b.[插入位置及之后的所有元素后移一位]2）操作步驟：q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)

*(p+1)=*p;?。┤鬷<1||i>L.length+1，插入位置不合法，算法結(jié)束；

ⅱ）若L.length>=L.listsize，則無空的存儲(chǔ)空間，需增加分配。c.[插入]d.[修正表長]*q=e;//插入e++L.length;//表長增1

StatusListInsert_Sq(SqList&L,inti,ElemTypee){

//

在順序表L的第i個(gè)元素之前插入新的元素e,

//i的合法范圍為1≤i≤L.length+1}//ListInsert_Sq

算法時(shí)間復(fù)雜度為:O(ListLength(L))q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//插入位置及之后的元素右移*q=e;//插入e++L.length;//表長增1returnOK;……元素右移3）算法：P24/算法2.4if(L.length>=L.listsize){

//當(dāng)前存儲(chǔ)空間已滿，增加分配

newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);//存儲(chǔ)分配失敗

L.elem=newbase;//新基址

L.listsize+=LISTINCREMENT;//增加存儲(chǔ)容量}if(i<1||i>L.length+1)returnERROR;

//

插入位置不合法考慮移動(dòng)元素的平均情況:

假設(shè)在第

i個(gè)元素之前插入的概率為，

則在長度為n的線性表中插入一個(gè)元素所需移動(dòng)元素次數(shù)的期望值為：

若假定在線性表中任何一個(gè)位置上進(jìn)行插入的概率都是相等的，則移動(dòng)元素的期望值為：首先分析：問題：刪除元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？4.刪除操作

ListDelete(&L,i,&e)的實(shí)現(xiàn)：

1）要求：

將第i個(gè)位置上的元素刪除P24/算法2.5

(a1,…,ai-1,ai,ai+1,…,an)改變?yōu)?/p>

(a1,…,ai-1,ai+1,…,an)ai+1…an<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的長度減少a1a2

…ai-1ai

ai+1

…ana1a2

…ai-1

21183075425687……L.length-10pppqpp5687p=&(L.elem[i-1]);//p為被刪除元素的位置e=*p;q=&L.elem[L.length-1];//q為表尾元素的位置for(;p<=q;++p)*(p-1)=*p;//前移……1例如：ListDelete_Sq(&L,4,&e)L.elemL.listsize75++p422）操作步驟：

1.檢測（判斷參數(shù)i是否合法）

2.前移（刪除元素之后的所有元素前移一位）p=&(L.elem[i-1]);//p指示刪除位置e=*p//用e返回被刪元素的值q=&(L.elem[L.length-1]);

//p指示表尾位置for(p++;p>=q;--p)*(p+1)=*p;//后移一位若i<1||i>L.length，刪除位置不合法，算法結(jié)束；3.修正表長

（表長減1）--L.length;//表長減1StatusListDelete_Sq(SqList&L,inti,ElemType&e){}//ListDelete_Sqfor(++p;p<=q;++p)*(p-1)=*p;

//

被刪除元素之后的元素左移--L.length;//表長減1returnOK;算法時(shí)間復(fù)雜度為:

O(ListLength(L))p=&(L.elem[i-1]);//p為被刪除元素的位置e=*p;//被刪除元素的值賦給eq=L.elem+L.length-1;//表尾元素的位置if((i<1)||(i>L.length))returnERROR;

//刪除位置不合法元素左移3）算法：P24/算法2.5考慮移動(dòng)元素的平均情況:

假設(shè)刪除第

i個(gè)元素的概率為

,則在長度為n的線性表中刪除一個(gè)元素所需移動(dòng)元素次數(shù)的期望值為：若假定在線性表中任何一個(gè)位置上進(jìn)行刪除的概率都是相等的，則移動(dòng)元素的期望值為：

所以，若表長為n,則插入和刪除算法的時(shí)間復(fù)雜度都為：O(n)思考題：(P26/算法2.7)

有兩個(gè)有序的順序表LＡ（有m個(gè)元素）和LＢ（有n個(gè)元素）其元素均以從小到大的升序排列，編寫一個(gè)函數(shù)將它們合并成一個(gè)順序表LC，并要求LC仍保持其有序性。

分析：

假設(shè)LA=（6,7,10,21），LB=（3,11,13,15,23,25,27)

papb合并后得LC=（3,6,7,10,11,13,15,21,23,25,27)

方法：

引進(jìn)兩個(gè)指針pa,pb分別指向LA和LB中的某個(gè)元素,pc指示LC中當(dāng)前插入元素的位置。*pa當(dāng)*pa<=*pb時(shí)*pc=*pb當(dāng)*pa>*pb時(shí)操作步驟：(算法見教材P26/算法2.7)1.置初值：1)pa=La.elem;pb=Lb.elem;2)為Lc分配足夠的存儲(chǔ)空間;2.當(dāng)pa<=La.elem+La.length-1和

pb<=Lb.elem+Lb.length-1時(shí),重復(fù)執(zhí)行：

1）當(dāng)*pa<=*pb，將*pa插入到Lc中pc指針?biāo)甘镜奈恢?pa指針后移;否則，將*pb插入到Lc中pc指針?biāo)甘镜奈恢?pb指針后移。2）pc指針后移3.pa<=La.elem+La.length-1

，將La中的剩余元素全部順序插入到Lc的尾部4.pb<=Lb.elem+Lb.length-1,將Lb中的剩余元素全部順序插入到Lc的尾部算法題：題集P17/2.11,P18/2.21作業(yè)1：實(shí)驗(yàn)題：

1.實(shí)驗(yàn)一順序表基本操作（驗(yàn)證性實(shí)驗(yàn)）——實(shí)驗(yàn)課之前并且在課外完成

2.實(shí)驗(yàn)一順序表基本操作（設(shè)計(jì)性實(shí)驗(yàn)）——實(shí)驗(yàn)課完成附加題:

編寫算法刪除順序表中“多余”的數(shù)據(jù)元素，即使操作之后的順序表中所有元素的值都不相同。

一、單鏈表二、結(jié)點(diǎn)和單鏈表的C語言描述三、線性表的操作在單鏈表中的實(shí)現(xiàn)五、一個(gè)帶頭結(jié)點(diǎn)的單鏈表類型六、其它形式的鏈表四、有序表類型2.3線性表類型的實(shí)現(xiàn)-鏈?zhǔn)接诚?/p>

用一組

地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。一、單鏈表以元素(數(shù)據(jù)元素的映象)

+指針(指示后繼元素存儲(chǔ)位置)=結(jié)點(diǎn)

(表示數(shù)據(jù)元素或數(shù)據(jù)元素的映象)以“結(jié)點(diǎn)的序列”表示線性表

稱作鏈表

以線性表中第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址作為線性表的地址，稱作線性表的頭指針。頭結(jié)點(diǎn)

a1a2…...an^頭指針頭指針

有時(shí)為了操作方便，在第一個(gè)結(jié)點(diǎn)之前虛加一個(gè)“頭結(jié)點(diǎn)”，以指向頭結(jié)點(diǎn)的指針為鏈表的頭指針?？罩羔樉€性表為空表時(shí)，頭結(jié)點(diǎn)的指針域?yàn)榭?/p>

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

structLNode*next;//指針域

}LNode,*LinkList;

二、結(jié)點(diǎn)和單鏈表的C語言描述LinkListL；//L為單鏈表的頭指針三、單鏈表中基本操作的實(shí)現(xiàn)GetElem(L,i,e)//取第i個(gè)數(shù)據(jù)元素ListInsert(&L,i,e)//插入數(shù)據(jù)元素ListDelete(&L,i,e)//刪除數(shù)據(jù)元素ClearList(&L)//重置線性表為空表CreateList(&L,n)

//生成含n個(gè)數(shù)據(jù)元素的鏈表1、線性表的取元素操作

GetElem(L,i,&e)在單鏈表中的實(shí)現(xiàn):P29/算法2.8

單鏈表是一種"順序存取"的結(jié)構(gòu)，即：為取第i元素，首先必須先找到第i-1個(gè)元素。因此不論i值為多少，都必須從頭結(jié)點(diǎn)開始起"點(diǎn)數(shù)"，直數(shù)到第i個(gè)為止。頭結(jié)點(diǎn)可看成是第0個(gè)結(jié)點(diǎn)。分析：L211830754256∧pppj123下面為操作Getelem(L,3,&e)動(dòng)態(tài)演示過程：

StatusGetElem_L(LinkListL,inti,ElemType&e){//L是帶頭結(jié)點(diǎn)的鏈表的頭指針，以e返回第i個(gè)元素}//GetElem_L算法時(shí)間復(fù)雜度為:O(ListLength(L))p=L->next;j=1;//p指向第一個(gè)結(jié)點(diǎn)，j為計(jì)數(shù)器while(p&&j<i){p=p->next;++j;}//

順指針向后查找，直到p指向第i個(gè)元素

//

或p為空if(!p||j>i)

returnERROR;//參數(shù)i不合法e=p->data;//取得第i個(gè)元素returnOK;P29/算法2.8問：能否將變量初始化改為"p=L;j=0;"?ai-12、線性表的插入操作

ListInsert(&L,i,e)

在單鏈表中的實(shí)現(xiàn)：

有序?qū)?lt;ai-1,ai>

改變?yōu)?lt;ai-1,e>和<e,ai>eaiai-1P29/算法2.9

a.查找第i個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)(或確定待插入的位置)

b.產(chǎn)生新結(jié)點(diǎn)Sc.將S插入到鏈表指定的位置2）算法基本步驟：s=(LinkList)malloc

(sizeof(LNode));S->data=e;p=L;j=0;while(p&&j<i-1)

{p=p->next;++j;}s->next=p->next;p->next=s;eai-1aiai-1sp(能否改為:p=L->next;j=1;)StatusListInsert_L(LinkList&L,inti,ElemTypee){

//L為帶頭結(jié)點(diǎn)的單鏈表的頭指針，本算法

//在鏈表中第i個(gè)結(jié)點(diǎn)之前插入新的元素e

}//LinstInsert_L算法的時(shí)間復(fù)雜度為:O(ListLength(L))……p=L;j=0;while(p&&j<i-1)

{p=p->next;++j;}

//

尋找第i-1個(gè)結(jié)點(diǎn)if(!p||j>i-1)

returnERROR;//

i大于表長或者小于1P29/算法2.9

問：如果單鏈表不帶頭結(jié)點(diǎn)，應(yīng)如何修改此算法？？s=(LinkList)malloc(sizeof(LNode));

//生成新結(jié)點(diǎn)s->data=e;s->next=p->next;p->next=s;

//插入returnOK;3、線性表的刪除操作ListDelete(&L,i,&e)在鏈表中的實(shí)現(xiàn):有序?qū)?lt;ai-1,ai>和<ai,ai+1>

改變?yōu)?lt;ai-1,ai+1>ai-1aiai+1ai-1P30/算法2.10

在單鏈表中刪除第

i個(gè)結(jié)點(diǎn)的基本操作為:找到線性表中第i-1個(gè)結(jié)點(diǎn)，修改其指向后繼的指針。ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;free(q);pqeStatusListDelete_L(LinkList&L,inti,ElemType&e){

//刪除以L為頭指針(帶頭結(jié)點(diǎn))的單鏈表中第i個(gè)結(jié)點(diǎn)

}//ListDelete_L算法的時(shí)間復(fù)雜度為:O(ListLength(L))p=L;j=0;while(p->next

&&j<i-1){p=p->next;++j;}

//尋找第i個(gè)結(jié)點(diǎn)，并令p指向其前趨if(!(p->next)||j>i-1)

returnERROR;//刪除位置不合理q=p->next;p->next=q->next;

//刪除并釋放結(jié)點(diǎn)e=q->data;free(q);returnOK;P30/算法2.10

問：如果單鏈表不帶頭結(jié)點(diǎn)，應(yīng)如何修改此算法？？4、操作ClearList(&L)在鏈表中的實(shí)現(xiàn):voidClearList(Linklist&L){//將單鏈表重新置為一個(gè)空表

while(L->next){

p=L->next;L->next=p->next;

}}//ClearListfree(p);算法時(shí)間復(fù)雜度：O(ListLength(L))如何從線性表得到單鏈表？

鏈表是一個(gè)動(dòng)態(tài)的結(jié)構(gòu)，它不需要予分配空間，因此生成鏈表的過程是一個(gè)結(jié)點(diǎn)“逐個(gè)插入”的過程。5、鏈表的建立操作方法一、頭插法要求：逆位序輸入n個(gè)數(shù)據(jù)元素的值，建立帶頭結(jié)點(diǎn)的單鏈表。操作步驟一、建立一個(gè)“空表”；二、輸入數(shù)據(jù)元素an，建立結(jié)點(diǎn)并插入在表頭；三、輸入數(shù)據(jù)元素an-1，建立結(jié)點(diǎn)并插入在表頭；ananan-1四、依次類推，直至輸入a1為止。P30/算法2.11操作步驟實(shí)現(xiàn)的主要語句：L=(LinkList)malloc(sizeof(LNode));//申請(qǐng)空間L->next=NULL;

//先建立一個(gè)帶頭結(jié)點(diǎn)的空單鏈表一、建立一個(gè)“空表”；二、輸入數(shù)據(jù)元素ai(i=n…1),

建立結(jié)點(diǎn)并插入在表頭；for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));//申請(qǐng)結(jié)點(diǎn)空間

scanf(&p->data);//輸入元素值

p->next=L->next;L->next=p;//插入}voidCreateList_L(LinkList&L,intn){//逆序輸入n個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的單鏈表}//CreateList_L算法的時(shí)間復(fù)雜度為:O(Listlength(L))L=(LinkList)malloc(sizeof(LNode));L->next=NULL;

//先建立一個(gè)帶頭結(jié)點(diǎn)的空單鏈表for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));

scanf(&p->data);//輸入元素值

p->next=L->next;L->next=p;//插入}P30/算法2.11思考：若順位序輸入n個(gè)數(shù)據(jù)元素的值，如何建立帶頭結(jié)點(diǎn)的單鏈表？操作步驟一、建立一個(gè)“空表”；二、輸入數(shù)據(jù)元素a1，建立結(jié)點(diǎn)并插入在表尾；三、輸入數(shù)據(jù)元素a2，建立結(jié)點(diǎn)并插入在表尾；a1a1a2五、最后，將an結(jié)點(diǎn)的指針域置空。四、依次類推，直至輸入an為止。方法二、尾插法操作步驟實(shí)現(xiàn)的主要語句：L=(LinkList)malloc(sizeof(LNode));//申請(qǐng)結(jié)點(diǎn)空間L->next=NULL;

//先建立一個(gè)帶頭結(jié)點(diǎn)的空單鏈表一、建立一個(gè)“空表”；二、輸入數(shù)據(jù)元素ai(i=1…n),

建立結(jié)點(diǎn)并插入在表尾；q=L;//q始終指向表尾結(jié)點(diǎn)for(i=0;i<n;++i){p=(LinkList)malloc(sizeof(LNode));//申請(qǐng)結(jié)點(diǎn)空間

scanf(&p->data);//輸入元素值

q->next=p;//插入

q=p;//q指向新表尾結(jié)點(diǎn)}算法：

學(xué)生課堂（或課后）自行完成三、將an結(jié)點(diǎn)的指針域置空。q->next=NULL;

voidCreateList_L(LinkList&L,intn){//順序輸入n個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的單鏈表}//CreateList_L算法的時(shí)間復(fù)雜度為:O(Listlength(L))L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一個(gè)帶頭結(jié)點(diǎn)的空單鏈表q=L;//q始終指向表尾結(jié)點(diǎn)for(i=0;i<n;++i){p=(LinkList)malloc(sizeof(LNode));//申請(qǐng)結(jié)點(diǎn)空間

scanf(&p->data);//輸入元素值

q->next=p;//插入新結(jié)點(diǎn)于表尾（即q結(jié)點(diǎn)之后）

q=p;//q指向新表尾結(jié)點(diǎn)}q->next=NULL;

//置尾部結(jié)點(diǎn)的指針域?yàn)榭找陨蠈?duì)鏈表的各種操作的討論可知，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)勢在于：

(1)能有效利用存儲(chǔ)空間；

(2)用"指針"指示數(shù)據(jù)元素之間的后繼關(guān)系，便于進(jìn)行"插入"、"刪除"等操作；

而其劣勢則是不能隨機(jī)存取數(shù)據(jù)元素,只能順序存取數(shù)據(jù)元素。四、有序表1.有序表類型類型定義2.應(yīng)用舉例例：將兩個(gè)有序單鏈表合并成一個(gè)有序單鏈表.分析：算法思想：

a1…...am^LaLb

b1…...bn^Pa（初始位置）pb（初始位置）LCpc（初始位置）

引進(jìn)3個(gè)指針pa,pb和pc，其中pa,pb分別指向La和Lb表中當(dāng)前待比較插入的結(jié)點(diǎn)，而pc指向Lc表當(dāng)前最后一個(gè)結(jié)點(diǎn)，若pa->data<=pb->data,則將pa所指結(jié)點(diǎn)鏈接到pc所指結(jié)點(diǎn)之后，否則將pb所指結(jié)點(diǎn)鏈接到pc所指結(jié)點(diǎn)之后。當(dāng)其中一個(gè)表為空時(shí)，則只要將另一個(gè)表的剩余段鏈接在pc所指的結(jié)點(diǎn)之后即可P31/算法2.12操作步驟：1.置初值：2.當(dāng)pa和pb皆為非空時(shí)，重復(fù)執(zhí)行：否則，將pb所指結(jié)點(diǎn)插入到pc所指結(jié)之后，pc后移，再pb后移；3.當(dāng)pa或pb非空時(shí)，將La或Lb中的剩余段鏈接到pc所指的結(jié)點(diǎn)之后若pa->data<=pb->data,則將pa所指結(jié)點(diǎn)插入到pc所指結(jié)點(diǎn)之后，再pc后移，pa后移；pc->next=pa;Pc=pa;pa=pa->nextpc->next=pb;Pc=pb;pb=pb->nextpc->next=pa?pa:pbpa=La->next;pb=Lb->next;Lc=Pc=La//用La的頭結(jié)點(diǎn)作為Ｌc的頭結(jié)點(diǎn)動(dòng)畫演示:VoidMergelist_L(Linklist&La,Linklist&Lb,Linklist&Lc){//已知單鏈線性表Ｌa和Ｌb的元素按值非遞增減排列//歸并La和Lb得到新的單鏈線性表Lc，Lc的元素也按值非遞減排列}//MergList_LPa=La->next;pb=Lb->next;Lc=pc=La//用La的頭結(jié)點(diǎn)作為Ｌc的頭結(jié)點(diǎn)While(pa&&pb){

if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;elsepc->next=pb;pc=pb;pb=pb->next;}pc->next=pa?pa:pb;

//將La或Lb的剩余段鏈接到Pc的結(jié)點(diǎn)之后free(Lb);//釋放Lb的頭結(jié)點(diǎn)P31/算法2.12用上述定義的單鏈表實(shí)現(xiàn)線性表的操作時(shí)，存在的問題：

改進(jìn)鏈表的設(shè)置：1．單鏈表的表長是一個(gè)隱含的值；

1．增加“表長”、“表尾指針”和“當(dāng)前位置的指針”三個(gè)數(shù)據(jù)域；2．在單鏈表的最后一個(gè)元素之后插入元素時(shí)，需遍歷整個(gè)鏈表；3．在鏈表中，元素的“位序”概念淡化，結(jié)點(diǎn)的“位置”概念加強(qiáng)。2．將基本操作中的“位序i”改變?yōu)椤爸羔榩”。五*、一個(gè)帶頭結(jié)點(diǎn)的線性鏈表類型typedefstructLNode{//結(jié)點(diǎn)類型

ElemTypedata;structLNode*next;}*Link,*Position;typedefstruct

{//鏈表類型

Linkhead,tail;//分別指向頭結(jié)點(diǎn)和

//

最后一個(gè)結(jié)點(diǎn)的指針

intlen;//指示鏈表長度

Linkcurrent;//指向當(dāng)前被訪問的結(jié)點(diǎn)

//的指針，初始位置指向頭結(jié)點(diǎn)}LinkList;P37

1.雙向鏈表六、其它形式的鏈表typedefstructDuLNode{

ElemTypedata;

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

structDuLNode*prior;

//指向前驅(qū)的指針域

structDuLNode*next;

//

指向后繼的指針域}

DuLNode,*DuLinkList;

最后一個(gè)結(jié)點(diǎn)的指針域的指針又指回第一個(gè)結(jié)點(diǎn)的鏈表2.循環(huán)鏈表a1a2…...an

和單鏈表的差別僅在于，判別鏈表中最后一個(gè)結(jié)點(diǎn)的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點(diǎn)”。也就是說：

單循環(huán)鏈表的操作和線性單鏈表基本一致，差別僅在于算法中的循環(huán)條件不是p或p->next是否為空,而應(yīng)是p或p->next是否為head。L空表：判空條件：L->next=L單循環(huán)鏈環(huán)特點(diǎn)：1）從任一結(jié)點(diǎn)出發(fā)都可訪問到表中所有結(jié)點(diǎn)2）用頭指針表示的單循環(huán)鏈找開始結(jié)點(diǎn)的時(shí)間是O（1）用頭指針表示的單循環(huán)鏈找終端結(jié)點(diǎn)的時(shí)間是O（n）3）用尾指針表示的單循環(huán)鏈找開始結(jié)點(diǎn)的時(shí)間是O（1）用尾指針表示的單循環(huán)鏈找終端結(jié)點(diǎn)的時(shí)間是O（1）

例：在單循環(huán)鏈表上實(shí)現(xiàn)將線性表不得

(a1,a2,…,an)和（b1,b2,…,bm)合成一個(gè)線性表(a1,a2,…,an,b1,b2,…,bm)的運(yùn)算。

用尾指針ra和rb分別表示兩個(gè)單循環(huán)鏈表，則僅需將一個(gè)的表尾和另一個(gè)表的表頭相接。分析：a1a2…...anb1b2…...bmrarb①②①:p=rb->nextrb->next=ra->next②:ra->next=p->nextp③:free(p)Linklistunion(Linklist

ra,Linklist

rb)//將表rb鏈到表ra之后，返回新鏈表尾指針{

p=rb->next;rb->next=ra->next;ra->next=p->next;

free(p);returnrb;}雙向循環(huán)鏈表空表非空表a1a2…...an判空條件：L->prior=L->next=L雙向鏈表的操作特點(diǎn)：“查詢”和單鏈表相同。“插入”和“刪除”時(shí)需要同時(shí)修改兩個(gè)方向上的指針。ai-1aies->next=p->next;p->next=s;s->next->prior=s;s->prior=p;psai-1ai插入ai-1刪除aiai+1p->next=p->next->next;p->next->prior=p;pai-1算法題：題集P17/2.13、2.14;P18/2.22作業(yè)2：實(shí)驗(yàn)題：

1.實(shí)驗(yàn)一鏈表的基本操作（驗(yàn)證性實(shí)驗(yàn)）——實(shí)驗(yàn)課之前并且在課外完成

2.實(shí)驗(yàn)一鏈表的基本操作（設(shè)計(jì)性實(shí)驗(yàn)）——實(shí)驗(yàn)課完成附加題:

編寫算法刪除鏈表中“多余”的數(shù)據(jù)元素，即使操作之后的順序表中所有元素的值都不相同。

在計(jì)算機(jī)中，可以用一個(gè)線性表來表示:P=(p0,p1,…，pn)一元多項(xiàng)式但是對(duì)于形如

S(x)=1+3x10000–2x20000的多項(xiàng)式，上述表示方法是否合適？2.4一元多項(xiàng)式

一般情況下的一元稀疏多項(xiàng)式可寫成

Pn(x)=p1xe1+p2xe2+┄+pmxem其中：pi

是指數(shù)為ei

的項(xiàng)的非零系數(shù)，

0≤e1<e2<┄<em=n可以下列線性表表示：（（p1,e1）,(p2,e2),┄,(pm,em)）

P999(x)=7x3-2x12-8x999例如:可用線性表

((7,3),(-2,12),(-8,999))表示ADTPolynomial{

數(shù)據(jù)對(duì)象：

數(shù)據(jù)關(guān)系：抽象數(shù)據(jù)類型一元多項(xiàng)式的定義如下：D＝{ai|ai∈TermSet,i=1,2,...,m,m≥0TermSet中的每個(gè)元素包含一個(gè)表示系數(shù)的實(shí)數(shù)和表示指數(shù)的整數(shù)

}R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n

且ai-1中的指數(shù)值＜ai中的指數(shù)值

}

CreatPolyn(&P,m)

DestroyPolyn(&P)

PrintPolyn(&P)

基本操作：操作結(jié)果：輸入

m項(xiàng)的系數(shù)和指數(shù)，建立一元多項(xiàng)式

P。初始條件：一元多項(xiàng)式P已存在。