【文章內(nèi)容簡介】 最前端，本身不帶數(shù)據(jù)， 僅標志表頭 。 ? 設(shè)置表頭結(jié)點的目的是 ? 統(tǒng)一空表與非空表的操作 ? 簡化鏈表操作的實現(xiàn) 非空表 ? an a1 L ? 空表 頭指針 頭結(jié)點 L a1 a2 a3 a4 ? L 活動指針 單鏈表的基本操作 p=Lnext。 //p指向第一個結(jié)點 p=pnext。 //p指向下一個結(jié)點 直到 p== ? 結(jié)束 P ? p=Lnext。 //p指向第一個結(jié)點 while(p!=NULL) //當(dāng)存在這個結(jié)點 { p=pnext。 //移動 p指向下一個結(jié)點 } 鏈表的基本操作形式 p L a1 a2 a3 ? n= 1 p L a1 a2 a3 ? n= 2 p L a1 a2 a3 ? n= 3 P=^ L a1 a2 a3 ? 求單鏈表長度 n= 0 int ListLength ( LinkList *L ) { LinkList *p = Lnext。 //活動指針 p 指向第一個結(jié)點 int n = 0。 //計數(shù)器初值 while ( p != NULL ) { n++。 //逐個結(jié)點檢測 p = plink。 } return n。 } 求單鏈表長度 建立單鏈表（尾插法） ? 建立一個空表。 ? 依次將新結(jié)點插入在鏈表的表尾。 L ? p ? r r ? r ? p r 生成一個新結(jié)點 L ? 注意 ：要設(shè)置一個尾指針 r，總是指向表中最后一個結(jié)點， 新結(jié)點插在它的后面；尾指針 r 初始時置為指向表頭結(jié)點地址。 p=malloc( )。 rnext=p。 r = p。 void InitList(LinkList *amp。L ) //建立一個空表 { L=(LinkList *)malloc(sizeof(LinkList))。//生成頭結(jié)點 Lnext=NULL。 return(h)。 //返回頭指針 } 建立單鏈表（尾插法） （ 1）建立一個空表 Initlist( )。 （ 2）依次將每個新結(jié)點插入鏈表中。 void CreatList( LinkList *amp。L,Elemtype a[ ], int n ) //利用尾插法建立單鏈表 { LinkList *L, *s, *r。 InitList(L)。 //建立一個空表 r= L。 for(i=1。i=n。i++) { s=(LinkList *)malloc(sizeof(LinkList))。//生成新結(jié)點 sdata=a[i]。 //存儲數(shù)據(jù)元素 snext=NULL。 rnext=s 。 //插入表尾 r= s 。 //r總是指向表尾 } rnext=NULL。 } 在單鏈表中插入新結(jié)點 snext = pnext。 s 插入 p s p 注意：先確定 s的直接前驅(qū) r,在 p之后插入新結(jié)點 p。 pnext = s。 生成新結(jié)點 s=malloc( ) pnext 在單鏈表中第 i個位置插入一個新元素 （ 1）確定第 i1個結(jié)點 GetElem(L, i1)。 （ 2）生成新結(jié)點 p （ 3）插入新結(jié)點 bool GetElem(LinkList *L, int i,LinkList *amp。p) //取單鏈表中第 i個結(jié)點 { LinkList *p。 int j。 p=L。 j=0。 while( ji amp。amp。 p!=NULL) //不是第 i個結(jié)點 { p=pnext。 j++。 } if(p==NULL) return false。 else return true。 } 掃描單鏈表 尋找第 i個結(jié)點 i初值 ? bool ListInsert (LinkList *amp。L, int i, ElemType e) //將新元素 x 插入在鏈表中第 i 個結(jié)點位置 { linklist *p,*s。 GetElem (head,i1,p)。 //確定新結(jié)點的前驅(qū) if ( p==NULL ) return false。//插入失敗 s=(LinkList *)malloc(sizeof(LinkList))。 sdata= e。 //生成新結(jié)點 p并賦值 snext=pnext。 pnext=s。 //將 p插入 r之后 return true。 //插入成功 } 在單鏈表中刪除一個結(jié) p pnext = qnext。 free(q)。 //釋放 p p q 注意： 先確定 q的前驅(qū) p 刪除單鏈表中第 i個結(jié)點 （ 1）確定第 i1個結(jié)點 GetElem(L, i1, p)。 （ 2）確定第 i個結(jié)點； （ 3）刪除該結(jié)點，并釋放； int ListDelete (LinkList *L, int i) //將在鏈表中第 i 個結(jié)點刪除 { LinkList *p,*q。 GetElem(L,i1,p)。 //確定第 i1個結(jié)點的前驅(qū) if ( p==NULL ) return false。 //刪除失敗 q=pnext。 //p指向第 i個結(jié)點 pnext=qnext。 //刪除 p free (q)。 return true。 //刪除成功 } 單鏈表應(yīng)用舉例 例 1 單鏈表的逆置 a1 a2 a3 a4 ? 逆置前 L a4 a3 a2 a1 ? 逆置后 L a1 a2 a3 an1 an a1 a2 a3 an1 an 利用頭插法 a5 p pnext=Lnext。 Lnext=p。 依次將每個結(jié)點頭插到單鏈表中 （ 1）分成兩個單鏈表 L1和 L2 a1 a2 a3 a4 ? L q 空表 L1 含所結(jié)點的無頭鏈表 L2 （ 2）依次將 L2中每一個結(jié)點逆置到 L1中 a2 a1 ? L q 取出 L2中第一個結(jié)點 p (作為當(dāng)前逆置的結(jié)點） a3 a4 ? p 將 p頭插到 L1中