[院校資料]第二章-線性表-資料下載頁
2025-10-07 23:56本頁面
【正文】 uLnode, *DuLinklist。 prior data next 結(jié)點(diǎn)： 雙向鏈表 a1 a3 a2 p s 插入前： p s 插入后： a1 a2 a3 ?插入結(jié)點(diǎn)：指針 p所指的結(jié)點(diǎn)前插入 指針 s所指的結(jié)點(diǎn) ? sprior=pprior。 ppriornext=s。 snext=p。pprior=s。 雙向鏈表 ?插入結(jié)點(diǎn)程序 Status ListInsert_DuL(DuLinklist L, int i, ElemType e) { DuLinklist s,p。 // 在 L中確定第 i個(gè)元素的位置指針 p if (!(p=GetElemP_DuL(L,i))) return ERROR。 if(!(s = (DuLinklist)malloc(sizeof(DuLNode)))) return ERROR。 sdata = e。 // 構(gòu)造數(shù)據(jù)為 e的結(jié)點(diǎn) s sprior = pprior。 p prior next = s。 snext = p。 pprior = s。 return OK。 } 雙向鏈表 p a1 a2 刪除前： a3 刪除后： ppriornext =pnext a1 a2 p a3 pnextproir =pprior 釋放結(jié)點(diǎn)： free(p)。 ?刪除結(jié)點(diǎn)：刪除指針 p所指的結(jié)點(diǎn) 雙向鏈表 ?刪除結(jié)點(diǎn) :刪除第 i個(gè)元素，并由 e返回其值 Status ListDelete_DuL(DuLinklist L, int i, ElemType amp。e) { DuLinklist p。 // 在 L中確定第 i個(gè)元素的位置指針 p if (!(p=GetElemP_DuL(L,i))) return ERROR。 e = pdata。 // 刪除的結(jié)點(diǎn)的值存入 e p prior next = pnext。 pnextprior = pprior。 free(p)。 return OK。 } 一元多項(xiàng)式的表示及加法 Pn(x)=p0+p1x+p2x2+…+p nxn Qm(x)=q0+q1x+q2x2+…+q mxm 設(shè) mn,則 ? Rm(x)= Pn(x)+ Qm(x) =(p0+q0)+(p1+q1)x+(p2+q2)x2+…+(p m+qm)xm +(pm+1+qm+1)xm+1 + … + p nxn ? 可用線性表 R表示 R=(p0+q0,p1+q1,p2+q2,…,p m+qm,pm+1+qm+1,…, p n) 一元多項(xiàng)式的表示及加法 ? 順序存儲(chǔ)結(jié)構(gòu)線性表 :很難處理多項(xiàng)式次數(shù)很高且變化很大的情況，存儲(chǔ)結(jié)構(gòu)的最大長(zhǎng)度很難確定。 例 :S(x)=1+3x10000+2x20210 一元多項(xiàng)式的表示及加法 Pn(x)=p1xe1+p2xe2+… + pmxem ? 可用長(zhǎng)度為 m且每個(gè)元素有兩個(gè)數(shù)據(jù)項(xiàng) (系數(shù)項(xiàng)和指數(shù)項(xiàng) )的線性表表示一元多項(xiàng)式 Pn(x) ? 最壞情況下：需要多存儲(chǔ)一倍的數(shù)據(jù) ? 普遍情況下 ,對(duì)于多數(shù)多項(xiàng)式 ,將大大節(jié)約存儲(chǔ)空間。 一元多項(xiàng)式的表示及加法 ADT Polynomial { 數(shù)據(jù)對(duì)象：略 數(shù)據(jù)關(guān)系：略 基本操作： CreatePolyn( amp。P, m ) 操作結(jié)果 :輸入 m項(xiàng)的系數(shù)和指數(shù)，建立一元多項(xiàng)式 DestroyPolyn( amp。P) 操作結(jié)果：銷毀一元多項(xiàng)式 P AddPolyn( amp。Pa, amp。Pb) 操作結(jié)果：完成多項(xiàng)式的加法運(yùn)算 ,即 Pa=Pa+Pb,并銷毀一元多項(xiàng)式 Pb SubtractPolyn(amp。Pa,amp。Pb) 操作結(jié)果：完成多項(xiàng)式的想減運(yùn)算 ,即 Pa=PaPb,并銷毀一元多項(xiàng)式 Pb MultiplyPolyn(amp。Pa,amp。Pb) 操作結(jié)果：完成多項(xiàng)式的相乘運(yùn)算 ,即 Pa=PaxPb,并銷毀一元多項(xiàng)式 Pb } ADT Polynomial 。 一元多項(xiàng)式的表示及加法 ? A17(x)=7+3x+9x8+5x17 ? B8(x)=8x+22x79x8 7 0 3 1 頭結(jié)點(diǎn) 9 8 5 17 ^ 8 1 22 7 頭結(jié)點(diǎn) 9 8 ^ 一元多項(xiàng)式的表示及加法 typedef struct { float coef 。 int expn 。 } ElemType 。 typedef LinkList polynomial 。 void AddPoly( polynomial amp。pa, polynomial amp。pb) { ha=GetHead(pa)。 hb=GetHead(pb) 。 qa=NextPos(pa,ha)。qb=NextPos(pb,hb)。 while(qaamp。amp。qb){ a=GetCurElem(qa) 。 b=GetCurElem(qb)。 switch( *cmp(a,b) ){ case 1: ha=qa。 qa=NextPos(pa,qa)。 break 。 case 0: sum=+ 。 if( sum!= ) { SetCurElem(qa,sum)。 ha=qa } else { DelFirst(ha,qa) 。 FreeNode(qa) 。 DelFirst(hb,qb) 。 FreeNode(qb) 。 qa=NextPos(pa,ha) 。 qb=NextPos(pb,hb) 。} case 1: DelFirst(hb,qb) 。 InsFirst(ha,qb)。 qb=NextPos(pb,hb) 。 ha = NextPos(Pa,ha) 。 break 。 } } if( !ListEmpty(pb) Append(pa,qb) 。 FreeNode(hb) 。 }
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1