西安電子科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課件2 Linear lists

第二章線性表本章內(nèi)容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)式的表示及相加12.1線性表的類型定義定義：一個(gè)線性表是有n個(gè)數(shù)據(jù)元素的有限序列：(a1，a2，…，ai，…，an)。線性表中元素之間的關(guān)系是線性關(guān)系：存在惟一的第一個(gè)元素；存在惟一的最后一個(gè)元素；除第一個(gè)元素之外，每個(gè)元素均只有一個(gè)直接前驅(qū)；除最后一個(gè)元素之外，每個(gè)元素均只有一個(gè)直接后繼。線性表中的元素類型：原子類型：如整數(shù)、字符等。結(jié)構(gòu)類型：如表示一個(gè)學(xué)生信息的數(shù)據(jù)元素，包含學(xué)號(hào)、姓名、性別等數(shù)據(jù)項(xiàng)。一個(gè)線性表中元素的個(gè)數(shù)n(n≥0)定義為線性表的長(zhǎng)度，n=0時(shí)稱為空表。非空線性表中的每個(gè)元素都有一個(gè)確定的位序。22.1線性表的類型定義線性表的抽象數(shù)據(jù)類型定義：ADTList{

數(shù)據(jù)對(duì)象：D={ai

|ai

ElemSet,i=1,2,…n,n0}

數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1,aiD,i=1,2,…n}

基本運(yùn)算：InitList(&L);DestroyList(&L);Length(L);GetElem(L,i,&e);LocateElem(L,e,compare());InsertElem(&L,i,e);DeleteElem(&L,i,&e);……}ADTList32.1線性表的類型定義抽象運(yùn)算（算法2.1）

例2-1利用兩個(gè)線性表LA和LB分別表示集合A和B，求一個(gè)新的集合A=A∪B。

算法思路：集合中的元素間是松散的關(guān)系，只需將在線性表LB中而不在LA中的數(shù)據(jù)元素追加到LA的尾部即可。voidunion(List&La，ListLb){

La_len=Length(La);Lb_len=Length(Lb);

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

GetElem(Lb,i,e);if(!LocatElem(La,e,equal))

InsertElem(La,++La_len,e);}}//union4特點(diǎn)：存儲(chǔ)單元地址連續(xù)（需要一段連續(xù)空間）邏輯上相鄰的數(shù)據(jù)元素其物理位置也相鄰存儲(chǔ)密度大（100%）隨機(jī)存取元素序號(hào)與存儲(chǔ)位置存在如下關(guān)系：2.2線性表的順序表示和實(shí)現(xiàn)順序表---線性表的順序存儲(chǔ) 內(nèi)涵：

線性表的順序存儲(chǔ)指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。這稱為順序表。a1a2...aian...}d

Loc(ai)=Loc(a1)+(i-1)*d(1≤i≤n)52.2線性表的順序表示和實(shí)現(xiàn)順序表存儲(chǔ)的Ｃ語(yǔ)言實(shí)現(xiàn) 由于C語(yǔ)言中的一維數(shù)組也是采用順序存儲(chǔ)表示，故可以用數(shù)組類型來(lái)描述順序表。下面我們用結(jié)構(gòu)類型來(lái)定義順序表類型。 //----------動(dòng)態(tài)分配------------#defineLIST_INIT_SIZE100 //空間初始分配量#defineLISTINCREMENT10 //空間分配增量typedefstruct{

ElemType*elem; //存儲(chǔ)空間基址

intlength; //當(dāng)前長(zhǎng)度

intlistsize; //當(dāng)前分配的存儲(chǔ)容量}SqList；62.2線性表的順序表示和實(shí)現(xiàn)創(chuàng)建一個(gè)空的順序表（算法2.3） StatusInitList_sq(SqList&L){

L.elem=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType)); if(!L.elem)exit(OVERFLOW);

L.length=0;

L.listsize=INIT_SIZE; returnOK;}//InitList_sq72.2線性表的順序表示和實(shí)現(xiàn)線性表上的基本運(yùn)算插入運(yùn)算 含義： 將元素e插入到線性表：(a1,a2,…,ai-1,ai,…,an)中，構(gòu)成新的線性表(a1,a2,…,ai-1,e,ai,…,an)，滿足ai-1≤e≤ai,(其中≤為比較關(guān)系),即不破壞原線性關(guān)系。表的長(zhǎng)度為n+1將元素e插入到元素ai-1之后，ai-1的直接后繼和ai

的直接前驅(qū)就改變了，需要在順序表的存儲(chǔ)結(jié)構(gòu)上反映出來(lái)。82.2線性表的順序表示和實(shí)現(xiàn)順序表上插入運(yùn)算的實(shí)現(xiàn):a1a2......ai-1anai將元素ai～an（n-i+1個(gè)元素）依次向后移動(dòng)一個(gè)位置，騰出要放置e的單元。a1a2......ai-1anaie將元素e放在騰出的第i個(gè)空位上。a1a2...aian...ai-1e在線性表L的第i個(gè)位置上插入元素e。e92.2線性表的順序表示和實(shí)現(xiàn)以7個(gè)元素的順序表為例進(jìn)行說(shuō)明，將元素e插入a5之前。a1a2a5a7a4a3a6KK+1K+4K+6K+3K+2K+5K+7e(1)元素a7向后移動(dòng)一個(gè)位置；(2)元素a6向后移動(dòng)一個(gè)位置；a1a2a5a4a3a6a7KK+1K+4K+6K+3K+2K+5K+7a1a2a5a6a4a3a7KK+1K+4K+6K+3K+2K+5K+7(3)元素a5向后移動(dòng)一個(gè)位置；a1a2a6a4a3a5a7KK+1K+4K+6K+3K+2K+5K+7(4)將元素e插入到空位上。

ee102.2線性表的順序表示和實(shí)現(xiàn)用類C語(yǔ)言實(shí)現(xiàn)順序表的插入StatusListInsert_sq(SqList&L,inti,ElemTypex){//將元素x插入在線性表L的第i個(gè)元素位置上if(i<1||i>L.length+1)returnERROR;if(L.length>=L.Listsize){

newbase=(ElemType*)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);

L.elem=newbase;

L.listsize+=INCREMENT;}q=&(L.elem[i-1]);//q為插入位置,C語(yǔ)言數(shù)組下標(biāo)從0開(kāi)始

for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=x;L.length++; returnOK;}//ListInsert_sq①判定輸入是否合法②判定空間是否夠用③修改順序表的參數(shù)④移動(dòng)元素并插入，可改用數(shù)組下標(biāo)實(shí)現(xiàn)112.2線性表的順序表示和實(shí)現(xiàn)順序表上插入運(yùn)算效率分析：

時(shí)間復(fù)雜度 從算法流程上看，查找插入位置、插入元素的時(shí)間消耗是常數(shù)級(jí)，算法執(zhí)行時(shí)間主要消耗在插入前元素的移動(dòng)上，而移動(dòng)元素的個(gè)數(shù)與插入位置i有關(guān)。

最好情況:在表尾插入，不移動(dòng)元素，T(n)=O(1)最壞情況:在表頭插入，移動(dòng)n個(gè)元素，T(n)=O(n)平均復(fù)雜度 設(shè)pi為在第i個(gè)元素之前插入一個(gè)元素的概率，且P1=P2=…=Pi=…=Pn=1/(n+1)，則平均移動(dòng)次數(shù)為： 即T(n)=O(n)

?？臻g復(fù)雜度不需要額外空間，S(n)=O(1)。122.2線性表的順序表示和實(shí)現(xiàn)線性表上的基本運(yùn)算刪除 含義： 將元素ai從線性表：(a1,a2,…,ai-1,ai,ai＋1,…,an)中刪除，構(gòu)成新的線性表(a1,a2,…,ai-1,ai＋1,…,an)，刪除后不破壞原線性關(guān)系。表的長(zhǎng)度為n-1將元素ai刪除之后，ai-1的直接后繼和ai＋1

的直接前驅(qū)就改變了，需要在順序表的存儲(chǔ)結(jié)構(gòu)上反映出來(lái)。132.2線性表的順序表示和實(shí)現(xiàn)順序表上刪除運(yùn)算的實(shí)現(xiàn):a1a2...ai-1an...aiai+1a1a2...ai-1an...ai+1anStatusListDelete_Sq(SqList&L,inti,ElemType&e){第一步：判斷參數(shù)是否合法合理，否則出錯(cuò)；第二步：在物理空間中找到刪除位置；第三步：刪除(將后續(xù)元素位置依次前移)；第四步：刪除后的善后工作(修改表長(zhǎng))}//ListDelete_Sq請(qǐng)同學(xué)們課后自學(xué)順序表的刪除算法及復(fù)雜度分析。14內(nèi)容回顧線性表的邏輯定義元素的一個(gè)有限序列元素之間滿足線性關(guān)系線性表的抽象數(shù)據(jù)類型定義ADTList{

數(shù)據(jù)對(duì)象：D={ai

|ai

ElemSet,i=1,2,…n,n0}

數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1,aiD,i=1,2,…n}

基本運(yùn)算：……}ADTList線性表的順序存儲(chǔ)－－順序表a1…a1a2...aian...…a2aian15內(nèi)容回顧順序表的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：不需要額外的存儲(chǔ)空間來(lái)表示元素間的邏輯關(guān)系可以隨機(jī)地存取表中的任意一個(gè)元素缺點(diǎn)：插入和刪除元素時(shí)要移動(dòng)大量的元素必須事先進(jìn)行空間分配，表的容量難以擴(kuò)充(新算法已解決)順序表的基本運(yùn)算的復(fù)雜度插入T(n)=O(n)，S(n)=O(1)刪除T(n)=O(n)，S(n)=O(1)16內(nèi)容回顧用類C語(yǔ)言實(shí)現(xiàn)順序表的插入StatusListInsert_sq(Sqlist&L,inti,ElemTypex){if(i<1||i>L.length+1)returnERROR;if(L.length>=L.Listsize){

newbase=(ElemType*)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);

L.elem=newbase;

L.listsize+=INCREMENT;}q=&(L.elem[i-1]);//q為插入位置,C語(yǔ)言數(shù)組下標(biāo)從0開(kāi)始for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=x;L.length++; returnOK;}//ListInsert_sq類C語(yǔ)言書(shū)寫(xiě)的算法與C程序之間的差別：(1)算法中除形式參數(shù)外,變量不作定義，在C程序中必須定義；(2)算法中使用的元素類型(ElemType)沒(méi)有定義，C程序中必須定義，常量OK、ERROR、OVERFLOW等在第一章統(tǒng)一定義；(3)算法中的比較運(yùn)算符(equal、less)未作定義，C程序中必須定義；(4)必要的頭文件(用作輸入輸出的stdio.h及內(nèi)存申請(qǐng)的stdlib.h)，在C程序中必須包含。172.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線性表的鏈?zhǔn)酱鎯?chǔ)思路a1a2...aian...存儲(chǔ)結(jié)構(gòu)……a1a2aian邏輯結(jié)構(gòu)實(shí)現(xiàn)方式對(duì)每一個(gè)元素的存儲(chǔ)單位進(jìn)行擴(kuò)充，在包含元素值存儲(chǔ)的同時(shí)，在結(jié)點(diǎn)中存儲(chǔ)與當(dāng)前元素有直接關(guān)系的其他元素(直接前趨／直接后繼)存儲(chǔ)單位的地址(指針)。鏈?zhǔn)酱鎯?chǔ)單位結(jié)構(gòu)示意圖：ai

ai

182.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)鏈表---線性表的鏈?zhǔn)酱鎯?chǔ)內(nèi)涵： 線性表的鏈?zhǔn)酱鎯?chǔ)指用任意的存儲(chǔ)單元存放線性表中的元素，每個(gè)元素與其直接前驅(qū)和（或）直接后繼之間的關(guān)系用指針來(lái)存儲(chǔ)。這稱為鏈表。術(shù)語(yǔ)結(jié)點(diǎn)：數(shù)據(jù)元素及與其有直接關(guān)系的元素的地址構(gòu)成的存儲(chǔ)單位。數(shù)據(jù)域指針域datanext（a）鏈表結(jié)點(diǎn)結(jié)構(gòu)示意圖datapriornextdata（b）（c）nextdata（d）prior192.3.1單鏈表的表示和實(shí)現(xiàn)單鏈表 鏈表中，如果每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，則稱之為線性鏈表或單鏈表。單鏈表的存儲(chǔ)： 每個(gè)結(jié)點(diǎn)存儲(chǔ)當(dāng)前元素的直接后繼。 線性表(a1,a2,…,ai-1,ai,ai＋1,…,an)

邏輯結(jié)構(gòu)………………110ai135………………130a2143135ai+1180………………160anNull165a1130170ai-1110………………單鏈表示意圖a1

a2

ai-1

…ai

ai+1

an^…Head單鏈表的內(nèi)存鏡像指向單鏈表中第一個(gè)結(jié)點(diǎn)的頭指針可惟一確定一個(gè)單鏈表。Head165202.3.1單鏈表的表示和實(shí)現(xiàn)單鏈表的C語(yǔ)言實(shí)現(xiàn)//----------用結(jié)構(gòu)指針描述------------typedef

struct

LNode{

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

struct

LNode*next; //指針域}LNode,*LinkList;與之對(duì)應(yīng)的結(jié)點(diǎn)結(jié)構(gòu)示意圖單鏈表構(gòu)建示意圖(表頭插入法)Headpan^a1

Headppan-1pHead…ai

…ai

LinkList212.3.1單鏈表的表示和實(shí)現(xiàn)帶頭結(jié)點(diǎn)的單鏈表單鏈表示意圖a1

a2

ai-1

…ai

ai+1

an^…Head

頭結(jié)點(diǎn)除指針域外可以存儲(chǔ)鏈表的其他信息，如鏈表的長(zhǎng)度、鏈表的說(shuō)明等信息，也可以不存儲(chǔ)任何信息。帶頭結(jié)點(diǎn)的空鏈表Head

^頭結(jié)點(diǎn)222.3.1單鏈表的表示和實(shí)現(xiàn)單鏈表上的查找運(yùn)算在單鏈表中，必須從頭指針出發(fā)進(jìn)行查找：查找第i個(gè)元素查找指定的元素是否在表中...若找到，則返回該元素的值，否則返回ERROR。在單鏈表上查找第i個(gè)元素的示意圖pk=1單鏈表查找示意圖a1

a2

…ai

an^…Head

232.3.1單鏈表的表示和實(shí)現(xiàn)單鏈表上的查找運(yùn)算在單鏈表中，必須從頭指針出發(fā)進(jìn)行查找：查找第i個(gè)元素查找指定的元素是否在表中...若找到，則返回該元素的值，否則返回ERROR。在單鏈表上查找第i個(gè)元素的示意圖pk=2單鏈表查找示意圖a1

a2

…ai

an^…Head

242.3.1單鏈表的表示和實(shí)現(xiàn)單鏈表上的查找運(yùn)算在單鏈表中，必須從頭指針出發(fā)進(jìn)行查找：查找第i個(gè)元素查找指定的元素是否在表中...若找到，則返回該元素的值，否則返回ERROR。在單鏈表上查找第i個(gè)元素的示意圖pk=i單鏈表查找示意圖a1

a2

…ai

an^…Head

找到，返回P指向的結(jié)點(diǎn)的數(shù)據(jù)。問(wèn)題：i<0或i>n呢？252.3.1單鏈表的表示和實(shí)現(xiàn)用類C語(yǔ)言實(shí)現(xiàn)單鏈表上的查詢(查找第i個(gè)元素)：StatusGetElem_L(LinkListL,inti,ElemType&e){//L是帶頭結(jié)點(diǎn)的單鏈表的頭指針//當(dāng)?shù)趇個(gè)元素存在時(shí)，將該元素的值賦給e并返回OK，否則返回ERRORp=L->next;k=1;//初始化，p指向第一個(gè)結(jié)點(diǎn)，k為計(jì)數(shù)器while(p&&k<i){//順指針向后查找，直到p指向第i個(gè)元素或p為空

p=p->next;++k;} //循環(huán)的退出條件為k=i或到達(dá)單鏈表結(jié)尾(P為空)if(!p||k>i)returnERROR;//第i個(gè)元素不存在e=p->data;returnOK;}//GetElem_L思考:①本算法為何沒(méi)有考慮i值的合法性？

②查找指定元素是否在表中如何實(shí)現(xiàn)？

③查找算法的復(fù)雜度？a1

a2

…ai

an^…L

262.3.1單鏈表的表示和實(shí)現(xiàn)單鏈表上的插入運(yùn)算(第i個(gè)位置上插入新的結(jié)點(diǎn))邏輯運(yùn)算(a1,a2,…,ai-1,ai,ai+1,…,an)(a1,a2,…,ai-1,e,ai,ai+1,…,an)在元素ai之前插入一個(gè)新元素e單鏈表上的實(shí)現(xiàn)示意圖……a1

ai

an^L

ai-1

ai+1

基本步驟：①找到第i-1個(gè)元素所在結(jié)點(diǎn)；②申請(qǐng)一個(gè)新結(jié)點(diǎn)s并填入e值；③

修改s的指針域指向p的下一結(jié)點(diǎn)；p①es②③272.3.1單鏈表的表示和實(shí)現(xiàn)單鏈表上的插入運(yùn)算(第i個(gè)位置上插入新的結(jié)點(diǎn))邏輯運(yùn)算(a1,a2,…,ai-1,ai,ai+1,…,an)(a1,a2,…,ai-1,e,ai,ai+1,…,an)在元素ai之前插入一個(gè)新元素e單鏈表上的實(shí)現(xiàn)示意圖基本步驟：①找到第i-1個(gè)元素所在結(jié)點(diǎn)；p②申請(qǐng)一個(gè)結(jié)點(diǎn)s并填入e值；e③

修改s的指針域指向p的下一結(jié)點(diǎn)；s④修改p的指針域指向s。①②③思考：第③④步是否可交換？……a1

ai

an^L

ai-1

ai+1

④282.3.1單鏈表的表示和實(shí)現(xiàn)插入的類C語(yǔ)言實(shí)現(xiàn)StatusListInsert_L(LinkList&L,inti,ElemTypee){

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

p=L;k=0;//初始化，p指向頭結(jié)點(diǎn)，k為計(jì)數(shù)器

while(p&&k<i-1){//逐步移動(dòng)指針p，直到p指向第i-1個(gè)元素或p為空

p=p->next;++k;}//①if(!p||k>i-1)returnERROR;//無(wú)法插入

if(!(s=(LinkLinst)malloc(sizeof(LNode))))//申請(qǐng)?jiān)豦的結(jié)點(diǎn)空間

returnOVERFLOW;

//內(nèi)存無(wú)空閑單元，無(wú)法申請(qǐng)到空間

s->data=e;

//②

s->next=p->next;

//③插入元素e的結(jié)點(diǎn)

p->next=s; //④returnOK;}//LinstInsert_L復(fù)雜度：

①查找：T1(n)=O(n)

②插入：T2(n)=O(1)

T(n)=O(n)a1

a2

…ai

an^…L

292.3.1單鏈表的表示和實(shí)現(xiàn)單鏈表上的刪除運(yùn)算(把第i個(gè)位置的結(jié)點(diǎn)刪除)邏輯運(yùn)算(a1,a2,…,ai-1,ai,ai+1,…,an)(a1,a2,…,ai-1,ai+1,…,an)刪除結(jié)點(diǎn)ai單鏈表上的實(shí)現(xiàn)示意圖a1

…ai

an^…L

ai-1

ai+1

基本步驟：①找到第i-1個(gè)元素所在結(jié)點(diǎn)；p①②增設(shè)臨時(shí)指針q指向p的下一結(jié)點(diǎn)(待刪除的結(jié)點(diǎn))；q②302.3.1單鏈表的表示和實(shí)現(xiàn)單鏈表上的刪除運(yùn)算(把第i個(gè)位置的結(jié)點(diǎn)刪除)邏輯運(yùn)算(a1,a2,…,ai-1,ai,ai+1,…,an)(a1,a2,…,ai-1,ai+1,…,an)刪除結(jié)點(diǎn)ai單鏈表上的實(shí)現(xiàn)示意圖基本步驟：①找到第i-1個(gè)元素所在結(jié)點(diǎn)；③

修改結(jié)點(diǎn)p的指針域，指向第i-1個(gè)結(jié)點(diǎn)(p->next=p->next->next)；②增設(shè)臨時(shí)指針q指向p的下一結(jié)點(diǎn)(待刪除的結(jié)點(diǎn))；④

刪除結(jié)點(diǎn)q，釋放內(nèi)存空間。a1

…ai

an^…L

ai-1

ai+1

③p①q②312.3.1單鏈表的表示和實(shí)現(xiàn)單鏈表上的刪除運(yùn)算(把第i個(gè)位置的結(jié)點(diǎn)刪除)邏輯運(yùn)算(a1,a2,…,ai-1,ai,ai+1,…,an)(a1,a2,…,ai-1,ai+1,…,an)刪除結(jié)點(diǎn)ai單鏈表上的實(shí)現(xiàn)示意圖基本步驟：①找到第i-1個(gè)元素所在結(jié)點(diǎn)；③

修改結(jié)點(diǎn)p的指針域，指向第i-1個(gè)結(jié)點(diǎn)(p->next=p->next->next)；②增設(shè)臨時(shí)指針q指向p的下一結(jié)點(diǎn)(待刪除的結(jié)點(diǎn))；④

刪除結(jié)點(diǎn)q，釋放內(nèi)存空間。p①③④a1

…ai

an^…L

ai-1

ai+1

q②322.3.1單鏈表的表示和實(shí)現(xiàn)StatusListDelete_L(LinkList&L,inti,ElemType&e){//在帶頭結(jié)點(diǎn)的單鏈表L中，刪除第i個(gè)元素，并由e返回其值

p=L;k=0;//初始化，p指向頭結(jié)點(diǎn)，k為計(jì)數(shù)器

while(p->next&&k<i-1){

//逐一移動(dòng)指針p，直到p指向第i-1個(gè)元素或p為空

p=p->next;++k;}if(!p->next||j>i-1)returnERROR;//無(wú)法刪除

q=p->next;

//* 令q指向待刪除的元素結(jié)點(diǎn)；

p->next=q->next;//*e=q->data;free(q);returnOK;}//ListDelete_L刪除的類C語(yǔ)言實(shí)現(xiàn)思考：①

while語(yǔ)句中的p->next可否用p替代？

②用*注釋的兩條語(yǔ)句可否位置交換？

③本算法的T(n)和S(n)?a1

…ai

an^…L

ai-1

ai+1

pq332.3.1單鏈表的表示和實(shí)現(xiàn)鏈表的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：插入、刪除時(shí)無(wú)須移動(dòng)元素，只需修改指針根據(jù)需要申請(qǐng)存儲(chǔ)空間，且不要求連續(xù)的存儲(chǔ)空間缺點(diǎn)：對(duì)表中的元素只能進(jìn)行順序訪問(wèn)用指針指示元素之間的邏輯關(guān)系（直接前驅(qū)、后繼），存儲(chǔ)空間利用率低自學(xué)內(nèi)容：?jiǎn)捂湵淼谋眍^插入構(gòu)造算法(算法2.11)34內(nèi)容回顧鏈表－－線性表的鏈?zhǔn)酱鎯?chǔ)……a1a2aian邏輯結(jié)構(gòu)單鏈表示意圖a1

a2

ai-1

…ai

ai+1

an^…Heada1

a2

…ai

an^…Head

帶頭結(jié)點(diǎn)的單鏈表示意圖35內(nèi)容回顧單鏈表上的查找運(yùn)算(查找第i個(gè)元素)a1

a2

…ai

an^…Head

計(jì)數(shù)器kpk=2pk=i查找失敗的情形：(1)i<=0：此時(shí)k>i(2)i>n：此時(shí)p==NULLp(初始化)k=1計(jì)數(shù)器k找到，返回P指向的結(jié)點(diǎn)的數(shù)據(jù)。36內(nèi)容回顧單鏈表上的插入運(yùn)算(在第i個(gè)元素前插入新的元素)p①es②a1

…ai

an^…L

ai-1

ai+1

③②s=(LinkLinst)malloc(sizeof(LNode))基本操作對(duì)應(yīng)語(yǔ)句：

①

p=L;k=0;

while(p&&k<i-1){p=p->next;++k;}③

s->next=p->next;④

p->next=s;④37內(nèi)容回顧單鏈表上的刪除運(yùn)算(刪除第i個(gè)元素)③p①q②基本操作對(duì)應(yīng)語(yǔ)句：

①

p=L;k=0;

while(p&&k<i-1){p=p->next;++k;}②q=p->next;

③

p->next=q->next;

④

e=q->data;free(q);

特別注意：修改指針的語(yǔ)句次序一定要小心處理，否則會(huì)出現(xiàn)意想不到的錯(cuò)誤。a1

…ai

an^…L

ai-1

ai+1

ai

④382.3.1單鏈表的表示和實(shí)現(xiàn)用表頭插入法建立帶頭結(jié)點(diǎn)的單鏈表基本步驟： (1)建立頭結(jié)點(diǎn)；L=(LinkList)malloc(sizeof(LNode));L->next=NULL;an

…a2

L^a1 (2)建立新結(jié)點(diǎn)p，填入元素；p=(LinkList)malloc(sizeof(LNode));P->data=ai (3)將新結(jié)點(diǎn)p插入到頭結(jié)點(diǎn)之后，修改頭結(jié)點(diǎn)指針域指向p；p->next=L->next;L->next=p;

^ (4)重復(fù)(2)(3)步直到插入所有結(jié)點(diǎn)，結(jié)束。注：表頭插入法建立的鏈表是輸入元素序列的逆序！392.3.1單鏈表的表示和實(shí)現(xiàn)用類C語(yǔ)言實(shí)現(xiàn)表頭插入算法：an

an-1

…ai

a1^…Head

voidCreateList_L(LinkLinst&L,intn){ //用表頭插入法逆序建立帶頭結(jié)點(diǎn)的單鏈表

L=(LinkList)malloc(sizeof(LNode)); //未做溢出判定，應(yīng)加入 L->next=NULL;//建立頭結(jié)點(diǎn)，假定與元素結(jié)點(diǎn)結(jié)構(gòu)相同

for(i=n;i>0;--i){ //從后向前輸入元素

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

scanf(&p->data);//從鍵盤(pán)輸入元素值，存入新結(jié)點(diǎn)中

p->next=L->next;L->next=p;//新結(jié)點(diǎn)插入到表頭 }}算法復(fù)雜度：T(n)=O(n),S(n)=O(1)402.3.1單鏈表的表示和實(shí)現(xiàn)用C語(yǔ)言實(shí)現(xiàn)表頭插入算法：

LinkList

CreateList_LH(intn){

inti;//聲明本函數(shù)的內(nèi)部變量類型

LinkListhead;//head為指向鏈表的指針類型

LNode*p; //p為指向結(jié)點(diǎn)的指針類型 head=NULL;for(i=n;i>0;--i){//從后向前輸入元素p=(LNode*)malloc(sizeof(LNode));//未做溢出判定，應(yīng)加

scanf(“%d”,&p–>data);//將鍵盤(pán)輸入置入p的數(shù)據(jù)域p–>next=head;head=p;}return(head);//返回指向鏈表的頭指針}//-------用結(jié)構(gòu)指針描述---------typedef

struct

LNode{

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

struct

LNode*next;//指針域}LNode,*LinkList;412.3.1單鏈表的表示和實(shí)現(xiàn)用表尾插入法建立帶頭結(jié)點(diǎn)的單鏈表基本步驟： (1)建立頭結(jié)點(diǎn)，并附設(shè)一個(gè)指針r一直指向最后一個(gè)結(jié)點(diǎn)；

L=(LinkList)malloc(sizeof(LNode));L.next=NULL;r=L;L^ (2)申請(qǐng)一個(gè)新的結(jié)點(diǎn)空間，存入元素值；

p=(LinkList)malloc(sizeof(LNode)); p->data=ai;p->next=NULL; (3)將新結(jié)點(diǎn)插入鏈表尾部，r指向最后結(jié)點(diǎn)；a1^rrra2^r…an^rr

r->next=p;r=p; (4)重復(fù)(2)(3)直到最后一個(gè)結(jié)點(diǎn)，結(jié)束。r作業(yè)：用類C語(yǔ)言寫(xiě)出該算法。是否每次申請(qǐng)結(jié)點(diǎn)都要給其指針域賦空值？422.3.1單鏈表的表示和實(shí)現(xiàn)用表尾插入法建立不帶頭結(jié)點(diǎn)的單鏈表基本步驟： (1)初始化頭指針Head和指向最后結(jié)點(diǎn)的指針r；

head=NULL;r=NULL; (2)申請(qǐng)一個(gè)新的結(jié)點(diǎn)并令p指向該結(jié)點(diǎn)，存入元素值； (3)將新結(jié)點(diǎn)插入到表尾； r->next=p;r=p;?

①當(dāng)r指向非空結(jié)點(diǎn)時(shí)使用上面的語(yǔ)句

②當(dāng)r指向空地址時(shí)head=p;r=p; (4)重復(fù)(2)(3)直到最后一個(gè)結(jié)點(diǎn)，結(jié)束。L^ra1

Lra2

rr…an

rr^注:表尾插入法建立的鏈表與輸入元素順序一致！432.3.1單鏈表的表示和實(shí)現(xiàn)用表尾插入法建立不帶頭結(jié)點(diǎn)的單鏈表(元素為字符，C語(yǔ)言)：LinkList

CreateList_LT(

){charch;LinkListhead;

LNode*p,*r;//p指向新申請(qǐng)的結(jié)點(diǎn)，r指向鏈表的尾結(jié)點(diǎn)head=NULL;r=NULL;

while((ch=getchar()!=‘\n’){p=(LNode*)malloc(sizeof(LNode));if(!p)returnNULL;p–>data=ch;

if(head==

NULL) //插入第一個(gè)結(jié)點(diǎn) head=p;else

r–>next=p; //插入第二個(gè)及以后的結(jié)點(diǎn)r=p;}if(r!=NULL)r–>next=NULL;return(head);}442.3.1單鏈表的表示和實(shí)現(xiàn)說(shuō)明：

第一個(gè)生成的結(jié)點(diǎn)(開(kāi)始結(jié)點(diǎn))要插入到鏈表尾部，此時(shí)指向最后一個(gè)結(jié)點(diǎn)的指針r指向的是空地址，插入時(shí)需要修改的是指針變量r，而隨后插入其余結(jié)點(diǎn)時(shí)，指向最后一個(gè)結(jié)點(diǎn)的指針r指向的是一個(gè)存在的結(jié)點(diǎn)，插入時(shí)需要修改該結(jié)點(diǎn)的指針域r->next。故在算法中應(yīng)加以區(qū)分。 對(duì)于表尾插入法，因?yàn)殡S后的插入要修改前一結(jié)點(diǎn)的指針域，故可以在申請(qǐng)結(jié)點(diǎn)后不處理指針域，而在結(jié)束前對(duì)尾結(jié)點(diǎn)指針域賦空值。452.3.1單鏈表的表示和實(shí)現(xiàn)說(shuō)明：

如果我們?cè)阪湵淼拈_(kāi)始結(jié)點(diǎn)之前附加一個(gè)頭結(jié)點(diǎn)，那么會(huì)帶來(lái)以下兩個(gè)優(yōu)點(diǎn)：a.由于開(kāi)始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中，所以在鏈表的第一個(gè)位置上的操作就和在表的其它位置上的操作一致，無(wú)需進(jìn)行特殊處理；b.無(wú)論鏈表是否為空，其頭指針是指向頭結(jié)點(diǎn)的非空指針（空表中頭結(jié)點(diǎn)的指針域?yàn)榭眨虼丝毡砗头强毡淼奶幚硪簿徒y(tǒng)一了。462.3.1單鏈表的表示和實(shí)現(xiàn)兩個(gè)有序單鏈表的合并(Lc=La∪Lb)La

9

14

15

2740^Lb

7

14

20

^Lc

7

9

14

141520

2740^處理思路：(1)設(shè)置三個(gè)指針pa、pb、pc分別指向La、Lb、Lc的當(dāng)前結(jié)點(diǎn)；(2)比較pa、pb所指結(jié)點(diǎn)的元素值大小，將元素值小的結(jié)點(diǎn)鏈接到pc所指結(jié)點(diǎn)之后；(3)重復(fù)(2)，直到pa、pb中某一指針為空，將另一非空指針鏈追加到pc之后，算法結(jié)束。472.3.1單鏈表的表示和實(shí)現(xiàn)用類C語(yǔ)言實(shí)現(xiàn)歸并算法：voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){//歸并兩個(gè)非遞減單鏈表La、Lb到Lc中，且使Lc非遞減

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

Lc=pc=La; 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; } }//while pc->next=pa?pa:pb; free(Lb);}//MergeList_L算法復(fù)雜度：?T(n)=O(na)+O(nb)＝O(nLa+nLb)482.3.2循環(huán)單鏈表和雙向鏈表循環(huán)單鏈表

線性表：(a1，a2，…，ai，…，an)taila2a1anan-1…(a)循環(huán)單鏈表帶尾指針的循環(huán)單鏈表的特點(diǎn)：通過(guò)表尾指針可以一步得到表頭指針；對(duì)于簡(jiǎn)單的兩個(gè)表的合并可以通過(guò)簡(jiǎn)單操作完成(T(n)=O(1))；492.3.2循環(huán)單鏈表和雙向鏈表循環(huán)單鏈表的合并tailbb2b1bmbn-1…(b)循環(huán)單鏈表Lbtailaa2a1anan-1…(a)循環(huán)單鏈表La502.3.2循環(huán)單鏈表和雙向鏈表tailbb2b1bmbn-1…(b)循環(huán)單鏈表Lb…tailaa2a1anan-1(a)循環(huán)單鏈表La循環(huán)單鏈表的合并pa①②512.3.2循環(huán)單鏈表和雙向鏈表tailbb2b1bmbn-1…(b)循環(huán)單鏈表Lb…tailaa2a1anan-1(a)循環(huán)單鏈表La循環(huán)單鏈表的合并pa①②③522.3.2循環(huán)單鏈表和雙向鏈表tailbb2b1bmbn-1…(b)循環(huán)單鏈表Lba2a1anan-1…循環(huán)單鏈表的合并②③(a)循環(huán)單鏈表La53內(nèi)容回顧單鏈表的建立方法表頭插入法建立單鏈表建立的鏈表是元素輸入次序的逆序表尾插入法建立單鏈表建立的鏈表與元素輸入次序一致帶頭結(jié)點(diǎn)的單鏈表的優(yōu)點(diǎn) 使得指向鏈表的起始結(jié)點(diǎn)(第一個(gè)元素所在的結(jié)點(diǎn))的指針與指向其它元素結(jié)點(diǎn)的指針形式上相同(都是存儲(chǔ)在前一結(jié)點(diǎn)的指針域里)，而可以在算法上一致處理。 與此對(duì)應(yīng)，在不帶頭結(jié)點(diǎn)的單鏈表上，指向起始結(jié)點(diǎn)的指針是一個(gè)指針變量，而指向其他結(jié)點(diǎn)的指針是前一結(jié)點(diǎn)結(jié)構(gòu)的指針域，因此在遍歷、插入、刪除等操作時(shí)必須特殊處理起始結(jié)點(diǎn)。循環(huán)單鏈表的優(yōu)點(diǎn) 使得對(duì)鏈表的某些操作簡(jiǎn)化542.3.2循環(huán)單鏈表和雙向鏈表雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)：Datanextprior雙向鏈表的C語(yǔ)言描述：typedef

struct

DuLNode{

ElemTypedata;

struct

DuLNode*prior;

struct

DuLNode*next;}DuLNode,*DulinkList;雙向鏈表

線性表：(a1，a2，…，ai，…，an)heada1∧a2an-1anai…∧雙向鏈表示意圖…55head∧ai-1ai+1anai…∧…a12.3.2循環(huán)單鏈表和雙向鏈表雙向鏈表上的插入操作(將元素e插入到鏈表的第i個(gè)結(jié)點(diǎn)前)基本步驟：(1)定位指針p指向結(jié)點(diǎn)ai-1;pe

s(2)建立新結(jié)點(diǎn)s并賦e;(3)修改s的next指針域指向p下一結(jié)點(diǎn)：s->next=p->next;(5)修改p的next指針域指向s結(jié)點(diǎn)：p->next=s;(6)修改s下一結(jié)點(diǎn)的prior指針域指向s：s->next->prior=s;(4)修改s的prior指針域指向p結(jié)點(diǎn)：s->prior=p;問(wèn)題：①修改指針的步驟是否可隨意？②不帶頭結(jié)點(diǎn)？562.3.2循環(huán)單鏈表和雙向鏈表雙向鏈表上的刪除操作(刪除第i個(gè)結(jié)點(diǎn))head

∧ai-1ai+1anai…∧…a1∧基本步驟：(1)定位指針p指向結(jié)點(diǎn)ai;p(2)修改p的前一結(jié)點(diǎn)的next指針域指向p下一結(jié)點(diǎn)：p->prior->next=p->next;(3)修改p的下一結(jié)點(diǎn)的prior指針域指向p前一結(jié)點(diǎn)：p->next->prior=p->prior;(3)釋放結(jié)點(diǎn)p。572.3.2循環(huán)單鏈表和雙向鏈表雙向鏈表上的刪除操作(刪除第i個(gè)結(jié)點(diǎn))p基本步驟：(1)定位指針p指向結(jié)點(diǎn)ai;(2)修改p的前一結(jié)點(diǎn)的next指針域指向p下一結(jié)點(diǎn)：p->prior->next=p->next;(3)修改p的下一結(jié)點(diǎn)的prior指針域指向p前一結(jié)點(diǎn)：p->next->prior=p->prior;(4)釋放結(jié)點(diǎn)p。head

∧ai-1ai+1an…∧…a1∧582.3.2循環(huán)單鏈表和雙向鏈表雙向循環(huán)鏈表

head帶頭結(jié)點(diǎn)的空雙向循環(huán)鏈表head

^a1an-1anai…^…帶頭結(jié)點(diǎn)的非空雙向循環(huán)鏈表592.4一元多項(xiàng)式的表示及相加一元多項(xiàng)式的形式：A(x)=p0+p1x+p2x2+…+pixi+…+pnxn存儲(chǔ)形式(a)順序存儲(chǔ)pip0p1...p2pn...pi……Head

(b)單鏈表方式存儲(chǔ)pip0

p1

pi

pn^問(wèn)題：各存儲(chǔ)方式的優(yōu)缺點(diǎn)和使用場(chǎng)合？

Head(c)單鏈表方式存儲(chǔ)pi和ip1

1p5

5…pi

i…pn^n602.4一元多項(xiàng)式的表示及相加例A(x)=7+3x+9x8+

5x17-8x100B(x)=8x+22x7-9x8C(x)=A(x)+B(x)=7+11x+22x7+5x17-8x100存儲(chǔ)方式的選擇－－以單鏈表存儲(chǔ)多項(xiàng)式系數(shù)和指數(shù)+headA703198517-8^100headB81227-9^8//-------多項(xiàng)式的項(xiàng)---------typedef

struct{floatcoef; //系數(shù)

int

expn;//指數(shù)}term,ElemType;//-------多項(xiàng)式結(jié)點(diǎn)---------typedef

struct

LNode{

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

struct

LNode*next;//指針域}*polynomial;612.4一元多項(xiàng)式的表示及相加一元多項(xiàng)式的相加實(shí)現(xiàn)headA703198517-8^100headB81227-9^8headC^qaqbqc//-------多項(xiàng)式結(jié)點(diǎn)---------typedef

struct

LNode{

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

struct

LNode*next;//指針域}*polynomial;622.4一元多項(xiàng)式的表示及相加一元多項(xiàng)式的相加實(shí)現(xiàn)headA703198517-8^100headB81227-9^8headC^qb7^0qcqcqaqa632.4一元多項(xiàng)式的表示及相加一元多項(xiàng)式的相加實(shí)現(xiàn)headB81227-9^8qbheadA703198517-8^100qaheadC^7^0qc11^1qaqbqc642.4一元多項(xiàng)式的表示及相加一元多項(xiàng)式的相加實(shí)現(xiàn)headA703198517-8^100qaheadB81227-9^8qbheadC^7^011^1qc22^7qbqc652.4一元多項(xiàng)式的表示及相加一元多項(xiàng)式的相加實(shí)現(xiàn)headA703198517-8^100qaheadB81227-9^8qbheadC^7^011^122^7qcqaqb662.4一元多項(xiàng)式的表示及相加一元多項(xiàng)式的相加實(shí)現(xiàn)headC^7^011^122^7qcheadA703198517-8^100qaheadB81227-9^8qb5^17qaqc672.4一元多項(xiàng)式的表示及相加一元多項(xiàng)式的相加實(shí)現(xiàn)headB81227-9^8qbheadA703198517-8^100qaheadC^7^011^122^75^17qc-8^100qaqc682.4一元多項(xiàng)式的表示及相加上機(jī)實(shí)現(xiàn)提示(1)編寫(xiě)單鏈表創(chuàng)建算法(函數(shù))；(2)編寫(xiě)多項(xiàng)式加、減法算法；(3)編寫(xiě)多項(xiàng)式表達(dá)式的輸出算法；(4)編寫(xiě)主函數(shù)，兩次調(diào)用建表函數(shù)建立單鏈表；調(diào)用加法函數(shù)創(chuàng)建結(jié)果鏈表；調(diào)用減法函數(shù)創(chuàng)建結(jié)果鏈表；調(diào)用輸出函數(shù)將結(jié)果鏈表轉(zhuǎn)為表達(dá)式輸出。69約瑟夫環(huán)(JosephCircle)問(wèn)題描述： 編號(hào)為1,2,...,n的n個(gè)人按順時(shí)針?lè)较驀蝗Γ咳顺钟幸粋€(gè)密碼（正整數(shù)）?，F(xiàn)在給定一個(gè)隨機(jī)數(shù)m>0，從編號(hào)為1的人開(kāi)始，按順時(shí)針?lè)较?開(kāi)始順序報(bào)數(shù)，報(bào)到m時(shí)停止。報(bào)m的人出圈，同時(shí)留下他的密碼作為新的m值，從他在順時(shí)針?lè)较蛏系南乱粋€(gè)人開(kāi)始，重新從1開(kāi)始報(bào)數(shù)，如此下去，直至所有的人全部出列為止。 請(qǐng)編寫(xiě)程序求出圈的順序。70約瑟夫環(huán)(JosephCircle)例：4596157318213224m：密碼k：計(jì)數(shù)出隊(duì)序列：startk=1571約瑟夫環(huán)(JosephCircle)例：4596157318213224m：密碼k：計(jì)數(shù)出隊(duì)序列：startk=2572約瑟夫環(huán)(JosephCircle)例：4596157318213224m：密碼k：計(jì)數(shù)出隊(duì)序列：startk=3573約瑟夫環(huán)(JosephCircle)例：4596157318213224m：密碼k：計(jì)數(shù)出隊(duì)序列：startk=4574約瑟夫環(huán)(JosephCircle)例：m：密碼k：計(jì)數(shù)出隊(duì)序列：start4596157318213224k=55存入密碼75約瑟夫環(huán)(JosephCircle)例：96157318213224m：密碼k：計(jì)數(shù)出隊(duì)序列：startk=14576約瑟夫環(huán)(JosephCircle)例：96157318213224m：密碼k：計(jì)數(shù)出隊(duì)序列：start5k=4477約瑟夫環(huán)(JosephCircle)例：961573113224m：密碼k：計(jì)數(shù)出隊(duì)序列：start5k=18278約瑟夫環(huán)(JosephCircle)例：961573113224m：密碼k：計(jì)數(shù)出隊(duì)序列：start52k=8879約瑟夫環(huán)(JosephCircle)例：1573113224m：密碼k：計(jì)數(shù)出隊(duì)序列：start52k=19680約瑟夫環(huán)(JosephCircle)例：1573113224m：密碼k：計(jì)數(shù)出隊(duì)序列：start52k=99681約瑟夫環(huán)(JosephCircle)例：3113224m：密碼k：計(jì)數(shù)出隊(duì)序列：start52k=1156782約瑟夫環(huán)(JosephCircle)例：3113224m：密碼k：計(jì)數(shù)出隊(duì)序列：start5267k=151583約瑟夫環(huán)(JosephCircle)例：3113m：密碼k：計(jì)數(shù)出隊(duì)序列：start52674k=12284約瑟夫環(huán)(JosephCircle)例：3113m：密碼k：計(jì)數(shù)出隊(duì)序列：start52674k=222285約瑟夫環(huán)(JosephCircle)例：31m：密碼k：計(jì)數(shù)出隊(duì)序列：start526743k=1186約瑟夫環(huán)(JosephCircle)例：m：密碼k：計(jì)數(shù)出隊(duì)序列：start526743k=13187約瑟夫環(huán)(JosephCircle)存儲(chǔ)結(jié)構(gòu)4596157318213224tailp需要的變量：k：計(jì)數(shù)p:指向當(dāng)前結(jié)點(diǎn)pre：指向p的前驅(qū)結(jié)點(diǎn)上機(jī)實(shí)現(xiàn)提示：①編寫(xiě)建立循環(huán)鏈表算法②編寫(xiě)結(jié)點(diǎn)輸出算法(帶輸入?yún)?shù)k)③編寫(xiě)主程序pre88Joseph問(wèn)題代碼#include<stdio.h>#include<stdlib.h>typedef

structnode{

intcode;/*游戲者的編號(hào)*/u