《2022年狼追兔子数据结构课程方案》由会员分享，可在线阅读，更多相关《2022年狼追兔子数据结构课程方案（15页珍藏版）》请在金锄头文库上搜索。
1、个人资料整理仅限学习使用青岛大学软件技术学院游戏算法实践报告姓名曹宁专业数字媒体艺术班级 10级 4 班指导教师刘春秋2018 年 1 月 16 日目录精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 15 页个人资料整理仅限学习使用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 测试结果
2、及分析7 7 心得体会 8 附录：程序代码 9 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 15 页个人资料整理仅限学习使用1 问题定义与描述1.1 问题定义现实中很多利用顺序表，栈解决一些数学模型问题1.2 问题描述围绕着山顶有10 个圆形排列的洞，狐狸要吃兔子，兔子说：“可以，但必须找到我，我就藏身于这十个洞中，你可以先到1 号洞找我，第二次隔一个洞即 3 号洞）找，第三次隔两个洞 即 6 号洞）找，以后如此类推，次数不限。”但狐狸从早到晚进进出出1000次，但仍没有找到兔子，问兔子究竟藏身于哪个洞里2. 关键技术顺序表一次申请
3、多个空间，包括结构体定义的。N 为整数，这样得到的就是N 个连续的空间。顺序表可以利用类似于数组的形式访问，即通过下标访问。当然定义的变量类型必须是指针类型的，很方便，当然也可以通过像链表一样的访问。单链表只是将空间分散开了，这样的优点就是动态申请，需要多少就申请多少，一般一次申请一个空间结点，即 N=1。3 数据的组织3.1 数据类型定义数据结构，顺序表，栈，单链表，数组。在程序设计中，为了处理方便，把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在 C 语言中， 数组属于构造数据类型。一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是
4、构造类型。因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 15 页个人资料整理仅限学习使用3.2 数据存储结构栈以顺序结构实现，队列以链表结构实现。顺序存储,大概意思就是把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间逻辑关系由存储单元的邻接关系来体现主要用在线性的数据结构4 总体设计4.1 顺序表系统模块图图 4.1 顺序表系统模块图4.2 栈的基本操作定义栈的顺序存取结构，分别定义栈的基本操作初始化栈、判栈为空、入栈、出栈等），通过定义
5、函数实现。4.3 顺序表的基本操作在顺序存储结构实现基本操作：初始化、创建、插入、删除、查找等运算。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 15 页个人资料整理仅限学习使用5 详细设计5.1 顺序存储的线性表1）程序中包括哪些函数？画出函数之间的调用关系。答：程序中包含 12 个成员函数和 1个主函数。 12个成员函数。如下，:SqList,SqList,CreateList,Insert,Delete,GetElem,Locate,Clear,Eepty,Full,Length,ListDisp2）程序中数据采用了什么样的逻辑
6、结构、物理结构？答：逻辑结构为依次存放线性表中的数据；物理结构为一组地址连续的储存单元。3）程序中那个函数实现顺序表的创建？其中包括顺序表的初始化吗？答：函数 SqList 用于实现顺序表的创建，不包括表的初始化。4）程序中哪个函数实现结点的插入？画出流程图。答： 函数 Insert实现结点的插入。图 5.1 实现结点插入5）程序中哪个函数实现结点的删除？画出流程图。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 15 页个人资料整理仅限学习使用答：函数 Delete实现了结点的删除。图 5.2 实现结点删除6）程序中提供了几种元素查找
7、方法？分别在哪个函数中实现？答：一种是按位置查找，在GetElem 中实现；另一种是按元素查找在Locate 中实现。7）程序退出时，调用了哪个函数？该函数主要操作有哪些？答：调用 SqList 函数，该函数主要操作是：删除顺序表元素，使表长和表容量为0. 6 测试结果及分析运行程序，程序主界面如图6.1 所示。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 15 页个人资料整理仅限学习使用图 6.1 程序的主界面运行结果如图 6.2 图 6.2 程序的运行结果精选学习资料 - - - - - - - - - 名师归纳总结 - - -
8、- - - -第 7 页，共 15 页个人资料整理仅限学习使用7 心得体会本次课程设计，使我对数据结构这门课程有了更深入的理解。数据结构是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。我的课程设计题目关于顺序表和栈。刚开始做这个程序的时候，感到完全无从下手，甚至让我觉得完成这次程序设计根本就是不可能的，于是开始查阅各种资料以及参考文献，之后便开始着手写程序，写完运行时有很多问题。特别是实现线索二叉树的删除运算时很多情况没有考虑周全，经常运行出现错误，但通过同学间的帮助最终基本解决问题。在本课程设计中，我明白了理论与实际应用相结合的重要性，并提高了自己组织数据及
9、编写大型程序的能力。培养了基本的、良好的程序设计技能以及合作能力。这次课程设计同样提高了我的综合运用所学知识的能力。并对C 有了更深入的了解。数据结构是一门实践性很强的课程，上机实习是对学生全面综合素质进行训练的一种最基本的方法，是与课堂听讲、自学和练习相辅相成的、必不可少的一个教案环节。上机实习一方面能使书本上的知识变“ 活” ，起到深化理解和灵活掌握教案内容的目的。另一方面，上机实习是对学生软件设计的综合能力的训练，包括问题分析，总体结构设计，程序设计基本技能和技巧的训练。此外，还有更重要的一点是：机器是比任何更严厉的检查者。因此，在 “ 数据结构 ” 的学习过程中，必须严格按照老师的要求
10、，主动地、积极地、认真地做好每一个实验，以不断提高自己的编程能力与专业素质。通过这段时间的课程设计，我认识到数据结构是一门比较难的课程。需要多花时间上机练习。这次的程序训练培养了我实际分析问题、编程和动手能力，使我掌握了程序设计的基本技能，提高了我适应实际，实践编程的能力。总的来说，这次课程设计让我获益匪浅，对数据结构也有了进一步的理解和认识。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 15 页个人资料整理仅限学习使用附录：程序代码#include #include #include #define StackSize 100 ty
11、pedef int DataType 。typedef struct DataType stackStackSize 。 int top。SeqStack。#define MAXSIZE 1100 typedef struct DataType listMAXSIZE 。 int last。SeqList。void InitList(SeqList *L /*顺序表的初始化 */ L-last=-1。 int ListEmpty(SeqList L /*判断顺序表是否为空 */ if(L.last=-1/* 判断最后一个元素的序号是否为-1*/ return 1。/*当顺序表为空时返回1；否则
12、返回 0*/ else return 0。/*否则返回 0*/ 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 15 页个人资料整理仅限学习使用int ListLength(SeqList L /*求线性表的长度 */ return L.last+1。 int GetElem(SeqList L,int i,DataType *e /*按序号顺序查找元素。查找成功将该值返回给e，并返回 1 表示成功；否则返回 -1 表示失败*/ if(iL.last+1/* 在查找第 i 个元素之前，先判断该序号是否合法*/ return -1。 *e
13、=L.listi-1 。/*将第 i 个元素值赋值给 e*/ return 1。 int LocateElem(SeqList *L,DataType x /*按内容查找，查找成功，将对应元素的序号返回；否则返回-1*/ int i=0。 while(ilast&L-listi!=x i+。 if(iL-last return -1。 else return i+1。 int InsertList(SeqList *L,int i,DataType x int j。 if(L-last=MAXSIZE-1/*表空间已满，不能插入 */ 精选学习资料 - - - - - - - - - 名师归纳
14、总结 - - - - - - -第 10 页，共 15 页个人资料整理仅限学习使用 printf(表满，不能插入 。 return -1。 if(iL-last+2/* 检查插入位置是否合法 */ printf(插入位置非法 。 return 0。 for(j=L-last 。j=i-1。j- L-listj+1=L-listj。/*结点移动 */ L-listi-1=x 。/* 新元素插入 */ L-last+。/*last 仍指向最后一个元素 */ return 1。/*插入成功，返回 */ int DeleteList(SeqList *L,int i,DataType *e int j
15、。if(L-last printf( 顺序表已空 ,不能插入进行操作 !n。 return 0。 else if(iL-last+1 printf( 插入位置不合法 !n。 return -1。 else 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 15 页个人资料整理仅限学习使用 *e=L-listi-1 。 for(j=i 。jlast 。j+ L-listj-1=L-listj。L-last-。 return 1。 void InitStack(SeqStack *S /*栈的初始化 */ S-top=-1。/*把栈顶指针置
16、为 -1*/ int StackEmpty(SeqStack S /*判断栈是否为空 */ if(S.top=-1/* 判断栈顶指针 top 是否为 -1*/ return 1。/*当栈为空时，返回1；否则返回 0*/ else return 0。 int GetTop(SeqStack S,DataType *e /*取栈顶元素 */ if(S.top/* 在取栈顶元素之前，判断栈是否为空*/ printf( 栈已经空！ n。 return 0。 else 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 15 页个人资料整理仅限学习
17、使用 *e=S.stackS.top。/*再取栈顶元素 */ return 1。 int PushStack(SeqStack *S,DataType x /*将元素 x 进栈，元素进栈成功返回1，否则返回 0*/ if(S-top=StackSize/*在元素进栈前，判断栈是否已满*/ printf( 栈已满 ,不能进栈！ n。 return 0。 else S-top+。/*修改栈顶指针 */ S-stackS-top=x。/*元素 x 进栈*/ return 1。 int PopStack(SeqStack *S,DataType *e /*出栈操作，出栈成功返回1，否则返回 0*/ i
18、f(S-top=-1/* 元素出栈前，判断栈是否为空*/ printf( 栈已经没有元素 ,不能出栈 !n。 return 0。 else *e=S-stackS-top。/*将出栈元素赋值给e*/ S-top-。/*修改栈顶指针，即出栈 */ 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 15 页个人资料整理仅限学习使用 return 1。 void main( SeqList a 。 InitList(&a 。 int b10=0,0,0,0,0,0,0,0,0,0 。 int i=0。/表示第 n-1 次 int f_n_1=
19、0。/表示 f(n-1。 int f_n=0。/表示 f(n a.list0=1。 a.last+。 for(i=1。i GetElem(a,i,&f_n_1。/从数组 a中将 f(n-1取出 f_n=f_n_1+(i+1。 if(f_n10 f_n=(f_n%10。 InsertList(&a,i+1,f_n 。/将第 n 次的结果输入到数组a for(i=0。i switch(a.listi case 1:b0+。break。 case 2:b1+。break。 case 3:b2+ 。break。 case 4:b3+ 。break。 case 5:b4+。break。 case 6:b
20、5+。break。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 15 页个人资料整理仅限学习使用 case 7:b6+ 。break。 case 8:b7+。break。 case 9:b8+。break。 case 10:case 0:b9+ 。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( 1 2 3 4 5 6 7 8 9 10 n。 printf(-n。 printf( 。 for(i=0。i printf(%3d ,bi 。 printf(n 。 printf(n。 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 15 页
