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

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

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

基本內(nèi)容

1線(xiàn)性表的概念；

2線(xiàn)性表兩類(lèi)存儲(chǔ)結(jié)構(gòu)和它們的類(lèi)型定義；

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

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

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

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

5能夠從時(shí)間復(fù)雜度的角度，比較線(xiàn)性表兩類(lèi)存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及適用場(chǎng)合；

第二章線(xiàn)性表

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

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

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

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

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

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

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

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

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

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

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

例如，我們要在設(shè)計(jì)一個(gè)電話(huà)號(hào)碼詢(xún)系統(tǒng)，顯然這個(gè)系統(tǒng)至少要具備下列功能：

·

查詢(xún)某人的電話(huà)號(hào)碼；

·在電話(huà)號(hào)碼薄中，插入一新用戶(hù)姓名及電話(huà)號(hào)碼；

·在電話(huà)號(hào)碼薄中，刪除已撤銷(xiāo)的用戶(hù)姓名及電話(huà)號(hào)碼；

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

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

2.2

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

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

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

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

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

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

以上用自然語(yǔ)言描述了線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)，怎樣將這種存儲(chǔ)方式在計(jì)算機(jī)上實(shí)現(xiàn)？為此，我們用C語(yǔ)言對(duì)這種存儲(chǔ)方式進(jìn)行描述，我們知道C語(yǔ)言一維數(shù)組的機(jī)內(nèi)表示也是順序結(jié)構(gòu)，因此，可借用C語(yǔ)言的一維數(shù)組實(shí)現(xiàn)線(xiàn)性表的順序存儲(chǔ)。第十一頁(yè)，共103頁(yè)。2.2線(xiàn)性表的順序存儲(chǔ)和實(shí)現(xiàn)順序表的類(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;SqList：類(lèi)型名，SqList類(lèi)型的變量是結(jié)構(gòu)變量，它的三個(gè)域分別是：

*elem：

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

length：

存放線(xiàn)性表的表長(zhǎng)；

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

二、順序表的基本操作算法回顧本書(shū)算法中常用到的兩個(gè)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)型變量所占空間的大小(一般為32bit)分配m*sizeof(float)個(gè)的存儲(chǔ)單元,并將其基址賦值給指針變量p;第十四頁(yè)，共103頁(yè)。

01299p

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

01299p

調(diào)用free(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線(xiàn)性表的順序存儲(chǔ)和實(shí)現(xiàn)第十六頁(yè)，共103頁(yè)。如何在順序表上實(shí)現(xiàn)線(xiàn)性表的基本操作？如何建空表？如何求表長(zhǎng)？如何插入？刪除？？

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

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

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

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

再演示一次2.2線(xiàn)性表的順序存儲(chǔ)和實(shí)現(xiàn)第十九頁(yè)，共103頁(yè)。初始化操作算法：StatusInitList_Sq(SqList&L){//構(gòu)造一個(gè)空的順序表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_Sq

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

銷(xiāo)毀操作圖示2銷(xiāo)毀操作

DetroyList(SqList&L)

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

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

銷(xiāo)毀順序表L.lengthL.listsizeL.elem01LIST_INIT_SIZE-1a1a2ai-1aiai+1an

nLIST_INIT_SIZE00=null

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

StatusDetroyList_Sq(SqList&L){

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

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

L.elem=null;

L.length=0;

L.Listsize=0;

returnOK;

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

置空操作圖示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)性表的順序存儲(chǔ)和實(shí)現(xiàn)第二十四頁(yè)，共103頁(yè)。2.2線(xiàn)性表的順序存儲(chǔ)和實(shí)現(xiàn)L.lengthL.listsizeL.elem0199a1a2ai-1aiai+1an

n

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

GetElem_Sq(SqListL,inti,ElemType&e)

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

算法：

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

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

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

returnOK;

}//GetElem_Sq

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

取元素操作

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

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

ListInsert_Sq(&L,i,e)

參數(shù)：L:順序表，i插入位置，e被插入元素;因?yàn)椴迦氩僮鲗?duì)順序表進(jìn)行修改,所以用了引用參數(shù)&L;

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

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

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

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

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

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

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

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

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

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

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

//插入位置及之后的元素后移一個(gè)位置

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

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

returnOK;

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

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

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

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

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

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

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

//插入位置及之后的元素后移一個(gè)位置

*q=e;//插入e

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

returnOK;

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

插入位置移動(dòng)元素個(gè)數(shù)

1

n

2

n-1

in-i+1

n1

n+10

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

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

·在順序表中插入一個(gè)元素，平均要移動(dòng)表的一半元素。

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

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

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

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

刪除操作主要步驟：

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

2）將ai賦值給e;

3）將順序表中ai后面的元素依次向前移動(dòng)一個(gè)位置;

4）表長(zhǎng)-12.2線(xiàn)性表的順序存儲(chǔ)和實(shí)現(xiàn)

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

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

//在順序表L中刪除第i個(gè)元素，并用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;//表長(zhǎng)減1

returnOK;

}//ListDelete_Sq

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

//在順序線(xiàn)性表L中刪除第.i個(gè)元素，并用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;//表長(zhǎng)減1

returnOK;

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

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

電話(huà)號(hào)碼簿

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

例：將兩個(gè)有序線(xiàn)性表歸并成一個(gè)有序線(xiàn)性表；

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

1）將Lb并入La;

2）將La并入Lb;

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

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

順序表的歸并圖示（算法2.7a)0199La.elem358La.length3100La.listsize0199Lb.elem2689Lb.length4100Lb.listsize01992356889100建空表Lc0La,Lb歸并7第四十二頁(yè)，共103頁(yè)。2.2線(xiàn)性表的順序存儲(chǔ)和實(shí)現(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)性表的基本操作實(shí)現(xiàn)線(xiàn)性表的其它操作第四十三頁(yè)，共103頁(yè)。Lc.elemLc.lengthLc.listsize2.2線(xiàn)性表的順序存儲(chǔ)和實(shí)現(xiàn)

順序表的歸并圖示（算法2.7a)0199La.elem358La.length3100La.listsize0199Lb.elem2689Lb.length4100Lb.listsize01992356889100建空表Lc0La,Lb歸并7第四十四頁(yè)，共103頁(yè)。2.2線(xiàn)性表的順序存儲(chǔ)和實(shí)現(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);//存儲(chǔ)分配失敗

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兩線(xiàn)性表歸并操作也可不調(diào)用基本操作：而是通過(guò)直接對(duì)順序表進(jìn)行操作實(shí)現(xiàn)。直接對(duì)順序表進(jìn)行操作實(shí)現(xiàn)順序表的的其它操作第四十五頁(yè)，共103頁(yè)。Lc.elemLc.lengthLc.listsize2.2線(xiàn)性表的順序存儲(chǔ)和實(shí)現(xiàn)順序表的歸并圖示（算法2.7b)

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

017

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

順序表是線(xiàn)性表最簡(jiǎn)單的一種存儲(chǔ)結(jié)構(gòu)

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

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

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

一線(xiàn)性鏈表的概念

二線(xiàn)性鏈表的基本操作算法

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

2.3.3雙向鏈表

一雙向鏈表的概念

二雙向鏈表的基本操作算法第四十九頁(yè)，共103頁(yè)。一線(xiàn)性鏈表的概念

1線(xiàn)性鏈表2.3.1線(xiàn)性鏈表a4a3a1a2

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

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

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

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

頭結(jié)點(diǎn)：線(xiàn)性鏈表的第一元素結(jié)點(diǎn)前面的一個(gè)附加結(jié)點(diǎn)，稱(chēng)為頭結(jié)點(diǎn)；

帶頭結(jié)點(diǎn)的線(xiàn)性鏈表：第一元素結(jié)點(diǎn)前面增加一個(gè)附加結(jié)點(diǎn)的線(xiàn)性鏈表稱(chēng)為帶頭結(jié)點(diǎn)的線(xiàn)性鏈表；帶頭結(jié)點(diǎn)的線(xiàn)性鏈表圖示

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

第五十五頁(yè)，共103頁(yè)。2.3.1線(xiàn)性鏈表結(jié)點(diǎn)變量圖示typedefstructLNode{

ElemTypedata;

StructLNode*next;

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

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

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

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

·該類(lèi)型結(jié)構(gòu)變量用于表示線(xiàn)性鏈表中的一個(gè)結(jié)點(diǎn)；

·LinkList：指針類(lèi)型名；

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

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

datanext

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

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

功能：建空線(xiàn)性鏈表L

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

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

2)將第i個(gè)元素結(jié)點(diǎn)中的數(shù)據(jù)元素賦值給e;ai-1aia2a1ai+1nanLeai取元素元素操作圖示第六十頁(yè)，共103頁(yè)。2.3.1線(xiàn)性鏈表·取元素操作算法：StatusGetElem_L(LinkListL,intI,ElemType&e){//L為帶頭結(jié)點(diǎn)的單鏈表的頭指針。//當(dāng)?shù)趇個(gè)元素存在時(shí)，其值賦給e并返回OK，否則返回ERRORp=L->next;j=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

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

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

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

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

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

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

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

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

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

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

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

returnOK;}//LinstInsert_L

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1）將Lb并入La;

2）將La并入Lb;

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

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

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

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

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

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

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)

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

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

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

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

電話(huà)號(hào)碼簿姓名電話(huà)號(hào)碼蔡穎63214444陳紅63217777劉建平63216666王小林63218888張力63215555...第七十六頁(yè)，共103頁(yè)。2．3線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)

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

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

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

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

StatusListInsert_DuL(DuLinkList&L,inti,ElemTypee){

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

//i的合法值為1≤i≤表長(zhǎng)+1。

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

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

//建新結(jié)點(diǎn)、

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第八十三頁(yè)，共103頁(yè)。2.3.3雙向鏈表2）刪除操作算法StatusListDelete_DuL(DuLinkList&L,inti,ElemType&e){

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

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

returnERROR;//p=NULL，第i個(gè)元素不存在

e=p->data;

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

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

free(p);returnOK;

}//LinstDelete_DuL

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

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

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

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

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

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

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

ElemTypedata;

StructLNode*next;

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

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

typedefstruct{

Linkhead,tail;

intlen;

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

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

Nextpos(LinkListL,Linkp)

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

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

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

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

功能：

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

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

功能：將s所指的鏈表鏈接在線(xiàn)性鏈表L的尾部La1ana2

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

floatcoef;//存儲(chǔ)項(xiàng)系數(shù)

intexpn;//存儲(chǔ)項(xiàng)指數(shù)

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