第二章, 数据结构
一般都是认为, 程序=算法+数据结构.
个人认为, 数据结构就好比人的骨架(好像不太贴切, 毕竟人的骨架都差不多), 我们的内存就像是各种不同结构的房子, 里面可以构建出不同的空间, 就好比各种各样的数据, int, float, double对应着不同存储空间, 存储在房子里面, 而算法的话, 各种软设施, 比如, 水电煤,网络,暖气等.
这样的组合, 就是我们一套完整的,可以居住的, 令人舒服的房子了. 从代码层面讲,就是一套可以工作, 高效的程序代码.
常见的数据结构都是源于我们生活.
队列, 先进先出,
1.比是食堂里面排队打饭, 排在前面的就先打到饭菜, 然后出队列.
栈, 先进后出,
1.手枪子弹装弹夹, 先进去的子弹最后发射出来;
2.物流装车, 先装的后出, 后装车的先出来.
3.薯片盒子, 最先装进去的最后吃到
链表, 几种常见的链表类型: 单向链表, 双向链表, 循环链表
先来看看:
队列
举个🌰:
解密QQ, 小哈和小哼是同学, 小哼想要小哈的QQ号, 但是美女的QQ哪是这么容易得到的, 小哈就给了小哼一串数字, 但是这个串数字是加密过的, 需要通过一定的规则才能获得.
解密规则:
1.第一个数删除, 第二个数移动到队列尾部; 第三个数删除, 第四个数移动到队列尾部.
2.以此类推, 直到删除所有的数
3.把这些所有删除的数连起来就是小哈的QQ号了.
首先我们需要定一个队列, 这个队列可以存放我们的这个QQ号, 然后需要个头指针(head), 尾指针(tail), 这样我们就可以移动头尾指针来改变队列中的数.
// 结构体
struct queue {
int data[101];
int head;
int tail;
}
// 初始化队列
struct queue q;
q.head =1;
q.tail = 1;
// 完整代码
#include <stdio.h>
int main() {
int i;
struct queue q;
//初始化队列
q.head = 1;
q.tail = 1;
for(i = 0; i <= 100; i++)
q.data[i] = 0;
// 输入加密的QQ号码, 假设加密的QQ号为9位
for (i = 1; i <= 9; i++)
{
scanf("%d", &q.data[q.tail]);
q.tail++;
}
// 开始解密过程
while(q.head != q.tail) {
printf("%d", q.data[q.head]); // 输出正确的数字
q.head++; // 移动头指针
q.data[tail] = q.data[q.head]; // 把第二个数移动到队列尾部
q.head++; // 继续移动头指针
q.tail++; // 移动尾指针
}
getchar();
return 0;
}
这是一个队列的简单应用, 通过 两个指针 来模拟出队, 入队的动作, 提高了效率.
栈
举例🌰2: 判断回文数
回文数, 类似这样的字符串 xyzyx, 就是从头读和从尾读的内容是一样的, 这个就可以用到栈.
// 使用结构体定义栈
struct stack {
int data[101]; // 定义一个101个长度的数组
int top; // 指针, 指向栈顶
}
// 判断一个字符串是不是回文数
include <stdio.h>
include <string.h>
int main() {
char a[101];
int i, mid, next, len;
struct stack s;
// 初始化栈
s.top = -1;
gets(a); // 输入字符串
len = strlen(a);
mid = len/2-1;
// 字符串入栈操作
i = 0;
while (i <= mid) {
s.top++;
s.data[s.top] = a[i];
i++;
}
// 判断字符串的奇偶性
mid = len%2==0?mid+1:mid+2;
// 判断是否是回文数, 出栈操作
for (i = mid ; i < len; i++)
{
if (s[s.top] != a[i]) {
break;
}
s.top--;
}
if (s.top == 0)
printf("%s: 是回文数", s);
else
printf("%s, 不是回文数", s);
getchar();
return 0;
}
下面的例子是, 队列和栈的综合运用
举例🌰3: 纸牌游戏-小猫钓鱼
小哼和小哈一起玩桌游,
游戏规则如下:
一副扑克牌均分, 每个拿一份, 小哼先出一张牌, 然后小哈再出一张牌, 在出牌的过程中, 如果小哼出的牌 和 在桌面上的某一张一样, 那么小哼就可以把桌面上的两张牌以及中间的牌全部取走, 并且放在自己手中牌的尾部. 当任意一个人手中的牌全部出完时, 游戏结束, 对手获胜.
这道题中, 小哼和小哈有两副牌(先入先出). 所以, 我们可以定义两个队列.
struct queue {
int data[101];
int head; // 队头,
int tail; // 队尾
}
// 队列初始化
struct queue q1; // 小哈的牌队列
q1.head = 1;
q1.tail = 1;
// 输入牌, 假设每人有10张牌
for (int i = 1; i <= 10; i++) {
scanf("%d", &q1.data[q1.tail]);
q1.tail++;
}
struct queue q2; // 小哼的牌队列
q2.head = 1;
q2.tail = 1;
// 输入牌, 假设每人有10张牌
for (int i = 1; i <= 10; i++) {
scanf("%d", &q2.data[q2.tail]);
q2.tail++;
}
桌面的牌, 我们使用栈来模拟
struct stack {
int data[100];
int top; // 栈顶指针
}
struct stack s; // 初始化栈信息
// 入栈操作
s.data[s.top] = xx;
s.top++;
判断游戏是否结束
while (q1.head < q1.tail && q2.head < q2.tail) {
}
判断谁输赢
if (q1.head == q1.tail) {
printf("小哼赢拉");
// 输出 小哼手机的牌
while(q2.head != q2.tail) {
printf("%d ", q2.data[q2.head]);
q2.head++;
}
}
else {
printf("小哈赢拉");
// 输出 小哈手机的牌
while(q1.head != q1.tail) {
printf("%d ", q1.data[q1.head]);
q1.head++;
}
}
// 输出桌面上的剩余牌
if (s.top > 0) {
while (s.top > 0) {
printf("%d ", s.data[s.top]);
s.top--;
}
}
else {
printf("桌面上没有牌了!");
}
完整代码
#include <stdio.h>
struct queue {
int data[101];
int head;
int tail;
}
struct stack {
int data[100];
int top;
}
int main() {
struct queue q1, q2;
struct stack s;
int i, t;
int book[10];
q1.head = 1; q1.tail = 1;
q2.head = 1; q2.tail = 1;
s.top = 0;
// 初始化book信息
for( i = 0; i <= 9; i++) {
book[i] = 0;
}
// 输入 小哼牌
for(i = 1; i <= 10; i++ ) {
scanf("%d", &q1.data[q1.tail]);
q1.tail++;
}
// 输入 小哈牌
for(i = 1; i <= 10; i++ ) {
scanf("%d", &q2.data[q2.tail]);
q2.tail++;
}
// 开始出牌
while (q1.head < q1.tail && q2.head < q2.tail) {
// 小哼出牌
t = q1.data[q1.head];
if (book[t] == 0) { // 如果桌面上没有相同的牌, 就需要入栈
book[t] = 1; // 标记牌信息
s.top++;
s.data[s.top] = t; // 牌入栈
q1.head++;// 出队列
}
else {
// 如果栈中有相同的牌, 就需要出栈, 并且保存到q1尾部
q1.data[q1.tail] = t;
q1.tail++;
// 出栈, 把相同t之前的牌都加到q1尾部
while(s.data[s.top] != t) {
book[s.data[s.top]] = 0;
q1.data[q1.tail] = s.data[s.top];
q1.tail++;
s.top--;
}
}
// 小哈出牌
t = q2.data[q2.head];
if (book[t] == 0) { // 如果桌面上没有相同的牌, 就需要入栈
book[t] = 1; // 标记牌信息
s.top++;
s.data[s.top] = t; // 牌入栈
q2.head++; // 出队列
}
else {
// 如果栈中有相同的牌, 就需要出栈, 并且保存到q1尾部
q2.data[q2.tail] = t;
q2.tail++;
// 出栈, 把相同t之前的牌都加到q1尾部
while(s.data[s.top] != t) {
book[s.data[s.top]] = 0;
q2.data[q2.tail] = s.data[s.top];
q2.tail++;
s.top--;
}
}
}
if (q1.head == q1.tail) {
printf("小哼赢拉");
// 输出 小哼手机的牌
while(q2.head != q2.tail) {
printf("%d ", q2.data[q2.head]);
q2.head++;
}
}
else {
printf("小哈赢拉");
// 输出 小哈手机的牌
while(q1.head != q1.tail) {
printf("%d ", q1.data[q1.head]);
q1.head++;
}
}
// 输出桌面上的牌
if (s.top > 0) {
for(i = 1; i <= s.top; i++) {
printf("%d ", s.data[s.top]);
}
}
else {
printf("桌面上没有牌了!');
}
}
链表
使用数组的时候, 数组在内存中的结构是连续的一段内存地址.
当我们需要插入数据的时候, 发现使用数组做数据结构会很困难,
如下图:
图中可以看到每插入一个数据, 要移动之后的n个数据, 效率很差.
链表 就是一个很好的解决这个问题的数据结构.
如下图:
只要我们找到对应结点, 就可以直接在当前的结点处插入新结点.
在定义链表结构之前, 需要了解一下指针的概念:
指针, 存储一个地址, 这个地址所指向对应类型的内存空间的地址,
指针里面的值, 其实是一个内存地址, 而这个内存地址指向了具体数据的存放地方.
*在C中, 有三种作用
1.乘法运算, 如 5 * 5;
2.定义指针变量, int *p;
3.读取指针指向的内存变量中的值, printf("%d", *p);
->, 操作符, 结构体的指针运算符
用来访问结构体内部的成员
链表中节点的结构, 定义如下
struct node {
int data; // 数据
struct node *next; // 指向下个节点的指针
}
// 定义头指针
struct node *head;
head = NULL;
// 动态生成 新的节点
struct node *p;
p = (struct node*)malloc(sizeof(struct node));
scanf(“%d”, &a);
p->data = a;
p->next = NULL;
// 连接节点
if (head == NULL) {
head = p;
}
else {
q->next = p; // q的 下个节点指向新节点p
q = p; // 把q移动到p节点
}
参考代码:
// 链表的生成, 输出
#include <stdio.h>
// 定义链表结点结构体
struct node {
int data;
struct node *next;
}
int main() {
struct node *head, *p, *q, *t;
int i, n, data;
scanf("%d", &n); // 输入链表的个数
for (i = 1; i <= n; i++)
{
// 生成新的节点
p = (struct node *)malloc(sizeof(struct node));
scanf("%d", &data);
p->data = data;
p->next = NULL;
// 判断是否为空节点, 如果为空就把头指针head指向p
if (head == NULL) {
head = p;
}
else {
q->next = p; // 如果头指针不为空, 把q的next指针指向新结点p
}
q = p; // 让q指向p节点, 方便下个结点的接入
}
// 遍历链表
t = head;
while(t = NULL) {
printf("%d ", t->data);
t = t->next;
}
getchar();
return 0;
}
向链表插入数据
// 输入要插入的数据
scanf("%d", &a);
// 遍历链表, 查找需要插入的结点
t = head;
while(t != NULL) {
if (t->next->data > a) {
// 生成一个新结点, 并赋值data数据
p = (struct node*)malloc(sizeof(struct node));
p->data = a;
p->next = t->next; // 把新结点的next指针指向当前结点的next结点
t->next = p; // 把当前结点next指针指向新结点p
break; // 跳出循环
}
t = t->next;
}
模拟链表
使用数组来模拟链接操作.
关键点:
1.定义两个数组, data, right
2.data用于保存数据; right用于保存, 在data中的每个数 右边的数 在data数组中的位置.
还有一个关键点: 数组里面的数据必须是已经排序过的.即为有序数列.
看以下截图:
1.data保存数据.
2.right保存data数据对应结点中 右边的数 在data数组中位置.
参考代码:
#include <stdio.h>
int main()
{
int data[101], right[101];
int i, n, len, t;
scanf("%d", &n); // 输入6;
for (i = 1; i <= n ; i++)
{
scanf("%d", &data[i]); // 输入数据: 2, 3, 5, 8, 17, 32
}
len = n;
// 初始化right数组
for(i = 1; i <=n ; i++)
{
if (i != len) {
right[i] = i;
}
else {
right[i] = 0;
}
}
// 插入新数据
len = len + 1;
scanf("%d", &data[len]);
t = 1;
// 判断新数据应该在插入到哪个位置
while(right[t] != 0) {
if (data[right[t]] > data[len]) { // 如果当前结点的下一个结点大于新结点
right[len] = right[t]; // 新插入数的下一个 结点标号等于当前结点的下一个结点编号
right[t] = len; // 当前结点的下一个结点编就是新数据的编号
break; // 跳出循环
}
t = right[t];
}
// 输出链表数据
t = 1;
while(right[t] != 0)
{
printf("%d", data[right[t]]);
t = right[t];
}
getchar();
return 0;
}
