版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、.实验 二 栈和队列的基本操作实现及其应用一_一、实验目的1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。一_二、实验内容题目一、试写一个算法,判断依次读入的一个以为结束符的字符序列,是否为回文。所谓“回文“是指正向读和反向读都一样的一字符串,如“321123”或“ableelba”。相关常量及结构定义:#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int SElemType;typedef struct SqStack SElemType *base; SElemType *top; int stacksize;
2、SqStack;设计相关函数声明:判断函数:int IsReverse()栈:int InitStack(SqStack &S )int Push(SqStack &S, SElemType e ) int Pop(SqStack &S,SElemType &e) int StackEmpty(s)一_三、数据结构与核心算法的设计描述1、初始化栈/* 函数功能:对栈进行初始化 。参数:栈(SqStack S)。成功初始化返回0,否则返回-1 */int InitStack(SqStack &S) S.base=(SElemType *)malloc(10*sizeof(SElemType);i
3、f(!S.base) /判断有无申请到空间 return -1; /没有申请到内存,参数失败返回-1S.top=S.base;S.stacksize=STACK_INIT_SIZE;S.base=new SElemType;return 0;2、判断栈是否是空/*函数功能:判断栈是否为空。参数; 栈(SqStack S)。栈为空时返回-1,不为空返回0*/int StackEmpty(SqStack S)if(S.top=S.base) return -1;else return 0;3、入栈/*函数功能:向栈中插入元素。参数; 栈(SqStack S),元素(SElemtype e)。成功插
4、入返回0,否则返回-1 */int Push(SqStack &S,SElemType e)if(S.top-S.base=S.stacksize)S.base=(SElemType *)realloc(S.base,(S.stacksize+1) * sizeof(SElemType); /重新分配空间if(!S.base) return -1; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT;*S.top+=e; /插入操作return 0;4、出栈/*函数功能:在栈中删除元素。参数;栈(SqStack S),元素(SElemty
5、pe e)。成功删除返回0,否则返回-1 */int Pop(SqStack &S,SElemType &e)if(S.top=S.base) return -1;e=*-S.top; /删除操作return 0;5、判断是否为回文/*函数功能:判断栈中的字符串是否为回文。参数; 栈(SqStack S)。是回文时返回1,否则返回0*/int IsReverse(SqStack &S)int i;char a;for(i=0;ij;i+)Pop(S,a);if(a!=bi) return 0;return 1;一_四、函数的调用主函数主要设计:int lpp;char ch;SqStack p
6、;InitStack(p);cout请输入字符:;while(ch=cin.get()&ch!=)Push(p,ch);bj=ch;j+;if (StackEmpty(p)=-1) cout此为空栈endl;return 0;lpp=IsReverse(p);if(lpp=0) cout此字符串不是回文。endl;else cout此字符串是回文。endl;一_五、实验总结通过这次试验我熟悉了对栈的基本操作,对基本的栈操作有了很好的掌握,知道自己容易在什么地方出错,。一_六、程序清单#includeusing namespace std;#define STACK_INIT_SIZE 100#
7、define STACKINCREMENT 10char bSTACK_INIT_SIZE+STACKINCREMENT;int j=0;typedef char SElemType;typedef struct SqStack SElemType *base; SElemType *top; int stacksize;SqStack;int InitStack(SqStack &S) S.base=(SElemType *)malloc(10*sizeof(SElemType);if(!S.base) return -1;S.top=S.base;S.stacksize=STACK_INI
8、T_SIZE;S.base=new SElemType;return 0;int StackEmpty(SqStack S)if(S.top=S.base) return -1;else return 0;int Push(SqStack &S,SElemType e)if(S.top-S.base=S.stacksize)S.base=(SElemType *)realloc(S.base,(S.stacksize+1) * sizeof(SElemType);if(!S.base) return -1; S.top=S.base+S.stacksize; S.stacksize+=STAC
9、KINCREMENT;*S.top+=e;return 0;int Pop(SqStack &S,SElemType &e)if(S.top=S.base) return -1;e=*-S.top;return 0;int IsReverse(SqStack &S)int i;char a;for(i=0;ij;i+)Pop(S,a);if(a!=bi) return 0;return 1;int main()int lpp;char ch;SqStack p;InitStack(p);cout请输入字符:;while(ch=cin.get()&ch!=)Push(p,ch);bj=ch;j+
10、;if (StackEmpty(p)=-1) cout此为空栈endl;return 0;lpp=IsReverse(p);if(lpp=0) cout此字符串不是回文。endl;else cout此字符串是回文。next=NULL;return 0;2、入队列int EnQueue(LinkQueue &Q,QElemType e)QueuePtr lpp;lpp=(QueuePtr)malloc(sizeof(QNode);if(!lpp) return -1;lpp-data=e; lpp-next=NULL; if(Q.front=NULL)Q.front-next=lpp;Q.rea
11、r=lpp; else Q.rear-next=lpp;Q.rear=lpp; return 0;3、出队列int DeQueue(LinkQueue &Q,QElemType &e)QueuePtr lpp;if(Q.front=Q.rear) return -1;lpp=Q.front-next;e=lpp-data;Q.front-next=lpp-next;if(Q.rear=lpp) Q.rear=Q.front;delete lpp;return 0;4、统计队列的长度int QueueLength(LinkQueue Q)QueuePtr lpp=Q.front;int i=0;
12、while(lpp!=Q.rear)i+;lpp=lpp-next;return i;5、查找队列的某个元素int QueueFind(LinkQueue Q,QElemType e)QueuePtr p;p=Q.front-next;while(p)if(p-data=e) return 1;p=p-next;return 0; 6、遍历队列int QueueTraverse(LinkQueue Q)QueuePtr p; p=Q.front-next;while(p) coutdatanext;coutendl;return 0;7、主界面函数void zhujiemian()couten
13、dl;cout【tt 数据结构实验二 】endl;cout【tt-】endl;cout【tt 1 队列初始化 】endl; cout【tt 2 出队列 】endl;cout【tt 3 入队列 】endl; cout【tt 4 队列长度 】endl;cout【tt 5 在队列中查找元素 】endl;cout【tt 6 遍历队列 】endl;cout【tt 其他键退出 】endl;cout【tt-】endl;couta;while(a!=1) couta;coutendl;doswitch(a)case 1:if(InitQueue(Q)=0)cout初始化成功!endl;elsecout初始化失
14、败!endl;break;case 2:if(QueueLength(Q)=0)cout队列为空无法出队!endl;break;if(DeQueue(Q,c)=0)cout删除成功!endl;elsecout删除失败!endl;break;case 3:cout输入你要入队元素c;if(EnQueue(Q,c) =0)cout入队成功!endl;elsecout入队失败!endl;break;case 4:b=QueueLength(Q);cout队列的长度为:bendl;break;case 5:coutb;if(QueueFind(Q,b)=1)cout恭喜您,队列中有您要找的元素bend
15、l;elsecout不好意思,队列中没有您要找的元素ba;cout0&a=6);说明:通过调用序列号不同的函数进行各种操作。函数根据每次输入的数进行判断不在16内的函数将结束,否则将继续进行。二_五、程序调试及运行结果分析 程序第一步必须执行初始化,否则程序不能运行。 在程序第一步必须执行初始化后,程序完美运行,在进行任何函数操作程序都是正常运行,而且本程序对插入和删除时进行错误检测如有的地方不可以插入,有点地方不能删除,如果队列为空时则程序会输出队列为空,并继续进行其他操作,大大减少了程序的bug。二_六、程序清单#includeusing namespace std;typedef int
16、 QElemType;typedef struct QNodeQElemType data;struct QNode *next;QNode, *QueuePtr;typedef structQueuePtr front;QueuePtr rear;int count;LinkQueue;int InitQueue(LinkQueue &Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front) return -1;Q.front-next=NULL;return 0;int EnQueue(LinkQueue &Q,QElemTy
17、pe e)QueuePtr lpp;lpp=(QueuePtr)malloc(sizeof(QNode);if(!lpp) return -1;lpp-data=e; lpp-next=NULL; if(Q.front=NULL)Q.front-next=lpp;Q.rear=lpp; else Q.rear-next=lpp;Q.rear=lpp; return 0;int DeQueue(LinkQueue &Q,QElemType &e)QueuePtr lpp;if(Q.front=Q.rear) return -1;lpp=Q.front-next;e=lpp-data;Q.fron
18、t-next=lpp-next;if(Q.rear=lpp) Q.rear=Q.front;delete lpp;return 0;int QueueLength(LinkQueue Q)QueuePtr lpp=Q.front;int i=0;while(lpp!=Q.rear)i+;lpp=lpp-next;return i;int QueueTraverse(LinkQueue Q)QueuePtr p; p=Q.front-next;while(p) coutdatanext;coutnext;while(p)if(p-data=e) return 1;p=p-next;return 0; void zhujiemian()coutendl;cout【tt 数据结构实验二 】endl;cout【tt-】endl;cout【t
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 瓜类病虫害防治策略
- 雅居乐物业提升-工程贴心服务方案
- 房地产财务工作计划方案样本
- 医院感染控制策略:暴发概念探讨
- 动态心电图在急诊医学中的应用
- 艺术展览:房地产招商手册
- 医院感染防控:应对细菌感染流行
- 2024年临时救助申请书范文
- 2024年《阿甘正传》观后感(15篇)
- 2024年《鲁滨逊漂流记》读后感汇编15篇
- 老年社会工作课件
- 火车站、高铁站钢结构无柱雨棚防腐涂料施工方案
- 电动吊篮安装拆除专项施工方案(27页)
- 地下管网数据采集标准及计价标准
- 金融市场学-张亦春-第三版-官方PPT_(5)
- 部编版四年级语文下册知识点整理(全部考点)
- 班组长管理能力提升培训(PPT96张)课件
- 钢结构设计图中的焊接符号标注大全(图)
- ansys教学算例集汽轮机内蒸汽平衡态与非平衡态仿真分析
- 人教版九年级数学上册同步练习题 22.2二次函数与一元二次方程
- 职业分类大典(2015年版).xls
评论
0/150
提交评论