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

2 3 3雙向鏈表雙向鏈表 Doublelinkedlist 在單鏈表的每個結(jié)點里再增加一個指向其直接前趨的指針域prior 這樣就形成的鏈表中有兩個方向不同的鏈 故稱為雙向鏈表 形式描述為 structDuLNode datatypedata DuLNode prior next 結(jié)點 存儲前趨結(jié)點的地址 存儲數(shù)據(jù)元素 存儲后繼結(jié)點的地址 雙鏈表一般由頭指針唯一確定的 將頭結(jié)點和尾結(jié)點鏈接起來構(gòu)成循環(huán)鏈表 并稱之為雙向鏈表 設(shè)指針p指向某一結(jié)點 則雙向鏈表結(jié)構(gòu)的對稱性可用下式描述 p prior next p p next prior 雙向鏈表結(jié)點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é)點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é)點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指針所指的結(jié)點 p prior next p next p next prior p prior deletep p 刪除p指針所指的結(jié)點 p prior next p next p next prior p prior deletep p 刪除p指針所指的結(jié)點 雙向鏈表的插入 刪除靈活 鏈表維護的工作量大 所需的存儲空間較大 2 4一元多項式的表示及相加 一 一元多項式的表示多項式的操作是表處理的典型用例 數(shù)學上 一元多項式可按升冪寫成 在計算機中 可以用一個線性表來表示 P p0 p1 pn 但是對于形如 S x 1 3x10000 2x20000 的多項式 上述表示方法是否合適 一般情況下的一元稀疏多項式可寫成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 表示 ADTPolynomial 數(shù)據(jù)對象 數(shù)據(jù)關(guān)系 抽象數(shù)據(jù)類型一元多項式的定義如下 D ai ai TermSet i 1 2 m m 0TermSet中的每個元素包含一個表示系數(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項的系數(shù)和指數(shù) 建立一元多項式P 初始條件 一元多項式P已存在 操作結(jié)果 銷毀一元多項式P 初始條件 一元多項式P已存在 操作結(jié)果 打印輸出一元多項式P PolynLength P AddPolyn Pa Pb SubtractPolyn Pa Pb 相減操作 ADTPolynomial 初始條件 一元多項式P已存在 操作結(jié)果 返回一元多項式P中的項數(shù) 初始條件 一元多項式Pa和Pb已存在 操作結(jié)果 完成多項式相加運算 即 Pa Pa Pb 并銷毀一元多項式Pb 二 一元多項式的實現(xiàn) typedefstruct 表達式中項的表示floatcoef 系數(shù)intexpn 指數(shù) term ElemType typedefOrderedLinkListpolynomial 用帶表頭結(jié)點的有序鏈表表示多項式 結(jié)點的數(shù)據(jù)元素類型定義為 存儲結(jié)構(gòu) 用線性鏈表表示 有頭結(jié)點 每個結(jié)點有coef 系數(shù)exp指數(shù)next 指針 其中 頭結(jié)點的exp為 1 多項式A x 7 3x 9x8 5x17 例 求兩多項式的和多項式A x 7 3x 9x8 5x17B x 8x 22x7 9x8 二 一元多項式的相加算法 一元多項式相加運算規(guī)則 指數(shù)相同的項系數(shù)相加 A x B x 相加的和多項式為C x A x B x 7 11x 22x7 5x17 設(shè)多項式A x B x 分別用帶表頭結(jié)點的線性鏈表pa pb表示 完成 ha ha hb 一元多項式加法算法主要步驟 分別對兩個鏈表ha hb進行掃描 ha和hb分別指向兩個表的頭結(jié)點 設(shè)工作指針pa pb分別指向兩個多項式當前進行比較的結(jié)點 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é)點的系數(shù) 加 到pa所指結(jié)點的系數(shù)上 若和為0 則pa所指結(jié)點刪除 pb所指結(jié)點刪除 qa pa qb pb調(diào)整 否則pb所指結(jié)點刪除 qa pa qb pb調(diào)整 pa exp pb exp 將表hb中pb所指結(jié)點插入到ha表pa所指結(jié)點之前 qb pb后移 若pb不空 hb表中從pb開始的結(jié)點插入到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