还剩8页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
有支戒工用院《数据结构》实验指导及报告书学年第:学期2022/2022姓名学号班级指导教师计算机科学与工程学院
20225、彳警以带头结点的循环链表表示队列,并且只试编写相应的置空队列、入队列、出队列的算法实现代码
三、实验小结
四、教师评语实验二栈和队列
一、实验目的
1、掌握栈的结构特性及其入栈,出栈操作;
2、掌握队列的结构特性及其入队、出队的操作,掌握循环队列的特点及其操作
二、实验内容和要求
1、阅读下面程序,将函数Push和函数Pop补充完整要求输入元素序列12345e,运行结果如下所示#include stdio.h#include malloc.h#define ERROR0#define OK1#define STACK.INT_SIZE10/*存储空间初始分配量*/#define STACKINCREMENT5/*存储空间分配增量*/typedef intElemType;/*定义兀素的类型*/typedef struct{ElemType*base;ElemType*top;int stacksize;/*当前已分配的存储空间*/}SqStack;int InitStackSqStack*S;/*构造空栈*/int pushSqStack*S,ElemType*e;/*入底*/int PopSqStack*S,ElemType*e;/*出栈*/int CreateStackSqStack*S;/*创建栈*/void PrintStackSqStack*S;/*出栈并输出栈中元素*/int InitStackSqStack*S{S-base=ElemType*malloc STACK,INT_SIZE*sizeof ElemType;if!S-base returnERROR;S-top=S-base;S-stacksize=STACK.INT_SIZE;return OK;}/*InitStack*/int Push SqStack*S,ElemType e{}/*Push*/int PopSqStack*S,ElemType*e{}/*Pop*/int CreateStackSqStack*S{int e;ifInitStackSelsereturn ERROR;Push S,e;return OK;}/*CreateStack*/void PrintStackSqStack*S{ElemType e;while PopS,e}/*Pop_and_Print*/int main{SqStack ss;CreateStackss;PrintStackss;return0;.算法分析输入元素序列12345,为什么输出序列为54321体现了栈的什么生?#includestdio.h#includemalloc.h ttdefine ERROR0ttdefine OK1ttdefine STACK_INT_SIZE10/*存储空间初始分配量*/^define STACKINCREMENT5/*存储空间分配增量*/typedef intElemType;/*定义兀素的类型*/typedef struct{ElemType*base;ElemType*top;int stacksize;/*当前已分配的存储空间*/}SqStack;int InitStackSqStack*S;/*构造空栈*/int PushSqStack*S,ElemType*e;/*入栈*/int PopSqStack*S,ElemType*e;/*出栈*/int CreateStackSqStack*S;/*创建栈*/void PrintStackSqStack*S;/*出栈并输出栈中元素*/int InitStackSqStack*S{S-base=ElemType*mallocSTACK_INT_SIZE*sizeofElemType;if!S-base return ERROR;S-top=S-base;S-stacksize=STACK_INT_SIZE;return OK;}/*InitStack*/int PushSqStack*S,ElemType e{ifS-top-S-base=S-stacksizeS-base=ElemType*reallocS-base,S-stacksize+STACKINCREMENT*sizeofEle mType;if!S-base return ERROR;S-top=S-base+S-stacksize;S-〉stacksize+=STACKINCREMENT;*S-top++=e;return OK;}/*Push*/int PopSqStack*S,ElemType*e{ifS-top=S-basereturn ERROR;e=-S-top;return OK;}/*Pop*/int CreateStackSqStack*S{int e;if InitStackSelse{returnERROR;PushS,e;return OK;}/*CreateStack*/void PrintStackSqStack*S{ElemType e;while PopS,e}/*Pop_and_Print*/int main{SqStack ss;CreateStack ss;Popss,e;PrintStackss;return0;
2、在第1题的程序中,编写一个十进制转换为二进制的数制转换算法函数(要求利用栈来实现),并验证其正确性实现代码■#includestdio.h#includemalloc.h#defineERROR0#define OK1#define STACKINIT SIZE10/*存储6空?间?初?始°分?配?量C*/Sdefine STACKINCREMENT5/*存储i空?间?分0配?增?量C*/typedef intSElemType;/*定i§义元打素?的i类CT口型y*/typedef struct{SElemType*base;SElemType*top;int stacksize;}SqStack;int InitStackSqStack S;int CreateStackSqStack*S;int GetTopSqStack S,SElemType e;int PushSqStack S,SElemType e;int PopSqStack S,SElemType e;void conversion;void maininte;SqStack S;CreateStackS;GetTopS,e;PushS,e;conversion;}int InitStackSqStack S{S.base=SElemType*mallocSTACK INITSIZE*sizeofSElemType;if!S.basereturn ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;int CreateStackSqStackSint e;ifInitStack Sprintf;else printf;returnERROR;printf);while scanf,ePushS,e;return OK;int GetTopSqStackS,SElemType eifS.top==S.base returnERROR;e=*S.top-1;return OK;int PushSqStackS,SElemType eifS.top-S.base=S.stacksizeS.base=SElemType*reallocS.base,S.stacksize+STACKINCREMENT*sizeofSElemType;if!S.basereturn ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}int PopSqStackS,SElemType eifS.top==S.basereturn ERROR;e=*--S.top;return OK;}void conversionintn,e;SqStackS;printf;scanf,n;whilenPushS,n;n=n/2;PopS,e;printf,e;
3、阅读并运行程序,并分析程序功能#include stdio.h#include malloc.h#include string.h#define M20#define elemtypechartypedef struct{elemtype stackfM];int top;void initstacknode*st;void pushstacknode*st,elemtype x;void popstacknode*st;stacknode;void initstacknode*st st-top=0;void pushstacknode*st,elemtype xifst-top==Melsest-top=st-top+1;st-stack[st-top]=x;}void popstacknodest-top=st-top-1;int mainchars[M];int i;stacknode*sp;sp=malloc sizeofstacknode;initsp;gets s;for i=0;i strlens;i++ifs[i]==push sp,s[i];ifs[i]==popsp;if sp-top==0elsereturn0;}输入2+c-d*6-f-7*a/6运行结果输入a-c-d*6-s/3-x/2运行结果程序的基本功能以下为选做实验
4、设计算法,将一个表达式转换为后缀表达式,并按照后缀表达式进行计算,得出表达式得结果.实现代码。