線性表雙向鏈表和習題課課件

雙向鏈表線性表(List)部分操作的實現(xiàn)小結(jié)和作業(yè)雙向循環(huán)鏈表習題講解復習一元多項式雙向鏈表線性表(List)部分操作的實現(xiàn)小結(jié)和作業(yè)雙向循環(huán)鏈復習-單鏈表a1a2a3LL邏輯形態(tài)空鏈表復習-單鏈表a1a2a3LL邏輯形態(tài)空鏈表復習-循環(huán)單鏈表a1a2a3L尾指針：a1a2a3L頭指針：L復習-循環(huán)單鏈表a1a2a3L尾指針：a1a2a3L頭指針：雙向鏈表一、作用：方便定位一個結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點二、結(jié)點的形式ai三、C語言描述typedefstructDuLNode{ElemTypedata;

structDuLNode*prior;

structDuLNode*next;

}DuLNode；雙向鏈表一、作用：方便定位一個結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點二、結(jié)雙向鏈表五、邏輯形態(tài)四、頭指針的描述typedefstructDuLNode*DuLinkList;La2a3a1L雙向鏈表五、邏輯形態(tài)四、頭指針的描述typedefstr部分操作的實現(xiàn)InitList(&L)ListInsert(&L,i,e)ListDelete(&L,i,&e)ListLength(L)部分操作的實現(xiàn)InitList(&L)ListInsert(InitListStatusInitList(DuListLink&L){node=(DuLNode*)malloc(sizeof(DuLNode));}return(OK);if(!node)return(ERROR);node->prior=node->next=NULL;L=node;LInitListStatusInitList(DuListListLength1、p指向頭結(jié)點,j=02、如果p->next不為空，j++,p->next3、重復2，直到p->next為空，j即為長度。a2a3a1LListLength1、p指向頭結(jié)點,j=02、如果p->ListLength(討論)1、p指向頭結(jié)點,j=02、如果p->prior不為空，j++,p->prior3、重復2，直到p->prior為空，j即為長度。a2a3a1LListLength(討論)1、p指向頭結(jié)點,j=02、如ListLengthintListLength(DuLinkListL){count=0;p=p->next;count++}}return(count);p=L;while(p->next){count=0;p=p->prior;count++}}return(count);p=L;while(p->prior){ListLengthintListLength(DuLinListInsert邏輯結(jié)構(gòu)的變化<ai-1,ai>→<ai-1,e>,<e,ai>(a1,…,ai-1,ai,…,an)

→

(a1,…,ai-1,e,ai,…,an)存儲結(jié)構(gòu)的變化ListInsert邏輯結(jié)構(gòu)的變化<ai-1,ai>ListInsertai-1aies->next=p->next;s->prior=p;

p->next=s;

s->next->prior=s;

psai-1aiListInsertai-1aies->next=p->ListInsert1、p指向頭結(jié)點分析：2、執(zhí)行p=p->nexti-1次，使得p指向第i-1個結(jié)點3、申請一個新結(jié)點s，調(diào)整s、第i-1和第i個結(jié)點的指針ListInsert1、p指向頭結(jié)點分析：2、執(zhí)行p=p->ListInsert找到第i-1個結(jié)點的代碼是：p=L;j=0;while(j<i-1

){p=p->next;j++}ListInsert找到第i-1個結(jié)點的代碼是：p=L;jListInsert生成一個新結(jié)點存放數(shù)據(jù)元素e的代碼是：s=(DuLNode*)malloc(sizeof(DuLNode));if(!s)return(ERROR);s->data=e;ListInsert生成一個新結(jié)點存放數(shù)據(jù)元素e的代碼是：ListInserts->next=p->next;s->prior=p;

p->next=s;

s->next->prior=s;

ListInserts->next=p->next;ListInsert(討論)a2a3a1Less->next=p->next;s->prior=p;

p->next=s;

s->next->prior=s;

i=1?i=length+1???ListInsert(討論)a2a3a1Less->nextListDelete(討論)

(a1,…,ai-1,ai,ai+1,…,an)<ai-1,ai>,<ai,ai+1><ai-1,ai+1>(a1,…,ai-1,ai+1,…,an)邏輯結(jié)構(gòu)的變化：存儲結(jié)構(gòu)的變化：ListDelete(討論)(a1,…,ai-1,aListDelete(討論)ai-1aiai+1p->next=p->next->next;p->next->prior=p;pai-1qq=p->next;ListDelete(討論)ai-1aiai+1p->nexListDelete(討論)1、p指向頭結(jié)點q=p->next;p->next=p->next->next;

p->next->prior=p;

e=q->data;free(q);2、執(zhí)行i-1次p=p->next，p指向了第i-1個結(jié)點3、q=p->next,q指向第i個結(jié)點4、修改第i-1個和第i個結(jié)點的指針5、釋放結(jié)點qListDelete(討論)1、p指向頭結(jié)點q=p->nListDelete(討論)a2a3a1Lp->next=p->next->next;p->next->prior=p;ai-1aiai+1pai-1i=1?i=length???ListDelete(討論)a2a3a1Lp->next=雙向循環(huán)鏈表1、每個結(jié)點的next域構(gòu)成了一個循環(huán)單鏈表2、每個結(jié)點的prior域構(gòu)成了另一個循環(huán)單鏈表邏輯形態(tài)La2a3a1L雙向循環(huán)鏈表1、每個結(jié)點的next域構(gòu)成了一個循環(huán)單鏈表2、雙向循環(huán)鏈表-Insertai-1aiepsai-1ais->next=p->next;s->prior=p;

p->next=s;

s->next->prior=s;

a2a3a1L雙向循環(huán)鏈表-Insertai-1aiepsai-1ais-雙向循環(huán)鏈表-Deletep->next=p->next->next;p->next->prior=p;a2a3a1Lai-1pai-1aiai+1雙向循環(huán)鏈表-Deletep->next=p->next線性表的應用---一元多項式p=(p0,p1,…，pn)但是對于形如:S(x)=1+3x10000–2x20000線性表的應用---一元多項式p=(p0,p1,…，p稀疏一元多項式

一般情況下的一元稀疏多項式可寫成：

Pn(x)=p1xe1+p2xe2+…+pmxem其中：pi是指數(shù)為ei的項的非零系數(shù)，0≤e1<e2<┄<em=n可以下列線性表表示：((p1,e1),(p2,e2),…,(pm,em))稀疏一元多項式一般情況下的一元稀疏多項式可寫成：可以下列稀疏一元多項式

P999(x)=7x3-2x12-8x999例如:((7,3),(-2,12),(-8,999))稀疏一元多項式P999(x)=7x3-2x12-稀疏一元多項式的實現(xiàn)typedefstruct{//項的表示

floatcoef;//系數(shù)

intexpn;//指數(shù)}

ElemType;typedefLinkListpolynomial;

//用帶表頭結(jié)點的有序鏈表表示多項式稀疏一元多項式的實現(xiàn)typedefstruct{一元多項式的操作AH=1-3x6+7x12BH=-x4+3x6-9x10+8x14-36712AH36-910814BH-1410

10CH-14-910712814

一元多項式的操作AH=1-3x6+7x12-3習題講解-2.212.21逆置順序表a1a2a3a4……an-3an-2an-1anL.elemL.lengthL.listsizeanan-1an-2an-3……a4a3a2a1L.elemL.lengthL.listsizea1

ana2an-1a3an-2ai

an-i+1i=1,…,length/2習題講解-2.212.21逆置順序表a1習題講解-2.21voidreverse(SqList&l){if(L.length<=1)return;for(i=1;i<=L.length%2;i++){tmp=L.elem[i-1];L.elem[i-1]=L.elem[L.length-i];L.elem[L.length-i]=L.elem[i-1];}}ai

an-i+1i=1,…,length/2習題講解-2.21voidreverse(SqList習題講解-2.22(方法一)La1a2…an2.22逆置線性鏈表Lanan-1…a1習題講解-2.22(方法一)La1a2…an2.22逆置線習題講解-2.22(方法一)(a1,a2,…,ai-1,ai,ai+1,…,an-1,an)(an,an-1,…,ai+1,ai,ai-1,…,a2,a1)ai的前驅(qū)變成了后繼，后繼變成了前驅(qū)該問題的核心是要修改數(shù)據(jù)元素的鄰里關(guān)系習題講解-2.22(方法一)(a1,a2,…,ai-1習題講解-2.22(方法一)1、p指向要修改指針的結(jié)點，初始時是a12、q指向p的后繼？否則，修改p的指針，鏈就斷了3、t指向p的前驅(qū)？在新表中t是p的后繼4、p->next=t，t=p，p=q，q=p->next5、重復執(zhí)行，直到q為空指針La1a2ptq6、L->next->next=NULL,L->next=p;習題講解-2.22(方法一)1、p指向要修改指針的結(jié)點，初始習題講解-2.22(方法一)1、如果表中只有一個結(jié)點，不處理2、如果表是空表，不處理LL習題講解-2.22(方法一)1、如果表中只有一個結(jié)點，不處理習題講解-2.22(方法一)voidreverse(LinList&L){if(!L->next||!L->next->next)return;//空表或單元素t=L,p=t->next,q=p->next;//t,p,q分別指向ai-1,ai,ai+1while(q){p->next=t;t=p,p=q,q=p->next;}L->next->next=NULL;L->next=p;}習題講解-2.22(方法一)voidreverse(Lin習題講解-2.22(方法二)a1a2a3LLpsucca1psucca2psucca3p習題講解-2.22(方法二)a1a2a3LLpsucca習題講解-2.22(方法二)voidreverse(LinkList&L){//逆置帶頭結(jié)點的單鏈表Lp=L->next;L->next=NULL;while(p){succ=p->next;//succ指向*p的后繼p->next=L->next;L->next=p;//*p插入在頭結(jié)點之后p=succ;}}習題講解-2.22(方法二)voidreverse(Li習題講解-2.22(擴展)雙向循環(huán)鏈表???a2a3a1LL習題講解-2.22(擴展)雙向循環(huán)鏈表???a2a3a1L習題講解-2.22(擴展)a2a3a1Lpqpqpqpqq=p->next;p->next=p->prior;p->prior=q;習題講解-2.22(擴展)a2a3a1Lpqpqpqpqq習題講解-2.22(擴展)voidreverse(DuLinkList&L){//逆置帶頭結(jié)點的單鏈表Lp=L;q=p->next;while(q!=L){p->next=p->prior;p->prior=q;p=q;q=p->next;}}習題講解-2.22(擴展)voidreverse(Du小結(jié)雙向循環(huán)鏈表雙向鏈表由于結(jié)構(gòu)的不合理，使用的較少小結(jié)雙向循環(huán)鏈表雙向鏈表由于結(jié)構(gòu)的不合理，使用的較少作業(yè)作業(yè)：2.8，2.32作業(yè)作業(yè)：2.8，2.32雙向鏈表線性表(List)部分操作的實現(xiàn)小結(jié)和作業(yè)雙向循環(huán)鏈表習題講解復習一元多項式雙向鏈表線性表(List)部分操作的實現(xiàn)小結(jié)和作業(yè)雙向循環(huán)鏈復習-單鏈表a1a2a3LL邏輯形態(tài)空鏈表復習-單鏈表a1a2a3LL邏輯形態(tài)空鏈表復習-循環(huán)單鏈表a1a2a3L尾指針：a1a2a3L頭指針：L復習-循環(huán)單鏈表a1a2a3L尾指針：a1a2a3L頭指針：雙向鏈表一、作用：方便定位一個結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點二、結(jié)點的形式ai三、C語言描述typedefstructDuLNode{ElemTypedata;

structDuLNode*prior;

structDuLNode*next;

}DuLNode；雙向鏈表一、作用：方便定位一個結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點二、結(jié)雙向鏈表五、邏輯形態(tài)四、頭指針的描述typedefstructDuLNode*DuLinkList;La2a3a1L雙向鏈表五、邏輯形態(tài)四、頭指針的描述typedefstr部分操作的實現(xiàn)InitList(&L)ListInsert(&L,i,e)ListDelete(&L,i,&e)ListLength(L)部分操作的實現(xiàn)InitList(&L)ListInsert(InitListStatusInitList(DuListLink&L){node=(DuLNode*)malloc(sizeof(DuLNode));}return(OK);if(!node)return(ERROR);node->prior=node->next=NULL;L=node;LInitListStatusInitList(DuListListLength1、p指向頭結(jié)點,j=02、如果p->next不為空，j++,p->next3、重復2，直到p->next為空，j即為長度。a2a3a1LListLength1、p指向頭結(jié)點,j=02、如果p->ListLength(討論)1、p指向頭結(jié)點,j=02、如果p->prior不為空，j++,p->prior3、重復2，直到p->prior為空，j即為長度。a2a3a1LListLength(討論)1、p指向頭結(jié)點,j=02、如ListLengthintListLength(DuLinkListL){count=0;p=p->next;count++}}return(count);p=L;while(p->next){count=0;p=p->prior;count++}}return(count);p=L;while(p->prior){ListLengthintListLength(DuLinListInsert邏輯結(jié)構(gòu)的變化<ai-1,ai>→<ai-1,e>,<e,ai>(a1,…,ai-1,ai,…,an)

→

(a1,…,ai-1,e,ai,…,an)存儲結(jié)構(gòu)的變化ListInsert邏輯結(jié)構(gòu)的變化<ai-1,ai>ListInsertai-1aies->next=p->next;s->prior=p;

p->next=s;

s->next->prior=s;

psai-1aiListInsertai-1aies->next=p->ListInsert1、p指向頭結(jié)點分析：2、執(zhí)行p=p->nexti-1次，使得p指向第i-1個結(jié)點3、申請一個新結(jié)點s，調(diào)整s、第i-1和第i個結(jié)點的指針ListInsert1、p指向頭結(jié)點分析：2、執(zhí)行p=p->ListInsert找到第i-1個結(jié)點的代碼是：p=L;j=0;while(j<i-1

){p=p->next;j++}ListInsert找到第i-1個結(jié)點的代碼是：p=L;jListInsert生成一個新結(jié)點存放數(shù)據(jù)元素e的代碼是：s=(DuLNode*)malloc(sizeof(DuLNode));if(!s)return(ERROR);s->data=e;ListInsert生成一個新結(jié)點存放數(shù)據(jù)元素e的代碼是：ListInserts->next=p->next;s->prior=p;

p->next=s;

s->next->prior=s;

ListInserts->next=p->next;ListInsert(討論)a2a3a1Less->next=p->next;s->prior=p;

p->next=s;

s->next->prior=s;

i=1?i=length+1???ListInsert(討論)a2a3a1Less->nextListDelete(討論)

(a1,…,ai-1,ai,ai+1,…,an)<ai-1,ai>,<ai,ai+1><ai-1,ai+1>(a1,…,ai-1,ai+1,…,an)邏輯結(jié)構(gòu)的變化：存儲結(jié)構(gòu)的變化：ListDelete(討論)(a1,…,ai-1,aListDelete(討論)ai-1aiai+1p->next=p->next->next;p->next->prior=p;pai-1qq=p->next;ListDelete(討論)ai-1aiai+1p->nexListDelete(討論)1、p指向頭結(jié)點q=p->next;p->next=p->next->next;

p->next->prior=p;

e=q->data;free(q);2、執(zhí)行i-1次p=p->next，p指向了第i-1個結(jié)點3、q=p->next,q指向第i個結(jié)點4、修改第i-1個和第i個結(jié)點的指針5、釋放結(jié)點qListDelete(討論)1、p指向頭結(jié)點q=p->nListDelete(討論)a2a3a1Lp->next=p->next->next;p->next->prior=p;ai-1aiai+1pai-1i=1?i=length???ListDelete(討論)a2a3a1Lp->next=雙向循環(huán)鏈表1、每個結(jié)點的next域構(gòu)成了一個循環(huán)單鏈表2、每個結(jié)點的prior域構(gòu)成了另一個循環(huán)單鏈表邏輯形態(tài)La2a3a1L雙向循環(huán)鏈表1、每個結(jié)點的next域構(gòu)成了一個循環(huán)單鏈表2、雙向循環(huán)鏈表-Insertai-1aiepsai-1ais->next=p->next;s->prior=p;

p->next=s;

s->next->prior=s;

a2a3a1L雙向循環(huán)鏈表-Insertai-1aiepsai-1ais-雙向循環(huán)鏈表-Deletep->next=p->next->next;p->next->prior=p;a2a3a1Lai-1pai-1aiai+1雙向循環(huán)鏈表-Deletep->next=p->next線性表的應用---一元多項式p=(p0,p1,…，pn)但是對于形如:S(x)=1+3x10000–2x20000線性表的應用---一元多項式p=(p0,p1,…，p稀疏一元多項式

一般情況下的一元稀疏多項式可寫成：

Pn(x)=p1xe1+p2xe2+…+pmxem其中：pi是指數(shù)為ei的項的非零系數(shù)，0≤e1<e2<┄<em=n可以下列線性表表示：((p1,e1),(p2,e2),…,(pm,em))稀疏一元多項式一般情況下的一元稀疏多項式可寫成：可以下列稀疏一元多項式

P999(x)=7x3-2x12-8x999例如:((7,3),(-2,12),(-8,999))稀疏一元多項式P999(x)=7x3-2x12-稀疏一元多項式的實現(xiàn)typedefstruct{//項的表示

floatcoef;//系數(shù)

intexpn;//指數(shù)}

ElemType;typedefLinkListpolynomial;

//用帶表頭結(jié)點的有序鏈表表示多項式稀疏一元多項式的實現(xiàn)typedefstruct{一元多項式的操作AH=1-3x6+7x12BH=-x4+3x6-9x10+8x14-36712AH36-910814BH-1410

10CH-14-910712814

一元多項式的操作AH=1-3x6+7x12-3習題講解-2.212.21逆置順序表a1a2a3a4……an-3an-2an-1anL.elemL.lengthL.listsizeanan-1an-2an-3……a4a3a2a1L.elemL.lengthL.listsizea1

ana2an-1a3an-2ai

an-i+1i=1,…,length/2習題講解-2.212.21逆置順序表a1習題講解-2.21voidreverse(SqList&l){if(L.length<=1)return;for(i=1;i<=L.length%2;i++){tmp=L.elem[i-1];L.elem[i-1]=L.elem[L.length-i];L.elem[L.length-i]=L.elem[i-1];}}ai

an-i+1i=1,…,length/2習題講解-2.21voidreverse(SqList習題講解-2.22(方法一)La1a2…an2.22逆置線性鏈表Lanan-1…a1習題講解-2.22(方法一)La1a2…an2.22逆置線習題講解-2.22(方法一)(a1,a2,…,ai-1,ai,ai+1,…,an-1,an)(an,an-1,…,ai+1,ai,ai-1,…,a2,a1)ai的前驅(qū)變成了后繼，后繼變成了前驅(qū)該問題的核心是要修改數(shù)據(jù)元素的鄰里關(guān)系習題講解-2.22(方法一)(a1,a2,…,ai-1習題講解-2.22(方法一)1、p指向要修改指針的結(jié)點，初始時是a12、q指向p的后繼？否則，修改p的指針，鏈就斷了3、t指向p的前驅(qū)？在新表中t是p的后繼4、p->ne