《栈和队列的基本操作的实现》由会员分享，可在线阅读，更多相关《栈和队列的基本操作的实现（13页珍藏版）》请在金锄头文库上搜索。
1、封面：安徽大学网络工程栈和队列的基本操作的实现_2010412【实验目的】1.理解并掌握栈和队列的逻辑结构和存储结构；2.理解栈和队列的相关基本运算；3.编程对相关算法进行验证。【实验内容】（一）分别在顺序和链式存储结构上实现栈的以下操作（含初始化，入栈，出栈，取栈顶元素等）：1.构造一个栈S，将构造好的栈输出；2.在第1步所构造的栈S中将元素e 入栈，并将更新后的栈S输出；3.在第2步更新后所得到的栈S中将栈顶元素出栈，用变量e返回该元素，并将更新后的栈S输出。（二）分别在链队列和循环队列上实现以下操作（初始化，入队，出队，取队头元素等）：1.构造一个队列Q，将构造好的队列输出；2.在第1步
2、所构造的队列Q中将元素e入队，并将更新后的队列Q输出；3.在第2步更新后所得到的队列Q中将队头元素出队，用变量e返回该元素，并将更新后的队列Q输出。【要求】1.栈和队列中的元素要从终端输入；2.具体的输入和输出格式不限；3.算法要具有较好的健壮性，对运行过程中的错误操作要做适当处理。三、实验步骤1本实验用到的数据结构(1)逻辑结构：线性结构(2)存储结构：程序一、四（顺序存储结构）； 程序二、三（链式存储结构）；2各程序的功能和算法设计思想 程序一：顺序栈# include # include # include #define STACKINITISIZE 100# define STACK
3、INCREMENT 10# define OK 1# define ERROR 0# define OVERFLOW -2typedef int SElemtype;typedef int status;typedef struct SElemtype *base;SElemtype *top;int stacksize;sqstack;void Initstack (sqstack *s) (*s).base = (SElemtype *)malloc(STACKINITISIZE * sizeof (SElemtype); if(!(*s).base) exit(OVERFLOW);(*s
4、).top = (*s).base;(*s).stacksize = STACKINITISIZE;void push ( sqstack *s , SElemtype e )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 ;(
5、*s).stacksize += STACKINCREMENT;*(*s).top + = e;status Gettop (sqstack s ) int e;if (s.top =s.base )return ERROR;e=*(s.top-1);printf (栈顶元素是%dn,e);return OK;status pop ( sqstack *s ) int f;if ( (*s).top=(*s).base) return ERROR;f = *(-(*s).top);printf(出栈元素是%dn,f);return OK;void stackTraverse(sqstack s
6、 )SElemtype * p =s.base;while (s.topp)printf (%d ,*p+);printf(n);void main()int h,k,e,i;sqstack la;printf (构建一个空栈n);Initstack (&la);printf(请输入栈内元素的个数n);scanf (%d,&k);printf(请输入%d个元素n,k);for (i=0;ik;i+) scanf (%d,&e); printf (n); push (&la,e);printf(输出栈内所有元素n);stackTraverse (la);fflush (stdin);printf
7、(查找栈顶元素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);功能：实现顺序栈的各种功能，如能建立空栈，实现栈的初始化，插入，删除栈顶元素等操作。算法设计思想：首先建立一个空栈，再实现栈的初始化，用一个主函数包
8、涵栈的各种操作。程序调式如下：程序二：链栈/ shuju3.cpp : 定义控制台应用程序的入口点。 #include stdafx.h#include #include #include # define OK 1# define ERROR 0typedef int status;typedef struct SNodevoid Createsqstack(Sqstack *l,int n)int i; Sqstack s; *l=(Sqstack) malloc(sizeof(SNode); (*l)-next=NULL; printf(请输入%d个元素n,n); for(i=n;i0;
9、-i) s=(Sqstack) malloc(sizeof(SNode); scanf(%d,&(s-data); int data; struct SNode *next; SNode,*Sqstack;s-next=(*l)-next;status Getelem(Sqstack *l,int *e)status insertsqtack(Sqstack l,int e,int n) Sqstack p,s; Sqstack s; s=(*l)-next; *e=s-data; printf(头元素是%dn,*e); return OK; (*l)-next=s;int i; p=l; f
10、or(i=0;inext;s=(Sqstack) malloc (sizeof(SNode);status Deletesqstack(Sqstack l)int h; Sqstack p,q; p=l; s-data = e; p-next=s; s-next=NULL; return OK;q=p-next;p-next=q-next;h=q-data;printf(删除的元素是%d,h); free(q);return OK;void sqstackTraverse(Sqstack l)void main () int i,j,n,k,e; p=l-next; while(p) prin
11、tf(%d ,p-data); p=p-next; Sqstack p;Sqstack la;printf(请输入链栈的长度n); scanf(%d,&n); Createsqstack(&la,n); printf(建立一个链栈n);printf(输出各元素n); printf(la=); fflush(stdin); printf(n); printf(查找栈顶元素n); Getelem(&la,&e); fflush(stdin); printf(插入新的栈顶元素n); scanf(%d,&e); sqstackTraverse(la); printf(n);insertsqtack(l
12、a,e,n);printf(输出各元素n); printf(la=);sqstackTraverse(la);fflush(stdin);printf(n);printf(删除栈顶元素n);Deletesqstack(la);printf(输出各元素n);printf(la=);sqstackTraverse(la);printf(n);功能：实现链栈的基本功能，如初始化，删除，插入，查找栈顶元素等。算法设计思想：利用单链表的形式建立一个链栈，定义一个结构体，利用指针指向，建立链栈的具有不同功能的函数（删除、插入、查找等），利用主函数合理安排顺序实现链栈操作。调试情况如下：程序三:链队列/ S
13、HUJU.cpp : 定义控制台应用程序的入口点。 链队列的建立#include stdafx.h# include # include # include # define OK 1# define ERROR 0# define OVERFLOW -2typedef int QElemtype;typedef int status;typedef struct QNode QElemtype data; struct QNode *next;QNode,*Queueptr;typedef struct Queueptr front; Queueptr rear;LinkQueue;stat
14、us InitQueue (LinkQueue &Q)status DestoryQueue (LinkQueue &Q)status EnQueue (LinkQueue &Q,QElemtype e)status DeQueue (LinkQueue &Q,QElemtype &e) Queueptr p; Queueptr p; while (Q.front) Q.rear = Q.front-next; free(Q.front); Q.front = Q.rear; return OK; Q.front = (Queueptr)malloc(sizeof (QNode); if (!Q.front ) exit (OVERFLOW); Q.rear= Q.front; Q.front -next=NULL; return OK; p=(Queueptr)malloc(sizeof (QNode); i
