数据结构栈及队列实验报告计划

数据结构栈及队列实验报告计划数据结构栈及队列实验报告计划14/14数据结构栈及队列实验报告计划一、实验目的和要求(1)理解栈和队列的特色以及它们之间的差异，知道在何时使用那种数据结构。(2)重点掌握在序次栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。(3)重点掌握在序次队上和链队上实现队列的基本运算算法，注意循环队队列满和队空的条件。(4)灵便运用栈和队列这两种数据结构解决一些综合应用问题。二、实验环境和方法实验方法：（一）综合运用课本所学的知识，用不同样的算法实现在不同样的程序功能。（二）结合指导老师的指导，解决程序中的问题，正确解决实质中存在的异常情况，逐步改进功能。（三）依照实验内容，编译程序。实验环境：Windowsxp三、实验内容及过程描述实验步骤：①进入集成环境。②输入自己编好的程序。③检查一遍已输入的程序可否有错（包括输入时输错的和编程中的错误），如发现有错，及时改正。④进行编译和连接。若是在编译和连接过程中发现错误，频幕上会出现“报错信息”，依照提示找到出错地址和原因，加以改正。再进行编译，这样屡次直到不出错为止。.专业word可编写⑤运行程序并解析运行结果可否合理。在运行是要注意当输入不同样的数据时所得结果可否正确，应运行多次，分别检查在不同样情况下结果可否正确。实验内容：编译以下题目的程序并调试运行。1）、编写一个程序algo3-1.cpp，实现序次栈的各种基本运算，并在此基础上设计一个主程序并完成以下功能：（1）初始化栈s；（2）判断栈s可否非空；（3）依次进栈元素a,b,c,d,e；（4）判断栈s可否非空；（5）输出出栈序列；（6）判断栈s可否非空；（7）释放栈。图Proj3_1工程组成本工程Proj3_1的组成结构如图3.1所示。本工程的模块结构如图3.2所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。mainInitStackDestroyStackStackEmptyPusPopGetTo图Proj3_1工程的程序结构图其中包括以下函数：InitStack(SqStack*&s)//初始化栈SDestroyStack(SqStack*&s)//销毁栈s.专业word可编写StackEmpty(SqStack*s)//判断栈空Push(SqStack*&s,ElemTypee)//进栈Pop(SqStack*&s,ElemType&e)//出栈GetTop(SqStack*s,ElemType&e)//取栈顶元素对应的程序以下：//文件名#include<stdio.h>#include<malloc.h>#defineMaxSize100typedefcharElemType;typedefstruct{.专业word可编写ElemTypedata[MaxSize];inttop;//栈顶指针}SqStack;voidInitStack(SqStack*&s)//初始化栈S{s=(SqStack*)malloc(sizeof(SqStack));s->top=-1;//栈顶指针置为-1}voidDestroyStack(SqStack*&s)//销毁栈s{free(s);}boolStackEmpty(SqStack*s)//判断栈空{return(s->top==-1);}boolPush(SqStack*&s,ElemTypee)//进栈{if(s->top==MaxSize-1)//栈满的情况，即栈上溢出returnfalse;s->top++;//栈顶指针增1s->data[s->top]=e;//元素e放在栈顶指针处returntrue;}boolPop(SqStack*&s,ElemType&e)//出栈{if(s->top==-1)//栈为空的情况，即栈下溢出returnfalse;e=s->data[s->top];//取栈顶指针元素的元素s->top--;//栈顶指针减1returntrue;}boolGetTop(SqStack*s,ElemType&e)//取栈顶元素{if(s->top==-1)//栈为空的情况，即栈下溢出returnfalse;e=s->data[s->top];//取栈顶指针元素的元素returntrue;}设计exp3-1.cpp程序以下.专业word可编写文件名:exp3-1.cpp#include<stdio.h>#include<malloc.h>#defineMaxSize100typedefcharElemType;typedefstruct{ElemTypedata[MaxSize];inttop;//栈顶指针}SqStack;externvoidInitStack(SqStack*&s);externvoidDestroyStack(SqStack*&s);externboolStackEmpty(SqStack*s);externboolPush(SqStack*&s,ElemTypee);externboolPop(SqStack*&s,ElemType&e);externboolGetTop(SqStack*s,ElemType&e);voidmain(){ElemTypee;SqStack*s;printf("栈s的基本运算以下:\n");printf("(1)初始化栈s\n");InitStack(s);printf("(2)栈为%s\n",(StackEmpty(s)?"空":"非空"));printf("(3)依次进栈元素a,b,c,d,e\n");Push(s,'a');Push(s,'b');Push(s,'c');Push(s,'d');Push(s,'e');printf("(4)栈为%s\n",(StackEmpty(s)?"空":"非空"));printf("(5)出栈序列:");while(!StackEmpty(s)){Pop(s,e);printf("%c",e);}printf("\n");printf("(6)栈为%s\n",(StackEmpty(s)?"空":"非空"));printf("(7)释放栈\n");DestroyStack(s);}运行结果以下：.专业word可编写2）、编写一个程序，实现链栈的各种基本运算，并在此基础上设计一个主程序并完成以下功能：1）初始化链栈s；2）判断链栈s可否非空；3）依次进栈a，b，c，d，e；4）判断链栈s可否非空；5）输出链栈长度；6）输出从栈底到栈顶元素；7）输出出队序列；（8）判断链栈s能否非空；

图Proj3_2工程组成（9）释放队列。本工程Proj3_2的组成结构如图3.3所示。本工程的模块结构如图3.4所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。mainInitStackDestroyStackStackEmptyPusPopGetTo图3.4Proj3_2工程的程序结构图.专业word可编写其中包括以下函数：InitStack(LiStack*&s)//初始化栈sDestroyStack(LiStack*&s)//销毁栈StackEmpty(LiStack*s)//判断栈可否为空Push(LiStack*&s,ElemTypee)//进栈Pop(LiStack*&s,ElemType&e)//出栈GetTop(LiStack*s,ElemType&e)//取栈顶元素对应的程序以下：//文件名#include<stdio.h>#include<malloc.h>typedefcharElemType;typedefstructlinknode{ElemTypedata;//数据域.专业word可编写ElemTypedata;//数据域structlinknode*next;//指针域}LiStack;voidInitStack(LiStack*&s)//初始化栈s{s=(LiStack*)malloc(sizeof(LiStack));s->next=NULL;}voidDestroyStack(LiStack*&s)//销毁栈{LiStack*p=s,*q=s->next;while(q!=NULL){free(p);p=q;q=p->next;}free(p);//此时p指向尾节点,释放其空间}boolStackEmpty(LiStack*s)//判断栈可否为空{return(s->next==NULL);}voidPush(LiStack*&s,ElemTypee)//进栈{LiStack*p;p=(LiStack*)malloc(sizeof(LiStack));p->data=e;//新建元素e对应的节点*pp->next=s->next;//插入*p节点作为开始节点s->next=p;}boolPop(LiStack*&s,ElemType&e)//出栈{LiStack*p;if(s->next==NULL)//栈空的情况returnfalse;p=s->next;//p指向开始节点e=p->data;s->next=p->next;//删除*p节点free(p);//释放*p节点returntrue;}boolGetTop(LiStack*s,ElemType&e)//取栈顶元素{if(s->next==NULL)//栈空的情况returnfalse;e=s->next->data;returntrue;}设计exp3-2.cpp主程序.专业word可编写//文件名#include<stdio.h>#include<malloc.h>typedefcharElemType;typedefstructlinknode{ElemTypedata;//数据域structlinknode*next;//指针域}LiStack;externvoidInitStack(LiStack*&s);externvoidDestroyStack(LiStack*&s);externboolStackEmpty(LiStack*s);externvoidPush(LiStack*&s,ElemTypee);externboolPop(LiStack*&s,ElemType&e);externboolGetTop(LiStack*s,ElemType&e);voidmain(){ElemTypee;LiStack*s;printf("栈s的基本运算以下:\n");printf("(1)初始化栈s\n");InitStack(s);printf("(2)栈为%s\n",(StackEmpty(s)?"空":"非空"));printf("(3)依次进栈元素a,b,c,d,e\n");Push(s,'a');Push(s,'b');Push(s,'c');Push(s,'d');Push(s,'e');printf("(4)栈为%s\n",(StackEmpty(s)?"空":"非空"));printf("(5)出栈序列:");while(!StackEmpty(s)){Pop(s,e);printf("%c",e);}printf("\n");printf("(6)栈为%s\n",(StackEmpty(s)?"空":"非空"));printf("(7)释放栈\n");DestroyStack(s);}程序运行结果以下：.专业word可编写3）、编写一个程序，实现序次环形队列的各种基本运算，并在此基础上设计一个主程序并完成以下功能：1）初始化队列q；2）判断队列q可否非空；3）依次进队列a,b,c；4）出队一个元素，输出该元素；5）输出队列q的元素个数；（6）依次进队列元素d,e,f；图3-5Proj3_3的工程组成7）输出队列q的元素个数；8）输出出队序列；9）释放队列。本工程Proj3_3的组成结构如图3.5所示。本工程的模块结构如图3.6所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。mainInitStackDestroyStackStackEmptyPusPopGetTo图3.6Proj3_3工程的程序结构图.专业word可编写其中包括以下函数：InitQueue(SqQueue*&q)//初始化队列DestroyQueue(SqQueue*&q)//销毁队列QueueEmpty(SqQueue*q)//判断队列空enQueue(SqQueue*&q,ElemTypee)//进队deQueue(SqQueue*&q,ElemType&e)//出队对应的程序以下：.专业word可编写文件名:algo3-3.cpp#include<stdio.h>#include<malloc.h>#defineMaxSize5typedefcharElemType;typedefstruct{ElemTypedata[MaxSize];intfront,rear;//队首和队尾指针}SqQueue;voidInitQueue(SqQueue*&q)//初始化队列{q=(SqQueue*)malloc(sizeof(SqQueue));q->front=q->rear=0;}voidDestroyQueue(SqQueue*&q)//销毁队列{free(q);}boolQueueEmpty(SqQueue*q)//判断队列空{return(q->front==q->rear);}boolenQueue(SqQueue*&q,ElemTypee)//进队{if((q->rear+1)%MaxSize==q->front)//队满上溢出returnfalse;q->rear=(q->rear+1)%MaxSize;q->data[q->rear]=e;returntrue;}booldeQueue(SqQueue*&q,ElemType&e)//出队{if(q->front==q->rear)//队空下溢出returnfalse;q->front=(q->front+1)%MaxSize;e=q->data[q->front];returntrue;}设计exp3-3.cpp主程序#include<stdio.h>#include<malloc.h>#defineMaxSize5.专业word可编写typedefcharElemType;typedefstruct{ElemTypeelem[MaxSize];intfront,rear;//队首和队尾指针}SqQueue;externvoidInitQueue(SqQueue*&q);externvoidDestroyQueue(SqQueue*&q);externboolQueueEmpty(SqQueue*q);externboolenQueue(SqQueue*&q,ElemTypee);externbooldeQueue(SqQueue*&q,ElemType&e);voidmain(){ElemTypee;SqQueue*q;printf("环形队列基本运算以下:\n");printf("(1)初始化队列q\n");InitQueue(q);printf("(2)依次进队列元