数据结构-实验3-程序栈和队列的实现.doc

《数据结构-实验3-程序栈和队列的实现.doc》由会员分享，可在线阅读，更多相关《数据结构-实验3-程序栈和队列的实现.doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程实验报告实验名称程序栈和队列的实现实验序号3实验日期2012-4-18姓 名曹志华院系计算机科学与信息工程学院班 级C1学 号专 业计算机科学与技术指导教师武伟成 绩教师评语一、实验目的和要求1. 理解栈和队列的特性以及它们之间的差异，知道在何时使用哪种数据结构；2. 掌握栈和队列的顺序存储结构及其基本运算实现；3. 注意栈满和栈空的条件；4. 重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队满和队空的条件；5. 灵活运用栈和队列这两种数据结构解决一些综合应用问题。二、实验项目摘要实验1：编写一个程序，实现顺序栈的各类基本运算，并在此基础上设计一个主程序完成如下功能：

2、1. 初始化栈s；2. 判断栈s是否非空；3. 以此进栈元素a,b,c,d,e;4. 判断栈s是否非空；5. 输出栈长度；6. 输出从栈顶到栈底元素；7. 输出出栈序列；8. 判断栈s是否非空；9. 释放栈。 实验2：编写一个程序，实现顺序环形队列的各类基本运算，并在此基础上设计一个主程序完成如下功能： 1 初始化队列q； 2 判断队列q是否为空； 3 依次进队元素a,b,c； 4 出队一个元素，输出该元素； 5 输出队列q的元素个数；6 依次进队列元素d,e,f； 7 输出队列q的元素个数； 8 输出出队序列；9 释放队列。三、实验预习内容1，栈和环形队列的顺序存储结构及其基本运算实现栈的顺

3、序存储结构以及基本运算实现：l 初始化栈l 销毁栈l 求栈的长度l 判断栈是否为空l 进栈（Push）l 出栈（Pop）l 显示栈中元素 2. 环形队列的性质：环形队列的队头指针和队尾指针初始化时都置为0；三、实验结果与分析 1. 实验结果： 实验1：实验2：2.实验分析： 本次实验需要对栈和队列进行充分的了解，虽然栈和队列实质上是不同的，但在编写程序时大致相似。通常栈可以用顺序的方式存储，分配一块连续的存储区域存放栈中元素，并用一个变量指向当前的栈顶。而队列的顺序存储结构需要使用一个数组和两个整数型变量来实现。3.源代码 实验1：#include#include#define MaxSize

4、 1024 typedef char ElemType;typedef struct ElemType data MaxSize;int top ;SqStack;void InitStack(SqStack *&s)/初始化栈 s=(SqStack *)malloc(sizeof(SqStack);s-top=-1;int StackEmpty(SqStack*s)/判断栈是否为空 return(s-top=-1);int Push(SqStack *&s,ElemType e)/进栈 if(s-top=MaxSize-1)return 0;s-top+;s-datas-top=e;retu

5、rn 1;int StackLength(SqStack *s)/求栈的长度 return(s-top+1);int DispStack(SqStack *s)/显示栈中元素 int i;for(i=s-top;i=0;i-)printf(%c,s-datai);printf(n);int Pop (SqStack*&s,ElemType &e)/出栈 if(s-top=-1) return 0; e=s-datas-top; s-top-; return 1; int ClearStack(SqStack *&s)/释放栈 free(s); void main() SqStack *s; E

6、lemType e; InitStack(s); printf(1.初始化栈 s); printf(nn); printf(2.判断栈s是否为空:); printf(栈%sn,(StackEmpty(s)=1?空:非空); printf(n); printf(3.依次进栈); printf(n); printf(a进栈n);Push(s,a); printf(b进栈n);Push(s,b); printf(c进栈n);Push(s,c); printf(d进栈n);Push(s,d); printf(e进栈n);Push(s,e); printf(n); printf(4.判断栈s是否为空:)

7、; printf(栈%sn,(StackEmpty(s)=1?空:非空); printf(n); printf(5.输出栈长度:%d,StackLength(s); printf(nn); printf(6.输出从栈顶到栈底元素); DispStack(s); printf(n); printf(7.输出出栈序列:); while(!StackEmpty(s) Pop(s,e); printf(%c,e); printf(nn); printf(8.判断栈s是否为空:); printf(栈%sn,(StackEmpty(s)=1?空:非空); printf(n); printf(9.释放栈);

8、 ClearStack(s); printf(nn); 实验2 #include#include#define MaxSize 1024 typedef char ElemType;typedef struct ElemType data MaxSize; int front,rear; SqQueue; /初始化队列 void InitQueue(SqQueue *&q) q=(SqQueue *)malloc(sizeof(SqQueue); q-front=q-rear=0; /判断队列q是否为空int QueueEmpty (SqQueue *q)return(q-front=q-re

9、ar);/求队列的长度int QueueLength(SqQueue *q) return(q-rear-q-front);/入队列int enQueue(SqQueue *&q,ElemType e) if(q-rear+1)%MaxSize=q-front) return 0; q-rear=(q-rear+1)%MaxSize; q-dataq-rear=e; return 1; /出队列int deQueue(SqQueue *&q,ElemType &e) if(q-front=q-rear) return 0; q-front=(q-front+1)%MaxSize; e=q-da

10、taq-front; return 1;/销毁队列 int ClearQueue(SqQueue *&q) free(q); /主函数void main()SqQueue *q;ElemType e;InitQueue(q);printf(1.初始化队列 q); printf(nn); printf(2.判断队列q是否为空:); printf(队列%sn,(QueueEmpty(q)=1?空:非空); printf(n); printf(3.依次进队); printf(n); printf(a进队n);enQueue(q,a); printf(b进队n);enQueue(q,b); print

11、f(c进队n);enQueue(q,c); printf(n); deQueue(q,e);printf(4.出队一个元素，输出该元素为：%cn,e); printf(nn); printf(5.输出栈长度:%d,QueueLength(q); printf(nn); printf(6.依次进队); printf(n); printf(d进队n);enQueue(q,d); printf(e进队n);enQueue(q,e); printf(f进队n);enQueue(q,f); printf(n); printf(7.队列中的元素个数：%dn,QueueLength(q); printf(n); printf(8.出队序列：); while(deQueue(q,e) printf(%c,e); printf(nn); printf(9.释放队列); ClearQueue(q); printf(nn); 注：空间不够，可以增加页码。