网站建设汇编资料,wordpress 点赞数量翻倍,服饰视频网站建设,成都装修设计公司网站啊哈!算法-第2章-栈、队列、链表 第1节 解密qq号——队列第2节 解密回文——栈第3节 纸牌游戏——小猫钓鱼第4节 链表第5节 模拟链表 第1节 解密qq号——队列
新学期开始了#xff0c;小哈是小哼的新同桌(小哈是个大帅哥哦~)#xff0c;小哼向小哈询问 QQ 号#xff0c; 小… 啊哈!算法-第2章-栈、队列、链表 第1节 解密qq号——队列第2节 解密回文——栈第3节 纸牌游戏——小猫钓鱼第4节 链表第5节 模拟链表 第1节 解密qq号——队列
新学期开始了小哈是小哼的新同桌(小哈是个大帅哥哦~)小哼向小哈询问 QQ 号 小哈当然不会直接告诉小哼啦原因嘛你懂的。所以小哈给了小哼一串加密过的数字同时 小哈也告诉了小哼解密规则。规则是这样的:首先将第 1 个数删除紧接着将第 2 个数放到 这串数的末尾再将第 3 个数删除并将第 4 个数放到这串数的末尾再将第 5 个数删除… 直到剩下最后一个数将最后一个数也删除。按照刚才删除的顺序把这些删除的数连在一 起就是小哈的 QQ 啦。现在你来帮帮小哼吧。小哈给小哼加密过的一串数是“5 3 0 3 9 3 0 1”。
密文删除的数字移到最后的数字QQ号53039301535039301303509301339350901333015090333133509033133150903331350903331150903331
解密的第一步是将第一个数删除你可以想一下如何在数组中删除一个数呢。最简单的 方法是将所有后面的数都往前面挪动一位将前面的数覆盖。就好比我们在排队买票最前 面的人买好离开了后面所有的人就需要全部向前面走一步补上之前的空位但是这样的 做法很耗费时间。 在这里我将引入两个整型变量 head 和 tail。head 用来记录队列的队首(即第一位) tail 用来记录队列的队尾(即最后一位)的下一个位置。你可能会问:为什么 tail 不直接记 录队尾却要记录队尾的下一个位置呢?这是因为当队列中只剩下一个元素时队首和队尾重合会带来一些麻烦。我们这里规定队首和队尾重合时队列为空。 现在有 n 个数n 个数全部放入队列之后 head 0;tail strlen(QQ);此时 head 和 tail 之间的数就是 目前队列中“有效”的数。如果要删除一个数的话就将 head就 OK 了这样仍然可以保 持 head 和 tail 之间的数为目前队列中“有效”的数。这样做虽然浪费了一个空间却节省了 大量的时间这是非常划算的。新增加一个数也很简单把需要增加的数放到队尾即 q[tail] 之后再 tail就 OK 啦。
在队首删除一个数的操作是 head;在队尾增加一个数(假设这个数是 x)的操作是 q[tail] x; tail;以上操作重复执行若干次直到head tail结束即可
#includeiostreamusing namespace std;const int maxn 100;
int head, tail;
char QQ[maxn];
int main(){cin QQ;head 0; // head指向密文的开始位置tail指向密文的结束位置1tail strlen(QQ);// 当队列不为空的时候执行循环while (head tail){// 打印队首并将队首出队cout QQ[head];//先将新队首的数添加到队尾再将队首出队QQ[tail] QQ[head];}return 0;
}队列是一种特 殊的线性结构它只允许在队列的首部(head)进行删除操作这称为“出队”而在队列 的尾部(tail)进行插入操作这称为“入队”。 当队列中没有元素时(即 headtail)称为 空队列。 “先进先出”(First In First OutFIFO)原则。 struct queue{int data[100]; // 队列的主体用来存储内容int head; // 队首int tail; // 队尾
};上面定义了一个结构体类型我们通常将其放在 main 函数的外面请注意结构体的定 义末尾有个;号。struct 是结构体的关键字queue 是我们为这个结构体起的名字。这个结构 体有三个成员分别是:整型数组 data、整型 head 和整型 tail。这样我们就可以把这三个部分 放在一起作为一个整体来对待。你可以这么理解:我们定义了一个新的数据类型这个新类 型非常强大用这个新类型定义出的每一个变量可以同时存储一个整型数组和两个整数。
有了新的结构体类型如何定义结构体变量呢?很简单这与我们之前定义变量的方式 是一样的具体做法如下。
struct queue QQ;请注意 struct queue 需要整体使用不能直接写 queue q;。这样我们就定义了一个结构体 变量 q。这个结构体变量就可以满足队列的所有操作了。那又该如何访问结构体变量的内部 成员呢?可以使用.号它叫做成员运算符或者点号运算符如下:
QQ.head 1;
QQ.tail 1;
scanf(%d, QQ.data[q.tail]);下面这段代码就是使用结构体来实现的队列操作。
#includeiostreamusing namespace std;struct queue{string data; // 队列主体用来存储内容int head, tail; // 队首和队尾
};int main(){queue QQ;cin QQ.data;// 初始化队列QQ.head 0;QQ.tail QQ.data.length();// //当队列不为空的时候执行循环while (QQ.head QQ.tail){cout QQ.data[QQ.head]; //打印队首QQ.head; // 将队首出队QQ.data[QQ.tail] QQ.data[QQ.head]; // 先将新队首的数添加到队尾QQ.head; // 再将队首出队QQ.tail;}return 0;
}第2节 解密回文——栈
栈是后进先出的数据 结构。它限定为只能在一端进行插入和删除操作。比如说有一个小桶小桶的直 径只能放一个小球我们现在小桶内依次放入 2、1、3 号小球。假如你现在需要拿出 2 号小球 那就必须先将 3 号小球拿出再拿出 1 号小球最后才能将 2 号小球拿出来。在刚才取小球的 过程中我们最先放进去的小球最后才能拿出来最后放进去的小球却可以最先拿出来。 栈究竟有哪些作用呢?我们来看一个例子。“xyzyx”是一个回文字符串所谓回文字符 串就是指正读反读均相同的字符序列如“席主席”、“记书记”、“aha”和“ahaha”均是回 文但“ahah”不是回文。通过栈这个数据结构我们将很容易判断一个字符串是否为回文。 首先我们需要读取这行字符串并求出这个字符串的长度。
char arr[100];
int len;
cin arr;
len strlen(arr);如果一个字符串是回文的话那么它必须是中间对称的我们需要求中点即:
mid len / 2 1;接下来就轮到栈出场了。 我们先将 mid 之前的字符全部入栈。因为这里的栈是用来存储字符的所以这里用来实 现栈的数组类型是字符数组即 char s[101];初始化栈很简单top 0;就可以了。入栈的操作 是top; s[top] x(;假设需要入栈的字符暂存在字符变量x中)其实可以简写为arr[top] x;。 现在我们就来将 mid 之前的字符依次全部入栈。
for (int i 0; i mid; i){s[top] arr[i];接下来进入判断回文的关键步骤。将当前栈中的字符依次出栈看看是否能与 mid 之后 的字符一一匹配如果都能匹配则说明这个字符串是回文字符串否则这个字符串就不是回 文字符串。
for(i mid1; i len - 1; i){if (a[i] ! s[top]){break; }top--;
}
if(top 0)printf(YES);
elseprintf(NO);最后如果 top 的值为 0就说明栈内所有的字符都被一一匹配了那么这个字符串就是 回文字符串。完整的代码如下。
#includeiostreamusing namespace std;
const int maxn 200;
int main(){char arr[maxn], s[maxn];int len, mid, next, top;cin arr; // 读入一行字符串len strlen(arr); // 求字符串的长度mid len / 2 - 1; // 求字符串的终点top 0; // 栈的初始化// 将mid前的字符一次入栈for (int i 0; i mid; i){s[top] arr[i];}// 判断字符串的长度是奇数还是偶数并找出需要进行字符匹配的起始下标if (len % 2 0){next mid 1;}else{next mid 2;}// 开始匹配for (int i next; i len; i){if (arr[i] ! s[top]){break;}top--;}// 如果top的值为0则说明栈内所有的字符都被一一匹配了if (top 0){cout YES;}else{cout NO;}return 0;
}第3节 纸牌游戏——小猫钓鱼
星期天小哼和小哈约在一起玩桌游他们正在玩一个非常古怪的扑克游戏——“小猫钓 鱼”。游戏的规则是这样的:将一副扑克牌平均分成两份每人拿一份。小哼先拿出手中的 第一张扑克牌放在桌上然后小哈也拿出手中的第一张扑克牌并放在小哼刚打出的扑克牌 的上面就像这样两人交替出牌。出牌时如果某人打出的牌与桌上某张牌的牌面相同即可将两张相同的牌及其中间所夹的牌全部取走并依次放到自己手中牌的末尾。当任意一人 手中的牌全部出完时游戏结束对手获胜。
假如游戏开始时小哼手中有 6 张牌顺序为 2 4 1 2 5 6小哈手中也有 6 张牌顺序 为 3 1 3 5 6 4最终谁会获胜呢?现在你可以拿出纸牌来试一试。接下来请你写一个程序来 自动判断谁将获胜。这里我们做一个约定小哼和小哈手中牌的牌面只有 1~9。 我们先来分析一下这个游戏有哪几种操作。小哼有两种操作分别是出牌和赢牌。这恰 好对应队列的两个操作出牌就是出队赢牌就是入队。小哈的操作和小哼是一样的。而桌 子就是一个栈每打出一张牌放到桌上就相当于入栈。当有人赢牌的时候依次将牌从桌上 拿走这就相当于出栈。那如何解决赢牌的问题呢?赢牌的规则是:如果某人打出的牌与桌 上的某张牌相同即可将两张牌以及中间所夹的牌全部取走。那如何知道桌上已经有哪些牌 了呢?最简单的方法就是枚举桌上的每一张牌当然也有更好的办法我们待会再说。OK 小结一下我们需要两个队列、一个栈来模拟整个游戏。
首先我们先来创建一个结构体用来实现队列如下。
struct queue{int data[1000];int head;int tail;
}上面代码中 head 用来存储队头tail 用来存储队尾。数组 data 用来存储队列中的元素 数组 data 的大小我预设为 1000其实应该设置得更大一些以防数组越界。当然对于本题 的数据来说 1000 已经足够了。 再创建一个结构体用来实现栈如下。
struct stack{int data[10];int top;
};其中 top 用来存储栈顶数组 data 用来存储栈中的元素大小设置为 10。因为只有 9 种不同的牌面所以桌上最多可能有 9 张牌因此数组大小设置为 10 就够了。提示一下: 为什么不设置为 9 呢?因为 C 数组下标是从 0 开始的。
接下来我们需要定义两个队列变量 q1 和 q2。q1 用来模拟小哼手中的牌q2 用来模拟小 哈手中的牌。定义一个栈变量 s 用来模拟桌上的牌。
struct queue heng, ha;
struct stack table;接下来来初始化一下队列和栈。
// 初始化队列heng, ha为空此时两人手中都还没有牌
heng.head 1;
heng.tail 1;
ha.head 1;
ha.tail 1;
// 初始化栈table为空最开始的时候桌上也没有牌
table.top 0;未完待续… …
第4节 链表
第5节 模拟链表
