【数据结构】宜宾大学-计院-实验六

实验 6 栈和队列(综合实验)

  • 实验目的:
  • 实验内容:
    • 进制转换问题:
      • 第1题测试结果:
      • 第1题代码实现:
    • 括号匹配问题:
      • 第2题测试结果:
      • 第2题代码实现:
    • 回文字符串问题:(栈)
      • 第3题(实验自带做法,纯C)

实验目的:

熟悉掌握数据结构中队列的基本操作,能够结合栈与队列的结构灵活解决一些实际中问题。

实验内容:

备注:1,2 任选一题
1.用栈的操作实现10进制数和d进制数的转换,并输出结果

2.括号配对的检测: 利用栈来解决括号配对问题,左括号配右括号, 如: ( ) 配对正确 ( ] 配对错误 ( [ ] ) 配对正确 ( [ ) ) 配对错误。

3.在许多语言现象中,常见到一种形如abcba的文字,这种文字从左到右读和从右到左读结果是一样的,这种文字就是常说的回文。设计一个程序可以判断给定的一个文字串是否是回文。

注意:在本实验中,要求在实现上面的题目时,必须使用如下算法: 考虑到栈的先进后出以及队列的先进先出,可以结合这两种结构来实现需要的功能,即将文字串分别入队和入栈,然后依次通过出队和出栈输出判断是否有不相同的字符,一旦发现就证明文字不是一个回文。
实验步骤:
第一步:编写程序,实现栈,该栈可以用数组实现,也可以用链表实现
第二步:编写程序,实现队列,该队列可为循环队列,也可以用链表实现
第三步:编写主算法,使用自己编写的栈和队列实现回文判断问题(通过键盘输入一个以#结束的字符串,进行判断)

进制转换问题:

第1题测试结果:

在这里插入图片描述

第1题代码实现:

由于实验四那里也有这个题的低级版本,所以这里借用实验四当时实现的栈来完成本小题。

void conversion()
{int num, x;cout << "请输入要转化的十进制数字:" << endl;cin >> num;cout << "期望将它转化为几进制数:" << endl;cin >> x;cout << "将十进制数 " << num  << " " << "转化为 " << x << " " << "进制数得到的结果为:" << endl;ST st;InitStack(st);while (num > 0){Push(st, num % x);num /= x;}while (!EmptyStack(st)){cout << GetTop(st);PopTop(st);}DestroyStack(st);
}int main()
{conversion();return 0;
}

括号匹配问题:

第2题测试结果:

在这里插入图片描述

第2题代码实现:

下面代码用c++写便捷一点;纯c解题思路完全一样;即直接使用C++自带stack和string。

#include<iostream>
#include<stack>
#include<string>
using namespace std;bool Match(string str)
{stack<char> s;int count = 0;//计数,处理部分特殊情况,如1.只有一个括号,如2.第一个或最后一个为右括号for (int i = 0; i < str.size(); i++){if (str[i] == '{' || str[i] == '[' || str[i] == '<' || str[i] == '('){s.push(str[i]);count++;}if (str[i] == ')' && !s.empty()){count++;if (s.top() == '(')s.pop();elsereturn false;}if (str[i] == '>' && !s.empty()){count++;if (s.top() == '<')s.pop();elsereturn false;}if (str[i] == ']' && !s.empty()){count++;if (s.top() == '[')s.pop();elsereturn false;}if (str[i] == '}' && !s.empty()){count++;if (s.top() == '{')s.pop();elsereturn false;}}if (count != str.size())return false;return s.empty();
}int main()
{string str1("><}{{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]");string str2("{{}}{{}}<<>><<>>(())(())[[]][[]]");string str3("}");string str4("}[]()");string str5("}}}[]()");string str6("[][]))");cout << Match(str1) << endl;cout << Match(str2) << endl;cout << Match(str3) << endl;cout << Match(str4) << endl;cout << Match(str5) << endl;cout << Match(str6) << endl;return 0;
}

回文字符串问题:(栈)

第3题(实验自带做法,纯C)

这里的代码是比较老旧的写法了,下面是实验里面提供的一个栈,合理里利用这个栈来达到了第3小题的判断回文字符串的目的,第3小题在这里的它提供的做法目的就仅仅是锻炼使用栈的能力而已。

#include"stdlib.h"#include"stdio.h"  
#define STACK_INCREAMENT 10   //宏定义,堆栈增量;无分号 #define STACK_INI_SIZE 100   //宏定义,堆栈初始空间大小  
typedef char ElemType;  //堆栈元素类型为chartypedef struct{ ElemType *base;  ElemType *top;  int  stacksize; 
}sqstack;//结构体,顺序结构存储的栈的首尾指针  
typedef struct QNode{  
char  data; struct QNode *next; 
}QNode,*Queueptr;  //结构体,链式结构的队列  
typedef struct{  
Queueptr front;  
Queueptr rear; 
}linkQueue;   //结构体,用于存放队列的首尾指针  
void initStack(sqstack &s){ 
s.base=(ElemType*)malloc(STACK_INI_SIZE*sizeof(ElemType));  if(!s.base)   
exit(0);  
s.top=s.base; s.stacksize=STACK_INI_SIZE;}//初始化空栈  
void initLinkQueue(linkQueue &q){ q.front=(Queueptr)malloc(sizeof(QNode)); if(!q.front)   
exit(0);  
q.rear=q.front; 
}//初始化空队列void push(sqstack &s,ElemType e){  
if(s.top-s.base>=s.stacksize)
{   
ElemType *newbase;  newbase=(ElemType*)realloc(s.base,(STACK_INI_SIZE+STACK_INCREAMENT)*sizeof(ElemType));  if(!newbase)      
exit(0);   
s.base=newbase;   
s.top=s.base+s.stacksize;   
s.stacksize=STACK_INI_SIZE+STACK_INCREAMENT;  
}//追加空间  
*s.top=e;  
s.top++; 
}//元素入栈操作  
void pop(sqstack &s,ElemType &e){  
if(s.base==s.top)   
return;   //栈空,退出  
s.top--;  
e=*s.top; 
}//元素出栈,并用e返回其值  
void EnQueue(linkQueue &q,char c){  
Queueptr pre=q.rear; 
q.rear=(Queueptr)malloc(sizeof(QNode));  
q.rear->data=c; 
q.rear->next=NULL;  
pre->next=q.rear; 
}//元素入队列操作  
void DeQueue(linkQueue &q,char &e){  
Queueptr temp=q.front;  
e=temp->data; 
q.front=q.front->next;  
free(temp); 
}//元素出队列操作,并用e返回其结点数据域int main(){ sqstack s;//定义堆栈结构体,用于存放堆栈首尾指针  
linkQueue lQueue;//定义结构体,用于存放队列首尾指针  
char c; initStack(s);//初始化一个空的堆栈 initLinkQueue(lQueue);//初始化一个空的队列  
printf("请输入一串字符,并以#结束:\n");    
scanf("%c",&c);  
while(c!='#') {   
push(s, c); //字符入栈   
EnQueue(lQueue, c);//字符入队列     
scanf("%c",&c);   }//分别向堆栈与队列中存入该字符串  
lQueue.front=lQueue.front->next;  
while(!(s.top==s.base)){   
char a,b;   
pop(s,a);  //字符出栈     
DeQueue(lQueue,b);  //字符出队列   
if(a!=b) {    
printf("该字符串不是回文字\n");  //不是回文字    
exit(0);      
}//两字符进行比较 
}//将堆栈与队列中的元素出栈,并进行比较,判断该字符串是否为回文字  
printf("该字符串是回文字\n");  //输出判断结果,是回文字  
return 0; 
}//主程序,完成回文字符串的判定,并输出判定结果

学习C++得看这

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

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

相关文章

java并发编程-CAS详解

一定要看这个链接的视频&#xff0c;讲解十分清楚&#xff01;&#xff01;&#xff01; 【【Java并发】面试官问我CAS、乐观锁、悲观锁&#xff0c;我反手就是骑脸输出】 https://www.bilibili.com/video/BV1ff4y1q7we/?share_sourcecopy_web&vd_sourceafbacdc02063c57e7…

【C/C++】qsort函数的学习与使用

零.导言 在之前的文章中&#xff0c;我介绍了冒泡排序&#xff0c;即按ASCII码值把元素从小到大排序&#xff08;文章链接我放在了第五部分&#xff0c;有兴趣的小伙伴可以求看看&#xff09;。而今天我将继续介绍qsort函数&#xff0c;这个函数可以起到和冒泡排序一样的作用&a…

华为实时视频使用FLV播放RTSP流

import flvjs from ‘flv.js’; 安装flv <video style"width:100%;height:100%;" ref"videoHWRef" ></video>// src 华为rtsp流 rtsp://admin:Huaweivideo10.10.8.151:554/xxx/trackID1// url 需要后端提供视频源地址playVideo() {if (fl…

【STM32】通过 DWT 实现毫秒级延时

目录 零、前言一、DWT1、DEMCR2、DWT_CTRL3、DWT_CYCCNT 二、实现代码三、测试 零、前言 在 FreeRTOS 中&#xff0c;SysTick 被用于作为调度器的一部分进行任务调度&#xff0c;那么如果我需要使用软件模拟通信&#xff0c;例如软件 I2C&#xff0c;需要使用 delay&#xff0…

如何在Linux系统中使用Ansible进行自动化部署

如何在Linux系统中使用Ansible进行自动化部署 Ansible简介 安装Ansible 在Debian/Ubuntu系统中安装 在CentOS/RHEL系统中安装 启动Ansible服务 Ansible基本概念 Inventory Playbook Module 配置Ansible 测试Ansible配置 执行Ansible Playbook Ansible模块 文件模块 包管理模块…

「Mac畅玩鸿蒙与硬件20」鸿蒙UI组件篇10 - Canvas 组件自定义绘图

Canvas 组件在鸿蒙应用中用于绘制自定义图形,提供丰富的绘制功能和灵活的定制能力。通过 Canvas,可以创建矩形、圆形、路径、文本等基础图形,为鸿蒙应用增添个性化的视觉效果。本篇将介绍 Canvas 组件的基础操作,涵盖绘制矩形、圆形、路径和文本的实例。 关键词 Canvas 组件…

从零开始构建 ChatGPT

今天&#xff0c;我们要介绍的是一个名为 LLMs-from-scratch 的 GitHub 项目&#xff0c;它由开发者 rasbt 精心打造&#xff0c;旨在一步步教你如何使用 PyTorch 从零开始实现一个类似 ChatGPT 的大型语言模型&#xff08;LLM&#xff09;。 这是一个教育性质的开源项目&…

【Git】Git常用命令

目录 1 前言2 git命令2.1 branch2.2 checkout2.3 pull and push2.4 config2.4.1 Proxy 2.5 tag2.6 rebase2.7 patch2.8 remote2.9 submodule2.10 rm2.10 gitignore2.11 某个commit更改了哪些文件2.12 clean 3 结束语 1 前言 本章记录总结在使用git过程中常用的一些命令&#x…

redis分布式锁在项目中的应用总结

项目应用 应用1 redis分布式锁实现两个操作的原子性 需求&#xff1a;实现一人一单业务逻辑时&#xff08;如果能走到这个逻辑&#xff0c;代表库存是充足的&#xff09;&#xff0c;我们需要 先查询订单 如果订单不存在即没有买过则创建订单 这两个步骤我们要保证是原子…

前端 react 面试题(二)

文章目录 hooks的使用规则为什么hooks要确保在函数组件的最顶层,而不能放置在循环或者条件语句中。react的事件模型react的合成事件是如何实现的react事件传参,可以使用箭头函数或bind方法,这两种哪一种更好使用箭头函数:使用`bind`方法:react的事件模型和vue的区别React …

1分钟解决Excel打开CSV文件出现乱码问题

一、编码问题 1、不同编码格式 CSV 文件有多种编码格式&#xff0c;如 UTF - 8、UTF - 16、ANSI 等。如果 CSV 文件是 UTF - 8 编码&#xff0c;而 Excel 默认使用的是 ANSI 编码打开&#xff0c;就可能出现乱码。例如&#xff0c;许多从网络应用程序或非 Windows 系统生成的 …

【python】OpenCV—Tracking(10.4)—Centroid

文章目录 1、任务描述2、人脸检测模型3、完整代码4、结果展示5、涉及到的库函数6、参考 1、任务描述 基于质心实现多目标&#xff08;以人脸为例&#xff09;跟踪 人脸检测采用深度学习的方法 核心步骤&#xff1a; 步骤#1&#xff1a;接受边界框坐标并计算质心 步骤#2&…

GraphQL系列 - 第2讲 Spring集成GraphQL

目录 一、maven依赖二、Schema 定义三、代码集成3.1 创建模型类3.2 创建服务类3.3 创建控制器类 四、单元测试五、实际 HTTP 请求测试5.1 查询单个 Person5.2 查询所有 People5.3 添加 Person 六、其他6.1 开启graphiql6.2 开启schema查看端点 一、maven依赖 首先&#xff0c;…

Golang | Leetcode Golang题解之第526题优美的排列

题目&#xff1a; 题解&#xff1a; func countArrangement(n int) int {f : make([]int, 1<<n)f[0] 1for mask : 1; mask < 1<<n; mask {num : bits.OnesCount(uint(mask))for i : 0; i < n; i {if mask>>i&1 > 0 && (num%(i1) 0 |…

模拟栈的实现

栈的概念 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈 顶&#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出 LIFO &#xff08; Last In First Out &#xff09;的原则。 压栈&…

Win10搭建SFTP服务器

1、下载安装 Release v9.5.0.0p1-Beta PowerShell/Win32-OpenSSH GitHub 下载OpenSSH-Win64.zip 解压之后放入到&#xff1a;C:\Program Files (x86)\OpenSSH-Win64以管理员身份打开CMD进入到 C:\Program Files (x86)\OpenSSH-Win64 文件夹执行命令 powershell.exe -Exec…

WordPress网站添加嵌入B站视频,自适应屏幕大小,取消自动播放

结合bv号 改成以下嵌入式代码&#xff08;自适应屏幕大小,取消自动播放&#xff09; <iframe style"width: 100%; aspect-ratio: 16/9;" src"//player.bilibili.com/player.html?isOutsidetrue&bvidBV13CSVYREpr&p1&autoplay0" scrolling…

C语言内幕--全局变量(结合内存分区、汇编视角看类型、连接器)

前言 学习资源&#xff1a;b站up主&#xff1a;底层技术栈学过C语言都知道&#xff0c;全局变量可以再全局中使用&#xff0c;其实全局变量内部还是涉及到不少知识&#xff0c;这里从内存分区、汇编视角看类型、连接器等角度看待全局变量&#xff1b;由于涉及到底层技术&#…

省级-建成区绿化覆盖率数据(2006-2022年)

建成区绿化覆盖率是指城市建成区的绿化覆盖面积占建成区的百分比。 城市绿化覆盖率的提升&#xff0c;不仅能够改善城市的空气质量&#xff0c;降低噪音污染&#xff0c;还能提高城市的生物多样性&#xff0c;为市民提供更多的休闲和娱乐空间。 2006年-2022年省级-建成区绿化…

基于CNN-BiLSTM的时间序列数据预测,15个输入1个输出,可以更改数据集,MATLAB代码

1. 数据收集与预处理 数据清洗&#xff1a;处理缺失值、异常值等。特征工程&#xff1a;提取有助于预测的特征。数据标准化&#xff1a;将时间序列数据标准化&#xff0c;使其具有零均值和单位方差&#xff0c;有助于模型训练。滑动窗口划分&#xff1a;将时间序列数据划分为多…