软件技术基础栈队列二叉树的应用.docx
《软件技术基础栈队列二叉树的应用.docx》由会员分享，可在线阅读，更多相关《软件技术基础栈队列二叉树的应用.docx（12页珍藏版）》请在冰点文库上搜索。
软件技术基础栈队列二叉树的应用
软件技术基础相关实验
实验名称：
栈的应用
一、实验目的：
掌握顺序栈和链式栈的定义和运算，了解它们的应用。
二、实验要求：
1、掌握顺序栈的定义、特点及常见算法。
2、掌握链式栈的定义、特点及常见算法。
3、参照给定的栈的程序样例，验证给出的栈的常见算法。
4、提交实验报告，报告内容包括：
目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容：
1、顺序栈的操作和测试。
要求：
设计一个主函数实现对顺序栈进行操作测试。
测试方法为：
依次把数据元素1,3,5，7,9入栈，并显示入栈结果；接着依次出栈其中的数据元素并在屏幕上显示。
2、链式栈的操作。
设计一个主函数实现对链式栈进行操作测试。
测试方法为：
依次把数据元素3,6,9，12,15入栈，并显示入栈结果；接着依次出栈其中的数据元素并在屏幕上显示。
3、栈的应用。
利用顺序栈求解表达式（a+b）*（c-d）的值。
四、程序要求：
1、顺序栈的长度自行确定。
2、重点理解栈的算法思想，能够根据实际情况选择合适的存储结构。
3、写出完整的程序并能调试通过。
五、实验结果：
入栈一个元素：
删除一个元素：
取栈顶元素：
退出
六、实验中遇到的问题及解决方法：
栈的操作有了前面的基础，相对而言能够编写出来，遇到的问题还是地址操作相关的，通过不断的练习对于指针对于地址传递应该说有了比较好的理解。
附：
源程序（自行编写或修改的程序。
若为修改程序请注明修改部分的功能，若为书上实例则可不附。
）
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#defineMAXNUM20
#defineElemTypeint
/*定义顺序栈的存储结构*/
typedefstruct
{ ElemTypestack[MAXNUM];
inttop;
}SqStack;
/*初始化顺序栈*/
voidInitStack（SqStack*p）
{
if（!
p）
printf（"内存分配失败!
"）;
p->top=-1;
}
/*入栈*/
voidPush（SqStack*p,ElemTypex）
{
if（p->top{
p->top=p->top+1;
p->stack[p->top]=x;
}
else
printf（"Overflow!
\n"）;
}
/*出栈*/
ElemTypePop（SqStack*p）
{
ElemTypex;
if（p->top>=0）
{
x=p->stack[p->top];
printf（"以前的栈顶数据元素%d已经被删除!
\n",p->stack[p->top]）;
p->top=p->top-1;
returnx;
}
else
{
printf（"Underflow!
\n"）;
return（0）;
}
}
/*获取栈顶元素*/
ElemTypeGetTop（SqStack*p）
{
ElemTypex;
if（p->top>=0）
{
x=p->stack[p->top];printf（"\n栈顶元素为：
%d\n",x）;
returnx;
}
else
{
printf（"Underflow!
\n"）;
return0;
}
}
/*遍历顺序栈*/
voidOutStack（SqStack*p）
{
inti;
printf（"\n"）;
if（p->top<0）
printf（"这是一个空栈!
"）;
printf（"\n"）;
for（i=p->top;i>=0;i--）
printf（"第%d个数据元素是：
%6d\n",i,p->stack[i]）;
}
/*主函数*/
voidmain（）
{
SqStack*q;
intcord;ElemTypea;
printf（"第一次使用必须初始化!
\n"）;
do{
printf（"\n-----------主菜单-----------"）;
printf（"\n 1 初始化顺序栈 "）;
printf（"\n 2 插入一个元素 "）;
printf（"\n 3 删除栈顶元素 "）;
printf（"\n 4 取栈顶元素 "）;
printf（"\n 5 置空顺序栈 "）;
printf（"\n 6 结束程序运行 "）;
printf（"\n----------------------------"）;
printf（"\n请输入指令"）;
scanf（"%d",&cord）;
printf（"\n"）;
switch（cord）
{
case1:
{
q=（SqStack*）malloc（sizeof（SqStack））;
InitStack（q）;
OutStack（q）;
}break;
case2:
{
printf（"请输入要插入的数据元素：
a="）;
scanf（"%d",&a）;
Push（q,a）;
OutStack（q）;
}break;
case3:
{
Pop（q）;
OutStack（q）;
}break;
case4:
{
GetTop（q）;
OutStack（q）;
}break;
case5:
{
printf（"\n顺序栈被置空!
\n"）;
OutStack（q）;
}break;
case6:
exit（0）;
}
}while（cord<=6）;
}
实验名称：
队列的应用
一、实验目的：
掌握循环队列和链队列的定义及其基本运算，了解并熟悉队列的应用。
二、实验要求：
1、掌握循环队列和链队列的特点及常见算法。
2、参照给定的循环队列和链队列的程序样例，验证给出的队列的常见算法。
3、能对队列进行简单的应用。
4、提交实验报告，报告内容包括：
目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容：
1、循环队列的基本操作。
要求：
设计一个主函数对循环队列进行测试。
主要功能有：
入队操作、出队操作、取对头元素。
2、链队列的基本操作。
要求：
设计一个主函数对链队列进行测试。
主要功能有：
链队列的初始化、求队列的长度、入队列操作、出队列操作、取对头元素。
3、对队列进行简单的应用。
四、程序要求：
1、能用数字化菜单的方式选择队列的各项操作。
2、循环队列中选择入队或出队时能一次入队或出队多个数据。
3、程序具有一定的防误操作性，能处理常见的突发事件。
4、写出完整的程序并能调试通过。
五、实验结果：
1、创建队列进行入队操作
2、出对操作，根据先进先出原理，一次出队
3、取出队头元素
4、判断队列是不是空队列
5将队列置空
六、实验心得体会：
通过本次实验，让我了解了队列的一些操作，掌握了队列编程的技巧。
学会了循环队列的算法。
队列的操作在计算机领域应用较为广泛，通过队列的学习也让我了解到了一些队列相关的应用，让我对于计算机操作系统的任务控制也有了一定的了解。
先进先出的模式在生活中也十分常见，有了队列可以解决很多的实际难题，队列的知识需要我们掌握。
附：
源程序（自行编写或修改的程序。
若为修改程序请注明修改部分的功能，若为书上实例则可不附。
）
#include
#include
typedefintboolean;
#definetrue1
#definefalse0
typedefstructqueue{
intelement[10];
intrear;
intfront;
}*Squeue,Queue;
voidEnqueue（Squeueq）;//入队操作
voidDequeue（Squeueq）;//出队操作
voidGetfront（Squeueq）;//取对头元素
booleanIsEmpty（Squeueq）;//判断是否为空
voidEnEmpty（Squeueq）;//使队列置空
voidmain（）
{
intinput;
Squeueq;
q=（Squeue）malloc（sizeof（Queue））;
q->front=0;
q->rear=-1;
printf（"================循环队列================\n"）;
printf（" 1. 入队操作\n"）;
printf（" 2. 出队操作\n"）;
printf（" 3. 取对头元素\n"）;
printf（" 4. 判断队列是否为空\n"）;
printf（" 5. 置空队列\n"）;
printf（"========================================\n"）;
do
{
printf（"请输入您的操作：
"）;
scanf（"%d",&input）;
switch（input）
{
case1:
{
Enqueue（q）;
}break;
case2:
{
Dequeue（q）;
}break;
case3:
{
Getfront（q）;
}break;
case4:
{
if（IsEmpty（q））
printf（"不存在该队列\n"）;
else
printf（"存在该队列\n"）;
}break;
case5:
{
EnEmpty（q）;
}break;
}
}while（input<=5）;
}
voidEnqueue（Squeueq）
{
intnum,i=0,record=0;
printf（"请输入您想入队的元素个数（一次队列存在不超过10个数据）：
"）;
scanf（"%d",&num）;
for（i;i{
printf（"请输入第%d个元素：
",i+1）;
if（++q->rear<=9）
{
if（q->rear==q->front&&record==1）
升级会员 