[工學(xué)]數(shù)據(jù)結(jié)構(gòu)第04次課線性表b-資料下載頁
2025-10-10 00:02本頁面
【正文】 ... , )m m m nR p q p q p q p p?? ? ? ?假定 mn 數(shù) 據(jù) 結(jié) 構(gòu) 計(jì)算機(jī)與信息學(xué)院 劉勇 第 38頁 分析： 一元多項(xiàng)式在計(jì)算機(jī)內(nèi)存儲(chǔ)時(shí)，既可用 順序表 存儲(chǔ)，又可用 鏈表 存儲(chǔ)。那么實(shí)際應(yīng)用中如何選取采用哪種存儲(chǔ)方式呢？ p0 p1 p2 … pn1 pn 順序表 鏈表 a 1 0 2 28 3 104 ^ 多項(xiàng)式的次數(shù)不高且零系數(shù)項(xiàng)較少時(shí) 多項(xiàng)式的次數(shù)很高且零系數(shù)項(xiàng)較多時(shí) 1 0 0 4 5 68 3 1 0b x x x? ? ?1 0 4 2 83 2 1a x x? ? ?0 0 1 1 1( , , ... , , , ... , )m m m nR p q p q p q p p?? ? ? ?（ 通常設(shè)計(jì)兩個(gè)數(shù)據(jù)域和一個(gè)指針域 ） 數(shù) 據(jù) 結(jié) 構(gòu) 計(jì)算機(jī)與信息學(xué)院 劉勇 第 39頁 2. 用 C語言如何具體描述它的定義？ 法一：用類 C語言， 參見教材 P42 法二：用標(biāo)準(zhǔn) C語言： typedef struct poly_node *poly_pointer。 typedef struct poly_node { int coef。 //coefficient系數(shù) int expon。 //exponent指數(shù) poly_pointer link。 }。 poly_pointer a, b, c。 coef expon link 數(shù) 據(jù) 結(jié) 構(gòu) 計(jì)算機(jī)與信息學(xué)院 劉勇 第 40頁 4. 如何編程實(shí)現(xiàn)兩個(gè)一元多項(xiàng)式相加？ b x x x? ? ?8 3 1014 10 63 14 2 8 1 0 a ^ 8 14 － 3 10 10 6 b ^ 例： 123 814 ??? xxa運(yùn)算規(guī)則 ： 兩多項(xiàng)式中 指數(shù)相同的項(xiàng)對(duì)應(yīng)系數(shù)相加 ，若和不為 0,則構(gòu)成多項(xiàng)式 c(=a+b)中的一項(xiàng)； a和 b中所有 指數(shù)不相同的項(xiàng)均應(yīng)復(fù)制 到 c中。 數(shù) 據(jù) 結(jié) 構(gòu) 計(jì)算機(jī)與信息學(xué)院 劉勇 第 41頁 實(shí)現(xiàn)思路： 依次比較 Pa和 Pb所指結(jié)點(diǎn)中的指數(shù)項(xiàng) ， 依 Paexpon == Pbexpon等情況 ， 再?zèng)Q定是將兩系數(shù)域的數(shù)值相加 （ 并判其和是否為 0） ，還是將較高指數(shù)項(xiàng)的結(jié)點(diǎn)插入到新表 c中 。 3 14 2 8 1 0 ^ a Pa 8 14 3 10 10 6 ^ b Pb 11 14 3 10 2 8 1 0 ^ c Pc 10 6 + 數(shù) 據(jù) 結(jié) 構(gòu) 計(jì)算機(jī)與信息學(xué)院 劉勇 第 42頁 1. 設(shè) p,q分別指向 A,B中某一結(jié)點(diǎn)， p,q初值是第一結(jié)點(diǎn) 2. 比較 pexp與 qexp pexp qexp: p結(jié)點(diǎn)是和多項(xiàng)式中的一項(xiàng) p后移 ,q不動(dòng) pexp qexp: q結(jié)點(diǎn)是和多項(xiàng)式中的一項(xiàng) 將 q插在 p之前 ,q后移 ,p不動(dòng) pexp= =qexp: 系數(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ī)則（ 將 A， B兩多項(xiàng)式的和存儲(chǔ)在 A中 ） 數(shù) 據(jù) 結(jié) 構(gòu) 計(jì)算機(jī)與信息學(xué)院 劉勇 第 43頁 加法運(yùn)算的拓展－乘法 : 12121( ) ( ) ( )( ) ( . . . )()nieeenneiiM x A x B xA x b x b x b xb A x x??????????? ? ? ? ? ??????????? ? ?＝數(shù) 據(jù) 結(jié) 構(gòu) 計(jì)算機(jī)與信息學(xué)院 劉勇 第 44頁 本章小結(jié) 1. 線性表 邏輯結(jié)構(gòu) ： “ 一對(duì)一 ” 或 1:1 存儲(chǔ)結(jié)構(gòu) ：順序、鏈?zhǔn)? 運(yùn) 算 ：修改、插入、刪除 特征： 邏輯上相鄰，物理上 不一定 相鄰； 優(yōu)點(diǎn)： 插入刪除效率高 O(1)（ 后 ） 缺點(diǎn)： 查找慢 O(n) 特征： 邏輯上相鄰，物理上也相鄰； 優(yōu)點(diǎn)： 隨機(jī)查找快 O(1) 缺點(diǎn)： 插入、刪除慢 O(n) 有獎(jiǎng)思考題 ：在實(shí)際應(yīng)用中如何選用順序表和鏈表？ 數(shù) 據(jù) 結(jié) 構(gòu) 計(jì)算機(jī)與信息學(xué)院 劉勇 第 45頁 作業(yè) 請(qǐng)下周上課時(shí)交來！ ， ， 有獎(jiǎng)附加 第一次實(shí)驗(yàn)：第一次作業(yè)程序?qū)崿F(xiàn) ， 地點(diǎn)：電氣信息樓 2樓實(shí)驗(yàn)室
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1