数据结构-实验3-程序栈和队列的实现.doc
数据结构课程实验报告实验名称程序栈和队列的实现实验序号3实验日期2012-4-18姓 名曹志华院系计算机科学与信息工程学院班 级C1学 号专 业计算机科学与技术指导教师武伟成 绩教师评语一、实验目的和要求1. 理解栈和队列的特性以及它们之间的差异，知道在何时使用哪种数据结构；2. 掌握栈和队列的顺序存储结构及其基本运算实现；3. 注意栈满和栈空的条件；4. 重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队满和队空的条件；5. 灵活运用栈和队列这两种数据结构解决一些综合应用问题。二、实验项目摘要实验1：编写一个程序，实现顺序栈的各类基本运算，并在此基础上设计一个主程序完成如下功能：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，栈和环形队列的顺序存储结构及其基本运算实现栈的顺序存储结构以及基本运算实现：l 初始化栈l 销毁栈l 求栈的长度l 判断栈是否为空l 进栈（Push）l 出栈（Pop）l 显示栈中元素 2. 环形队列的性质：环形队列的队头指针和队尾指针初始化时都置为0；三、实验结果与分析 1. 实验结果： 实验1：实验2：2.实验分析： 本次实验需要对栈和队列进行充分的了解，虽然栈和队列实质上是不同的，但在编写程序时大致相似。通常栈可以用顺序的方式存储，分配一块连续的存储区域存放栈中元素，并用一个变量指向当前的栈顶。而队列的顺序存储结构需要使用一个数组和两个整数型变量来实现。3.源代码 实验1：#include<stdio.h>#include<malloc.h>#define MaxSize 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;return 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; ElemType 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是否为空:"); 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.释放栈"); ClearStack(s); printf("nn"); 实验2 #include<stdio.h>#include<malloc.h>#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->rear);/求队列的长度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->dataq->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'); printf("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"); 注：空间不够，可以增加页码。
