1.概述：
C語言中的單向鏈表（單鏈表）是鏈表的一種，其特點是鏈表的鏈接方向是單向的，對鏈表的訪問要通過順序讀取從頭部開始。
鏈表中最簡單的一種是單向鏈表，它包含兩個域，一個信息域和一個指針域。這個鏈接指向列表中的下一個節點，而最后一個節點則指向一個空值。
如下圖所示：
一個單向鏈表包含兩個值: 當前節點的值和一個指向下一個節點的鏈接
一個單向鏈表的節點被分成兩個部分。第一個部分保存或者顯示關于節點的信息，第二個部分存儲下一個節點的地址。單向鏈表只可向一個方向遍歷。
鏈表最基本的結構是在每個節點保存數據和到下一個節點的地址，在最后一個節點保存一個特殊的結束標記，另外在一個固定的位置保存指向第一個節點的指針，有的時候也會同時儲存指向最后一個節點的指針。一般查找一個節點的時候需要從第一個節點開始每次訪問下一個節點，一直訪問到需要的位置。但是也可以提前把一個節點的位置另外保存起來，然后直接訪問。當然如果只是訪問數據就沒必要了，不如在鏈表上儲存指向實際數據的指針。這樣一般是為了訪問鏈表中的下一個或者前一個節點。
相對于雙向鏈表，這種普通的，每個節點只有一個指針的鏈表也叫單向鏈表，或者單鏈表，通常用在每次都只會按順序遍歷這個鏈表的時候（例如圖的鄰接表，通常都是按固定順序訪問的）。
2.程序實現：
|
1
2
3
4
5
6
7
|
/* c2-2.h 線性表的單鏈表存儲結構 */ struct LNode { ElemType data; struct LNode *next; }; typedef struct LNode *LinkList; /* 另一種定義LinkList的方法 */ |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
/* bo2-2.c 單鏈表線性表(存儲結構由c2-2.h定義)的基本操作(12個) */ Status InitList(LinkList *L) { /* 操作結果：構造一個空的線性表L */ *L=(LinkList)malloc(sizeof(struct LNode)); /* 產生頭結點,并使L指向此頭結點 */ if(!*L) /* 存儲分配失敗 */ exit(OVERFLOW); (*L)->next=NULL; /* 指針域為空 */ return OK; } Status DestroyList(LinkList *L) { /* 初始條件：線性表L已存在。操作結果：銷毀線性表L */ LinkList q; while(*L) { q=(*L)->next; free(*L); *L=q; } return OK; } Status ClearList(LinkList L) /* 不改變L */ { /* 初始條件：線性表L已存在。操作結果：將L重置為空表 */ LinkList p,q; p=L->next; /* p指向第一個結點 */ while(p) /* 沒到表尾 */ { q=p->next; free(p); p=q; } L->next=NULL; /* 頭結點指針域為空 */ return OK; } Status ListEmpty(LinkList L) { /* 初始條件：線性表L已存在。操作結果：若L為空表，則返回TRUE，否則返回FALSE */ if(L->next) /* 非空 */ return FALSE; else return TRUE; } int ListLength(LinkList L) { /* 初始條件：線性表L已存在。操作結果：返回L中數據元素個數 */ int i=0; LinkList p=L->next; /* p指向第一個結點 */ while(p) /* 沒到表尾 */ { i++; p=p->next; } return i; } Status GetElem(LinkList L,int i,ElemType *e) /* 算法2.8 */ { /* L為帶頭結點的單鏈表的頭指針。當第i個元素存在時,其值賦給e并返回OK,否則返回ERROR */ int j=1; /* j為計數器 */ LinkList p=L->next; /* p指向第一個結點 */ while(p&&j<i) /* 順指針向后查找,直到p指向第i個元素或p為空 */ { p=p->next; j++; } if(!p||j>i) /* 第i個元素不存在 */ return ERROR; *e=p->data; /* 取第i個元素 */ return OK; } int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)) { /* 初始條件: 線性表L已存在,compare()是數據元素判定函數(滿足為1,否則為0) */ /* 操作結果: 返回L中第1個與e滿足關系compare()的數據元素的位序。 */ /* 若這樣的數據元素不存在,則返回值為0 */ int i=0; LinkList p=L->next; while(p) { i++; if(compare(p->data,e)) /* 找到這樣的數據元素 */ return i; p=p->next; } return 0; } Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e) { /* 初始條件: 線性表L已存在 */ /* 操作結果: 若cur_e是L的數據元素,且不是第一個,則用pre_e返回它的前驅, */ /* 返回OK;否則操作失敗,pre_e無定義,返回INFEASIBLE */ LinkList q,p=L->next; /* p指向第一個結點 */ while(p->next) /* p所指結點有后繼 */ { q=p->next; /* q為p的后繼 */ if(q->data==cur_e) { *pre_e=p->data; return OK; } p=q; /* p向后移 */ } return INFEASIBLE; } Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e) { /* 初始條件：線性表L已存在 */ /* 操作結果：若cur_e是L的數據元素，且不是最后一個，則用next_e返回它的后繼， */ /* 返回OK;否則操作失敗，next_e無定義，返回INFEASIBLE */ LinkList p=L->next; /* p指向第一個結點 */ while(p->next) /* p所指結點有后繼 */ { if(p->data==cur_e) { *next_e=p->next->data; return OK; } p=p->next; } return INFEASIBLE; } Status ListInsert(LinkList L,int i,ElemType e) /* 算法2.9。不改變L */ { /* 在帶頭結點的單鏈線性表L中第i個位置之前插入元素e */ int j=0; LinkList p=L,s; while(p&&j<i-1) /* 尋找第i-1個結點 */ { p=p->next; j++; } if(!p||j>i-1) /* i小于1或者大于表長 */ return ERROR; s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新結點 */ s->data=e; /* 插入L中 */ s->next=p->next; p->next=s; return OK; } Status ListDelete(LinkList L,int i,ElemType *e) /* 算法2.10。不改變L */ { /* 在帶頭結點的單鏈線性表L中，刪除第i個元素,并由e返回其值 */ int j=0; LinkList p=L,q; while(p->next&&j<i-1) /* 尋找第i個結點,并令p指向其前趨 */ { p=p->next; j++; } if(!p->next||j>i-1) /* 刪除位置不合理 */ return ERROR; q=p->next; /* 刪除并釋放結點 */ p->next=q->next; *e=q->data; free(q); return OK; } Status ListTraverse(LinkList L,void(*vi)(ElemType)) /* vi的形參類型為ElemType，與bo2-1.c中相應函數的形參類型ElemType&不同 */ { /* 初始條件：線性表L已存在 */ /* 操作結果:依次對L的每個數據元素調用函數vi()。一旦vi()失敗,則操作失敗 */ LinkList p=L->next; while(p) { vi(p->data); p=p->next; } printf("\n"); return OK; } |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
/* algo2-5.c 主程序 */ #include"c1.h" typedef int ElemType; #include"c2-2.h" #include"bo2-2.c" void CreateList(LinkList *L,int n) /* 算法2.11 */ { /* 逆位序(插在表頭)輸入n個元素的值，建立帶表頭結構的單鏈線性表L */ int i; LinkList p; *L=(LinkList)malloc(sizeof(struct LNode)); (*L)->next=NULL; /* 先建立一個帶頭結點的單鏈表 */ printf("請輸入%d個數據\n",n); for(i=n;i>0;--i) { p=(LinkList)malloc(sizeof(struct LNode)); /* 生成新結點 */ scanf("%d",&p->data); /* 輸入元素值 */ p->next=(*L)->next; /* 插入到表頭 */ (*L)->next=p; } } void CreateList2(LinkList *L,int n) { /* 正位序(插在表尾)輸入n個元素的值，建立帶表頭結構的單鏈線性表 */ int i; LinkList p,q; *L=(LinkList)malloc(sizeof(struct LNode)); /* 生成頭結點 */ (*L)->next=NULL; q=*L; printf("請輸入%d個數據\n",n); for(i=1;i<=n;i++) { p=(LinkList)malloc(sizeof(struct LNode)); scanf("%d",&p->data); q->next=p; q=q->next; } p->next=NULL; } void MergeList(LinkList La,LinkList *Lb,LinkList *Lc)/* 算法2.12 */ { /* 已知單鏈線性表La和Lb的元素按值非遞減排列。 */ /* 歸并La和Lb得到新的單鏈線性表Lc，Lc的元素也按值非遞減排列 */ LinkList pa=La->next,pb=(*Lb)->next,pc; *Lc=pc=La; /* 用La的頭結點作為Lc的頭結點 */ while(pa&&pb) if(pa->data<=pb->data) { pc->next=pa; pc=pa; pa=pa->next; } else { pc->next=pb; pc=pb; pb=pb->next; } pc->next=pa?pa:pb; /* 插入剩余段 */ free(*Lb); /* 釋放Lb的頭結點 */ Lb=NULL; } void visit(ElemType c) /* ListTraverse()調用的函數(類型要一致) */ { printf("%d ",c); } void main() { int n=5; LinkList La,Lb,Lc; printf("按非遞減順序, "); CreateList2(&La,n); /* 正位序輸入n個元素的值 */ printf("La="); /* 輸出鏈表La的內容 */ ListTraverse(La,visit); printf("按非遞增順序, "); CreateList(&Lb,n); /* 逆位序輸入n個元素的值 */ printf("Lb="); /* 輸出鏈表Lb的內容 */ ListTraverse(Lb,visit); MergeList(La,&Lb,&Lc); /* 按非遞減順序歸并La和Lb,得到新表Lc */ printf("Lc="); /* 輸出鏈表Lc的內容 */ ListTraverse(Lc,visit); } |
