啊哈!算法-第2章-栈、队列、链表

啊哈!算法-第2章-栈、队列、链表

  • 第1节 解密qq号——队列
  • 第2节 解密回文——栈
  • 第3节 纸牌游戏——小猫钓鱼
  • 第4节 链表
  • 第5节 模拟链表

第1节 解密qq号——队列

  1. 新学期开始了,小哈是小哼的新同桌(小哈是个大帅哥哦~),小哼向小哈询问 QQ 号, 小哈当然不会直接告诉小哼啦,原因嘛你懂的。所以小哈给了小哼一串加密过的数字,同时 小哈也告诉了小哼解密规则。规则是这样的:首先将第 1 个数删除,紧接着将第 2 个数放到 这串数的末尾,再将第 3 个数删除并将第 4 个数放到这串数的末尾,再将第 5 个数删除… 直到剩下最后一个数,将最后一个数也删除。按照刚才删除的顺序,把这些删除的数连在一 起就是小哈的 QQ 啦。现在你来帮帮小哼吧。小哈给小哼加密过的一串数是“5 3 0 3 9 3 0 1”。
密文删除的数字移到最后的数字QQ号
53039301535
03930130350
93013393509
01333015090
33313350903
31331509033
3135090333
1150903331

解密的第一步是将第一个数删除,你可以想一下如何在数组中删除一个数呢。最简单的 方法是将所有后面的数都往前面挪动一位,将前面的数覆盖。就好比我们在排队买票,最前 面的人买好离开了,后面所有的人就需要全部向前面走一步,补上之前的空位,但是这样的 做法很耗费时间。
在这里,我将引入两个整型变量 head 和 tail。head 用来记录队列的队首(即第一位), tail 用来记录队列的队尾(即最后一位)的下一个位置。你可能会问:为什么 tail 不直接记 录队尾,却要记录队尾的下一个位置呢?这是因为当队列中只剩下一个元素时,队首和队尾重合会带来一些麻烦。我们这里规定队首和队尾重合时,队列为空。
现在有 n 个数,n 个数全部放入队列之后 head = 0;tail = strlen(QQ);此时 head 和 tail 之间的数就是
目前队列中“有效”的数。如果要删除一个数的话,就将 head++就 OK 了,这样仍然可以保 持 head 和 tail 之间的数为目前队列中“有效”的数。这样做虽然浪费了一个空间,却节省了 大量的时间,这是非常划算的。新增加一个数也很简单,把需要增加的数放到队尾即 q[tail] 之后再 tail++就 OK 啦。

  1. 在队首删除一个数的操作是 head++;
  2. 在队尾增加一个数(假设这个数是 x)的操作是 q[tail] = x; tail++;
  3. 以上操作重复执行若干次,直到head < tail结束即可
#include<iostream>using 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)进行插入操作,这称为“入队”。
当队列中没有元素时(即 head==tail),称为 空队列。
“先进先出”(First In First Out,FIFO)原则。

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]);

下面这段代码就是使用结构体来实现的队列操作。

#include<iostream>using 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 = mid+1; i <= len - 1; i++){if (a[i] != s[top]){break; }top--; 
}
if(top == 0)printf("YES");
elseprintf("NO");

最后如果 top 的值为 0,就说明栈内所有的字符都被一一匹配了,那么这个字符串就是 回文字符串。完整的代码如下。

#include<iostream>using 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节 模拟链表

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/335849.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

有限元之抛物型方程初边值问题解法

目录 一、原方程的变分形式 二、有限元法进行空间半离散 三、差分法进行时间全离散 四、相关量的数值计算 五、编程时的说明 六、算例实现 6.1 C代码 6.2 计算结果 本节我们将采用有限元法联合差分法来数值求解抛物型方程的初边值问题&#xff1a; 其中常数。 一、原方…

Element-UI 入门指南:从安装到自定义主题的详细教程

Element-UI 是一个基于 Vue.js 的前端组件库&#xff0c;它提供了丰富的 UI 组件&#xff0c;可以帮助开发者快速构建高质量的用户界面。以下是使用 Element-UI 的快速入门指南&#xff1a; 安装 Element-UI Element-UI 是一个基于 Vue.js 的组件库&#xff0c;它提供了丰富的…

LangChain入门开发教程(一):Model I/O

官方文档&#xff1a;https://python.langchain.com/docs/get_started/introduction/ LangChain是一个能够利用大语言模型&#xff08;LLM&#xff0c;Large Language Model&#xff09;能力进行快速应用开发的框架&#xff1a; 高度抽象的组件&#xff0c;可以像搭积木一样&a…

LeetCode2336无限集中的最小数字

题目描述 现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, …] 。实现 SmallestInfiniteSet 类&#xff1a;SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。int popSmallest() 移除 并返回该无限集中的最小整数。void addBack(int num) 如果正整数 …

基于Python实现 HR 分析(逻辑回归和基于树的机器学习)【500010104】

介绍 数据集说明 此数据集包含与员工有关的综合属性集合&#xff0c;从人口统计细节到与工作相关的因素。该分析的主要目的是预测员工流动率并辨别导致员工流失的潜在因素。 在这个数据集中&#xff0c;有14,999行&#xff0c;10列&#xff0c;以及这些变量&#xff1a;满意度…

Python轻量级的插件框架库之pluginbase使用详解

概要 在软件开发中,插件系统是一个常见的需求。插件系统允许开发者动态加载和卸载功能模块,从而提高应用程序的灵活性和可扩展性。Python的pluginbase库是一个轻量级的插件框架,旨在简化插件系统的构建过程。pluginbase库提供了一套简单易用的API,使开发者能够快速集成插件…

leetCode-hot100-数组专题之子数组+二维数组

数组专题之子数组二维数组 子数组238.除自身以外数组的乘积560.和为K的子数组 二维数组48.旋转图像 子数组 数组的子数组问题是算法中常见的一类问题&#xff0c;通常涉及到数组的连续元素。在解决这类问题时&#xff0c;常用的方法有前缀和、滑动窗口、双指针&#xff0c;分治…

Sping源码(九)—— Bean的初始化(非懒加载)— getMergedLocalBeanDefinition

序言 前两篇文章介绍了Bean初始化之前的一些准备工作&#xff0c;包括设置BeanFacroty的ConversionService属性以及将Bean进行冻结。这篇文章将会进入到preInstantiateSingletons方法。进一步了解Bean的初始化流程。 preInstantiateSingletons public void preInstantiateSin…

一篇文章讲透排序算法之快速排序

前言 本篇博客难度较高&#xff0c;建议在学习过程中先阅读一遍思路、浏览一遍动图&#xff0c;之后研究代码&#xff0c;之后仔细体会思路、体会动图。之后再自己进行实现。 一.快排介绍与思想 快速排序相当于一个对冒泡排序的优化&#xff0c;其大体思路是先在文中选取一个…

装机必备——截图工具Snipaste安装教程

装机必备——截图工具Snipaste安装教程 软件下载 软件名称&#xff1a;Snipaste2.7 软件语言&#xff1a;简体中文 软件大小&#xff1a;15.37M 系统要求&#xff1a;Windows7或更高&#xff0c; 32/64位操作系统 硬件要求&#xff1a;CPU2GHz &#xff0c;RAM2G或更高 下载通…

数据结构(七)查找

2024年5月26日一稿&#xff08;王道P291&#xff09; 7.1 查找的基本概念 7.2 顺序查找和折半查找 7.2.1 顺序查找 7.2.2 折半查找 7.2.3 分块查找 7.3 树形查找 7.3.1 二叉排序树(BST) 7.3.2 平衡二叉树 7.4 B树和B树 7.4.1 B树及其基本操作 7.4.2 B树的基本概念 7.5 散列&…

idea、datagrip注册记录下

一、DataGrip注册 DataGrip版本号&#xff1a;DataGrip 2023.2 访问地址&#xff1a;https://3.jetbra.in/ 点击“hardbin.com”&#xff0c;下载“jetbra.zip” 在vm里面添加上&#xff1a; -javaagent:D:\work\idea\jetbra\ja-netfilter.jarjetbrains重启datagrip 在刚刚…

【408真题】2009-28

“接”是针对题目进行必要的分析&#xff0c;比较简略&#xff1b; “化”是对题目中所涉及到的知识点进行详细解释&#xff1b; “发”是对此题型的解题套路总结&#xff0c;并结合历年真题或者典型例题进行运用。 涉及到的知识全部来源于王道各科教材&#xff08;2025版&…

WebGL技术在教育培训中的应用

WebGL技术在教育培训中的应用非常广泛&#xff0c;通过其强大的三维图形处理能力&#xff0c;能够为教育培训提供更加生动、互动和沉浸式的学习体验。以下是WebGL在教育培训中的几个主要应用及其具体实现。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xf…

奶奶也能看懂的耦合协调度分析

不会计算&#xff1f;跟着文献学起来~ 案例数据连接&#xff08;复制链接后粘贴到浏览器中&#xff09;&#xff1a; 耦合协调度数据​spssau.com/spssaudata.html?shareDataF363000CD033FF15E557BB75B9B0D412 假如你有这样一组数据&#xff1a; 如何进行计算分析耦合协调度…

蓝桥楼赛第30期-Python-第三天赛题 统计学习数据题解

楼赛 第30期 Python 模块大比拼 统计学习数据 介绍 JSON&#xff08;JavaScript Object Notation, /ˈdʒeɪsən/&#xff09;是一种轻量级的数据交换格式&#xff0c;最初是作为 JavaScript 的子集被发明的&#xff0c;但目前已独立于编程语言之外&#xff0c;成为了通用的…

淘宝API探秘:一键获取店铺所有商品的魔法之旅

在数字时代的今天&#xff0c;数据已经成为了商业世界中的魔法石。而对于淘宝店主或者那些想要深入探索淘宝数据的人来说&#xff0c;淘宝API就像是打开阿里巴巴宝藏库的钥匙。今天&#xff0c;我们就来一起探索如何使用淘宝API&#xff0c;特别是如何获取店铺所有商品的接口&a…

ElasticSearch学习篇12_《检索技术核心20讲》基础篇

背景 学习极客实践课程《检索技术核心20讲》https://time.geekbang.org/column/article/215243 课程分为基础篇、进阶篇、系统案例篇 主要记录企业课程学习过程课程大纲关键点&#xff0c;以文档形式记录笔记。 内容 检索技术&#xff1a;它是更底层的通用技术&#xff0c…

芝加哥大学最新研究:GPT-4与财务预测,重塑财务分析的未来

最近&#xff0c;芝加哥大学的研究团队发表了一篇突破性的研究&#xff0c;展示了大型语言模型&#xff08;LLM&#xff09;&#xff0c;特别是 OpenAI 开发的 GPT-4&#xff0c;如何在财务报表分析领域取得了与专业分析师相匹配甚至超越的表现。这项研究不仅凸显了人工智能在高…

鸿蒙开发接口图形图像:【WebGL】

WebGL WebGL提供图形绘制的能力&#xff0c;包括对当前绘制图形的位置、颜色等进行处理。 WebGL标准图形API&#xff0c;对应OpenGL ES 2.0特性集。 说明&#xff1a; 开发前请熟悉鸿蒙开发指导文档&#xff1a; gitee.com/li-shizhen-skin/harmony-os/blob/master/README.md…