栈和队列实验报告

（规格为A4纸或A3纸折叠）佛山科学技术学院（用四号宋体）实验报告（用小二号黑体）课程名称数据结构实验实验项目实现队列和栈的各种算法及操作专业班级10网络工程（2）班姓名___蒲永毅学号23指导教师成绩日期2011/11/7（用小四号宋体）一、目的和要求1.理解队列和栈的顺序存储结构和链式存储结构。通过本实验，熟悉队列、栈的结构特点；2.熟悉队列、栈结构上的操作与算法的实现。

二、实验内容1.队列的基本操作和应用。2.栈的基本操作和应用。

三、仪器、设备和材料1.适合实验要求的计算机系统2.Ｃ语言编程平台。四、实验原理队列与栈是一种操作受限制的线性表，在了解线性表的基本原理的基础上，理解与完成此项实验。

五、实验步骤1.采用队列的顺序存储结构，2．用菜单的形式完成队列的建立，出队，入队等基本操作。3.采用栈的链式存储结构4.用菜单的形式完成栈的出栈、入栈等基本操作。六、程序算法源代码：#include<stdio.h>#include<stdlib.h>#defineOVERFLOW-2#defineERROR0#defineOK1#defineMAX100 //栈的最大值typedefintSElemType;typedefintQElemType;typedefstruct{SElemType*base; SElemType*top;}SqStack;SqStackInitStacka() //顺序存储实现栈的初始化{SqStackS;S.base=(SElemType*)malloc(MAX*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;return(S);}voidPusha(SqStack&S,intx) //顺序存储实现栈的入栈操作{if(S.top-S.base>=MAX)exit(OVERFLOW);*S.top++=x;}voidPopa(SqStack&S) //顺序存储实现栈的出栈操作{SElemType*p;intx;if(S.top==S.base)return;else{p=S.top;x=*--S.top;printf("\t删除的栈顶元素是%d\n\t出栈操作完成后的栈为:\n",x);}}voidprinta(SqStackS) //输出{SElemType*p;p=S.base;printf("\t");while(p!=S.top){printf("%d",*(p++));}printf("\n");}typedefstructSqNode{SElemTypedata;SqNode*Link;}*Sqptr,NODE;typedefstruct{Sqptrtop;}Stack;StackInitStackb() //链式存储实现栈的初始化{StackS;S.top=(Sqptr)malloc(sizeof(NODE));if(!S.top)exit(OVERFLOW);S.top->Link=NULL;return(S);}voidPushb(Stack&S,intx) //链式存储实现栈的入栈操作{Sqptrp;p=(Sqptr)malloc(sizeof(NODE));if(!p)return;p->data=x;p->Link=S.top->Link;S.top->Link=p;}voidPopb(Stack&S) //链式存储实现栈的出栈操作{intx;Sqptrp;if(S.top->Link==NULL)return;else{p=S.top->Link;x=p->data; S.top->Link=p->Link; printf("\t删除的栈顶元素是%d\n",x); free(p);}}typedefstructQNode{QElemTypedata;structQNode*next;}*QueuePtr,QNode;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;LinkQueueInitQueue() //链式存储实现队列的初始化{LinkQueueQ;Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->next=NULL; return(Q);}voidEnQueue(LinkQueue&Q,QElemTypex) //链式存储实现队列的入队{QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p->data=x;p->next=NULL;Q.rear->next=p;Q.rear=p;}voidDeQueue(LinkQueue&Q) //链式存储实现队列的出队{intx;if(Q.front==Q.rear)return;QueuePtrp;p=Q.front->next;x=p->data;printf("\t删除的队头元素是：%d\n",x);Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);return;}typedefstruct{SElemType*base;intfront,rear;}SqQueue;SqQueueInitQueueb() //顺序存储实现队列的初始化{SqQueueS;S.base=(SElemType*)malloc(MAX*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.front=S.rear=0;return(S);}voidEnQueueb(SqQueue&S,intx) //顺序存储实现队列的入队{if((S.rear+1)%MAX==S.front)return;S.base[S.rear]=x;S.rear=(S.rear+1)%MAX;}voidDeQueueb(SqQueue&S) //顺序存储实现队列的出队{intx;if(S.front==S.rear)return;x=S.base[S.front];S.front=(S.front+1)%MAX;printf("\t删除的队头元素是:%d\n",x);}voidmain(){intchoice;intn,x;printf("\n\n");printf("\t1.采用链式存储实现栈的初始化、入栈、出栈操作\n");printf("\t2.采用顺序存储实现栈的初始化、入栈、出栈操作\n");printf("\t3.采用链式存储实现队列的初始化、入队、出队操作\n");printf("\t4.采用顺序存储实现队列的初始化、入队、出队操作\n");printf("\t请选择:");scanf("%d",&choice);switch(choice){case1:StackSa; printf("\t1.链式存储实现栈的初始化\n"); printf("\t2.链式存储实现栈的入栈操作\n"); printf("\t3.链式存储实现栈的出栈操作\n");while(1){printf("\t请选择：");scanf("%d",&n);switch(n){case1:Sa=InitStackb();printf("\t链式存储栈的初始化完成!\n");break;case2:printf("\t以'0'结束\n");printf("\t"); scanf("%d",&x); while(x){ Pushb(Sa,x);scanf("%d",&x);} printf("\t链式存储栈的入栈操作完成!\n");break;case3:Popb(Sa);break;}}break;case2:SqStackS; printf("\t1.顺序存储实现栈的初始化\n"); printf("\t2.顺序存储实现栈的入栈操作\n"); printf("\t3.顺序存储实现栈的出栈操作\n"); while(1){ printf("\t请选择:"); scanf("%d",&n); switch(n) {case1:S=InitStacka(); printf("\t顺序存储栈的初始化完成!\n");break; case2:printf("\t以'0'结束\n"); printf("\t"); scanf("%d",&x); while(x){ Pusha(S,x); scanf("%d",&x);} printf("\t顺序存储栈的入栈操作完成!\n"); printa(S);break;case3:Popa(S); printa(S);break;}}break;case3:LinkQueueQ;printf("\t1.链式存储实现队的初始化\n");printf("\t2.链式存储实现队的入栈操作\n");printf("\t3.链式存储实现队的出栈操作\n");while(1){printf("\t请选择：");scanf("%d",&n);switch(n){case1:Q=InitQueue();printf("\t链式存储队的初始化完成!\n");break;case2:printf("\t以'0'结束\n");printf("\t");scanf("%d",&x); while(x){ EnQueue(Q,x);scanf("%d",&x);} printf("\t链式存储队的入栈操作完成!\n");break;case3:DeQueue(Q);break;}}break;case4:SqQueueSv; printf("\t1.顺序存储实现队的初始化\n");printf("\t2.顺序存储实现队的入栈操作\n");printf("\t3.顺序存储实现队的出栈操作\n");while(1){printf("\t请选择：");scanf("%d",&n);switch(n){case1:Sv=InitQueueb();printf("\t链式存储栈的初始化完成!\n");break;case2:printf("\t以'0'结束\n");printf("\t");scanf("%d",&x); while(x){ EnQueueb(Sv,x);scanf("%d",&x);} printf("\t链式存储栈的入栈操作完成!\n");break;case3:DeQueueb(Sv);break;}}break;}}程序调试截图：1.采用链式存储实现栈的初始化、入栈、出栈操作2.采用顺序存储实现栈的初始化、入栈、出栈操作3.采用链式存储实