數(shù)據(jù)結(jié)構(gòu)一元多項(xiàng)式與線性表習(xí)題PPT課件

1、雙向鏈表 每個(gè)結(jié)點(diǎn)中設(shè)置兩個(gè)指針，一個(gè)指向后繼，一個(gè)指向前驅(qū)。可直接確定一個(gè)結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)。從而可提高效率。 prior data next Pp=(p-prior)-next=(p-next)-prior 第1頁/共42頁線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu)typedef struct DuNode ElemType data; struct DuNode *prior，*next;DuNode, * DulinkList; 第2頁/共42頁雙向鏈表的操作特點(diǎn)：1、“查詢” 和單鏈表相同2、“插入” 和“刪除”時(shí)需要同時(shí)修改兩個(gè)方向上的指針。第3頁/共42頁aiai-1es-next = p-ne

2、xt; p-next = s;s-next-prior = s; s-prior = p;psai-1雙向鏈表的插入（后插）第4頁/共42頁ai-1aiepsai-1ai雙向鏈表的插入（前插）sprior=pprior; snext=p;ppriornext=s; pprior=s;第5頁/共42頁ai-1雙向鏈表的刪除aiai+1p-next = p-next-next;p-next-prior = p;pai-1第6頁/共42頁雙向循環(huán)鏈表空表非空表a1a2an第7頁/共42頁用鏈表實(shí)現(xiàn)線性表的操作時(shí)，存在的問用鏈表實(shí)現(xiàn)線性表的操作時(shí)，存在的問題：題： 1 1表長是一個(gè)隱含的值；表長是一個(gè)

3、隱含的值； 2 2插入元素時(shí)，可能需遍歷整個(gè)鏈表；插入元素時(shí)，可能需遍歷整個(gè)鏈表； 3 3在鏈表中，元素的在鏈表中，元素的“位序位序”概念淡化，概念淡化，結(jié)點(diǎn)的結(jié)點(diǎn)的“位置位置”概念加強(qiáng)。概念加強(qiáng)。第8頁/共42頁改進(jìn)鏈表結(jié)構(gòu)：改進(jìn)鏈表結(jié)構(gòu)：Typedef struct LNode Typedef struct LNode /結(jié)點(diǎn)類型結(jié)點(diǎn)類型 ElemType data; ElemType data; struct LNode struct LNode * *next; next; * *Link, Link, * *Position;Position;Typedef struct LNode

4、 Typedef struct LNode /鏈表類型鏈表類型 Link head, tail; Link head, tail; int len; int len; LinkList ; LinkList ;基本操作基本操作第9頁/共42頁第2章 線性表2.1 線性表的類型定義2.2 線性表的順序表示和實(shí)現(xiàn)2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 線性鏈表 循環(huán)鏈表 雙向鏈表 2.4 一元多項(xiàng)式的表示及相加 第10頁/共42頁nnnxpxpxppxp.)(2210計(jì)算機(jī)中，可以用一個(gè)關(guān)于系數(shù)的線性表來表示： P = （p0, p1, ，pn）2.4 一元多項(xiàng)式的表示及相加但是對(duì)于形如S(x) = 1

5、+ 3x10000 2x20000的多項(xiàng)式，上述表示方法是否合適？第11頁/共42頁 一般情況下的一元稀疏多項(xiàng)式可寫成 Pn(x) = p1xe1 + p2xe2 + + pmxem 其中：pi 是指數(shù)為 ei 的項(xiàng)的非零系數(shù)， 0 e1 e2 em = n可以下列線性表表示：（p1, e1）, (p2, e2), , (pm,em) ）將單鏈表的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)著一元多項(xiàng)式中的一個(gè)非零項(xiàng)，它由三個(gè)域組成，分別表示非零項(xiàng)的系數(shù)、指數(shù)和指向下一個(gè)結(jié)點(diǎn)的指針。第12頁/共42頁 P99(x) = 7x3 - 2x12 - 8x99例:可用線性表( (7, 3),(-2, 12),(-8, 99) )表

6、示： 7 3 -2 12 - 8 99 head 第13頁/共42頁一元多項(xiàng)式的表示：typedef struct / 項(xiàng)的表示 float coef; / 系數(shù) int expn; / 指數(shù) term, ElemType;typedef OrderedLinkList polynomial; / 用帶表頭結(jié)點(diǎn)的有序鏈表表示多項(xiàng)式數(shù)據(jù)元素類型定義為:第14頁/共42頁抽象數(shù)據(jù)類型一元多項(xiàng)式的定義抽象數(shù)據(jù)類型一元多項(xiàng)式的定義ADT Polynomial 數(shù)據(jù)對(duì)象： D ai|aiTermSet, i=1,2,.,m, m0 TermSet 中的每個(gè)元素包含一個(gè)表示 系數(shù)的實(shí)數(shù)和表示指數(shù)的整數(shù) 數(shù)

7、據(jù)關(guān)系： R1 |ai-1 ,aiD, i=2,.,n 且ai-1中的指數(shù)值ai中的指數(shù)值 第15頁/共42頁 基本操作基本操作： CreatPolyn ( &P, m )CreatPolyn ( &P, m ) DestroyPolyn ( &P )DestroyPolyn ( &P ) PrintPolyn ( P )PrintPolyn ( P ) PolynLength( P )PolynLength( P ) AddPolyn ( &Pa, &Pb ) AddPolyn ( &Pa, &Pb ) SubtractPoly

8、n ( &Pa, &Pb ) SubtractPolyn ( &Pa, &Pb ) MultiplyPolyn ( &Pa, &Pb ) MultiplyPolyn ( &Pa, &Pb ) ADT Polynomial ADT Polynomial初始條件：一元多項(xiàng)式 Pa 和 Pb 已存在。 操作結(jié)果：Pa = PaPb，并銷毀一元多項(xiàng)式 Pb。第16頁/共42頁 在實(shí)際的應(yīng)用程序中取用順序結(jié)構(gòu)存儲(chǔ)一元在實(shí)際的應(yīng)用程序中取用順序結(jié)構(gòu)存儲(chǔ)一元多項(xiàng)式，還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)多項(xiàng)式，要視多項(xiàng)式，還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)多項(xiàng)式，要視多項(xiàng)式作

9、何種運(yùn)算而定，若只對(duì)多項(xiàng)式進(jìn)行多項(xiàng)式作何種運(yùn)算而定，若只對(duì)多項(xiàng)式進(jìn)行“求值求值”等不改變多項(xiàng)式的系數(shù)和指數(shù)的運(yùn)算，等不改變多項(xiàng)式的系數(shù)和指數(shù)的運(yùn)算，則采用類似于順序表的順序存儲(chǔ)結(jié)構(gòu)即可，否則采用類似于順序表的順序存儲(chǔ)結(jié)構(gòu)即可，否則應(yīng)采用鏈?zhǔn)酱鎯?chǔ)表示。則應(yīng)采用鏈?zhǔn)酱鎯?chǔ)表示。 第17頁/共42頁例：設(shè)兩個(gè)一元多項(xiàng)式為例：設(shè)兩個(gè)一元多項(xiàng)式為: : A(X)= 4 + 6X A(X)= 4 + 6X4 4 + 5X+ 5X8 8 + 4X+ 4X1212 B(X)= 2X B(X)= 2X3 3 - 5X- 5X8 8 + 3X+ 3X12 12 + 7X+ 7X1515 求此兩一元多項(xiàng)式之和求此兩一

10、元多項(xiàng)式之和: C(x)=A(x)+B(x): C(x)=A(x)+B(x)第18頁/共42頁AddPolyn ( &Pa, &Pb ) 4 0 6 5 8 4 12 headA 2 3 -5 8 3 12 headB 7 15 7 12 7 15 4 0 6 4 headC 2 3 121547764)(xxxxC32x4第19頁/共42頁設(shè)p,q分別指向A,B中某一結(jié)點(diǎn)，p,q初值是第一結(jié)點(diǎn)比較p-exp與q-expp-exp exp: p結(jié)點(diǎn)是和多項(xiàng)式中的一項(xiàng) p后移,q不動(dòng)p-exp q-exp: q結(jié)點(diǎn)是和多項(xiàng)式中的一項(xiàng) 將q插在p之前,q后移,p不動(dòng)p-exp =

11、q-exp: 系數(shù)相加0：從A表中刪去p, 釋放p,q，p,q后移0：修改p系數(shù)域, 釋放q，p,q后移直到p或q為NULL 若q=NULL，結(jié)束 若p=NULL，將B中剩余部分連到A上運(yùn)算規(guī)則第20頁/共42頁Void AddPolyn( polynomial &pa, polynomial &pb ) ha=GetHead(pa); hb=GetHead(pb) ; / ha和hb分別指向Pa和Pb的頭結(jié)點(diǎn) qa=NextPos(pa, ha); qb=NextPos(pb, hb) ; /qa和qb分別指向Pa和Pb中當(dāng)前結(jié)點(diǎn) haqaqb4 0 6 4 5 8 4 12

12、 2 3 -5 8 3 12 7 15 0 -1 hb 0 -1 while (qa & qb ) /Pa和Pb均非空 a=GetCurElem(qa); b=GetCurElem(qb); /a和b為兩表中當(dāng)前比較元素 switch(*cmp(a, b) ) case -1; /pa當(dāng)前的指數(shù)小于pb當(dāng)前的指數(shù) ha=qa; qa=NextPos(pa, qa); break;case 1; /pa當(dāng)前的指數(shù)大于pb當(dāng)前的指數(shù)DelFirst(hb,qb);InsFirst(ha,qb);qb=NextPos(pb, hb);ha=NextPos(pa, ha);break;case

13、 0; sum=a.coef+b.coef; if (sum!=0) /修改pa當(dāng)前結(jié)點(diǎn)系數(shù) SetCurElem(qa,sum); ha=qa; DelFirst(ha,qa);FreeNode(qa); DelFirst(hb,qb);FreeNode(qb); qb=NextPos(pb,hb); qa=NextPos(pa,ha); break;else /刪除pa當(dāng)前結(jié)點(diǎn)7if (!ListEmpty(pb) Append(pa, qb) ; /鏈接pb剩余結(jié)點(diǎn)FreeNode(hb); /釋放pb頭結(jié)點(diǎn) pa121547764)(xxxxC32x第21頁/共42頁兩個(gè)一元多項(xiàng)式相加

14、的算法Void AddPolyn( polynomial &pa, polynomial &pb ) ha=GetHead(pa); hb=GetHead(pb) ; / ha和hb分別指向Pa和Pb的頭結(jié)點(diǎn) qa=NextPos(pa, ha); qb=NextPos(pb, hb) ; /qa和qb分別指向Pa和Pb中當(dāng)前結(jié)點(diǎn) while (qa & qb ) /Pa和Pb均非空 a=GetCurElem(qa); b=GetCurElem(qb); /a和b為兩表中當(dāng)前比較元素 switch(*cmp(a, b) ) case -1; /pa當(dāng)前的指數(shù)小于pb當(dāng)前

15、的指數(shù) ha=qa; qa=NextPos(pa, qa); break; case 1; /pa當(dāng)前的指數(shù)大于pb當(dāng)前的指數(shù) DelFirst(hb,qb); InsFirst(ha,qb); qb=NextPos(pb, hb); ha=NextPos(pa, ha); break;int cmp (term a，term b)； /依a的指數(shù)值)b的指數(shù)值，分別返回-1,0和1； 第22頁/共42頁兩個(gè)一元多項(xiàng)式相加的算法 case 0; sum=a.coef+b.coef; if (sum!=0) /修改pa當(dāng)前結(jié)點(diǎn)系數(shù) SetCurElem(qa,sum); ha=qa; else

16、/刪除pa當(dāng)前結(jié)點(diǎn) DelFirst(ha,qa); FreeNode(qa); DelFirst(hb,qb); FreeNode(qb); qb=NextPos(pb,hb); qa=NextPos(pa,ha); break; / switch /while if (!ListEmpty(pb) Append(pa, qb) ; /鏈接pb剩余結(jié)點(diǎn) FreeNode(hb); /釋放pb頭結(jié)點(diǎn) / AddPolyn第23頁/共42頁本章小結(jié)1.了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間 存在著線性關(guān)系，在計(jì)算機(jī)中表示這種關(guān)系 的兩類不同的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)和鏈 式存儲(chǔ)結(jié)構(gòu)。用前者表示的線

17、性表簡稱為順 序表，用后者表示的線性表簡稱為鏈表。2.熟練掌握這兩類存儲(chǔ)結(jié)構(gòu)的描述方法，以及 線性表的各種基本操作的實(shí)現(xiàn)。3.能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線 性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場合第24頁/共42頁一、基礎(chǔ)知識(shí)題1. 在一個(gè)單鏈表HL中，若要向表頭插入一個(gè)由 指針P指向的結(jié)點(diǎn)，則執(zhí)行（ ）。 A） HL = p ；p - next = HL； B） p - next = HL； HL = p ； C） p - next = HL； p = HL ； D） p - next = HL - next； HL - next = p ；習(xí)題與練習(xí)第25頁/共42頁2. 在一個(gè)單

18、鏈表HL中，若要在指針q指向的結(jié) 點(diǎn)的后面插入一個(gè)由指針P指向的結(jié)點(diǎn)，則 執(zhí)行（ ）。 A） q - next = p - next ； p = q； B） p - next = q - next ； q = p； C） q - next = p - next ； p - next = q ； D） p - next = q - next ； q - next = p ；第26頁/共42頁3. 指出以下算法中的錯(cuò)誤和低效（費(fèi)時(shí)）之處，并 將其修改正確。Status DeleteK ( &L,i,k) /從順序存儲(chǔ)結(jié)構(gòu)的線性表L中刪除第i個(gè)元素起的K個(gè)元素 if ( i 1 | k L.

19、len ) return ERROR; for (count = 1; count = i+1; j- - ) L.elemj-1 = L.elemj; L.len - -; return OK; / DeleteK1.不合法條件錯(cuò)誤。2.第二個(gè)for語句中，元素前移的次序錯(cuò)誤。2.低效之處是每次刪除一個(gè)元素的策略。第27頁/共42頁Status DeleteK ( &L,i,k) /從順序存儲(chǔ)結(jié)構(gòu)的線性表L中刪除第i個(gè)元素起的k個(gè)元素 if (i1|kL.len+1|iL.len) return ERROR; for (j = i+k ; jdata=P-next-data;2877

20、5PRHH28375PR第31頁/共42頁(2) T=P; while(T!=NULL) T-data=(T-data)*2; T=T-next; H2P1014616H28375P第32頁/共42頁(3) T=P; while(T-next!=NULL) T-data=(T-data)*2; T=T-next; H28375PH2P101468第33頁/共42頁(4) P=(LNode*)malloc(sizeof(LNode); P-data=10; R-next=P; P-next=S;HS28375PR第34頁/共42頁(4) P=(LNode*)malloc(sizeof(LNode); P-data=10; R-next=P; P-next=S;PHS28375PRHS28375R第35頁/共42頁P(yáng)10HS28375RHS28375PR(4) P=(LNode*)malloc(sizeof(LNode); P-data=10; R-next=P; P-next=S;第36頁/共42頁(4) P=(LNode*)malloc(sizeof(LNode); P-data=10; R-next=P; P-next=S;P10HS28375PRHS28375R第37頁/共42頁(4) P=(LNode*)malloc(siz