数据结构课程设计报告 敢死队问题.doc

课 程 设 计（数据结构）班 级计科1003姓 名 学 号1011051093 指导教师 二一一年一月十日课程设计任务书及成绩评定课题名称 敢死队问题 、题目的目的和要求： 巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。 、设计进度及完成情况日 期内 容12.31-1.1选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。1.11.2创建相关数据结构,录入源程序。1.21.3调试程序并记录调试中的问题，初步完成课程设计报告。1.4上交课程设计报告打印版并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。、主要参考文献及资料1 严蔚敏 数据结构（C语言版）清华大学出版社 19992 严蔚敏 数据结构题集（C语言版）清华大学出版社 19993 徐宝文等译 C语言程序设计 清华大学出版社4 与所用编程环境相配套的C语言或C+相关的资料、成绩评定：设计成绩： （教师填写）指导老师： （签字）二一一 年 一 月 十 日目 录第一章 概述1第二章 系统分析2第三章 概要设计3第四章 详细设计4第五章 运行与测试9第六章 总结与心得13参考文献14第一章 概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。数据结构是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。在这次的课程设计中我选择的题目是图书管理。传统的人工图书管理，基本业务活动有对一本书的采编入库、清除库存、借阅和归还等等，但是人工统计操作起来效率相对来说要低，也容易出错。但是现在这些业务借助计算机系统完成后，效率可以得到提高，也可以减少出错的几率。可以使图书管理的日常业务更加的方便，迅捷，减少很多劳动量。课程设计的目的意义：加深对循环队列和数组的理解，以及对循环队列和数组的实际应用，加强自己的动手操作能力，增加对课程的兴趣，而不是枯燥的看课本。课程设计的问题：敢死队问题 有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。 排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。第二章 系统分析 1 敢死队问题包括：两个数据的输入，一个是队员的数量，另一个是模拟的形式。由于问题给出的数数的数量为5 ，所以k 值就默认为5 ，不再设置数据输入。故重点是要完成两种数据结构形式的删除，循环标记等操作。2 演示程序是以用户于计算机的对话方式执行，这需要调用一个清屏函数来完成使用者与计算机语言之间界面的处理。3 程序执行时的命令：本程序为了使用时的方便，采用阿拉伯数字的方式来完成程序的等各种选择输入，几乎不用输入什么特殊的命令。（要注意输入时必须用数字，否者可能会引起一些死循环）5. 测试数据。 1 5 13 数据运行结果 在第五章有详细的截图第三章 概要设计1. 数据结构类型： 一种是循环队列，另一种是数组形式 其中循环队列操作只需要删除操作，用数组形式处理和运算上则较复杂些 因此，循环队列占优势2. 程序总体上分为两大块，一块是循环队列的模拟，一块是数组形式的模拟 这两种形式功能都是模拟每个开始数数的位置对员的死亡顺序，其中循环 队列的函数接口为：lianbiao(n) ，数组的函数接口为：array(n);两模块算法基本一致，数据结构形式不同而已算法概述：For(int i=1;i<=n;i+) 初始化数据 对每个位置进行模拟/调用del /delx 函数进行模拟 判断是否安全 Printf->安全的位置； 第四章 详细设计1：存储结构形式 struct node int data; node *next;struct nodel int data;sqlistN;2：成员函数部分 int del(node *p,node *q) / 链表的删除操作 while(q->next!=q) int k=4; while(k-) p=p->next; q=q->next; if(q->data=1) return 0; else cout<<q->data<<" " q=q->next; p->next=q; if(q->next=q) return 1; void lianbiao(int n) int i,flag=0; for( i=1;i<=n;i+)/ 循环找出安全的开始位置 int k=i; cout<<"nn报数的位置为"<<k<<"时的排长之前的人员死亡顺序:n" node *head=new node,*t=head; head->data=1; head->next=head; int j=1; while(+j<=n) /构造循环队列 node *p=new node; p->data=j; p->next=t->next; t->next=p; t=t->next; t=head; node *p=head,*q;/ 设置p q 指针 while(p->next!=head) p=p->next; q=head; while(-k) /循环找开始的位置 p=p->next; q=q->next; if(del(p,q)=1) /判断位置是否安全 cout<<endl<<i<<"位置安全n" flag=i; else cout<<endl<<i<<"位置不安全n" continue ; if(flag) cout<<"nn安全位置是： "<<flag<<"nn" else cout<<"所有的位置都不安全"<<endl; /漏洞检测int delx(nodel sq,int key,int n,int sum) /数组的伪删除操作 / printf("第%d个位置开始数数的死亡的顺序号n",key); do int k=4; while(k) key+; if(key>13) key-=13; if(sqkey.data!=0) k-; if(key=1) if(sum=1) return 1; else return 0; else sum-=sqkey.data; sqkey.data=0; cout<<key<<" " key+;if(key>13) key-=13; / cout<<sqkey.data<<" "<<key<<endl; while(sqkey.data=0) key+; if(key>13) key-=13; / cout<<sqkey.data<<" "<<key<<endl; while(1);void array(int n) int i,flag=0; for( i=1;i<=n;i+)/ 循环找出安全的开始位置 int k=i; cout<<"nn报数的位置为"<<k<<"时的排长之前的人员死亡顺序:n" int j=1,sum=0; while(j <= n) /构造循环队列 sqlistj.data=j; sum+=j+; if( delx(sqlist,k,n,sum)=1) cout<<endl<<i<<"位置安全n" flag=i;/cout<<flag<<endl; else cout<<endl<<k<<"位置不安全n" /cout<<flag<<endl; cout<<" 所有人员情况： 0 表示已死 其它表示幸存者编号nn" for(int xx=1;xx<=n;xx+) cout<<sqlistxx.data<<" " cout<<endl; if(flag) cout<<"安全的位置是："<<flag<<"nnn" else cout<<"nn无安全位置可选n"<<endl;/ 漏洞检测3 ： 主函数部分int main() cout<<"-敢死队之死亡游戏模拟-n" int n,cas; cout<<"作为一名行政长官，报数开始位置很重要n"<<endl; cout<<"下面将模拟每个开始位置的人员死亡顺序-n" /system("cls"); do cout<<"请选择模拟的形式：n 1：链表 2：数组 3: 退出程序n" cin>>cas; if(cas>3|cas<=0) cout<<"输入错误n"continue; cout<<"n请输入队员的数量"<<endl; cin>>n; switch(cas) case 1: lianbiao(n);break; case 2: array(n); break; default : cout<<"输入错误n"break; cout<<"还要继续吗？ 按3 退出程序,其他输入继续n" int ss;cin>>ss; if(ss=3) break; else system("cls"); while(cas!=3); return 0;第五章 运行与测试1. 调试程序的过程中遇到什么问题 处理过程中经常忽视特殊位置的处理 像开始位置为1时，循环队列就会出现bugs而数组形式中删除操作不容易处理，用0 标记来代替 删除操作，在循环数数的时候经常认为是5 ，但是 循环只需要进行4 次即可。而删除操作的判断则用sum 总和进行判断，替换循环判断，省时！操作方便，在4 层循环数数操作中容易漏 data 为0 的判断以及 对 key 的变相取余3.测试数据 1 5 13 第六章 总结与心得 通过这一课程设计，加深了我对数据结构这门课程所学内容的进一步的理解与掌握；同时，通过对循环队列和数组的应用，使得我将计算机课程所学知识与实际问题很好地相联接在了一起。在这次课程设计中，培养了我开发一个中小型程序的能力。调程序的时候，要稳扎稳打，每个子函数单调试后在和主函数链接，效率较高，不然都最后全在一块，给调程序会带来极大的不便！对于每个子函数都要考虑到一些特殊值。最大的收获还是感觉到数据结构的实用性，不像看课本和考试那样，总是参生厌烦情绪，离开发一些东西越来越近了，而不像以前那样很遥远。总之，在这个的课程设计中，我的收获还是挺大的，不仅对于专业课有了更好的认识，而且还学到做事要细心、全面周到的重要性。参考文献:1 严蔚敏、吴伟民主编 数据结构（C语言版） 清华大学出版社 20022 殷人昆等著 数据结构（C+版） 清华大学出版社 20013 金远平著 数据结构（C+描述） 清华大学出版社 2005 4 许卓群等著 数据结构与算法 高等教育出版社 20045 Frank M.Carrano 等著 数据结构与+高级教程清华大学出版社 20046 严蔚敏、吴伟民 数据结构习题集（C语言版）清华大学出版社