线性表、栈以及队列的实现

前言

啊,终于写完了。

我是指,那9个.c文件以及3个.h文件。

其实,前几天就写完了,只是写完后发现似乎可以再优化一下,于是就在重构代码的路上一去不复返了……

简单说一下,我用顺序储存结构(数组)和链式储存结构(链表)分别实现了线性表、栈以及队列的ADT,文件如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
├─LinearList
│ ├─driver.c
│ ├─LinearList.h
│ ├─LinearList_Array.c
│ ├─LinearList_Linked.c

├─Queue
│ ├─driver.c
│ ├─Queue.h
│ ├─Queue_Array.c
│ ├─Queue_Linked.c

└─Stack
├─driver.c
├─Stack.h
├─Stack_Array.c
├─Stack_Linked.c

LinearList(线性表)目录下共有四个文件,其中driver.c是驱动代码,用来测试实现的功能。LinearList.hLinearList_Array.cLinearList_Linked.c共用的头文件,用来定义统一的接口,这种接口无关具体的实现,也就是说无论该接口的具体实现是用的数组(LinearList_Array.c)还是用的链表(LinearList_Linked.c),都不影响使用该接口的程序(driver.c)。

如果是线性表或者是栈还好,很容易就统一了,但是队列就很麻烦,因为队列用数组实现的时候并没有指向每一个元素的指针,而用链表实现的时候不仅有链表内部的指针,还有一个包含两个指针的结构体分别指向队头和队尾,而这个指针结构体也是用一个指针来表示的,换句话说就是一个指针指向包含两个指针的结构体,这两个指针又分别指向一个链表的头和尾,而另一边只是一个数组以及两个表示头和尾的整数组成的结构体,所以统一起来很麻烦,也没有专业的老师指导,全靠我自己瞎想,不过好在我花了差不多两天的时间最终还是统一了。

我又有完美强迫症,总想着优化优化再优化,结果就是把一个简单的写来练习的程序硬是重构成了比较标准的ADT接口包……

一开始每种ADT只有两个.c文件(数组实现和链表实现),那两个.c文件重构了好几次然后拆分成四个文件:驱动代码,头文件,数组实现的代码和链表实现的代码,这期间的曲折我就不细说了,总之我一个人坎坎坷坷总算完成了……人生太难了。

这里我就只把线性表的头文件和链表实现的代码以及驱动代码贴出来简单说一下,不可能全部贴出来的,太多了。

头文件

头文件如下:

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
/*
线性表(Linear List)
对象集:n(n>=0)个元素构成的有序序列 a1, a2, a3 ... an
操作集:线性表 list 属于 list_t ,整数 i 表示元素下标(从0开始),元素 data 属于 item_t ,基本操作有:
1. list_t CreateList(void)
2. int GetLength(list_t list)
3. bool IsFull(list_t list)
4. bool IsEmpty(list_t list)
5. item_t FindByIndex(list_t list, int i)
6. int Find(list_t list, item_t data)
7. bool Insert(list_t list, int i, item_t data)
8. bool Delete(list_t list, int i)
9. void Print(list_t list)
10. bool LinkList(list_t list1, list_t list2)
*/

#ifndef LINEAR_LIST_H
#define LINEAR_LIST_H

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

#define SIZE 100
#define ERROR (-1)

typedef int item_t;

typedef struct list * list_t;

list_t CreateList(void);
int GetLength(list_t list);
bool IsFull(list_t list);
bool IsEmpty(list_t list);
item_t FindByIndex(list_t list, int i);
int Find(list_t list, item_t data);
bool Insert(list_t list, int i, item_t data);
bool Delete(list_t list, int i);
void Print(list_t list);
bool LinkList(list_t list1, list_t list2);

#endif

其中item_t是抽象的,用户需要不同的数据类型的时候只需要在头文件这里改一下就可以了,数组实现或链表实现都不用改。

链表实现

下面看看链表实现的代码:

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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include "LinearList.h"

struct list
{
item_t data;
list_t next;
};

list_t CreateList(void)
{
list_t list = (list_t)malloc(sizeof(struct list));
if (list == NULL)
{
fprintf(stderr, "ERROR: There was not enough memory.\n");
exit(-2);
}

list->next = NULL;
printf("Create a new list successful.\n");
return list;
}

int GetLength(list_t list)
{
list_t current = list->next;
int length = 0;
while (current)
{
current = current->next;
length++;
}
return length;
}

bool IsFull(list_t list)
{
return GetLength(list) >= SIZE;
}

bool IsEmpty(list_t list)
{
return list->next == NULL;
}

item_t FindByIndex(list_t list, int i)
{
if (i < 0 || i > (GetLength(list) - 1))
{
printf("Illegal location.\n");
return ERROR;
}

list_t current = list->next;
int j = 0;
while (current != NULL && j < i)
{
current = current->next;
j++;
}
if (current)
{
return current->data;
}
else
{
return ERROR;
}
}

int Find(list_t list, item_t data)
{
int index = 0;
list_t current = list->next;
while (current != NULL && current->data != data)
{
current = current->next;
index++;
}
if (current)
{
return index;
}
else
{
return ERROR;
}
}

bool Insert(list_t list, int i, item_t data)
{
if (IsFull(list))
{
printf("The list is full.\n");
return false;
}

if (i < 0 || i > GetLength(list))
{
printf("Illegal location.\n");
return false;
}

list_t new = (list_t)malloc(sizeof(struct list));
if (new == NULL)
{
fprintf(stderr, "ERROR: There was not enough memory.\n");
exit(-2);
}

list_t tmp = list;
for (int j = 0; j < i; j++)
{
tmp = tmp->next;
}
new->data = data;
new->next = tmp->next;
tmp->next = new;
return true;
}

bool Delete(list_t list, int i)
{
if (IsEmpty(list))
{
printf("The list is empty.\n");
return false;
}

if (i < 0 || i > (GetLength(list) - 1))
{
printf("Illegal location.\n");
return false;
}

list_t tmp = list;
for (int j = 0; j < i; j++)
{
tmp = tmp->next;
}
list_t del = tmp->next;
tmp->next = del->next;
free(del);
return true;
}

void Print(list_t list)
{
printf("Now print the list elements:\n");
list_t tmp = list->next;
for (int i = 0; i < GetLength(list); i++)
{
printf("%d: %d\n", i, tmp->data);
tmp = tmp->next;
}
printf("That's all.\n");
}

bool LinkList(list_t list1, list_t list2)
{
if (list1 == list2)
{
printf("Do you want to make a circular linked list?\n");
return false;
}

list_t tail = list1;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = list2->next;
free(list2);
list2 = NULL;
printf("Link list 1 and list 2 successful.\n");
return true;
}

简单说几点:

  1. 其实结构体的定义应该放在头文件里的,但是为了让数组和链表都可以使用一个统一的头文件,我只能把它放在具体的实现里。
  2. 这些是我写来练习的程序,因此并没有实现所有的链表操作,同时在函数内部有充分的提示信息。
  3. 变量命名和函数命名很重要。C语言不具有面向对象的特性,因此这里函数采用大驼峰命名法,变量采用小驼峰命名法。别小看这一点,好的命名一看就懂,比如GetLength()表示获取长度,LinkList()表示连接链表,new表示待插入的新结点,del表示待删除的结点,tail表示尾结点等等。网上太多代码的命名都乱七八糟的。
  4. 大家都知道,malloc()free()一定要成对出现、一一对应。但是我看网上好多人都不知道free()p = NULL也一定要成对存在,也就是说释放一个(全局)指针变量p指向的内存空间后要立刻把它指向NULL。为什么呢?因为释放前后,p所指向的内存空间是一样的。所以释放后p所指向的仍然是那块内存空间。可是释放后的那块内存空间已经不属于p了,该内存空间可能会被分配给其他函数使用。如果其他函数在那块内存空间存放了值,而你现在不小心再用p往里面写入了数据就会把那个值给覆盖了。所以当内存空间被释放后,要立刻把指针变量指向NULL
  5. 使用malloc()申请了内存空间之后一定要紧接着用if (p == NULL)判断申请成功没。好多人申请就申请了,都不检查一下,虽然一般不会出错,可是保持良好的编程习惯以后写程序不容易出Bug。
  6. 肯定还有不足的地方,但是我不想再花时间改了。

驱动代码

最后是驱动代码:

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
#include "LinearList.h"

int main(int argc, char const *argv[])
{
list_t list1 = CreateList(), list2 = CreateList();
item_t a[] = {1, 2, 3, 4}, b[] = {233, 666, 888, 999};
printf("\n");

for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
if (Insert(list1, i, a[i]))
{
printf("Insert an item to list 1: %d.\n", a[i]);
}
else
{
printf("Failed to insert items.\n");
}
}
printf("\n");

for (int i = 0; i < sizeof(b) / sizeof(b[0]); i++)
{
if (Insert(list2, i, b[i]))
{
printf("Insert an item to list 2: %d.\n", b[i]);
}
else
{
printf("Failed to insert items.\n");
}
}
printf("\n");

LinkList(list1, list2);
Print(list1);
printf("\n");

int length = GetLength(list1);
for (int i = 0; i < length; i++)
{
printf("Delete an item %s.\n", Delete(list1, 0) ? "successful" : "failed");
}
printf("The list is empty? %s.\n", IsEmpty(list1) ? "yes" : "no");

getchar();
return 0;
}

运行结果

测试的时候只需要

1
gcc driver.c LinearList_Array.c && ./a.exe

或者
1
gcc driver.c LinearList_Linked.c && ./a.exe

就可以了。

运行结果如下:

最后

栈和队列也是这样的,代码我都放到了GitHub上:Data-Structure

呼……最近又开始忙了,不知道啥时候再更新。

就写到这吧。


0%