数据结构栈和队列实验报告.doc

。一、实验目的和要求(1)理解栈和队列的特征以及它们之间的差异，知道在何时使用那种数据结构。(2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。(3)重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队列满和队空的条件。(4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。二、实验环境和方法实验方法：（一）综合运用课本所学的知识，用不同的算法实现在不同的程序功能。（二）结合指导老师的指导，解决程序中的问题，正确解决实际中存在的异常情况，逐步改善功能。（三）根据实验内容，编译程序。实验环境：Windows xp Visual C+6.0三、实验内容及过程描述实验步骤： 进入Visual C+ 6.0集成环境。 输入自己编好的程序。 检查一遍已输入的程序是否有错（包括输入时输错的和编程中的错误），如发现有错，及时改正。 进行编译和连接。如果在编译和连接过程中发现错误，频幕上会出现“报错信息”，根据提示找到出错位置和原因，加以改正。再进行编译，如此反复直到不出错为止。 运行程序并分析运行结果是否合理。在运行是要注意当输入不同的数据时所得结果是否正确，应运行多次，分别检查在不同情况下结果是否正确。实验内容：编译以下题目的程序并调试运行。1）、编写一个程序algo3-1.cpp，实现顺序栈的各种基本运算，并在此基础上设计一个主程序并完成如下功能：（1）初始化栈s；（2）判断栈s是否非空；（3）依次进栈元素a,b,c,d,e；（4）判断栈s是否非空；（5）输出出栈序列；（6）判断栈s是否非空； （7）释放栈。 图3.1 Proj3_1 工程组成本工程Proj3_1的组成结构如图3.1所示。本工程的模块结构如图3.2所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。mainInitStackDestroyStackStackEmptyPushPopGetTop图3.2 Proj3_1工程的程序结构图其中包含如下函数：InitStack(SqStack *&s)/初始化栈SDestroyStack(SqStack *&s)/销毁栈sStackEmpty(SqStack *s)/判断栈空Push(SqStack *&s,ElemType e)/进栈Pop(SqStack *&s,ElemType &e)/出栈GetTop(SqStack *s,ElemType &e)/取栈顶元素 对应的程序如下： /文件名:algo3-1.cpp#include #include #define MaxSize 100typedef char ElemType;typedef struct ElemType dataMaxSize;int top;/栈顶指针 SqStack;void InitStack(SqStack *&s)/初始化栈Ss=(SqStack *)malloc(sizeof(SqStack);s-top=-1;/栈顶指针置为-1void DestroyStack(SqStack *&s)/销毁栈sfree(s);bool StackEmpty(SqStack *s)/判断栈空return(s-top=-1);bool Push(SqStack *&s,ElemType e)/进栈if (s-top=MaxSize-1)/栈满的情况，即栈上溢出return false;s-top+;/栈顶指针增1s-datas-top=e;/元素e放在栈顶指针处return true;bool Pop(SqStack *&s,ElemType &e)/出栈if (s-top=-1)/栈为空的情况，即栈下溢出return false;e=s-datas-top;/取栈顶指针元素的元素s-top-;/栈顶指针减1return true; bool GetTop(SqStack *s,ElemType &e)/取栈顶元素if (s-top=-1)/栈为空的情况，即栈下溢出return false;e=s-datas-top;/取栈顶指针元素的元素return true;设计exp3-1.cpp程序如下/文件名:exp3-1.cpp#include #include #define MaxSize 100typedef char ElemType;typedef struct ElemType dataMaxSize;int top;/栈顶指针 SqStack;extern void InitStack(SqStack *&s);extern void DestroyStack(SqStack *&s);extern bool StackEmpty(SqStack *s);extern bool Push(SqStack *&s,ElemType e);extern bool Pop(SqStack *&s,ElemType &e);extern bool GetTop(SqStack *s,ElemType &e);void main()ElemType e;SqStack *s;printf(栈s的基本运算如下:n);printf( (1)初始化栈sn);InitStack(s);printf( (2)栈为%sn,(StackEmpty(s)?空:非空);printf( (3)依次进栈元素a,b,c,d,en);Push(s,a);Push(s,b);Push(s,c);Push(s,d);Push(s,e);printf( (4)栈为%sn,(StackEmpty(s)?空:非空);printf( (5)出栈序列:);while (!StackEmpty(s)Pop(s,e);printf(%c ,e);printf(n);printf( (6)栈为%sn,(StackEmpty(s)?空:非空);printf( (7)释放栈n);DestroyStack(s);运行结果如下：2）、编写一个程序algo3-2.cpp，实现链栈的各种基本运算，并在此基础上设计一个主程序并完成如下功能：（1）初始化链栈s；（2）判断链栈s是否非空；（3）依次进栈a，b，c，d，e；（4）判断链栈s是否非空；（5）输出链栈长度；（6）输出从栈底到栈顶元素；（7）输出出队序列；（8）判断链栈s是否非空； 图3.3 Proj3_2工程组成（9）释放队列。本工程Proj3_2的组成结构如图3.3所示。本工程的模块结构如图3.4所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。mainInitStackDestroyStackStackEmptyPushPopGetTop 图3.4 Proj3_2工程的程序结构图其中包含如下函数：InitStack(LiStack *&s)/初始化栈s DestroyStack(LiStack *&s)/销毁栈StackEmpty(LiStack *s)/判断栈是否为空Push(LiStack *&s,ElemType e)/进栈Pop(LiStack *&s,ElemType &e)/出栈GetTop(LiStack *s,ElemType &e)/取栈顶元素对应的程序如下：/文件名:algo3-2.cpp#include #include typedef char ElemType;typedef struct linknodeElemType data;/数据域ElemType data;/数据域struct linknode *next;/指针域 LiStack;void InitStack(LiStack *&s)/初始化栈ss=(LiStack *)malloc(sizeof(LiStack);s-next=NULL;void DestroyStack(LiStack *&s)/销毁栈LiStack *p=s,*q=s-next;while (q!=NULL)free(p);p=q;q=p-next;free(p);/此时p指向尾节点,释放其空间bool StackEmpty(LiStack *s)/判断栈是否为空return(s-next=NULL);void Push(LiStack *&s,ElemType e)/进栈LiStack *p;p=(LiStack *)malloc(sizeof(LiStack);p-data=e;/新建元素e对应的节点*pp-next=s-next;/插入*p节点作为开始节点s-next=p;bool Pop(LiStack *&s,ElemType &e)/出栈LiStack *p;if (s-next=NULL)/栈空的情况return false;p=s-next;/p指向开始节点e=p-data;s-next=p-next;/删除*p节点free(p);/释放*p节点return true;bool GetTop(LiStack *s,ElemType &e)/取栈顶元素if (s-next=NULL)/栈空的情况return false;e=s-next-data;return true;设计 exp3-2.cpp 主程序/文件名:exp3-2.cpp#include #include typedef char ElemType;typedef struct linknodeElemType data;/数据域struct linknode *next;/指针域 LiStack;extern void InitStack(LiStack *&s);extern void DestroyStack(LiStack *&s);extern bool StackEmpty(LiStack *s);extern void Push(LiStack *&s,ElemType e);extern bool Pop(LiStack *&s,ElemType &e);extern bool GetTop(LiStack *s,ElemType &e);void main()ElemType e;LiStack *s;printf(栈s的基本运算如下:n);printf( (1)初始化栈sn);InitStack(s);printf( (2)栈为%sn,(StackEmpty(s)?空:非空);printf( (3)依次进栈元素a,b,c,d,en);Push(s,a);Push(s,b);Push(s,c);Push(s,d);Push(s,e);printf( (4)栈为%sn,(StackEmpty(s)?空:非空);printf( (5)出栈序列:);while (!StackEmpty(s)Pop(s,e);printf(%c ,e);printf(n);printf( (6)栈为%sn,(StackEmpty(s)?空:非空);printf( (7)释放栈n);DestroyStack(s);程序运行结果如下：3）、编写一个程序algo3-3.cpp，实现顺序环形队列的各种基本运算，并在此基础上设计一个主程序并完成如下功能：（1）初始化队列q；（2）判断队列q是否非空；（3）依次进队列a,b,c；（4）出队一个元素，输出该元素；（5）输出队列q的元素个数；（6）依次进队列元素d,e,f； 图3-5 Proj3_3的工程组成（7）输出队列q的元素个数；（8）输出出队序列；（9）释放队列。本工程Proj3_3的组成结构如图3.5所示。本工程的模块结构如图3.6所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。mainInitStackDestroyStackStackEmptyPushPopGetTop图3.6 Proj3_3工程的程序结构图其中包含如下函数：InitQueue(SqQueue *&q)/初始化队列DestroyQueue(SqQueue *&q)/销毁队列QueueEmpty(SqQueue *q)/判断队列空enQueue(SqQueue *&q,ElemType e)/进队deQueue(SqQueue *&q,ElemType &e)/出队对应的程序如下：/文件名:algo3-3.cpp#include #include #define MaxSize 5typedef char ElemType;typedef struct ElemType dataMaxSize;int front,rear;/队首和队尾指针 SqQueue;void InitQueue(SqQueue *&q)/初始化队列q=(SqQueue *)malloc (sizeof(SqQueue);q-front=q-rear=0;void DestroyQueue(SqQueue *&q)/销毁队列free(q);bool QueueEmpty(SqQueue *q)/判断队列空return(q-front=q-rear);bool enQueue(SqQueue *&q,ElemType e)/进队if (q-rear+1)%MaxSize=q-front)/队满上溢出return false;q-rear=(q-rear+1)%MaxSize;q-dataq-rear=e;return true;bool deQueue(SqQueue *&q,ElemType &e)/出队if (q-front=q-rear)/队空下溢出return false;q-front=(q-front+1)%MaxSize;e=q-dataq-front;return true;设计 exp3-3.cpp 主程序#include #include #define MaxSize 5 typedef char ElemType;typedef struct ElemType elemMaxSize;int front,rear;/队首和队尾指针 SqQueue;extern void InitQueue(SqQueue *&q);extern void DestroyQueue(SqQueue *&q);extern bool QueueEmpty(SqQueue *q);extern bool enQueue(SqQueue *&q,ElemType e);extern bool deQueue(SqQueue *&q,ElemType &e);void main()ElemType e;SqQueue *q;printf(环形队列基本运算如下:n);printf( (1)初始化队列qn);InitQueue(q);printf( (2)依次进队列元素a,b,