2.1

線性表的類型定義2.3線性表類型的實現

鏈式映象2.4一元多項式的表示及相加2.2線性表類型的實現

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

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

b.有且僅有一個第一個元素和最后一個元素；

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

數據對象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數據關系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

基本操作：……}ADTList

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

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

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

假設上述基本操作已經實現，則可以利用上述定義的線性表基本操作，來實現其它更復雜的操作例

2-2例

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

用一組地址連續的存儲單元依次存放

線性表中的數據元素的存儲結構線性表的起始地址稱作線性表的基地址

a1a2

…ai-1ai

…an一.概念順序存儲：順序表：

用順序存儲的線性表就稱為順序表n為表的長度2.2線性表類型的實現-順序映象以“存儲位置相鄰”表示有序對<ai-1，ai>即：LOC(ai)=LOC(ai-1)+C

一個數據元素所占存儲量↑

所有數據元素的存儲位置均取決于第一個數據元素的存儲位置

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

↑基地址三、地址計算公式存儲地址

內在狀態

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

該元素實際所需的存儲空間3.便于隨機存?。?.不便于插入、刪除操作。

（會引起大量結點的移動）例如四.線性表的靜態順序存儲結構的C語言描述(補充內容）#defineMAXLEN80//線性表的最大長度typedefstruct{ElemTypeelem[MAXLEN];intlength;}SqListtp;//俗稱靜態順序表C語言中用一維數組來描述：

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

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

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

五.基本操作在靜態順序表上的實現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個元素。for(j=i;j<=L.length-1;j++)L.elem[j-1]=L.elem[j];//將第i元素之后的所有元素前移一位

L.length--;六.線性表的動態順序存儲結構的C語言描述typedefstruct{

}SqList;//俗稱動態順序表#defineLIST_INIT_SIZE80//線性表存儲空間的初始分配量#defineLISTINCREMENT10//線性表存儲空間的分配增量Elemtype*elem;//存儲空間基址int

length;//當前長度int

listsize;//當前分配的存儲容量

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

InitList(&L)1）申請分配“足夠應用”的線性表的存儲空間2）若分配失敗，則結束函數的執行3）若分配成功，則置：

a)表的當前長度為0b)當前分配的存儲容量為預分配空間的大小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){//構造一個空的線性表

}//InitList_Sq算法時間復雜度：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可見，基本操作是：將順序表中的元素逐個和給定值e相比較。2.定位操作：

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

intLocateElem_Sq(SqListL,ElemTypee,

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

//

在順序表中查詢第一個滿足判定條件的數據元素，

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

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

//p的初值為第1元素的存儲位置while

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

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

在第i個元素之前插入一個值為e的元素

問題：

插入元素時，線性表的

邏輯結構發生什么變化？P24/算法2.4

(a1,…,ai-1,ai,…,an)改變為

(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.[檢測參數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，插入位置不合法，算法結束；

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

StatusListInsert_Sq(SqList&L,inti,ElemTypee){

//

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

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

算法時間復雜度為: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){

//當前存儲空間已滿，增加分配

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

L.elem=newbase;//新基址

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

//

插入位置不合法考慮移動元素的平均情況:

假設在第

i個元素之前插入的概率為，

則在長度為n的線性表中插入一個元素所需移動元素次數的期望值為：

若假定在線性表中任何一個位置上進行插入的概率都是相等的，則移動元素的期望值為：首先分析：問題：刪除元素時，線性表的邏輯結構發生什么變化？4.刪除操作

ListDelete(&L,i,&e)的實現：

1）要求：

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

(a1,…,ai-1,ai,ai+1,…,an)改變為

(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.檢測（判斷參數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，刪除位置不合法，算法結束；3.修正表長

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

//

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

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考慮移動元素的平均情況:

假設刪除第

i個元素的概率為

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

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

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

分析：

假設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)

方法：

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

pb<=Lb.elem+Lb.length-1時,重復執行：

1）當*pa<=*pb，將*pa插入到Lc中pc指針所指示的位置,pa指針后移;否則，將*pb插入到Lc中pc指針所指示的位置,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作業1：實驗題：

1.實驗一順序表基本操作（驗證性實驗）——實驗課之前并且在課外完成

2.實驗一順序表基本操作（設計性實驗）——實驗課完成附加題:

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

一、單鏈表二、結點和單鏈表的C語言描述三、線性表的操作在單鏈表中的實現五、一個帶頭結點的單鏈表類型六、其它形式的鏈表四、有序表類型2.3線性表類型的實現-鏈式映象

用一組

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

+指針(指示后繼元素存儲位置)=結點

(表示數據元素或數據元素的映象)以“結點的序列”表示線性表

稱作鏈表

以線性表中第一個數據元素的存儲地址作為線性表的地址，稱作線性表的頭指針。頭結點

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

有時為了操作方便，在第一個結點之前虛加一個“頭結點”，以指向頭結點的指針為鏈表的頭指針?？罩羔樉€性表為空表時，頭結點的指針域為空

typedefstructLNode{ElemTypedata;//數據域

structLNode*next;//指針域

}LNode,*LinkList;

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

//生成含n個數據元素的鏈表1、線性表的取元素操作

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

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

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

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

//

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

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

ListInsert(&L,i,e)

在單鏈表中的實現：

有序對<ai-1,ai>

改變為<ai-1,e>和<e,ai>eaiai-1P29/算法2.9

a.查找第i個結點的前驅結點(或確定待插入的位置)

b.產生新結點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為帶頭結點的單鏈表的頭指針，本算法

//在鏈表中第i個結點之前插入新的元素e

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

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

//

尋找第i-1個結點if(!p||j>i-1)

returnERROR;//

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

問：如果單鏈表不帶頭結點，應如何修改此算法？？s=(LinkList)malloc(sizeof(LNode));

//生成新結點s->data=e;s->next=p->next;p->next=s;

//插入returnOK;3、線性表的刪除操作ListDelete(&L,i,&e)在鏈表中的實現:有序對<ai-1,ai>和<ai,ai+1>

改變為<ai-1,ai+1>ai-1aiai+1ai-1P30/算法2.10

在單鏈表中刪除第

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

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

//刪除以L為頭指針(帶頭結點)的單鏈表中第i個結點

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

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

//尋找第i個結點，并令p指向其前趨if(!(p->next)||j>i-1)

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

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

問：如果單鏈表不帶頭結點，應如何修改此算法？？4、操作ClearList(&L)在鏈表中的實現:voidClearList(Linklist&L){//將單鏈表重新置為一個空表

while(L->next){

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

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

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

//先建立一個帶頭結點的空單鏈表一、建立一個“空表”；二、輸入數據元素ai(i=n…1),

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

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

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

//先建立一個帶頭結點的空單鏈表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個數據元素的值，如何建立帶頭結點的單鏈表？操作步驟一、建立一個“空表”；二、輸入數據元素a1，建立結點并插入在表尾；三、輸入數據元素a2，建立結點并插入在表尾；a1a1a2五、最后，將an結點的指針域置空。四、依次類推，直至輸入an為止。方法二、尾插法操作步驟實現的主要語句：L=(LinkList)malloc(sizeof(LNode));//申請結點空間L->next=NULL;

//先建立一個帶頭結點的空單鏈表一、建立一個“空表”；二、輸入數據元素ai(i=1…n),

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

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

q->next=p;//插入

q=p;//q指向新表尾結點}算法：

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

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

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

q->next=p;//插入新結點于表尾（即q結點之后）

q=p;//q指向新表尾結點}q->next=NULL;

//置尾部結點的指針域為空以上對鏈表的各種操作的討論可知，鏈式存儲結構的優勢在于：

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

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

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

a1…...am^LaLb

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

引進3個指針pa,pb和pc，其中pa,pb分別指向La和Lb表中當前待比較插入的結點，而pc指向Lc表當前最后一個結點，若pa->data<=pb->data,則將pa所指結點鏈接到pc所指結點之后，否則將pb所指結點鏈接到pc所指結點之后。當其中一個表為空時，則只要將另一個表的剩余段鏈接在pc所指的結點之后即可P31/算法2.12操作步驟：1.置初值：2.當pa和pb皆為非空時，重復執行：否則，將pb所指結點插入到pc所指結之后，pc后移，再pb后移；3.當pa或pb非空時，將La或Lb中的剩余段鏈接到pc所指的結點之后若pa->data<=pb->data,則將pa所指結點插入到pc所指結點之后，再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的頭結點作為Ｌc的頭結點動畫演示: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的頭結點作為Ｌc的頭結點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的結點之后free(Lb);//釋放Lb的頭結點P31/算法2.12用上述定義的單鏈表實現線性表的操作時，存在的問題：

改進鏈表的設置：1．單鏈表的表長是一個隱含的值；

1．增加“表長”、“表尾指針”和“當前位置的指針”三個數據域；2．在單鏈表的最后一個元素之后插入元素時，需遍歷整個鏈表；3．在鏈表中，元素的“位序”概念淡化，結點的“位置”概念加強。2．將基本操作中的“位序i”改變為“指針p”。五*、一個帶頭結點的線性鏈表類型typedefstructLNode{//結點類型

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

{//鏈表類型

Linkhead,tail;//分別指向頭結點和

//

最后一個結點的指針

intlen;//指示鏈表長度

Linkcurrent;//指向當前被訪問的結點

//的指針，初始位置指向頭結點}LinkList;P37

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

ElemTypedata;

//數據域

structDuLNode*prior;

//指向前驅的指針域

structDuLNode*next;

//

指向后繼的指針域}

DuLNode,*DuLinkList;

最后一個結點的指針域的指針又指回第一個結點的鏈表2.循環鏈表a1a2…...an

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

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

例：在單循環鏈表上實現將線性表不得

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

用尾指針ra和rb分別表示兩個單循環鏈表，則僅需將一個的表尾和另一個表的表頭相接。分析：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;}雙向循環鏈表空表非空表a1a2…...an判空條件：L->prior=L->next=L雙向鏈表的操作特點：“查詢”和單鏈表相同?！安迦搿焙汀皠h除”時需要同時修改兩個方向上的指針。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作業2：實驗題：

1.實驗一鏈表的基本操作（驗證性實驗）——實驗課之前并且在課外完成

2.實驗一鏈表的基本操作（設計性實驗）——實驗課完成附加題:

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

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

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

一般情況下的一元稀疏多項式可寫成

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

是指數為ei

的項的非零系數，

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

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

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

數據對象：

數據關系：抽象數據類型一元多項式的定義如下：D＝{ai|ai∈TermSet,i=1,2,...,m,m≥0TermSet中的每個元素包含一個表示系數的實數和表示指數的整數

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

且ai-1中的指數值＜ai中的指數值

}

CreatPolyn(&P,m)

DestroyPolyn(&P)

PrintPolyn(&P)

基本操作：操作結果：輸入

m項的系數和指數，建立一元多項式

P。初始條件：一元多項式P已存在。