数 据 结 构 课 程 设 计.doc

.数 据 结 构 课 程 设 计 约瑟夫环 学 生 姓 名： 张娟 学 号： 131006432 指 导 教 师： 刘双红 完 成 日 期： 2014/6/7 . 目 录1 设计任务书21.1 题目与要求21.2 设计知识点21.3 输入输出分析21.4 测试数据分析32 概要设计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个人按照顺时针方向围坐一圈，每个人只有一个密码(正整数)。一开始任选一个正整数作为报数上限值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)输出形式：建立一个输出函数，将正确的出列顺序输出。 1.2 知识点 (1)掌握单向循环链表的建立。 (2)掌握单向循环链表的操作。 1.3 输入输出分析 输入:对于约瑟夫环的输入采用的是单向循环链表，单向循环链表的结点包含两部分：一是数据域，它又包括对单向循环链表进行密码的输入和对密码对应的序列的输入；二是指针域。输出：对于约瑟夫环的输出，需要输出结点数据域密码对应的序列，同时还要删除该结点，并释放该结点所对应的动态空间。 1.4 测试数据分析在程序运行结果出现的时候，对屏幕上出现的提示要按照其规则去完成，若是输入的不合法，则程序会结束。在提示是否要继续的时候：若是输入1，则继续；否则则停止。 2 概要设计2.1 结构体类型及函数声明(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 循环链表函数模块图（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;/输入每个人所对应的密码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;delet(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）：刚开始，在输入结点数据后，输出函数中序列输出的结果不正确。分析：指针代码的编写出现错误，使指针在一个节点删除后，不能够指向下一个结点。解决：在输出函数中，使循环条件发生改变，使指针指向的数据直接为要输出的数据。问题（2）：在主函数中，使用do-while循环时，程序出现错误。分析：while中的变量flag在循环体中被定义，造成系统识别不了该变量。解决：将flag变量定义在循环体外。4.2算法时空分析循环链表函数的算法：由程序可知，在单循环链表函数中，用了一次for循环,其时间复杂度为O（n）。删除结点函数的算法：在此函数中用了一次for循环，其时间复杂度为O（n）。输出函数的算法：在此函数中用了两次for循环，其时间复杂度为O（n2）。4.3 算法改进程序不太完善，如可以把删除结点写在输出函数中，这样会降低时间复杂度4.4 经验与体会通过这次课程设计，使我深深的感受到自己的不足和以前自己的渺小。这次的课程设计虽然代码较少，但在编写的过程中仍感到很吃力，同时也让我感到自己数据结构学得不好，给自己提了一个醒。 不过，虽然过程辛苦了一些，但还算学到了一些东西，提高了自己的能力，使我更加相信有付出就会有收获。也让我更加的对编程感兴趣，我相信皇天不负有心人，只要你努力了，就会有一些收获。 5测试结果 参考文献1 苏士华，黄学俊 数据结构 解析.习题.课程设计M.合肥，中国科学技术大学出版社，20092 张瑞军，数据结构M.北京：清华大学出版社，20093 刘怀亮 ，数据结构 习题解析与实验指导M.北京：治金出版社，20094 数据结构课程设计，北京：机械工业出版社，20045 杨正宏，数据结构，中国铁道出版社，20016 张士和，数据结构，清华大学出版社，20047 黄维通 ，清华大学出版社，20018 徐士良 ，数据结构，清华大学出版社，20029蒋文荣，数据结构，高等教育出版社，200310 闵敏，朱辉生，数据结构，高等教育出版社，2003 数据结构课程设计评分标准 学号131006432姓名张娟得分程序运行情况（占总成绩20%） 能正确运行 基本能正确运行能运行但结果不完善程序功能的完善程度（占总成绩15%） 完善基本完善 不完善程序结构的合理性（占总成绩15%）合理基本合理 不太合理数据结构的合理性（占总成绩25%） 正确应用并有创新 正确应用 基本正确应用