多項式的表示
一元多項式及其運算
f(x)=a_0 + a_1x + a_{n-1}x^{n-1} + a_nx^n
主要運算：多項式相加、相減、相乘等

如何表示多項式？

多項式的關(guān)鍵數(shù)據(jù)

• 多項式項數(shù)n
• 各項系數(shù)a_i 和指數(shù) i

方法1：順序存儲結(jié)構(gòu)直接表示

數(shù)組各分量對應(yīng)多項式各項
比如
f(x)=4x^5 - 3x^2 +1
用兩個數(shù)組表示

image.png

第一個數(shù)組表示的是次冪
第二個數(shù)組表示的是系數(shù)

不足之處在于當(dāng)遇到x + 3x^{2000}
表示次冪的數(shù)組前面0-1999空置，很多空間被浪費

方法2：順序存儲結(jié)構(gòu)表示非零項

每個非零項涉及兩個信息：指數(shù)和系數(shù)

image.png

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

方法3：鏈表結(jié)構(gòu)存儲非零項

鏈表中的每個結(jié)點存儲多項式中的一個非零項，包括系數(shù)和指數(shù)兩個數(shù)據(jù)域以及一個指針域

鏈表存儲表示為

image.png

多項式表示問題的啟示

• 同一個問題可以有不同的表示存儲方法
• 有同一類共性問題：有序線性序列的組織和管理

線性表：由同類型數(shù)據(jù)元素構(gòu)成有序序列的線性結(jié)構(gòu)

• 表中元素個數(shù)稱為線性表的長度
• 線性表沒有元素時，稱為空表
• 表起始位置稱表頭，表結(jié)束位置稱表尾

線性表的抽象數(shù)據(jù)類型描述

類型名稱：線性表（List）

數(shù)據(jù)對象集：線性表是n(>=0)個元素構(gòu)成的有序序列(a_1,a_2 ...a_n)

操作集：線性表L屬于List，整數(shù)i表示位置，元素X屬于ElemenType

線性表基本操作主要有：

• List MakeEmpty(): 初始化一個空線性表L
• ElementType FindKth(int K,List L):根據(jù)位序K，返回相應(yīng)元素
• int Find(ElementType X,List L):在線性表L中查找X的第一次出現(xiàn)位置
• void Insert(ElementType X,int i,List L):在位序i前插入一個新元素X
• void Delete(int i,List L):刪除指定位序i的元素
• int Lenght(List L):返回線性表L的長度n

線性表的順序存儲實現(xiàn)

利用數(shù)組的連續(xù)存儲空間順序存放線性表的各元素

image.png

主要操作的實現(xiàn)

1. 初始化（建立空的順序表）

image.png

通過malloc申請結(jié)構(gòu)

image.png

把結(jié)構(gòu)的Last聲明為-1，因為Last代表的是最后一個，對應(yīng)下標(biāo)需要-1

image.png

返回結(jié)構(gòu)的指針

image.png

2. 查找

image.png

平均查找次數(shù)為(n+1)/2
平均時間性能為O(n)

3. 插入

插入到第i個位置，對應(yīng)下標(biāo)為i-1
其次，先把最后一個往后挪，依次騰出直到騰出第i個位置

image.png

image.png

p->[num]表示p指向的結(jié)構(gòu)體變量中的num成員。

4. 刪除

和插入不一樣的是
插入，是從前往后挪
刪除，從前往后挪

image.png

image.png