數(shù)據(jù)結(jié)構(gòu)(C)第2章線性表.ppt

1、NCU-ZQP,1,第2章 線性表,第1章介紹了幾種基本邏輯結(jié)構(gòu)：線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖結(jié)構(gòu)。線性結(jié)構(gòu)是最簡(jiǎn)單、最基本的數(shù)據(jù)結(jié)構(gòu)，本章討論線性表的基本概念、存儲(chǔ)結(jié)構(gòu)以及相關(guān)運(yùn)算。 主要內(nèi)容： 線性表的基本概念 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 線性表的鏈表存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 線性表的應(yīng)用,NCU-ZQP,2,2.1 線性表的基本概念,現(xiàn)實(shí)中存在大量線性表的實(shí)例。例如： 大寫英文字母表：(A,B,C,Y,Z)； 一周中7天(星期一，星期二，星期日)； MP3播放器中的若干個(gè)歌曲的目錄。怎樣查找自己喜歡的歌曲？怎樣輸入新的曲目？刪除過(guò)時(shí)曲目？這就是本節(jié)所研究的內(nèi)容：線性表及其運(yùn)算。,NCU-ZQP,3,2.

2、1.1 線性表的定義,線性表（Linear List）是n(n0)個(gè)數(shù)據(jù)元素的有限序列。記作：(a1，a2，an) ai(1in)屬于同一數(shù)據(jù)對(duì)象，具有相同的數(shù)據(jù)類型。 n代表表長(zhǎng)，即線性表中數(shù)據(jù)元素的個(gè)數(shù)。 當(dāng)n=0時(shí)，線性表為空表。 對(duì)于ai: 當(dāng)1in時(shí)，它有一個(gè)直接前驅(qū)ai1 ； 當(dāng)1in時(shí)，它有一個(gè)直接后繼ai+1 。,NCU-ZQP,4,2.1.2 線性表的抽象數(shù)據(jù)類型,ADT Linear_list 數(shù)據(jù)對(duì)象：D=ai | ai ElemSet , i=1,2,n, n0 ； 數(shù)據(jù)關(guān)系：R= | ai-1 ,aiD, i=2,3, ,n 基本操作：初始化空線性表; 求線性表表長(zhǎng);

3、 取線性表的第i個(gè)元素; 在線性表的第i個(gè)位置插入元素x; 刪除線性表的第i個(gè)元素; 修改線性表中的第i個(gè)元素; 按某種要求重排線性表中各元素的順序; 按某個(gè)特定值查找線性表中的元素; 等等; ADT Linear_list;,NCU-ZQP,5,2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn),為了用計(jì)算機(jī)解決線性表問題，需要考慮數(shù)據(jù)信息如何在計(jì)算機(jī)內(nèi)存儲(chǔ)。計(jì)算機(jī)可以用多種不同的方法來(lái)存儲(chǔ)數(shù)據(jù)信息，常用的方法是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。,NCU-ZQP,6,2.2.1 線性表的順序存儲(chǔ)結(jié)構(gòu),順序存儲(chǔ)結(jié)構(gòu)是最簡(jiǎn)單常用的方法。順序存儲(chǔ)結(jié)構(gòu)也稱為向量存儲(chǔ)。向量是內(nèi)存中一批地址連續(xù)的存儲(chǔ)單元。 線性表的順序存儲(chǔ)

4、結(jié)構(gòu)，要求邏輯上相鄰的數(shù)據(jù)元素在物理位置上也一定是相鄰的，如圖所示。,NCU-ZQP,7,假設(shè)a1的地址為L(zhǎng)OC(a1)，每個(gè)元素占L個(gè)字節(jié)（本例L為2），ai的存放地址為： LOC(ai)=LOC(a1)+L*(i1) 只要確定了線性表存儲(chǔ)的起始位置，線性表中任一數(shù)據(jù)元素的位置都可確定，可以隨機(jī)存取。,特點(diǎn)：邏輯上相鄰物理地址相鄰； 可以隨機(jī)存取數(shù)據(jù)；,NCU-ZQP,8,為了更好地體現(xiàn)信息隱蔽原則以及數(shù)據(jù)抽象原則，一維數(shù)組elem和線性表的長(zhǎng)度length封裝在一個(gè)結(jié)構(gòu)體中。 const int MAXSIZE=100; typedef int ElemType ; struct SqLi

5、st0 ElemType elemMAXSIZE; /一維數(shù)組 int length ; /表的實(shí)際長(zhǎng)度 SqList0就是順序存儲(chǔ)結(jié)構(gòu)的類型標(biāo)識(shí)符。,在高級(jí)語(yǔ)言環(huán)境中使用一維數(shù)組來(lái)模擬實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)。,NCU-ZQP,9,1在類中使用靜態(tài)一維數(shù)組 靜態(tài)一維數(shù)組是指在聲明定義數(shù)組時(shí)，所給出數(shù)組的大小是確定的。數(shù)組的大小留有余地。 const int MAXSIZE=100; typedef int ElemType ; class SqList1 private: ElemType elemMAXSIZE; /一維數(shù)組 int length ; /線性表長(zhǎng)度 public: ;/其他成員函數(shù)

6、; ；,在面向?qū)ο蟮某绦蛟O(shè)計(jì)中，通常將數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)和對(duì)數(shù)據(jù)的操作封裝在一個(gè)類之中。,NCU-ZQP,10,2在類中使用動(dòng)態(tài)一維數(shù)組 動(dòng)態(tài)一維數(shù)組是指在聲明定義數(shù)組時(shí)用指針表示，數(shù)組的大小沒有確定。在數(shù)據(jù)成員中除數(shù)組elem、表長(zhǎng)length還給出表的容量maxlen。 class SqList2 private: ElemType *elem； /用指針表示一維數(shù)組 int length ; /表的實(shí)際長(zhǎng)度 int maxlen; /表的最大長(zhǎng)度，容量 public: ; /其他成員函數(shù) ;,在面向?qū)ο蟮某绦蛟O(shè)計(jì)中，通常將數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)和對(duì)數(shù)據(jù)的操作封裝在一個(gè)類之中。,NCU-ZQP

7、,11,2.2.2 順序表類定義,順序表類是指采用順序存儲(chǔ)結(jié)構(gòu)來(lái)表示線性表的類。 線性表采用順序存儲(chǔ)結(jié)構(gòu)，其數(shù)組和線性表長(zhǎng)可以作為類的數(shù)據(jù)成員。線性表各種操作的處理可以作為類的函數(shù)成員，且大多是公有函數(shù)，目的是提供類對(duì)外部的接口供調(diào)用。 一個(gè)簡(jiǎn)明的順序表類：SqList。,NCU-ZQP,12,/順序表類SqList的定義 typedef int ElemType; /數(shù)據(jù)元素的類型 const int MAXSIZE=100; /數(shù)組的容量 class SqList private: ElemType elemMAXSIZE; /數(shù)組 int length; /線性表長(zhǎng) public: Sq

8、List( void); /構(gòu)造函數(shù) SqList() ; /析構(gòu)函數(shù) void Creat() ; /初建一個(gè)簡(jiǎn)表函數(shù) void PrintOut(); /輸出線性表函數(shù) void Insert( int i, ElemType e); /插入函數(shù) ElemType Delet(int i); /刪除函數(shù) ;/類定義結(jié)束,NCU-ZQP,13,SqList:SqList() length=0; /構(gòu)造函數(shù)，構(gòu)造空表 void SqList:Creat() /建立一個(gè)簡(jiǎn)表函數(shù) coutlength; coutelemk; void SqList:PrintOut() /輸出線性表函數(shù) cout

9、n length=length ; coutn PrintOut Data:n ; for(int k=0; klength;k+) coutsetw(6)elemk; coutendl; 這兩個(gè)函數(shù)主要是為上機(jī)實(shí)驗(yàn)提供方便。從“數(shù)據(jù)結(jié)構(gòu)”課程的角度看，線性表的主要操作是插入、刪除等，這些重要算法將在下文詳細(xì)介紹。,NCU-ZQP,14,2.2.3 順序表的插入和刪除,1順序表的插入 插入操作是在線性表的第i1個(gè)數(shù)據(jù)元素和第i個(gè)數(shù)據(jù)元素之間插入一個(gè)新的數(shù)據(jù)元素e。使長(zhǎng)度為n的線性表： (a1, ，ai-1, ai，an) 變成長(zhǎng)度為n+1的線性表： (a1, ，ai-1,e，ai，an) 先把

10、元素an，an1，ai向后各自移動(dòng)一個(gè)位置，然后將e插在第i個(gè)位置上。 注意插入位置i取值的正確范圍，從邏輯上講是： 1=i=length+1 由于C/C+的數(shù)組下標(biāo)從零開始，在程序中位置的正確范圍變換為： 0=i1=length,NCU-ZQP,15,順序表的插入,有一線性表（11，23，35，46，57，67，78，89），要求在第4個(gè)位置（下標(biāo)為3）插入一個(gè)值為38的數(shù)據(jù)。,NCU-ZQP,16,順序表的插入算法-算法2.1,void SqList:Insert( int i, ElemType e) int j; i-; /邏輯位置換算為C+數(shù)組下標(biāo)值 if(ilength) cout

11、i; j-) elemj=elemj-1; /移動(dòng)元素 elemi=e; /插入元素 length+; /線性表長(zhǎng)加1 算法采用SqList類的成員函數(shù)來(lái)表示。默認(rèn)線性表已經(jīng)存在。插入位置i和插入元素值e是已知條件。,NCU-ZQP,17,2順序表的刪除,刪除線性表中的第i個(gè)元素ai，需把元素ai+1， an分別向前移動(dòng)一個(gè)位置。對(duì)于長(zhǎng)度為n的線性表： (a1, ，ai1,ai，an) 變成長(zhǎng)度為n1的線性表： (a1,，ai-1,ai+1，an) 刪除位置i的合理取值： 1=i=length 算法中假設(shè)a1存放在elem0中。在程序中位置i的正確范圍是： 0=i1=length1,NCU-Z

12、QP,18,順序表的刪除,有一線性表（11，23，35，46，57，67，78，89），要求刪除在第4個(gè)（下標(biāo)為3）數(shù)據(jù)元素。,11 23 35 46 57 67 78 89,11 23 35 57 67 78 89,下標(biāo) 0 1 2 3 4 5 6 7,NCU-ZQP,19,順序表的刪除算法-算法2.1,ElemType SqList:Delet(int i) ElemType x; int j; i-; /轉(zhuǎn)換成C+數(shù)組下標(biāo) if(ilength-1) cout i Error!endl; x=-1; /判斷刪除位置 else x=elemi; for(j=i; jlength-1; j+

13、) elemj=elemj+1; /向前移動(dòng)數(shù)據(jù)元素 length-; /線性表長(zhǎng)減1 return x; 算法默認(rèn)線性表已經(jīng)存在。刪除元素的位置i是已知條件。 本函數(shù)具有返回值，就是被刪除的數(shù)據(jù)元素值。,NCU-ZQP,20,用順序表的類對(duì)象，調(diào)用線性表的插入和刪除算法,int main() int i; ElemType e,x; SqList as; /聲明創(chuàng)建一個(gè)類對(duì)象as as.Creat(); /輸入數(shù)據(jù)建立線性表 coutie; as.Insert(i,e); /調(diào)用插入算法函數(shù) as.PrintOut(); couti; x=as.Delet(i); /調(diào)用刪除算法函數(shù) cou

14、tn 元素?cái)?shù)值= x; as.PrintOut() _getch(); return 0; ,NCU-ZQP,21,3插入和刪除算法的時(shí)間復(fù)雜度分析,在順序存儲(chǔ)結(jié)構(gòu)的線性表中某個(gè)位置上插入或刪除一個(gè)數(shù)據(jù)元素時(shí)，其時(shí)間主要耗費(fèi)在數(shù)據(jù)元素的移動(dòng)上。而移動(dòng)元素的次數(shù)取決于插入或刪除元素的位置。 算法由于插入（或刪除）的位置不同，移動(dòng)元素的次數(shù)也不同，在分析算法時(shí)采用移動(dòng)元素次數(shù)的平均值，來(lái)估算時(shí)間復(fù)雜度。,NCU-ZQP,22,插入算法的平均移動(dòng)次數(shù)分析,假設(shè)Pi是在第i個(gè)元素之前插入一個(gè)元素的概率（可能性），ni+1是在第i個(gè)元素之前插入一個(gè)元素所需移動(dòng)元素的次數(shù)。 在插入時(shí)，i的取值范圍是1到n

15、+1。在長(zhǎng)度為n的線性表中插入一個(gè)元素時(shí)所需移動(dòng)元素次數(shù)的平均次數(shù)為：,NCU-ZQP,23,插入算法的平均移動(dòng)次數(shù)分析,假設(shè)在任何位置插入元素的概率pi相等（暫不考慮概率不相等情況）：,元素插入位置的可能值為： i=1,2, n, n+1 相應(yīng)向后移動(dòng)元素次數(shù)為： ( ni+1)=n,n1, 1,0 對(duì)其求總和，為n(n+1)/2。 所以插入時(shí)，數(shù)據(jù)元素平均移動(dòng)次數(shù)為：,NCU-ZQP,24,刪除算法的平均移動(dòng)次數(shù)分析,假設(shè)qi是刪除第i個(gè)元素的概率，ni是刪除第i個(gè)元素所需移動(dòng)元素的次數(shù)。 在刪除時(shí)，i的取值范圍是1到n。 則在長(zhǎng)度為n的線性表中刪除一個(gè)元素時(shí)所需移動(dòng)元次數(shù)的平均次數(shù)為：,

16、NCU-ZQP,25,刪除算法的平均移動(dòng)次數(shù)分析,假設(shè)在線性表的任何位置刪除元素的概率qi相等（暫不考慮概率不相等情況）:,元素刪除位置的可能值： i=1,2,n 相應(yīng)向前移動(dòng)元素次數(shù)： ni=n1,n-2,0 對(duì)n1,1,0求總和，顯然為n(n1)/2，則刪除時(shí)數(shù)據(jù)元素平均移動(dòng)次數(shù)為：,NCU-ZQP,26,插入和刪除算法的時(shí)間復(fù)雜度分析,在順序表中插入或刪除一個(gè)元素時(shí)，平均移動(dòng)表中大約一半的數(shù)據(jù)元素。根據(jù)上述兩式( n/2 和 (n-1)/2)，忽略常數(shù)項(xiàng)以及常系數(shù)。若表長(zhǎng)為n，則兩個(gè)算法的時(shí)間復(fù)雜度都為：T(n)=O(n)。,NCU-ZQP,27,2.2.4 線性表的其他運(yùn)算,除前面兩種

17、基本運(yùn)算外，還有一些較復(fù)雜的運(yùn)算。 class SqList /代碼與前文類Sqlist的定義完全同前； public: /以下是增加的兩個(gè)公有函數(shù)成員 void Insertdz( ElemType x); /有序表插入 void Deletaz(ElemType x); /有序表刪除 ;,NCU-ZQP,28,1在非遞減有序表中插入一個(gè)數(shù)據(jù)元素x，使線性表仍保持非遞減有序。,前提是線性表中數(shù)據(jù)元素已經(jīng)有序。已知條件是將要插入的數(shù)據(jù)x，插入的位置需要程序來(lái)查找。 已知有線性表：（14，21，21，38，46，80） 若x=30，結(jié)果：（14，21，21，30，38，46，80） 若x=10，

18、結(jié)果：（10，14，21，21，38，46，80） 若x=99，結(jié)果：（14，21，21，38，46，80，99） 因插入的數(shù)據(jù)元素x值不同其插入位置也不同。插入位置怎樣確定？,NCU-ZQP,29,1在非遞減有序表中插入一個(gè)數(shù)據(jù)元素x，使線性表仍保持非遞減有序。,算法2.3 void SqList:Insertdz( ElemType x) int i=length-1; while(i=0 算法從表尾元素開始與x比較，當(dāng)elemix且未到表頭元素時(shí)繼續(xù)循環(huán)。一邊比較一邊向后移動(dòng)數(shù)據(jù)元素。 算法的主要考慮數(shù)據(jù)元素的移動(dòng)，時(shí)間復(fù)雜度為O(n)。 若采用從表頭元素開始與x比較的方法，其效率如何？

19、,NCU-ZQP,30,2在非遞減有序表中刪除所有值為x的元素。,已知條件是某數(shù)據(jù)元素x的值。以elemi與x是否相等為判斷條件來(lái)查找刪除的位置，然后刪除所有值為x的元素。 算法2.4 void SqList:Deletaz(ElemType x) int i=0,j; /查找第一個(gè)x值出現(xiàn)的位置 while(ilength /表長(zhǎng)減1 ,NCU-ZQP,31,刪除非遞減有序表中所有值為x的元素，算法分析,本算法含有兩個(gè)并列的循環(huán)結(jié)構(gòu)，由于影響時(shí)間效率的主要因素是大量數(shù)據(jù)元素的移動(dòng)，因此前面關(guān)于下標(biāo)i的循環(huán)忽略不計(jì)。 else中是一個(gè)二重循環(huán)，如果忽略x重復(fù)出現(xiàn)的次數(shù)，主要依據(jù)是移動(dòng)數(shù)據(jù)元素的

20、for循環(huán)，經(jīng)估算元素的平均移動(dòng)次為(n1)/2，因此算法的時(shí)間復(fù)雜度是O(n)。 綜上所述，線性表采用順序存儲(chǔ)結(jié)構(gòu)在插入、刪除時(shí)，需大量移動(dòng)數(shù)據(jù)元素，效率較低。由于是靜態(tài)存儲(chǔ)結(jié)構(gòu)，需預(yù)先定義大小確定的數(shù)組，容量有限。,NCU-ZQP,32,2.3 線性表的鏈表存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn),采用順序存儲(chǔ)結(jié)構(gòu)的線性表，在頻繁進(jìn)行插入、刪除操作時(shí)會(huì)大量移動(dòng)數(shù)據(jù)元素，效率較低。同時(shí)，順序存儲(chǔ)必須占用一批地址連續(xù)的存儲(chǔ)空間，存儲(chǔ)分配只能預(yù)先進(jìn)行。但是，它適于直接（隨機(jī)）存取操作。 本節(jié)將討論線性表的另一種存儲(chǔ)結(jié)構(gòu)鏈表存儲(chǔ)結(jié)構(gòu)，由于它不要求邏輯上相鄰的數(shù)據(jù)元素在物理位置上也一定相鄰，因此，它沒有順序存儲(chǔ)結(jié)構(gòu)所具有的弱

21、點(diǎn)。,NCU-ZQP,33,2.3.1單鏈表與指針,對(duì)于程序設(shè)計(jì)基礎(chǔ)較好的讀者，可以越過(guò)本節(jié)直接學(xué)習(xí)2.3.2節(jié)。 線性表的鏈表存儲(chǔ)結(jié)構(gòu)可以利用內(nèi)存空間中一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)線性表的各個(gè)數(shù)據(jù)元素，這些存儲(chǔ)單元地址可以連續(xù)也可不連續(xù)。那么怎樣根據(jù)第i個(gè)數(shù)據(jù)元素找到第i+1個(gè)數(shù)據(jù)元素呢？ 為了弄清單鏈表的概念，首先需回顧指針的基本概念。,NCU-ZQP,34,1指針和指針變量,所謂指針是指計(jì)算機(jī)內(nèi)某個(gè)存儲(chǔ)單元的地址。 一個(gè)用來(lái)存放指針（地址）的獨(dú)立變量稱作指針變量。 如果有：int *a; int m=6; 就允許：a= 那么name指針就是該字符串的首地址。 雖然指針變量可以存放存變量單元的

22、地址，但是根據(jù)其數(shù)據(jù)類型聲明的不同，其地址性質(zhì)是不同的。,NCU-ZQP,35,在存儲(chǔ)和表示線性表時(shí)，一個(gè)結(jié)點(diǎn)用來(lái)存儲(chǔ)線性表的一個(gè)數(shù)據(jù)元素。 每個(gè)結(jié)點(diǎn)一般分為兩個(gè)域：數(shù)據(jù)域；指針域。 一個(gè)結(jié)點(diǎn)定義為結(jié)構(gòu)體類型： typedef int ElemType; struct NodeType ElemType data; /數(shù)據(jù)域，存放數(shù)據(jù)信息 NodeType *next; /指針域，存放同樣結(jié)構(gòu)體類型結(jié)點(diǎn)的首地址 ;,2結(jié)點(diǎn),NCU-ZQP,36,對(duì)結(jié)點(diǎn)的訪問和處理常通過(guò)指針變量。 用來(lái)存放結(jié)點(diǎn)首地址的指針變量，可用下列語(yǔ)句來(lái)聲明： NodeType *h,*s; 變量h,s被定義為指針型之后，

23、并沒有指向任何實(shí)際結(jié)點(diǎn)，即指針變量中還沒有某個(gè)實(shí)際結(jié)點(diǎn)所占空間的首地址值。 如何為指針變量提供一個(gè)結(jié)點(diǎn)的首地址？,2結(jié)點(diǎn),NCU-ZQP,37,讓指針變量p指向一個(gè)新分配的結(jié)點(diǎn)，語(yǔ)句如下： p = new NodeType; 系統(tǒng)分配了一個(gè)結(jié)點(diǎn)所需的存儲(chǔ)空間，并且將首地址賦值給指針變量p。 可以通過(guò)賦值語(yǔ)句： s=p； 讓指針變量s存放與p指針之中相同的地址，也稱s和p指向同一個(gè)結(jié)點(diǎn)，如圖所示。,3結(jié)點(diǎn)的動(dòng)態(tài)申請(qǐng)和釋放,NCU-ZQP,38,結(jié)點(diǎn)s的數(shù)據(jù)域用s-data來(lái)表示，根據(jù)前文定義的數(shù)據(jù)域是整型的，像一般的整型變量一樣可以在輸入/輸出、賦值語(yǔ)句中使用。例如： s-data=110; /

24、或者cins-data; coutdata; /這樣輸出的結(jié)果就是110 結(jié)點(diǎn)s的指針域用s-next來(lái)表示，可以用來(lái)存放另外一個(gè)結(jié)點(diǎn)的首地址。根據(jù)需要也可以使其為空，如： s-next=NULL；,3結(jié)點(diǎn)的動(dòng)態(tài)申請(qǐng)和釋放,NCU-ZQP,39,要把上述結(jié)點(diǎn)s釋放、歸還給系統(tǒng)，則必須用命令來(lái)實(shí)現(xiàn)： delete s; 值得注意的是，這里釋放的只是數(shù)據(jù)元素結(jié)點(diǎn)所占用結(jié)點(diǎn)的存儲(chǔ)單元，而指針變量h,s本身仍然存在，只是h,s之中不再有具體地址內(nèi)容，什么結(jié)點(diǎn)也不指向了。,3結(jié)點(diǎn)的動(dòng)態(tài)申請(qǐng)和釋放,NCU-ZQP,40,多個(gè)結(jié)點(diǎn)連接在一起可以構(gòu)成一個(gè)鏈表。由于每個(gè)結(jié)點(diǎn)只包含一個(gè)指針域，故稱這種鏈表為單鏈表

25、。一個(gè)非空線性表(a1，a2，a3)對(duì)應(yīng)的單鏈表如圖所示。,4鏈表,詳細(xì)講解,NCU-ZQP,41,5指針變量的主要操作,詳細(xì)講解,NCU-ZQP,42,2.3.2 單鏈表類定義,在面向?qū)ο蟮某绦蛟O(shè)計(jì)中，鏈表被設(shè)計(jì)成一個(gè)類。鏈表類在不同教科書有不同的設(shè)計(jì)。 鏈表有一種簡(jiǎn)明的設(shè)計(jì)，將結(jié)點(diǎn)設(shè)計(jì)為一個(gè)結(jié)構(gòu)體類型，再將該鏈表的頭指針Head作為鏈表類的數(shù)據(jù)成員。 結(jié)點(diǎn)結(jié)構(gòu)的定義： typedef int ElemType; struct NodeType /結(jié)點(diǎn)類型定義 ElemType data; NodeType *next; ;,NCU-ZQP,43,頭指針Head可唯一確地定一個(gè)單鏈表。,對(duì)鏈

26、表中各數(shù)據(jù)結(jié)點(diǎn)的訪問都將從頭指針Head開始查找。 將一個(gè)NodeType類型結(jié)點(diǎn)的指針變量Head作為單鏈表的頭指針。 單鏈表類的組成： 將頭指針Head作為類LinkList的私有數(shù)據(jù)成員； 將重要的算法設(shè)計(jì)成類的若干成員函數(shù)。,NCU-ZQP,44,/鏈表類定義 class LinkList private: NodeType *Head; /鏈表頭指針 public: LinkList(); /構(gòu)造函數(shù)，初始化空鏈表 LinkList(); /析構(gòu)函數(shù) void creat(); /初建一個(gè)非空鏈表 void Display(); /輸出鏈表的數(shù)據(jù)元素 void insert(int

27、i,ElemType x);/插入 ElemType delet(int i ); /刪除第i個(gè)結(jié)點(diǎn) ;/類定義結(jié)束,NCU-ZQP,45,LinkList:LinkList() /創(chuàng)建一個(gè)空鏈表，有一個(gè)頭結(jié)點(diǎn) Head=new NodeType; Head-next=NULL; Head-data=0; coutnext; /p 指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn) while(p!=NULL) /循環(huán)釋放鏈表的數(shù)據(jù)結(jié)點(diǎn) Head-next=p-next; delete p; p=Head-next; coutn 鏈表已經(jīng)刪除。endl; delete Head; /最后釋放頭結(jié)點(diǎn)的空間 Head=NULL;

28、 ,NCU-ZQP,46,算法2.5 void LinkList:creat() /輸入建立一個(gè)鏈表 NodeType *s; ElemType x; Coutx; /先輸入數(shù)據(jù)：an-1 while(x!=-999) s=new NodeType; s-data=x; s-next=Head-next; /Head為頭結(jié)點(diǎn)的指針 Head-next=s; coutx; /逐個(gè)輸入 an -2,a0 coutn 插入結(jié)束。鏈表建成。endl; ,NCU-ZQP,47,/輸出顯示鏈表內(nèi)容 void LinkList:Display() NodeType *p; p=Head-next; /p指向

29、第一個(gè)數(shù)據(jù)結(jié)點(diǎn) while(p!=NULL) coutdatanext; /p移向下一個(gè)結(jié)點(diǎn) coutendl; /p為空，輸出完畢 頭指針Head必須保持不變，需另設(shè)一個(gè)指針變量p從第一個(gè)數(shù)據(jù)結(jié)點(diǎn)向后逐步移動(dòng)，邊輸出邊移動(dòng)p直至表尾。,NCU-ZQP,48,上述函數(shù)不是單鏈表的典型算法，之所以列出是為了配合典型算法，構(gòu)成體系比較完整的類設(shè)計(jì)。 為了在實(shí)際中應(yīng)用單鏈表，還必須能夠?qū)⑺惴ê秃瘮?shù)放在程序系統(tǒng)中去認(rèn)識(shí)和設(shè)計(jì)編碼。 在主函數(shù)中聲明和創(chuàng)建LinkList鏈表類對(duì)象h，同時(shí)初始化h為空鏈表。然后調(diào)用建立鏈表的函數(shù)輸入數(shù)據(jù)，接著調(diào)用輸出函數(shù)將鏈表內(nèi)容輸出顯示。 int main( ) Lin

30、kList h; h.creat(); /通過(guò)對(duì)象h調(diào)用建立函數(shù) h.Display(); /通過(guò)對(duì)象h調(diào)用輸出函數(shù) _getch(); return 0; ,NCU-ZQP,49,2.3.3 鏈表的插入和刪除,為了規(guī)范單鏈表的表示和運(yùn)算，約定使用附加頭結(jié)點(diǎn)，在一般情況下均默認(rèn)帶有附加頭結(jié)點(diǎn)，簡(jiǎn)稱頭結(jié)點(diǎn)。所謂頭結(jié)點(diǎn)是指該結(jié)點(diǎn)的數(shù)據(jù)域并不存放線性表的任何數(shù)據(jù)元素，一個(gè)空表如左圖，非空鏈表如右圖。,單鏈表是數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)的重要基礎(chǔ)。下面從最基本的插入、刪除的語(yǔ)句組和圖示入手，介紹鏈表類的插入和刪除算法。,NCU-ZQP,50,1插入,在討論插入算法前，首先看單鏈表中插入結(jié)點(diǎn)的基本操作。 （1）假設(shè)已

31、知p指針指向的結(jié)點(diǎn)，在p結(jié)點(diǎn)之后插入一個(gè)元素x，操作如圖2.8所示。,相關(guān)操作的語(yǔ)句組如下： s=new NodeType; /分配新的結(jié)點(diǎn)s s-data=x; s-next=p-next; /插入s結(jié)點(diǎn) p-next=s; /注意，兩條修改指針的語(yǔ)句順序不可顛倒。,NCU-ZQP,51,（2）在p指針?biāo)赶虻慕Y(jié)點(diǎn)前插入一個(gè)元素，操作如圖所示。 若在p前插入需先找出p前驅(qū)結(jié)點(diǎn)地址。另設(shè)一指針q，從鏈表的頭結(jié)點(diǎn)head開始向后移動(dòng)進(jìn)行查找，直到q指向p的前驅(qū)結(jié)點(diǎn)為止。然后在q結(jié)點(diǎn)之后，p結(jié)點(diǎn)之前進(jìn)行插入。 語(yǔ)句組如下： q=head; while(q-next!=p) q=q-next; /查

32、找p前驅(qū)結(jié)點(diǎn) s=new NodeType; s-data=x; s-next=p; q-next=s; /插入s結(jié)點(diǎn) /在已知結(jié)點(diǎn)的“前”邊進(jìn)行插入的操作較為復(fù)雜。,NCU-ZQP,52,（3）在已知的線性表的第i個(gè)位置插入數(shù)據(jù)元素x。,，在此作為鏈表類的公有成員函數(shù)來(lái)實(shí)現(xiàn)。在線性表的第i個(gè)位置進(jìn)行插入，是指鏈表中有效數(shù)據(jù)元素結(jié)點(diǎn)的位置，頭結(jié)點(diǎn)不包含在內(nèi)。,介紹典型插入算法。在線性表的第i個(gè)位置進(jìn)行插入，是指鏈表中有效數(shù)據(jù)元素結(jié)點(diǎn)的位置，頭結(jié)點(diǎn)不包含在內(nèi)。該算法作為鏈表類的公有成員函數(shù)來(lái)實(shí)現(xiàn)。,NCU-ZQP,53,在線性表的第i個(gè)位置插入數(shù)據(jù)元素x。算法2.6,void LinkList:

33、insert(int i,ElemType x) NodeType *p,*q,*s; int k=1; /計(jì)數(shù)器k，用于尋找i位置 q=Head; p=Head -next; while(knext; k+; if(k=i) s=new NodeType; s-data=x; q-next=s; s-next=p; coutn 插入成功。 endl; else coutn i1,或 i太大，不存在。endl; coutn 插入結(jié)束。; ,NCU-ZQP,54,鏈表插入算法的說(shuō)明：,由于算法已知條件是：插入的位置i（或稱序號(hào)）和被插入的數(shù)據(jù)元素x，因此函數(shù)具有兩個(gè)形參： void LinkLi

34、st:insert(int i,ElemType x) 在順序表類中有數(shù)據(jù)成員length，它顯式的是記錄線性表的長(zhǎng)度，而鏈表類中沒有l(wèi)ength。 如要了解鏈表中有效數(shù)據(jù)元素的個(gè)數(shù)（即線性表的長(zhǎng)度）還需編寫一個(gè)函數(shù)來(lái)統(tǒng)計(jì)。 插入的位置i取值仍然是有限制的。它的正確范圍（0 i = length + 1），因length 未知而無(wú)法顯式的進(jìn)行判斷。,NCU-ZQP,55,插入的位置 i取值的正確范圍的保障,當(dāng)i n+1： while()循環(huán)會(huì)執(zhí)行到：p= =NULL，q指向最后一個(gè)數(shù)據(jù)結(jié)點(diǎn)，因?yàn)閗記數(shù)也達(dá)到n+1，k不等于i，也執(zhí)行else語(yǔ)句輸出：n i1,或 i太大，不存在。,NCU-ZQ

35、P,56,2.3.3 鏈表的插入和刪除 2刪除,在討論鏈表刪除的算法之前，先來(lái)看單鏈表中刪除結(jié)點(diǎn)的基本操作。 （1）刪除p所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)（結(jié)點(diǎn)存在）。 假設(shè)要?jiǎng)h除線性表中p所指向結(jié)點(diǎn)（元素a）的后繼結(jié)點(diǎn)（元素b），如圖：,語(yǔ)句組： q=p-next; /讓q指向p的后繼結(jié)點(diǎn) p-next=q-next; /修改指針，繞過(guò)q結(jié)點(diǎn) delete q; /刪除q結(jié)點(diǎn) ,NCU-ZQP,57,（2）刪除p所指向的結(jié)點(diǎn)。 要?jiǎng)h除表中p所指向的結(jié)點(diǎn)（元素），應(yīng)先找到p的前驅(qū)結(jié)點(diǎn)q。這就需要組織while循環(huán)讓q從鏈表頭部q=head向后查找，直到q-next=p為止，然后進(jìn)行刪除操作。 語(yǔ)句組如下：

36、 q=head; while (q-next!=p) q+; /讓q向后找p的前驅(qū)結(jié)點(diǎn) q-next=p-next; /修改指針，繞過(guò)p結(jié)點(diǎn) delete p; /刪除p結(jié)點(diǎn) ,NCU-ZQP,58,（3）在已知的線性表中，刪除第i個(gè)數(shù)據(jù)元素結(jié)點(diǎn)，返回元素的值。 -鏈表刪除典型算法,，在此作為鏈表類的公有成員函數(shù)來(lái)實(shí)現(xiàn)。在線性表的第i個(gè)位置進(jìn)行插入，是指鏈表中有效數(shù)據(jù)元素結(jié)點(diǎn)的位置，頭結(jié)點(diǎn)不包含在內(nèi)。,已知條件是數(shù)據(jù)結(jié)點(diǎn)的位置i（或稱序號(hào)）。為了刪除第i位置的數(shù)據(jù)結(jié)點(diǎn)，需要設(shè)置指針p從第一個(gè)數(shù)據(jù)元素（p=Head-next）向后查找，頭結(jié)點(diǎn)不包含在內(nèi)。另外還需要一個(gè)輔助指針q作為p的前驅(qū)結(jié)點(diǎn)指

37、針緊跟p指針，q的初始值是q=Head。當(dāng)它們不斷向后移動(dòng)達(dá)到確定位置后，即可進(jìn)行刪除操作，如圖：,NCU-ZQP,59,單鏈表刪除的典型算法2.7,ElemType LinkList:delet(int i) NodeType *p,*q,*s; ElemType x; int k=1; /k為計(jì)數(shù)器 q=Head; p=Head-next; /q指頭指針，p指第一個(gè)數(shù)據(jù)結(jié)點(diǎn) while(knext; k+; if(p!=NULL) x=p-data; q-next=p-next; delete p; coutn 刪除結(jié)點(diǎn)成功。endl; else coutn i1,或 i太大，i不存在。e

38、ndl; x=-1; return x; ,NCU-ZQP,60,鏈表刪除算法的說(shuō)明,由于算法的已知條件是數(shù)據(jù)結(jié)點(diǎn)的位置i（或稱序號(hào)），因此，函數(shù)僅有一個(gè)形參： ElemType LinkList:delet(int i) 本函數(shù)有返回值，通過(guò)return x;語(yǔ)句獲取被刪除結(jié)點(diǎn)的數(shù)據(jù)值。 由于鏈表中不顯式存儲(chǔ)線性表長(zhǎng)度，刪除位置i取值正確范圍也不是顯式判斷（0i=length）。但上述算法能夠隱含地保證刪除位置i的正確取值。,NCU-ZQP,61,刪除的位置 i取值的正確范圍的保障,當(dāng)i n： q會(huì)指向最后一個(gè)數(shù)據(jù)結(jié)點(diǎn)，而p為空，所以執(zhí)行else語(yǔ)句輸出提示：n i1,或 i太大，不存在。,

39、NCU-ZQP,62,3單鏈表插入和刪除算法的時(shí)間復(fù)雜度分析,在順序存儲(chǔ)結(jié)構(gòu)的線性表中插入/刪除一個(gè)元素時(shí)會(huì)大量移動(dòng)數(shù)據(jù)元素，其時(shí)間復(fù)雜度為O(n)。而在鏈表中插入/刪除一個(gè)元素時(shí)卻不大量移動(dòng)數(shù)據(jù)元素(只移動(dòng)指針)，其時(shí)間復(fù)雜度可以視為O(1)。如果每個(gè)數(shù)據(jù)元素占用字節(jié)數(shù)比較多，鏈表結(jié)構(gòu)在時(shí)間方面具有明顯優(yōu)勢(shì)。 但是，順序結(jié)構(gòu)可以直接存取，其時(shí)間復(fù)雜度可以視為O(1)。而鏈表結(jié)構(gòu)則需設(shè)一指針從鏈表的開頭向后查找，如果將指針的移動(dòng)視為影響時(shí)間效率的主要因素，則時(shí)間復(fù)雜度可以視為O(n)。,NCU-ZQP,63,2.3.4 單鏈表的其他運(yùn)算,單鏈表除了上述兩種基本運(yùn)算外，還有其他一些不同的或較為復(fù)

40、雜的運(yùn)算。這些算法可以作為類的函數(shù)成員實(shí)現(xiàn)。 主要介紹： 1根據(jù)數(shù)據(jù)元素的值進(jìn)行插入/刪除 2單鏈表的逆置 3兩條單鏈表的合并,NCU-ZQP,64,1根據(jù)數(shù)據(jù)元素的值進(jìn)行插入/刪除,（1）在線性表中值為x的元素前插入一個(gè)值為y的數(shù)據(jù)元素。如果值為x的結(jié)點(diǎn)不存在，則將y插在表尾，如圖。,NCU-ZQP,65,根據(jù)數(shù)據(jù)元素的值進(jìn)行插入算法：,void LinkList:insert2(ElemType x, ElemType y) NodeType *p,*q,*s; s=new NodeType; s-data=y; q=head; p=q-next; while( p!=NULL) /插入新

41、結(jié)點(diǎn) ,NCU-ZQP,66,根據(jù)數(shù)據(jù)元素的值進(jìn)行刪除,（2）刪除線性表中值為x的數(shù)據(jù)元素，輸出“YES！”；如果x不存在，輸出“NO！”。 為了查找值為x的結(jié)點(diǎn)，設(shè)p從頭找起； 為了刪除該結(jié)點(diǎn)，設(shè)q指向p的前驅(qū)結(jié)點(diǎn)；,NCU-ZQP,67,根據(jù)數(shù)據(jù)元素的值刪除算法：,void LinkList:delet2(ElemType x) NodeType *p,*q; q=head; p=q-next; while(p!=NULL) ,NCU-ZQP,68,2單鏈表的逆置,單鏈表的逆置方法不唯一。在此，介紹利用在頭結(jié)點(diǎn)和與之相鄰的數(shù)據(jù)結(jié)點(diǎn)之間不斷插入后邊元素結(jié)點(diǎn)的方法，來(lái)實(shí)現(xiàn)鏈表逆置，如圖所示。,

42、NCU-ZQP,69,鏈表逆置算法2.8：,void LinkList:nizhi() NodeType *h,*p, *q; h=Haed; /Haed是鏈表類的私有數(shù)據(jù)成員 p=h-next; h-next=NULL; /暫時(shí)將頭結(jié)點(diǎn)與后邊數(shù)據(jù)結(jié)點(diǎn)斷開 while (p!=NULL) /不斷地在頭結(jié)點(diǎn)之后插入結(jié)點(diǎn) q=p-next; p-next=h-next; h-next=p; p=q; ,NCU-ZQP,70,3兩條單鏈表的合并,單鏈表的合并具有多種不同的方式，一種方式是將兩個(gè)有序表合并成為一個(gè)新的有序表，還有一種方式是將兩個(gè)線性表的元素間隔交叉合并等。這里介紹兩個(gè)非遞減有序表的合并

43、 兩個(gè)單鏈表的合并涉及兩個(gè)類對(duì)象，算法中是將第1條鏈表作為基礎(chǔ)，將第2條鏈表合并進(jìn)來(lái)，最終結(jié)果就在第1條鏈之中。具體實(shí)現(xiàn)見算法2.9。,NCU-ZQP,71,單鏈表合并算法2.9,void LinkList:merge( LinkList b) NodeType *p,*q,*r,*s; p=Head; r=p-next; /合并后的鏈表仍在Head之中 q=b.Head-next; s=q-next; /b是將被合并進(jìn)來(lái)的鏈表 while(r!=NULL ,NCU-ZQP,72,下面是一段調(diào)用程序：,int main() LinkList ha,hb; cout 建立第1條鏈表，注意數(shù)據(jù)遞增

44、有序?。篹ndl; ha.creat1(); cout 建立第2條鏈表，注意數(shù)據(jù)遞增有序！：endl; hb.creat1(); ha.merge(hb); /以hb為實(shí)參，調(diào)用合并鏈表的函數(shù) ha.Display(); /輸出ha新鏈表 學(xué)習(xí)算法不僅要掌握算法本身的設(shè)計(jì)技能，也需要將算法函數(shù)放在完整的源程序系統(tǒng)之中認(rèn)識(shí)理解。,NCU-ZQP,73,2.4 循環(huán)鏈表和雙向鏈表,線性表的存儲(chǔ)結(jié)構(gòu)除單鏈表之外，還可以有循環(huán)鏈表和雙向鏈表。單鏈表是循環(huán)鏈表和雙向鏈表的基礎(chǔ)。,NCU-ZQP,74,2.4.1 循環(huán)鏈表,將單鏈表的最后一個(gè)結(jié)點(diǎn)的指針指向鏈表的表頭結(jié)點(diǎn)，形成一個(gè)循環(huán)鏈表，如圖所示。 使用

45、頭指針h，也使用尾指針r，操作更方便。 優(yōu)點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)。,NCU-ZQP,75,兩條循環(huán)鏈表連接的語(yǔ)句組如下：, B-next=A-next; A-next=HB-next; delete HB; /釋放B表附加頭結(jié)點(diǎn) A=B; /A鏈尾指針A指新尾結(jié)點(diǎn) 時(shí)間復(fù)雜度為O(1),NCU-ZQP,76,2.4.2 雙向鏈表,雙向鏈表中的某個(gè)結(jié)點(diǎn)，可以直接找到它的前驅(qū)和后繼結(jié)點(diǎn)。無(wú)論利用向前這一鏈還是向后這一鏈，都可以遍歷整個(gè)鏈表，如果有一根鏈?zhǔn)Я耍€可以利用另一根鏈修復(fù)整個(gè)鏈表。,結(jié)點(diǎn)結(jié)構(gòu)如下： typedef char ElemType; struct NodeT

46、ype2 ElemType data; NodeType2 *next, *prior; ; NodeType2 *p, *q, *s;,NCU-ZQP,77,假設(shè)結(jié)點(diǎn)s已準(zhǔn)備好，插入結(jié)點(diǎn)s的具體操作語(yǔ)句組如下： s-next=p; s-prior=p-prior; /s結(jié)點(diǎn)的前驅(qū)指針域，取p的前驅(qū)結(jié)點(diǎn)（值為a）地址 p-prior-next=s; /讓p的前驅(qū)結(jié)點(diǎn)（值為a）的后繼指針域，指向s結(jié)點(diǎn) p-prior=s; /讓p的前驅(qū)指針域，也指向s結(jié)點(diǎn) 注意，各語(yǔ)句順序不可隨意改變。,1在雙向鏈表中p結(jié)點(diǎn)之前插入一個(gè)值為x的結(jié)點(diǎn)。,NCU-ZQP,78,語(yǔ)句組： p-prior-next=p

47、-next; /對(duì)應(yīng)圖中上方的虛線指針 p-next-prior=p-prior; /對(duì)應(yīng)圖中下方的虛線指針 delete p; ,2在雙向鏈表中刪除一個(gè)p結(jié)點(diǎn)。,由此可見，在循環(huán)鏈表、雙向鏈表中進(jìn)行插入或刪除操作比較方便。,NCU-ZQP,79,2.4.3 順序結(jié)構(gòu)與鏈表結(jié)構(gòu)的分析比較,用順序的方式存儲(chǔ)線性表： 1.內(nèi)存的存儲(chǔ)密度高，在結(jié)點(diǎn)等長(zhǎng)時(shí)，可隨機(jī)存取結(jié)點(diǎn)； 2.對(duì)順序表的插入和刪除往往造成大量信息的移動(dòng)，效率比較低。 3. 順序表要求占用連續(xù)的存儲(chǔ)空間，存儲(chǔ)分配只能預(yù)先進(jìn)行。如果插入操作超出預(yù)先分配的存儲(chǔ)區(qū)間，需要臨時(shí)擴(kuò)大是困難的。,NCU-ZQP,80,2.4.3 順序結(jié)構(gòu)與鏈表結(jié)

48、構(gòu)的分析比較,采用鏈表存儲(chǔ)結(jié)構(gòu)可克服上述不足， 1.它適合于需要頻繁插入和刪除元素的線性表，不會(huì)大量移動(dòng)數(shù)據(jù)元素。 2. 也適合于存儲(chǔ)空間大小不能預(yù)先確定的線性表?？梢噪S時(shí)分配和釋放存儲(chǔ)空間。 3. 鏈表結(jié)構(gòu)不能隨機(jī)存取結(jié)點(diǎn)中的數(shù)據(jù)，而需要在鏈表上先進(jìn)行查找，然后進(jìn)行存取操作。,NCU-ZQP,81,2.5 一元多項(xiàng)式相加問題,一元符號(hào)多項(xiàng)式的相加操作是線性表處理的典型用例。數(shù)學(xué)上一個(gè)一元多項(xiàng)式如下： 稱p為x的n階多項(xiàng)式，aixi是多項(xiàng)式的某個(gè)單項(xiàng)（0in），其中x為自變量，ai為系數(shù)，i為自變量的指數(shù)。已知有兩個(gè)一元多項(xiàng)式A和B： 將這兩個(gè)多項(xiàng)式相加得一個(gè)新的多項(xiàng)式C：,NCU-ZQP,8

49、2,2.5.1 多項(xiàng)式的鏈表存儲(chǔ)結(jié)構(gòu),一個(gè)多項(xiàng)式可以采用一條鏈表來(lái)表示。每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于多項(xiàng)式的一個(gè)項(xiàng)，其結(jié)點(diǎn)的結(jié)構(gòu)如下： struct Lpoly int coef ; /自變量的系數(shù) intexp ; /自變量的指數(shù) Lpoly *next; /指向下一結(jié)點(diǎn)的指針 ; 每個(gè)多項(xiàng)式的鏈表由多個(gè)單項(xiàng)的結(jié)點(diǎn)組成，高指數(shù)的項(xiàng)（高次冪）結(jié)點(diǎn)在鏈表頭部，低指數(shù)的項(xiàng)（低次冪）結(jié)點(diǎn)在鏈表的后部。A，B兩個(gè)多項(xiàng)式的鏈表結(jié)構(gòu)如圖所示。,NCU-ZQP,83,2.5.2 多項(xiàng)式相加的實(shí)現(xiàn),一個(gè)鏈表中結(jié)點(diǎn)的順序按照x的指數(shù)遞減排列。兩個(gè)多項(xiàng)式相加實(shí)質(zhì)上是兩個(gè)有序鏈表的合并操作。 為了實(shí)現(xiàn)兩個(gè)多項(xiàng)式相加，現(xiàn)設(shè)C鏈表為

50、A、B鏈表相加后的新鏈表。為了節(jié)省內(nèi)存資源，以A鏈表為基礎(chǔ)將B鏈表的結(jié)點(diǎn)合并到A鏈表中。在此，設(shè)C鏈表頭指針為pc，令其指向pa(pc=pa)，這樣以pa鏈表為基礎(chǔ)進(jìn)行合并操作，最終的結(jié)果就是這條以pc為頭指針的鏈表。,NCU-ZQP,84,多項(xiàng)式加法（鏈表合并）的方法,為了進(jìn)行多項(xiàng)式加法運(yùn)算，設(shè)置p，q兩個(gè)指針變量分別指向pa，pb兩個(gè)鏈表的第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)。 然后對(duì)p，q兩個(gè)結(jié)點(diǎn)的指數(shù)域進(jìn)行比較： 1. 兩個(gè)結(jié)點(diǎn)的指數(shù)相同，則結(jié)點(diǎn)的系數(shù)相加。新的系數(shù)非零，則連入第3條鏈表C；否則跳過(guò)這兩個(gè)結(jié)點(diǎn)。 2. 兩個(gè)結(jié)點(diǎn)的指數(shù)不同，將指數(shù)較大的結(jié)點(diǎn)連入C表。,NCU-ZQP,85,初始狀態(tài) 第1次處理后 第