锐客网

  1. 首页 > it技术 > >

寒假|Data Structure 栈和队列（三道）


数据结构 课堂作业 实验五 实验报告

  • 第一题
    • 题目
    • 代码
  • 第二题
    • 题目
    • 代码
  • 第三题
    • 题目
    • 代码
【寒假|Data Structure 栈和队列（三道）】
第一题 题目
判断回文数，回文是指正读反读均相同的字符序列，如“1221”和“12321”均是回文，但“1234”不是回文。
请写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)
代码
//头文件 #include #include #include #include using namespace std; /* 我要做的工作： 1.设计一个栈 //这里实现的是顺序栈 这个设计包括一系列函数功能的补充2.利用栈实现回文序列的判断 *///常数定义 //一般的栈的默认长度 #define STACK_INIT_SIZE 100 //如果默认不够，每次补充的空间大小 #define STACK_INCREMENT 10//结构体设计 //顺序栈 typedef struct SqStack { //存放数据的数组 char *elem; //记录栈顶的排序 int top; //开辟的栈的大小 int stacksize; }SqStack; //栈的初始化 void InitStack_Sq(SqStack &S) { //以elem为首开辟一个连续的内存 S.elem=new char[STACK_INIT_SIZE]; //top初始化 //注意： //这里是为了通过记录数组的下标而返回栈顶元素 S.top=-1; //记录空间的大小 S.stacksize=STACK_INIT_SIZE; } //销毁操作 void DestroyStack_Sq(SqStack S) { //销毁数组 delete []S.elem; //top回原形 S.top=-1; //空间大小回0 S.stacksize=0; } //求栈长度的操作 int LengthStack_Sq(SqStack S) { return (S.top+1); } //清空操作 void DeleteStack_Sq(SqStack S) { S.top=-1; } //取栈顶元素 void GetTop_Sq(SqStack S,char &e) { //判断栈是不是空的 if(S.top==-1) { cout<<"The stack is EMPTY."<top-- //先用原先的top填入e， //然后再把top减少 e=S.elem[S.top--]; } } //--------------顺序栈的设计到此为止--------------------- //设计判断回文序列的函数 //放一半到栈的数组里面？然后再进行两个数组的比较？？ bool ifPalindromic(char a[]) { SqStack S; InitStack_Sq(S); //length记录a的长度 int length=strlen(a); //如果字符串长度是奇数 //那么要被压入判断栈中的字符数是(n-1)/2 if(length%2!=0) { int i; for(i=0; i<(length-1)/2; i++) { Push_Sq(S,a[i]); } i=i+1; while(S.top!=-1) { char temp; GetTop_Sq(S,temp); if(a[i]!=temp) { return false; } else { Pop_Sq(S,temp); i++; } } return true; } //如果字符串长度是偶数 //那么要被压入判断栈中的字符数是n/2 if(length%2==0) { int i; for(i=0; i>a; /* SqStack S; InitStack_Sq(S); //length记录a的长度 int length=strlen(a); //如果字符串长度是奇数 //那么要被压入判断栈中的字符数是(n-1)/2 if(length%2!=0) { int i; for(i=0; i<(length-1)/2; i++) { Push_Sq(S,a[i]); } i=i+1; while(S.top!=-1) { char temp; GetTop_Sq(S,temp); if(a[i]!=temp) { cout<<"no"<

第二题 题目
用两个顺序栈实现一个共享栈，具体要求为：
设有两个栈都采用顺序栈方式，共享一个存储区，[0,maxsize - 1]，采用栈顶相向，迎面增长的存储方式，设计出栈和入栈等操作算法。
代码
//头文件 #include #include #include #include using namespace std; //常数设置 #define MAXSIZE 100 #define ADDSIZE 100 /* 解析本次任务两个顺序栈实现一个共享栈 内存是同一块数组（连续的内存单元 但是栈底是不同的。 */ /*草稿 *///共享栈的结构设计 /* 共享栈的数组空间 两个栈顶 两个栈的大小 */ typedef struct shareStack { char *share; int top_left; int top_right; int stacksize; }shareStack; //栈的初始化 void InitStack_share(shareStack &S) { S.share=new char[MAXSIZE]; //根据数组的特点！ //左边开头的是-1 S.top_left=-1; //右边的开头是MAXSIZE S.top_right=MAXSIZE; S.stacksize=MAXSIZE; } //销毁操作 void DestroyStack_share(shareStack S) { //销毁数组 delete []S.share; //两个top打回原形 S.top_left=-1; S.top_right=MAXSIZE; //空间借用大小也回0 S.stacksize=0; } //左边的栈长 int LengthStack_share_left(shareStack S) { return S.top_left+1; } //右边的栈长 int LengthStack_share_right(shareStack S) { return S.stacksize-S.top_right; } //删除左边的栈 void DeleteStack_share_left(shareStack S) { S.top_left=-1; } //删除右边的栈 void DeleteStack_share_right(shareStack S) { S.top_right=MAXSIZE; } //得到左边栈顶元素 void GetTop_share_left(shareStack S,char &e) { if(S.top_left==-1) { cout<<"The LEFT stack is EMPTY."<=S.top_right; i--) { newstack[i]==S.share[i]; } //删除原先的顺序表 delete []S.share; //移动指针指向新的数组内存 S.share=newstack; //更新S的栈空间大小 S.stacksize=S.stacksize+ADDSIZE; } //出栈操作 //左栈 void Pop_share_left(shareStack &S,char &e) { //判断能不能出的来 if(S.top_left==-1) { cout<<"LEFT stack is EMPTY."<top-- //先用原先的top填入e， //然后再把top减少 e=S.share[S.top_left--]; } } //右栈 void Pop_share_right(shareStack &S,char &e) { //判断能不能出的来 if(S.top_right==-1) { cout<<"RIGHT stack is EMPTY."<top-- //先用原先的top填入e， //然后再把top减少 e=S.share[S.top_right++]; } }

第三题 题目
用两个栈实现一个队列。
算法思想：
1>设计类
成员变量：给两个栈s1和s2来模拟实现一个队列
成员函数：入队Push()和出队Pop()
2>给两个指向栈对象s1、s2的指针input和output，分别用来入队和出队
3>按照先进先出的方式模拟入队和出队操作
Push：将input指向不空的栈，然后在input中入队
Pop：将input所指栈中的前n-1(n为栈中元素个数)的数据先转移到output所指的栈中，同时pop掉input中的前n-1个元素，最后pop掉input中的最后一个元素，即可实现先进先出。
代码
//头文件 #include #include #include #pragma once #include using namespace std; /* 任务： 设计一个类 包括： 两个栈 函数 1.push 入队 2.pop */ class Queue { private: //信息缓冲栈 stack Former; //输出控制栈 stack Latter; public: Queue(); ~Queue(); void Push(char e); void Pop(); void getTop(); }; Queue::Queue() {} Queue::~Queue() {} void Queue::getTop() { //如果后栈是空栈 if(this->Latter.empty()) { //把前栈元素都压入后栈 //让后栈变成非空栈 //并且销毁前栈当中的存储 for(int i=1; iFormer.size(); i++) { this->Latter.push(this->Former.top()); this->Former.pop(); } this->Former.pop(); } //如果后栈不是空栈 //那就有栈顶元素，也就是队首元素 cout<Former.top()<Former.push(e); return; }void Queue::Pop() { //如果后者栈是空栈 if(this->Latter.empty()) { //把前栈元素压入后栈 //并且销毁前栈当中的存储 for(int i=1; iFormer.size(); i++) { this->Latter.push(this->Former.top()); this->Former.pop(); } this->Former.pop(); } //后栈出栈即可 this->Latter.pop(); return; } int main() { Queue q; for(int i=0; i<6; i++) { char a; cin>>a; q.Push(a); } q.Pop(); q.getTop(); return 0; }

    推荐阅读


    上一篇：SpringCloud微服务实战——搭建企业级开发框架（二十二）（基于MybatisPlus插件TenantLineInnerInterceptor实现多租户功能）

    下一篇：vue|vue 组件内绑定prop数据