2022年武汉理工数据结构实验栈和队列基本操作和应用借鉴 .pdf

《2022年武汉理工数据结构实验栈和队列基本操作和应用借鉴 .pdf》由会员分享，可在线阅读，更多相关《2022年武汉理工数据结构实验栈和队列基本操作和应用借鉴 .pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验2 栈和队列的基本操作和应用1实验目的(1) 熟练掌握顺序栈的基本操作。(2) 掌握顺序栈的应用。(3) 掌握顺序循环队列的基本操作。(4) 掌握链式队列的基本操作。2实验内容(1) 设计一个顺序栈的基本操作的演示程序；(2) 利用顺序栈，进行整数的不同进制之间的转换；(3) 设计一个顺序循环队列的基本操作演示程序；(4) 设计一个链式队列的基本操作演示程序。【基本要求】I. 实验内容 (1)的基本要求：编写一个程序，将一个顺序栈的元素依次取出，并打印其元素值。II. 实验内容 (2)的基本要求：编写一个程序，将一个非负的十进制整数转换成二进制。III. 实验内容 (3)的基本要求：编写一

2、个程序，将一个顺序队列的元素依次取出，并打印其元素值。IV. 实验内容 (4)的基本要求：编写一个程序，将一个链式队列的元素依次取出，并打印其元素值。【测试数据】自定3实验结果按照学校实验格式要求撰写实验报告，内容主要包括1）实验目的；2）实验内容； 3）实验环境和方法；4）实验过程描述； 5）实验心得体会名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 14 页 - - - - - - - - - 参考程序如下：实验内容（ 1）参考程序/*sqStack.h文件 */#d

3、efine INIT_SIZE 100#define INCREMENT 10typedef int ElemType;/typedef char ElemType;typedef struct SqStack ElemType *base;ElemType *top;int stacksize;SqStack;enum StatusOK,ERROR,OVERFLOW;/*sqStackOp.h 文件 */#include sqStack.hStatus InitStack(SqStack &S) ;Status GetTop(SqStack S,ElemType &e);Status Pus

4、h(SqStack &S,ElemType e);Status Pop(SqStack &S,ElemType &e);bool StackEmpty(SqStack &S);/*sqStackOp.cpp 文件 */#include #include #include sqStackOp.hStatus InitStack(SqStack &S) /构造一个空的栈 S.base=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType); if(! S.base) exit(OVERFLOW); / 存储分配失败名师资料总结 - - -精品资料欢迎下载 - -

5、- - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 14 页 - - - - - - - - - S.top=S.base; S.stacksize=INIT_SIZE; return OK; /InitStackStatus GetTop(SqStack S,ElemType &e)/若栈不空，则用 e返回 S的栈顶元素，并返回OK；否则返回 ERROR if(S.top=S.base) return ERROR; e=*(S.top-1); return OK; /GetTopStatus Push(SqStack &S

6、,ElemType e)/插入元素 e为新的栈顶元素 if(S.top-S.base=S.stacksize) /栈满，追加存储空间 S.base=(ElemType *)realloc(S.base,(S.stacksize+INCREMENT)*sizeof(ElemType); if(!S.base)exit(OVERFLOW); / 存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=INCREMENT; *S.top+=e;return OK; /PushStatus Pop(SqStack &S,ElemType &e)/若栈不空，则删除 S

7、的栈顶元素，用 e返回其值，并返回OK；否则返回ERROR if(S.top=S.base) return ERROR; e=*(-S.top); return OK; /Push名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 14 页 - - - - - - - - - /判断栈是否为空bool StackEmpty(SqStack &S)if(S.top = S.base) return true;else return false;/*main.cpp 文件 */#

8、include #include #include sqStackOp.hvoid main()printf(Hellow stack n);SqStack S; /定义顺序栈 Sif(OK != InitStack(S) printf( 顺序栈初始化出错，退出.n); exit(-1);Push(S, 1);Push(S,2);Push(S,3);int e;Pop(S, e);printf( 出栈元素 = %d n,e);Push(S,4);Push(S,5);while(!StackEmpty(S) Pop(S, e);名师资料总结 - - -精品资料欢迎下载 - - - - - - -

9、 - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 14 页 - - - - - - - - - printf( 出栈元素 = %d n,e); /*SqStack S; char x,y; InitStack(S); x=c;y=k; Push(S,x); Push(S,a); Push(S,y); Pop(S,x); Push(S,t); Push(S,x); Pop(S,x); Push(S,s); while(!StackEmpty(S) Pop(S,y);printf(%c ,y); ; printf(%c ,x);*/getcha

10、r();实验内容（ 2）参考程序/*sqStack.h 文件 */#define INIT_SIZE 100#define INCREMENT 10typedef int ElemType;typedef struct SqStack ElemType *base;ElemType *top;int stacksize;SqStack;enum StatusOK,ERROR,OVERFLOW;/*sqStackOp.h 文件 */#include sqStack.h名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -

11、 - - - - - - 第 5 页，共 14 页 - - - - - - - - - Status InitStack(SqStack &S) ;Status GetTop(SqStack S,ElemType &e);Status Push(SqStack &S,ElemType e);Status Pop(SqStack &S,ElemType &e);bool StackEmpty(SqStack &S);/*sqStackOp.cpp 文件 */#include #include #include sqStackOp.hStatus InitStack(SqStack &S) /构造

12、一个空的栈 S.base=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType); if(! S.base) exit(OVERFLOW); / 存储分配失败 S.top=S.base; S.stacksize=INIT_SIZE; return OK; /InitStackStatus GetTop(SqStack S,ElemType &e)/若栈不空，则用 e返回 S的栈顶元素，并返回OK；否则返回 ERROR if(S.top=S.base) return ERROR; e=*(S.top-1); return OK; /GetTopStatus Pu

13、sh(SqStack &S,ElemType e)/插入元素 e为新的栈顶元素 if(S.top-S.base=S.stacksize) /栈满，追加存储空间 S.base=(ElemType *)realloc(S.base,名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 14 页 - - - - - - - - - (S.stacksize+INCREMENT)*sizeof(ElemType); if(!S.base)exit(OVERFLOW); / 存储分配失败

14、 S.top=S.base+S.stacksize; S.stacksize+=INCREMENT; *S.top+=e;return OK; /PushStatus Pop(SqStack &S,ElemType &e)/若栈不空，则删除 S的栈顶元素，用 e返回其值，并返回OK；否则返回ERROR if(S.top=S.base) return ERROR; e=*(-S.top); return OK; /Push/判断栈是否为空bool StackEmpty(SqStack &S)if(S.top = S.base) return true;else return false;/*ma

15、in.cpp 文件 */#include #include #include sqStackOp.hvoid main()SqStack s;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 14 页 - - - - - - - - - int x;InitStack(s);scanf(%d,&x); /%d- 十进制输入； %O-八进制输入； %x-十六进制输入 /修改这里输入进制和下面整除和余数计算，就可以获得其他进制的转换while(x!=0) Push(s,x%8)

16、; x=x/8; while(!StackEmpty(s) Pop(s,x); printf(%d ,x); printf(n);getchar();实验内容（ 3）参考程序/*sqQueue.h 文件 */#define MAXQSIZE 100typedef int QElemType;typedef struct SqQueue QElemType *base;int front; int rear;SqQueue;enum StatusOK,ERROR,OVERFLOW;/*sqQueueOp.h 文件 */名师资料总结 - - -精品资料欢迎下载 - - - - - - - - -

17、- - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 14 页 - - - - - - - - - #include sqQueue.hStatus InitQueue (SqQueue &Q) ;Status EnQueue (SqQueue &Q, QElemType e);Status DeQueue (SqQueue &Q, QElemType &e) ;bool QueueEmpty(SqQueue &Q);int QueueLength(SqQueue Q);/*sqQueueOp.cpp 文件 */#include #include #in

18、clude sqQueueOp.hStatus InitQueue (SqQueue &Q) / 构造一个空队列 Q Q.base = (QElemType *) malloc (MAXQSIZE *sizeof (QElemType); if (!Q.base) exit (OVERFLOW); / 存储分配失败 Q.front = Q.rear = 0; return OK;Status EnQueue (SqQueue &Q, QElemType e) / 插入元素 e为Q的新的队尾元素 if (Q.rear+1) % MAXQSIZE = Q.front) return ERROR;

19、/队列满 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 14 页 - - - - - - - - - Status DeQueue (SqQueue &Q, QElemType &e) / 若队列不空，则删除Q的队头元素， / 用e返回其值，并返回 OK; 否则返回 ERROR if (Q.front = Q.rear) return ERROR; e

20、 = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; return OK;/判断队列是否为空bool QueueEmpty(SqQueue &Q)if(Q.front= Q.rear) return true;else return false;/计算循环队列长度int QueueLength(SqQueue Q)return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;/*main.cpp 文件 */#include #include #include sqQueueOp.hvoid main()prin

21、tf(Hello Queue n);SqQueue Q; /定义顺序队列 QQElemType e;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 14 页 - - - - - - - - - if(OK != InitQueue(Q) printf( 顺序队列初始化出错，退出.n); exit(-1);EnQueue(Q,1);EnQueue(Q,3);EnQueue(Q,5);EnQueue(Q,7); printf( 当前队列长度 = %d n,QueueLeng

22、th(Q);DeQueue(Q,e);printf( 队首元素 %d出队，当前队列长度=%dn,e,QueueLength(Q);EnQueue(Q,9);EnQueue(Q,11);while(!QueueEmpty(Q) DeQueue(Q,e); printf( 队首元素 %d出队，当前队列长度=%dn,e,QueueLength(Q); getchar();实验内容（ 4）参考程序/*linkQueue.h 文件 */typedef int QElemType;typedef struct QNode / 结点类型 QElemType data; struct QNode *next;

23、 QNode, *QueuePtr;typedef struct / 链队列类型名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 14 页 - - - - - - - - - QueuePtr front; / 队头指针 QueuePtr rear; / 队尾指针 LinkQueue;enum StatusOK,ERROR,OVERFLOW;/*linkQueueOp.h 文件 */#include linkQueue.hStatus InitQueue (LinkQue

24、ue &Q) ;Status EnQueue (LinkQueue &Q, QElemType e);Status DeQueue (LinkQueue &Q, QElemType &e) ;bool QueueEmpty(LinkQueue &Q);/*linkQueueOp.cpp 文件 */#include #include #include linkQueueOp.hStatus InitQueue (LinkQueue &Q) / 构造一个空队列 Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!Q.front) ex

25、it (OVERFLOW); /存储分配失败 Q.front-next = NULL; return OK;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 14 页 - - - - - - - - - Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素 e为Q的新的队尾元素 QueuePtr p = (QueuePtr) malloc (sizeof (QNode); if (!p) exit (OVERFLOW); /存

26、储分配失败 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK;Status DeQueue (LinkQueue &Q, QElemType &e) / 若队列不空，则删除Q的队头元素， /用 e 返回其值，并返回 OK；否则返回 ERROR if (Q.front = Q.rear) return ERROR; QueuePtr p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear = p) Q.rear = Q.front; free

27、(p); return OK;/判断队列是否为空bool QueueEmpty(LinkQueue &Q)if(Q.front = Q.rear) return true;else return false;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 14 页 - - - - - - - - - /*main.cpp 文件 */#include #include #include linkQueueOp.hvoid main()printf(Hello LinkQu

28、eue n);LinkQueue Q; /定义顺序队列 QQElemType e;if(OK != InitQueue(Q) printf( 顺序队列初始化出错，退出.n); exit(-1);EnQueue(Q,1);EnQueue(Q,3);EnQueue(Q,5);EnQueue(Q,7); DeQueue(Q,e);printf( 队首元素 %d出队， n,e);EnQueue(Q,9);EnQueue(Q,11);while(!QueueEmpty(Q) DeQueue(Q,e); printf( 队首元素 %d出队， n,e); getchar();名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 14 页 - - - - - - - - -