1.概述：
C語(yǔ)言中的單向鏈表（單鏈表）是鏈表的一種，其特點(diǎn)是鏈表的鏈接方向是單向的，對(duì)鏈表的訪問(wèn)要通過(guò)順序讀取從頭部開(kāi)始。
鏈表中最簡(jiǎn)單的一種是單向鏈表，它包含兩個(gè)域，一個(gè)信息域和一個(gè)指針域。這個(gè)鏈接指向列表中的下一個(gè)節(jié)點(diǎn)，而最后一個(gè)節(jié)點(diǎn)則指向一個(gè)空值。
如下圖所示：
一個(gè)單向鏈表包含兩個(gè)值: 當(dāng)前節(jié)點(diǎn)的值和一個(gè)指向下一個(gè)節(jié)點(diǎn)的鏈接
一個(gè)單向鏈表的節(jié)點(diǎn)被分成兩個(gè)部分。第一個(gè)部分保存或者顯示關(guān)于節(jié)點(diǎn)的信息，第二個(gè)部分存儲(chǔ)下一個(gè)節(jié)點(diǎn)的地址。單向鏈表只可向一個(gè)方向遍歷。
鏈表最基本的結(jié)構(gòu)是在每個(gè)節(jié)點(diǎn)保存數(shù)據(jù)和到下一個(gè)節(jié)點(diǎn)的地址，在最后一個(gè)節(jié)點(diǎn)保存一個(gè)特殊的結(jié)束標(biāo)記，另外在一個(gè)固定的位置保存指向第一個(gè)節(jié)點(diǎn)的指針，有的時(shí)候也會(huì)同時(shí)儲(chǔ)存指向最后一個(gè)節(jié)點(diǎn)的指針。一般查找一個(gè)節(jié)點(diǎn)的時(shí)候需要從第一個(gè)節(jié)點(diǎn)開(kāi)始每次訪問(wèn)下一個(gè)節(jié)點(diǎn)，一直訪問(wèn)到需要的位置。但是也可以提前把一個(gè)節(jié)點(diǎn)的位置另外保存起來(lái)，然后直接訪問(wèn)。當(dāng)然如果只是訪問(wèn)數(shù)據(jù)就沒(méi)必要了，不如在鏈表上儲(chǔ)存指向?qū)嶋H數(shù)據(jù)的指針。這樣一般是為了訪問(wèn)鏈表中的下一個(gè)或者前一個(gè)節(jié)點(diǎn)。
相對(duì)于雙向鏈表，這種普通的，每個(gè)節(jié)點(diǎn)只有一個(gè)指針的鏈表也叫單向鏈表，或者單鏈表，通常用在每次都只會(huì)按順序遍歷這個(gè)鏈表的時(shí)候（例如圖的鄰接表，通常都是按固定順序訪問(wèn)的）。
2.程序?qū)崿F(xiàn)：
|
1
2
3
4
5
6
7
|
/* c2-2.h 線性表的單鏈表存儲(chǔ)結(jié)構(gòu) */ 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 單鏈表線性表(存儲(chǔ)結(jié)構(gòu)由c2-2.h定義)的基本操作(12個(gè)) */ Status InitList(LinkList *L) { /* 操作結(jié)果：構(gòu)造一個(gè)空的線性表L */ *L=(LinkList)malloc(sizeof(struct LNode)); /* 產(chǎn)生頭結(jié)點(diǎn),并使L指向此頭結(jié)點(diǎn) */ if(!*L) /* 存儲(chǔ)分配失敗 */ exit(OVERFLOW); (*L)->next=NULL; /* 指針域?yàn)榭?*/ return OK; } Status DestroyList(LinkList *L) { /* 初始條件：線性表L已存在。操作結(jié)果：銷毀線性表L */ LinkList q; while(*L) { q=(*L)->next; free(*L); *L=q; } return OK; } Status ClearList(LinkList L) /* 不改變L */ { /* 初始條件：線性表L已存在。操作結(jié)果：將L重置為空表 */ LinkList p,q; p=L->next; /* p指向第一個(gè)結(jié)點(diǎn) */ while(p) /* 沒(méi)到表尾 */ { q=p->next; free(p); p=q; } L->next=NULL; /* 頭結(jié)點(diǎn)指針域?yàn)榭?*/ return OK; } Status ListEmpty(LinkList L) { /* 初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE */ if(L->next) /* 非空 */ return FALSE; else return TRUE; } int ListLength(LinkList L) { /* 初始條件：線性表L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個(gè)數(shù) */ int i=0; LinkList p=L->next; /* p指向第一個(gè)結(jié)點(diǎn) */ while(p) /* 沒(méi)到表尾 */ { i++; p=p->next; } return i; } Status GetElem(LinkList L,int i,ElemType *e) /* 算法2.8 */ { /* L為帶頭結(jié)點(diǎn)的單鏈表的頭指針。當(dāng)?shù)趇個(gè)元素存在時(shí),其值賦給e并返回OK,否則返回ERROR */ int j=1; /* j為計(jì)數(shù)器 */ LinkList p=L->next; /* p指向第一個(gè)結(jié)點(diǎn) */ while(p&&j<i) /* 順指針向后查找,直到p指向第i個(gè)元素或p為空 */ { p=p->next; j++; } if(!p||j>i) /* 第i個(gè)元素不存在 */ return ERROR; *e=p->data; /* 取第i個(gè)元素 */ return OK; } int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)) { /* 初始條件: 線性表L已存在,compare()是數(shù)據(jù)元素判定函數(shù)(滿足為1,否則為0) */ /* 操作結(jié)果: 返回L中第1個(gè)與e滿足關(guān)系compare()的數(shù)據(jù)元素的位序。 */ /* 若這樣的數(shù)據(jù)元素不存在,則返回值為0 */ int i=0; LinkList p=L->next; while(p) { i++; if(compare(p->data,e)) /* 找到這樣的數(shù)據(jù)元素 */ return i; p=p->next; } return 0; } Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e) { /* 初始條件: 線性表L已存在 */ /* 操作結(jié)果: 若cur_e是L的數(shù)據(jù)元素,且不是第一個(gè),則用pre_e返回它的前驅(qū), */ /* 返回OK;否則操作失敗,pre_e無(wú)定義,返回INFEASIBLE */ LinkList q,p=L->next; /* p指向第一個(gè)結(jié)點(diǎn) */ while(p->next) /* p所指結(jié)點(diǎn)有后繼 */ { 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已存在 */ /* 操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼， */ /* 返回OK;否則操作失敗，next_e無(wú)定義，返回INFEASIBLE */ LinkList p=L->next; /* p指向第一個(gè)結(jié)點(diǎn) */ while(p->next) /* p所指結(jié)點(diǎn)有后繼 */ { 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 */ { /* 在帶頭結(jié)點(diǎn)的單鏈線性表L中第i個(gè)位置之前插入元素e */ int j=0; LinkList p=L,s; while(p&&j<i-1) /* 尋找第i-1個(gè)結(jié)點(diǎn) */ { p=p->next; j++; } if(!p||j>i-1) /* i小于1或者大于表長(zhǎng) */ return ERROR; s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新結(jié)點(diǎn) */ s->data=e; /* 插入L中 */ s->next=p->next; p->next=s; return OK; } Status ListDelete(LinkList L,int i,ElemType *e) /* 算法2.10。不改變L */ { /* 在帶頭結(jié)點(diǎn)的單鏈線性表L中，刪除第i個(gè)元素,并由e返回其值 */ int j=0; LinkList p=L,q; while(p->next&&j<i-1) /* 尋找第i個(gè)結(jié)點(diǎn),并令p指向其前趨 */ { p=p->next; j++; } if(!p->next||j>i-1) /* 刪除位置不合理 */ return ERROR; q=p->next; /* 刪除并釋放結(jié)點(diǎn) */ p->next=q->next; *e=q->data; free(q); return OK; } Status ListTraverse(LinkList L,void(*vi)(ElemType)) /* vi的形參類型為ElemType，與bo2-1.c中相應(yīng)函數(shù)的形參類型ElemType&不同 */ { /* 初始條件：線性表L已存在 */ /* 操作結(jié)果:依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)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個(gè)元素的值，建立帶表頭結(jié)構(gòu)的單鏈線性表L */ int i; LinkList p; *L=(LinkList)malloc(sizeof(struct LNode)); (*L)->next=NULL; /* 先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表 */ printf("請(qǐng)輸入%d個(gè)數(shù)據(jù)\n",n); for(i=n;i>0;--i) { p=(LinkList)malloc(sizeof(struct LNode)); /* 生成新結(jié)點(diǎn) */ scanf("%d",&p->data); /* 輸入元素值 */ p->next=(*L)->next; /* 插入到表頭 */ (*L)->next=p; } } void CreateList2(LinkList *L,int n) { /* 正位序(插在表尾)輸入n個(gè)元素的值，建立帶表頭結(jié)構(gòu)的單鏈線性表 */ int i; LinkList p,q; *L=(LinkList)malloc(sizeof(struct LNode)); /* 生成頭結(jié)點(diǎn) */ (*L)->next=NULL; q=*L; printf("請(qǐng)輸入%d個(gè)數(shù)據(jù)\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的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn) */ 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的頭結(jié)點(diǎn) */ Lb=NULL; } void visit(ElemType c) /* ListTraverse()調(diào)用的函數(shù)(類型要一致) */ { printf("%d ",c); } void main() { int n=5; LinkList La,Lb,Lc; printf("按非遞減順序, "); CreateList2(&La,n); /* 正位序輸入n個(gè)元素的值 */ printf("La="); /* 輸出鏈表La的內(nèi)容 */ ListTraverse(La,visit); printf("按非遞增順序, "); CreateList(&Lb,n); /* 逆位序輸入n個(gè)元素的值 */ printf("Lb="); /* 輸出鏈表Lb的內(nèi)容 */ ListTraverse(Lb,visit); MergeList(La,&Lb,&Lc); /* 按非遞減順序歸并La和Lb,得到新表Lc */ printf("Lc="); /* 輸出鏈表Lc的內(nèi)容 */ ListTraverse(Lc,visit); } |
