狼追兔子数据结构课程方案.docx
《狼追兔子数据结构课程方案.docx》由会员分享，可在线阅读，更多相关《狼追兔子数据结构课程方案.docx（18页珍藏版）》请在冰点文库上搜索。
狼追兔子数据结构课程方案
青岛大学软件技术学院
游戏算法实践报告
姓名曹宁
专业数字媒体艺术
班级10级4班
指导教师刘春秋
2018年1月16日
目录
1问题定义与描述3
1.1问题定义3
1.2问题描述3
2关键技术3
3数据的组织3
3.1数据类型定义3
3.2数据存储结构4
4总体设计4
4.1系统模块图4
4.2栈的基本操作4
4.3顺序表的基本操作4
5详细设计5
5.1顺序存储的线性表5
6测试结果及分析7
7心得体会8
附录：
程序代码9
1问题定义与描述
1.1问题定义
现实中很多利用顺序表，栈解决一些数学模型问题
1.2问题描述
围绕着山顶有10个圆形排列的洞，狐狸要吃兔子，兔子说：
“可以，但必须找到我，我就藏身于这十个洞中，你可以先到1号洞找我，第二次隔一个洞<即3号洞）找，第三次隔两个洞<即6号洞）找，以后如此类推，次数不限。
”但狐狸从早到晚进进出出1000次，但仍没有找到兔子，问兔子究竟藏身于哪个洞里
2.关键技术
顺序表一次申请多个空间，包括结构体定义的。
N为整数，这样得到的就是N个连续的空间。
顺序表可以利用类似于数组的形式访问，即通过下标访问。
当然定义的变量类型必须是指针类型的，很方便，当然也可以通过像链表一样的访问。
单链表只是将空间分散开了，这样的优点就是动态申请，需要多少就申请多少，一般一次申请一个空间结点，即N=1。
3数据的组织
3.1数据类型定义
数据结构，顺序表，栈，单链表，数组。
在程序设计中，为了处理方便，把具有相同类型的若干变量按有序的形式组织起来。
这些按序排列的同类数据元素的集合称为数组。
在C语言中，数组属于构造数据类型。
一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。
因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。
3.2数据存储结构
栈以顺序结构实现，队列以链表结构实现。
顺序存储,大概意思就是把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间逻辑关系由存储单元的邻接关系来体现
主要用在线性的数据结构
4总体设计
4.1顺序表系统模块图
图4.1顺序表系统模块图
4.2栈的基本操作
定义栈的顺序存取结构，分别定义栈的基本操作<初始化栈、判栈为空、入栈、出栈等），通过定义函数实现。
4.3顺序表的基本操作
在顺序存储结构实现基本操作：
初始化、创建、插入、删除、查找等运算。
5详细设计
5.1顺序存储的线性表
<1）程序中包括哪些函数？
画出函数之间的调用关系。
答：
程序中包含12个成员函数和1个主函数。
12个成员函数。
如下，
:
SqList,~SqList,CreateList,Insert,Delete,GetElem,Locate,Clear,Eepty,Full,Length,ListDisp
<2）程序中数据采用了什么样的逻辑结构、物理结构？
答：
逻辑结构为依次存放线性表中的数据；
物理结构为一组地址连续的储存单元。
<3）程序中那个函数实现顺序表的创建？
其中包括顺序表的初始化吗？
答：
函数SqList用于实现顺序表的创建，不包括表的初始化。
<4）程序中哪个函数实现结点的插入？
画出流程图。
答：
函数Insert实现结点的插入。
图5.1实现结点插入
<5）程序中哪个函数实现结点的删除？
画出流程图。
答：
函数Delete实现了结点的删除。
图5.2实现结点删除
<6）程序中提供了几种元素查找方法？
分别在哪个函数中实现？
答：
一种是按位置查找，在GetElem中实现；另一种是按元素查找在Locate中实现。
<7）程序退出时，调用了哪个函数？
该函数主要操作有哪些？
答：
调用~SqList函数，该函数主要操作是：
删除顺序表元素，使表长和表容量为0.
6测试结果及分析
运行程序，程序主界面如图6.1所示。
图6.1程序的主界面
运行结果如图6.2
图6.2程序的运行结果
7心得体会
本次课程设计，使我对《数据结构》这门课程有了更深入的理解。
《数据结构》是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。
我的课程设计题目关于顺序表和栈。
刚开始做这个程序的时候，感到完全无从下手，甚至让我觉得完成这次程序设计根本就是不可能的，于是开始查阅各种资料以及参考文献，之后便开始着手写程序，写完运行时有很多问题。
特别是实现线索二叉树的删除运算时很多情况没有考虑周全，经常运行出现错误，但通过同学间的帮助最终基本解决问题。
在本课程设计中，我明白了理论与实际应用相结合的重要性，并提高了自己组织数据及编写大型程序的能力。
培养了基本的、良好的程序设计技能以及合作能力。
这次课程设计同样提高了我的综合运用所学知识的能力。
并对C有了更深入的了解。
《数据结构》是一门实践性很强的课程，上机实习是对学生全面综合素质进行训练的一种最基本的方法，是与课堂听讲、自学和练习相辅相成的、必不可少的一个教案环节。
上机实习一方面能使书本上的知识变“活”，起到深化理解和灵活掌握教案内容的目的。
另一方面，上机实习是对学生软件设计的综合能力的训练，包括问题分析，总体结构设计，程序设计基本技能和技巧的训练。
此外，还有更重要的一点是：
机器是比任何更严厉的检查者。
因此，在“数据结构”的学习过程中，必须严格按照老师的要求，主动地、积极地、认真地做好每一个实验，以不断提高自己的编程能力与专业素质。
通过这段时间的课程设计，我认识到数据结构是一门比较难的课程。
需要多花时间上机练习。
这次的程序训练培养了我实际分析问题、编程和动手能力，使我掌握了程序设计的基本技能，提高了我适应实际，实践编程的能力。
总的来说，这次课程设计让我获益匪浅，对数据结构也有了进一步的理解和认识。
附录：
程序代码
#include
#include
#include
#defineStackSize100
typedefintDataType。
typedefstruct
{
DataTypestack[StackSize]。
inttop。
}SeqStack。
#defineMAXSIZE1100
typedefstruct
{
DataTypelist[MAXSIZE]。
intlast。
}SeqList。
voidInitList（SeqList*L>
/*顺序表的初始化*/
{
L->last=-1。
}
intListEmpty（SeqListL>
/*判断顺序表是否为空*/
{
if（L.last==-1>/*判断最后一个元素的序号是否为-1*/
return1。
/*当顺序表为空时返回1；否则返回0*/
else
return0。
/*否则返回0*/
}
intListLength（SeqListL>
/*求线性表的长度*/
{
returnL.last+1。
}
intGetElem（SeqListL,inti,DataType*e>
/*按序号顺序查找元素。
查找成功将该值返回给e，并返回1表示成功；否则返回-1表示失败*/
{
if（i<1||i>L.last+1>/*在查找第i个元素之前，先判断该序号是否合法*/
return-1。
*e=L.list[i-1]。
/*将第i个元素值赋值给e*/
return1。
}
intLocateElem（SeqList*L,DataTypex>
/*按内容查找，查找成功，将对应元素的序号返回；否则返回-1*/
{
inti=0。
while（i<=L->last&&L->list[i]!
=x>
i++。
if（i>L->last>
return-1。
else
returni+1。
}
intInsertList（SeqList*L,inti,DataTypex>
{
intj。
if（L->last==MAXSIZE-1>/*表空间已满，不能插入*/
{
printf（"表满，不能插入">。
return-1。
}
if（i>L->last+2>/*检查插入位置是否合法*/
{
printf（"插入位置非法">。
return0。
}
for（j=L->last。
j>=i-1。
j-->
L->list[j+1]=L->list[j]。
/*结点移动*/
L->list[i-1]=x。
/*新元素插入*/
L->last++。
/*last仍指向最后一个元素*/
return1。
/*插入成功，返回*/
}
intDeleteList（SeqList*L,inti,DataType*e>
{
intj。
if（L->last<0>
{
printf（"顺序表已空,不能插入进行操作!
\n">。
return0。
}
elseif（i<0||i>L->last+1>
{
printf（"插入位置不合法!
\n">。
return-1。
}
else
{
*e=L->list[i-1]。
for（j=i。
j<=L->last。
j++>
L->list[j-1]=L->list[j]。
L->last--。
return1。
}
}
voidInitStack（SeqStack*S>
/*栈的初始化*/
{
S->top=-1。
/*把栈顶指针置为-1*/
}
intStackEmpty（SeqStackS>
/*判断栈是否为空*/
{
if（S.top==-1>/*判断栈顶指针top是否为-1*/
return1。
/*当栈为空时，返回1；否则返回0*/
else
return0。
}
intGetTop（SeqStackS,DataType*e>
/*取栈顶元素*/
{
if（S.top<0>/*在取栈顶元素之前，判断栈是否为空*/
{
printf（"栈已经空！
\n">。
return0。
}
else
{
*e=S.stack[S.top]。
/*再取栈顶元素*/
return1。
}
}
intPushStack（SeqStack*S,DataTypex>
/*将元素x进栈，元素进栈成功返回1，否则返回0*/
{
if（S->top>=StackSize>/*在元素进栈前，判断栈是否已满*/
{
printf（"栈已满,不能进栈！
\n">。
return0。
}
else
{
S->top++。
/*修改栈顶指针*/
S->stack[S->top]=x。
/*元素x进栈*/
return1。
}
}
intPopStack（SeqStack*S,DataType*e>
/*出栈操作，出栈成功返回1，否则返回0*/
{
if（S->top==-1>/*元素出栈前，判断栈是否为空*/
{
printf（"栈已经没有元素,不能出栈!
\n">。
return0。
}
else
{
*e=S->stack[S->top]。
/*将出栈元素赋值给e*/
S->top--。
/*修改栈顶指针，即出栈*/
return1。
}
}
voidmain（>
{
SeqLista。
InitList（&a>。
intb[10]={0,0,0,0,0,0,0,0,0,0}。
inti=0。
//表示第n-1次
intf_n_1=0。
//表示f（n-1>。
intf_n=0。
//表示f（n>
a.list[0]=1。
a.last++。
for（i=1。
i<1000。
i++>
{
GetElem（a,i,&f_n_1>。
//从数组a中将f（n-1>取出
f_n=f_n_1+（i+1>。
if（f_n>10>
f_n=（f_n%10>。
InsertList（&a,i+1,f_n>。
//将第n次的结果输入到数组a
}
for（i=0。
i<1000。
i++>
{
switch（a.list[i]>
{
case1:
b[0]++。
break。
case2:
b[1]++。
break。
case3:
b[2]++。
break。
case4:
b[3]++。
break。
case5:
b[4]++。
break。
case6:
b[5]++。
break。
case7:
b[6]++。
break。
case8:
b[7]++。
break。
case9:
b[8]++。
break。
case10:
case0:
b[9]++。
break。
}
}
printf（"┏━━━━━━━━━━━━━━━━━━━━━━━┓\n">。
printf（"┃┃\n">。
printf（"┃狼追兔子┃\n">。
printf（"┃狼追踪的次数为1000次┃\n">。
printf（"┃狼找的洞的号数f（n>=f（n-1>+n┃\n">。
printf（"┃求狼追兔子的洞的号数┃\n">。
printf（"┗━━━━━━━━━━━━━━━━━━━━━━━┛\n">。
printf（"请稍等，程序正在运行中............................\n">。
Sleep（10000>。
printf（"┏━━━━━━━━━━━━━━━━━━━━━━━┓\n">。
printf（"┃┃\n">。
printf（"┃狼追踪的次数为1000次┃\n">。
printf（"┃狼找的洞的号数f（n>=f（n-1>+n┃\n">。
printf（"┃求狼追兔子的洞的号数与被狼需找的次数┃\n">。
printf（"┃12345678910┃\n">。
printf（"--------------------------------------------------\n">。
printf（"">。
for（i=0。
i<10。
i++>
printf（"%3d",b[i]>。
printf（"\n">。
printf（"┗━━━━━━━━━━━━━━━━━━━━━━━┛\n">。
}
升级会员 