电大实验3-栈、队列、递归程序设计实验报告(共12页).docx
精选优质文档-倾情为你奉上数据结构课程实验报告学生姓名王稼骏学 号49班 级指导老师实验名称栈、队列、递归程序设计实验成绩实验报告实验概述实验目的：编写一个算法，输出指定栈中的栈底元素，并使得原栈中的元素倒置。实验要求：（1）正确理解栈的先进后出的操作特点，建立初始栈，通过相关操作显示栈底元素。（2）程序中要体现出建栈过程和取出栈底元素后恢复栈的入栈过程，按堆栈的操作规则打印结果栈中的元素。实验基本原理：（1）采用顺序栈，即用数组存储栈元素。（2）设定一个临时队列，用来存放从初始栈中出栈的元素。（3）取出栈底元素后，将队列中的元素逐一出队并压入初始栈中。实验内容实验设计思路、步骤和方法等：（1） 根据栈的先进后出特点，来进行实验（2） 建立顺序栈、临时队列、依次取出压入栈实验过程（实验中涉及的记录、数据、分析）：#include <stdio.h>#include <stdlib.h>#define MaxSize 100typedef int ElemType;typedef struct ElemType dataMaxSize; int top; SeqStack; typedef struct ElemType dataMaxSize; int front,rear; SeqQueue; void InitStack(SeqStack *s);int StackEmpty(SeqStack *s);int StackFull(SeqStack *s);void Push(SeqStack *s,ElemType x);ElemType Pop(SeqStack *s);ElemType GetTop(SeqStack *s);void DispStack(SeqStack *s);void DispBottom(SeqStack *s);void InitQueue(SeqQueue *sq);int QueueEmpty(SeqQueue *sq);void InQueue(SeqQueue *sq,ElemType x);ElemType OutQueue(SeqQueue *sq,ElemType x); ElemType GetQueue(SeqQueue *sq)void main() SeqStack *s; SeqQueue *sq; ElemType x; int n,i; printf("(1)初始化栈sn"); s=(SeqStack *)malloc(sizeof(SeqStack); InitStack(s); printf("(2)栈为%sn",(StackEmpty(s)?"空":"非空"); printf("(3)输入要进栈的数据个数："); scanf("%d",&n);printf("依次输入进栈的%d个整数：",n); for(i=0; i<n; i+) scanf("%d",&x); Push(s,x); printf("(4)栈为%sn",(StackEmpty(s)?"空":"非空"); printf("(5)从栈顶到栈底的元素依次为:"); DispStack(s); printf("(6)栈底元素为:"); DispBottom(s); printf("(7)初始化队列sqn"); sq=(SeqQueue *)malloc(sizeof(SeqQueue); InitQueue(sq); printf("(8)队列为%sn",(QueueEmpty(sq)?"空":"非空"); printf("(9)出栈/入队的元素依次为:"); while(!StackEmpty(s) x=Pop(s); printf("%d ",x); InQueue(sq,x); printf("n"); printf("(10)栈为%s,",(StackEmpty(s)?"空":"非空"); printf("队列为%sn",(QueueEmpty(sq)?"空":"非空"); printf("(11)出队/进栈的元素依次为:"); while(!QueueEmpty(sq) x=OutQueue(sq,x); printf("%d ",x); Push(s,x); printf("n"); printf("(12)栈为%s,",(StackEmpty(s)?"空":"非空"); printf("队列为%sn",(QueueEmpty(sq)?"空":"非空"); printf("(13)从栈顶到栈底的元素依次为:"); DispStack(s); printf("(14)栈底元素为:"); DispBottom(s); free(s); free(sq); void InitStack(SeqStack *s) s->top=-1;int StackEmpty(SeqStack *s) if(s->top=-1) return 1; else return 0; /*否则返回0 */int StackFull(SeqStack *s) if(s->top=MaxSize-1) return 1; else return 0; void Push(SeqStack *s,ElemType x) if (StackFull(s) printf("栈满溢出错误！n"); exit(1); s->top+; s->datas->top=x;ElemType Pop(SeqStack *s) if(StackEmpty(s) printf("栈下溢错误！n"); exit(1); s->top-; return s->datas->top+1;ElemType GetTop(SeqStack *s) if(StackEmpty(s) printf("栈下溢错误！n"); exit(1); return s->datas->top;void DispStack(SeqStack *s) int i; for(i=s->top; i>=0; i-) printf("%d ",s->datai); printf("n");void DispBottom(SeqStack *s) printf("%d ",s->data0); printf("n");void InitQueue(SeqQueue *sq) sq->front=sq->rear=0;int QueueEmpty(SeqQueue *sq) if(sq->rear=sq->front) return 1; else return 0;void InQueue(SeqQueue *sq,ElemType x) if (sq->rear+1)%MaxSize=sq->front) printf("循环队列已满！n"); exit(1); sq->datasq->rear=x; sq->rear=(sq->rear+1)%MaxSize; ElemType OutQueue(SeqQueue *sq,ElemType x) if(QueueEmpty(sq) /*队空*/ printf("循环队列已空，不能进行出队操作！n"); exit(1); else x=sq->datasq->front; sq->front=(sq->front+1)%MaxSize; return x; ElemType GetQueue(SeqQueue *sq) if(QueueEmpty(sq) printf("队列已空，不能进行出队操作！n"); exit(1); return sq->datasq->front;实验结果：（1） 初始化栈（2） 栈为空（3） 输入要进栈的数据个数为5，依次输入进栈的5个整数：1 2 3 4 5（4） 栈为非空（5） 从栈顶到栈底的元素依次为：5 4 3 2 1（6） 栈底元素为：1（7） 初始化队列为：1（8） 队列为空（9） 出栈/入队的元素依次为： 5 4 3 2 1 （10） 栈为空，队列为空（11） 出队/进栈的元素依次为：5 4 3 2 1（12） 栈为非空，队列为空（13） 从栈顶到栈底的元素依次为：1 2 3 4 5（14） 栈底元素为：5实验小结实验的心得体会：栈和队列都是运算受限的线性表。栈是后进先出（LIFO）表，只能在栈顶做插入删除运算。队列是先进先出（FIFO）表，在队尾插入，在队头删除。实验思考：实验中采用的是顺序存储的栈和循环队列，要注意栈空、栈满、队空、队满的判断。指导教师评语 指导教师 日期专心-专注-专业
