栈和队列的基本操作的实现

封面：安徽大学网络工程栈和队列的根本操作的实现______2010\4\12【实验目的】理解并掌握栈和队列的逻辑结构和存储结构；理解栈和队列的相关根本运算；编程对相关算法进行验证。【实验内容】〔一〕分别在顺序和链式存储结构上实现栈的以下操作〔含初始化，入栈，出栈，取栈顶元素等〕：构造一个栈S，将构造好的栈输出；在第1步所构造的栈S中将元素e入栈，并将更新后的栈S输出；在第2步更新后所得到的栈S中将栈顶元素出栈，用变量e返回该元素，并将更新后的栈S输出。〔二〕分别在链队列和循环队列上实现以下操作〔初始化，入队，出队，取队头元素等〕：1.构造一个队列Q，将构造好的队列输出；2.在第1步所构造的队列Q中将元素e入队，并将更新后的队列Q输出；3.在第2步更新后所得到的队列Q中将队头元素出队，用变量e返回该元素，并将更新后的队列Q输出。【要求】栈和队列中的元素要从终端输入；具体的输入和输出格式不限；算法要具有较好的健壮性，对运行过程中的错误操作要做适当处理。三、实验步骤1．本实验用到的数据结构(1)逻辑结构：线性结构(2)存储结构：程序一、四〔顺序存储结构〕；程序二、三〔链式存储结构〕；2．各程序的功能和算法设计思想程序一：顺序栈#include<stdio.h>#include<malloc.h>#include<process.h>#defineSTACKINITISIZE100#defineSTACKINCREMENT10#defineOK1#defineERROR0#defineOVERFLOW-2typedefintSElemtype;typedefintstatus;typedefstruct{SElemtype*base;SElemtype*top;intstacksize;}sqstack;voidInitstack(sqstack*s){(*s).base=(SElemtype*)malloc(STACKINITISIZE*sizeof(SElemtype));if(!(*s).base)exit(OVERFLOW);(*s).top=(*s).base;(*s).stacksize=STACKINITISIZE;}voidpush(sqstack*s,SElemtypee){if((*s).top-(*s).base>=(*s).stacksize){(*s).base=(SElemtype*)realloc((*s).base,((*s).stacksize+STACKINCREMENT)*sizeof(SElemtype));if(!(*s).base)exit(OVERFLOW);(*s).top=(*s).base+(*s).stacksize;(*s).stacksize+=STACKINCREMENT;}*(*s).top++=e;}statusGettop(sqstacks){inte;if(s.top==s.base)returnERROR;e=*(s.top-1);printf("栈顶元素是%d\n",e);returnOK;}statuspop(sqstack*s){intf;if((*s).top==(*s).base)returnERROR;f=*(--(*s).top);printf("出栈元素是%d\n",f);returnOK;}voidstackTraverse(sqstacks){ SElemtype*p=s.base;while(s.top>p) printf("%d",*p++);printf("\n");}voidmain(){ inth,k,e,i; sqstackla; printf("构建一个空栈\n");Initstack(&la); printf("请输入栈内元素的个数\n"); scanf("%d",&k);printf("请输入%d个元素\n",k); for(i=0;i<k;i++){ scanf("%d",&e); push(&la,e); } printf("\n"); printf("输出栈内所有元素\n");stackTraverse(la); fflush(stdin);printf("查找栈顶元素\n");Gettop(la); printf("删除栈顶元素\n"); pop(&la); printf("输出栈内所有元素\n");stackTraverse(la); fflush(stdin); printf("\n"); printf("插入一个元素\n"); printf("请输入插入的元素值\n"); scanf("%d",&h); push(&la,h); printf("输出栈内所有元素\n");stackTraverse(la); printf("\n");}功能：实现顺序栈的各种功能，如能建立空栈，实现栈的初始化，插入，删除栈顶元素等操作。算法设计思想：首先建立一个空栈，再实现栈的初始化，用一个主函数包涵栈的各种操作。程序调式如下：程序二：链栈//shuju3.cpp:定义控制台应用程序的入口点。#include"stdafx.h"#include<malloc.h>#include<stdio.h>#include<process.h>#defineOK1#defineERROR0typedefintstatus;typedefstructSNode{intdata;structSNode*next;}SNode,*Sqstack;voidCreatesqstack(Sqstack*l,intn){inti; Sqstacks; *l=(Sqstack)malloc(sizeof(SNode)); (*l)->next=NULL; printf("请输入%d个元素\n",n);for(i=n;i>0;--i){ s=(Sqstack)malloc(sizeof(SNode)); scanf("%d",&(s->data));s->next=(*l)->next; (*l)->next=s; }}statusGetelem(Sqstack*l,int*e){ Sqstacks; s=(*l)->next; *e=s->data; printf("头元素是%d\n",*e);returnOK;}statusinsertsqtack(Sqstackl,inte,intn){ Sqstackp,s;inti; p=l;for(i=0;i<n;i++){ p=p->next; }s=(Sqstack)malloc(sizeof(SNode)); s->data=e; p->next=s; s->next=NULL;returnOK;}statusDeletesqstack(Sqstackl){inth; Sqstackp,q; p=l;q=p->next;p->next=q->next;h=q->data;printf("删除的元素是%d",h);free(q);returnOK;}voidsqstackTraverse(Sqstackl){Sqstackp; p=l->next;while(p){ printf("%d",p->data); p=p->next; }}voidmain(){inti,j,n,k,e;Sqstackla; printf("请输入链栈的长度\n"); scanf("%d",&n);printf("建立一个链栈\n"); Createsqstack(&la,n); printf("输出各元素\n"); printf("la=");sqstackTraverse(la); fflush(stdin); printf("\n"); printf("查找栈顶元素\n"); Getelem(&la,&e); fflush(stdin);printf("\n"); printf("插入新的栈顶元素\n"); scanf("%d",&e);insertsqtack(la,e,n); printf("输出各元素\n"); printf("la=");sqstackTraverse(la); fflush(stdin);printf("\n"); printf("删除栈顶元素\n");Deletesqstack(la);printf("输出各元素\n"); printf("la=");sqstackTraverse(la); printf("\n");}功能：实现链栈的根本功能，如初始化，删除，插入，查找栈顶元素等。算法设计思想：利用单链表的形式建立一个链栈，定义一个结构体，利用指针指向，建立链栈的具有不同功能的函数〔删除、插入、查找等〕，利用主函数合理安排顺序实现链栈操作。调试情况如下：程序三:链队列//SHUJU.cpp:定义控制台应用程序的入口点。\\链队列的建立#include"stdafx.h"#include<stdio.h>#include<malloc.h>#include<process.h>#defineOK1#defineERROR0#defineOVERFLOW-2typedefintQElemtype;typedefintstatus;typedefstructQNode{ QElemtypedata;structQNode*next;}QNode,*Queueptr;typedefstruct{ Queueptrfront; Queueptrrear;}LinkQueue;statusInitQueue(LinkQueue&Q){ Q.front=(Queueptr)malloc(sizeof(QNode));Q.rear=Q.front;if(!Q.front) exit(OVERFLOW); Q.front->next=NULL;returnOK;}statusDestoryQueue(LinkQueue&Q){while(Q.front){ Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; }returnOK;}statusEnQueue(LinkQueue&Q,QElemtypee){ Queueptrp; p=(Queueptr)malloc(sizeof(QNode));if(!p) exit(OVERFLOW); p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p;returnOK;}statusDeQueue(LinkQueue&Q,QElemtype&e){ Queueptrp;if(Q.front==Q.rear)returnERROR; p=Q.front->next; e=p->data; Q.front->next=p->next;if(Q.rear==p) Q.rear=Q.front; free(p);returnOK;}statusGethead(LinkQueue&Q){ Queueptrp; QElemtypee;if(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data; printf("头元素是%d",e); printf("\n");returnOK;}statusQueueqTraverse(LinkQueueQ){Queueptrp; p=Q.front->next;while(p){ printf("%d",p->data); p=p->next; } printf("\n");returnOK;}voidmain(){ LinkQueuela; QElemtypee,k;inth,i; printf("构建一个空队列\n");InitQueue(la); printf("请输入元素个数\n");scanf("%d",&h); printf("请输入%d个元素\n",h);for(i=0;i<h;i++){ scanf("%d",&e);EnQueue(la,e); }printf("输出队列内的元素\n");QueueqTraverse(la);fflush(stdin); printf("\n"); printf("获得对列的头元素\n");Gethead(la);printf("输出队列内的元素\n");QueueqTraverse(la);fflush(stdin); printf("\n");printf("开始插入一元素\n"); printf("请输入插入元素\n"); scanf("%d",&k);EnQueue(la,k);printf("输出队列内的元素\n");QueueqTraverse(la);fflush(stdin); printf("\n"); printf("删除对头的元素\n");DeQueue(la,e); printf("删除的元素是%d\n",e);printf("输出队列内的元素\n");QueueqTraverse(la);fflush(stdin); printf("\n"); printf("摧毁队列\n");DestoryQueue(la);printf("输出队列内的元素\n");QueueqTraverse(la);}功能：实现链队列的各种不同的操作，如队列的初始化，队列的插入，删除，查询以及摧毁队列等。算法设计思想：构建两个不同的结构体，如下：typedefstructQNode{ QElemtypedata;structQNode*next;}QNode,*Queueptr;typedefstruct{ Queueptrfront; Queueptrrear;}LinkQueue;其中有指向头和尾的front和rear指针，利用它们构建链队列。调试情况如下：程序四：循环队列//shujiu4.cpp:定义控制台应用程序的入口点。#include"stdafx.h"#include<stdio.h>#include<malloc.h>#include<process.h>#defineMAXSIZE10#defineOK1#defineERROR0#defineOVERFLOW-2typedefintQElemtype;typedefintstatus;typedefstruct{ QElemtype*base;intfront;intrear;}sqQueue;statusInitQueue(sqQueue&Q){ Q.base=(QElemtype*)malloc(MAXSIZE*sizeof(QElemtype));if(!Q.base) exit(OVERFLOW); Q.front=Q.rear=0;returnOK;}statusQueueLength(sqQueueQ){QElemtypex; x=(Q.rear-Q.front+MAXSIZE)%MAXSIZE;printf("队列的元素个数是%d",x);returnOK;}statusEnQueue(sqQueue&Q,QElemtypee){if((Q.rear+1)%MAXSIZE==Q.front)returnERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXSIZE;returnOK;}statusDeQueue(sqQueue&Q){QElemtypee;if(Q.front==Q.rear)returnERROR; e=Q.base[Q.front]; printf("删除的元素是%d",e); Q.front=(Q.front+1)%MAXSIZE;returnOK;}statusGetQueue(sqQueue&Q){ QElemtypee; e=Q.base[Q.front]; printf("头元素是%d",e); printf("\n");returnOK;}statusQueueTraverse(sqQueue&Q,intk){ QElemtypeh,i; i=Q.front;for(;k>0;k--){ h=Q.base[Q.front]; printf("%d