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