一元多項式的表示

分析：多項式的關鍵數(shù)據:多項式項數(shù)n，各項系數(shù)ai 及指數(shù) i

• 方法1:順序存儲結構直接表示

利用數(shù)組存儲，數(shù)組下標表示指數(shù)i，然后數(shù)組數(shù)值表示系數(shù)ai

arr1.png

兩個多項式相加: 兩個數(shù)組對應分量相加

問題:如何表示多項式 x+3x^2000 ? 

需要創(chuàng)建2001個空間 ，內部會包含很多0 造成很多的空間浪費不合理

• 方法2:順序存儲結構表示非零項

  每個非零項 ai xi 涉及兩個信息:系數(shù) ai 和指數(shù) i
  可以將一個多項式看成是一個 (ai,i) 二元組的集合。

  
  
  arr2.png

按指數(shù)大小有序存儲!

相加過程:從頭開始，比較兩個多項式當前對應項的指數(shù)

P1: (9,12), (15,8), (3,2)

P2: (26,19), (-4,8), (-13,6), (82,0)

P3: (26,19) (9,12) (11,8) (-13,6)

實現(xiàn)了倆個多項式相加 空間也沒有造成浪費 利用結構數(shù)組存儲

• 方法3:鏈表結構存儲非零項

list.png

“線性表(Linear List)”:由同類型數(shù)據元素構成有序序列的線性結構

廣義表(Generalized List)

• 廣義表是線性表的推廣
• 對于線性表而言， n個元素都是基本的單元素;
• 廣義表中，這些元素不僅可以是單元素也可以是另一個廣義表。

多重鏈表:鏈表中的節(jié)點可能同時隸屬于多個鏈

• 多重鏈表中結點的指針域會有多個，如前面例子包含了Next和 SubList兩個指針域;
• 但包含兩個指針域的鏈表并不一定是多重鏈表，比如在雙向鏈表 不是多重鏈表。

什么是堆棧

具有一定操作約束的線性表 只在一端(棧頂，Top)做 插入、刪除

后入先出:Last In First Out(LIFO)