数据结构栈和队列上机报告教程.docx

数据结构 栈和队列 一 上机的目的和要求 实验目的： 1.??掌握实现栈/队列的基本操作方法 2.??掌握栈的基本操作：建栈，Push，Pop等运算在顺序存储上的实现 3.?掌握队列的基本操作：建队列，入队，出队等运算在顺序存储结构上的实现 队列的实验参照栈编程实现。 实验报告要求： 1. 上机前完成所有的函数编写 2.??实验记录部分填写编写主函数调用所写所有函数的屏幕输出 3.??实验总结部分填写对该次实验所编写函数的运行情况，和在实验过程中对栈的认识和实现情况? 二 基本知识和原理 ??栈和队列是两种常用的数据结构，栈和队列是操作受限的线性表，栈和队列的数据元素具有单一的前驱和后继的线性关系；栈和队列又是两种重要的抽象数据类型。??栈是限定在表尾进行插入和删除操作的线性表允许插入和删除的一端为栈顶，另一端为栈底，出栈元素只能是栈顶元素，后进先出，相邻元素具有前驱与后继关系。??队列是只允许在一端进行插入操作，在另一端进行删除操作的线性表。允许插入的一端为队尾，允许删除的一端为队头，先进先出，相邻元素具有前驱与后继关系。 三 程序算法分析及实现代码 #include stdio.h #include conio.h #define MaxSize 100 /*栈中的元素的最大个数*/ typedef int ElemType; typedef struct { ElemType data[MaxSize];/*存放堆栈的数组*/ int top;/*栈顶元素*/ }Stack,*S; /*堆栈的初始化*/ void InitStack(Stack *S) { /*指向的是最顶端的元素 取值范围为从0~MaxSize-1 为-1时说明为空栈*/ S-top=-1; } int StackEmpty(SqStack *s) //判断是否为空 { if(s-top==s-base) { return TRUE; } else { return 0; } } int GetTop(SqStack* s,int *e) //取栈顶 { //若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR if(s-top==s-base) { return ERROR; } *e=*(s-top-1); return 1; } int Push(SqStack *s,int e) //进栈 { //插入元素e为新的栈顶元素 if(s-top-s-base=s-stacksize) { //栈满，追加存储空间 s-base=(int *)malloc(SIZE*sizeof(int)); if(!s-base) exit(OVERFLOW); s-top=s-base + s-stacksize; s-stacksize +=SIZE; } *(s-top)++=e; return 1; } int Pop(SqStack *s ,int *e)//出栈 { // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR if(s-base == s-top) return ERROR; *e = *--s-top; return 1; } int main ( ) {SqStack sq; InitStack(sq); int e; int N; int k; int n=0; Z: { printf(\n\t********************************************); printf(\n\t*** 请你输入相应的操作序号进行操作 ***); printf(\n\t*** 1.是否空 ***); printf(\n\t*** 2.取栈顶元素 ***); printf(\n\t*** 3.进栈 ***); printf(\n\t*** 4.出栈 ***); printf(\n\t*** 0. 退出 ***\n); printf(\t*********