數(shù)據(jù)結(jié)構(gòu)-第4次課第二章線性表(雙向鏈表多項(xiàng)式).ppt

2 3 3雙向鏈表雙向鏈表 Doublelinkedlist 在單鏈表的每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其直接前趨的指針域prior 這樣就形成的鏈表中有兩個(gè)方向不同的鏈 故稱為雙向鏈表 形式描述為 structDuLNode datatypedata DuLNode prior next 結(jié)點(diǎn) 存儲(chǔ)前趨結(jié)點(diǎn)的地址 存儲(chǔ)數(shù)據(jù)元素 存儲(chǔ)后繼結(jié)點(diǎn)的地址 雙鏈表一般由頭指針唯一確定的 將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來(lái)構(gòu)成循環(huán)鏈表 并稱之為雙向鏈表 設(shè)指針p指向某一結(jié)點(diǎn) 則雙向鏈表結(jié)構(gòu)的對(duì)稱性可用下式描述 p prior next p p next prior 雙向鏈表結(jié)點(diǎn)p前的插入數(shù)據(jù)x的操作 p x q newDuLNode q data x q prior p prior q next p p prior next q p prior q 雙向鏈表結(jié)點(diǎn)p前的插如數(shù)據(jù)x的操作 p x q newDuLNode q data x q prior p prior q next p p prior next q p prior q 雙向鏈表結(jié)點(diǎn)p前的插如數(shù)據(jù)x的操作 p x q newDuLNode q data x q prior p prior q next p p prior next q p prior q p prior next p next p next prior p prior deletep p 刪除p指針?biāo)傅慕Y(jié)點(diǎn) p prior next p next p next prior p prior deletep p 刪除p指針?biāo)傅慕Y(jié)點(diǎn) p prior next p next p next prior p prior deletep p 刪除p指針?biāo)傅慕Y(jié)點(diǎn) 雙向鏈表的插入 刪除靈活 鏈表維護(hù)的工作量大 所需的存儲(chǔ)空間較大 2 4一元多項(xiàng)式的表示及相加 一 一元多項(xiàng)式的表示多項(xiàng)式的操作是表處理的典型用例 數(shù)學(xué)上 一元多項(xiàng)式可按升冪寫成 在計(jì)算機(jī)中 可以用一個(gè)線性表來(lái)表示 P p0 p1 pn 但是對(duì)于形如 S x 1 3x10000 2x20000 的多項(xiàng)式 上述表示方法是否合適 一般情況下的一元稀疏多項(xiàng)式可寫成Pn x p1xe1 p2xe2 pmxem其中 pi是指數(shù)為ei的項(xiàng)的非零系數(shù) 0 e1 e2 em n 可以下列線性表表示 p1 e1 p2 e2 pm em P999 x 7x3 2x12 8x999 例如 可用線性表 7 3 2 12 8 999 表示 ADTPolynomial 數(shù)據(jù)對(duì)象 數(shù)據(jù)關(guān)系 抽象數(shù)據(jù)類型一元多項(xiàng)式的定義如下 D ai ai TermSet i 1 2 m m 0TermSet中的每個(gè)元素包含一個(gè)表示系數(shù)的實(shí)數(shù)和表示指數(shù)的整數(shù) R1 ai 1 ai D i 2 n且ai 1中的指數(shù)值 ai中的指數(shù)值 CreatPolyn P m DestroyPolyn P PrintPolyn P 基本操作 操作結(jié)果 輸入m項(xiàng)的系數(shù)和指數(shù) 建立一元多項(xiàng)式P 初始條件 一元多項(xiàng)式P已存在 操作結(jié)果 銷毀一元多項(xiàng)式P 初始條件 一元多項(xiàng)式P已存在 操作結(jié)果 打印輸出一元多項(xiàng)式P PolynLength P AddPolyn Pa Pb SubtractPolyn Pa Pb 相減操作 ADTPolynomial 初始條件 一元多項(xiàng)式P已存在 操作結(jié)果 返回一元多項(xiàng)式P中的項(xiàng)數(shù) 初始條件 一元多項(xiàng)式Pa和Pb已存在 操作結(jié)果 完成多項(xiàng)式相加運(yùn)算 即 Pa Pa Pb 并銷毀一元多項(xiàng)式Pb 二 一元多項(xiàng)式的實(shí)現(xiàn) typedefstruct 表達(dá)式中項(xiàng)的表示floatcoef 系數(shù)intexpn 指數(shù) term ElemType typedefOrderedLinkListpolynomial 用帶表頭結(jié)點(diǎn)的有序鏈表表示多項(xiàng)式 結(jié)點(diǎn)的數(shù)據(jù)元素類型定義為 存儲(chǔ)結(jié)構(gòu) 用線性鏈表表示 有頭結(jié)點(diǎn) 每個(gè)結(jié)點(diǎn)有coef 系數(shù)exp指數(shù)next 指針 其中 頭結(jié)點(diǎn)的exp為 1 多項(xiàng)式A x 7 3x 9x8 5x17 例 求兩多項(xiàng)式的和多項(xiàng)式A x 7 3x 9x8 5x17B x 8x 22x7 9x8 二 一元多項(xiàng)式的相加算法 一元多項(xiàng)式相加運(yùn)算規(guī)則 指數(shù)相同的項(xiàng)系數(shù)相加 A x B x 相加的和多項(xiàng)式為C x A x B x 7 11x 22x7 5x17 設(shè)多項(xiàng)式A x B x 分別用帶表頭結(jié)點(diǎn)的線性鏈表pa pb表示 完成 ha ha hb 一元多項(xiàng)式加法算法主要步驟 分別對(duì)兩個(gè)鏈表ha hb進(jìn)行掃描 ha和hb分別指向兩個(gè)表的頭結(jié)點(diǎn) 設(shè)工作指針pa pb分別指向兩個(gè)多項(xiàng)式當(dāng)前進(jìn)行比較的結(jié)點(diǎn) qa指針指向pa的前驅(qū) qb指針指向pb的前驅(qū) 初始 qa ha pa ha next pb hb next 若pa pb都不為空 則比較兩者指數(shù) pa expexp qa pa后移 pa exp pb exp 將pb所指結(jié)點(diǎn)的系數(shù) 加 到pa所指結(jié)點(diǎn)的系數(shù)上 若和為0 則pa所指結(jié)點(diǎn)刪除 pb所指結(jié)點(diǎn)刪除 qa pa qb pb調(diào)整 否則pb所指結(jié)點(diǎn)刪除 qa pa qb pb調(diào)整 pa exp pb exp 將表hb中pb所指結(jié)點(diǎn)插入到ha表pa所指結(jié)點(diǎn)之前 qb pb后移 若pb不空 hb表中從pb開始的結(jié)點(diǎn)插入到ha表尾上 intcomp inta intb if anext pb hb next while pa NULL pb qb pb pb next break 1 qb next pb next qa next pb pb next pa pb qb next qa qa next break if pb NULL qa next pb delet