任务一： 顺序栈的基本操作
任务描述： 本关任务：实现顺序栈的基本操作，包括栈的初始化、置空栈、进栈、出栈、判栈空、栈的输出（遍历）等。
相关知识： 为了完成本关任务，你需要掌握：
规定空栈时s->top=-1
进栈操作需要先判断时候是否栈满 栈满条件：s->top==MAXSIZE-1 栈未满才执行以下进栈操作 s->top++; s->data[s->top]=x;
出栈操作需要判断栈是否为空 栈空条件：s->top==-1; 如果栈空，返回-1表示操作失败 若栈非空，才执行以下出栈操作，返回栈顶元素的值： s->top–; return s->top[s->top+1]; 想想为什么？
可以实现逆向输出。 两种方式：
1、whie(栈不为空) {出栈； 输出栈顶元素； }
2、顺序栈本质上就是一个顺序表 for(i=s->top;i>=0;i–) 输出s->data[i]
建议使用第一种方式
编程要求：
本关中，需要定义两个完整的函数，补充一个函数
测试说明：
从键盘输入字符串，以#作为结束符。 平台会对你编写的代码进行测试：
please input an express end with symbol ‘#’: hello# olleh
示例代码如下：（温馨提示：本文全部代码只在 EduCoder 平台上通过测试，仅供参考，如有运行错误请自行改正） #include "stdio.h" #define MAXSIZE 100 typedef int datatype; /*顺序栈的结构体类型定义*/ typedef struct {datatype stack[MAXSIZE]; int top; }seqstack; /*函数功能：置空栈,请在下面给出函数的完整定义，定义时注意函数的返回值、形参个数、形参类型等*/ void setnull(seqstack *s) /*置空栈—由于c语言的数组下标是从0开始的，所以置空栈操作时将栈顶指针放在下标为0之前，即-1处。*/ {s->top=-1;} /*判断当前栈是否为空栈*/ int empty(seqstack *s) {if(s->top<0) return 1; else return 0; } /*函数功能：把元素x压入栈s中，请在下面给出函数的完整定义。注意函数返回值、形参类型等*/ int push(seqstack *s,datatype x) /*把元素x压入栈s中*/ {if(s->top>=MAXSIZE-1) {printf("stack overflow!\n"); /*发生上溢*/ return -1; } else { s->top++; s->stack[s->top]=x; return s; } } /*函数功能：弹出当前栈s的栈顶元素，若成功返回栈顶元素；不成功，返回-1.请在下面补充代码，函数原型已经给出了头部*/ datatype pop(seqstack *s) { if(s->top==-1) {printf("stack empty!\n"); /*栈空，返回空值*/ return -1; } else { s->top--; return(s->stack[s->top+1]); } } int main() { char ch; seqstack q;/*定义一个顺序栈变量*/ setnull(&q);/*初始化一个顺序栈*/ /*从键盘输入一个表达式入栈。表达式以#结尾*/ ch=getchar(); while(ch!='#') {push(&q,ch); ch=getchar(); } while(empty(&q)!=1) {ch=pop(&q); putchar(ch); } return 0; }任务二： 括号匹配算法
任务描述： 本关任务：括号配对检查。试设计一个程序对任意输入的语句或数学表达式，判断其括号是否匹配。若匹配，则返回1，否则返回0。调试程序并对相应的输出作出分析；加深对算法的理解。
相关知识： 你需要掌握： 1.栈的基本操作 2.括号匹配算法 3.程序设计技巧
这是上一关的内容，这里我们重点讲解这里为什么要用到栈结构？ 给定一个表达式 {a【b/(c+d)】-a}b 上面这个表达式中括号出现的顺序{[（）]} 在进行括号匹配的时候，我们发现 最早读入的左括号，最后匹配 最后读入的左括号，最先匹配 也就是说后读入的左括号先匹配 符合栈后进先出的特点 因此在算法中 我们可以将所有左括号依次入栈 当读到右括号的时候，这个右括号应该最先跟栈顶的左括号匹配 如果不匹配，算法结束 如果匹配，那就出栈，这样栈顶的左括号永远是最“迫切匹配的” 左括号的迫切匹配程度是越后读入的左括号越高
假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例： {（）（） [（）]}（这里忽略了表达式中除括号外其他字符） 方法：每出现一个左括号，保留起来；对于出现的右括号，检查后出现的左括号是否与它匹配。 分析可能出现的不匹配的情况： 1）到来的右括号不是所期待的； 2）到来的是“不速之客”； —右括号多了 3）直到结束，也没有到来“所期待的”—右括号少了 首先建立一个栈结构，且初始化栈为空。然后由键盘上随即输入一个带括号的语句或带括号的数学表达式，以#结束。扫描表达式exps,当遇到“(”、“[”、“{”时，将其入栈。遇到“）”、“]”、“}”时，判断栈顶是否有相匹配的括号。遇到其他字符跳过不处理。匹配成功返回1，不成功返回0. symb接收键盘接收过来的字符 根据字符类型不同，处理方式不同 …… switch(symb) { case ‘(‘: case ‘[‘: case ‘{‘: push(s,symb);break; case ‘)’: ch=pop(s); if(ch!=’(‘) return FALSE; break; case ‘]’: ch=pop(s); if(ch!=’[‘) return FALSE; break; case ‘}’: ch=pop(s); if(ch!=’{‘) return FALSE; break; default:; }
在空栈中放入#垫底，push(s,‘#’)作用： （1）执行出栈操作不用判断栈空！因为有#垫底，当左括号匹配完了，栈顶元素为#，这时它与右括号肯定不匹配，所以就会直接返回false,避免了空栈时还要出栈的情况。 （2）当栈顶元素为#时，说明当前栈里的左括号已经全部出栈了。
编程要求： 需要写出judge函数原型定义。
测试说明： 从键盘输入字符串，以#作为结束符。 平台会对你编写的代码进行测试： 左括号多了： please input an express end with symbol ‘#’: a+(b*(c+d)/(a+b)# no
右括号多了 please input an express end with symbol ‘#’: a+(b*(c+d)/(a+b)# no
括号类型不匹配 please input an express end with symbol ‘#’: 【（a+b)/[c+d])# no
完全匹配： please input an express end with symbol ‘#’: {a+(b*(c+d)/a）*a}-1# no
示例代码如下：（温馨提示：本文全部代码只在 EduCoder 平台上通过测试，仅供参考，如有运行错误请自行改正） #include "stdio.h" #define MAXSIZE 100 #define TRUE 1 #define FALSE 0 typedef int datatype; typedef struct /*顺序栈的结构体类型定义*/ {datatype stack[MAXSIZE]; int top; }seqstack; int judge(seqstack *s); /*置空栈-由于c语言的数组下 标是从0开始的，所以置空栈操作时将栈顶指针放在下标为0之前， 即-1处。*/ void setnull(seqstack *s) {s->top=-1;} int empty(seqstack *s) /*判断当前栈是否为空栈*/ {if(s->top<0) return TRUE; else return FALSE; } int push(seqstack *s,datatype x) /*把元素x压入栈s中*/ {if(s->top>=MAXSIZE-1) {printf("stack overflow!\n"); /*发生上溢*/ return FALSE; } else {s->stack[++s->top]=x; /*栈顶指针上移，数据元素入栈*/ return TRUE; } } datatype pop(seqstack *s) /*弹出当前栈s的栈顶元素*/ {if(s->top<0) {printf("stack empty!\n"); /*栈空，返回空值*/ return -1; } else {s->top--; return(s->stack[s->top+1]); } } /*括号匹配检查算法。--遇到"("、"["、"{"时，将其压入 栈s中。请在下面写出匹配算 法的函数原型，注意函数名、形参的个数、类型在main函数已给出*/ int judge(seqstack *s) { datatype symb,ch,store; push(s,'#'); symb=getchar();/*从键盘接受字符*/ while(symb!='#') { switch(symb) { case '(': case '[': case '{': push(s,symb);break; case ')': ch=pop(s); if(ch!='(') return FALSE; break; case ']': ch=pop(s); if(ch!='[') return FALSE; break; case '}': ch=pop(s); if(ch!='{') return FALSE; break; default:; } symb=getchar(); } if(pop(s)=='#') return TRUE; else return FALSE; } int main() {char ch; seqstack q; setnull(&q); //printf("please input an express end with symbol '#':\n"); if(judge(&q)) printf("yes\n"); /*括号匹配，则输出yes*/ else printf("no\n"); /*括号不匹配，则输出no*/ return 0; }任务三： 进制转换问题
任务描述： 编写一个进制转换算法
相关知识： 你需要掌握： 1.为什么用到栈 2.算法的实现。
先来看一下十进制转二进制的计算过程。就以121为例，用 2 除 121，取余数，然后再用 2 去除得到的商，取余数……如此循环往复，直到商为零，将余数逆序输出即可得到 121 的二进制表示。 具体过程，我这里就不赘述了。 由于我们要将计算过程中产生的余数逆序输出，即121的二进制表示为：1111001，也就是先产生的余数要后输出，这恰恰符合栈的操作规则，所以当我们把该进制转换的算法实现为程序时，就可以用栈来存储计算过程中产生的余数序列。
设被除数变量为m,要转换的进制数为N while(m不为0) {把m%N(即余数)入栈 m=m/n} 最后将栈中元素依次出栈可得到结果。
测试说明： ① 平台会对你编写的代码进行测试： 请输入一个十进制数m和要转换的进制数n: 58 2 111010 ② 请输入一个十进制数m和要转换的进制数n: 50 8 62
示例代码如下：（温馨提示：本文全部代码只在 EduCoder 平台上通过测试，仅供参考，如有运行错误请自行改正） #include "stdio.h" #define MAXSIZE 100 #define TRUE 1 #define FALSE 0 typedef int datatype; typedef struct /*顺序栈的结构体类型定义*/ {datatype stack[MAXSIZE]; int top; }seqstack; /*置空栈-由于c语言的数组下 标是从0开始的，所以置空栈操作时将栈顶指针放在下标为0之前， 即-1处。*/ void setnull(seqstack *s) {s->top=-1;} int empty(seqstack *s) /*判断当前栈是否为空栈*/ {if(s->top<0) return TRUE; else return FALSE; } int push(seqstack *s,datatype x) /*把元素x压入栈s中*/ {if(s->top>=MAXSIZE-1) {printf("stack overflow!\n"); /*发生上溢*/ return FALSE; } else {s->stack[++s->top]=x; /*栈顶指针上移，数据元素入栈*/ return TRUE; } } datatype pop(seqstack *s) /*弹出当前栈s的栈顶元素*/ {if(s->top<0) {printf("stack empty!\n"); /*栈空，返回空值*/ return -1; } else {s->top--; return(s->stack[s->top+1]); } } /*进制转换算法*--将十进制的m转换为n进制，请在下面写出进制转换函数的原型定义， 提示：从main函数中的函数调用语句确定函数名、函数参数的个数和类型*/ transform(seqstack *s,int m,int n) { int i=0,p,x; while (m!=0) { p=m%n; push(s,p); m=m/n; } while (!empty(s)) { x=pop(s); printf("%d",x); } } int main() {char ch; int m,n; seqstack q; setnull(&q); /*printf("请输入一个十进制数m和要转换的进制数n:\n");*/ scanf("%d%d",&m,&n); transform(&q,m,n);/*调用进制转换函数进行调用*/ return 0; }我把我目前写的关于数据结构 题目 的链接全部汇总整理在下面，有需要的小伙伴自己点击哈。
数据结构 习题 第一章 概论数据结构 习题 第二章 线性表 （C语言描述）数据结构 习题 第三章 栈和队列 （C语言描述）数据结构 习题 第四章 串 （C语言描述）数据结构 习题 第五章 多维数组和广义表（C语言描述）数据结构 习题 综合复习实验：
数据结构 实验一 顺序表的操作数据结构 实验二 链表的基本操作数据结构 实验三 栈的基本运算数据结构 实验四 二叉树的操作数据结构实验五-马踏棋盘数据结构-顺序表的排序操作-冒泡排序好了，关于栈的基本运算的相关实验差不多就是这样了。本文只是提供一种思路，可能会有更好、更简洁的代码，等着我们去思考探索。
