數(shù)據(jù)結(jié)構(gòu)-線性表-ppt課件-文檔資料

數(shù)據(jù)結(jié)構(gòu)--線性表--ppt課件-文檔資料第一頁，共103頁。第二章線性表

在本課程介紹的幾種數(shù)據(jù)結(jié)構(gòu)中，線性表是最常簡單的，也是最常用的數(shù)據(jù)結(jié)構(gòu)，線性表在實際應(yīng)用大量使用，并不是一個陌生的概念。第二頁，共103頁。

基本內(nèi)容

1線性表的概念；

2線性表兩類存儲結(jié)構(gòu)和它們的類型定義；

3在這些存儲結(jié)構(gòu)下，線性表的基本操作的算法；學(xué)習(xí)要點：

1了解線性表邏輯結(jié)構(gòu)的特征;

2重點掌握線性表的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，它們?nèi)绾伪磉_(dá)線性表中數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系；如何用C語言描述它們的類型定義；3掌握在順序存儲結(jié)構(gòu)下，線性表的基本操作的算法；

4掌握在鏈?zhǔn)酱鎯Y(jié)構(gòu)下，線性表的基本操作的算法；

5能夠從時間復(fù)雜度的角度，比較線性表兩類存儲結(jié)構(gòu)的不同特點及適用場合；

第二章線性表

第三頁，共103頁。線性表是n個類型相同數(shù)據(jù)元素的有限序列，通常記作(a1,a2,a3,…,an)2.1線性表的概念例1、數(shù)學(xué)中的數(shù)列（11，13，15，17，19，21）

例2、英文字母表（A,B,C,D,EZ）。

例3、某單位的電話號碼簿。一、線性表的邏輯結(jié)構(gòu)

電話號碼簿是數(shù)據(jù)元素的有限序列，每一數(shù)據(jù)元素包括兩個數(shù)據(jù)項，一個是用戶姓名，一個是對應(yīng)的電話號碼。

姓名電話號碼蔡穎63214444陳紅63217777劉建平63216666王小林63218888張力63215555...第四頁，共103頁。2.1線性表的概念說明：設(shè)A=(a1,a2,...,ai-1,ai,ai+1,…,an)是一線性表1）線性表的數(shù)據(jù)元素可以是各種各樣的，但同一線性表中的元素須是同一類型的；2）在表中ai-1領(lǐng)先于ai，ai領(lǐng)先于ai+1，稱ai-1是ai的直接前趨，ai+1是ai的直接后繼；3）在線性表中，除第一個元素和最后一個元素之外，其他元素都有且僅有一個直接前趨，有且僅有一個直接后繼，具有這種結(jié)構(gòu)特征的數(shù)據(jù)結(jié)構(gòu)稱為線性結(jié)構(gòu)。線性表是一種線性數(shù)據(jù)結(jié)構(gòu)；4）線性表中元素的個數(shù)n稱為線性表的長度，n=0時稱為空表；5）ai是線性表的第i個元素，稱i為數(shù)據(jù)元素ai的序號，每一個元素在線性表中的位置，僅取決于它的序號；第五頁，共103頁。2.1線性表的概念設(shè)L=（a1,a2,...ai-1,ai,ai+1,…,an）是一線性表1初始化操作InitList(&L)功能：建立空的線性表L；2銷毀操作DetroyList(&L)功能：回收為線性表L動態(tài)分配的存儲空間；3置空操作ClearList(&L)功能：L中已存在，重新將其置成空表；4判空操作ListEmpty(L)功能：判斷線性表L是否為空表，若為空表返回TRUE，否則返回FALSE；5求表長操作

ListLength(L)功能：返回線性表L的表長；二、線性表的基本操作6取元素操作：GetElem(L,i,&e)功能：將線性表L中第i個元素賦值給

e；7查找操作LocateElem(L,e,compare())功能：在線性表L中查找與元素e滿足compare()的第1個元素，返回該元素在表中的序號（或位置），若表中不存在這樣的元素，則返回0；8插入操作ListInsert(&L,i,e)功能：在線性表L的第i個元素之前插入一個新元素e;9刪除操作

ListDelete(&L,i,&e)功能：刪除線性表L的第i個元素，并用e返回；10遍歷操作

ListTraverse(&L,visit())功能：依次對線性表L的每一個元素調(diào)用函數(shù)visit()。若visit()失敗，則返回ERROR，否則返回OK；說明1上面列出的操作，只是線性表的一些常用的基本操作；2不同的應(yīng)用，基本操作可能是不同的；

例如：上面列出的刪除操作Delete(&L,i,&e),功能是在線性表L中刪除第i個元素，并用e返回其值。在電話號碼查詢系統(tǒng)中，一旦某用戶撤掉某部電話，則需在系統(tǒng)的電話號碼簿中刪除該用戶對應(yīng)的數(shù)據(jù)，因此電話號碼查詢系統(tǒng)，需要提供這樣的功能，在電話號碼簿中刪除與給定元素e值相同的數(shù)據(jù)元素；3線性表的復(fù)雜操作可通過基本操作實現(xiàn)；

這有點類似于數(shù)中的情形，例如整數(shù)的基本操作是+,-,,/。如果要求某班同學(xué)的平均年齡則可利用+/實現(xiàn)，全班同學(xué)的平均年齡=(age1+age2+age3+…)/全班同學(xué)的人數(shù)

例如，我們要在設(shè)計一個電話號碼詢系統(tǒng)，顯然這個系統(tǒng)至少要具備下列功能：

·

查詢某人的電話號碼；

·在電話號碼薄中，插入一新用戶姓名及電話號碼；

·在電話號碼薄中，刪除已撤銷的用戶姓名及電話號碼；

由上我們知道，電話號碼薄可用線性表表示，上面列出的功能實際上就是對線性表的查找、插入、刪除操作，為了在計算機(jī)上實現(xiàn)上述功能，我們應(yīng)該做什么呢？

顯然，首先需要將電話號碼薄上的信息存儲到計算機(jī)中，然后才可能對這些信息進(jìn)行加工處理，實現(xiàn)上述功能。第六頁，共103頁。

2.2

線性表的順序存儲和實現(xiàn)

一、線性表的順序存儲結(jié)構(gòu)——順序表1.線性表的順序存儲結(jié)構(gòu)2.順序表的類型定義二、順序表的基本操作算法三、利用基本操作實現(xiàn)線性表的其他操作第七頁，共103頁。為了存儲線性表，至少要保存兩類信息：

1）線性表中的數(shù)據(jù)元素；

2）線性表中數(shù)據(jù)元素的順序關(guān)系；2.2線性表的順序存儲和實現(xiàn)

在計算機(jī)內(nèi)部可以采用不同的方式來存儲一個線性表，其中最簡單的方式就是本節(jié)要講的線性表的順序存儲結(jié)構(gòu)。第八頁，共103頁。線性表的順序存儲結(jié)構(gòu)，就是用一組連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元素。用順序表存儲線性表時，數(shù)據(jù)元素之間的邏輯關(guān)系，是通過數(shù)據(jù)元素的存儲順序反映出來的a1a2ai-1aiai+1an線性表(a1,a2a3,...an)的順序存儲結(jié)構(gòu)用順序存儲結(jié)構(gòu)存儲的線性表:稱為順序表2.2線性表的順序存儲和實現(xiàn)一、線性表的順序存儲結(jié)構(gòu):順序表1.線性表的順序存儲結(jié)構(gòu)第九頁，共103頁。2.2線性表的順序存儲和實現(xiàn)說明：在順序存儲結(jié)構(gòu)下，線性表元素之間的邏輯關(guān)系，可通過元素的存儲順序反映（表示）出來，所以只需存儲數(shù)據(jù)元素的信息；假沒線性表中每個數(shù)據(jù)元素占用k個存儲單元，那么，在順序存儲結(jié)構(gòu)中，線性表的第i個元素的存儲位置與第1個元素的存儲位置的關(guān)系是：Loc(ai)=Loc(a1)+(i–1)k

這里L(fēng)oc(ai)是第i個元素的存儲位置,Loc(a1)是第1個元素的存儲位置，也稱為線性表的基址；第十頁，共103頁。2.2線性表的順序存儲和實現(xiàn)怎樣在計算機(jī)上實現(xiàn)線性表的順序存儲結(jié)構(gòu)？？2、順序表的類型定義

以上用自然語言描述了線性表的順序存儲結(jié)構(gòu)，怎樣將這種存儲方式在計算機(jī)上實現(xiàn)？為此，我們用C語言對這種存儲方式進(jìn)行描述，我們知道C語言一維數(shù)組的機(jī)內(nèi)表示也是順序結(jié)構(gòu)，因此，可借用C語言的一維數(shù)組實現(xiàn)線性表的順序存儲。第十一頁，共103頁。2.2線性表的順序存儲和實現(xiàn)順序表的類型定義

#defineLIST_INIT_SIZE100//線性表存儲空間的初始分配量

#defineLISTINCREMENT10//線性表存儲空間的分配增量

typedefstruct{

ElemType*elem;//線性表存儲空間基址

intlength;//當(dāng)前線性表長度

intlistsize;//當(dāng)前分配的線性表存儲空間大小(以sizeof(ElemType)為單位)

}SqList;SqList：類型名，SqList類型的變量是結(jié)構(gòu)變量，它的三個域分別是：

*elem：

存放線性表元素的一維數(shù)組基址；其存儲空間在初始化操作（建空表）時動態(tài)分配；

length：

存放線性表的表長；

listsize：用于存放當(dāng)前分配（存放線性表元素）的存儲空間的大小。第十二頁，共103頁。2.2線性表的順序存儲和實現(xiàn)順序表圖示a1a2ai-1aiai+1anL.lengthL.listsizeL.elemnLIST_INIT_SIZE存放線性表元素的一維數(shù)組設(shè)A=（a1,a2,a3,...an）是一線性表，L是SqList類型的結(jié)構(gòu)變量，用于存放線性表A，則L在內(nèi)存中的狀態(tài)如圖所示：第十三頁，共103頁。2.2線性表的順序存儲和實現(xiàn)

二、順序表的基本操作算法回顧本書算法中常用到的兩個C函數(shù)。

1)

Malloc(intsize)

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

使用方法：

...

intm=100,float*p;

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

執(zhí)行語句p=(float*)malloc(m*sizeof(float))，計算機(jī)將按float類型變量所占空間的大小(一般為32bit)分配m*sizeof(float)個的存儲單元,并將其基址賦值給指針變量p;第十四頁，共103頁。

01299p

p=(float*)malloc(m*sizeof(float))圖示2.2線性表的順序存儲和實現(xiàn)第十五頁，共103頁。調(diào)用free(p)

01299p

調(diào)用free(p)圖示2)

free(p)

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

intm=100;float*p;

p=(float*)malloc(m*sizeof(float));//一旦p所指示的內(nèi)存空間不再使用，//調(diào)用free()回收之

free(p);2.2線性表的順序存儲和實現(xiàn)第十六頁，共103頁。如何在順序表上實現(xiàn)線性表的基本操作？如何建空表？如何求表長？如何插入？刪除？？

設(shè)線性表用順序表L存儲，下面我們介紹用順序表存儲線性表時，各種基本操作的算法。當(dāng)線性表用順序表存儲時，對線性表各種基本操作實際上就是對存儲在內(nèi)存中的順序表進(jìn)行操作。2.2線性表的順序存儲和實現(xiàn)第十七頁，共103頁。1）初始化操作InitList_Sq(SqList&L)

參數(shù)：L是存放線性表的結(jié)構(gòu)變量（稱L為順序表）,因為插入操作對順序表L進(jìn)行了修改,所以用了引用參數(shù)&L;功能：建立空的順序表L主要步驟：調(diào)用malloc()為順序表分配一預(yù)定大小(LIST_INIT_SIZE）的空間,并將其基址賦值給L.elem;

初始化操作演示2.2線性表的順序存儲和實現(xiàn)第十八頁，共103頁。

順序表初始化01LIST_INIT_SIZE-1L.lengthL.listsizeL.elem0LIST_INIT_SIZE

再演示一次2.2線性表的順序存儲和實現(xiàn)第十九頁，共103頁。初始化操作算法：StatusInitList_Sq(SqList&L){//構(gòu)造一個空的順序表LL.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//存儲分配失敗

L.length=0;//空表長度為0

L.listsize=LIST_INIT_SIZE;//初始存儲容量

ReturnOK;}//InitList_Sq

算法2.32.2線性表的順序存儲和實現(xiàn)第二十頁，共103頁。

銷毀操作圖示2銷毀操作

DetroyList(SqList&L)

功能：回收為順序表動態(tài)分配的存儲空間

主要步驟：調(diào)用free()回收為順序表動態(tài)分配的存儲空間2.2線性表的順序存儲和實現(xiàn)第二十一頁，共103頁。

銷毀順序表L.lengthL.listsizeL.elem01LIST_INIT_SIZE-1a1a2ai-1aiai+1an

nLIST_INIT_SIZE00=null

再演示一次2.2線性表的順序存儲和實現(xiàn)第二十二頁，共103頁。銷毀操作算法：

StatusDetroyList_Sq(SqList&L){

If(!L.elem)returnERROR;//若表L不存在

free(L.elem);//若表L已存在，回收動態(tài)分配的存儲空間

L.elem=null;

L.length=0;

L.Listsize=0;

returnOK;

}//DetroyList_Sq2.2線性表的順序存儲和實現(xiàn)第二十三頁，共103頁。

置空操作圖示3、置空操作ClearList_Sq(SqList&L)

功能：若L已存在，重新將其置成空表；

算法：

StatusClearList_Sq(SqList&L){

If(!L.elem)returnERROR;//若表L不存在

L.length=0;//若表L已存在，將L置空

returnOK;

}//ClearList_Sq2.2線性表的順序存儲和實現(xiàn)第二十四頁，共103頁。2.2線性表的順序存儲和實現(xiàn)L.lengthL.listsizeL.elem0199a1a2ai-1aiai+1an

n

990置空操作圖示置空再演示一次第二十五頁，共103頁。取元素操作圖示6取元素操作

GetElem_Sq(SqListL,inti,ElemType&e)

功能：將順序表中第i個元素賦值給e

算法：

StatusGetElem_Sq(SqList&L,inti,ElemType&e){

if((i<1)||(i>L.length-1))returnERROR;//i非法

e=L.elem[i-1];//將順序表中第i個元素賦值給e

returnOK;

}//GetElem_Sq

由于C語言的一維數(shù)組下標(biāo)從0開始,故線性表的第一個元素放在L.elem[0]，第i個素放L.elem[i-1]中，最后一個元素放在L.elem[L.length-1]中。2.2線性表的順序存儲和實現(xiàn)第二十六頁，共103頁。

取元素操作

nLIST_INIT_SIZEL.lengthL.listsizeL.elem01LIST_INIT_SIZE-1a1a2ai-1aiai+1annLIST_INIT_SIZE-1eai

再演示一次2.2線性表的順序存儲和實現(xiàn)第二十七頁，共103頁。8插入操作

ListInsert_Sq(&L,i,e)

參數(shù)：L:順序表，i插入位置，e被插入元素;因為插入操作對順序表進(jìn)行修改,所以用了引用參數(shù)&L;

功能：在順序表L的第i個元素之前插入一個新元素e;插入操作示意圖：2.2線性表的順序存儲和實現(xiàn)第二十八頁，共103頁。

為初學(xué)者易于理解插入算法主要步驟，這里簡化了書上的插入算法2.4，對插入算法中表空間已滿的情況，只簡單的返回出錯（ERROR），在2.2的最后部分給出完整的插入算法。當(dāng)然，應(yīng)用中對各種情況的如何處理，要根據(jù)實際問題的需要來決定。注意2.2線性表的順序存儲和實現(xiàn)第二十九頁，共103頁。2.2線性表的順序存儲和實現(xiàn)

插入操作圖示插入操作主要步驟：1）i是否合法，若合法轉(zhuǎn)2），否則算法結(jié)束，并返回ERROR；

2）L是否已滿，若未滿轉(zhuǎn)3），否則算法結(jié)束，并返回ERROR；3）將順序表ai及之后的所有元素后移一個位置；

4)將新元素寫入空出的位置；

5）表長+1；用鼠標(biāo)單擊圖中的綠字第三十頁，共103頁。StatusListInsert_Sq(SqList&L,inti,ElemTypee){

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

//i的合法值為1≤i≤L.length+1,當(dāng)i=L.length+1時//e插在表尾

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

if(L.length>=L.listsize)returnERROR;//順序表已滿

for(j=L.length-1;j>=i-1;--j)L.elem[j+1]=L.elem[j];

//插入位置及之后的元素后移一個位置

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

++L.length;//表長增1

returnOK;

}//ListInsert_Sq算法2.4a插入操作算法為初學(xué)者易于理解插入算法，這里通過下標(biāo)引用L.elem中的元素。2.2線性表的順序存儲和實現(xiàn)第三十一頁，共103頁。2.2線性表的順序存儲和實現(xiàn)StatusListInsert_Sq(SqList&L,intI,ElemTypee){

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

//i的合法值為1≤i≤L.length+1

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

if(L.length>=L.listsize)returnERROR;//順序表已滿

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

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

//插入位置及之后的元素后移一個位置

*q=e;//插入e

++L.length;//表長加1

returnOK;

}//ListInsert_Sq算法2.4b算法2.4b與算法2.4a唯一的不同是通過指針p引用L.elem中的元素。第三十二頁，共103頁。2.2線性表的順序存儲和實現(xiàn)

插入位置移動元素個數(shù)

1

n

2

n-1

in-i+1

n1

n+10

算法時間復(fù)雜度分析

下面分析插入算法的時間復(fù)雜度。順序表的插入算法2.4a或2.4b中，基本操作是移動元素，算法時間復(fù)雜度取決于移動元素的個數(shù)，即算法時間復(fù)雜度取決于算法中循環(huán)體執(zhí)行次數(shù)。移動元素的個數(shù)不僅與表長有關(guān)，而且與插入位置有關(guān)。第三十三頁，共103頁。2.2線性表的順序存儲和實現(xiàn)由此可見

·在順序表中插入一個元素，平均要移動表的一半元素。

·表長為n的順序表，插入算法的時間復(fù)雜度為On）假設(shè)在線性表的任何位置插入元素的概率相同，即pi=1/(n+1),則

若用pi表示在順序表的第i個元素之前插入元素的概率，在長度為n的順序表中插入一個元素，所需移動元素個數(shù)數(shù)學(xué)期望值為：第三十四頁，共103頁。2.2線性表的順序存儲和實現(xiàn)9.刪除操作:ListDelete_sq(SqList&L,inti,ElemType&e)

·功能：刪除順序表L的第i個元素，并用e返回

·刪除操作圖示第三十五頁，共103頁。

刪除操作主要步驟：

1）i不合法或表空，算法結(jié)束，并返回ERROR；否則轉(zhuǎn)2）

2）將ai賦值給e;

3）將順序表中ai后面的元素依次向前移動一個位置;

4）表長-12.2線性表的順序存儲和實現(xiàn)

刪除操作圖示用鼠標(biāo)單擊圖中的綠字第三十六頁，共103頁。2.2線性表的順序存儲和實現(xiàn)

刪除操作算法StatusListDelete_Sq(SqList&L,inti,ElemType&e){

//在順序表L中刪除第i個元素，并用e返回其值

//i的合法值為1≤i≤L.length，//表空L.length=0則i>L.lengthif((i<1)||(i>L.length))returnERROR;//i值不合法或表空

e=L.elem[i-1];//被刪除元素的值賦給e

for(j=i;j<=L.length-1;++j)L.elem[j-1]=L.elem[j]//被刪除元素之后的元素前移

--L.length;//表長減1

returnOK;

}//ListDelete_Sq

算法2.5a為初學(xué)者易于理解插入算法，這里通過下標(biāo)引用L.elem中的元素。第三十七頁，共103頁。2.2線性表的順序存儲和實現(xiàn)StatusListDelete_Sq(SqList&L,intI,ElemType&e){

//在順序線性表L中刪除第.i個元素，并用e返回其值

//i的合法值為1≤i≤L.length//表空L.length=0則i>L.length

if((i<1)||(i>L.Length))returnERROR;//i值不合法或表空

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

e=*p;//被刪除元素的值賦給e

q=L.elem[L.length-1];//表尾元素的位置

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

--L.length;//表長減1

returnOK;

}//ListDelete_Sq算法2.5b刪除操作算法算法2.5b與算法2.5a唯一的不同是通過指針p引用L.elem中的元素。第三十八頁，共103頁。第二章習(xí)題習(xí)題三1P162.102編寫算法：1）判空操作statusListEmpty_Sq(SqListL)2）求表長操作intListLength_Sq(SqListL)習(xí)題取自:數(shù)據(jù)結(jié)構(gòu)題集C語言版嚴(yán)尉敏等編第三十九頁，共103頁。第二章習(xí)題

實驗一（學(xué)時：4）電話號碼查詢系統(tǒng)功能：1建立電話號碼簿（用順序存儲結(jié)構(gòu)存儲電話號碼簿）2在電話號碼簿中插入一元素（輸入插入位置i,插入元素）3在電話號碼簿中刪除一元素（輸入刪除元素位置i）4顯示電話號碼簿

電話號碼簿

姓名電話號碼蔡穎63214444陳紅63217777劉建平63216666王小林63218888張力63215555...第四十頁，共103頁。2.2線性表的順序存儲和實現(xiàn)

例：將兩個有序線性表歸并成一個有序線性表；

設(shè)線性表A、B分別用La、Lb的兩個順序表存儲，兩順序表中元素按非遞減順序排列，編寫算法：將La、Lb歸并得到順序表Lc,Lc中的元素也按值非遞減順序排列。實現(xiàn)上述功能的算法有很多，我們采用第三種。

1）將Lb并入La;

2）將La并入Lb;

3）將La,Lb并入Lc;(順序表Lc中的空間是新分配的存儲空間）基本思想：同時對La.elem,Lb.elem進(jìn)行掃描，在掃描過程中按兩表當(dāng)前元素的大小，依次將其插入到Lc的表尾；三、利用基本操作實現(xiàn)線性表的其他操作

第四十一頁，共103頁。Lc.elemLc.lengthLc.listsize2.2線性表的順序存儲和實現(xiàn)

順序表的歸并圖示（算法2.7a)0199La.elem358La.length3100La.listsize0199Lb.elem2689Lb.length4100Lb.listsize01992356889100建空表Lc0La,Lb歸并7第四十二頁，共103頁。2.2線性表的順序存儲和實現(xiàn)voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){

//已知順序表La和Lb中的數(shù)據(jù)元素按值非遞減排列。

//歸并La和Lb得到新的順序表Lc,Lc的數(shù)據(jù)元素也按值非遞減排列。

InitList_Sq(Lc)；

i=j=1;k=0;

La_len=Listength_Sq(La);Lb_len=ListLength_Sq(Lb);

while((.i<=La_len)&&(j<=Lb_len)){//La和Lb均非空

GetElem_Sq(La,i,ai);GetElem_Sq(Lb,j,bj);

if(ai<=bj){ListInsert_Sq(Lc,++k,ai);++.i;}

else{ListInsert_Sq(Lc,++k,bj);++j;}

}

while(i<=La_len){

GetElem_Sq(La,.i++,ai);ListInsert_Sq(Lc,++k,ai);

}

while(j<=Lb_len){

GetElem_Sq(Lb,.j++,bj);ListInsert_Sq(Lc,++k,bj);

}

}//MergeList_Sq算法2.7a用線性表的基本操作實現(xiàn)線性表的其它操作第四十三頁，共103頁。Lc.elemLc.lengthLc.listsize2.2線性表的順序存儲和實現(xiàn)

順序表的歸并圖示（算法2.7a)0199La.elem358La.length3100La.listsize0199Lb.elem2689Lb.length4100Lb.listsize01992356889100建空表Lc0La,Lb歸并7第四十四頁，共103頁。2.2線性表的順序存儲和實現(xiàn)voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){

//已知順序表La和Lb的元素按值非遞減排列

//歸并La和Lb得到新的順序表Lc,Lc的元素也按值非遞減排列

pa=La.elem;pb=Lb.elem;

Lc.listsize=Lc.length=La.length+Lb.length;

pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));

if(!Lc.elem)exit(OVERFLOW);//存儲分配失敗

pa_last=La.elem+La.length-1;

pb_last=Lb.elem+Lb.length-1;

while(pa<=pa_last&&pb<=pb_last){//歸并

if(*pa<=*pb)*pc++=*pa++;

else*pc++=*pb++;

}

while(pa<=pa_last)*pc++=*pa++;//插入La的剩余元素

while(pb<=pb_last)*pc++=*pb++;//插入Lb的剩余元素

}//MergeList_Sq算法2.7b兩線性表歸并操作也可不調(diào)用基本操作：而是通過直接對順序表進(jìn)行操作實現(xiàn)。直接對順序表進(jìn)行操作實現(xiàn)順序表的的其它操作第四十五頁，共103頁。Lc.elemLc.lengthLc.listsize2.2線性表的順序存儲和實現(xiàn)順序表的歸并圖示（算法2.7b)

0199La.elem358La.length3100La.listsize0199Lb.elem2689Lb.length4100Lb.listsize

017

2356889077建空表LcLa,Lb歸并第四十六頁，共103頁。2.2線性表的順序存儲和實現(xiàn)

順序表是線性表最簡單的一種存儲結(jié)構(gòu)

小結(jié)順序表的特點：1通過元素的存儲順序反映線性表中數(shù)據(jù)元素之間的邏輯關(guān)系；2可隨機(jī)存取順序表的元素；3順序表的插入刪除操作要通過移動元素實現(xiàn)；第四十七頁，共103頁。2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)

線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲單元存儲線性表的各個數(shù)據(jù)元素。為了表示線性表中元素的先后關(guān)系，每個元素除了需要存儲自身的信息外還需保存直接前趨元素或直接后繼元素的存儲位置。下面介紹線性表的三種鏈?zhǔn)酱娼Y(jié)構(gòu)先從最簡單的開始：

用順序表存儲線性表時，線性表的插入刪除操作要移動大量的元素，平均的來看要移動線性表中一半的元素，因此對于應(yīng)用經(jīng)常要進(jìn)行進(jìn)行插入，刪除操作的線性表，一般不使用順序表存儲，下面我們來看線性表的另一種存儲結(jié)構(gòu):鏈?zhǔn)酱鎯Y(jié)構(gòu)。第四十八頁，共103頁。2.3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)2.3.1線性鏈表

一線性鏈表的概念

二線性鏈表的基本操作算法

三靜態(tài)鏈表四線性鏈表的其它操作2.3.2循環(huán)鏈表

2.3.3雙向鏈表

一雙向鏈表的概念

二雙向鏈表的基本操作算法第四十九頁，共103頁。一線性鏈表的概念

1線性鏈表2.3.1線性鏈表a4a3a1a2

0101010241014101010121014101610181020102210241026用一組任意的存儲單元存儲線性表中的數(shù)據(jù)元素，對每個數(shù)據(jù)元素除了保存自身信息外，還保存了直接后繼元素的存儲位置。

用線性鏈表存儲線性表時，數(shù)據(jù)元素之間的關(guān)系是通過保存直接后繼元素的存儲位置來表示的第五十頁，共103頁。2.3.1線性鏈表線性鏈表圖示ai-1aia2a1ai+1nan

用線性鏈表存儲線性表時，數(shù)據(jù)元素之間的關(guān)系是通過保存直接后繼元素的存儲位置來表示的2線性鏈表圖示一般來說，我們并不需要寫出直接后繼的實際地址，為直觀起見，通常用如下所示的圖表示鏈表，其中，箭頭表示相應(yīng)單元中保存的是它所指向結(jié)點的存儲地址。第五十一頁，共103頁。結(jié)點：數(shù)據(jù)元素及直接后繼的存儲位置（地址）組成一個數(shù)據(jù)元素的存儲結(jié)構(gòu)，稱為一個結(jié)點；結(jié)點的數(shù)據(jù)域：結(jié)點中用于保存數(shù)據(jù)元素的部分;結(jié)點的指針域：結(jié)點中用于保存數(shù)據(jù)元素直接后繼存儲地址的部分;3線性鏈表有關(guān)術(shù)語2.3.1線性鏈表存儲數(shù)據(jù)元素存儲后繼結(jié)點存儲地址結(jié)點數(shù)據(jù)域指針域第五十二頁，共103頁。2.3.1線性鏈表頭指針：用于存放線性鏈表中第一個結(jié)點的存儲地址;

空指針：不指向任何結(jié)點，線性鏈表最后一個結(jié)點的指針通常是指針;

頭結(jié)點：線性鏈表的第一元素結(jié)點前面的一個附加結(jié)點，稱為頭結(jié)點；

帶頭結(jié)點的線性鏈表：第一元素結(jié)點前面增加一個附加結(jié)點的線性鏈表稱為帶頭結(jié)點的線性鏈表；帶頭結(jié)點的線性鏈表圖示

L是頭指針ai-1aia2a1ai+1nan頭結(jié)點空指針L第五十三頁，共103頁。2.3.1線性鏈表ai-1aia2a1ai+1nan線性鏈表的每個結(jié)點中只有一個指針域故也稱為單鏈表第五十四頁，共103頁。2.3.1線性鏈表怎樣在計算機(jī)上實現(xiàn)線性鏈表？？上面用自然語言描述線性表的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)——線性鏈表，怎樣在計算機(jī)上實現(xiàn)線性鏈表？顯然，可以用C語言的結(jié)構(gòu)表示線性鏈表的結(jié)點，可以用指針存放直接后繼的存儲地址。

第五十五頁，共103頁。2.3.1線性鏈表結(jié)點變量圖示typedefstructLNode{

ElemTypedata;

StructLNode*next;

}LNode,*LinkList;·LNode：結(jié)構(gòu)類型名；

LNode類型結(jié)構(gòu)變量有兩個域：

data：用于存放線性表的數(shù)據(jù)元素，

next：用于存放元素直接后繼結(jié)點的地址；

·該類型結(jié)構(gòu)變量用于表示線性鏈表中的一個結(jié)點；

·LinkList：指針類型名；

·LinkList類型指針變量用于存放LNode類型結(jié)構(gòu)變量的地址；

數(shù)據(jù)域指針域

datanext

Lnode類型結(jié)構(gòu)變量LLinkList類型指針變量L4線性鏈表的結(jié)點類型定義及指向結(jié)點的指針類型定義第五十六頁，共103頁。2.3.1線性鏈表設(shè)L是LinkList類型變量，L用來保存線性鏈表中第一個結(jié)點的地址，則L為線性鏈表的頭指針。ai-1aia2a1ai+1nanL以L為頭指針的線性鏈表稱為線性鏈表L二線性鏈表基本操作的算法

假設(shè)線性表用帶頭結(jié)點的線性鏈表L的存儲。下面討論在這種存儲方式下，線性表各種基本操作的算法。當(dāng)線性表用線性鏈表存儲時，對線性表各種基本操作實際上就是對存儲在內(nèi)存中的線性鏈表進(jìn)行操作。第五十七頁，共103頁。2.3.1線性鏈表如何在線性鏈表L上實現(xiàn)線性表的基本操作？如何建空表？如何插入？刪除？？第五十八頁，共103頁。2.3.1線性鏈表初始化操作演示L∧算法：

StatusInitList_L(LinkList&L){

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

If(!L)exit(OVERFLOW);

L->next=null;

ReturnOK;

}//InitList_L

1）初始化操作InitList_L(LinkList&L)

功能：建空線性鏈表L

參數(shù)：L為線性鏈表的頭指針主要步驟：調(diào)用malloc()分配一結(jié)點的空間,并將其地址賦值給L；第五十九頁，共103頁。2.3.1線性鏈表2取元素操作GetElem_L(LinkListL,inti,ElemType&e)

·功能：將線性鏈表中第i個元素賦值給e取元素操作主要步驟：1）查找鏈表的第i個元素結(jié)點；

2)將第i個元素結(jié)點中的數(shù)據(jù)元素賦值給e;ai-1aia2a1ai+1nanLeai取元素元素操作圖示第六十頁，共103頁。2.3.1線性鏈表·取元素操作算法：StatusGetElem_L(LinkListL,intI,ElemType&e){//L為帶頭結(jié)點的單鏈表的頭指針。//當(dāng)?shù)趇個元素存在時，其值賦給e并返回OK，否則返回ERRORp=L->next;j=1;//初始化，p指向第一個結(jié)點，j為計數(shù)器

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

p=p->next;++j;}if(!p||j>i)returnERROR;//第i個元素不存在

e=p->data;//取第i個元素

returnOK;}//GetElem_L

算法2.8第六十一頁，共103頁。3插入操作ListInsert_L(LinkList&L,inti,ElemTypee)

功能：在線性鏈表L的第i個元素結(jié)點之前插入一個新元素結(jié)點；插入操作圖示：2.3.1線性鏈表插入前插入后

ai-1aia2a1ai+1nanLai-1aia2a1ai+1naneL第六十二頁，共103頁。2.3.1線性鏈表插入操作主要步驟：

1）查找鏈表L的第i-1個元素結(jié)點；

2）為新元素建立結(jié)點；

3）修改第i-1個元素結(jié)點的指針和新元素結(jié)點指針完成插入；

插入操作演示用鼠標(biāo)單擊圖中的綠字第六十三頁，共103頁。2.3.1線性鏈表插入操作算法：

StatusListInsert_L(LinkList&L,inti,ElemTypee){//在帶頭結(jié)點的線性鏈表L中第I元素結(jié)點之前插入元素ep=L;j=0while(p&&j<i-1){p=p->next;++j;}//尋找第i-1個元素結(jié)點

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

s=(LinkList)malloc(sizeof(LNode));//分配新結(jié)點

s->data=e;s->next=p->next;p->next=s;//插入新結(jié)點

returnOK;}//LinstInsert_L

算法2.9第六十四頁，共103頁。4刪除操作ListDelete_L(LinkList&L,inti,ElemType&e)

功能：在線性鏈表L中刪除第i個元素，并且用e返回其值刪除操作圖示：

2.3.1線性鏈表刪除前刪除后ai-1aia2a1ai+1nanLai-1aia2a1ai+1nanL第六十五頁，共103頁。2.3.1線性鏈表刪除操作主要步驟：1）查找鏈表的第i-1個元素結(jié)點；

2）修改第i-1個元素結(jié)點指針，刪除第i個元素結(jié)點；

3)將第i個元素結(jié)點中的數(shù)據(jù)元素賦值給e;

4）回收被刪除結(jié)點空間；

刪除操作演示用鼠標(biāo)單擊圖中的綠字第六十六頁，共103頁。2.3.1線性鏈表刪除操作算法：StatusListDelete_L(LinkList&L,inti,ElemType&e){//在帶頭結(jié)點的單鏈線性表L中，刪除第i個元素，并由e返回其值

p=L;j=0;while(p->next&&j<i-1){//尋找第i個結(jié)點，并令p指向其前趨

p=p->next;++j;}if(!p->next)||j>i-1)returnERROR;//表中無第i個結(jié)點(i不合法)

q=p->next;p->next=q->next;//刪除結(jié)點

e=q->data;free(q);//回收（釋放）結(jié)點空間

returnOK;}//LinstDelete_L算法：2.10第六十七頁，共103頁。第二章習(xí)題習(xí)題四P132.1,2.2,2.3,2.14,2.17第六十八頁，共103頁。2.3.1線性鏈表

四、線性鏈表的其他操作例：將兩個有序線性鏈表歸并成一個有序表。設(shè)線性表A、B分別用頭指針為La、Lb的兩個帶頭結(jié)點的線性鏈表存儲，且兩線性鏈表中元素按非遞減順序排列，編寫算法，將La、Lb歸并得到線性鏈表Lc,Lc中的元素也按值非遞減順序排列。（注意：線性鏈表Lc中的結(jié)點利用原La，Lb的結(jié)點）

實現(xiàn)上述功能的算法有很多，我們采用第三種。

1）將Lb并入La;

2）將La并入Lb;

3）將La,Lb并入Lc;基本思想：設(shè)兩個指針pa,pb分別對La,Lb進(jìn)行掃描，在掃描過程中按

pa,pb所指結(jié)點的大小，將其插入到Lc的表尾。第六十九頁，共103頁。算法演示LaLbpapbpcLc2234331^^第七十頁，共103頁。2.3.1線性鏈表線性鏈表歸并操作算法（直接對鏈表進(jìn)行操作）voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){

//已知單鏈線性表La和Lb的元素按值非遞減排列

//歸并La和Lb得到新的單鏈線性表Lc,Lc的元素也按值非遞減排列。

pa=La->next;pb=Lb->next;

Lc=pc=La;//用La的頭結(jié)點作為Lc的頭結(jié)點

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é)點}//MergeList_L

算法2.12直接對線性鏈表進(jìn)行操作實現(xiàn)線性鏈表的其它操作第七十一頁，共103頁。例2頭插法建立單鏈表算法描述:逆位序輸入n個元素的值,建立帶頭結(jié)點的單鏈表算法演示:如輸入二個元素a,b,頭插法建立單鏈表L^ab^pp第七十二頁，共103頁。2.3.1線性鏈表例2建立線性鏈表voidCreateList_L(LinkList&1,intn){//逆序輸入n個元素的值，建立帶表頭結(jié)點的線性鏈表

L=（LinkList）malloc(sizeof(LNode));L->next=NULL;//先建立一個帶頭結(jié)點的單鏈表

for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點

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

p->next=L->next;L->next=p;//插入到表頭/}}//CreateList_L直接對線性鏈表進(jìn)行操作實現(xiàn)線性鏈表的其它操作第七十三頁，共103頁。2.3.1線性鏈表小結(jié)線性鏈表是線性表的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)

線性鏈表的特點1通過保存直接后繼元素的存儲位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系；2插入刪除操作通過修改結(jié)點的指針實現(xiàn)；3不能隨機(jī)存取元素；第七十四頁，共103頁。2.3.1線性鏈表

以上學(xué)習(xí)了線性表的順序存儲結(jié)構(gòu)——順序表，鏈?zhǔn)酱鎯Y(jié)構(gòu)——線性鏈表,以及在這兩種存儲結(jié)構(gòu)下如何實現(xiàn)線性表的基本操作。需要強(qiáng)調(diào)的是：本課程不僅要從概念和方法上了解每一種數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)，基本操作，更重要的是要學(xué)習(xí)如何在計算機(jī)上實現(xiàn)，即如何在計算機(jī)上存儲線性表？如何在計算機(jī)上實現(xiàn)線性表的操作，我們已經(jīng)看到，在不同的存儲結(jié)構(gòu)下，線性表的同一操作的算法是不同的。在順序表存儲結(jié)構(gòu)下，線性表的插入刪除操作，通過移動元素實現(xiàn)，在線性鏈表存儲結(jié)構(gòu)下，線性表的插入刪除操作，通過修改指針實現(xiàn)。我們要很好地理解和掌握以上兩種存儲結(jié)構(gòu)，及兩種存儲結(jié)構(gòu)下操作的特點。它們是應(yīng)用中最常用的兩種存儲結(jié)構(gòu)，也是后續(xù)課程其它存儲結(jié)構(gòu)的基礎(chǔ)。第七十五頁，共103頁。第二章習(xí)題實驗二（學(xué)時：4）電話號碼查詢系統(tǒng)功能：1建立電話號碼簿（用線性鏈表存儲電話號碼簿）2在電話號碼簿中插入一元素（輸入插入位置i，插入元素）3在電話號碼簿中刪除一元素（輸入刪除元素位置i）4顯示電話號碼簿

電話號碼簿姓名電話號碼蔡穎63214444陳紅63217777劉建平63216666王小林63218888張力63215555...第七十六頁，共103頁。2．3線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)

線性鏈表的缺點之一，是無法從指定的某結(jié)點到達(dá)該結(jié)點的前趨結(jié)點，這可能會給某些應(yīng)用帶來一些不便，下面介紹線性表的另外兩種鏈?zhǔn)酱鎯Y(jié)構(gòu)——循環(huán)鏈表和雙向鏈表。第七十七頁，共103頁。

1循環(huán)鏈表的概念循環(huán)鏈表是線性表的另一種鏈?zhǔn)酱鎯Y(jié)構(gòu)，它的特點是將線性鏈表的最后一個結(jié)點的指針指向鏈表的第一個結(jié)點2循環(huán)鏈表圖示2.3.2循環(huán)鏈表(a)非空表（b）空表HHa1an第七十八頁，共103頁。2.3.2循環(huán)鏈表說明·在解決某些實際問題時循環(huán)鏈表可能要比線性鏈表方便些。如將一個鏈表鏈在另一個鏈表的后面；·循環(huán)鏈表與線性鏈表操作的主要差別是算法中循環(huán)結(jié)束的條件；

·對循環(huán)鏈表，有時不給出頭指針，而是給出尾指針，設(shè)立尾指針可以很方便的找到線性表的第一個元素和最后一個元素結(jié)點，可使某些操作易于實現(xiàn)；例如將兩個鏈表首尾相連的操作；Ta1an給出尾指針的循環(huán)鏈表第七十九頁，共103頁。1雙向鏈表的概念2.3.3雙向鏈表(a)結(jié)點圖示數(shù)據(jù)域指針域指針域結(jié)點存儲數(shù)據(jù)元素存儲后繼結(jié)點的地址存儲前趨結(jié)點的地址雙向鏈表中，每個結(jié)點有兩個指針域，一個指向直接后繼元素結(jié)點，另一個指向直接前趨元素結(jié)點。第八十頁，共103頁。2.3.3雙向鏈表2雙向鏈表圖示L（c）非空的雙向循環(huán)鏈表

(b)空的雙向循環(huán)鏈表Lab第八十一頁，共103頁。在雙向鏈表中刪除結(jié)點時指針變化情況在雙向鏈表中插入一個結(jié)點時指針的變化情況ai-1px①②③④aiaiai+1p①②ai-12.3.3雙向鏈表3、雙向鏈表的基本操作算法第八十二頁，共103頁。2.3.3雙向鏈表ai-1px①②③④ai1）插入操作算法

StatusListInsert_DuL(DuLinkList&L,inti,ElemTypee){

//在帶頭結(jié)點的雙鏈循環(huán)線性表L中第i個位置之前插入元素e，

//i的合法值為1≤i≤表長+1。

if(!p=GetElemP_DuL(L,i)))//在L中確定第i個元素的位置指針p

returnERROR;//p=NULL，即第i個元素不存在

//建新結(jié)點、

if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))returnERROR;

s->data=e;

s->prior=p-prior;p->prior->next=s;//完成插入圖示中的①②

s->next=p;p->prior=s;//完成插入圖示中的③④

returnOK;

}//LinstInsert_DuL

算法2.18第八十三頁，共103頁。2.3.3雙向鏈表2）刪除操作算法StatusListDelete_DuL(DuLinkList&L,inti,ElemType&e){

//刪除帶頭結(jié)點的雙鏈循環(huán)線性表L的第i個元素，i的合法值為1≤i≤表長

if(!p=GetElemP_DuL(L,i)))//在L中確定第i個元素的位置指針p

returnERROR;//p=NULL，第i個元素不存在

e=p->data;

p->prior->next=p->next;//完成刪除圖示中的①

p->next->prior=p->prior;//完成刪除圖示中的②

free(p);returnOK;

}//LinstDelete_DuL

算法2.19aiai+1p①②ai-1第八十四頁，共103頁。2.4一元多項式的表示及相加線性表是最簡單常用的數(shù)據(jù)結(jié)構(gòu)。本節(jié)介紹一個線性表的典型應(yīng)用:一元多項式的運(yùn)算。第八十五頁，共103頁。

2.4一元多項式的表示及相加它由個系數(shù)唯一確定。多項式基本運(yùn)算有加法減法乘法，為了用計算機(jī)實現(xiàn)多項式運(yùn)算，可用一個由系數(shù)構(gòu)成的線性表來表示一元多項式：

P=(p0,p1,p2,…pn)

Q=(q0,q1,q2,…qm)不失一般性，設(shè)m<n，則兩個多項式相加的結(jié)果可用線性表R表示： R=(p0+q0,p1+q1,…,pm+qm,pm+1,…,pn)

顯然可以對P，Q，R采用順序結(jié)構(gòu)存儲，這樣一元多項式相加運(yùn)算很容易實現(xiàn)。Pn(x)=p0+p1x+p2x2+…+pnxnQm(x)=q0+q1x+q2x2+…+qmxm一、一元多項式的表示多項式的操作是表處理的典型用例。數(shù)學(xué)上,一元多項式可按升冪寫成：第八十六頁，共103頁。

2.4一元多項式的表示及相加以下用非0項（系數(shù)，指數(shù)）構(gòu)成的線性表表示一元多項式。用這種方式表示一元多項式時，一元多項式運(yùn)算經(jīng)常要對線性表進(jìn)行插入刪除操作，所以采用線性鏈表存儲結(jié)構(gòu)它們。應(yīng)用中一元多項式往往冪次很高，且有大量項的系數(shù)為零。例：S(x)=1+3x10000+2x20000

如果用系數(shù)構(gòu)成的線性表表示該多項式，就要用一長度為20001的線性表表示，可表中只有三個非零項，這顯然很浪費(fèi)內(nèi)存空間。可采用另一種方式，即用非0項（系數(shù)，指數(shù)）構(gòu)成的線性表表示一元多項式，S=((1,0),(3,10000),(2,20000))第八十七頁，共103頁。2.4一元多項式的表示及相加鏈表中結(jié)點指針的類型定義typedefstructLNode{

ElemTypedata;

StructLNode*next;

}*Link,*Position;1）線性鏈表的類型定義ai-1aia2a1ai+1nanL鏈表中結(jié)點指針二一元多項式的鏈?zhǔn)酱鎯Y(jié)構(gòu)1重新定義線性鏈表

一元多項式運(yùn)算，將利用線性鏈表的基本操作實現(xiàn)。為了實現(xiàn)多項式的加減乘等運(yùn)算需要重新定義線性鏈表和基本操作。第八十八頁，共103頁。2.4一元多項式的表示及相加鏈表的類型定義（鏈表表頭結(jié)點的類型定義）

typedefstruct{

Linkhead,tail;

intlen;

}LinkList;表頭結(jié)點是一結(jié)構(gòu)a1anLheadtaillennL是Linklist類型的結(jié)構(gòu)變量第八十九頁，共103頁。2.4一元多項式的表示及相加a1anLheadtaillenn2）新定義線性鏈表圖示表頭結(jié)點頭結(jié)點L是Linklist類型的結(jié)構(gòu)變量第九十頁，共103頁。2.4一元多項式的表示及相加3）在原線性鏈表的基礎(chǔ)上，增加如下的基本操作：（1）取表頭操作PositionGetHead(LinkListL)

功能：L為線性鏈表的表頭結(jié)點，該操作返回鏈表的頭結(jié)點指針；（2）求后繼操作Position

Nextpos(LinkListL,Linkp)

功能：p指向線性鏈表L的某個結(jié)點，返回p所指結(jié)點的后繼的指針；（3）求前趨操作PositionPrior(LinkListL,Linkp)

功能：p指向線性鏈表L的某個結(jié)點，返回p所指結(jié)點的前趨的指針；（4）取當(dāng)前結(jié)點值的操作ElemTypeGetCurElem(Linkp)

功能：p指向線性鏈表L的某一結(jié)點，返回p的所指結(jié)點的值；headtaillennL是表頭結(jié)點頭結(jié)點a1anL第九十一頁，共103頁。2.4一元多項式的表示及相加a1anLhs插入首結(jié)點StatusInsFirst(Linkh,Links)圖示（5）為當(dāng)前結(jié)點賦值StatusSetCurElem(Link&p,ElemTypee)功能：p指向線性鏈表L的某個結(jié)點,用e更新p所指結(jié)點中數(shù)據(jù)元素的值（6）插入首結(jié)點StatusInsFirst(Linkh,Links)

功能：h指向線性鏈表L的頭結(jié)點,在線性鏈表的第一元素結(jié)點之前插入s所指結(jié)點；第九十二頁，共103頁。2.4一元多項式的表示及相加（7）刪除首結(jié)點StatusDelFirst(Linkh,Linkq)

功能：

h指向線性鏈表L的頭結(jié)點,刪除線性鏈表的第一元素結(jié)點，并用q返回其指針；

（8）連接鏈表StatusAppend(LinkList&L,Links)

功能：將s所指的鏈表鏈接在線性鏈表L的尾部La1ana2

刪除首結(jié)點StatusDelFirst(Linkh,Linkq)圖示hq第九十三頁，共103頁。2.4一元多項式的表示及相加1）元素的類型定義typedefstruct{

floatcoef;//存儲項系數(shù)

intexpn;//存儲項指數(shù)

}ElemType;2）一元多項式鏈表的類型定義typedefLinkListpolynomail;//用帶表頭結(jié)點的線性鏈表表示//一元多項式，為類型重命名//是為增加算法的可讀性