狼追兔子数据结构课程设计

1、青岛大学软件技术学院游戏算法实践报告姓 名 曹宁 专 业 数字媒体艺术 班 级 10级 4班 指导教师 刘春秋 2013年 1 月 16日目录1 问题定义与描述31.1 问题定义31.2 问题描述32 关键技术33 数据的组织33.1数据类型定义33.2数据存储结构44 总体设计44.1 系统模块图44.2栈的基本操作44.3顺序表的基本操作45 详细设计55.1顺序存储的线性表56 测试结果及分析77 心得体会8附录：程序代码91问题定义与描述1.1 问题定义现实中很多利用顺序表，栈解决一些数学模型问题1.2 问题描述围绕着山顶有10个圆形排列的洞，狐狸要吃兔子，兔子说：“可以，但必须找到我

2、，我就藏身于这十个洞中，你可以先到1号洞找我，第二次隔一个洞（即3号洞）找，第三次隔两个洞（即6号洞）找，以后如此类推，次数不限。”但狐狸从早到晚进进出出1000次，但仍没有找到兔子，问兔子究竟藏身于哪个洞里2.关键技术顺序表一次申请多个空间，包括结构体定义的。n为整数，这样得到的就是n个连续的空间。顺序表可以利用类似于数组的形式访问，即通过下标访问。当然定义的变量类型必须是指针类型的，很方便，当然也可以通过像链表一样的访问。单链表只是将空间分散开了，这样的优点就是动态申请，需要多少就申请多少，一般一次申请一个空间结点，即n=1。3 数据的组织3.1数据类型定义 数据结构，顺序表，栈，单链表，

3、数组。在程序设计中，为了处理方便， 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在c语言中， 数组属于构造数据类型。一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。 3.2数据存储结构栈以顺序结构实现，队列以链表结构实现。顺序存储,大概意思就是把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间逻辑关系由存储单元的邻接关系来体现主要用在线性的数据结构4总体设计4.1 顺序表系统模块图图4.1 顺序表系统模块图4.2栈的基本操作 定

4、义栈的顺序存取结构，分别定义栈的基本操作（初始化栈、判栈为空、入栈、出栈等），通过定义函数实现。4.3顺序表的基本操作在顺序存储结构实现基本操作：初始化、创建、插入、删除、查找等运算。5 详细设计5.1顺序存储的线性表（1）程序中包括哪些函数？画出函数之间的调用关系。答：程序中包含12个成员函数和1个主函数。12个成员函数。如下，:sqlist,sqlist,createlist,insert,delete,getelem,locate,clear,eepty,full,length,listdisp（2）程序中数据采用了什么样的逻辑结构、物理结构？答：逻辑结构为依次存放线性表中的数据；物理结

5、构为一组地址连续的储存单元。（3）程序中那个函数实现顺序表的创建？其中包括顺序表的初始化吗？答：函数sqlist用于实现顺序表的创建，不包括表的初始化。（4）程序中哪个函数实现结点的插入？画出流程图。答： 函数insert实现结点的插入。图5.1实现结点插入（5）程序中哪个函数实现结点的删除？画出流程图。答：函数delete实现了结点的删除。图5.2实现结点删除（6）程序中提供了几种元素查找方法？分别在哪个函数中实现？ 答：一种是按位置查找，在getelem中实现；另一种是按元素查找在locate 中实现。（7）程序退出时，调用了哪个函数？该函数主要操作有哪些？ 答：调用sqlist函数，该函

6、数主要操作是：删除顺序表元素，使表长和表容量为0.开始输入initstack()构造堆栈来记!l.basel.top=l.base;栈顶等于栈底 l.stacksize_curren=0;当前栈的长度为0结束exit(0)构造失败否是6 测试结果及分析运行程序，程序主界面如图6.1所示。 图6.1 程序的主界面运行结果如图6.2图6.2 程序的运行结果7心得体会本次课程设计，使我对数据结构这门课程有了更深入的理解。数据结构是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。我的课程设计题目关于顺序表和栈。刚开始做这个程序的时候，感到完全无从下手，甚至让我觉得完成这

7、次程序设计根本就是不可能的，于是开始查 阅各种资料以及参考文献，之后便开始着手写程序，写完运行时有很多问题。特别是实现线索二叉树的删除运算时很多情况没有考虑周全，经常运行出现错误，但通 过同学间的帮助最终基本解决问题。在本课程设计中，我明白了理论与实际应用相结合的重要性，并提高了自己组织数据及编写大型程序的能力。培养了基本的、良好的程序设计技能以及合 作能力。这次课程设计同样提高了我的综合运用所学知识的能力。并对c有了更深入的了解。数据结构是一门实践性很强的课程，上机实习是对学生全面综合 素质进行训练的一种最基本的方法，是与课堂听讲、自学和练习相辅相成的、必不可少的一个教学环节。上机实习一方面

8、能使书本上的知识变“活”，起到深化理解 和灵活掌握教学内容的目的;另一方面，上机实习是对学生软件设计的综合能力的训练，包括问题分析，总体结构设计，程序设计基本技能和技巧的训练。此外，还 有更重要的一点是：机器是比任何更严厉的检查者。因此，在“数据结构”的学习过程中，必须严格按照老师的要求，主动地、积极地、认真地做好每一个实验，以不断提高自己的编程能力与专业素质。通过这段时间的课程设计，我认识到数据结构是一门比较难的课程。需要多花时间上机练习。这次的程序训练培养了我实际分析问题、编程和动手能力，使我掌握了程序设计的基本技能，提高了我适应实际，实践编程的能力。总的来说，这次课程设计让我获益匪浅，对

9、数据结构也有了进一步的理解和认识。 附录：程序代码#include<stdio.h>#include<stdlib.h>#include <windows.h>#define stacksize 100typedef int datatype;typedef struct datatype stackstacksize; int top;seqstack;#define maxsize 1100typedef struct datatype listmaxsize; int last;seqlist;void initlist(seqlist *l)/*顺序

10、表的初始化*/l->last=-1;int listempty(seqlist l)/*判断顺序表是否为空*/ if(l.last=-1)/*判断最后一个元素的序号是否为-1*/ return 1;/*当顺序表为空时返回1；否则返回0*/ else return 0;/*否则返回0*/int listlength(seqlist l)/*求线性表的长度*/return l.last+1;int getelem(seqlist l,int i,datatype *e)/*按序号顺序查找元素。查找成功将该值返回给e，并返回1表示成功；否则返回-1表示失败*/ if(i<1|i>l

11、.last+1)/*在查找第i个元素之前，先判断该序号是否合法*/ return -1; *e=l.listi-1;/*将第i个元素值赋值给e*/ return 1;int locateelem(seqlist *l,datatype x)/*按内容查找，查找成功，将对应元素的序号返回；否则返回-1*/ int i=0; while(i<=l->last&&l->listi!=x) i+; if(i>l->last) return -1; else return i+1;int insertlist(seqlist *l,int i,datatyp

12、e x) int j; if(l->last=maxsize-1)/*表空间已满，不能插入*/ printf("表满，不能插入"); return -1; if(i>l->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;/*插入

13、成功，返回*/int deletelist(seqlist *l,int i,datatype *e)int j;if(l->last<0) printf("顺序表已空,不能插入进行操作!n"); return 0;else if(i<0|i>l->last+1) printf("插入位置不合法!n"); return -1;else *e=l->listi-1; for(j=i;j<=l->last;j+)l->listj-1=l->listj; l->last-; return 1;v

14、oid initstack(seqstack *s)/*栈的初始化*/ s->top=-1;/*把栈顶指针置为-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<0)/*在取栈顶元素之前，判断栈是否为空*/ printf("栈已经空！n"); return 0; else *e=s

15、.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)/*出栈操作，出

16、栈成功返回1，否则返回0*/ if(s->top=-1)/*元素出栈前，判断栈是否为空*/ printf("栈已经没有元素,不能出栈!n"); return 0; else *e=s->stacks->top;/*将出栈元素赋值给e*/ s->top-;/*修改栈顶指针，即出栈*/ 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=0;/表示f(n-1); int f_n=0;/表示f(n

17、) a.list0=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.listi) case 1:b0+;break; case 2:b1+;break; case 3:b2+;break; case 4:b3+;break; case 5:b4+;break; c

18、ase 6:b5+;break; 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(" 狼追踪的次数为1