第二章線性表

第二章線性表線性表的概念及抽象數(shù)據(jù)類(lèi)型順序表單鏈表循環(huán)鏈表雙向鏈表應(yīng)用與比較本章目標(biāo)基于空間的考慮順序表的存儲(chǔ)空間是靜態(tài)分配的，在程序執(zhí)行之前必須明確規(guī)定它的存儲(chǔ)規(guī)模。動(dòng)態(tài)鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的，只要內(nèi)存空間尚有空閑，就不會(huì)產(chǎn)生溢出。 當(dāng)線性表的長(zhǎng)度變化較大，難以估計(jì)存儲(chǔ)規(guī)模時(shí)，采用動(dòng)態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu)較好順序表和鏈表的比較基于時(shí)間的考慮順序表可以隨機(jī)存取，對(duì)表中任一結(jié)點(diǎn)都可以在O(1)時(shí)間內(nèi)直接存??；鏈表中的結(jié)點(diǎn)需從頭指針起開(kāi)始順著鏈找才能取得。 若線性表的操作主要是進(jìn)行查找，很少做插入和刪除時(shí)，宜采用順序表存儲(chǔ)結(jié)構(gòu)順序表進(jìn)行插入、刪除時(shí)，平均要移動(dòng)表中近一半的元素；而鏈表只需要修改指針。 需要頻繁進(jìn)行插入、刪除操作的線性表，宜采用鏈表存儲(chǔ)結(jié)構(gòu)。順序表和鏈表的比較基于語(yǔ)言的考慮順序表易于操作順序表和鏈表的比較線性表鏈?zhǔn)酱鎯?chǔ)方式的比較操作名鏈表名稱(chēng)找表頭結(jié)點(diǎn)找表尾結(jié)點(diǎn)找P結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)帶頭結(jié)點(diǎn)單鏈表LL->nextO(1)一重循環(huán)O(n)順P結(jié)點(diǎn)的next域無(wú)法找到P結(jié)點(diǎn)的前驅(qū)帶頭結(jié)點(diǎn)循環(huán)單鏈表LL->nextO(1)一重循環(huán)O(n)順P結(jié)點(diǎn)的next域可以找到P結(jié)點(diǎn)的前驅(qū)：O(n)帶尾指針的循環(huán)單鏈表RR->nextO(1)RO(1)順P結(jié)點(diǎn)的next域可以找到P結(jié)點(diǎn)的前驅(qū)：O(n)帶頭結(jié)點(diǎn)雙向循環(huán)鏈表LL->nextO(1)L->priorO(1)P->priorO(1)一元多項(xiàng)式可按升冪的形式寫(xiě)成：

Pn(x)=p0+p1xe1+p2xe2+…+pnxen，其中ei為第i項(xiàng)的指數(shù)(且1≤e1≤e2≤…≤en)pi是指數(shù)ei的項(xiàng)的系數(shù)一元多項(xiàng)式的表示及相加一元多項(xiàng)式的順序存儲(chǔ)表示(兩種方法)一元多項(xiàng)式的鏈?zhǔn)酱鎯?chǔ)表示一元多項(xiàng)式的存儲(chǔ)一元多項(xiàng)式的順序存儲(chǔ)表示—方法1只存儲(chǔ)該一元多項(xiàng)式各項(xiàng)的系數(shù)，每個(gè)系數(shù)所對(duì)應(yīng)的指數(shù)項(xiàng)則隱含在存儲(chǔ)系數(shù)的順序表的下標(biāo)中。如：B(x)=8x+22x7-9x8一元多項(xiàng)式的存儲(chǔ)值080000022-9下標(biāo)012345678一元多項(xiàng)式的順序存儲(chǔ)表示—方法1采用這種存儲(chǔ)方法使得多項(xiàng)式的相加運(yùn)算的算法定義十分簡(jiǎn)單，只需將下標(biāo)相同的單元的內(nèi)容相加即可。缺點(diǎn)：若多項(xiàng)式的非零項(xiàng)指數(shù)很高但非零項(xiàng)很少時(shí)，十分浪費(fèi)存儲(chǔ)空間，如：

R(x)=1+5x10000+7x20000一元多項(xiàng)式的存儲(chǔ)一元多項(xiàng)式的順序存儲(chǔ)表示—方法2只存儲(chǔ)非零項(xiàng)，此時(shí)每個(gè)非零項(xiàng)需要存儲(chǔ)：非零項(xiàng)系數(shù)非零項(xiàng)指數(shù)如：B(x)=8x+22x7-9x8

一元多項(xiàng)式的存儲(chǔ)

值系數(shù)822－9指數(shù)178下標(biāo)012一元多項(xiàng)式的鏈?zhǔn)酱鎯?chǔ)表示只存非零項(xiàng)，每一非零項(xiàng)由兩部分構(gòu)成（指數(shù)項(xiàng)和系數(shù)項(xiàng)）一元多項(xiàng)式的存儲(chǔ)系數(shù)coef

指數(shù)exp指針next一元多項(xiàng)式的鏈?zhǔn)酱鎯?chǔ)表示一元多項(xiàng)式的單鏈表表示示意圖一元多項(xiàng)式的存儲(chǔ)

A(x)=7+3x+9x8+5x17-17031517∧9881-1227-98∧

B(x)=8x+22x7-9x8

建立一元多項(xiàng)式鏈?zhǔn)酱鎯?chǔ)的算法算法思想通過(guò)鍵盤(pán)輸入一組多項(xiàng)式的系數(shù)和指數(shù)，用尾插法建立一元多項(xiàng)式的鏈表;以輸入系數(shù)0為結(jié)束標(biāo)志;并約定建立多項(xiàng)式鏈表時(shí)，總是按指數(shù)從小到大的順序排列。一元多項(xiàng)式的存儲(chǔ)兩個(gè)一元多項(xiàng)式相加運(yùn)算規(guī)則：兩個(gè)多項(xiàng)式中所有指數(shù)相同的項(xiàng)的對(duì)應(yīng)系數(shù)相加，若和不為零，則構(gòu)成“和多項(xiàng)式”中的一項(xiàng)；所有指數(shù)不相同的項(xiàng)均復(fù)抄到“和多項(xiàng)式”中。一元多項(xiàng)式的存儲(chǔ)-17031517∧9881-1227-98∧

polyapolyb-170111517∧227兩個(gè)一元多項(xiàng)式相加一元多項(xiàng)式的存儲(chǔ)-17031517∧9881-1227-98∧

polyapolybpqtail兩個(gè)一元多項(xiàng)式相加若p->exp<q->exp，則結(jié)點(diǎn)p所指的結(jié)點(diǎn)應(yīng)是“和多項(xiàng)式”中的一項(xiàng)，令指針p后移；若p->exp>q->exp，則結(jié)點(diǎn)q所指的結(jié)點(diǎn)應(yīng)是“和多項(xiàng)式”中的一項(xiàng)，將結(jié)點(diǎn)q插入在結(jié)點(diǎn)p之前，且令指針q在原來(lái)的鏈表上后移；若p->exp==q->exp，則將兩個(gè)結(jié)點(diǎn)中的系數(shù)相加，當(dāng)和不為零時(shí)修改結(jié)點(diǎn)p的系數(shù)域，釋放q結(jié)點(diǎn)；若和為零，則和多項(xiàng)式中無(wú)此項(xiàng)，從A中刪去p結(jié)點(diǎn)，同時(shí)釋放p和q結(jié)點(diǎn)。一元多項(xiàng)式的存儲(chǔ)兩個(gè)一元多項(xiàng)式相加一元多項(xiàng)式的存儲(chǔ)-17031517∧9881-1227-98∧

polyapolybpqtail兩個(gè)一元多項(xiàng)式相加一元多項(xiàng)式的存儲(chǔ)-17031517∧98-1227-98∧

81polyapolybpqtail11temp兩個(gè)一元多項(xiàng)式相加一元多項(xiàng)式的存儲(chǔ)-170111517∧98-1227-98∧

polyapolybpqtailtail兩個(gè)一元多項(xiàng)式相加一元多項(xiàng)式的存儲(chǔ)-170111517∧98-1227-98∧

polyapolybpqtailtemptemp兩個(gè)一元多項(xiàng)式相加一元多項(xiàng)式的存儲(chǔ)-170111517∧-1227polyapolybpqtail多項(xiàng)式深度拷貝及應(yīng)用比較兩個(gè)多項(xiàng)式是否相等//比較兩個(gè)多項(xiàng)式是否相等publicboolean

equals(Object

obj){ returnthis==obj||obj

instanceofPolynomia