???♂? 個(gè)人主頁: @計(jì)算機(jī)魔術(shù)師
????? 作者簡(jiǎn)介：CSDN內(nèi)容合伙人，全棧領(lǐng)域優(yōu)質(zhì)創(chuàng)作者。
本文是浙大數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記專欄
一、問題引入 - 如何用編程表達(dá)多項(xiàng)式
這里我們引入一個(gè)問題，最常見的多項(xiàng)式，我們?nèi)绾问褂镁幊虒⒍囗?xiàng)式表示出來呢？
方法一 - 順序存儲(chǔ)結(jié)構(gòu)
我們可以使用數(shù)組來表示，但是會(huì)隨著一個(gè)問題，如下圖底部所表示的多項(xiàng)式，我們需要多大的數(shù)組來表示呢？顯然需要使用2001個(gè)數(shù)組來表示，缺只有兩項(xiàng)多項(xiàng)式，會(huì)有非常大一部分為0，會(huì)很浪費(fèi)空間
方法二- 順序存儲(chǔ)結(jié)構(gòu)表示非零項(xiàng)
這樣我們就可以只存儲(chǔ)存在的多項(xiàng)式，減少了大量空間的浪費(fèi)，那么難點(diǎn)來了，怎么進(jìn)行加減操作呢？ 要求是按指數(shù)大小有序存儲(chǔ)
我們按照次方排序，不相同時(shí)往下放，相同時(shí)系數(shù)相加即可，
方法三 - 鏈表結(jié)構(gòu)存儲(chǔ)非零項(xiàng)
我們還可以使用鏈表來實(shí)現(xiàn)，加減也是和上面的方法一樣
二、什么是線性表
2.1 抽象類型描述
（描述分為 數(shù)據(jù)對(duì)象集和操作集`）
三、 線性表的順序存儲(chǔ)實(shí)現(xiàn)
3.3 主要操作的實(shí)現(xiàn)
初始化與查找
插入（首先需要全部元素往后挪）
刪除操作
四、 線性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)
其中問題在于我們只知道一個(gè)鏈表頭，那我們?nèi)绾沃涝摼€性表的長(zhǎng)度為多少？，
4.3 主要操作的實(shí)現(xiàn)
實(shí)現(xiàn)方法是遍歷鏈表長(zhǎng)
查找 （在鏈表中查找值比數(shù)組麻煩，也需要便利鏈表）
插入
刪除操作
需要注意的是刪除第一個(gè)結(jié)點(diǎn)的操作，由于第一個(gè)結(jié)點(diǎn)沒有上一個(gè)結(jié)點(diǎn)（頭節(jié)點(diǎn)不算）所以將后面的結(jié)點(diǎn)往前挪，如果不是第一個(gè)節(jié)點(diǎn)，則將結(jié)點(diǎn)指針指向往后指向一位
五、 廣義表
為了表示二元多項(xiàng)式，我們可以將二元多項(xiàng)式看作只關(guān)于
x
x
x得一元多項(xiàng)式，如下（每個(gè)鏈表鐘第一個(gè)地址代表著參數(shù)，第二個(gè)值代表x的冪
我們使用 c語言所提供的聯(lián)合實(shí)現(xiàn)
六、多重鏈表
廣義表其實(shí)就是特殊的多重鏈表
我們看一個(gè)矩陣的例子（和之前存貯多項(xiàng)式一樣，用數(shù)組存儲(chǔ)面對(duì)非常多的系數(shù)為0時(shí)，非常浪費(fèi)空間）
我們抓住關(guān)鍵信息，構(gòu)造結(jié)點(diǎn)，其中如下，左上角的Term為入口點(diǎn)，兩個(gè)指針指向行頭結(jié)點(diǎn)和列頭結(jié)點(diǎn)， 
文章來源：http://www.zghlxwxcb.cn/news/detail-812236.html
我們便可通過聯(lián)合將非0元素與0元素合并為一個(gè)tag
文章來源地址http://www.zghlxwxcb.cn/news/detail-812236.html
?謝謝你的閱讀，您的點(diǎn)贊和收藏就是我創(chuàng)造的最大動(dòng)力！?
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu) | 入門】線性表與鏈表 （問題引入&實(shí)現(xiàn)&算法優(yōu)化）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
