栈-队列的顺序-链式储存结构(数据结构试验报告).doc

数据结构实验报告班 级： 计 学 号： 姓 名： 设计日期： 西安计算机学院实验题目 1)栈的顺序存储结构 2)栈的链式存储结构 3)队列的链式存储结构 4)队列的循环存储结构2. 需求分析 本演示程序用C语言编写，完成栈和列的初始化，入栈、出栈、输出操作。1） 对于顺序栈，入栈时要先判断栈是否满了，栈满不能入栈，否则出现空间溢出；在进栈出栈和读取栈顶时先判栈是否为空，为空时不能操作。2） 在一个链队表中需设定两个指针分别指向队列的头和尾。3） 队列的存储结构：注意要判断队满和队空。4） 程序所能达到的功能：完成栈的初始化，入栈，出栈和输出操作；完成队列的初始化，入队列，出队列和输出操作。3. 概要设计 本程序包含1、栈的顺序存储结构包含的函数：1） 主函数main（）2） 入栈函数Push（）3） 出栈函数Pop（）2、栈的链式存储结构包含的函数：1） 主函数main（）2） 入栈函数PushStack（）3） 退栈函数PopStack（）4） 取栈顶元素函数Getstack top（）3、队列的链式存储结构所包含的函数：1） 主函数main（）2） 入队函数EnQueue（）3） 出队函数DeQueue（）4 队列的循环所包含的函数：1） 主函数main（）2） 初始化循环函数CircSeqQueue（）3） 入队函数EnQueue（）4） 出队函数DeQueue（）5） 取队首元素函数GetFront（）4. 详细设计 1）栈的顺序存储结构#include#include#include#define MAXSIZE 20typedef int datatype;typedef struct datatype elemMAXSIZE; int top;SeqStack;int init(SeqStack *s) s-top=-1; return 1;void print(SeqStack *s)char ch; int i;if(s-top=-1)printf(n 栈已空.);elsei=s-top;while(i!=-1)printf(n data=%d,s-elemi); i-;printf(n 按回车继续);ch=getch();void push(SeqStack *s,datatype x)if(s-top=MAXSIZE-1) printf(n 栈已满！);else s-elem+s-top=x;datatype pop(SeqStack*s)datatype x;if(s-top=-1)printf(n 栈已空! ); x=-1;elsex=s-elems-top-;return(x);void main()SeqStack s; int k; datatype x;if(init(&s)do printf(nnn); printf(n*); printf(nn 1. x进栈); printf(nn 2.出栈返回其值); printf(nn 3 结束); printf(n*); printf(n 请选择(123); scanf(%d,&k); switch(k) case 1:printf(n 请输入进栈整数 X=?);scanf(%d,&x); push(&s,x);print(&s); break; case 2: x=pop(&s); printf(n 出栈元素:%d,x); print(&s); break; case 3:exit(0); printf(n-);while(k=1 &k3);printf(n 按回车返回);getch();else printf(n 初始化失败！n);2) .栈的链式存储结构#include#includetypedef struct SNodeint data;struct SNode*next;SNode,*LinkStack;LinkStack top;LinkStack PushStack(LinkStack top,int x)/入栈LinkStack s;s=(LinkStack)malloc(sizeof(SNode);s-data=x;s-next=top;top=s;return top;LinkStack PopStack(LinkStack top) /退栈LinkStack p;if(top!=NULL)p=top;top=top-next;free(p);printf(退栈已完成n);return top;elseprintf(栈是空的，无法退栈！n);return 0;int GetStackTop(LinkStack top) /取栈顶元素return top-data;bool IsEmpty()return top=NULL?true:false;void Print()SNode*p;p=top;if(IsEmpty()printf(The stack is empty!n);return;while(p)printf(%d ,p-data);p=p-next;printf(n);void main()int x,a,b;char m;do printf(n); printf( 链栈的基本操作 n); printf( n); printf( 1.置空栈 n); printf( 2.进栈 n); printf( 3.退栈 n); printf( 4.取栈顶元素 n); printf( 5.退出程序 n); printf(n 请选择一个数字（1 2 3 4 5）：); scanf(%c,&m);switch(m)case 1: top=NULL; printf(n栈已置空!); break;case 2: printf(请输入要进栈的元素个数是：); scanf(%d,&a); printf(n请输入要进栈的%d个元素:,a); for(b=0;ba;b+) scanf(%d,&x); top=PushStack(top,x); printf(进栈已完成！n); printf(n输出栈为:); Print(); break;case 3: printf(n操作之前的输出栈为:); Print(); top=PopStack(top); printf(n操作过后的输出栈为:); Print(); break;case 4: printf(n输出栈为:); Print(); if(top!=NULL) printf(n栈顶元素是：%dn,GetStackTop(top); else printf(n栈是空的，没有元素！); break;case 5:break;default:printf(n输入的字符不对，请重新输入!);break;getchar();while(m!=5);运算结果:3） 队列的链式存储结构#include#include#include#include#include#includetypedef int dataType;typedef struct node dataType data; struct node *next;QNode;typedef structQNode *front,*rear;LQueue;/*初始化*/int init(LQueue *q)if(q-front=(QNode *)malloc(sizeof(QNode)=NULL)return 0;q-rear=q-front;q-front-next=NULL;return 1;/*出队*/void print(LQueue Q) QNode *p; char ch; p=Q.front-next; while(p!=NULL)printf(n%d,p-data); p=p-next; printf(n 按回车键继续。); ch=getch();/*入队*/int EnQueue(LQueue *q,dataType x) QNode *p; if(p=(QNode*)malloc(sizeof(QNode)=NULL) return 0; p-data=x; p-next=NULL; q-rear-next=p; q-rear=p; return 1;/*出队*/dataType DeQueue(LQueue *q)QNode *p;dataType x;if(q-front=q-rear)printf(n 队列空); x=-1;elsep=q-front-next;q-front-next=p-next;x=p-data;free(p);if(q-front-next=NULL) q-rear=q-front;return(x);void main()int k;dataType e,x;char ch;LQueue Q;init(&Q);doprintf(nnn);printf(n*);printf(nn1.元素入队列);printf(nn2.出队列返回);printf(nn3.结束);printf(n*);printf(n请选择(1,2,3);scanf(%d,&k);switch(k)case 1:printf(n 进队 e=?);scanf(%d,&e);EnQueue(&Q,e);print(Q);break;case 2:x=DeQueue(&Q);printf(n 出队元素:%d,x);print(Q); break;case 3:exit(0);printf(n-);while(k=1&k3);printf(n按回车键，返回。);ch=getch(); 4） 队列的循环存储#include #include #include #include #define MaxSize 100 typedef int ElemType; typedef struct ElemType dataMaxSize; int front; int rear; CircSeqQueue; /顺序循环队列的初始化 void QueueInitial(CircSeqQueue *pQ) /创建一个又指针pQ所指向的空顺序循环队列 pQ-front=pQ-rear=0; /顺序循环队列判空 int IsEmpty(CircSeqQueue *pQ) /顺序循环队列为空时返回1，否则返回0 return pQ-front=pQ-rear; /顺序循环队列判满 int IsFull(CircSeqQueue *pQ) /循环队列为满时返回1，否则返回0 return (pQ-rear+1)%MaxSize=pQ-front; /元素进队 void EnQueue(CircSeqQueue *pQ, ElemType e) /若队列不满，则元素e进队 if(IsFull(pQ)/队列已满，退出 printf(队列溢出！n); exit(1); pQ-rear=(pQ-rear+1)%MaxSize;/队尾指针后移 pQ-datapQ-rear=e; /元素出队 ElemType DeQueue(CircSeqQueue *pQ) /若循环队列不为空，则删除队头元素，并返回它的值 if(IsEmpty(pQ)/队列为空，退出 printf(空队列!n); exit(1); pQ-front=(pQ-front+1)%MaxSize;/队头指针后移 return pQ-datapQ-front; /取队头元素 ElemType GetFront(CircSeqQueue *pQ) /若队列不为空，则返回队头元素的值 if(IsEmpty(pQ) printf(空队列!n); exit(1); return pQ-data(pQ-front+1)%MaxSize; /循环队列置空 void MakeEmpty(CircSeqQueue *pQ) /将由指针pQ所指向的队列变为孔队 pQ-front=pQ-rear=0; void main() int k,m=1,n,i; CircSeqQueue *pQ; ElemType e; pQ=new CircSeqQueue; QueueInitial(pQ); while(k) printf(n*n);printf( 1.元素进队 n);printf( 2.元素出队返回 n);printf( 3.取首元素 n);printf( 4.队列置空 );printf(n*n);printf(请选择:(1,2,3)n); scanf(%d,&m); switch(m) case 0:return; case 1: printf(请输入入队元素的个数：n); scanf(%d,&n); printf(输入元素，入队n); for(i=0;in;i+) scanf(%d,&e);EnQueue(pQ,e);break