数据结构报告堆栈与队列程序设计报告.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