陈正宁123349数据结构第2次实验报告.docx
《陈正宁123349数据结构第2次实验报告.docx》由会员分享，可在线阅读，更多相关《陈正宁123349数据结构第2次实验报告.docx（20页珍藏版）》请在冰点文库上搜索。
陈正宁123349数据结构第2次实验报告
淮海工学院计算机科学系
实验报告书
课程名：
《数据结构》
题目：
线性数据结构实验
（栈与队列及其应用）
班级：
软嵌151
学号：
2015123349
姓名：
陈正宁
线性表算法实现与应用报告要求
1目的与要求:
1）掌握栈与队列的数据类型描述及特点；
2）掌握栈的顺序和链式存储存表示与基本算法的实现；
3）掌握队列的链式和循环存储表示与基本操作算法实现;
4）掌握栈与队列在实际问题中的应用和基本编程技巧;
5）按照实验题目要求，独立完成实际程序的编写编写、调试和运行，并通过用例的运行过程抓获相关屏面验证程序设计的正确性；
7）希望大家过一个丰富多彩的国庆节，抽出一定时间圆满完成实验，并于第6周周5以前按时提交实验报告，逾期按照旷交处理。
2实验内容或题目
（一）必做题：
1、实现顺序栈的创建（初始化）、压入（插入）、弹出（删除）操作（数据元素类型自己选取，如整型、字符型等），并给出栈的每次操作变化状态；
2、实现链栈的创建（初始化）、压入（插入）、弹出（删除）操作（数据元素类型自己选取，如整型、字符型等），要求给出栈的操作变化过程；
3、实现循环队列的创建、进队、出队等基本操作（数据元素类型自己选取，如整型、字符型等），并实时给出队列的操作变化状态；
4、实现链式队列的创建、进队、出队等基本操作（数据元素类型自己选取，如整型、字符型等），并实时给出队列的操作变化状态；
（注意：
必做题需用一个主程序实现所有功能）
（二）选做题（视自己能力而定，数量不限）：
任选下列一个或多个栈或队列应用源程序（已经发给学委），并阅读、调试和运行程序，而后给出程序功能分析和实例运行演示；
1、实现表达式求值算法程序；
2、用递归算法实现汉诺塔问题算法程序；
3、使用循环队列实现打印杨辉三角形算法程序。
3实验步骤与源程序
必做题源程序
#include
#include
#include
#defineMAXSIZE50
#defineTRUE1
#defineFALSE0
#defineStack_Size50
typedefstructNode
{
chardata;
structNode*next;
}LinkQueueNode;
typedefstruct
{
LinkQueueNode*front;
LinkQueueNode*rear;//相当于创建一个头结点，一个尾结点，用头指针和尾指针指向他们，结点包括数据域和指针域
}LinkQueue;//链式队列定义
typedefstruct
{
charelement[MAXSIZE];
intfront;
intrear;
}SeqQueue;
typedefstruct//顺序栈定义。
{
charelem[Stack_Size];
inttop;
}SeqStack;
typedefstructnode//链栈定义。
{
chardata;
structnode*next;
}LinkStackNode;
intDeleteQueue1（LinkQueue*Q,char*x）
{
LinkQueueNode*p;//创建新结点
if（Q->front==Q->rear）//判断是否为空队列，即头尾指针重合
return（FALSE）;
p=Q->front->next;//新结点等于头指针的下一位，即要出队的结点赋给P
Q->front->next=p->next;//头指针指向的指针域指向头指针的下一个结点的下一个，即跳过头指针的下个结点P
if（Q->rear==p）//如果队中只有一个元素p，则p出队后成为空队
Q->rear=Q->front;
*x=p->data;//用指针把出队结点的数据读出来
free（p）;//释放P结点
return（TRUE）;
}
intEnterQueue1（LinkQueue*Q,charx）
{
LinkQueueNode*NewNode;//创建一个新结点
NewNode=（LinkQueueNode*）malloc（sizeof（LinkQueueNode））;
if（NewNode!
=NULL）
{
NewNode->data=x;//结点数据域为所给数据
NewNode->next=NULL;//指针域为空
Q->rear->next=NewNode;//尾结构指针所指向的指针域指向新建结点
Q->rear=NewNode;//尾结构指针后移一位，指向新插入的结点，该方法相当于尾插法
return（TRUE）;
}
elsereturn（FALSE）;//溢出
}
intInitQueue1（LinkQueue*Q）
{
Q->front=（LinkQueueNode*）malloc（sizeof（LinkQueueNode））;//Q->front同样为结构体指针，使用前要创建空间。
if（Q->front!
=NULL）
{
Q->rear=Q->front;//Q->front创建了空间，所以把Q->front赋给Q->rear，即头尾指针重合
Q->front->next=NULL;//头指针指向空间为空
return（TRUE）;
}
elsereturn（FALSE）;/*溢出！
*/
}
intDeleteQueue（SeqQueue*Q,char*x）//出队操作
{
if（Q->front==Q->rear）//队列为空
return（FALSE）;
*x=Q->element[Q->front];//x指向头指针指向的数据
Q->front=（Q->front+1）%MAXSIZE;
return（TRUE）;/*操作成功*/
}
intEnterQueue（SeqQueue*Q,charx）//入队操作
{
if（（Q->rear+1）%MAXSIZE==Q->front）
return（FALSE）;
Q->element[Q->rear]=x;
Q->rear=（Q->rear+1）%MAXSIZE;
return（TRUE）;//保持尾指针范围一直在0到49之间
}
voidInitQueue（SeqQueue*Q）//初始时，头尾所指向的位置相同，都为数组的起始位置
{
Q->front=Q->rear=0;
}
intPush1（LinkStackNode*top,charx）//链栈进栈
{
LinkStackNode*temp;
temp=（LinkStackNode*）malloc（sizeof（LinkStackNode））;
if（temp==NULL）
return（FALSE）;
temp->data=x;
temp->next=top->next;//头插法
top->next=temp;
return（TRUE）;
}
intPop1（LinkStackNode*top,char*x）//链栈出栈
{
LinkStackNode*temp;
temp=top->next;
if（temp==NULL）
return（FALSE）;
top->next=temp->next;
*x=temp->data;
//top=top->next;
free（temp）;
return（TRUE）;
}
voidInitStack（SeqStack*S）//顺序栈构造一个空栈S
{
S->top=-1;
}
intPush（SeqStack*S,charx）//顺序栈压入
{
if（S->top==Stack_Size-1）
return（FALSE）;
S->top++;
S->elem[S->top]=x;
return（TRUE）;
}
intPop（SeqStack*S,char*x）//顺序栈弹出
{
if（S->top==-1）
return（FALSE）;
else
{
*x=S->elem[S->top];
S->top--;
return（TRUE）;
}
}
voidLianzhan（）
{
inta;
LinkStackNode*s;
charx,*x1;
s=（LinkStackNode*）malloc（sizeof（LinkStackNode））;//链栈初始化，TOP为头节点
x1=（char*）malloc（sizeof（char））;
while（true）
{
printf（"请输入操作（1-压入元素,2-弹出元素,0-退出）:
"）;
scanf（"%d",&a）;
//printf（"\n"）;
if（a==1）
{
printf（"请输入压入的字符:
"）;
scanf（"%c",&x）;
Push1（s,x）;
continue;
}
if（a==2）
{
Pop1（s,x1）;
printf（"弹出的字符为:
%c\n",*x1）;
continue;
}
if（a==0）
{
break;
}
printf（"输入错误\n"）;
}
}
voidXunhuan（）
{
SeqQueue*s;
charx,*x1;
inta;
s=（SeqQueue*）malloc（sizeof（SeqQueue））;
x1=（char*）malloc（sizeof（char））;
while（true）
{
printf（"请输入操作（1-创建循环队列,2-进队,3-出队,0-退出）:
"）;
scanf（"%d",&a）;
//printf（"\n"）;
if（a==1）
{
InitQueue（s）;
continue;
}
if（a==2）
{
printf（"请输入进队的字符:
"）;
scanf（"%c",&x）;//此处%c前必须有空格，否则出错，如果是整形则不用
EnterQueue（s,x）;
printf（"进队完毕\n"）;
continue;
}
if（a==3）
{
DeleteQueue（s,x1）;
printf（"出队的字符为:
%c\n",*x1）;
continue;
}
if（a==0）
{
break;
}
printf（"输入错误\n"）;
}
}
voidDuilie（）
{
inta;
LinkQueue*s;
charx,*x1;
s=（LinkQueue*）malloc（sizeof（LinkQueue））;
x1=（char*）malloc（sizeof（char））;
while（true）
{
printf（"请输入操作（1-创建链式队列,2-进队,3-出队,0-退出）:
"）;
scanf（"%d",&a）;
//printf（"\n"）;
if（a==1）
{
InitQueue1（s）;
continue;
}
if（a==2）
{
printf（"请输入进队的字符:
"）;
scanf（"%c",&x）;
EnterQueue1（s,x）;
printf（"进队完毕\n"）;
continue;
}
if（a==3）
{
DeleteQueue1（s,x1）;
printf（"出队的字符为:
%c\n",*x1）;
continue;
}
if（a==0）
{
break;
}
printf（"输入错误\n"）;
}
}
voidShunxv（）
{
inta;
SeqStack*s;
charx,*x1;
s=（SeqStack*）malloc（sizeof（SeqStack））;
x1=（char*）malloc（sizeof（char））;
while（true）
{
printf（"请输入操作（1-创建顺序栈,2-压入元素,3-弹出元素,0-退出）:
"）;
scanf（"%d",&a）;
//printf（"\n"）;
if（a==1）
{
InitStack（s）;
continue;
}
if（a==2）
{
printf（"请输入压入的字符:
"）;
scanf（"%c",&x）;Push（s,x）;
printf（"压入完毕\n"）;
continue;
}
if（a==3）
{
Pop（s,x1）;
printf（"弹出的字符为:
%c\n",*x1）;
continue;
}
if（a==0）
{
break;
}
printf（"输入错误\n"）;
}
}
voidmain（）
{
intcho;
do
{
printf（"请选择1-顺序栈，2-链栈，3-循环队列，4-链式队列，0-退出：
"）;
scanf（"%d",&cho）;
switch（cho）
{
case1:
system（"cls"）;Shunxv（）;break;
case2:
system（"cls"）;Lianzhan（）;break;
case3:
system（"cls"）;Xunhuan（）;break;
case4:
system（"cls"）;Duilie（）;break;
default:
printf（"没有该选项"）;
}
}while（cho!
=0）;
}
选做题一源程序
（1）表达式求值
选做题
（2）汉诺塔
选做题（3）杨辉三角
4测试数据与实验结果（可以抓图粘贴）
必做题一测试结果
主界面：
顺序栈：
链栈：
循环队列：
链式队列：
选做题一测试结果
选做题
（1）表达式求值
测试组
（1）运算1+2所得结果为3检验正确
测试组
（2）运算2*5所得结果为10检验正确
选做题
（2）汉诺塔测试一组简单的汉诺塔问题，输出搬运的步骤，检验正确
选做题（3）杨辉三角
打印一个取值N为14的杨辉三角形经检验正确
5结果分析与实验体会
必做题中，可以再增加显示当前所有元素的选项，也可以在压入元素或者进队时能够连续输入多个元素，看着会简洁一点。
说到具体各个题目的体会，由于老师事先对我们进行了专项的辅导，所有完成实验并没有太大的困难。
关键在于一些细节的掌握，由于我的粗心，经常在头文件的读入上出现问题，可能是头文件与关联文件的命名不统一，可能是命名的重复，总之一系列的错误暴露了出来。
这可能也是实验的初衷，让同学们在实践中发现自己的错误，为自己留下深刻的印象，为以后的学习与进步打下坚实的基础吧。
选做题我无一疏漏的全部进行了调试，可能是想得到更多的锻炼机会吧！
虽然这些题目在以前C语言的学习中已经有所遇见。
但是自从引入了栈和队的知识后，我发现原来冗长的代码得到了极大的精简。
可能一个精巧的算法就可以代替原来百行的代码。
这完全改变了我原来的看法。
就拿汉诺塔问题为例，老师教我们用递归的方法，虽然很仔细的去分析，但依然是一个很耗时耗力的所在。
老师把相关算法给出来，这样写程序还比较容易一点，如果算法没有给，自己想的话很耗费时间，看到算法就觉得，原来是这样实现的，挺简单的。
所以还需要提高，算法是程序的核心。
注：
选做题
（1），（3）用了老师提供的头文件，有些同学的VC++6.0头文件夹中可能未包含进去，导致运行我的源程序出错。
升级会员 