數(shù)據(jù)結(jié)構(gòu)線性表單向和雙向循環(huán)鏈表及習(xí)題課課件

線性表(List)小結(jié)和作業(yè)雙向循環(huán)鏈表習(xí)題講解單向循環(huán)鏈表一元多項式線性表(List)小結(jié)和作業(yè)雙向循環(huán)鏈表習(xí)題講解單向循環(huán)鏈表單向循環(huán)鏈表定義：最后一個結(jié)點的指針不是空指針，而是指向了頭結(jié)點。La1a2a3L邏輯形態(tài)：單向循環(huán)鏈表定義：最后一個結(jié)點的指針不是空指針，而是指向了頭單向循環(huán)鏈表差異：1、判斷空表的條件：L->next==NULL變?yōu)長->next==L2、判斷最后一個數(shù)據(jù)元素的條件由p->next==NULL改變?yōu)閜->next==L單向循環(huán)鏈表差異：1、判斷空表的條件：2、判斷最后一個數(shù)據(jù)元InitListLStatusInitList(LinkList&L){ node=(LNode*)malloc(sizeof(LNode)); if(!node)return(OVERFLOW); L=node;

node->next=L; return(OK);}InitListLStatusInitList(LinkLListLength1、p指向頭結(jié)點,j=02、如果p->next!=L，j++,p->next3、重復(fù)2，直到p為空，j即為長度。a1a2a3LListLength1、p指向頭結(jié)點,j=02、如果p->ListLengthintListLength(LinkListL){count=0;p=p->next;count++;}}return(count);p=L;while(p->next){count=0;p=p->next;count++;}}return(count);p=L;while(p->next!=L){ListLengthintListLength(LinkLGetItem1、p指向頭結(jié)點2、重復(fù)p=p->next操作i次3、p指向了第i個元素pa1a2a3LGetItem1、p指向頭結(jié)點2、重復(fù)p=p->next操作單向循環(huán)鏈表a1a2a3L尾指針：a1a2a3L頭指針：單向循環(huán)鏈表a1a2a3L尾指針：a1a2a3L頭指針：單向循環(huán)鏈表a1a2a3A將循環(huán)單鏈表A的尾和B的頭相連，構(gòu)成一個新的循環(huán)單鏈表，由B指向新表尾b1b2b3BA->next=q->next;q=B->next;B->next=A->nextfree(q);A=NULL;q單向循環(huán)鏈表a1a2a3A將循環(huán)單鏈表A的尾和B的頭相連，構(gòu)雙向鏈表一、作用：方便定位一個結(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(OVERFLOW);node->prior=node->next=NULL;L=node;LInitListStatusInitList(DuListListLength1、p指向頭結(jié)點,j=02、如果p->next不為空，j++,p=p->next3、重復(fù)2，直到p->next為空，j即為長度。a2a3a1LListLength1、p指向頭結(jié)點,j=02、如果p->ListLength(討論)1、p指向頭結(jié)點,j=02、如果p->prior不為空，j++,p=p->prior3、重復(fù)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(OVERFLOW);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,ai,aListDeleteai-1aiai+1p->next=p->next->next;p->next->prior=p;pai-1qq=p->next;ListDeleteai-1aiai+1p->next=ListDelete1、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é)點qListDelete1、p指向頭結(jié)點q=p->next;ListDelete(討論)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線性表的應(yīng)用---一元多項式p=(p0,p1,…，pn)但是對于形如:S(x)=1+3x10000–2x20000nnxpxpxppxp++++=...)(2210線性表的應(yīng)用---一元多項式p=(p0,p1,…，p稀疏一元多項式

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

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

p(x)=7x3-2x12-8x999例如:((7,3),(-2,12),(-8,999))稀疏一元多項式p(x)=7x3-2x12-8x稀疏一元多項式的實現(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習(xí)題講解-2.21(方法一)2.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習(xí)題講解-2.21(方法一)2.21逆置順序表a1習(xí)題講解-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]=tmp;}}ai

an-i+1i=1,…,length/2ElemTypetmp;習(xí)題講解-2.21voidreverse(SqList習(xí)題講解-2.21(方法二)2.21逆置順序表a1a2a3a4……an-3an-2an-1anL.elemL.lengthL.listsizeanan-1an-2an-3……a4a3a2a1L.elemL.lengthL.listsizea1

ana2an-1a3an-2i=1,2,3…j=n,n-1,…習(xí)題講解-2.21(方法二)2.21逆置順序表a1習(xí)題講解-2.21voidreverse(SqList&L){if(L.length<=1)return;for(i=1,j=L.length;i<j;i++,j--){tmp=L.elem[i-1];L.elem[i-1]=L.elem[j-1];L.elem[j-1]=tmp;}}ElemTypetmp;習(xí)題講解-2.21voidreverse(SqList習(xí)題講解-2.22(方法一)La1a2…an2.22逆置線性鏈表Lanan-1…a1習(xí)題講解-2.22(方法一)La1a2…an2.22逆置線習(xí)題講解-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)系習(xí)題講解-2.22(方法一)(a1,a2,…,ai-1習(xí)題講解-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、重復(fù)執(zhí)行，直到q為空指針La1a2ptq6、L->next->next=NULL,L->next=p;習(xí)題講解-2.22(方法一)1、p指向要修改指針的結(jié)點，初始習(xí)題講解-2.22(方法一)1、如果表中只有一個結(jié)點，不處理2、如果表是空表，不處理LL習(xí)題講解-2.22(方法一)1、如果表中只有一個結(jié)點，不處理習(xí)題講解-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;}習(xí)題講解-2.22(方法一)voidreverse(Lin習(xí)題講解-2.22(擴展)雙向循環(huán)鏈表???a2a3a1LL習(xí)題講解-2.22(擴展)雙向循環(huán)鏈表???a2a3a1L習(xí)題講解-2.22(擴展)a2a3a1Lpqpqpqpqp->next=p->prior;p->prior=q;p=q;q=p->next;p=L;q=p->next;習(xí)題講解-2.22(擴展)a2a3a1Lpqpqpqpqp習(xí)題講解-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;}}習(xí)題講解-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)小結(jié)和作業(yè)雙向循環(huán)鏈表習(xí)題講解單向循環(huán)鏈表一元多項式線性表(List)小結(jié)和作業(yè)雙向循環(huán)鏈表習(xí)題講解單向循環(huán)鏈表單向循環(huán)鏈表定義：最后一個結(jié)點的指針不是空指針，而是指向了頭結(jié)點。La1a2a3L邏輯形態(tài)：單向循環(huán)鏈表定義：最后一個結(jié)點的指針不是空指針，而是指向了頭單向循環(huán)鏈表差異：1、判斷空表的條件：L->next==NULL變?yōu)長->next==L2、判斷最后一個數(shù)據(jù)元素的條件由p->next==NULL改變?yōu)閜->next==L單向循環(huán)鏈表差異：1、判斷空表的條件：2、判斷最后一個數(shù)據(jù)元InitListLStatusInitList(LinkList&L){ node=(LNode*)malloc(sizeof(LNode)); if(!node)return(OVERFLOW); L=node;

node->next=L; return(OK);}InitListLStatusInitList(LinkLListLength1、p指向頭結(jié)點,j=02、如果p->next!=L，j++,p->next3、重復(fù)2，直到p為空，j即為長度。a1a2a3LListLength1、p指向頭結(jié)點,j=02、如果p->ListLengthintListLength(LinkListL){count=0;p=p->next;count++;}}return(count);p=L;while(p->next){count=0;p=p->next;count++;}}return(count);p=L;while(p->next!=L){ListLengthintListLength(LinkLGetItem1、p指向頭結(jié)點2、重復(fù)p=p->next操作i次3、p指向了第i個元素pa1a2a3LGetItem1、p指向頭結(jié)點2、重復(fù)p=p->next操作單向循環(huán)鏈表a1a2a3L尾指針：a1a2a3L頭指針：單向循環(huán)鏈表a1a2a3L尾指針：a1a2a3L頭指針：單向循環(huán)鏈表a1a2a3A將循環(huán)單鏈表A的尾和B的頭相連，構(gòu)成一個新的循環(huán)單鏈表，由B指向新表尾b1b2b3BA->next=q->next;q=B->next;B->next=A->nextfree(q);A=NULL;q單向循環(huán)鏈表a1a2a3A將循環(huán)單鏈表A的尾和B的頭相連，構(gòu)雙向鏈表一、作用：方便定位一個結(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(OVERFLOW);node->prior=node->next=NULL;L=node;LInitListStatusInitList(DuListListLength1、p指向頭結(jié)點,j=02、如果p->next不為空，j++,p=p->next3、重復(fù)2，直到p->next為空，j即為長度。a2a3a1LListLength1、p指向頭結(jié)點,j=02、如果p->ListLength(討論)1、p指向頭結(jié)點,j=02、如果p->prior不為空，j++,p=p->prior3、重復(fù)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(OVERFLOW);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,ai,aListDeleteai-1aiai+1p->next=p->next->next;p->next->prior=p;pai-1qq=p->next;ListDeleteai-1aiai+1p->next=ListDelete1、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é)點qListDelete1、p指向頭結(jié)點q=p->next;ListDelete(討論)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線性表的應(yīng)用---一元多項式p=(p0,p1,…，pn)但是對于形如:S(x)=1+3x10000–2x20000nnxpxpxppxp++++=...)(2210線性表的應(yīng)用---一元多項式p=(p0,p1,…，p稀疏一元多項式

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

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

p(x)=7x3-2x12-8x999例如:((7,3),(-2,12),(-8,999))稀疏一元多項式p(x)=7x3-2x12-8x稀疏一元多項式的實現(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習(xí)題講解-2.21(方法一)2.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習(xí)題講解-2.21(方法一)2.21逆置順序表a1習(xí)題講解-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]=tmp;}}ai

an-i+1i=1,…,length/2ElemTypetmp;習(xí)題講解-2.21voidreverse(SqList習(xí)題講解-2.21(方法二)2.21逆置順序表a1a2a3a4……an-3an-2an-1anL.elemL.lengthL.listsizeanan-1an-2an-3……a4a3a2a1L.elemL.lengthL.listsizea1

ana2an-1a3an-2i=1,2,3…j=n,n-1,…習(xí)題講解-2.21(方法二)2.21逆置順序表