博客为参考《啊哈！算法》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.解密QQ号-队列
假设有一串加密的数字为“6 3 1 7 5 8 9 2 4”。解密的规则为：首先将第1个数删除，紧接着将第2个数放到这串数的末尾，再将第3个数删除并将第4个数放到这串数的末尾，再将第5个数删除，……，直到剩下最后一个数，将最后一个数也删除。按照刚才删除的顺序，把这些删除的数连在一起就是解密后的结果。解密后得到的一串数字应该是“6 1 5 9 4 7 2 8 3”。
如果我们把待解密的数放在数组里，解密的第一步是将第一个数删除，最简单的方法是将所有后面的数都往前面挪动一位，将前面的数覆盖。但是这样的做法很耗费时间：
在这里，我们引入两个整型变量head和tail。head用来记录队列的队首（即第一位），tail用来记录队列的队尾（即最后一位）的下一个位置。
现在有9个数，9个数全部放入队列之后head=1，tail=10；此时head和tail之间的数就是目前队列中“有效”的数。如果要删除一个数的话，就将head++就OK了，这样仍然可以保持head和tail之间的数为目前队列中“有效”的数。这样做虽然浪费了一个空间，却节省了大量的时间，这是非常划算的。新增加一个数也很简单，把需要增加的数放在队尾即q[tail]之后再tail++就OK了。
我们来小结一下，在队首删除一个数的操作是head++：
在队尾增加一个数（假设这个数是x）的操作是q[tail]=x，tail++：
整个解密过程可表示为：
代码实现见下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
int main()
{
int q[102] = {0,6,3,1,7,5,8,9,2,4},head,tail;
int i;
//初始化队列
head = 1;
tail = 10; //队列中已经有9个元素了，tail指向队尾的后一个位置
while(head<tail) //当队列不为空的时候执行循环
{
//打印队首并将队首出队
printf("%d", q[head]);
head++;
//先将新队首的数添加到队尾
q[tail] = q[head];
tail++;
//再将队首出队
head++;
}
getchar();getchar();
return 0;
}
总结一下，队列是一种特殊的线性结构，它只允许在队列的首部（head）进行删除操作，这称为“出队”，而在队列的尾部（tail）进行插入操作，这称为“入队”。当队列中没有元素时（即head==tail），称为空队列。队列遵循“先进先出”（First In First Out，FIFO）原则。
我们可以将队列封装为一个结构体类型，如下：
1
2
3
4
5
6
struct queue
{
int data[100]; //队列的主体，用来存储内容
int head; //队首
int tail; //队尾
};
接着我们使用定义的结构体来实现队列操作：
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
#include <stdio.h>
struct queue
{
int data[100]; //队列的主体，用来存储内容
int head; //队首
int tail; //队尾
};
int main()
{
struct queue q;
int i;
//初始化队列
q.head = 1;
q.tail = 1;
for(i=0; i<9; i++)
{
//依次向队列插入9个数
scanf("%d",&q.data[q.tail]);
q.tail++;
}
while(q.head < q.tail) //当队列不为空的时候执行循环
{
//打印队首并将队首出队
printf("%d",q.data[q.head]);
q.head++;
//先将新队首的数添加到队尾
q.data[q.tail] = q.data[q.head];
q.tail++;
//再将队首出队
q.head++;
}
getchar();getchar();
return 0;
}
实际上，C++的STL库已经有队列的实现，无需我们自己再定义了。
2.解密回文-栈
第1部分介绍了队列，它是一种先进先出的数据结构。还有一种是后进先出的数据结构，它叫做栈。栈限定为只能在一端进行插入和删除操作。
栈的实现也很简单，只需要一个一维数组和一个指向栈顶的变量top就可以了。我们通过top来对栈进行插入和删除操作。
栈究竟有哪些作用呢？我们来看一个例子。“xyzyx”是一个回文字符串，所谓回文字符串就是指正读反读均相同的字符序列。通过栈这个数据结构我们将很容易判断一个字符串是否为回文。实现代码见下：
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
#include <stdio.h>
#include <string.h>
int main()
{
char a[101],s[101];
int i,len,mid,next,top;
gets(a); //读入一行字符串
len = strlen(a); //求字符串的长度
mid = len/2 - 1; //求字符串的中点
top = 0; //栈的初始化
//将mid前的字符依次入栈
for(i=0; i<=mid; i++)
s[++top] = a[i];
//判断字符串的长度是奇数还是偶数，并找出需要进行字符匹配的起始下标
if(len%2 == 0)
next = mid+1;
else
next = mid+2;
//开始匹配
for(i=next; i<len; i++)
{
if(a[i] != s[top])
break;
top--;
}
//如果top值为0，则说明栈内所有的字符都被一一匹配了
if(top == 0)
printf("YES");
else
printf("NO");
getchar();getchar();
return 0;
}
3.纸牌游戏-小猫钓鱼
接下来我们用第1和第2部分学到的知识实现一个“接竹竿”的纸牌小游戏：将一副扑克牌平均分成两份，每人拿一份，两人交替出牌。出牌时，如果某人打出的牌与桌子上某张牌的牌面相同，即可将两张相同的牌及其中间所夹的牌全部取走，并依次放到自己手中牌的末尾。当任意一人手中的牌全部出完时，游戏结束，对手获胜。
假如游戏开始时，玩家1手中有6张牌，顺序为2 4 1 2 5 6，玩家2手中也有6张牌，顺序为3 1 3 5 6 4，最终谁会获胜呢？假设牌面只有1～9。
我们先来分析一下，玩家有两种操作，分别是出牌和赢牌。这恰好对应队列的两个操作，出牌就是出队，赢牌就是入队。而桌子就是一个栈，每打出一张牌放到桌上就相当于入栈。当有人赢牌的时候，依次将牌从桌上拿走，这就相当于出栈。因此我们可以用两个队列，一个栈来实现上述游戏，代码见下：
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
#include <stdio.h>
struct queue
{
int data[1000];
int head;
int tail;
};
struct stack
{
int data[10];
int top;
};
int main()
{
struct queue q1,q2;
struct stack s;
int book[10];
int i,t;
//初始化队列
q1.head = 1; q1.tail = 1;
q2.head = 1; q2.tail = 1;
//初始化栈
s.top = 0;
//初始化用来标记的数组，用来标记哪些牌已经在桌上
for(i=1; i<=9; i++)
book[i] = 0;
//依次向队列插入6个数
for(i=1; i<=6; i++)
{
scanf("%d", &q1.data[q1.tail]);
q1.tail++;
}
for(i=1; i<=6; i++)
{
scanf("%d", &q2.data[q2.tail]);
q2.tail++;
}
while(q1.head<q1.tail && q2.head<q2.tail) //当队列不为空的时候执行循环
{
t = q1.data[q1.head]; //玩家1出一张牌
//判断玩家1当前打出的牌是否能赢牌
if(book[t] == 0) //表明桌上没有牌面为t的牌
{
//玩家1此轮没有赢牌
q1.head++; //玩家1已经打出一张牌，所以要把打出的牌出队
s.top++;
s.data[s.top] = t; //再把打出的牌放到桌上，即入栈
book[t] = 1; //标记桌上现在已经有牌面为t的牌
}
else
{
//玩家1此轮可以赢牌
q1.head++; //玩家1已经打出一张牌，所以要把打出的牌出队
q1.data[q1.tail] = t; //紧接着把打出的牌放到手中牌的末尾
q1.tail++;
while(s.data[s.top] != t) //把桌上可以赢得的牌依次放到手中牌的末尾
{
book[s.data[s.top]] = 0; //取消标记
q1.data[q1.tail] = s.data[s.top]; //依次放入队尾
q1.tail++;
s.top--; //栈中少了一张牌，所以栈顶要减1
}
}
t = q2.data[q2.head]; //玩家2出一张牌
//判断玩家2当前打出的牌是否能赢牌
if(book[t] == 0) //表明桌上没有牌面为t的牌
{
//玩家2此轮没有赢牌
q2.head++; //玩家2已经打出一张牌，所以要把打出的牌出队
s.top++;
s.data[s.top] = t; //再把打出的牌放到桌上，即入栈
book[t] = 1; //标记桌上现在已经有牌面为t的牌
}
else
{
//玩家2此轮可以赢牌
q2.head++; //玩家2已经打出一张牌，所以要把打出的牌出队
q2.data[q2.tail] = t; //紧接着把打出的牌放到手中牌的末尾
q2.tail++;
while(s.data[s.top] != t) //把桌上可以赢得的牌依次放到手中牌的末尾
{
book[s.data[s.top]] = 0; //取消标记
q2.data[q2.tail] = s.data[s.top]; //依次放入队尾
q2.tail++;
s.top--; //栈中少了一张牌，所以栈顶要减1
}
}
}
if(q2.head == q2.tail)
{
printf("player1 win\n");
printf("cards in player1 :");
for(i=q1.head; i<=q1.tail-1; i++)
printf(" %d", q1.data[i]);
if(s.top > 0) //如果桌上有牌则依次输出桌上的牌
{
printf("\ncards on desk :");
for(i=1; i<=s.top; i++)
printf(" %d", s.data[i]);
}
else
printf("\nno cards on desk");
}
else
{
printf("player2 win\n");
printf("cards in player2 :");
for(i=q2.head; i<=q2.tail-1; i++)
printf(" %d", q2.data[i]);
if(s.top > 0) //如果桌上有牌则依次输出桌上的牌
{
printf("\ncards on desk :");
for(i=1; i<=s.top; i++)
printf(" %d", s.data[i]);
}
else
printf("\nno cards on desk");
}
getchar();getchar();
return 0;
}
可以输入以下数据进行验证：
1
2
2 4 1 2 5 6
3 1 3 5 6 4
运行结果是：
1
2
3
player1 win
cards in player1 : 5 6 2 3 1 4 6 5
cards on desk : 2 1 3 4
4.链表
在存储一大波数的时候，我们通常使用的是数组，但有时候数组显得不够灵活，比如下面这个例子。
有一串已经从小到大排好序的数2 3 5 8 9 10 18 26 32。现需要往这串数中插入6使其得到的新序列仍符合从小到大排列。如我们使用数组来实现这一操作，则需要将8和8后面的数都依次往后挪一位，如下：
这样操作显然很耽误时间，如果使用链表则会快很多。那什么是链表呢？请看下图：
此时如果需要在8前面插入一个6，就只需像下图这样更改一下就可以了，而无需再将8及后面的数都依次往后挪一位。这样就很节省时间：
我们使用指针和动态分配内存函数malloc来实现链表。我们想在程序中存储一个整数10，除了使用int a这种方式在内存中申请一块区域来存储，还有另外一种动态存储方法。
1
malloc(4);
malloc函数的作用就是从内存中申请分配指定字节大小的内存空间。上面这行代码就申请了4个字节。如果你不知道int类型是4个字节的，还可以使用sizeof(int)获取int类型所占用的字节数，如下：
1
malloc(sizeof(int));
现在我们已经成功地从内存中申请了4个字节的空间来准备存放一个整数，可是如何来对这个空间进行操作呢？这里我们就需要用一个指针来指向这个空间，即存储这个空间的首地址。
1
2
int* p;
p = (int*)malloc(sizeof(int));
需要注意，malloc函数的返回类型是void*类型。void*表示未确定类型的指针。在C和C++中，void*类型可以强制转换为任何其他类型的指针。上面代码中我们将其强制转化为整型指针，以便告诉计算机这里的4个字节作为一个整体用来存放整数。指针变量存储的是一个内存空间的首地址（第一个字节的地址），但是这个空间占用了多少个字节，用来存储什么类型的数，则是由指针的类型来标明的。这样系统才知道应该取多少个连续内存作为一个数据。
链表的每一个结点都由两个部分组成。左边的部分用来存放具体的数值，本例中用一个整型变量就可以；右边的部分需要存储下一个结点的地址，可以用指针来实现（也称为后继指针）。这里我们定义一个结构体类型来存储这个结点：
1
2
3
4
5
struct node
{
int data;
struct node *next;
}
如何建立链表呢？首先我们需要一个头指针head指向链表的最开始。当链表还没有建立的时候头指针head为空（也可以理解为指向空结点）。
1
2
struct node *head;
head = NULL; //头指针初始为空
现在我们来创建第一个结点，并用临时指针p指向这个结点。
1
2
3
struct node *p;
//动态申请一个空间，用来存放一个结点，并用临时指针p指向这个结点
p = (struct node *)malloc(sizeof(struct node));
接下来分别设置新创建的这个结点的左半部分和右半部分。
1
2
3
scanf("%d",&a);
p->data=a; //将数据存储到当前结点的data域中
p->next=NULL; //设置当前结点的后继指针指向空，也就是当前结点的下一个结点为空
下面来设置头指针并设置新创建结点的*next指向空。头指针的作用是方便以后从头遍历整个链表。
1
2
3
4
if(head == NULL)
head=p; //如果这是第一个创建的结点，则将头指针指向这个结点
else
q->next=p; //如果不是第一个创建的结点，则将上一个结点的后继指针指向当前结点
如果这是第一个创建的结点，则将头指针指向这个结点。
如果不是第一个创建的结点，则将上一个结点的后继指针指向当前结点。
最后要将指针q也指向当前结点，因为待会儿临时指针p将会指向新创建的结点。
1
q=p; //指针q也指向当前结点
假设我们需要往链表中插入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
56
#include <stdio.h>
#include <stdlib.h>
//这里创建一个结构体用来表示链表的结点类型
struct node
{
int data;
struct node *next;
};
int main()
{
struct node *head,*p,*q,*t;
int i,n,a;
scanf("%d",&n);
head = NULL; //头指针初始为空
for(i=1; i<=n; i++) //循环读入n个数
{
scanf("%d",&a);
//动态申请一个空间，用来存放一个结点，并用临时指针p指向这个结点
p = (struct node *)malloc(sizeof(struct node));
p->data = a; //将数据存储到当前结点的data域中
p->next = NULL; //设置当前结点的后继指针指向空，也就是当前结点的下一个结点为空
if(head == NULL)
head = p; //如果这是第一个创建的结点，则将头指针指向这个结点
else
q->next = p; //如果不是第一个创建的结点，则将上一个结点的后继指针指向当前结点
q = p; //指针q也指向当前结点
}
scanf("%d",&a); //读入待插入的数
t = head; //从链表头部开始遍历
while (t != NULL) //当没有到达链表尾部的时候循环
{
if(t->next->data > a) //如果当前结点下一个结点的值大于待插入数，将数插入到中间
{
p = (struct node *)malloc(sizeof(struct node)); //动态申请一个空间，用来存放新增结点
p->data = a;
p->next = t->next; //新增结点的后继指针指向当前结点的后继指针所指向的结点
t->next = p; //当前结点的后继指针指向新增结点
break; //插入完毕退出循环
}
t = t->next; //继续下一个结点
}
//输出链表中的所有数
t = head;
while(t != NULL)
{
printf("%d ",t->data);
t = t->next; //继续下一个结点
}
getchar();getchar();
return 0;
}
需要说明的一点是：上面这段代码没有释放动态申请的空间。
可以输入以下数据进行验证。
1
2
3
9
2 3 5 8 9 10 18 26 32
6
运行结果是：
1
2 3 5 6 8 9 10 18 26 32
5.模拟链表
链表还有另外一种使用数组来实现的方式，叫做模拟链表。
链表中的每一个结点只有两个部分。我们可以用一个数组data来存储每序列中的每一个数。然后再用另一个数组right来存放序列中每一个数右边的数。
上图的两个数组中，第一个整型数组data是用来存放序列中具体数字的，另外一个整型数组right是用来存放当前序列中每一个元素右边的元素在数组data中位置的。right[9]的值为0，就表示当前序列中9号元素的右边没有元素。
现在需要在8前面插入一个6，只需将6直接存放在数组data的末尾即data[10]=6。接下来只需要将right[3]改为10，表示新序列中3号元素右边的元素存放在data[10]中。再将right[10]改为4，表示新序列中10号元素右边的元素存放在data[4]中。这样我们通过right数组就可以从头到尾遍历整个序列了（序列的每个元素的值存放在对应的数组data中），如下。
完整的代码实现如下。
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
#include <stdio.h>
int main()
{
int data[101],right[101];
int i,n,t,len;
//读入已有的数
scanf("%d",&n);
for(i=1; i<=n; i++)
scanf("%d",&data[i]);
len = n;
//初始化数组right
for(i=1; i<=n; i++)
{
if(i != n)
right[i] = i+1;
else
right[i] = 0;
}
//直接在数组data的末尾增加一个数
len++;
scanf("%d",&data[len]);
//从链表的头部开始遍历
t = 1;
while(t != 0)
{
if(data[right[t]] > data[len]) //如果当前结点下一个结点的值大于待插入数，将数插入到中间
{
right[len] = right[t]; //新插入数的下一个结点标号等于当前结点的下一个结点编号
right[t] = len; //当前结点的下一个结点编号就是新插入数的编号
break; //插入完成跳出循环
}
t = right[t];
}
//输出链表中所有的数
t = 1;
while(t != 0)
{
printf("%d ",data[t]);
t = right[t];
}
getchar();
getchar();
return 0;
}
可以输入以下数据进行验证。
1
2
3
9
2 3 5 8 9 10 18 26 32
6
运行结果是：
1
2 3 5 6 8 9 10 18 26 32
使用模拟链表也可以实现双向链表和循环链表。
