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

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

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

一元多項式的存儲

值系數822－9指數178下標012一元多項式的鏈式存儲表示只存非零項，每一非零項由兩部分構成（指數項和系數項）一元多項式的存儲系數coef

指數exp指針next一元多項式的鏈式存儲表示一元多項式的單鏈表表示示意圖一元多項式的存儲

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

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

建立一元多項式鏈式存儲的算法算法思想通過鍵盤輸入一組多項式的系數和指數，用尾插法建立一元多項式的鏈表;以輸入系數0為結束標志;并約定建立多項式鏈表時，總是按指數從小到大的順序排列。一元多項式的存儲兩個一元多項式相加運算規則：兩個多項式中所有指數相同的項的對應系數相加，若和不為零，則構成“和多項式”中的一項；所有指數不相同的項均復抄到“和多項式”中。一元多項式的存儲-17031517∧9881-1227-98∧

polyapolyb-170111517∧227兩個一元多項式相加一元多項式的存儲-17031517∧9881-1227-98∧

polyapolybpqtail兩個一元多項式相加若p->exp<q->exp，則結點p所指的結點應是“和多項式”中的一項，令指針p后移；若p->exp>q->exp，則結點q所指的結點應是“和多項式”中的一項，將結點q插入在結點p之前，且令指針q在原來的鏈表上后移；若p->exp==q->exp，則將兩個結點中的系數相加，當和不為零時修改結點p的系數域，釋放q結點；若和為零，則和多項式中無此項，從A中刪去p結點，同時釋放p和q結點。一元多項式的存儲兩個一元多項式相加一元多項式的存儲-17031517∧9881-1227-98∧

polyapolybpqtail兩個一元多項式相加一元多項式的存儲-17031517∧98-1227-98∧

81polyapolybpqtail11temp兩個一元多項式相加一元多項式的存儲-170111517∧98-1227-98∧

polyapolybpqtailtail兩個一元多項式相加一元多項式的存儲-170111517∧98-1227-98∧

polyapolybpqtailtemptemp兩個一元多項式相加一元多項式的存儲-170111517∧-1227polyapolybpqtail多項式深度拷貝及應用比較兩個多項式是否相等//比較兩個多項式是否相等publicboolean

equals(Object

obj){ returnthis==obj||obj

instanceofPolynomia