数据结构报告堆栈与队列程序设计报告.docx
《数据结构报告堆栈与队列程序设计报告.docx》由会员分享，可在线阅读，更多相关《数据结构报告堆栈与队列程序设计报告.docx（15页珍藏版）》请在冰点文库上搜索。
数据结构报告堆栈与队列程序设计报告
一、设计目的
1.掌握栈这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。
2.掌握队列这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。
3.了解和掌握递归程序设计的基本原理和方法。
二、设计要求
先为栈分配一个基本容量，并给存储空间分配增量当栈的空间不够使用时再逐段扩大。
其中stacksize指示的是栈的当前可使用的最大容量。
而false和true分别指的是栈是否为空，false为1反之亦然；error和ok则是指栈中元素是否可以返回即栈底元素是否为零，error为1反之亦然。
分别对从一到十二等十二个元素进行压栈然后弹栈，每当插入新的栈顶元素时，指针top增1；删除栈顶元素时即弹栈时指针top减1，因此非空栈中的栈顶指针始终在栈顶元素的下一个位置上。
最后进行销毁栈的操作，并得到top=0，stacksize=0，base=0的运行结果。
三、设计步骤
1、顺序栈程序
（1）输入M对M用8进行求模操作，M=M/8。
然后每次对模入栈。
利用栈先进后出的方式对数据出栈就是转换后的结果。
（2）程序设计步骤：
●提供宏va_start，va_arg和va_end，用于存取变长参数表
●定义栈元素类型，此句要在c3-1.h的前面
●存储空间初始分配量
●构造一个空栈S。
●把栈S置为空栈
●追加存储空间
●以十进制整型的格式输出元素的值
（3）调试清单：
对于这两个程序虽然用得数据结构不一样但本质算法一样。
核心也只是对于入栈出栈的考察。
但对于算法的考虑不全面出现了如下问题：
当输入31是想转换成16进制怎电脑会输出115。
而如果想转换的进制<10时则不会出现这一问题。
因此考虑后这个程序还是有待欠缺。
最好在转换进制输入时提示输入的数值小于10最好。
或者加一个switch语句专门对16进制进行特殊处理。
2、用队列实现杨辉三角
（1）算法思想：
对于变相数组的，单列队列若个个体成员存储的是一个数则算法复杂，若个体成员中每个存放个一维数组。
每个成员表示一行则会比较便捷。
（2）设计步骤：
●对每个成员做如下定义
●对每一行结束都加上0这样对下一行的最后一个元素操作简洁
●
入队、出队
●利用循环创建用户想要的行数
●创建一个空队列
四、程序设计框图
1、顺序栈框图
（如图一）
图一
（如图二）
2、杨辉三角队列设计框图
图二
五、程序源代码
1、顺序栈程序设计
#include
#include
#include
#include
#include
//#include
#include
#include
#include
#include
#include //提供宏va_start，va_arg和va_end，用于存取变长参数表
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
//#defineINFEASIBLE-1没使用
//#defineOVERFLOW-2因为在已定义值为3，故去掉此行
typedefintStatus; //Status是函数的类型，其值是函数结果状态代码，如OK等
typedefintBoolean; //Boolean是布尔类型，其值是TRUE或FALSE
typedefintSElemType; //定义栈元素类型，此句要在c3-1.h的前面
#defineSTACK_INIT_SIZE10 //存储空间初始分配量
#defineSTACK_INCREMENT2 //存储空间分配增量
structSqStack //顺序栈
{
SElemType*base; //在栈构造之前和销毁之后，base的值为NULL
SElemType*top; //栈顶指针
intstacksize; //当前已分配的存储空间，以元素为单位
};
voidInitStack（SqStack&S） //构造一个空栈S。
{
if（!
（S.base=（SElemType*）malloc（STACK_INIT_SIZE*sizeof（SElemType））））
exit（OVERFLOW）; //动态分配存储空间失败，则退出
S.top=S.base; //栈顶指向栈底（空栈）
S.stacksize=STACK_INIT_SIZE;//存储空间为初始分配量
}
voidDestroyStack（SqStack&S） //销毁栈S，S不再存在
{
free（S.base）; //释放栈空间
S.top=S.base=NULL; //栈顶、栈底指针均为空
S.stacksize=0; //当前已分配的存储空间为0
}
voidClearStack（SqStack&S）//把栈S置为空栈
{
S.top=S.base; //栈顶指针指向栈底
}
StatusStackEmpty（SqStackS）//若栈S为空栈，则返回TRUE；否则返回FALSE
{
if（S.top==S.base） //空栈条件
returnTRUE;
else
returnFALSE;
}
intStackLength（SqStackS）//返回栈S的元素个数，即栈的长度
{
returnS.top-S.base;
}
StatusGetTop（SqStackS,SElemType&e）//若栈S不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
{
if（S.top>S.base） //栈不空
{
e=*（S.top-1） ; //将栈顶元素赋给e
returnOK;
}
else
returnERROR;
}
voidPush（SqStack&S,SElemTypee）//插入元素e为栈S新的栈顶元素
{
if（S.top-S.base==S.stacksize） //栈满
{
S.base=（SElemType*）realloc（S.base,（S.stacksize+STACK_INCREMENT）*
sizeof（SElemType））;//追加存储空间
if（!
S.base） //追加存储空间失败，则退出
exit（OVERFLOW）;
S.top=S.base+S.stacksize; //修改栈顶指针，指向新的栈顶
S.stacksize+=STACK_INCREMENT;//更新当前已分配的存储空间
}
*（S.top）++=e; //将e入栈，成为新的栈顶元素，栈顶指针上移1个存储单元
}
StatusPop（SqStack&S,SElemType&e）
{
if（S.top==S.base）//栈空
returnERROR;
e=*--S.top;//将栈顶元素赋给e，栈顶指针下移1个存储单元
returnOK;
}
voidStackTraverse（SqStackS,void（*visit）（SElemType））//从栈底到栈顶依次对栈S中每个元素调用函数visit（）
{
while（S.top>S.base） //S.base指向栈元素
visit（*S.base++）; //对该栈元素调用visit（），
cout<<"\n"; //栈底指针上移1个存储单元
}
#defineElemTypeSElemType
Statusequal（ElemTypec1,ElemTypec2）//判断是否相等的函数
{
if（c1==c2）
returnTRUE;
else
returnFALSE;
}
intcomp（ElemTypea,ElemTypeb）//根据a<、=或>b，分别返回-1、0或1
{
if（a==b）
return0;
else
return（a-b）/abs（a-b）;
}
voidprint（ElemTypec） //以十进制整型的格式输出元素的值
{
cout<cout<<"\t";
}
voidprint1（ElemType&c） //以十进制整型的格式输出元素的值（设c为引用类型）
{
cout<}
voidprint2（ElemTypec） //以字符型的格式输出元素的值
{
cout<}
voidmain（）
{
intj;
SqStacks;
SElemTypee;
InitStack（s）; //初始化栈s
for（j=1;j<=12;j++）
Push（s,j）;
//将值为j的栈元素入栈s中
cout<<"栈中元素依次为\n";
StackTraverse（s,print）;
//从栈底到栈顶依次对栈s中每个元调用print（）函数
Pop（s,e）;//弹出栈顶元素，其值赋给e
cout<<"弹出的栈顶元素e=";
cout<cout<cout<<"栈空否?
";
cout<cout<<"\t（1:
空0:
否）";
GetTop（s,e）; //将新的栈顶元素赋给e
cout<<"\n栈顶元素e=";
cout<cout<cout<<"栈的长度为";
cout<ClearStack（s）;//清空栈s
cout<cout<<"清空栈后，栈空否？
";
cout<cout<<"\t（1:
空0:
否）\n";
DestroyStack（s）;//销毁栈s
cout<<"销毁栈后:
\ns.top=";
cout<cout<cout<<"s.stacksize=";
cout<cout<cout<<"s.base=";
cout<cout<2、队列程序设计
#include
#include
typedefstructNodeType{//对每个成员做如下定义
intdata[100];
structNodeType*next;
}NodeType;
NodeType*p;
typedefstruct{
NodeType*front,*rear;
}LinkQueue;
LinkQueueq;
voidsetNULL（LinkQueue*q）{//创建一个空队列
p=（NodeType*）malloc（sizeof（NodeType））;
p->next=NULL;
q->front=p;
q->rear=p;
}
voidAddQ（LinkQueue*q,inti）; //入队
voidPutQ（LinkQueue*q,inti,intt）;//出队
voidmain（）
{
inti,t;
setNULL（&q）;
printf（"请输入你想要多少行的杨辉三角:
"）;
scanf（"%d",&t）;
for（i=0;iAddQ（&q,i）;
}
printf（"你得到的杨辉三角:
\n"）;
for（i=0;iPutQ（&q,i,t）;
printf（"\n"）;
}
}
voidAddQ（LinkQueue*q,inti）
{
p=（NodeType*）malloc（sizeof（NodeType））;
p->next=NULL;
p->data[0]=1;
p->data[i+1]=0; //对每一行结束都加上0这样对下一行的最后一个元素操作简洁
while（i）{
p->data[i]=q->rear->data[i]+q->rear->data[i-1];
i--;
}
q->rear->next=p;
q->rear=p;
}
voidPutQ（LinkQueue*q,inti,intt）
{
intj=t-i-1;
p=q->front->next;
while（j）{printf（""）;j--;}
for（j=0;j<=i;j++）{
printf（"%4d",p->data[j]）;
}
p=p->next;
q->front->next=p;
}
六、编译与调试
。
图三
图四
七、心得体会
经过对《数据结构》的系统学习，不仅让我学会了理论知识，也拥有了第一次自己动手编程的经验。
第一次编程，总结了很多教训，例如首先要从一个好的模版开始编程，把书当作资料，而不是从头至尾的学习，那样只会多做无用功。
同时，也发现了学习这门课程要多上网查询资料，多与世界沟通，才是一个好的IT人。
对于栈其实是计算机常用的一种存储结构。
例如用C语言调用文件时计算机会先开辟一个缓冲区出来。
这里的操作也是入栈出栈。
对于杨辉三角队列的应用单列队列我实在想不出那个算法只能取巧。
对于控制其输出能让其更美观。
但到一定的行数后会出现乱序。
排不成三角形。
一直以来都没有花太多精力放在学习调试方面，主要还是平时调试的机会相对较少，一般情况下基本上就能解决问题了，还有就是，与其花精力去提高调试技能，还不如在设计、防御式编程和单元测试等能力去提高，以及提高自已编码的质量，减少BUG的出现或者缩小BUG的范围。
总的来说，这对我是一次尝试与创新的过程，也可以说是一个挑战的过程，毕竟以前没有做过，缺少经验。
现在利用自己学到的知识设计一个程序，这本身就是一个知识转化为生产力的过程，所以投入了很高的热情与努力。
在设计中我基本能按照规范的方法和步骤进行，所以学到了很多，同时也学会了细心与耐心的培养。
我想这在将来的工作或者社会“旅程”中都将起到很大的帮助。
更多地也明白了积累知识的重要性，最后想用一句成语结束本次心得——“学无止境”，虽然所学专业于C语言程序设计关系不大，但是学会了，仍然是对自己有力地提升。
八、参考文献
1.李春葆等编著.C语言程序设计题典.北京：
清华大学出版社，2002
2.钱能编著.C++程序设计教程.北京：
清华大学出版社，1999
3.程耀等编著.VisualC++6.0程序设计教程.北京：
电子工业出版社，1998
升级会员 