TCU_ZzR_实验3栈和队列

1、.数据构造A班级：软件二班学号：1607070212：X曾然日期：2021/10/25实验三 栈、队列的实现及简单应用一、实验目的1. 熟悉理解栈和队列的根本操作。2. 会使用栈和队列的根本操作求解一些实际问题。二、实验要求1. 根据布置的作业编写源程序，上机验证实验结果；2. 独立做实验，输入、调试所编程序；3. 实验完毕后，根据实验报告模板编写实验报告。三、实验内容和步骤用 Visual C+作为实验开发环境，创立一个Win32 Console Application工程，工程名为你的学号，添加下面文件：1数据构造定义：以seqStackDef.h和cirQueueDef.h为文件名； 2

2、根本操作和算法：以seqStackAlgo.h和cirQueueAlgo.h为文件名； 3调用根本操作和实现应用的主程序： 以stackQueueMain.cpp为文件名。 编写程序完成以下功能，文件seqStackDef.h定义顺序栈的构造体，文件cirQueueDef.h定义循环队列的构造体，文件seqStackAlgo.h实现栈在下面应用中所需的根本操作，文件cirQueueAlgo.h实现队列在下面应用中所需的根本操作，文件stackQueueMain.cpp中编写以下算法：源程序：seqStackDef.h：*define MAXSIZE 1024 /顺序栈最大长度typedef c

3、har elemtype;/elemtype可以为任意类型，假设为inttypedef struct SequenStackelemtype dataMAXSIZE;/将顺序栈定义为一维数组int top;SequenStack; /顺序栈的构造类型为SequenStackseqStackAlgo.h：SequenStack * Init_SequenStack()/申请内存空间SequenStack *S;S=(SequenStack *) malloc (sizeof(SequenStack);return S;int SequenStack_Empty(SequenStack *S)/判

4、断栈空if(S->top=-1)return 1;elsereturn 0;int SequenStack_Full(SequenStack *S)/判断栈满if(S->top+1=MAXSIZE)return 1;elsereturn 0;int SequenStack_Length(SequenStack *S)/取顺序栈的长度return(S->top+1);int Push_SequenStack(SequenStack *S,elemtype x)/入栈操作if(S->top>=MAXSIZE-1)printf("overflown"

5、);return 0;S->top+;S->dataS->top=x;return 1;int Pop_SequenStack(SequenStack *S,elemtype *x)/出栈操作if(S->top=-1) printf("overflown");return 0;else *x=S->dataS->top;S->top-;return 1;int GetTop_SequenStack(SequenStack *S,elemtype *x)/取栈顶元素if(S->top=-1) printf("overf

6、lown");return 0;else*x=S->dataS->top;return 1;cirQueueDef.h：*define MAXSIZE 1024/顺序队列最大长度typedef char elemtype;typedef struct SequenQueueelemtype dataMAXSIZE;int front; /定义头指针int rear; /定义尾指针SequenQueue;cirQueueAlgo.h：SequenQueue * Init_SequenQueue()/初始化队列SequenQueue *Q;Q=(SequenQueue *)m

7、alloc(sizeof(SequenQueue);Q->front=0;Q->rear=0;return Q;int SequenQueue_Empty(SequenQueue *Q)/判断队空if(Q->front=Q->rear)return 1;/空elsereturn 0;/不空int SequenQueue_Full(SequenQueue *Q)/判断队满if(Q->rear+1)%MAXSIZE=Q->front)return 1;elsereturn 0;int SequenQueue_Length(SequenQueue *Q)/取队列长

8、度return (Q->rear-Q->front+MAXSIZE)%MAXSIZE);int Enter_SequenQueue(SequenQueue *Q,elemtype x)/元素入队if(SequenQueue_Full(Q)return 0;/队满Q->dataQ->rear = x;Q->rear=(Q->rear+1)%MAXSIZE;return 1;int Delete_SequenQueue(SequenQueue *Q,elemtype *x)/队头元素出队if(Q->rear=Q->front)return 0;/队空

9、else*x=Q->dataQ->front;Q->front=(Q->front+1)%MAXSIZE;return 1;int GetFront_SequenQueue(SequenQueue *Q,elemtype *x)/取队头元素if(Q->rear=Q->front)return 0;/队空else*x=Q->dataQ->front;return 1;1. 函数Conversion实现进制转换。将十进制整数转换为二、八和十六进制数输出，要求用栈实现，栈中数据元素为char型。源程序：*include<stdio.h>*i

10、nclude<stdlib.h>*include"seqStackDef.h"*include"seqStackAlgo.h"*include"cirQueueDef.h"*include"cirQueueAlgo.h"void Conversion(int N,int d);int Inversion(char* a);void main()int N,d;printf("需要转换的十进制数为：");scanf("%d",&N);printf("

11、;n需要转换到几进制：");scanf("%d",&d); Conversion(N,d);void Conversion(int N,int d)elemtype *e,k;e=(elemtype *)malloc(sizeof(elemtype);int y;SequenStack *S=Init_SequenStack();printf("n%d转换到%d进制的数为",N,d);while(N>0)y=N%d;if(y<10)k=y+48;elsek=y+55;Push_SequenStack(S,k);N=N/d;w

12、hile(!SequenStack_Empty(S)Pop_SequenStack(S,e);printf("%c",*e);运行结果截图：2. 函数Inversion实现回文检测，判断字符串是否为回文，例abcba和123321为回文，字符串从键盘输入，要求用栈和队列实现。源程序：*include<stdio.h>*include<stdlib.h>*include"seqStackDef.h"*include"seqStackAlgo.h"*include"cirQueueDef.h"*

13、include"cirQueueAlgo.h"int Inversion(char* a);void main()char str20;int flag;printf("nn判断回文：请输入字符串n");scanf("%s",str);flag=Inversion(str);if(flag=1)printf("您所输入的数是回文");else printf("您所输入的数不是回文");int Inversion(char* a)int i=0;elemtype *x,*y;x=(elemtype *)malloc(sizeof(elemtype);y=(elemtype *)malloc(sizeof(elemtype); SequenStack *s=Init_SequenStack();SequenQueue *q=Init_SequenQueue();while(ai!='0')Push_SequenStack(s,ai);Enter_SequenQueue(q,ai);i+;while(!SequenStack_