数据结构课程设计

《数据结构课程设计》由会员分享，可在线阅读，更多相关《数据结构课程设计（11页珍藏版）》请在装配图网上搜索。

1、.数据结构课程设计约瑟夫环学生姓名：娟学号： 131006432指导教师：双红完 成 日 期：2014/6/7.目录1设计任务书21.1题目与要求21.2设计知识点21.3输入输出分析21.4测试数据分析错误 ! 未定义书签。2概要设计32.1结构体类型及函数声明32.2主程序流程32.3模块流程说明43详细设计53.1数据类型实现53.2程序伪码54调试分析74.1问题分析与回顾74.2算法时空分析84.3算法改进84.4经验和体会85测试结果8参考文献9.1 设计任务书1.1题目与要求题目：编号是 1，2， ，n 的 n 个人按照顺时针方向围坐一圈，每个人只有一个密码 ( 正整数 ) 。一

2、开始任选一个正整数作为报数上限值 m，从第一个仍开始顺时针方向自 1 开始顺序报数，报到 m时停止报数。报 m的人出列，将他的密码作为新的 m值，从他在顺时针方向的下一个人开始重新从 1 报数，如此下去，直到所有人全部出列为止。请设计一个程序求出出列顺序。要求： (1) 利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。(2) 测试数据： m的初值为 20，n=7，7 个人的密码依次为 3，1，7，2，4， 7，4，首先 m=6，则正确的输出是什么？(3) 输入数据：建立输入函数处理输入的数据，输入 m的初值 n，输入每个人的密码，建立单向循环链表。(4) 输出形式：建立一个

3、输出函数，将正确的出列顺序输出。1.2知识点(1) 掌握单向循环链表的建立。(2) 掌握单向循环链表的操作。1.3输入输出分析.输入 : 对于约瑟夫环的输入采用的是单向循环链表， 单向循环链表的结点包含两部分： 一是数据域，它又包括对单向循环链表进行密码的输入和对密码对应的序列的输入；二是指针域。输出：对于约瑟夫环的输出，需要输出结点数据域密码对应的序列，同时还要删除该结点，并释放该结点所对应的动态空间。1.4测试数据分析在程序运行结果出现的时候， 对屏幕上出现的提示要按照其规则去完成，若是输入的不合法，则程序会结束。在提示是否要继续的时候：若是输入 1，则继续；否则则停止。2 概要设计2.1

4、结构体类型及函数声明(1) 结构体定义了一个有数据和指针的结构体node(2) 函数声明循环链表函数void initList(int n,LinkList &R)输出函数void putout(int n,int k,LinkList R)结点删除函数void delet(node *p)2.2 主程序流程图.（1）主程序调用模块图主程序调用函数输入函数输出函数图 1 主程序调用模块图2.3模块流程说明主函数对各主要模块进行调用，各个主要模块又分别调用其他子模块。下面用简要流程图对各主要模块进行说明。（1）图 2 循环链表函数模块图开始有键盘输入个结点的信息调用结束图 2 循环链表函数模块图

5、.（ 2）图 3 输出函数模块图图 3 输出函数模块图3 详细设计3.1数据类型实现/ 构造结点结构体 typedef struct nodeint data;/ 用来储存人的密码 int order;/ 用来储存人的序号 struct node *next;*LinkList;3.2程序代码/ 建立循环链表函数void initList(int n,LinkList &R)R=(LinkList)malloc(sizeof(node);/创建一个带头结点的链表cinR-data;R-order=1;R-next=R;node *p,*q;q=R;for(int i=1;ix;/输入每个人所对

6、应的密码p-data=x;p-order=i+1;q-next=p;q=p;if(n1)p-next=R;void delet(node *p)/删除结点的函数node *q;q=p;while(q-next!=p)q=q-next;q-next=q-next-next;/删除结点free(p);/释放动态申请的结点空间/ 输出函数void putout(int n,int k,LinkList R)node *p,*q;p=R;cout 正确的出列顺序为 : ;for(int i=0;in;i+)for(int j=0;jnext;coutorderdata;q=p;p=p-next;del

7、et(q);coutendl;主函数int main()LinkList R;int n,k;int flag;.docoutn;coutk;cout 请输入 n 个人的密码 :endl;initList(n,R);cout 密码的原序列号为 :endl;for(int i=1;i=n;i+)couti ;coutendl;putout(n,k,R);coutendl;cout 还要继续吗，如果要，请输入1，否则输入其他数 flag;while(flag=1);return 0;4 调试分析4.1问题分析与回顾问题（ 1）：刚开始，在输入结点数据后，输出函数中序列输出的结果不正确。分析：指针代

8、码的编写出现错误，使指针在一个节点删除后，不能够指向下一个结点。解决：在输出函数中，使循环条件发生改变，使指针指向的数据直接为要输出的数据。问题（ 2）：在主函数中，使用do-while循环时，程序出现错误。分析： while 中的变量 flag在循环体中被定义，造成系统识别不了该变量。解决：将 flag变量定义在循环体外。.4.2 算法时空分析循环链表函数的算法：由程序可知，在单循环链表函数中，用了一次 for 循环 , 其时间复杂度为 O（n）。删除结点函数的算法：在此函数中用了一次 for 循环，其时间复杂度为 O（n）。输出函数的算法：在此函数中用了两次for 循环，其时间复杂度为 O

9、（n2）。4.3算法改进程序不太完善，如可以把删除结点写在输出函数中，这样会降低时间复杂度4.4经验与体会通过这次课程设计，使我深深的感受到自己的不足和以前自己的渺小。这次的课程设计虽然代码较少， 但在编写的过程中仍感到很吃力，同时也让我感到自己数据结构学得不好，给自己提了一个醒。不过，虽然过程辛苦了一些，但还算学到了一些东西，提高了自己的能力，使我更加相信有付出就会有收获。 也让我更加的对编程感兴趣，我相信皇天不负有心人，只要你努力了，就会有一些收获。5 测试结果.参考文献1士华，黄学俊数据结构 解析 . 习题 . 课程设计 M. ，中国科学技术大学， 20092瑞军，数据结构M. ：清华大

10、学， 20093怀亮 ，数据结构 习题解析与实验指导M. ：治金， 20094数据结构课程设计，：机械工业，20045正宏，数据结构，中国铁道，20016士和，数据结构，清华大学，20047黄维通， ，清华大学， 20018徐士良 ，数据结构，清华大学，20029 文荣，数据结构，高等教育，200310 闵敏，朱辉生，数据结构，高等教育，2003数据结构课程设计评分标准.学号131006432娟得分程序运行情况能正确运行（占总成绩 20%）基本能正确运行能运行但结果不完善程序功能的完善完善程度基本完善（占总成绩 15%）不完善程序结构的合理合理性基本合理（占总成绩 15%）不太合理数据结构的合理正确应用并有创新性正确应用（占总成绩 25%）基本正确应用学生的工作态度与工作态度认真能独立完成任务独立工作能力工作态度认真但独立性较差（占总成绩 10%）工作态度基本认真但缺乏独立性设计报告的规性符合规（占总成绩 15%）基本符合规规性较差成绩等级总分指导老师签字时间优秀： 90 分 100分良好： 80 分 89 分中等： 7079 分及格： 6069 分不及格 0 分59 分.