0%

『算法导论』第 10 章:基本数据结构

主要内容

本章介绍几种基本的数据结构:栈、队列、链表和有根树。此外还介绍由数组构造对象和指针的方法。

栈和队列

实现的是一种后进先出(last-in, first-out, LIFO)策略。队列实现的是一种先进先出(first-in, first-out, FIFO)策略。下面通过数组来实现它们。

栈的INSERT操作称为压入(PUSH),而无元素参数的DELETE操作称为弹出(POP)。可以用数组\(S[1..n]\)实现一个最多容纳\(n\)个元素的栈。实现代码如下:

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
typedef struct __stack {
int top; // 指向栈顶
int capacity; // 最大容量
int *data; // 数据空间
} Stack;

void StackInit(Stack *stk, int n)
{
stk->data = malloc(n * sizeof(int));
if (stk->data == NULL) {
printf("Alloc failed!\n");
exit(1);
}
stk->capacity = n;
stk->top = 0;
}

int StackEmpty(Stack *stk)
{
if (stk->top == 0) {
return true;
}
return false;
}

int StackFull(Stack *stk)
{
if (stk->top == stk->capacity) {
return true;
}
return false;
}

void Push(Stack *stk, int x)
{
if (StackFull(stk)) {
printf("Overflow!\n");
exit(1);
}
++stk->top;
stk->data[stk->top] = x;
}

int Pop(Stack *stk)
{
if (StackEmpty(stk)) {
printf("Underflow!\n");
exit(1);
} else {
--stk->top;
return stk->data[stk->top+1];
}
}

队列上的INSERT操作称之为入队(ENQUEUE),无元素参数的DELETE操作称之为出队(DEQUEUE)。队列有队头(head)和队尾(tail),元素入队时,它被放到队尾的位置;而出队的元素总是队头的那个。可以用数组\(Q[1..n]\)实现一个最多容纳\(n-1\)个元素的环形队列。代码实现如下:

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
typedef struct __queue {
int head; // 队头
int tail; // 队尾
int capacity; // 队列容量
int *data; // 数据空间
} Queue;

void QueueInit(Queue *q, int n)
{
q->data = malloc(n * sizeof(int));
if (q->data == NULL) {
printf("Alloc failed!\n");
exit(1);
}
q->capacity = n - 1; // 空间为n的数组只能容纳n-1个队列元素
q->head = 0;
q->tail = 0;
}

int QueueFull(Queue *q)
{
if (q->head == q->tail + 1) {
return TRUE;
}
return FALSE;
}

int QueueEmpty(Queue *q)
{
if (q->head == q->tail) {
return TRUE;
}
return FALSE;
}

void Enqueue(Queue *q, int x)
{
if (QueueFull(q)) {
printf("Overflow!\n");
exit(1);
}

q->data[q->tail] = x;
if (q->tail == q->capacity) {
q->tail = 0;
} else {
++q->tail;
}
}

int Dequeue(Queue *q)
{
if (QueueEmpty(q)) {
printf("Underflow!\n");
exit(1);
}

x = q->data[q->head];
if (q->head == q->capacity) {
q->head = 0;
} else {
++q->head;
}

return x;
}

链表

介绍了双向链表,这部分内容可以参考本站的另一篇文章Linux内核中的链表

指针和对象的实现

略。

有根树的表示

略。

习题解答

待完成。