線性表的鏈?zhǔn)奖硎?/h1>
單鏈表的定義
線性表的鏈?zhǔn)酱鎯ΨQ為單鏈表妨马；
每個鏈表節(jié)點盅视，除存放元素自身的信息外，還需要存放一個指向其后繼結(jié)點的指針询刹；
data為數(shù)據(jù)域谜嫉，存放數(shù)據(jù)；next為指針域凹联，存放指針
單鏈表中結(jié)點類型的描述
typedef struct LNode{
ElemType data; //數(shù)據(jù)域
struct LNode *next; //指針域
}LNode,*Linklist;
- 順序表需要大量連續(xù)存儲空間沐兰，單鏈表克服了這一缺點，即存儲空間不一定要連續(xù)
- 但是單鏈表相對于順序表多了指針域蔽挠，因此有浪費空間的缺點
- 單鏈表的元素是離散地分布在存儲空間的僧鲁，所以無法實現(xiàn)隨機存取，尋找特定的結(jié)點必須從表頭開始遍歷象泵，依次查找
頭指針與頭節(jié)點
通常用頭指針來標(biāo)識一個單鏈表寞秃，如單鏈表L；特別地偶惠，頭指針為NULL時表示一個空表
為了操作上的方便春寿，在單鏈表主體的第一個結(jié)點前加一個結(jié)點，稱為頭結(jié)點忽孽；頭結(jié)點的數(shù)據(jù)域可以記錄表長等信息绑改，也可以不記錄任何信息
頭指針和頭節(jié)點的區(qū)別
- 頭指針始終指向鏈表的第一個結(jié)點，無論頭結(jié)點是否存在
- 頭結(jié)點是帶頭結(jié)點鏈表的第一個結(jié)點
引入頭結(jié)點帶來的優(yōu)點
- 由于開始結(jié)點的位置被存放在頭結(jié)點的指針域中兄一，所以鏈表第一個位置的操作和其他位置相同（鏈表的第一個有效位置實際上是第二個結(jié)點）
- 引入頭結(jié)點后厘线，無論鏈表是否為空，頭指針都指向頭結(jié)點的非空指針出革；否則空鏈表與非空鏈表的處理不同
單鏈表上基本操作的實現(xiàn)
單鏈表上的主要操作主要有建立（頭插法造壮、尾插法）、查找（按序號、按值）耳璧、插入結(jié)點成箫、刪除結(jié)點、求表長
采用頭插法建立單鏈表
LinkList List_HeadInsert(LinkList &L){
LNode *s;int x;
L = (Linklist)malloc(sizeof(LinkList)); //創(chuàng)建頭結(jié)點
L->next = NULL; //頭結(jié)點指針為空旨枯，初始化為空鏈表
scanf("d",&x); 輸入（第一個）結(jié)點的值
while(x != 9999){ //結(jié)束條件（如輸入9999）
s = (LinkList)malloc(sizeof(LinkList)); //創(chuàng)建一個新結(jié)點
s->data = x;
s->next = L->next;
L->next = s; //插入過程
scanf("d",&x);
}
return L;
}
- 頭插法建立單鏈表時蹬昌，讀入數(shù)據(jù)的順序和鏈表中元素的順序是相反的
- 每個結(jié)點插入的時間為O(1)
- 設(shè)單鏈表長為n，則頭插法生成單鏈表的總時間復(fù)雜度為O(n)
采用尾插法建立單鏈表
頭插法雖然簡單攀隔，但是輸入順序和生成鏈表中結(jié)點的順序相反皂贩；尾插法將新結(jié)點插入當(dāng)前鏈表的表尾，為此必須增加一個尾指針昆汹，使其始終指向當(dāng)前鏈表的尾結(jié)點明刷；時間復(fù)雜度與頭插法相同
Linklist List_TailInsert(Linklist &L){
int x; //設(shè)元素類型為整型
L = (LinkList)malloc(sizeof(LNode));
LNode *s,*r = L; //r為表尾指針
scanf("%d",x); //輸入結(jié)點的data域值
while(x != 9999){ //結(jié)束條件（如輸入9999）
s = (LNode *)malloc(sizeof(LNode));
s->data = x;
r->next = s; //r指向下一個表尾結(jié)點
r = s; //r再次成為表尾指針
scanf("%d",x);
}
r->next = NULL; //尾結(jié)點指針為空
return L;
}
按序號查找結(jié)點值
LNode *GetElem(LinkList L,int i){
int j = 1; //計數(shù)器，初始化為1
LNode *p = L->next; //將頭結(jié)點的指針賦值給p
if(i == 0)
return L;
if(i <= 0)
return NULL;
while(p&&j < i){ //從第1個結(jié)點開始筹煮，查找到第i個結(jié)點
p = p->next;
j++;
}
return p; //返回第i個結(jié)點的指針
}
- 按序號查找結(jié)點的時間復(fù)雜度為O(n)
按值查找表結(jié)點
從單鏈表第一個結(jié)點開始，依次比較各個結(jié)點中數(shù)據(jù)域的值居夹；如果鏈表中某結(jié)點數(shù)據(jù)域的值等于給定值e败潦，則返回該結(jié)點的指針；若沒有這樣的結(jié)點准脂，則返回NULL
LNode *LocateElem(LinkList L,ElemType e){
LNode *p = L->next;
while(p != NULL&&p->data != e) //p后面無結(jié)點或該結(jié)點的data域等于被查找對象時跳出循環(huán)
p = p->next;
return p; //找到后返回p劫扒，否則返回NULL
}
插入結(jié)點操作
插入節(jié)點操作將值為x的新結(jié)點插入到單鏈表的第i個位置上；先檢查插入位置的合法性狸膏，然后找到待插入位置的前驅(qū)結(jié)點沟饥，即第i-1個結(jié)點，再在其后插入新結(jié)點
調(diào)用序號查找算法GetElem(L,i-1),查找第i-1個結(jié)點
假設(shè)返回的第i-1個結(jié)點為 *p湾戳，令新結(jié)點 *s的指針域指向 *p的后繼結(jié)點
令 *p的指針域指向新插入的結(jié)點 *s
1 p = GetElem(L,i-1);
2 s->next = p->next;
3 p->next = s;
- 2句和3句的順序不能顛倒贤旷，否則s將指向自己，顯然是錯誤的
- 算法的主要時間開銷在查找第i-1個元素砾脑，算法時間復(fù)雜度為O(n),插入操作的時間復(fù)雜度僅為O(1)
對某一結(jié)點實現(xiàn)前插操作
以上面的算法為例幼驶，前插操作可以轉(zhuǎn)化為后插操作，但需要調(diào)用GetElem函數(shù)找到第i-1個結(jié)點韧衣，而查找第i-1個元素的時間復(fù)雜度為O(n)
對于已知結(jié)點盅藻，可以采取另外一種方式進行前插轉(zhuǎn)換為后插的操作；設(shè)待插入結(jié)點為 *s,將其插入到 *p的前面畅铭，我們?nèi)匀豢梢詫⑵洳迦氲?*p的后面氏淑，將p->data與s->data交換，這樣既滿足了邏輯關(guān)系硕噩，又能使算法時間復(fù)雜度降為O(1)
s->next = p->next;
p->next = s;
temp = p->data;
p->data = s->data;
s->data = temp;
刪除結(jié)點操作
刪除結(jié)點操作是將單鏈表的第i個節(jié)點刪除假残；假設(shè)結(jié)點 *p為被刪除結(jié)點 *q的前驅(qū)節(jié)點，僅需修改 *p的指針域炉擅，將 *p的指針域next指向 *q的下一結(jié)點
p = GetElem(L,i-1);
q = p->next;
p->next = q->next;
free(q);
- 和插入算法一樣守问，該算法的時間主要耗費在查找上匀归，因此算法的時間復(fù)雜度為O(n)
刪除結(jié)點*p
刪除結(jié)點 *p，通常的做法是用GetElem找到 *p的前驅(qū)節(jié)點耗帕，然后再執(zhí)行刪除操作穆端，時間復(fù)雜度為O(n)
實際上，也可以通過刪除 *p的后繼結(jié)點的方法實現(xiàn)仿便；將其后繼結(jié)點的值賦給它体啰，并且刪除后繼結(jié)點，可以使算法的時間復(fù)雜度降為O(1)
q = p->next;
p->data = q->next->data;
p->next = q->next;
free(q)嗽仪；
求表長操作
求表長操作就是計算單鏈表中數(shù)據(jù)結(jié)點（不帶頭結(jié)點）的個數(shù)荒勇；遍歷+計數(shù)器，算法的時間復(fù)雜度為O(n);不帶頭結(jié)點和帶頭結(jié)點的單鏈表處理不同闻坚；對不帶頭結(jié)點的單鏈表沽翔，當(dāng)表為空時要單獨處理
