数据结构课程设计

约瑟夫环。学生姓名：张娟。

学号：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个人按照顺时针方向围坐一圈，每个人只有一个密码(正整数)。一开始任选一个正整数作为报数上限值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.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 node*linklist;

3.2程序**。

/建立循环链表函数。

voidinitlist(int n,linklist &r)

if(n>1)p->next=r;}

void delet(node *p)//删除结点的函数。

cout<主函数int main()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（n^2）。4.3算法改进。

程序不太完善，如可以把删除结点写在输出函数中，这样会降低时间复杂度4.4经验与体会．

通过这次课程设计，使我深深的感受到自己的不足和以前自己的渺小。这次的课程设计虽然**较少，但在编写的过程中仍感到很吃力，同时也让我感到自己数据结构学得不好，给自己提了一个醒。不过，虽然过程辛苦了一些，但还算学到了一些东西，提高了自己的能力，使我更加相信有付出就会有收获。

也让我更加的对编程感兴趣，我相信皇天不负有心人，只要你努力了，就会有一些收获。

5测试结果。

参考文献。1苏士华，黄学俊数据结构解析。习题。课程设计[m].合肥，中国科学技术大学出版社，20092张瑞军，数据结构[m].北京：清华大学出版社，2009

3刘怀亮，数据结构习题解析与实验指导[m].北京：治金出版社，20094数据结构课程设计，北京：

机械工业出版社，20045杨正宏，数据结构，中国铁道出版社，20016张士和，数据结构，清华大学出版社，2004

7黄维通，<9

数据结构课程设计》评分标准。学号。

程序运**况（占总成绩20%）

能正确运行基本能正确运行能运行但结果不完善。

程序功能的完善程度。

占总成绩15%）程序结构的合理性。

占总成绩15%）数据结构的合理性。

占总成绩25%）学生的工作态度与。

独立工作能力（占总成绩10%）设计报告的规范性。

占总成绩15%）

成绩等级指导老师签字。

完善基本完善不完善合理基本合理不太合理。

正确应用并有创新正确应用基本正确应用。

工作态度认真能独立完成任务工作态度认真但独立性较差工作态度基本认真但缺乏独立性。

符合规范基本符合规范规范性较差。

总分时间。姓名。

张娟。得分。

优秀：90分~100分良好：80分~89分。

中等：70~79分及格：60~69分不及格0分~59分。

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了