《实验三 栈和队列指导书》由会员分享，可在线阅读，更多相关《实验三 栈和队列指导书（22页珍藏版）》请在金锄头文库上搜索。
1、1实验三 栈和队列3.1 实验目的：（1） 熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现；（2） 熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基本操作在队列的顺序存储结构和链式存储结构上的实现。3.2 实验要求：（1） 复习课本中有关栈和队列的知识；（2） 用 C 语言完成算法和程序设计并上机调试通过；（3） 撰写实验报告，给出算法思路或流程图和具体实现（源程序） 、算法分析结果（包括时间复杂度、空间复杂度以及算法优化设想） 、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果） 。3.3
2、 基础实验实验 1 栈的顺序表示和实现实验内容与要求:编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化顺序栈（2）插入元素（3）删除栈顶元素（4）取栈顶元素（5）遍历顺序栈（6）置空顺序栈分析:栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p-top= =MAXNUM-1，栈满时，不能入栈; 否则出现空间溢出，引起错误，这种现象称为上溢。出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件。注意：（1）顺序栈中元素用向量存放（2）栈底位置是固定不
3、变的，可设置在向量两端的任意一个端点（3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量 top（通常称 top 为栈顶指针）来指示当前栈顶位置参考程序:#include#include2#define MAXNUM 20#define ElemType int/*定义顺序栈的存储结构*/typedef struct ElemType stackMAXNUM;int top;SqStack;/*初始化顺序栈*/void InitStack(SqStack *p) if(!p)printf(Eorror);p-top=-1;/*入栈*/void Push(SqStack *p,ElemTyp
4、e x) if(p-toptop=p-top+1;p-stackp-top=x;elseprintf(Overflow!n);/*出栈*/ElemType Pop(SqStack *p) ElemType x;if(p-top!=0) x=p-stackp-top;printf(以前的栈顶数据元素%d 已经被删除！n,p-stackp-top);p-top=p-top-1;return(x);else printf(Underflow!n);return(0);/*获取栈顶元素*/ElemType GetTop(SqStack *p) ElemType x;if(p-top!=0) x=p-s
5、tackp-top;return(x);else3 printf(Underflow!n);return(0);/*遍历顺序栈*/void OutStack(SqStack *p) int i;printf(n);if(p-toptop;i=0;i-)printf(第%d 个数据元素是：%6dn,i,p-stacki);/*置空顺序栈*/void setEmpty(SqStack *p)p-top= -1;/*主函数*/main() SqStack *q;int y,cord;ElemType a;doprintf(n);printf(第一次使用必须初始化！n);printf(n);print
6、f(n 主菜单 n);printf(n 1 初始化顺序栈 n);printf(n 2 插入一个元素 n);printf(n 3 删除栈顶元素 n);printf(n 4 取栈顶元素 n);printf(n 5 置空顺序栈 n);printf(n 6 结束程序运行 n);printf(n-n);printf(请输入您的选择( 1, 2, 3, 4, 5,6);scanf(%d,printf(n);switch(cord) case 1: q=(SqStack*)malloc(sizeof(SqStack);InitStack(q);OutStack(q);break;4case 2: print
7、f(请输入要插入的数据元素：a=);scanf(%d,Push(q,a);OutStack(q);break;case 3: Pop(q);OutStack(q);break;case 4: y=GetTop(q);printf(n 栈顶元素为：%dn,y);OutStack(q);break;case 5: setEmpty(q);printf(n 顺序栈被置空！n);OutStack(q);break;case 6:exit(0);while (cordtop=NULL;printf(n 已经初始化链栈！n);/*链栈置空*/void setEmpty(LinkStack * s) s-t
8、op=NULL;printf(n 链栈被置空！n);/*入栈*/void pushLstack(LinkStack * s, Elemtype x) StackNode * p;p=(StackNode *)malloc(sizeof(StackNode); /建立一个节点。p-data=x;p-next=s-top; /由于是在栈顶 pushLstack，所以要指向栈顶。s-top=p; /插入/*出栈*/Elemtype popLstack(LinkStack * s) Elemtype x;StackNode * p;p=s-top; /指向栈顶if (s-top =0) printf(
9、n 栈空，不能出栈！n);exit(-1);x=p-data; s-top=p-next; /当前的栈顶指向原栈的 nextfree(p); /释放return x;6/*取栈顶元素*/Elemtype StackTop(LinkStack *s) if (s-top =0) printf(n 链栈空n);exit(-1);return s-top-data;/*遍历链栈*/void Disp(LinkStack * s) printf(n 链栈中的数据为：n);printf(=n);StackNode * p;p=s-top;while (p!=NULL) printf(%dn,p-data
10、);p=p-next;printf(=n);void main() printf(= 链栈操作=nn);int i,m,n,a;LinkStack * s;s=(LinkStack *)malloc(sizeof(LinkStack);int cord;do printf(n);printf(第一次使用必须初始化！n);printf(n);printf(n 主菜单 n);printf(n 1 初始化链栈 n);printf(n 2 入栈 n);printf(n 3 出栈 n);printf(n 4 取栈顶元素 n);printf(n 5 置空链栈 n);printf(n 6 结束程序运行 n)
11、;printf(n-n);printf(请输入您的选择( 1, 2, 3, 4, 5,6);scanf(%d,printf(n);switch(cord) case 1: InitStack(s);7Disp(s);break;case 2:printf(输入将要压入链栈的数据的个数：n=);scanf(%d,printf(依次将%d 个数据压入链栈：n,n);for(i=1;i#include #define MAXNUM 100#define Elemtype int#define TRUE 1#define FALSE 0typedef struct Elemtype queueMAXN
12、UM;int front;int rear;sqqueue;/*队列初始化*/int initQueue(sqqueue *q) if(!q) return FALSE;q-front=-1;q-rear=-1;return TRUE;/*入队*/int append(sqqueue *q, Elemtype x) if(q-rear=MAXNUM-1) return FALSE;q-rear+;q-queueq-rear=x;9return TRUE;/*出队*/Elemtype Delete(sqqueue *q) Elemtype x;if (q-front=q-rear) return
13、 0;x=q-queue+q-front;return x;/*判断队列是否为空*/int Empty(sqqueue *q) if (q-front=q-rear) return TRUE;return FALSE; /*取队头元素*/int gethead(sqqueue *q) if (q-front=q-rear) return 0;return(q-queueq-front+1); /*遍历队列*/void display(sqqueue *q) int s;s=q-front;if (q-front=q-rear)printf(队列空!n);elseprintf(n 顺序队列依次为：);while(srear)s=s+1;printf(%dqueues);printf(n);printf(顺序队列的队尾元素所在位置:rear=%dn,q-rear);printf(顺序队列的队头元素所在位置:front=%dn,q-front);/*建立顺序队列*/void Setsqqueue(sqqueue *q) int n,i,m;printf(n 请输入将要入顺序队列的长度:);scanf(%d,printf(n 请依次输入入顺序队列的元素值:n);for (i=0;i#include#define ElemType inttypedef s
