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

数据结构实验报告班级：计学号：姓名：设计日期：西安计算机学院实验题目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）取栈顶元素函数Getstacktop（）3、队列的链式存储结构所包含的函数：1）主函数main（）2）入队函数EnQueue（）3）出队函数DeQueue（）4队列的循环所包含的函数：1）主函数main（）2）初始化循环函数CircSeqQueue（）3）入队函数EnQueue（）4）出队函数DeQueue（）5）取队首元素函数GetFront（）4.详细设计1）栈的顺序存储结构#includestdio.h#includestdlib.h#includeconio.h#defineMAXSIZE20typedefintdatatype;typedefstruct{datatypeelem[MAXSIZE];inttop;}SeqStack;intinit(SeqStack*s){s-top=-1;return1;}voidprint(SeqStack*s){charch;inti;if(s-top==-1)printf(\n栈已空.);else{i=s-top;while(i!=-1){printf(\ndata=%d,s-elem[i]);i--;}}printf(\n按回车继续);ch=getch();}voidpush(SeqStack*s,datatypex){if(s-top==MAXSIZE-1)printf(\n栈已满！);elses-elem[++s-top]=x;}datatypepop(SeqStack*s){datatypex;if(s-top==-1){printf(\n栈已空!);x=-1;}else{x=s-elem[s-top--];}return(x);}voidmain(){SeqStacks;intk;datatypex;if(init(&s)){do{printf(\n\n\n);printf(\n***************************************);printf(\n\n1.x进栈);printf(\n\n2.出栈返回其值);printf(\n\n3结束);printf(\n***************************************);printf(\n请选择(123));scanf(%d,&k);switch(k){case1:{printf(\n请输入进栈整数X=?);scanf(%d,&x);push(&s,x);print(&s);}break;case2:{x=pop(&s);printf(\n出栈元素:%d,x);print(&s);}break;case3:exit(0);}printf(n---------);}while(k=1&&k3);printf(\n按回车返回);getch();}elseprintf(\n初始化失败！\n);}2).栈的链式存储结构#includestdio.h#includestdlib.htypedefstructSNode{intdata;structSNode*next;}SNode,*LinkStack;LinkStacktop;LinkStackPushStack(LinkStacktop,intx)//入栈{LinkStacks;s=(LinkStack)malloc(sizeof(SNode));s-data=x;s-next=top;top=s;returntop;}LinkStackPopStack(LinkStacktop)//退栈{LinkStackp;if(top!=NULL){p=top;top=top-next;free(p);printf(退栈已完成\n);returntop;}elseprintf(栈是空的，无法退栈！\n);return0;}intGetStackTop(LinkStacktop)//取栈顶元素{returntop-data;}boolIsEmpty(){returntop==NULL?true:false;}voidPrint(){SNode*p;p=top;if(IsEmpty()){printf(Thestackisempty!\n);return;}while(p){printf(%d,p-data);p=p-next;}printf(\n);}voidmain(){intx,a,b;charm;do{printf(\n);printf(链栈的基本操作\n);printf(\n);printf(1.置空栈\n);printf(2.进栈\n);printf(3.退栈\n);printf(4.取栈顶元素\n);printf(5.退出程序\n);printf(\n请选择一个数字（12345）：);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栈顶元素是：%d\n,GetStackTop(top));elseprintf(\n栈是空的，没有元素！);}break;case'5':break;default:printf(\n输入的字符不对，请重新输入!);break;}getchar();}while(m!='5');}运算结果:3）队列的链式存储结构#includestdio.h#includestdlib.h#includeconio.h#includestdio.h#includestdlib.h#includemath.htypedefintdataType;typedefstructnode{dataTypedata;structnode*next;}QNode;typedefstruct{QNode*front,*rear;}LQueue;/*初始化*/intinit(LQueue*q){if((q-front=(QNode*)malloc(sizeof(QNode)))==NULL)return0;q-rear=q-front;q-front-next=NULL;return1;}/*出队*/voidprint(LQueueQ){QNode*p;charch;p=Q.front-next;while(p!=NULL){printf(\n%d,p-data);p=p-next;}printf(\n按回车键继续。);ch=getch();}/*入队*/intEnQueue(LQueue*q,dataTypex){QNode*p;if((p=(QNode*)malloc(sizeof(QNode)))==NULL)return0;p-data=x;p-next=NULL;q-rear-next=p;q-rear=p;return1;}/*出队*/dataTypeDeQueue(LQueue*q){QNode*p;dataTypex;if(q-front==q-rear){printf(\n队列空);x=-1;}else{p=q-front-next;q-front-next=p-next;x=p-data;free(p);if(q-front-next==NULL)q-rear=q-front;}return(x);}voidmain(){intk;dataTypee,x;charch;LQueueQ;init(&Q);do{printf(\n\n\n);printf(\n*******************************);printf(\n\n1.元素入队列);printf(\n\n2.出队列返回);printf(\n\n3.结束);printf(\n*******************************);printf(\n请选择(1,2,3));scanf(%d,&k);switch(k){case1:{printf(\n进队e=?);scanf(%d,&e);EnQueue(&Q,e);print(Q);}break;case2:{x=DeQueue(&Q);printf(\n出队元素:%d,x);print(Q);}break;case3:exit(0);}printf(\n--------------);}while(k=1&&k3);printf(\n按回车键，返回。);ch=getch();}4）队列的循环存储#includestdio.h#includeprocess.h#includeiostream.h#includestdlib.h#defineMaxSize100typedefintElemType;typedefstruct{ElemTypedata[MaxSize];intfront;intrear;}CircSeqQueue;//顺序循环队列的初始化voidQueueInitial(CircSeqQueue*pQ){//创建一个又指针pQ所指向的空顺序循环队列pQ-front=pQ-rear=0;}//顺序循环队列判空intIsEmpty(CircSeqQueue*pQ){//顺序循环队列为空时返回1，否则返回0returnpQ-front==pQ-rear;}//顺序循环队列判满intIsFull(CircSeqQueue*pQ){//循环队列为满时返回1，否则返回0return(pQ-rear+1)%MaxSize==pQ-front;}//元素进队voidEnQueue(CircSeqQueue*pQ,ElemTypee){//若队列不满，则元素e进队if(IsFull(pQ))//队列已满，退出{printf(队列溢出！\n);exit(1);}pQ-rear=(pQ-rear+1)%MaxSize;//队尾指针后移pQ-data[pQ-rear]=e;}//元素出队ElemTypeDeQueue(CircSeqQueue*pQ){//若循环队列不为空，则删除队头元素，并返回它的值if(IsEmpty(pQ))//队列为空，退出{printf(空队列!\n);exit(1);}pQ-front=(