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

1、.数据结构实验报告班 级： 计 学 号：姓 名：设计日期： 西安计算机学院实验题目 1)栈的顺序存储结构 2)栈的链式存储结构 3)队列的链式存储结构 4)队列的循环存储结构2. 需求分析 本演示程序用C语言编写，完成栈和列的初始化，入栈、出栈、输出操作。1） 对于顺序栈，入栈时要先判断栈是否满了，栈满不能入栈，否则出现空间溢出；在进栈出栈和读取栈顶时先判栈是否为空，为空时不能操作。2） 在一个链队表中需设定两个指针分别指向队列的头和尾。3） 队列的存储结构：注意要判断队满和队空。4） 程序所能达到的功能：完成栈的初始化，入栈，出栈和输出操作；完成队列的初始化，入队列，出队列和输出操作。3.

2、概要设计 本程序包含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） 取队首

3、元素函数GetFront（）4. 详细设计 1）栈的顺序存储结构*include<stdio.h>*include<stdlib.h>*include<conio.h>*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

4、("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)pri

5、ntf("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(

6、"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>

7、=1 &&k<3);printf("n 按回车返回");getch();else printf("n 初始化失败！n");2) .栈的链式存储结构*include<stdio.h>*include<stdlib.h>typedef struct SNodeint data;struct SNode*next;SNode,*LinkStack;LinkStack top;LinkStack PushStack(LinkStack top,int x)/入栈LinkStack s;s=(LinkStack)mal

8、loc(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

9、 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(&q

10、uot; 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栈已置空!"

11、); break;case '2': printf("请输入要进栈的元素个数是："); scanf("%d",&a); printf("n请输入要进栈的%d个元素:",a); for(b=0;b<a;b+) scanf("%d",&x); top=PushStack(top,x); printf("进栈已完成！n"); printf("n输出栈为:"); Print(); break;case '3': printf(&q

12、uot;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(&

13、quot;n输入的字符不对，请重新输入!");break;getchar();while(m!='5');运算结果:3） 队列的链式存储结构*include<stdio.h>*include<stdlib.h>*include<conio.h>*include<stdio.h>*include<stdlib.h>*include<math.h>typedef int dataType;typedef struct node dataType data; struct node *next;QNod

14、e;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);

15、 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->fron

16、t=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*");pri

17、ntf("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);p

18、rintf("n 出队元素:%d",x);print(Q); break;case 3:exit(0);printf("n-");while(k>=1&&k<3);printf("n按回车键，返回。");ch=getch();4） 队列的循环存储*include<stdio.h> *include<process.h> *include<iostream.h> *include<stdlib.h> *define MaxSize 100 typedef int

19、 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(CircS

20、eqQueue *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(CircSeqQu

21、eue *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->dat

22、a(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(&quo