線性鏈表西安交通大學

1、西安交通大學計教中心西安交通大學計教中心采用鏈式存儲結構的線性表有單鏈表、雙采用鏈式存儲結構的線性表有單鏈表、雙向鏈表、單循環(huán)鏈表以及雙向循環(huán)鏈表等多種向鏈表、單循環(huán)鏈表以及雙向循環(huán)鏈表等多種形式。形式。 單鏈表的概念單鏈表的概念結點定義結點定義 結點包含數(shù)據(jù)域和指針域結點包含數(shù)據(jù)域和指針域, ,結點結構可描結點結構可描述為述為: :其中其中data域用來存放結點本身信息，域用來存放結點本身信息，類型由具體問題而定，本節(jié)也將其設定類型由具體問題而定，本節(jié)也將其設定為為ElemType類型，表示某一種具體的已類型，表示某一種具體的已知類型，知類型，next域存放下一個元素地址。域存放下一個元素地

2、址。 Data next next 帶頭結點單鏈表的邏輯結構帶頭結點單鏈表的邏輯結構 為了能順次訪問每個結點，需要保存單鏈為了能順次訪問每個結點，需要保存單鏈表第一個結點的存儲地址。這個地址稱為線性表第一個結點的存儲地址。這個地址稱為線性表的頭指針，本節(jié)用表的頭指針，本節(jié)用head表示。表示。 為了操作上的方便，可以在單鏈表的頭部為了操作上的方便，可以在單鏈表的頭部增加一個特殊的頭結點。頭結點的類型與其他增加一個特殊的頭結點。頭結點的類型與其他結點一樣，只是頭結點的數(shù)據(jù)域為空。結點一樣，只是頭結點的數(shù)據(jù)域為空。 增加頭結點避免了在刪除或添加第一個位增加頭結點避免了在刪除或添加第一個位置的元素時

3、進行的特殊程序處理。置的元素時進行的特殊程序處理。 head a1a2an帶頭結點的單鏈表帶頭結點的單鏈表帶頭結點單鏈表的存儲結構帶頭結點單鏈表的存儲結構head 38數(shù)據(jù)域數(shù)據(jù)域數(shù)據(jù)域數(shù)據(jù)域38229486 a2 86 94 a3 NULL a1 22 存儲地址存儲地址單鏈表存儲結構示意圖單鏈表存儲結構示意圖結點的結點的c+描述描述typedef struct LNode ElemType data; /數(shù)據(jù)域，數(shù)據(jù)域，ElemType代代/表某種數(shù)據(jù)類型表某種數(shù)據(jù)類型struct LNode *next; / 指針域指針域 *LinkList; ;這個定義是自引用類型的。換言之，每個這個定

4、義是自引用類型的。換言之，每個結點都包含另一個同類型結點的地址。結點都包含另一個同類型結點的地址。 單鏈表的類形式定義如下：單鏈表的類形式定義如下：class LinkListpublic: LNode *head; /定義頭指針定義頭指針 LinkList() /構造函數(shù)構造函數(shù)head=new LNode;/建立頭結點建立頭結點head-next=NULL;/頭結點的指針為空頭結點的指針為空 int ListSize(); /求單鏈表長度求單鏈表長度 /返回表中指定序號結點的指針返回表中指定序號結點的指針 LNode* GetElemPointer(int pos); ( 接下一頁接下一頁

5、 .) ( 接上頁接上頁 ) /向單鏈表第向單鏈表第i個位置插入元素個位置插入元素x void InsertList(int i, ElemType x); /從單鏈表中刪除第從單鏈表中刪除第i個結點個結點 LNode* LinkList:DeleteList( int i); /在單鏈表中查找數(shù)據(jù)值為在單鏈表中查找數(shù)據(jù)值為x的結點的結點 LNode* Find( ElemType x )；; 這里將構造函數(shù)的實現(xiàn)直接放在了類定義中。如果要定這里將構造函數(shù)的實現(xiàn)直接放在了類定義中。如果要定義一個不帶頭結點的單鏈表，則只需定義空的頭指針，義一個不帶頭結點的單鏈表，則只需定義空的頭指針，即即hea

6、d=NULLhead=NULL。指針操作指針操作假如假如p p為指向某一結點的指針，則該結點的為指向某一結點的指針，則該結點的數(shù)據(jù)域用數(shù)據(jù)域用p-datap-data表示，該結點的指針域用表示，該結點的指針域用 p-nextp-next表示。它們都是變量，可以被賦值，表示。它們都是變量，可以被賦值，也可向其他變量賦值。也可向其他變量賦值。例如例如: : 假定假定datadata為整型變量為整型變量, ,則則p-data=5; p-next=NULL; 將將結點變?yōu)榻Y點變?yōu)? : 5 NULL next aiai-1ai-1aiai-1ai+1qqpp 如果如果p為指向結點為指向結點ai的指針，

7、那么的指針，那么p-next就是就是指向指向ai后繼后繼ai+1的指針；若的指針；若q為另一指針變量為另一指針變量 q=p 指針指針p指向指針指向指針q所指的結點所指的結點 q=p-next 指針指針p指向指針指向指針q所指結點的后繼所指結點的后繼p=p-next 指針指針p向后移動一個結點向后移動一個結點 pai-1ai ai+1p常用算法常用算法（1 1）求單鏈表的長度）求單鏈表的長度單鏈表長度不定，要確定鏈表長度需要走遍表中所有單鏈表長度不定，要確定鏈表長度需要走遍表中所有結點才能算出。結點才能算出。 int LinkList:ListSize() LNode *p=head-next;

8、 /p指向第一個元素所在結點指向第一個元素所在結點 int len=0; while( p!=NULL ) /逐個檢測逐個檢測p結點存在與否結點存在與否 len+; p=p-next; /指針后移指針后移 return len; 為了保持頭指針不變，使用了指針為了保持頭指針不變，使用了指針p在鏈表中移動。在鏈表中移動。（2）返回單鏈表中指定序號的結點的指針返回單鏈表中指定序號的結點的指針LNode* LinkList:GetElemPointer(int pos) if(posnext;/p為首元結點指針為首元結點指針int k=1;while( p!=head & knext; k+

9、; if(k=pos&p!=head) return p; /返回第返回第pos個結點指針個結點指針else return NULL; /該位置不存在該位置不存在 （3）從單鏈表中刪除第）從單鏈表中刪除第i個結點個結點為了從單鏈表中刪除第為了從單鏈表中刪除第i個結點，需進行如下操作：個結點，需進行如下操作： 若第若第i個結點存在則找到第個結點存在則找到第i和第和第i-1個個結結點的指針點的指針p和和q通過語句通過語句q-next=p-next將第將第i-1個個結結點的指針域賦值點的指針域賦值為第為第i+1個個結結點的指針，將第點的指針，將第i個結點從鏈表中斷開。個結點從鏈表中斷開。 釋

10、放第釋放第i個結點所占空間以便于重用。個結點所占空間以便于重用。qpai-1aiai+1LNode* LinkList:DeleteList( int i ) if(i1)cout”不存在第不存在第”i”個元素個元素”; else LNode *p=head; /p指向頭結點指向頭結點(第第0個結點個結點) LNode *q; /q和和p最終分別指向第最終分別指向第i-1和第和第i個結點個結點 int k=0; while( p!=NULL&knext;k+; if(p=NULL) cout inext=p-next;/從鏈表中刪除該結點從鏈表中刪除該結點delete p;/釋放結點釋

11、放結點p （4）在第）在第i個位置插入新結點個位置插入新結點x在鏈表的第在鏈表的第i個位置插入一個新結點，需進行如下操作：個位置插入一個新結點，需進行如下操作： 首先找到第首先找到第i-1個結點的指針個結點的指針p 建立新結點建立新結點s并通過語句并通過語句s-next=p-next將其指針指將其指針指向第向第i個結點個結點 通過語句通過語句p-next=s將第將第i-1個結點的指針指向新結點個結點的指針指向新結點ai-1aipxs12void LinkList:InsertList( int i, ElemType x) LNode *p=head; p=GetElemPointer(i-1

12、); /p最終將指向第最終將指向第i-1個結點個結點 if(!p) cout idata = x; s-next=p-next;/定義結點定義結點s的指針域的指針域 p-next=s;/修改結點修改結點p的指針域的指針域 （4）在單鏈表中查找數(shù)據(jù)值為）在單鏈表中查找數(shù)據(jù)值為x的結點的結點可以按照數(shù)據(jù)元素本身的值進行查找，也可以按照數(shù)可以按照數(shù)據(jù)元素本身的值進行查找，也可以按照數(shù)據(jù)元素的某個屬性進行查找。這里僅給出按照數(shù)據(jù)據(jù)元素的某個屬性進行查找。這里僅給出按照數(shù)據(jù)元素本身的值進行查找的算法。元素本身的值進行查找的算法。LNode* LinkList:Find( ElemType x ) LNo

13、de *p=head-next; /p指向第一個元素所在結點指向第一個元素所在結點 while ( p!=NULL & p-data!=x ) p = p-next; return p; 其他形式的鏈表其他形式的鏈表 （1 1）單循環(huán)鏈表）單循環(huán)鏈表通過把單鏈表最后一個結點的指針改為指向第一個通過把單鏈表最后一個結點的指針改為指向第一個結點，就可以把一個單鏈表改造成單循環(huán)鏈表。因結點，就可以把一個單鏈表改造成單循環(huán)鏈表。因為單鏈表最后一個結點的指針總是空為單鏈表最后一個結點的指針總是空值，所以這樣值，所以這樣的修改總是可行的。的修改總是可行的。head.a1a2anhead2 2）雙向鏈表）雙向鏈表如果每個鏈表結點既有指向下一個元素的指針，又如果每個鏈表結點既有指向下一個元素的指針，又有指向前一個元素的指針，那么這種有指向前一個元素的指針，那么這種鏈表就是鏈表就是雙雙向鏈表，雙向鏈表結點的定義只需在單鏈表結點向鏈表，雙向鏈表結點的定義只需在單鏈表結點定義的基礎上增加一個前向指針即可定義的基礎上增加一個前向指針即可。head.ana2a1鏈表應用舉例鏈表應用舉例 約瑟夫環(huán)問題可以解釋為：將