基础数据结构的实现

发表于 分类于 本文字数： 2.6k 阅读时长 ≈ 9 分钟

前言

啊，终于写完了。

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

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

简单说一下，我用顺序储存结构（数组）和链式储存结构（链表）分别实现了列表List、队列Queue以及栈Stack的ADT，文件如下（后来又增加了二叉搜索树BinarySearchTree，散列表HashTable，最大堆MaxHeap以及加权图WeightedGraph）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Data Structure
├─List
│    ├─main.c
│    ├─List.h
│    ├─ArrayList.c
│    ├─LinkedList.c
│
├─Queue
│    ├─main.c
│    ├─Queue.h
│    ├─ArrayQueue.c
│    ├─LinkedQueue.c
│
├─Stack
|    ├─main.c
|    ├─Stack.h
|    ├─ArrayStack.c
|    ├─LinkedStack.c
|
├─...

List（列表）目录下共有四个文件，其中main.c是驱动代码，用来测试实现的功能。List.h是ArrayList.c和LinkedList.c共用的头文件，用来定义统一的接口，这种接口无关具体的实现，也就是说无论该接口的具体实现是用的数组（ArrayList.c）还是用的链表（LinkedList.c），都不影响使用该接口的程序（main.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
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
/*
列表(List)
对象集：n(n>=0)个元素构成的有序序列 a1, a2, a3 ... an.
操作集：列表 list 属于 list_t ，整数 i 表示元素下标(从0开始)，元素 data 属于 item_t ，基本操作有：
    1. list_t CreateList(void)
    2. void DestroyList(list_t list)
    3. int GetLength(const list_t list)
    4. bool IsFull(const list_t list)
    5. bool IsEmpty(const list_t list)
    6. item_t Get(const list_t list, int i)
    7. int Find(const list_t list, item_t data)
    8. void Insert(list_t list, int i, item_t data)
    9. void Delete(list_t list, int i)
    10. void Print(const list_t list)
    11. void Reverse(list_t list);
*/

#ifndef LIST_H
#define LIST_H

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

#define ERROR (-1)

#define LIST_CAPACITY 128

typedef int item_t;

typedef struct list *list_t;

/*************************************************
  Description:    创建一个空列表
  Parameter:      空
  Return:         一个指向空列表的指针
*************************************************/
list_t CreateList(void);

/*************************************************
  Description:    销毁一个列表 list
  Parameter:      一个指向待销毁列表的指针 list
  Return:         空
*************************************************/
void DestroyList(list_t list);

/*************************************************
  Description:    求列表 list 的长度
  Parameter:      一个指向列表的指针 list
  Return:         列表长度
*************************************************/
int GetLength(const list_t list);

/*************************************************
  Description:    判断列表 list 是否已满
  Parameter:      一个指向列表的指针 list
  Return:         如果列表已满则返回 true ，否则返回 false
*************************************************/
bool IsFull(const list_t list);

/*************************************************
  Description:    判断列表 list 是否已空
  Parameter:      一个指向列表的指针 list
  Return:         如果列表已空则返回 true ，否则返回 false
*************************************************/
bool IsEmpty(const list_t list);

/*************************************************
  Description:    取列表 list 的第 i 个元素
  Parameter:      一个指向列表的指针 list
                  下标 i (0 <= i < GetLength(list))
  Return:         第 i 个元素
*************************************************/
item_t Get(const list_t list, int i);

/*************************************************
  Description:    求元素 data 在列表 list 中的下标
  Parameter:      一个指向列表的指针 list
                  一个待寻找元素 data
  Return:         待寻找元素 data 的下标 i 或者 ERROR
*************************************************/
int Find(const list_t list, item_t data);

/*************************************************
  Description:    在列表 list 的下标为 i 的位置上插入一个元素 data
  Parameter:      一个指向列表的指针 list
                  下标 i (0 <= i <= GetLength(list))
                  待插入元素 data
  Return:         空
*************************************************/
void Insert(list_t list, int i, item_t data);

/*************************************************
  Description:    从列表 list 当中删除下标为 i 的元素
  Parameter:      一个指向列表的指针 list
                  下标 i (0 <= i < GetLength(list))
  Return:         空
*************************************************/
void Delete(list_t list, int i);

/*************************************************
  Description:    输出列表 list 的内容
  Parameter:      一个指向列表的指针 list
  Return:         空
*************************************************/
void Print(const list_t list);

/*************************************************
  Description:    就地逆置列表 list
  Parameter:      一个指向列表的指针 list
  Return:         空
*************************************************/
void Reverse(list_t list);

#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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#include "List.h"

struct list
{
    item_t data;
    list_t next;
};

/*******************************
Helper functions implementation.
*******************************/

/*******************************
Interface functions implementation.
*******************************/

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

    list->next = NULL;

    return list;
}

void DestroyList(list_t list)
{
    if (list)
    {
        list_t current;

        while (list)
        {
            current = list->next;
            free(list);
            list = current;
        }
    }
}

int GetLength(const list_t list)
{
    list_t current = list->next;
    int length = 0;

    while (current)
    {
        current = current->next;
        length++;
    }

    return length;
}

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

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

item_t Get(const list_t list, int i) // list[i]
{
    if (i < 0 || i > (GetLength(list) - 1))
    {
        fprintf(stderr, "Illegal location.\n");
        return ERROR;
    }

    list_t current = list->next;

    for (int j = 0; j < i; ++j)
    {
        current = current->next;
    }

    return current->data;
}

int Find(const 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;
    }
}

void Insert(list_t list, int i, item_t data)
{
    if (IsFull(list))
    {
        fprintf(stderr, "The list is full.\n");
        return;
    }

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

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

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

void Delete(list_t list, int i)
{
    if (IsEmpty(list))
    {
        fprintf(stderr, "The list is empty.\n");
        return;
    }

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

    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);
    del = NULL;
}

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

void Reverse(list_t list)
{
    if (GetLength(list) <= 1)
    {
        return;
    }

    list_t pre = list->next;
    list->next = NULL;
    list_t tmp;

    while (pre)
    {
        tmp = pre;
        pre = pre->next;
        tmp->next = list->next;
        list->next = tmp;
    }
}

简单说几点：

  1. 这些是我写来练习的程序，因此并没有实现所有的链表操作，同时在函数内部有充分的提示信息。
  2. Print函数可以被抽象成一个Traverse函数，接受一个函数指针，这样更加抽象一点。
  3. 变量命名和函数命名很重要。C语言不具有面向对象的特性，因此这里函数采用大驼峰命名法，变量采用小驼峰命名法。
  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
49
50
51
52
53
54
55
#include "List.h"

int main(void)
{
    list_t list1 = CreateList(), list2 = CreateList();
    item_t a[] = {1, 2, 3, 4}, b[] = {233, 666, 888, 999};

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

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

    printf("Reverse list 1.\n");
    Reverse(list1);
    Print(list1);
    printf("\n");

    for (int i = 0; i < GetLength(list2); ++i)
    {
        Insert(list1, i, Get(list2, i));
        printf("Insert an item from list 2 to list 1 [%d]: %d.\n", i, Get(list2, i));
    }
    printf("\n");
    Print(list1);
    printf("\n");

    item_t elem = 999;
    printf("Find item in list 1: item %d at [%d].\n", elem, Find(list1, elem));
    printf("\n");

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

    DestroyList(list1);
    DestroyList(list2);
    printf("Destroy all lists.\n");

    return 0;
}

运行结果

测试的时候只需要

1
gcc main.c LinkedList.c && ./a.exe
就可以了。

运行结果如下：

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
Insert an item to list 1 [0]: 1.
Insert an item to list 1 [1]: 2.
Insert an item to list 1 [2]: 3.
Insert an item to list 1 [3]: 4.

Insert an item to list 2 [0]: 233.
Insert an item to list 2 [1]: 666.
Insert an item to list 2 [2]: 888.
Insert an item to list 2 [3]: 999.

Reverse list 1.
Now print the list elements:
[0]: 4
[1]: 3
[2]: 2
[3]: 1
That's all.

Insert an item from list 2 to list 1 [0]: 233.
Insert an item from list 2 to list 1 [1]: 666.
Insert an item from list 2 to list 1 [2]: 888.
Insert an item from list 2 to list 1 [3]: 999.

Now print the list elements:
[0]: 233
[1]: 666
[2]: 888
[3]: 999
[4]: 4
[5]: 3
[6]: 2
[7]: 1
That's all.

Find item in list 1: item 999 at [3].

Delete an item from list 1.
Delete an item from list 1.
Delete an item from list 1.
Delete an item from list 1.
Delete an item from list 1.
Delete an item from list 1.
Delete an item from list 1.
Delete an item from list 1.
Is list 1 empty? yes.

Destroy all lists.

最后

其他数据结构也是这样的，代码我都放到了GitHub上：Data-Structure。