數(shù)據(jù)結(jié)構(gòu)課件：第2章 線(xiàn)性表

教學(xué)內(nèi)容第1章緒論第2章線(xiàn)性表第3章棧和隊(duì)列第4章串第5章數(shù)組和廣義表第6章樹(shù)和二叉樹(shù)第7章圖第8章查找第9章排序第2章線(xiàn)性表2.1線(xiàn)性表的定義2.2線(xiàn)性表的順序表示和實(shí)現(xiàn)2.3線(xiàn)性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.4雙向鏈表2.5一元多項(xiàng)式的表示及相加線(xiàn)性結(jié)構(gòu)（線(xiàn)性表、棧、隊(duì)列、串）

線(xiàn)性結(jié)構(gòu)是最常用、最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)。而線(xiàn)性表是一種典型的線(xiàn)性結(jié)構(gòu)。其基本特點(diǎn)是線(xiàn)性表中的數(shù)據(jù)元素是有序且是有限的。在這種結(jié)構(gòu)中：①

存在一個(gè)唯一的被稱(chēng)為“第一個(gè)”的數(shù)據(jù)元素；②存在一個(gè)唯一的被稱(chēng)為“最后一個(gè)”的數(shù)據(jù)元素；③

除第一個(gè)元素外，每個(gè)元素均有唯一一個(gè)直接前驅(qū)；④

除最后一個(gè)元素外，每個(gè)元素均有唯一一個(gè)直接后繼。2.1線(xiàn)性表的定義線(xiàn)性表(LinearList)：是由n(n≧0)個(gè)數(shù)據(jù)元素(結(jié)點(diǎn))a1，a2…an組成的有限序列。該序列中的所有結(jié)點(diǎn)具有相同的數(shù)據(jù)類(lèi)型。其中數(shù)據(jù)元素的個(gè)數(shù)n稱(chēng)為線(xiàn)性表的長(zhǎng)度。當(dāng)n=0時(shí)，稱(chēng)為空表。當(dāng)n>0時(shí)，將非空的線(xiàn)性表記作：(a1，a2，…an)a1稱(chēng)為線(xiàn)性表的第一個(gè)(首)結(jié)點(diǎn)，an稱(chēng)為線(xiàn)性表的最后一個(gè)(尾)結(jié)點(diǎn)。a1，a2…ai-1都是ai(2≦i≦n)的前驅(qū)，其中ai-1是ai的直接前驅(qū);ai+1，ai+2…an都是ai(1≦i≦n-1)的后繼，其中ai+1是ai的直接后繼。線(xiàn)性表的邏輯結(jié)構(gòu)線(xiàn)性表中的數(shù)據(jù)元素ai所代表的具體含義隨具體應(yīng)用的不同而不同，在線(xiàn)性表的定義中，只不過(guò)是一個(gè)抽象的表示符號(hào)。線(xiàn)性表中的結(jié)點(diǎn)可以是單值元素(每個(gè)元素只有一個(gè)數(shù)據(jù)項(xiàng))。例1:26個(gè)英文字母組成的字母表：(A，B，…、Z）例2：某校從1978年到1983年各種型號(hào)的計(jì)算機(jī)擁有量的變化情況：(6，17，28，50，92，188）例3：一副撲克的點(diǎn)數(shù)(2，3，4…，J，Q，K，A)線(xiàn)性表的邏輯結(jié)構(gòu)線(xiàn)性表中的結(jié)點(diǎn)可以是記錄型元素，每個(gè)元素含有多個(gè)數(shù)據(jù)項(xiàng)，每個(gè)項(xiàng)稱(chēng)為結(jié)點(diǎn)的一個(gè)域。每個(gè)元素有一個(gè)可以唯一標(biāo)識(shí)每個(gè)結(jié)點(diǎn)的數(shù)據(jù)項(xiàng)組，稱(chēng)為關(guān)鍵字。例4：某校2001級(jí)同學(xué)的基本情況：線(xiàn)性表的邏輯結(jié)構(gòu)若線(xiàn)性表中的結(jié)點(diǎn)是按值(或按關(guān)鍵字值)由小到大(或由大到小)排列的，稱(chēng)線(xiàn)性表是有序的。線(xiàn)性表是一種相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu)，其長(zhǎng)度可根據(jù)需要增長(zhǎng)或縮短。對(duì)線(xiàn)性表的數(shù)據(jù)元素不僅可以訪(fǎng)問(wèn)，還可以進(jìn)行插入和刪除等操作。線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型定義（1）ADTList{數(shù)據(jù)對(duì)象：D={ai|ai∈ElemSet,i=1,2,…,n,n≧0}數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1,ai∈D,i=2,3,…,n}基本操作：InitList(&L)操作結(jié)果：構(gòu)造一個(gè)空的線(xiàn)性表L；ListLength(L)初始條件：線(xiàn)性表L已存在；操作結(jié)果：返回L中數(shù)據(jù)元素個(gè)數(shù)；線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型定義（2）…GetElem(L,i,&e)初始條件：線(xiàn)性表L已存在，1≦i≦ListLength(L)；操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值；ListInsert(L,i,&e)初始條件：線(xiàn)性表L已存在，1≦i≦ListLength(L)；操作結(jié)果：在線(xiàn)性表L中的第i個(gè)位置插入元素e；…}ADTList線(xiàn)性表的基本操作（1）(1)初始化線(xiàn)性表InitList(&L):構(gòu)造一個(gè)空的線(xiàn)性表L。(2)銷(xiāo)毀線(xiàn)性表DestroyList(&L):釋放線(xiàn)性表L占用的內(nèi)存空間。(3)清空線(xiàn)性表ClearList(&L):將線(xiàn)性表重置為空表。(4)判線(xiàn)性表是否為空表ListEmpty(L):若L為空表,則返回真,否則返回假。(5)求線(xiàn)性表的長(zhǎng)度ListLength(L):返回L中元素個(gè)數(shù)。線(xiàn)性表的基本操作（2）(6)求線(xiàn)性表L中指定位置的某個(gè)數(shù)據(jù)元素GetElem(L,i,&e):用e返回L中第i(1≤i≤ListLength(L))個(gè)元素的值。(7)定位查找LocateElem(L,e):返回L中第1個(gè)值域與e相等的位序。若這樣的元素不存在,則返回值為0。(8)插入數(shù)據(jù)元素ListInsert(&L,i,e):在L的第i(1≤i≤ListLength(L)+1)個(gè)元素之前插入新的元素e,L的長(zhǎng)度增1。(9)刪除數(shù)據(jù)元素ListDelete(&L,i,&e):刪除L的第i(1≤i≤ListLength(L))個(gè)元素,并用e返回其值,L的長(zhǎng)度減1。

例2.1

假設(shè)有兩個(gè)集合A和B分別用兩個(gè)線(xiàn)性表LA和LB表示,即線(xiàn)性表中的數(shù)據(jù)元素即為集合中的成員。編寫(xiě)一個(gè)算法求一個(gè)新的集合A=A∪B,即將兩個(gè)集合的并集放在線(xiàn)性表LC中。解:算法思想是:擴(kuò)大線(xiàn)性表LA，將存在于線(xiàn)性表LB中而不存在于線(xiàn)性表LA中的數(shù)據(jù)元素插入到線(xiàn)性表LA中去。只要從線(xiàn)性交LB中依次取得每個(gè)數(shù)據(jù)元素，并依值在線(xiàn)性表LA中進(jìn)行查訪(fǎng)，若不存在，則插入到表中。算法如下:voidUnion(List&La,ListLb){//算法2.1

//將所有在線(xiàn)性表Lb中但不在La中的數(shù)據(jù)元素插入到La中

intLa_len,Lb_len,i;

ElemTypee;

La_len=ListLength(La);//求線(xiàn)性表的長(zhǎng)度

Lb_len=ListLength(Lb);

for(i=1;i<=Lb_len;i++){

GetElem(Lb,i,e);//取Lb中第i個(gè)數(shù)據(jù)元素賦給e

if(!LocateElem(La,e,equal))//La中不存在和e相同的數(shù)據(jù)元素

ListInsert(La,++La_len,e);//插入

}}//union由于LocateElem(LA,e)運(yùn)算的時(shí)間復(fù)雜度為O(ListLength(LA)),所以本算法的時(shí)間復(fù)雜度為:

O(ListLength(LA)*ListLength(LB))。2.2線(xiàn)性表的順序表示和實(shí)現(xiàn)順序存儲(chǔ)：把線(xiàn)性表的結(jié)點(diǎn)按邏輯順序依次存放在一組地址連續(xù)的存儲(chǔ)單元里。用這種方法存儲(chǔ)的線(xiàn)性表簡(jiǎn)稱(chēng)順序表。順序存儲(chǔ)的線(xiàn)性表的特點(diǎn)：

線(xiàn)性表的邏輯順序與物理順序一致;

數(shù)據(jù)元素之間的關(guān)系是以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來(lái)體現(xiàn)。2.2.1

線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)設(shè)有非空的線(xiàn)性表：(a1，a2，…an)。順序存儲(chǔ)如圖所示。

…a1a2…ai…an…Loc(a1)Loc(a1)+(i-1)*l

在具體的機(jī)器環(huán)境下：設(shè)線(xiàn)性表的每個(gè)元素需占用l個(gè)存儲(chǔ)單元，以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。則線(xiàn)性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai)之間滿(mǎn)足下列關(guān)系：

LOC(ai+1)=LOC(ai)+l

線(xiàn)性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為：

LOC(ai)=LOC(a1)+(i-1)*l

LOC(a1)是線(xiàn)性表的第一個(gè)數(shù)據(jù)元素a1的存儲(chǔ)位置，通常稱(chēng)做線(xiàn)性表的起始位置或基地址。元素在計(jì)算機(jī)內(nèi)物理位置相鄰來(lái)表示線(xiàn)性表中數(shù)據(jù)元素之間的邏輯關(guān)系。只要確定了存儲(chǔ)線(xiàn)性表的起始位置，線(xiàn)性表中任一數(shù)據(jù)元素都可以隨機(jī)可取，所以線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。

在高級(jí)語(yǔ)言(如C語(yǔ)言)環(huán)境下：數(shù)組也具有隨機(jī)存取的特性，因此，借助數(shù)組來(lái)描述順序表的存儲(chǔ)結(jié)構(gòu)。由于線(xiàn)性表的長(zhǎng)度可變，且所需最大存儲(chǔ)空間隨問(wèn)題不同而不同，所以在C語(yǔ)言中可以用動(dòng)態(tài)分配的一維數(shù)組來(lái)描述。#defineLIST_INIT_SIZE100

//線(xiàn)性表存儲(chǔ)空間的初始分配量#defineLISTINCREMENT10

//線(xiàn)性表存儲(chǔ)空間的分配增量

typedefstruct{

ElemType*elem;

//線(xiàn)性表存儲(chǔ)空間基址

intlength;

//當(dāng)前線(xiàn)性表長(zhǎng)度

intlistsize;

//當(dāng)前分配的線(xiàn)性表存儲(chǔ)空間大小，以//sizeof(ElemType)為單位）

}SqList;在介紹基本操作的算法之前，先回顧本書(shū)算法中常用的兩C函數(shù)1)

malloc(intsize)

功能：在系統(tǒng)內(nèi)存中分配size個(gè)的存儲(chǔ)單元，并返回該空間的基址。

使用方法：...intm=100,float*p;

p=(float*)malloc(m*sizeof(float));

執(zhí)行語(yǔ)句p=(float*)malloc(m*sizeof(float))，計(jì)算機(jī)將按float

類(lèi)型變量所占空間的大?。ㄒ话銥?2bit）分配m*sizeof(float)個(gè)的存儲(chǔ)單元,并將其基址賦值給指針變量p;2)

free(p)

功能：將指針變量p所指示的存儲(chǔ)空間，回收到系統(tǒng)內(nèi)存空間中去；

使用方法：

...

intm=100;float*p;

p=(float*)malloc(m*sizeof(float));//一旦p所指示的內(nèi)存空間不再使用

//調(diào)用free()回收之

free(p);2.2.2

順序表的基本操作

順序存儲(chǔ)結(jié)構(gòu)中，很容易實(shí)現(xiàn)線(xiàn)性表的一些操作：如隨機(jī)存取第i個(gè)數(shù)據(jù)元素等。特別注意的是，C語(yǔ)言中數(shù)組的下標(biāo)是從0開(kāi)始的，因此，若L是SqList類(lèi)型的順序表，則表中第i個(gè)數(shù)據(jù)元素是L.elem[i-1]。有關(guān)順序表的操作有初始化、賦值、查找、修改、插入、刪除、求長(zhǎng)度等。以下將對(duì)幾種主要的操作進(jìn)行討論。1線(xiàn)性表的初始化操作voidInitList(SqList&L,intmaxsize){//算法2.3

//構(gòu)造一個(gè)空的線(xiàn)性表LL.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//存儲(chǔ)分配失敗

L.length=0;//空表長(zhǎng)度為0

L.listsize=LIST_INIT_SIZE;//初始存儲(chǔ)容量

ReturnOK;}//InitList_Sq2

順序線(xiàn)性表的插入

在線(xiàn)性表L=(a1，…ai-1，ai，ai+1，…，an)中的第i(1≦i≦n)個(gè)位置上插入一個(gè)新結(jié)點(diǎn)e，使其成為線(xiàn)性表：

L=(a1，…ai-1，e，ai，ai+1，…，an)

實(shí)現(xiàn)步驟：將線(xiàn)性表L中的第i個(gè)至第n個(gè)結(jié)點(diǎn)后移一個(gè)位置。將結(jié)點(diǎn)e插入到結(jié)點(diǎn)ai-1之后。線(xiàn)性表長(zhǎng)度加1。算法描述：StatusListInsert_Sq(SqList&L,inti,ElemTypee){//算法2.4

//在順序線(xiàn)性表L的第i個(gè)元素之前插入新的元素e，

//i的合法值為1≤i≤ListLength_Sq(L)+1

ElemType*p;

if(i<1||i>L.length+1)returnERROR;//i值不合法

if(L.length>=L.listsize){//當(dāng)前存儲(chǔ)空間已滿(mǎn)，增加容量

ElemType*newbase=(ElemType*)realloc(L.elem,

(L.listsize+LISTINCREMENT)*sizeof(ElemType));

if(!newbase)returnERROR;//存儲(chǔ)分配失敗

L.elem=newbase;//新基址

L.listsize+=LISTINCREMENT;//增加存儲(chǔ)容量

}

ElemType*q=&(L.elem[i-1]);//q為插入位置

for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;

//插入位置及之后的元素右移*q=e;//插入e

++L.length;//表長(zhǎng)增1

returnOK;}//ListInsert_Sq

時(shí)間復(fù)雜度分析

在線(xiàn)性表L中的第i個(gè)元素之前插入新結(jié)點(diǎn)，其時(shí)間主要耗費(fèi)在表中結(jié)點(diǎn)的移動(dòng)操作上，因此，可用結(jié)點(diǎn)的移動(dòng)來(lái)估計(jì)算法的時(shí)間復(fù)雜度。

設(shè)在線(xiàn)性表L中的第i個(gè)元素之前插入結(jié)點(diǎn)的概率為Pi，不失一般性，設(shè)各個(gè)位置插入是等概率，則Pi=1/(n+1)，而插入時(shí)移動(dòng)結(jié)點(diǎn)的次數(shù)為n-i+1。總的平均移動(dòng)次數(shù)：Einsert=∑pi*(n-i+1)(1≦i≦n+1)∴Einsert=n/2。即在順序表上做插入運(yùn)算，平均要移動(dòng)表上一半結(jié)點(diǎn)。當(dāng)表長(zhǎng)n較大時(shí)，算法的效率相當(dāng)?shù)?。因此算法的平均時(shí)間復(fù)雜度為O(n)。3順序線(xiàn)性表的刪除

在線(xiàn)性表L=(a1，…ai-1，ai，ai+1，…，an)中刪除結(jié)點(diǎn)ai(1≦i≦n)，使其成為線(xiàn)性表：

L=(a1，…ai-1，ai+1，…，an)

實(shí)現(xiàn)步驟：將線(xiàn)性表L中的第i+1個(gè)至第n個(gè)結(jié)點(diǎn)依此向前移動(dòng)一個(gè)位置。線(xiàn)性表長(zhǎng)度減1。算法描述:StatusListDelete_Sq(SqList&L,inti,ElemType&e){//算法2.5//在順序線(xiàn)性表L中刪除第i個(gè)元素，并用e返回其值。

//i的合法值為1≤i≤ListLength_Sq(L)。

ElemType*p,*q;if(i<1||i>L.length)returnERROR;//i值不合法

p=&(L.elem[i-1]);//p為被刪除元素的位置

e=*p;//被刪除元素的值賦給eq=L.elem+L.length-1;//表尾元素的位置

for(++p;p<=q;++p)*(p-1)=*p;//被刪除元素之后的元素左移

--L.length;//表長(zhǎng)減1returnOK;}//ListDelete_Sq時(shí)間復(fù)雜度分析:刪除線(xiàn)性表L中的第i個(gè)元素，其時(shí)間主要耗費(fèi)在表中結(jié)點(diǎn)的移動(dòng)操作上，因此，可用結(jié)點(diǎn)的移動(dòng)來(lái)估計(jì)算法的時(shí)間復(fù)雜度。設(shè)在線(xiàn)性表L中刪除第i個(gè)元素的概率為Pi，不失一般性，設(shè)刪除各個(gè)位置是等概率，則Pi=1/n，而刪除時(shí)移動(dòng)結(jié)點(diǎn)的次數(shù)為n-i。則總的平均移動(dòng)次數(shù)：Edelete=∑pi*(n-i)(1≦i≦n)∴Edelete=(n-1)/2。即在順序表上做刪除運(yùn)算，平均要移動(dòng)表上一半結(jié)點(diǎn)。當(dāng)表長(zhǎng)n較大時(shí)，算法的效率相當(dāng)?shù)?。因此算法的平均時(shí)間復(fù)雜度為O(n)。4順序線(xiàn)性表的查找定位刪除

在線(xiàn)性表L=(a1，a2，…，an)中刪除值為x的第一個(gè)結(jié)點(diǎn)。實(shí)現(xiàn)步驟:在線(xiàn)性表L查找值為x的第一個(gè)數(shù)據(jù)元素。將從找到的位置至最后一個(gè)結(jié)點(diǎn)依次向前移動(dòng)一個(gè)位置。

線(xiàn)性表長(zhǎng)度減1。算法描述:StatusLocate_Delete_SqList(Sqlist*L，ElemTypex)/*刪除線(xiàn)性表L中值為x的第一個(gè)結(jié)點(diǎn)*/{inti=0,k;while(i<L->length)/*查找值為x的第一個(gè)結(jié)點(diǎn)*/{if(L->Elem_array[i]!=x)i++;else{for(k=i+1;k<L->length;k++)L->Elem_array[k-1]=L->Elem_array[k];L->length--;break;}}if(i>L->length){printf(“要?jiǎng)h除的數(shù)據(jù)元素不存在!\n”);returnERROR;}returnOK;}

時(shí)間復(fù)雜度分析:

時(shí)間主要耗費(fèi)在數(shù)據(jù)元素的比較和移動(dòng)操作上。首先，在線(xiàn)性表L中查找值為x的結(jié)點(diǎn)是否存在;其次，若值為x的結(jié)點(diǎn)存在，且在線(xiàn)性表L中的位置為i，則在線(xiàn)性表L中刪除第i個(gè)元素。設(shè)在線(xiàn)性表L刪除數(shù)據(jù)元素概率為Pi，不失一般性，設(shè)各個(gè)位置是等概率，則Pi=1/n。

◆比較的平均次數(shù)：Ecompare=∑pi*i(1≦i≦n)∴Ecompare=(n+1)/2。◆刪除時(shí)平均移動(dòng)次數(shù)：Edelete=∑pi*(n-i)(1≦i≦n)∴Edelete=(n-1)/2。

◆平均時(shí)間復(fù)雜度：Ecompare+Edelete=n，即為O(n)線(xiàn)性表的順序存儲(chǔ)特點(diǎn)：1通過(guò)元素的存儲(chǔ)順序反映線(xiàn)性表中數(shù)據(jù)元素之間的邏輯關(guān)系；2可隨機(jī)存取順序表的元素；3順序表的插入刪除操作要通過(guò)移動(dòng)元素實(shí)現(xiàn)(平均移動(dòng)一半的元素，n/2)；2.3線(xiàn)性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

2.3.1線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

鏈?zhǔn)酱鎯?chǔ)：用一組任意的存儲(chǔ)單元存儲(chǔ)線(xiàn)性表中的數(shù)據(jù)元素。用這種方法存儲(chǔ)的線(xiàn)性表簡(jiǎn)稱(chēng)線(xiàn)性鏈表。

存儲(chǔ)鏈表中結(jié)點(diǎn)的一組任意的存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。鏈表中結(jié)點(diǎn)的邏輯順序和物理順序不一定相同。

為了正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其直接后繼結(jié)點(diǎn)的地址(或位置)，稱(chēng)為指針(pointer)或鏈(link)，這兩部分組成了鏈表中的結(jié)點(diǎn)結(jié)構(gòu)，如圖所示。

鏈表是通過(guò)每個(gè)結(jié)點(diǎn)的指針域?qū)⒕€(xiàn)性表的n個(gè)結(jié)點(diǎn)按其邏輯次序鏈接在一起的。

每一個(gè)結(jié)只包含一個(gè)指針域的鏈表，稱(chēng)為單鏈表。

為操作方便，總是在鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)頭結(jié)點(diǎn)(頭指針)head指向第一個(gè)結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息(或鏈表長(zhǎng)度等信息)。datanextdata：數(shù)據(jù)域，存放結(jié)點(diǎn)的值。next：指針域，存放結(jié)點(diǎn)的直接后繼的地址。數(shù)據(jù)域指針域存儲(chǔ)地址數(shù)據(jù)域指針域

1 Li 437 Qian 1313 Sun 1 19 Wang NULL25 Wu 3731 Zhao 737 Zheng1943 Zhou 2531頭指針H單鏈表：

線(xiàn)性鏈表的邏輯狀態(tài)LiZhaoQianSunZhouWuZhengWang^H1

結(jié)點(diǎn)的描述與實(shí)現(xiàn)

C語(yǔ)言中用帶指針的結(jié)構(gòu)體類(lèi)型，即結(jié)構(gòu)指針來(lái)描述:typedefstructLnode{ElemTypedata;/*數(shù)據(jù)域，保存結(jié)點(diǎn)的值*/structLnode*next;/*指針域*/}LNode;/*結(jié)點(diǎn)的類(lèi)型*/a1an^a2...頭指針H頭結(jié)點(diǎn)H^非空表空表線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上緊鄰，每個(gè)元素的存儲(chǔ)位置都可以從線(xiàn)性表的起始位置計(jì)算得到，因此是隨機(jī)可取的。線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，單鏈表中的任何兩個(gè)元素的存儲(chǔ)位置之間沒(méi)有固定的聯(lián)系,因此單鏈表是非隨機(jī)可取的存儲(chǔ)結(jié)構(gòu)。單鏈表中每個(gè)元素的位置都包含在其直接前驅(qū)結(jié)點(diǎn)的信息之中。假設(shè)p指向線(xiàn)性表中的第i個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)ai）的指針，則p->next是指向第i+1個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)ai+1）的指針。若p->data=ai，則p->next->data=ai+12結(jié)點(diǎn)的實(shí)現(xiàn)

結(jié)點(diǎn)是通過(guò)動(dòng)態(tài)分配和釋放來(lái)的實(shí)現(xiàn)，即需要時(shí)分配，不需要時(shí)釋放。實(shí)現(xiàn)時(shí)是分別使用C語(yǔ)言提供的標(biāo)準(zhǔn)函數(shù)：malloc()，realloc()，sizeof()，free()。動(dòng)態(tài)分配

p=(LNode*)malloc(sizeof(LNode));函數(shù)malloc分配了一個(gè)類(lèi)型為L(zhǎng)Node的結(jié)點(diǎn)變量的空間，并將其首地址放入指針變量p中。動(dòng)態(tài)釋放free(p);系統(tǒng)回收由指針變量p所指向的內(nèi)存區(qū)。P必須是最近一次調(diào)用malloc函數(shù)時(shí)的返回值。3常用的基本操作及其示意圖⑴結(jié)點(diǎn)的賦值LNode*p;p=(LNode*)malloc(sizeof(LNode));p->data=20;p->next=NULL;p20NULL①

q=p;pa……操作前pa……q操作后②

q=p->next;bpa……操作前操作后qbpa……③

p=p->next;bpa……操作前操作后pba……④

q->next=p;c…pbqa……操作前操作后qb……ac…p(a)⑵常見(jiàn)的指針操作⑤

q->next=p->next;(a)xy…pbqa……操作前操作后qb……axy…p操作前ypx……bqa…操作后ypx……bqa…(b)操作前ypx……bqa…操作后ypx……bqa…(b)課堂練習(xí)：對(duì)以下單鏈表分別執(zhí)行下列各程序段，畫(huà)出結(jié)果示意圖。2573864∧LPQRSL=P->next；R->data=P->data;R->data=P->next->data;P->next->next->next->data=P->data；T=P;while(T!=NULL){T->data=T->data*2；T=T->next；}T=P;while(T->next!=NULL){T->data=T->data*2；T=T->next;}2.3.2

單鏈表的基本操作1建立單鏈表2單鏈表的查找3單鏈表的插入4單鏈表的刪除5單鏈表的合并1

建立單鏈表動(dòng)態(tài)地建立單鏈表的常用方法有如下兩種：頭插入法，尾插入法。尾部插入方法生成的鏈表中結(jié)點(diǎn)的次序和輸入的順序是相同的，即將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾，使其成為當(dāng)前鏈表的尾結(jié)點(diǎn)。算法描述：voidCreateList_L(LinkList&L,intn){//算法2.11

//逆位序輸入（隨機(jī)產(chǎn)生）n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線(xiàn)性表L

LinkListp;

inti;

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL;//先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表

for(i=n;i>0;--i){

p=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點(diǎn)

p->data=random(200);//改為一個(gè)隨機(jī)生成的數(shù)字

p->next=L->next;L->next=p;//插入到表頭

}}//CreateList_L無(wú)論是哪種插入方法，如果要插入建立的單線(xiàn)性鏈表的結(jié)點(diǎn)是n個(gè)，算法的時(shí)間復(fù)雜度均為O(n)。(1)

按序號(hào)查找

取單鏈表中的第i個(gè)元素。

對(duì)于單鏈表，不能象順序表中那樣直接按序號(hào)i訪(fǎng)問(wèn)結(jié)點(diǎn)，而只能從鏈表的頭結(jié)點(diǎn)出發(fā)，沿鏈域next逐個(gè)結(jié)點(diǎn)往下搜索，直到搜索到第i個(gè)結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。

設(shè)單鏈表的長(zhǎng)度為n，要查找表中第i個(gè)結(jié)點(diǎn)，僅當(dāng)1≦i≦n時(shí)，i的值是合法的。2

單鏈表的查找算法描述StatusGetElem_L(LinkList&L,inti,ElemType&e){//算法2.8

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

//當(dāng)?shù)趇個(gè)元素存在時(shí)，其值賦給e并返回OK，否則返回ERROR

LinkListp;

p=L->next;

intj=1;//初始化，p指向第一個(gè)結(jié)點(diǎn)，j為計(jì)數(shù)器

while(p&&j<i){//順指針向后查找，直到p指向第i個(gè)元素或p為空

p=p->next;++j;

}

if(!p||j>i)returnERROR;//第i個(gè)元素不存在

e=p->data;//取第i個(gè)元素

returnOK;}//GetElem_L移動(dòng)指針p的頻度：i<1時(shí)：0次;i∈[1,n]：i-1次；i>n：n次?！鄷r(shí)間復(fù)雜度:O(n)。(2)

按值查找

按值查找是在鏈表中，查找是否有結(jié)點(diǎn)值等于給定值key的結(jié)點(diǎn)?若有，則返回首次找到的值為key的結(jié)點(diǎn)的存儲(chǔ)位置；否則返回NULL。查找時(shí)從開(kāi)始結(jié)點(diǎn)出發(fā)，沿鏈表逐個(gè)將結(jié)點(diǎn)的值和給定值key作比較。算法描述：LNode

*Locate_Node(LNode*L，intkey)/*在以L(fǎng)為頭結(jié)點(diǎn)的單鏈表中查找值為key的第一個(gè)結(jié)點(diǎn)*/{LNode*p=L–>next;while(p!=NULL&&p–>data!=key)p=p–>next;if(p–>data==key)returnp;else{printf(“所要查找的結(jié)點(diǎn)不存在!!\n”);retutn(NULL);}}算法的執(zhí)行與形參key有關(guān)，平均時(shí)間復(fù)雜度為O(n)。插入運(yùn)算是將值為e的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1所在的結(jié)點(diǎn)p，然后生成一個(gè)數(shù)據(jù)域?yàn)閑的新結(jié)點(diǎn)s，s結(jié)點(diǎn)作為p的直接后繼結(jié)點(diǎn)。3

單鏈表的插入abps->next=p->next;p->next=s;注意：順序不能反abesp

算法描述：StatusListInsert_L(LinkList&L,inti,ElemTypee){//算法2.9

//在帶頭結(jié)點(diǎn)的單鏈線(xiàn)性表L的第i個(gè)元素之前插入元素e

LinkListp,s;

p=L;

intj=0;

while(p&&j<i-1){//尋找第i-1個(gè)結(jié)點(diǎn)

p=p->next;

++j;

}

if(!p||j>i-1)returnERROR;//i小于1或者大于表長(zhǎng)

s=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點(diǎn)

s->data=e;s->next=p->next;//插入L中

p->next=s;

returnOK;}//LinstInsert_L

設(shè)鏈表的長(zhǎng)度為n，合法的插入位置是1≦i≦n。算法的時(shí)間主要耗費(fèi)移動(dòng)指針p上，故時(shí)間復(fù)雜度亦為O(n)。⑴按序號(hào)刪除

刪除單鏈表中的第i個(gè)結(jié)點(diǎn)。

為了刪除第i個(gè)結(jié)點(diǎn)ai，必須找到結(jié)點(diǎn)的存儲(chǔ)地址。該存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn)ai-1的next域中，因此，必須首先找到ai-1的存儲(chǔ)位置p，然后令p–>next指向ai的直接后繼結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間，將其歸還給“存儲(chǔ)池”。

4

單鏈表的刪除abpcabpp->next=p->next->next設(shè)單鏈表長(zhǎng)度為n，則刪去第i個(gè)結(jié)點(diǎn)僅當(dāng)1≦i≦n時(shí)是合法的。則當(dāng)i=n+1時(shí)，雖然被刪結(jié)點(diǎn)不存在，但其前趨結(jié)點(diǎn)卻存在，是終端結(jié)點(diǎn)。故判斷條件之一是p–>next!=NULL。顯然此算法的時(shí)間復(fù)雜度也是O(n)。算法描述StatusListDelete_L(LinkList&L,inti,ElemType&e){//算法2.10

//在帶頭結(jié)點(diǎn)的單鏈線(xiàn)性表L中，刪除第i個(gè)元素，并由e返回其值

LinkListp,q;

p=L;

intj=0;

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

p=p->next;

++j;

}

if(!(p->next)||j>i-1)returnERROR;//刪除位置不合理

q=p->next;

p->next=q->next;//刪除并釋放結(jié)點(diǎn)

e=q->data;

free(q);

returnOK;}//ListDelete_L⑵按值刪除

刪除單鏈表中值為key的第一個(gè)結(jié)點(diǎn)。與按值查找相類(lèi)似，首先要查找值為key的結(jié)點(diǎn)是否存在?若存在，則刪除；否則返回NULL。算法描述voidDelete_LinkList(LNode*L，intkey)/*刪除以L(fǎng)為頭結(jié)點(diǎn)的單鏈表中值為key的第一個(gè)結(jié)點(diǎn)*/{LNode*p=L,*q=L–>next;while(q!=NULL&&q–>data!=key){p=q;q=q–>next;}if(q–>data==key){p->next=q->next;free(q);}elseprintf(“所要?jiǎng)h除的結(jié)點(diǎn)不存在!!\n”);}

算法的執(zhí)行與形參key有關(guān)，平均時(shí)間復(fù)雜度為O(n)。從上面的討論可以看出，鏈表上實(shí)現(xiàn)插入和刪除運(yùn)算，無(wú)需移動(dòng)結(jié)點(diǎn)，僅需修改指針。解決了順序表的插入或刪除操作需要移動(dòng)大量元素的問(wèn)題。假設(shè)s為指向節(jié)點(diǎn)x的指針，則在p節(jié)點(diǎn)后面插入s節(jié)點(diǎn)指針修改語(yǔ)句為：s->next=p->next；p->next=s刪除p節(jié)點(diǎn)，修改指針語(yǔ)句為：p->next=p->next->next設(shè)有兩個(gè)有序的單鏈表，它們的頭指針?lè)謩e是La、Lb，將它們合并為以L(fǎng)c為頭指針的有序鏈表。合并前的示意圖如圖所示。15?-249……

Lb

pb-7312……

23?La

Lcpapc5

單鏈表的合并合并了值為-7，-2的結(jié)點(diǎn)后示意圖如圖所示。

合并了值為-7，-2的結(jié)點(diǎn)后的狀態(tài)-249……

15?Lb

pcpbLc-7312……

23?La

pa算法說(shuō)明算法中pa，pb分別是待考察的兩個(gè)鏈表的當(dāng)前結(jié)點(diǎn)，pc是合并過(guò)程中合并的鏈表的最后一個(gè)結(jié)點(diǎn)。如果pa->data≤pb->data，則將pa所指節(jié)點(diǎn)鏈接到pc所指結(jié)點(diǎn)之后，否則將pb所指節(jié)點(diǎn)鏈接到pc所指結(jié)點(diǎn)之后。如果其中一個(gè)指針為空，說(shuō)明有一個(gè)表的元素已經(jīng)歸并完成，只需要將另外一個(gè)表的剩余段鏈接在pc所指節(jié)點(diǎn)之后。算法描述voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){

//算法2.12

//已知單鏈線(xiàn)性表La和Lb的元素按值非遞減排列。

//歸并La和Lb得到新的單鏈線(xiàn)性表Lc，Lc的元素也按值非遞減排列。

LinkListpa,pb,pc;pa=La->next;pb=Lb->next;Lc=pc=La;//用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn)

while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;//插入剩余段

free(Lb);//釋放Lb的頭結(jié)點(diǎn)}//MergeList_L若La，Lb兩個(gè)鏈表的長(zhǎng)度分別是m，n，則鏈表合并的時(shí)間復(fù)雜度為O(m+n)。線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)特點(diǎn)：1通過(guò)保存直接后繼元素的存儲(chǔ)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系；2插入刪除操作通過(guò)修改結(jié)點(diǎn)的指針實(shí)現(xiàn)；3不能隨機(jī)存取元素；單鏈表與順序表的比較：比較順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)訪(fǎng)問(wèn)方式順序存取/直接存取從鏈表頭順序存取邏輯關(guān)系與物理位置完全對(duì)應(yīng)不一定對(duì)應(yīng)存儲(chǔ)空間利用率無(wú)附加空間附加一個(gè)指針的空間查找速度快慢插入和刪除速度慢快空間限制靜態(tài)分配：不能擴(kuò)充不需事先分配動(dòng)態(tài)分配：擴(kuò)充需移動(dòng)元素靜態(tài)鏈表（了解）可以借用一維數(shù)組來(lái)描述線(xiàn)性鏈表。靜態(tài)單鏈表的存儲(chǔ)結(jié)構(gòu)：#defineMAXSIZE1000//鏈表的最大長(zhǎng)度Typedefstruct{ElemTypedata；intcur；}component，SLinkList[MAXSIZE];數(shù)組的一個(gè)分量表示一個(gè)節(jié)點(diǎn)，同時(shí)用游標(biāo)（cur）代替指針指示節(jié)點(diǎn)在數(shù)組中的相對(duì)位置。2.3.3

循環(huán)鏈表

循環(huán)鏈表(CircularLinkedList)：是一種頭尾相接的鏈表。其特點(diǎn)是最后一個(gè)結(jié)點(diǎn)的指針域指向鏈表的頭結(jié)點(diǎn)，整個(gè)鏈表的指針域鏈接成一個(gè)環(huán)。從循環(huán)鏈表的任意一個(gè)結(jié)點(diǎn)出發(fā)都可以找到鏈表中的其它結(jié)點(diǎn)，使得表處理更加方便靈活。下圖是帶頭結(jié)點(diǎn)的單循環(huán)鏈表的示意圖?？毡矸强毡韆1

a2

……anhead

head

循環(huán)鏈表的操作

對(duì)于單循環(huán)鏈表，除鏈表的合并外，其它的操作和單線(xiàn)性鏈表基本上一致，僅僅需要在單線(xiàn)性鏈表操作算法基礎(chǔ)上作以下簡(jiǎn)單修改：⑴判斷是否是空鏈表：head->next==head;⑵判斷是否是表尾結(jié)點(diǎn)：p->next==head

;2.4

雙向鏈表雙向鏈表(DoubleLinkedList):指的是構(gòu)成鏈表的每個(gè)結(jié)點(diǎn)中設(shè)立兩個(gè)指針域：一個(gè)指向其直接前趨的指針域prior，一個(gè)指向其直接后繼的指針域next。這樣形成的鏈表中有兩個(gè)方向不同的鏈，故稱(chēng)為雙向鏈表。

和單鏈表類(lèi)似，雙向鏈表一般增加頭指針也能使雙鏈表上的某些運(yùn)算變得方便。

將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來(lái)也能構(gòu)成循環(huán)鏈表，并稱(chēng)之為雙向循環(huán)鏈表。

雙向鏈表是為了克服單鏈表的單向性的缺陷而引入的。1雙向鏈表的結(jié)點(diǎn)及其類(lèi)型定義

雙向鏈表的結(jié)點(diǎn)的類(lèi)型定義如下。其結(jié)點(diǎn)形式如圖所示，帶頭結(jié)點(diǎn)的雙向鏈表的形式如圖所示。typedefstructDulnode{ElemTypedata;structDulnode*prior,*next;}DulNode;datanextprior

雙向鏈表結(jié)點(diǎn)形式……非空雙向鏈表head?a2a1an?空雙向鏈表head??

帶頭結(jié)點(diǎn)的雙向鏈表形式雙向鏈表結(jié)構(gòu)具有對(duì)稱(chēng)性，設(shè)p指向雙向鏈表中的某一結(jié)點(diǎn)，則其對(duì)稱(chēng)性可用下式描述：(p->prior)->next=p=(p->next)->prior;

結(jié)點(diǎn)p的存儲(chǔ)位置存放在其直接前趨結(jié)點(diǎn)p->prior的直接后繼指針域中，同時(shí)也存放在其直接后繼結(jié)點(diǎn)p->next的直接前趨指針域中。2雙向鏈表的基本操作

雙向鏈表中，有一些操作，比如說(shuō)求鏈表長(zhǎng)度，取鏈表中某個(gè)結(jié)點(diǎn)值，定位等操作僅僅需要涉及一個(gè)方向的指針，則它們的算法描述和線(xiàn)性鏈表的操作相同，但是在插入、刪除時(shí)又很大的不同，在雙向鏈表中需要同時(shí)修改兩個(gè)方向的指針。雙向鏈表的插入（算法2.18）

將值為e的結(jié)點(diǎn)插入雙向鏈表中。插入前后鏈表的變化如圖所示。s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=sABCps

(2)雙向鏈表的結(jié)點(diǎn)刪除（算法2.19）

設(shè)要?jiǎng)h除的結(jié)點(diǎn)為p，刪除時(shí)可以不引入新的輔助指針變量，可以直接先斷鏈，再釋放結(jié)點(diǎn)。部分語(yǔ)句組如下：ABCpp->prior->next=p->next;p->next->prior=p->prior;free(p);2.5

一元多項(xiàng)式的表示和相加1一元多項(xiàng)式的表示

一元多項(xiàng)式p(x)=p0+p1x+p2x2+…

+pnxn，由n+1個(gè)系數(shù)唯一確定。則在計(jì)算機(jī)中可用線(xiàn)性表(p0

，p1

，p2

，…

，pn

)表示。既然是線(xiàn)性表，就可以用順序表和鏈表來(lái)實(shí)現(xiàn)。兩種不同實(shí)現(xiàn)方式的元素類(lèi)型定義如下：(1)順序存儲(chǔ)表示的類(lèi)型typedefstruct{floatcoef;/*系數(shù)部分*/intexpn;/*指數(shù)部分*/}ElemType;(2)鏈?zhǔn)酱鎯?chǔ)表示的類(lèi)型typedefstructploy{floatcoef;/*系數(shù)部分*/intexpn;/*指數(shù)部分*/structploy*next;}Ploy; S(x)=1+3x10000+2x20000

可采用另一種方式，即用非0項(xiàng)（系數(shù)，指數(shù)）構(gòu)成的線(xiàn)性表表示一元多項(xiàng)式，

S=((1,0),(3,10000),(2,20000))如果只存儲(chǔ)非0系數(shù)，則必須同時(shí)存儲(chǔ)相應(yīng)的指數(shù)一元n次多項(xiàng)式可寫(xiě)為：Pn(x)=p1xe1+p2xe2+p3xe3+…+pmxem（pi是指數(shù)為ei的項(xiàng)的非0系數(shù)，且0≤e1<e2<…<em=n我們可用一個(gè)長(zhǎng)度為m且每個(gè)元素有兩個(gè)數(shù)據(jù)項(xiàng)（系數(shù)項(xiàng)和指數(shù)項(xiàng)）的線(xiàn)性表((p1,e1),(p2,e2),…,(pm,em))，便可唯一確定多項(xiàng)式Pn(x)-17031517∧98如果采用線(xiàn)性鏈表來(lái)實(shí)現(xiàn)一元多項(xiàng)式則

A(x)=7+3x+9x8+5x17 B(x)=8x+22x7-9x8

的存儲(chǔ)狀態(tài)如下：81-1227-98∧

2一元多項(xiàng)式的相加

不失一般性，設(shè)有兩個(gè)一元多項(xiàng)式：P(x)=p0+p1x+p2x2+…

+pnxn，Q(x)=q0+q1x+q2x2+…

+qmxm(m<n)R(x)=P(x)+Q(x)

R(x)由線(xiàn)性表R((p0+q0)，(p1+q1)，(p2+q2)，…

，(pm+qm)，…

，

pn)唯一表示。⑴順序存儲(chǔ)表示的相加線(xiàn)性表的定義typedefstruct{ElemTypea[MAX_SIZE];intlength;}Sqlist;

用順序表示的相加非常簡(jiǎn)單。訪(fǎng)問(wèn)第5項(xiàng)可直接訪(fǎng)問(wèn)：L.a[4].coef，

L.a[4].expn(2)

鏈?zhǔn)酱鎯?chǔ)表示的相加當(dāng)采用鏈?zhǔn)酱鎯?chǔ)表示時(shí)，根據(jù)結(jié)點(diǎn)類(lèi)型定義，凡是系數(shù)為0的項(xiàng)不在鏈表中出現(xiàn)，從而可以大大減少鏈表的長(zhǎng)度。一元多項(xiàng)式相加的實(shí)質(zhì)：

指數(shù)不同：是鏈表的合并。指數(shù)相同：系數(shù)相加，和為0，去掉結(jié)點(diǎn)，和不為0，修改結(jié)點(diǎn)的系數(shù)域。算法之一：

就在原來(lái)兩個(gè)多項(xiàng)式鏈表的基礎(chǔ)上進(jìn)行相加，相加后原來(lái)兩個(gè)多項(xiàng)式鏈表就不在存在。當(dāng)然再要對(duì)原來(lái)兩個(gè)多項(xiàng)式進(jìn)行其它操作就不允許了。算法描述Ploy*add_ploy(ploy*La，ploy*Lb)/*將以L(fǎng)a，Lb為頭指針表示的一元多項(xiàng)式相加*/{ploy*Lc,*pc,*pa,*pb,*ptr;floatx;Lc=pc=La;pa=La->next;pb=Lb->next;while(pa!=NULL&&pb!=NULL){if(pa->expn<pb->expn){pc->next=pa;pc=pa;pa=pa->next;}/*將pa所指的結(jié)點(diǎn)合并，pa指向下一個(gè)結(jié)點(diǎn)*/if(pa->expn>pb->expn){pc->next=pb;pc=pb;pb=pb->next;}/*將pb所指的結(jié)點(diǎn)合并，pb指向下一個(gè)結(jié)點(diǎn)*/else{x=pa->coef+pb->coef;if(abs(x)<=1.0e-6)/*如果系數(shù)和為0，刪除兩個(gè)結(jié)點(diǎn)*/{ptr=pa;pa=pa->next;free(ptr);ptr=pb;pb=pb->next;free(ptr);}else/*如果系數(shù)和不為0，修改其中一個(gè)結(jié)點(diǎn)的系數(shù)域，刪除另一個(gè)結(jié)點(diǎn)*/{pc->next=pa;pa->coef=x;pc=pa;pa=pa->next;ptr=pb;pb=pb->next;free(pb);}}}/*endofwhile*/if(pa==NULL)pc->next=pb;elsepc->next=pa;return(Lc);}算法之二：

對(duì)兩個(gè)多項(xiàng)式鏈表進(jìn)行相加，生成一個(gè)新的相加后的結(jié)果多項(xiàng)式鏈表，原來(lái)兩個(gè)多項(xiàng)式鏈表依然存在，不發(fā)生任何改變，如果要再對(duì)原來(lái)兩個(gè)多項(xiàng)式進(jìn)行其它操作也不影響。算法描述Ploy*add_ploy(ploy*La，ploy*Lb)/*將以L(fǎng)a，Lb為頭指針表示的一元多項(xiàng)式相加，生成一個(gè)新的結(jié)果多項(xiàng)式*/{ploy*Lc,*pc,*pa,*pb,*p;floatx;Lc=pc=(ploy*)malloc(sizeof(ploy));pa=La->next;pb=Lb->next;while(pa!=NULL&&pb!=NULL){if(pa->expn<pb->expn){p=(ploy*)malloc(sizeof(ploy));p->coef=pa->coef;p->expn=pa->expn;p->next