(C語(yǔ)言詳細(xì)版)第二章-線性表課件

重點(diǎn)：順序表和鏈表上各種基本算法的實(shí)現(xiàn)及相關(guān)的時(shí)間性能分析難點(diǎn)：線性表應(yīng)用的算法設(shè)計(jì)第二章線性表第二章線性表從第2章至第4章將討論線性結(jié)構(gòu)。線性結(jié)構(gòu)的特點(diǎn)是：在數(shù)據(jù)元素的非空有限集中，(1)存在唯一的一個(gè)被稱做“第一個(gè)”的數(shù)據(jù)元素；(2)存在唯一的一個(gè)被稱做“最后一個(gè)”的數(shù)據(jù)元素；(3)除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)；(4)除最后一個(gè)之外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼。2023/7/10卓月明2第二章線性表2.1線性表的類型定義2.2線性表的順序表示和實(shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.1線性鏈表2.3.2循環(huán)鏈表2.3.3雙向鏈表2.4一元多項(xiàng)式的表示及相加(基于線性表的應(yīng)用)作業(yè)2023/7/10卓月明32.1線性表的類型定義定義n(≥0)個(gè)數(shù)據(jù)元素的有限序列,記作(a1,…ai-1,ai,ai+1,…,an)其中，ai

是表中數(shù)據(jù)元素，n

是表長(zhǎng)度(n=0時(shí)稱為空表)，i為ai在線性表中的位序。由此，我們也可以將線性表看成是由(i,ai

)構(gòu)成的集合。線性表中的數(shù)據(jù)元素可以是各種各樣的，只要是屬于同一個(gè)集合即可。

例如，26個(gè)小寫英文字母是一個(gè)線性表

(a,b,…,z)

同一花色的13張撲克牌

(2,3,4,5,6,7,8,9,10,J,Q,K,A)

可以構(gòu)成一個(gè)線性表。2023/7/10卓月明42.1線性表的類型定義在稍復(fù)雜的線性表中，一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)(Item)組成。在這種情況下，常把數(shù)據(jù)元素稱為記錄(Record)，含有大量記錄的線性表又稱文件(File)。

例如，一個(gè)學(xué)校的學(xué)生健康情況登記表如圖所示，表中每個(gè)學(xué)生的情況為一個(gè)記錄，它由姓名、學(xué)號(hào)、性別、年齡、班級(jí)和健康狀況等六個(gè)數(shù)據(jù)項(xiàng)組成。約定同一線性表中的元素必定具有相同的特性，即屬同一數(shù)據(jù)對(duì)象，相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系。2023/7/10卓月明52.1線性表的類型定義邏輯特征n>0時(shí)有且僅有一個(gè)“第一個(gè)”數(shù)據(jù)元素有且僅有一個(gè)“最后一個(gè)”數(shù)據(jù)元素除第一個(gè)數(shù)據(jù)元素外，其它元素有且僅有一個(gè)直接前驅(qū)除最后一個(gè)數(shù)據(jù)元素外，其它元素有且僅有一個(gè)直接后繼序偶<ai,ai+1>表示ai是ai+1的直接前驅(qū)，反之，ai+1是ai的直接后繼。

2023/7/10卓月明62.2線性表的順序表示和實(shí)現(xiàn)定義用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的數(shù)據(jù)元素特點(diǎn)邏輯上相鄰，物理上也相鄰。隨機(jī)存取688970674078

邏輯序號(hào)(位序)123456C數(shù)組下標(biāo)012345陳述問題時(shí)用2023/7/10卓月明92.2線性表的順序表示和實(shí)現(xiàn)

--順序表的存儲(chǔ)LOC(ai+1)=LOC(ai)+lLOC(a

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

a1

a2

…a

i………an12…i………n

aa+l…a+(i-1)*l………a+(n-1)*l

idle2023/7/10卓月明102.2線性表的順序表示和實(shí)現(xiàn)

--類型定義與基本操作實(shí)現(xiàn)順序表定義方案一#defineLIST_SIZE100typedefstruct{ElemTypeelem[LIST_SIZE]; /*存儲(chǔ)空間*/intlength; /*當(dāng)前長(zhǎng)度*/}SqList_static;1)LIST_SIZE過小，則會(huì)導(dǎo)致順序表上溢；2)LIST_SIZE過大，則會(huì)導(dǎo)致空間的利用率不高。2023/7/10卓月明112.2線性表的順序表示和實(shí)現(xiàn)

--類型定義與基本操作實(shí)現(xiàn)方案二#defineLIST_INIT_SIZE100 /*存儲(chǔ)空間的初始分配量 */#defineLISTINCREMENT10 /*存儲(chǔ)空間的分配增量*/typedefstruct{ElemType*elem; /*存儲(chǔ)空間的基址*/intlength;/*當(dāng)前長(zhǎng)度*/intlistsize;/*當(dāng)前分配的存儲(chǔ)容量*/}SqList;這種方法可以解決方案一中的“上溢”問題和“空間利用率不高”問題。但是這一方案是有時(shí)間和空間代價(jià)的：當(dāng)因插入元素而空間不足時(shí)，需要重新分配比原先的順序表多存儲(chǔ)LISTINCREMENT個(gè)數(shù)據(jù)元素的連續(xù)空間，并且需要將原空間的數(shù)據(jù)元素復(fù)制到新分配的空間中。

2023/7/10卓月明122.2線性表的順序表示和實(shí)現(xiàn)

--類型定義與基本操作實(shí)現(xiàn)注意1)必須記載當(dāng)前線性表的實(shí)際分配的空間大小；2)當(dāng)線性表不再使用時(shí)，應(yīng)釋放其所占的空間；3)這種方法要求實(shí)現(xiàn)級(jí)的語(yǔ)言能提供空間的動(dòng)態(tài)分配與釋放管理。void*malloc(unsignedintsize)生成一大小為size的結(jié)點(diǎn)空間，將該空間的起始地址賦給p；free(void*p)回收p所指向的結(jié)點(diǎn)空間;void*realloc(void*p,unsignedintsize)

將p所指向的已分配內(nèi)存區(qū)的大小改為size，size可以比原分配的空間大或小。若需使用上面三個(gè)函數(shù)，需＃include<stdlib.h>2023/7/10卓月明132.2線性表的順序表示和實(shí)現(xiàn)

--類型定義與基本操作實(shí)現(xiàn)基本操作的實(shí)現(xiàn)初始化

StatusInitList_Sq(SqList&L){//構(gòu)造一個(gè)空的線性表LL.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(L.elem==NULL) exit(OVERFLOW); //存儲(chǔ)分配失敗L.length=0; //空表長(zhǎng)度為0L.listsize=LIST_INIT_SIZE; //初始存儲(chǔ)容量returnOK;}//InitList_Sq2023/7/10卓月明142.2線性表的順序表示和實(shí)現(xiàn)

--類型定義與基本操作實(shí)現(xiàn)求表長(zhǎng)L.length取第i個(gè)元素L.elem[i-1](0<i<L.length+1)按值查找

intLocateElem_Sq(SqListL,ElemTypee,

Status(*compare)(ElemType,ElemType)){ i=1;

p=L.elem;

while(i<=L.length&&!(*compare)(*p++,e))++i;

if(i<=L.length)returni;

elsereturn0;

for(i=0;i<L.length&&!(*compare)(L.elem[i],e);i++);

if(i<L.length)returni+1;

elsereturn0;}2023/7/10卓月明152.2–插入操作的實(shí)現(xiàn)基本操作的實(shí)現(xiàn)插入操作

演示

15234616571064

1234567848插入e01234567i15234616571064

123456789482023/7/10卓月明162.2–插入操作的實(shí)現(xiàn)插入操作1、算法設(shè)計(jì)參數(shù)：順序表&L、插入位置i、插入元素e插入分析：第i個(gè)位置放e，則原來第i~L.length個(gè)數(shù)據(jù)元素必須先后移，以騰出第i個(gè)位置;注意后移的順序?yàn)椋簭淖詈笠粋€(gè)元素開始，逐個(gè)往后移for(j=L.length;j>=i;j--) L.elem[j]=L.elem[j-1];//后移L.elem[i-1]=e;//第i個(gè)元素存放在L.elem[i-1]中，數(shù)組下標(biāo)的起始為0L.length=L.length+1;合法的位置：i:1..L.length+1上溢及處理：上溢發(fā)生的條件：L.length≥L.listsize此時(shí)要先申請(qǐng)一個(gè)有一定增量的空間，申請(qǐng)成功則原空間的元素復(fù)制到新空間，修改L.listsize，再進(jìn)行插入工作；否則報(bào)錯(cuò)退出。2023/7/10卓月明172.2–插入操作的實(shí)現(xiàn)2、算法StatusListInsert_Sq(SqList&L,inti,ElemTypee){//位置合法性的判斷if(i<1||i>L.length+1) returnERROR;//上溢時(shí)增加空間的分配if(L.length>=L.listsize){newbase=(ElemType*)realloc(L.elem,

(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(newbase==NULL)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}//插入元素for(j=L.length;j>=i;j--) L.elem[j]=L.elem[j-1];L.elem[i-1]=e;L.length++;returnOK;}2023/7/10卓月明182.2–插入操作的實(shí)現(xiàn)算法分析——時(shí)間頻次最高的操作：移動(dòng)元素。另外，上溢時(shí)的空間的再分配與復(fù)制(realloc操作)的時(shí)間復(fù)雜度與realloc的算法以及當(dāng)前的表長(zhǎng)相關(guān)，至少為O(n)；但它僅在插入元素會(huì)引起上溢時(shí)才執(zhí)行。若線性表的長(zhǎng)度為n，則：最好情況：插入位置i為n+1，此時(shí)無(wú)須移動(dòng)元素，時(shí)間復(fù)雜度為O(1);最壞情況：插入位置i為1，此時(shí)須移動(dòng)n個(gè)元素，時(shí)間復(fù)雜度為O(n);2023/7/10卓月明192.2–插入操作的實(shí)現(xiàn)平均情況：假設(shè)pi為在第i個(gè)元素之前插入一個(gè)元素的概率，則：

插入時(shí)移動(dòng)次數(shù)的期望值：

等概率時(shí)，即，，

∴T(n)=O(n)2023/7/10卓月明202.2–刪除操作的實(shí)現(xiàn)基本操作的實(shí)現(xiàn)刪除操作

演示

StatusListDelete_Sq(SqList&L,inti,ElemType&e)15234616571064

1234567816刪除e01234567i152346571064

12345672023/7/10卓月明212.2–算法設(shè)計(jì)基于順序表的算法設(shè)計(jì)

例2-1和例2-2基本操作在順序表中的實(shí)現(xiàn)ListLength(La)

La.length

GetElem(Lb,i,e)

e=Lb.elem[i-1];LocateElem(La,e,equal)

ListInsert(La,++La_len,e)

La.elem[La_len++]=e;基于順序表實(shí)現(xiàn)例2-1和例2-2基本操作的簡(jiǎn)單替換，針對(duì)例2-2得到P26算法2.72023/7/10卓月明22單鏈表靜態(tài)鏈表循環(huán)鏈表雙向鏈表其他

2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2023/7/10卓月明23單鏈表

順序映像的弱點(diǎn)空間利用率不高（預(yù)先按最大空間分配）

表的容量不可擴(kuò)充（針對(duì)順序表的方案一）

即使表的容量可以擴(kuò)充（針對(duì)順序表的方案二），由于其空間再分配和復(fù)制的開銷，也不允許它頻繁地使用插入或刪除時(shí)需移動(dòng)大量元素鏈表定義特點(diǎn)邏輯上相鄰的元素，物理上未必相鄰；非隨機(jī)存取2.3.1線性鏈表–單鏈表2023/7/10卓月明24鏈表定義結(jié)點(diǎn)-數(shù)據(jù)元素的存儲(chǔ)映像，包括數(shù)據(jù)域和指針域（其信息稱為指針或鏈）頭指針-鏈表存取的開始；空(NULL)-最后一個(gè)結(jié)點(diǎn)的指針

2.3.1線性鏈表–單鏈表頭指針2023/7/10卓月明252.3.1線性鏈表–單鏈表鏈表定義每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，則稱為線性鏈表或單鏈表；相對(duì)地，稱含兩個(gè)或兩個(gè)以上指針域的結(jié)點(diǎn)構(gòu)成的鏈表稱為多重鏈表。用線性鏈表表示線性表時(shí)，數(shù)據(jù)元素之間的邏輯關(guān)系是由結(jié)點(diǎn)中的指針指示的。

換句話說，指針為數(shù)據(jù)元素之間的邏輯關(guān)系的映象，則邏輯上相鄰的兩個(gè)數(shù)據(jù)元素其存儲(chǔ)的物理位置不要求緊鄰，這種存儲(chǔ)結(jié)構(gòu)為非順序映象或鏈?zhǔn)接诚蟆?023/7/10卓月明26鏈表定義

typedefstructLNode{

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

structLNode*next; //后向指針域

}LNode,*LinkList;2.3.1線性鏈表–單鏈表2023/7/10卓月明272.3.1線性鏈表–單鏈表鏈表定義1、無(wú)頭結(jié)點(diǎn)的單鏈表頭指針為L(zhǎng)，則空表時(shí)，L==NULL由于第一個(gè)結(jié)點(diǎn)無(wú)前驅(qū)結(jié)點(diǎn)，所以只能通過某指針變量來指向，如L；其余結(jié)點(diǎn)均有前驅(qū)結(jié)點(diǎn)，故可通過其直接前驅(qū)結(jié)點(diǎn)的next域來指向，即……->next；表示方法的不同，會(huì)造成對(duì)結(jié)點(diǎn)的操作處理的不同。2、有頭結(jié)點(diǎn)的單鏈表空表時(shí)，L指向一結(jié)點(diǎn)(稱為頭結(jié)點(diǎn))，該結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)信息，也可存儲(chǔ)如表長(zhǎng)等的附加信息，結(jié)點(diǎn)的指針域存放NULL，即L->next==NULL。 第一個(gè)結(jié)點(diǎn)和其余結(jié)點(diǎn)均可統(tǒng)一表示為其直接前驅(qū)結(jié)點(diǎn)的next域所指向的結(jié)點(diǎn)，即……->next。a1a2Lan^a1an^L2023/7/10卓月明282.3.1線性鏈表–單鏈表基本操作的實(shí)現(xiàn)

演示取第i個(gè)元素

GetElem_L(LinkListL,inti,ElemType&e)

插入操作

ListInsert_L(LinkList&L,inti,ElemTypee)2023/7/10卓月明29基本操作的實(shí)現(xiàn)

演示刪除操作

ListDelete_L(LinkList&L,inti,ElemType&e)創(chuàng)建單鏈表

CreateList_L(LinkList&L)頭插法尾插法2.3.1線性鏈表–單鏈表2023/7/10卓月明30基于單鏈表的算法設(shè)計(jì)不能簡(jiǎn)單地用基本操作的實(shí)現(xiàn)來替換要結(jié)合問題的處理特征和存儲(chǔ)結(jié)構(gòu)的特征進(jìn)行適當(dāng)?shù)恼希?.3.1線性鏈表–單鏈表2023/7/10卓月明31靜態(tài)鏈表

問題：若語(yǔ)言不支持指針類型，能有鏈?zhǔn)酱鎯?chǔ)嗎？

可以借用一維數(shù)組來表示鏈表-靜態(tài)鏈表

數(shù)組元素(數(shù)據(jù)元素的值、指示器)-結(jié)點(diǎn)類型定義

#define MAXSIZE 1000

typedefstruct{

ElemType data;

int cur; //替代動(dòng)態(tài)鏈表結(jié)點(diǎn)中的指針域

}component,SLinkList[MAXSIZE];2.3.1線性鏈表–靜態(tài)鏈表2023/7/10卓月明32循環(huán)鏈表

問題1

如何從一個(gè)結(jié)點(diǎn)出發(fā)，訪問到鏈表中的全部結(jié)點(diǎn)？

——循環(huán)鏈表問題2

如何在O(1)時(shí)間內(nèi)由鏈表指針訪問到第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)？

——頭指針表示/