不带头结点
.h部分
1 #ifndef LIST_H
2 #define LIST_H
3
4 #include
5 typedef int Elemtype; //元素类型
6 typedef int Rank; //秩
7 typedef struct ListNode
8 {
9 Elemtype data;
10 struct ListNode *next;
11 }ListNode, *List;
12
13 void Init(List *L); //初始化
14 bool Empty(List L); //判空
15 int Length(List L); //长度
16 ListNode *GetElem(List L, Rank i); //按位查找
17 ListNode *LocateElem(List L, Elemtype e); //按值查找
18 ListNode *Insert(List *L, int i, Elemtype e); //按位插入
19 ListNode *InsertAsSucc(ListNode *p, Elemtype e); //插入后继
20 ListNode *InsertAsPred(ListNode *p, Elemtype e); //插入前驱
21 ListNode *InsertAsFirst(List *L, Elemtype e); //首节点插入
22 ListNode *InsertAsLast(List *L, Elemtype e); //末节点插入
23 //Elemtype Delete(ListNode *p); //删除节点（除末节点外）
24 Elemtype Delete(List *L, Rank i); //删除节点
25 void Traverse(List L, void (*Visit)(Elemtype e)); //遍历
26 void Clear(List *L); //重置
27 void Destroy(List *L); //销毁
28 void Reverse(List *L); //逆置
29
30 #endif
.c部分
1 #include
2 #include
3
4 static ListNode *NewNode()
5 {
6 ListNode *new_node = (ListNode *)malloc(sizeof(ListNode));
7 assert(new_node);
8 return new_node;
9 }
10
11 void Init(List *L)
12 {
13 *L = NULL;
14 }
15
16 bool Empty(List L)
17 {
18 return !L;
19 }
20
21 int Length(List L)
22 {
23 int len = 0; ListNode *p = L;
24 while (p)
25 {
26 p = p->next;
27 len++;
28 }
29 return len;
30 }
31
32 ListNode *GetElem(List L, Rank i)
33 {
34 int j = 0; ListNode *p = L;
35 while (j < i && p)
36 {
37 p = p->next;
38 j++;
39 }
40 if (j == i)
41 return p;
42 else
43 return NULL;
44 }
45
46 ListNode *LocateElem(List L, Elemtype e)
47 {
48 ListNode *p = L;
49 while (p && p->data != e)
50 p = p->next;
51 return p;
52 }
53
54 ListNode *Insert(List *L, int i, Elemtype e)
55 {
56 if (i < 0)
57 exit(EXIT_FAILURE);
58 else if (i == 0)
59 {
60 ListNode *new_node = NewNode();
61 new_node->data = e;
62 new_node->next = *L;
63 *L = new_node;
64 return new_node;
65 }
66 else
67 {
68 ListNode *p = GetElem(*L, i - 1);
69 assert(p);
70 ListNode *new_node = NewNode();
71 new_node->data = e;
72 new_node->next = p->next;
73 p->next = new_node;
74 return new_node;
75 }
76 }
77
78 ListNode *InsertAsSucc(ListNode *p, Elemtype e)
79 {
80 assert(p);
81 ListNode *new_node = NewNode();
82 new_node->data = e;
83 new_node->next = p->next;
84 p->next = new_node;
85 return new_node;
86 }
87
88 ListNode *InsertAsPred(ListNode *p, Elemtype e)
89 {
90 ListNode *newNode = InsertAsSucc(p, e);
91 newNode->data = p->data;
92 p->data = e;
93 return newNode;
94 }
95
96 ListNode *InsertAsFirst(List *L, Elemtype e)
97 {
98 ///* 方法一 */
99 //InsertAsPred(*L, e);
100
101 /* 方法二 */
102 ListNode *new_node = NewNode();
103 new_node->data = e;
104 new_node->next = *L;
105 *L = new_node;
106 return new_node;
107 }
108
109 ListNode *InsertAsLast(List *L, Elemtype e)
110 {
111 ListNode *new_node = NewNode();
112 new_node->data = e;
113 if (!*L)
114 *L = new_node;
115 else
116 {
117 ListNode *p = *L;
118 while (p->next)
119 p = p->next;
120 p->next = new_node;
121 }
122 new_node->next = NULL;
123 return new_node;
124 }
125
126 //Elemtype Delete(ListNode *p)
127 //{
128 // assert(p);
129 // ListNode *q = p->next; Elemtype e = p->data;
130 // p->data = q->data;
131 // p->next = q->next;
132 // free(q);
133 // return e;
134 //}
135
136 Elemtype Delete(List *L, Rank i)
137 {
138 if (i < 0)
139 exit(EXIT_FAILURE);
140 else if (i == 0)
141 {
142 if (!*L)
143 exit(EXIT_FAILURE);
144 ListNode *p = *L; Elemtype e = (*L)->data;
145 *L = (*L)->next;
146 free(p);
147 return e;
148 }
149 else
150 {
151 ListNode *p = GetElem(*L, i-1);
152 assert(p); assert(p->next);
153 ListNode *q = p->next; Elemtype e = (*L)->next->data;
154 p->next = q->next;
155 free(q);
156 return e;
157 }
158 }
159
160 void Traverse(List L, void (*Visit)(Elemtype e))
161 {
162 ListNode *p = L;
163 while (p)
164 {
165 Visit(p->data);
166 p = p->next;
167 }
168 }
169
170 void Clear(List *L)
171 {
172 ListNode *p = *L;
173 while (p)
174 {
175 *L = (*L)->next;
176 free(p);
177 p = *L;
178 }
179 }
180
181 void Destroy(List *L)
182 {
183 Clear(L);
184 free(*L);
185 }
186
187 void Reverse(List *L)
188 {
189 ListNode *p = *L, *q;
190 *L = NULL;
191 while (p)
192 {
193 q = p->next;
194 p->next = *L;
195 *L = p;
196 p = q;
197 }
198 }
带头结点
.h部分
.c部分