算法第二课

栈、队列、链表

队列

先进先出,前面出,后面进。队列分列表头,列表尾。使用2个位置标记量分别代表首、尾,当首=尾,标识队列为空队列。每当入数据,尾++,出数据,头++:

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
struct list {
int data[1000];
int head;
int tail;
};
int main(int argc, const char * argv[]) {
struct list list;
// 初始化列表首、尾
list.head = 1;
list.tail = 1;
// 读入数据
for (int i = 1; i <= 5; i ++) {
scanf("%d", &list.data[i]);
list.tail ++;
}
printf("list headNum: %d, tailNum: %d\n", list.data[list.head], list.data[list.tail - 1]);
// 模拟出一个值
list.head ++;
printf("list headNum: %d, tailNum: %d\n", list.data[list.head], list.data[list.tail - 1]);
// 模拟入一个值
list.data[list.tail] = 10;
list.tail ++;
printf("list headNum: %d, tailNum: %d\n", list.data[list.head], list.data[list.tail - 1]);
}

先进后出,只能后边进,从后边出。栈只有栈顶。使用一个数字标记栈顶,入栈,栈顶++,出栈,栈顶—:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct stack {
int data[10];
int top;
};
int main(int argc, const char * argv[]) {
struct stack stack;
// 没有对象
stack.top = 1;
for (int i = 1; i <= 5; i ++) {
scanf("%d", &stack.data[i]);
stack.top = i;
}
// 模拟入栈
stack.data[stack.top + 1] = 7;
stack.top ++;
// 模拟出栈
stack.data[stack.top] = 0;
stack.top --;
}

至此,大家可以模拟一个打扑克的游戏,俗称列火车,假设2个小朋友每个人都有10张排,你一张我一张放到桌子上,如果我出的这张之前也出过,那么2张牌中间的所有的排都是我赢的,谁先出光谁输(简单分析:2个列表存放2个人的扑克,先进后出,1个栈,从顶往底拿牌,赢的牌插入到每个人列表的后边)。

链表

一个链着一个,前一个数中知道下一个链着谁~。基本的形式:

1
2
3
4
struct node {
int data;
struct node *next;
};

如何建立一个链表呢?首先我们需要一个链表头,就像是火车头一样,然后链着一节一节的车厢。当链表还没有建立的时候,头部暂时置为空。

1
struct node *head = NULL; // 初始化;

紧接着,创建第一个结点,并用临时指针p指向这个节点,然后链接到头部:

1
2
3
4
5
6
7
8
9
10
11
12
13
struct node *head = NULL; // 初始化;
struct node *p;
p = (struct node *)malloc(sizeof(struct node));
scanf("%d", &p->data);
p->next = NULL;
if (head == NULL) {
head = p;
} else {
head->next = p;
}

所以我们来看完整的链表构建代码(并往其中插入一个数字):

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
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
int main(int argc, const char * argv[]) {
struct node *head = NULL, *p = NULL, *q = NULL, *t = NULL;
int count, inputData;
printf("Enter Number: ");
scanf("%d", &count);
for (int i = 1; i <= count; i ++) {
scanf("%d", &inputData);
p = (struct node *)malloc(sizeof(struct node));
p->data = inputData;
p->next = NULL;
if (head == NULL) {
head = p;
} else {
q->next = p;
}
q = p;
}
t = head;
int insert;
printf("Enter insertNumber: ");
scanf("%d", &insert);
while (t != NULL) {
if (t->next == NULL || t->next->data > insert) {
p = (struct node *)malloc(sizeof(struct node));
p->data = insert;
p->next = t->next;
t->next = p;
break;
}
t = t->next;
}
t = head;
while (t != NULL) {
printf("%d ", t->data);
t = t->next;
}
}

这里有malloc确没有free,留个问题给大家吧。上边所说的是使用指针的方式来制作链表,但是有些人的指针学的并不好,别急,还有另一种方法,我们使用数组来实现,叫做模拟链表。

模拟链表

如何实现呢,其实原理很简单,我们使用2个数组,第一个数组存放数据,第二个数组同样的位置上存放着该数据右边数据的位置:

1
2
3
4
5
<position>: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
data array: 9, 1, 4, 3, 2, 6, 7, 3, 4
<position> : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
right array: 2, 3, 4, 5, 6, 7, 8, 9, 0

不难理解,如果这个时候我们希望插入一个6到第三个位置该怎么办呢,只需要将数据6放入data array[10]的位置,然后将right array[3] 的值改为10,并且将right array[10]的值改为4就好了。

评论