数据结构猴子选大王学位论文.docx
- 文档编号:2607887
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:12
- 大小:26.46KB
数据结构猴子选大王学位论文.docx
《数据结构猴子选大王学位论文.docx》由会员分享,可在线阅读,更多相关《数据结构猴子选大王学位论文.docx(12页珍藏版)》请在冰点文库上搜索。
数据结构猴子选大王学位论文
湖北民族学院
数据结构课程设计
课题名称:
猴子选大王
专业:
计算机科学与技术
班级:
0311401
姓名:
学号:
031140105
指导老师:
一、设计题目
猴子选大王
二、主要内容
一堆猴子都有编号,编号是1,2,3...m,这群猴子(m个)按照1-m的顺序围坐一圈,从第1开始数,每数到第N个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。
三、具体要求及应提交的材料
要求:
使用数组和循环链表等两种以上的存储方式来做
输入数据:
输入m,nm,n为整数,n 输出形式: 中文提示按照m个猴子,数n个数的方法,输出为大王的猴子是几号,建立一个函数来实现此功能 用C/C++语言编程实现上述内容,对每个问题写出一个算法实现,并按数学与计算机学院对课程设计说明书规范化要求,写出课程设计说明书。 可采用数组、链表数据结构实现。 在此基础上用C/C++实现其操作。 五、推荐参考资料 [1]严蔚敏,吴伟民.数据结构.清华大学出版社出版。 [2]严蔚敏,吴伟民.数据结构题集(C语言版).清华大学出版社.2003年5月。 [3]唐策善,李龙澎.数据结构(作C语言描述).高等教育出版社.2001年9月 [4]朱战立.数据结构(C++语言描述)(第二版本).高等出版社出版.2004年4月 [5]胡学钢.数据结构(C语言版).高等教育出版社.2004年8月 [6]徐孝凯等著.数据结构(C语言描述).清华大学出版社.2004 目录 摘要3 引言4 1需求分析4 1.1任务与分析4 1.2链表定义4 1.3主函数实现调用操作·····························································5 2 详细设计9 3调试分析14 4 用户使用说明15 5 测试结果15 结论16 致谢16 参考文献16 摘要 随着计算机的普及,涉及计算机相关的科目也越来越普遍,其中数据结构是计算机专业重要的专业基础课程与核心课程之一,为适应我国计算机科学技术的发展和应用,学好数据结构非常必要,然而要掌握数据结构的知识非常难,所以对“数据结构”的课程设计比不可少。 本课程设计主要通过使用循环链表、数组、以及单向链表,将猴子编号来数据化待选猴子坐成一个圈,并对圈内的猴子进行报数选取大王。 最终输出选出的猴子大王的编号。 考虑到循环链表、数组、以及单向链表要使用不同的结构体、算法等,故将不同的三种方法设计为分开的三个类。 只在主函数中调用其相应的函数。 程序通过调试运行,结果与预计结果一致,初步实现了设计功能。 关键词: 现代版;队列(循环链表);队列(数组);单向链表;数据结构 引言 A、课程设计任务 本课程设计主要实现在循环链表、数组、单向链表三种不同存储结构下对问题(即: “一堆猴子都有编号,编号是1,2,3...m,这群猴子(m个)按照1-m的顺序围坐一圈,从第1开始数,每数到第N个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。 ”)实现要求。 依据猴子的编号数据化将猴子用以上方式存储。 并进行报数入队,与出队操作。 最终输出最后一位猴子编号,该猴子为此次当选的猴王。 B、课程设计性质 数据结构课程设计是重要地实践性教学环节。 在进行了程序设计语言课和《数据结构》课程教学的基础上,设计实现相关的数据结构经典问题,有助于加深对数据结构课程的认识。 本课程设计是数据结构中的一个关于数组、链表等算法的实现,包括在存储结构中添加、删除操作,最后把结果输出。 此课程设计要求对数组存储结构和链表存储结构非常熟悉,并能熟练使用它们。 C、课程设计目的 其目的是让我们在学习完C++、数据结构等课程基础上,掌握数据的存储结构、掌握数据相应的存储,添加,更新等操作,并用输出结果。 进一步掌握设计、实现较大系统的完整过程,包括系统分析、编码设计、系统集成、以及调试分析,熟练掌握数据结构的选择、设计、实现以及操作方法,为进一步的应用开发打好基础。 1需求分析 1.1任务与分析 猴子选大王,众多猴子纷纷想成为大王,以一统群族。 更便享有最高的地位与权利,因而导致猴子间惨重的事件发生。 在现代发展的社会中不管人类还是猴子都不想看到如此不幸的画面。 故利用计算机软件来解决血腥的冲突。 即将编号为1,2,……n的一群猴子按照1-n的顺序围坐成一个圈,所以可以用数组将其以循环的方式存储,输入猴子的总数m与要报的数n,且保证n 还用rear表示数组尾front数组头,并进行报数,将未报到指定数的猴子加到rear;用链表时可以用指针结点将一个猴子作为一个结点存储,也用front表示链表头,rear表示链表尾。 将未到报数的猴子加到链表尾;循环链表就将链表的头尾连接,不用将未报到n的猴子加到尾部,只需将报到n的猴子结点删除。 最后输出最后一个猴子的信息,便得出该猴子为此次选举的猴子大王。 具体步骤如下: 第一步建立数组(链表),填入猴子编号及猴子出局时报的数; 第二步从第一个猴子报数; 第三步数组存储中将数m的猴子不作操作,将未数到的猴子循环存在数组中,可以将报过数的信息猴子覆盖。 链表中将报到的猴子结点删除; 第四步继续报数,重复第三步。 到只剩一个猴子编号; 第五步输出此猴子的信息。 1.2.链表定义 /*定义链表节点类型*/ typedefstructnode { intdata; structnode*next; }linklist; 1.3主函数的实现调用操作: 采用循环链表来实现,可参考课本。 intmain() { inti,n,k,m,total; linklist*head,*p,*s,*q; /*读入问题条件*/ printf("Pleaseenterthenumberofmonkeys: "); scanf("%d",&n); printf("Pleaseenterfromthemonkeysbegantocountoffthefirstofseveral: "); scanf("%d",&k); printf("Pleaseenterthenumberout: "); scanf("%d",&m); /*创建循环链表,头节点也存信息*/ head=(linklist*)malloc(sizeof(linklist)); p=head; p->data=1; p->next=p; /*初始化循环链表*/ for(i=2;i<=n;i++) { s=(linklist*)malloc(sizeof(linklist)); s->data=i; s->next=p->next; p->next=s; p=p->next; } /*找到第k个节点*/ p=head; for(i=1;i { p=p->next; } /*保存节点总数*/ total=n; printf("\nOutofsequence: "); q=head; /*只剩一个节点时停止循环*/ while(total! =1) { /*报数过程,p指向要删除的节点*/ for(i=1;i { p=p->next; } /*打印要删除的节点序号*/ printf("[%d]",p->data); /*q指向p节点的前驱*/ while(q->next! =p) { q=q->next; } /*删除p节点*/ q->next=p->next; /*保存被删除节点指针*/ s=p; /*p指向被删除节点的后继*/ p=p->next; /*释放被删除的节点*/ free(s); /*节点个数减一*/ total--; } /*打印最后剩下的节点序号*/ printf("\n\nKingoftheMonkeyistheNo.[%d]\n\n",p->data); free(p); system("pause"); return0; } 2.详细设计 程序代码: #include #include /*定义链表节点类型*/ typedefstructnode { intdata; structnode*next; }linklist; intmain() { inti,n,k,m,total; linklist*head,*p,*s,*q; /*读入问题条件*/ printf("Pleaseenterthenumberofmonkeys: "); scanf("%d",&n); printf("Pleaseenterfromthemonkeysbegantocountoffthefirstofseveral: "); scanf("%d",&k); printf("Pleaseenterthenumberout: "); scanf("%d",&m); /*创建循环链表,头节点也存信息*/ head=(linklist*)malloc(sizeof(linklist)); p=head; p->data=1; p->next=p; /*初始化循环链表*/ for(i=2;i<=n;i++) { s=(linklist*)malloc(sizeof(linklist)); s->data=i; s->next=p->next; p->next=s; p=p->next; } /*找到第k个节点*/ p=head; for(i=1;i { p=p->next; } /*保存节点总数*/ total=n; printf("\nOutofsequence: "); q=head; /*只剩一个节点时停止循环*/ while(total! =1) { /*报数过程,p指向要删除的节点*/ for(i=1;i { p=p->next; } /*打印要删除的节点序号*/ printf("[%d]",p->data); /*q指向p节点的前驱*/ while(q->next! =p) { q=q->next; } /*删除p节点*/ q->next=p->next; /*保存被删除节点指针*/ s=p; /*p指向被删除节点的后继*/ p=p->next; /*释放被删除的节点*/ free(s); /*节点个数减一*/ total--; } /*打印最后剩下的节点序号*/ printf("\n\nKingoftheMonkeyistheNo.[%d]\n\n",p->data); free(p); system("pause"); return0; } 3调试分析 由于此次的课程设计题目所需要的相关知识大多数可在《数据结构》书中找到,或借鉴。 所以在完成代码后运行时,没出现严重错误和问题。 只是有点小问题,即局部变量用错: 没定义的也用了。 调试并找出错误,进行修改。 最后获得成功。 4 用户使用说明 该系统具有简单、明了、使用等特点,能够方便、准确的计算出众多猴子编号选举大王的结果。 当使用该系统时,系统会给出相关的提示信息,用户只需根据提示信息,即可完成系统提供的所有功能。 5 测试结果 结论 在课程设计中,首先要看清问题,将问题要求理解透彻,在构思要如何实现,要用到哪些函数,要用什么算法,在课程设计构思中选算法是一个很重要的概念。 只有确定用什么算法后才能接下来的工作,将流程图画在纸上,再进行代码的编写。 在程序设计中编写代码只是一个方面,调试才是关键,它是一个相当繁琐的过程。 有许多新的问题需要被解决,但同时它也是个比较重要的过程,在调试中,你会学到很多新的东西,从而增加你编程能力和经验。 通过本次实习,温固了数据结构的相关知识,加深了对课内所学的有关数据的逻辑结构和存储表示、数据结构的选择合应用、算法的设计和时空效率分析等内容的理解,进一步熟悉了C++的应用与编程环境,巩固并提高了分析问题,解决问题的能力。 致谢 在本次课程设计过程中,首先感谢学校相关领导给了我一次提升实力的机会。 其次要感谢监督我完成该实验的老师,是她在我需要必要帮助时,申出了援助之手。 还要感谢教过我C++语言和数据结构的各位老师,是他们的授课,让我打下了完成该实验的基础。 最后,感谢身边的同学们、朋友们以及网友们,是你们给了我完成该实验的思路、方法。 参考文献 [1]杨宝刚.开展企业管理信息化工作的步骤[J].企业管理.2002.(11).12~15 [2]Islamabad.Softwaretoolsforforgerydetection[J].Businessline.2001.(5).29~32 [3]王立柱.C/C++与数据结构.北京: 清华大学出版社,2002 [4]顾元刚.数据结构简明教程.南京: 东南大学出版社等,2003 [5]郭福顺,王晓芬,李莲治《数据结构》(修订本),大连理工大学出版社,1997
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 猴子 大王 学位 论文