【文章內(nèi)容簡介】 儲結構，簡稱為鏈表 (Linked List)。 線性鏈表 鏈表是指用一組任意的存儲單元來依次存放線性表的結點，這組存儲單元即可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。因此，鏈表中結點的邏輯次序和物理次序不一定相同。為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還必須存儲指示其后繼結點的地址（或位置）信息，這個信息稱為指針 (pointer)或鏈 (link)。這兩部分組成了鏈表中的結點結構： 來自 的資料庫下載 其中： data域是數(shù)據(jù)域，用來存放結點的值。next是指針域（亦稱鏈域），用來存放結點的直接后繼的地址（或位置）。鏈表正是通過每個結點的鏈域將線性表的 n個結點按其邏輯次序鏈接在一起的。由于上述鏈表的每一個結只有一個鏈域，故將這種鏈表稱為單鏈表（ Single Linked)。 顯然，單鏈表中每個結點的存儲地址是存放在其前趨結點 next域中，而開始結點無前趨，故應設頭指針 head指向開始結點。同時，由于 終端結點無后繼，故終端結點的指針域為空，即null（圖示中也可用 ^表示 )。 例 線性表 :(bat， cat， eat， fat， hat， jat，lat， mat) data link 來自 的資料庫下載 的單鏈表示意圖如下： …… 110 …… 130 135 …… 160 頭指針 head 165 170 …… 200 205 …… ……… …… hat 200 …… . …… cat 135 eat 170 … . …… mat Null bat 130 fat 110 …… …… jat 205 lat 160 …… …… 165 來自 的資料庫下載 ? head bat cat eat mat ^ … 單鏈表是由表頭唯一確定，因此單鏈表可以用頭 指針的名字來命名。 例如：若頭指針名是 head，則把鏈表稱為表 head。 用 C語言描述的單鏈表如下： Typedef char datatype。 Typedef struct node{ datatype data。 struct node *next。 }listnode。 來自 的資料庫下載 typedef listnode *linklist。 listnode *p。 linklist head。 注意區(qū)分指針變量和結點變量這兩個不同的概念。 P為動態(tài)變量，它是通過標準函數(shù)生成的，即 p=(listnode*)malloc(sizeof(listnode))。 函數(shù) malloc分配了一個類型為 listnode的結點變量的空間，并將其首地址放入指針變量 p中。一旦 p所指的結點變量不再需要了，又可通過標準函數(shù) free(p) 釋放所指的結點變量空間。 來自 的資料庫下載 ? 指針變量 P和（其值為結點地址）和結點變量*P之間的關系。 來自 的資料庫下載 一、建立單鏈表 假設線性表中結點的數(shù)據(jù)類型是字符，我們逐個輸入這些字符型的結點，并以換行符‘ \n‘為輸入結束標記。動態(tài)地建立單鏈表的常用方法有如下兩種： 頭插法建表 該方法從一個空表開始，重復讀入數(shù)據(jù)，生成新結點，將讀入數(shù)據(jù)存放到新結點的數(shù)據(jù)域中，然后將新結點插入到當前鏈表的表頭上，直到讀入結束標志為止。 來自 的資料庫下載 linklist createlistf(void) { char ch。 linklist head。 listnode *p。 head=null。 ch=getchar( )。 while (ch!=‵ \n′{ p=(listnode*)malloc(sizeof(listnode))。 p–data=ch。 p–next=head。 來自 的資料庫下載 head=p。 ch=getchar( )。 } return (head)。 } 來自 的資料庫下載 listlink createlist(int n) { int data。 linklist head。 listnode *p head=null。 for(i=n。i0。i){ p=(listnode*)malloc(sizeof(listnode))。 scanf((〝 %d〞 ， amp。p–data)。 p–next=head。 head=p。 } 來自 的資料庫下載 return(head)。 } 尾插法建表 頭插法建立鏈表雖然算法簡單，但生成的鏈表中結點的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結點插入到當前鏈表的表尾上，為此必須增加一個尾指針 r，使其始終指向當前鏈表的尾結點。例： 來自 的資料庫下載 linklist creater( ) { char ch。 linklist head。 listnode *p， *r。 //(， *head。) head=NULL。r=NULL。 while((ch=getchar( )!=‵ \n′){ p=(listnode *)malloc(sizeof(listnode))。 p–data=ch。 if(head=NULL) head=p。 else 來自 的資料庫下載 r–next=p。 r=p。 } if (r!=NULL) r–next=NULL。 return(head)。 } 說明：第一個生成的結點是開始結點，將開始結點插入到空表中，是在當前鏈表的第一個位置上插入，該位置上的插入操作和鏈表中其它位置上的插入操作處理是不一樣的，原因是開始結點的位置是存放在頭指針（指針變量）中， 來自 的資料庫下載 而其余結點的位置是在其前趨結點的指針域中。算法中的第一個 if語句就是用來對第一個位置上的插入操作做特殊處理。算法中的第二個 if語句的作用是為了分別處理空表和非空表兩種不同的情況，若讀入的第一個字符就是結束標志符，則鏈表 head是空表，尾指針 r亦為空，結點 *r不存在；否則鏈表 head非空，最后一個尾結點 *r是終端結點，應將其指針域置空。 如果我們在鏈表的開始結點之前附加一個結點，并稱它為 頭結點 ，那么會帶來以下兩個優(yōu)點： a、由于開始結點的位置被存放在頭結點的指針域中，所以在鏈表的第一個位置上的操作就 來自 的資料庫下載 和在表的其它位置上的操作一致，無需進行特殊處理； b、無論鏈表是否為空，其頭指針是指向頭結點 在的非空指針（空表中頭結點的指針域為空），因此空表和非空表的處理也就統(tǒng)一了。 其算法如下： linklist createlistr1( ){ char ch。 linklist head=(linklist)malloc(sizeof(listnode))。 listnode *p， *r 來自 的資料庫下載 r=head。 while((ch=getchar( ))!=‵ \n′{ p=(listnode*)malloc(sizeof(listnode))。 p–data=ch。 p–next=p。 r=p。 } r–next=NULL。 return(head)。 } 來自 的資料庫下載 上述算法里動態(tài)申請新結點空間時未加錯誤處理，可作下列處理： p=(listnode*)malloc(sizeof(listnode)) if(p==NULL) error(〝 No space for node can be obtained〞 )。 return ERROR。 以上算法的時間復雜度均為 O(n)。 來自 的資料庫下載 二、查找運算 按序號查找 在鏈表中，即使知道被訪問結點的序號 i，也不能象順序表中那樣直接按序號 i訪問結點，而只能從鏈表的頭指針出發(fā)，順鏈域 next逐個結點往下搜索，直到搜索到第 i個結點為止。因此，鏈表不是隨機存取結構。 設單鏈表的長度為 n，要查找表中第 i個結點，僅當 1≦i≦n 時， i的值是合法的。但有時需要找頭結點的位置，故我們將頭結點看做是第 0 個結點，其算法如下： 來自 的資料庫下載 Listnode * getnode(linklist head ， int i) { int j。 listnode * p。 p=head。j=0。 while(p–next amp。amp。 jI){ p=p–next。 j++。 } if (i==j) return p。 來自 的資料庫下載 else return NULL。 } 按值查找 按值查找是在鏈表中，查找是否有結點值等于給定值 key的結點，若有的話，則返回首次找到的其值為 key的結點的存儲位置；否則返回 NULL。查找過程從開始結點出發(fā)，順著鏈表逐個將結點的值和給定值 key作比較。其算法如下： 來自 的資料庫下載 Listnode * locatenode(linklist head， int key) { listnode * p=head–next。 while( p amp。amp。 p–data!=key) p=p–next。 return p。 } 該算法的執(zhí)行時間亦與輸入實例中的的取值key有關，其平均時間復雜度的分析類似于按序號查找，也為 O(n)。 來自 的資料庫下載 三、插入運算 插入運算是將值為 x的新結點插入到表的第 i個結點的位置上，即插入到 ai1與 ai之間。因此，我們必須首先找到 ai1的存儲位置 p，然后生成一個數(shù)據(jù)域為 x的新結點 *p，并令結點 *p的指針域指向新結點，新結點的指針域指向結點 ai。從而實現(xiàn)三個結點 ai1， x和 ai之間的邏輯關系的變化，插入過程如： 來自 的資料