数据结构报告堆栈与队列程序设计报告.docx
- 文档编号:15787496
- 上传时间:2023-07-07
- 格式:DOCX
- 页数:15
- 大小:104.87KB
数据结构报告堆栈与队列程序设计报告.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
#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;i AddQ(&q,i); } printf("你得到的杨辉三角: \n"); for(i=0;i PutQ(&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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 报告 堆栈 队列 程序设计