数据结构课程设计Joseph环.doc

软 件 学 院课程设计报告书课程名称 数据结构课程设计 设计题目 Joseph环 专业班级 学 号 姓 名 指导教师 2010年 12 月目 录 (一) 设计时间 3(二) 设计目的 3(三) 设计任务3(四) 设计内容3-10(五) 总结与展望10(六) 参考文献.111 设计时间 12月27日-12月31日2 设计目的数据结构是计算机专业的核心课程，是计算机科学的算法理论基础和软件设计的技术基础。数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并上机调试的基本方法。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。3设计任务编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。4 设计内容 设计一个程序，以人机交互的方式执行，用户指定约瑟夫环游戏的总人数n和初始的报数上限m，然后输入每个人所持有的密码key。模拟约瑟夫环，从头开始报数，直到所有人出列。系统按照出列顺序给出编号及该人所持有的密码。 4.1需求分析 1、程序所能达到的功能：用户指定约瑟夫环游戏的总人数n和初始的报数上限m，然后输入每个人所持有的密码key。模拟约瑟夫环，从头开始报数，直到所有人出列。系统按照出列顺序给出编号及该人所持有的密码。2、输入的形式为一个在-21474836482147483648之间的整数数值 。3、测试数据正确输入结果：参加的人数为:3起始报数上线值:2输入第1个人的密码：4输入第2个人的密码：5输入第3个人的密码：6输出结果为:第1个出列的人的编号是：2 密码是：5第2个出列的人的编号是：3 密码是：6最后一个出局的人的编号是：1 密码是：4错误的结果：若输入的内容格式不符合要求，则会出现乱码。4.2总体设计1、 本程序中用到的所有抽象数据类型的定义为： 创建一个循环链表struct LNode* CreateList_L( LinkList *L,int z) 对循环链表进行操作 Operate(LinkList L,int h,int n) 找到第m个元素将其删除并且将其data域的值赋给下一个m值继而进行循环。2、主程序的流程为：输入起始参加约瑟夫循环的人数以及起始上限m值，建立一个循环链表，之后对循环来表进行操作，实现目的。3、各程序模块之间的调用关系。主函数调用CreateList_L( LinkList *L,int z)函数和Operate(LinkList L,int h,int n)。4.3详细设计1、struct LNode* CreateList_L( LinkList *L,int z) (*L)=(LinkList) malloc (sizeof(LNode);q=(*L); q-next=NULL; for(i=1;inext=p; p-next=NULL; p-data=i; printf(输入第%d个人的密码：,i); scanf(%d,&key); p-password=key; q=p; *L=(*L)-next; p-next=*L； return L; /创建约瑟夫环 Operate(LinkList L,int h,int n)int i=1,j;LinkList J; for (i = 1; in; i+) for (j = 1; j next; J-next = L-next;printf(第%d个出列的人的编号是：%d 密码是：%dn,i,L-data,L-password);h=L-password;L=L-next; i =L-password; j=L-data;printf(最后一个出局的人的编号是：%d 密码是：%dn,j,i);/对单循环链表进行操作main() k=CreateList_L(&I,n);I=*k;Operate(I,m,n); 2、struct LNode* CreateList_L( LinkList *L,int z) (*L)=(LinkList) malloc (sizeof(LNode);/定义一个LinkList型的指针q=(*L); q-next=NULL; for(i=1;inext=p; p-next=NULL; p-data=i;/赋值 printf(输入第%d个人的密码：,i); scanf(%d,&key); p-password=key;/输入之后赋值 q=p; /将循环链表中的data和password依次赋值 *L=(*L)-next; p-next=*L；/将尾指针赋给头指针，使其变为一个循环链表 return L; /创建约瑟夫环 Operate(LinkList L,int h,int n)int i=1,j;LinkList J; for (i = 1; in; i+) for (j = 1; j next; /找出第m个元素J-next = L-next;/将其删除printf(第%d个出列的人的编号是：%d 密码是：%dn,i,L-data,L-password);h=L-password;/重新赋给hL=L-next;/让L指向下一个循环链表中的指针 i =L-password; j=L-data;printf(最后一个出局的人的编号是：%d 密码是：%dn,j,i);/对单循环链表进行操作main() k=CreateList_L(&I,n);I=*k; Operate(I,m,n);开始3、 函数的调用关系图为：建立单链表，使其成为循环链表输入人数和起始上限值inext=*L使p指向头结点对人持有的密码进行赋值p-next=*L返回头指针进行Operate函数i总人数n 是 否输出最后一个人的密码jnext结束输出此人所持有的密码，并将其付给下一个n4.4测试与分析4.4.1测试参加的人数为:3起始报数上线值:2输入第1个人的密码：4输入第2个人的密码：5输入第3个人的密码：6输出结果为:第1个出列的人的编号是：2 密码是：5第2个出列的人的编号是：3 密码是：6最后一个出局的人的编号是：1 密码是：44.4.2分析1、当初试图仅仅应用一个指针来指向循环链表，发现不行，采用两个指针，通过建立节点之处，通过复制是一个指针指向表头，赋完值之后，进行让位指针指向头指针，从而构建循环链表，在对循环链表进行操作的时候，发现最后一个元素不能通过循环链表将其输出，只能通过再一个输出语句来输出最后一个元素。2、用单循环链表来模拟约瑟夫环，结点信息包括编号、密码、指向下一个结点的指针，用三大主要的函数来实现功能，包括创建链表的函数、输出链表信息的函数、删除结点也就是出栈的函数、主函数等函数。4.5 附录#include #include typedef struct LNodeint data;int password; struct LNode * next;LNode, *LinkList;struct LNode* CreateList_L( LinkList *L,int z) int key,i;LinkList p,q;(*L)=(LinkList) malloc (sizeof(LNode);q=(*L); q-next=NULL; for(i=1;inext=p; p-next=NULL; p-data=i; printf(输入第%d个人的密码：,i); scanf(%d,&key); p-password=key; q=p; *L=(*L)-next; p-next=*L; return L; /创建约瑟夫环 Operate(LinkList L,int h,int n)int i=1,j;LinkList J;for (i = 1; in; i+) for (j = 1; j next; J-next = L-next;printf(第%d个出列的人的编号是：%d 密码是：%dn,i,L-data,L-password);h=L-password;L=L-next; i =L-password; j=L-data;printf(最后一个出局的人的编号是：%d 密码是：%dn,j,i); /对单循环链表进行操作void main()int n,m;LinkList I,*k;printf(参加的人数为:);scanf(%d,&n);printf(起始报数上线值:);scanf(%d,&m);k=CreateList_L(&I,n);I=*k;printf(输出结果为:n); Operate(I,m,n);5 总结与展望课程设计的过程，需要创建一个循环链表，这个循环链表是在单链表的基础上改造得来，途中遇到指针值传错的问题，需创建两个指针， p-next=*L;实现了单链表的循环，在程序运行的过程中，调用的两个函数并未完全运行，而自己有需要查找问题所在，运用一个简单的printf函数即可知道程序运行到哪里，书上提示的只是算法，不能直接在电脑上运行，缺点在程序运行过程中一旦输入错误，无法返回。从这次课程设计的实践中认识到自己还有很多的不足，发现自己眼高手低的毛病，经过这次课程设计，我对自己的实践方面进行了加强，虽然在课程设计的过程中遇