單連結清單的定義和表示
單連結清單是一種鍊式存取的資料結構，用一組位址任意的存儲單元存放線性表中的資料元素。
連結清單中的資料是以結點來表示的，每個結點的構成包括兩個域：其中存儲資料元素資訊的域成為資料域（data）；存儲直接後繼存儲位置的域稱為指針域（next）。
單連結清單是由頭指針唯一确定的，是以單連結清單可以用頭指針的名字來命名。若頭指針名是 L ，則簡稱該連結清單為表L。
單連結清單可由頭指針唯一确定，在c語言中可用結構指針來描述：
//單連結清單的存儲結構
typedef struct LNode
{
ElemType data; //結點的資料域
struct LNode *next; //結點的指針域
}LNode,*LinkList; //LinkList為指向結構體LNode的指針類型
差別首元結點、頭結點、頭指針：
-
首元結點
-
頭結點
-
頭指針
線性表-單連結清單的基本操作
連結清單增加頭節點的作用：
- 便于首元結點的處理
- 便于空表和非空表的統一處理
單連結清單基本操作的實作
①單連結清單的初始化（構造空表）
【算法步驟】
- 生成新結點作頭節點，用頭指針 L 指向頭節點
- 将頭節點的指針域置空
【算法描述】
Status InitList(LinkList &L)
{
L=new LNode; //生成一個新結點作為頭節點，用頭指針L指向頭節點
L->next NULL; //頭節點指針域置空
return OK;
}
注：
L=new LNode;（c++)也可寫成
L=(LinkList)malloc(sizeof(LNode));©
malloc函數用法（ c ）：
- malloc是動态記憶體配置設定函數，用于申請一塊連續的指定大小的記憶體塊區域以void類型傳回配置設定的記憶體區域位址（void為不确定類型指針）
- 在使用malloc開辟空間時，使用完成後要用
free函數釋放
- malloc函數必須在其前面加上指針類型
強制轉換
- 頭檔案是
stdlib.h
-
指針自身 = (指針類型*）malloc（sizeof（指針類型）*資料數量）
#include<stdio.h>
#include<stdlib.h>
int main()
{
int *p=NULL;
int n =5;
p=(int*)malloc(sizeof(int)*n);
}
free函數用法( c )：
- 用于釋放malloc(或calloc、realloc)函數給指針變量配置設定的記憶體空間。
- 使用後該指針變量需要重新
指向NULL
#include<stio.h>
#include<stdlib.h>
int main()
{
int *p=( int*)malloc(sizeof(int)) ;
*p=5;
free(p);
p=NULL;
}
②單連結清單的銷毀（頭節點、頭指針、所有元素均銷毀）
【算法思路】
從頭指針開始，依次釋放所有結點
【算法描述】
Status DestoryList_L(LinkList &L)
{
LinkList p; //或Lnode *p;p為指針變量
while(L) //L非空
{
p=L; //p、L指向同一結點
L=L->next; //L指針指向下一個結點
delete p; //删除結點p
}
}
③清空單連結清單 （頭指針、頭節點仍在）
【算法思路】
依次釋放所有結點，并将頭節點指針域設定為空
【算法描述】
Status ClearList(LinkList &L)
{
Lnode *p,*q; //或LinkList p,q;
p=L->next;
while(p) //非空，沒到表尾
{
q=p->next; //q指向p的下一個結點
delete p; //銷毀p
p=q; //使p、q指向同一結點
}
L->next=NULL; //将頭節點指針域置為空
return OK;
④求單連結清單的表長
【算法思路】
從首元結點開始，依次計數所有結點
【算法描述】
int ListLength_L(LinkList L)
{
Linklist p; //或Lnode *p;
p=L->next; //p指向第一個結點
i=0; //計數器i
whilw(p) //周遊單連結清單，統計結點數
{
i++;
p=p->next; //p指向下一個結點
}
}
⑤取第i個元素值 O(n)
【算法思路】
從首元結點出發，順着鍊域next逐個結點向下通路
【算法描述】
Status GetElem(LinkList L,int i,ELemType &e)
{
p=L->next;j=1; //p指向首元結點，計數器j=1
while(p&&j<i)
{
p=p->next; //p指向下一個結點
++j;
}
if(!p||j>i) return ERROR; //i不合法i>n或i≤0
e=p->data; //取第i個結點的資料域
return OK;
}
⑥按值查找 O(n)
【算法思路】
從首元結點出發，依次順着鍊域next向下查，直到查到與e相等或為空
【算法描述】
LNode *LocateElem(LinkList L,ElemType e)
{
p=L->next; //p指向首元結點
while(p&&p->data!=e) //順鍊向後掃描，直到p為空或p所指資料域=e
p=p->next; //p指向下一個結點
return p; //若查找成功傳回e的結點位址p，查找失敗p為NULL
}
⑦插入結點 O(n)
【算法思路】
将值為e的新結點插入到表的第i個結點的位置上，即插入到a(i-1)與a(i)之間,使a(i-1)的指針域指向資料域為e的那個新結點，使資料域為e的這個結點的指針域指向a(i)
【算法描述】
Status ListInsert(LinkList &L,int i,ElemType e)
{
p=L;j=0; //p指向頭結點
while(p&&(j<i-1))
{
p=p->next;++j; //查找第i-1個結點，p指向該結點
}
if(!p||j>i-1) return ERROR; //i>n+1或i<1
s=new LNode; //生成新結點*s
s->data=e; //将結點*s的資料域置為e
s->next=p->next; //将結點*s的指針域指向結點a(i)
p->next=s; //将結點*p的指針域指向結點*s
return OK;
}
⑧删除結點 O(n)
【算法思路】
删除單連結清單第i個結點a(i)并釋放a(i)的空間,使a(i-1)的指針域指向a(i+1)
【算法描述】
Status ListDelete(LinkList &L,int i)
{
p=L;j=0; //p指向頭結點
while((p->next)&&(j<i-1))
{
p=p->next;
++j; //查找第i-1個結點，p指向該結點
}
if(!(p->next)||(j>i-1)) return ERROR; //i>n或i<1時，删除位置不合理
q=p->next; //臨時儲存被删除結點的位址以備釋放
p->next=q->next; //改變删除結點前驅結點的指針域
delete q; //釋放删除結點的空間
return OK;
}
⑨前插法建立單連結清單 O(n)
【算法思路】
逆序輸入n個元素的值，建立帶表頭結點的單連結清單L
【算法描述】
void CreateList_H(LinkList &L,int n)
{
L=new LNode;
L->next=NULL; //先建立一個帶頭節點的空連結清單
for(i=0;i<n;++i)
{
p=new LNode; //生成新結點*p
cin >> p-data; //輸入元素值賦給新結點*p的資料域
p->next=L-next; L->next=p; //将新結點*p插入到頭節點之後
}
}
⑩後插法建立單連結清單 O(n)
【算法思路】
正序輸入n個元素的值，建立帶表頭結點的單連結清單L
【算法描述】
void CreatList_R(LinkList &L,int n)
{
L=new LNode;
L->next=NULL; //先建立一個帶頭節點的空連結清單
r=L; //尾指針r指向頭節點
for(i=0;i<n;++i)
{
p=new LNode; //生成新結點
cin >> p->data; //輸入元素值賦給新結點*p的資料域
p->next=NULL;r->nextp; //将新結點*p插入尾結點*r之後
r=p; //r指向新的尾結點*p
}
}
借鑒：《資料結構》嚴蔚敏