实习报告-约瑟夫环

《数据结构》课程设计报告课程名称：《数据结构》课程设计课程设计题目：约瑟夫环姓名：院系：计算机学院专业：计算机科学与技术年级：学号：指导教师：课程设计的目的1.熟练使用C语言编写程序，解决实际问题；2.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；3.掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；4.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；二、需求分析以单项循环链表存储结构模拟约瑟夫环问题。即编号为1、2、3…、n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。按出列顺序印出各人的编号。演示程序以用户与计算机的对话方式执行，用户输入相应的数据，输出结果显示在其后。测试数据：n=77个人的密码依次为：3,1,7,2,4,8,4；首先m值为6（正确的输出顺序为：6,1,4,7,2,3,5）n=55个人的密码依次为：1,2,3,4,5首先m值为1（正确的输出顺序为：1,2,4,3,5）n=5首先m值为-2（输入的人数和初始密码不能为负数!）三、课程设计报告内容（一）、概要设计为实现上述程序功能，应利用单向循环链表存储结构模拟此过程。单向循环链表的抽象数据类型定义为：ADTCircularList{数据对象：D={ai|ai∈LNode,i=1,2,…,n,n≥0}数据关系：R1={<ai-1,ai>|ai-1∈D,i=2,…,n}基本操作：StatusListDelete_L(LinkList&L,intI,ElemType&e)操作结果：在带头结点的单链表L中，删除第i个元素，并用e返回其值}本程序中包括的三个基本模块：主程序模块：Voidmain(){初始化；do{接受命令；处理命令；}while(“命令”=”退出”)}线性表模块：实现线性表的抽象数据结构元素结构单元模块：定义线性表中每个元素的结构（二）、详细设计结点类型typedefstructLNode{ intdata;//密码 inti;//编号 structLNode*next;}LNode,*LinkList;用循环链表存储约瑟夫环，没有头结点，基本操作函数如下：intCreateList(LinkList&L,inta[],intn){//创建循环链表结构的约瑟夫环 LinkLists,r; inti; r=L; for(i=1;i<=n;i++) { s=(LinkList)malloc(sizeof(LNode)); s->data=a[i]; s->i=i; if(i==1) { L=s; s->next=s; r=s;//尾指针指向当前元素 } else { s->next=r->next; r->next=s; r=s; } } return1;}intListDelete_L(LNode*L){//删除表中一个结点 if(L->next==L)//只剩一个结点 { printf("%d\n",L->i); free(L); return0; } LNode*p; p=L->next;//p指向要删除元素的下一个结点 while(p->next!=L) p=p->next; LNode*q=L;//q指向需要被删除的元素结点 inte=L->i; p->next=L->next; free(q); printf("%d",e); return1;}intFindNode(LinkListL,intx){//查找表中某个结点 LinkListp=L; LinkListq; for(inti=1;i<x;i++) p=p->next; q=p->next;//下一次循环的起始位置 x=p->data; if(ListDelete_L(p)) FindNode(q,x); returnp->i;}主函数：intmain(){ intn,m; LinkListL; printf("请输入人数和初始密码:"); scanf("%d%d",&n,&m); if(n<0||m<0) { printf("输入的人数和初始密码不能为负数!\n"); return0; } inta[100]; printf("请输入每个人的密码:"); for(inti=1;i<=n;i++) scanf("%d",&a[i]); if(CreateList(L,a,n)) { printf("\n"); printf("正确的出列顺序为："); FindNode(L,m); printf("\n"); } return0;}函数的调用关系图反映了演示程序的层次结构：mainCreateListFindNodeListDelete_L（三）、调试分析刚开始时，忽略了题目要求的没有头结点这一项，没有把第一个结点单独拿出来建立，出现了逻辑上的错误。程序在编译时，有很多错误，主要是指针与引用概念不清导致。查找下一个时候采用求余数的方法，减少了循环次数。程序的算法复杂度为O(n2),不过虽然是C++写的，但还有很大的面向过程的思想，函数间的调用显得不好。（四）、用户手册本程序的运行环境为DOS操作系统，执行文件名为：JosephC.exe运行程序后，需要根据提示输入人数n、初始密码m，然后根据提示输入n个正整数，作为这n个人的密码，密码之间用空格隔开。按回车键即可得到测试结果。本程序的输入输出只进行一次，即只做一个案例的处理，如果用户要输入第二个案例，则需要退出并再运行本程序。（五）测试结果第一组数据测试结果：请输入人数和初始密码：720请输入每个人的密码：3172484正确的出列顺序为：6147235第二组数据测试结果：请输入人数和初始密码:51请输入每个人的密码：12345正确的出列顺序为：12435第三组数据测试结果：请输入人数和初始密码：5-2输入的人数和初始密码不能为负数!、程序清单#include<iostream>typedefstructLNode{ intdata;//密码 inti;//编号 structLNode*next;}LNode,*LinkList;intCreateList(LinkList&L,inta[],intn){ LinkLists,r; inti; r=L; for(i=1;i<=n;i++) { s=(LinkList)malloc(sizeof(LNode)); s->data=a[i]; s->i=i; if(i==1) { L=s; s->next=s; r=s;//尾指针指向当前元素 } else { s->next=r->next; r->next=s; r=s; } } return1;}intListDelete_L(LNode*L){ if(L->next==L)//只剩一个结点 { printf("%d\n",L->i); free(L); return0; } LNode*p; p=L->next;//p指向要删除元素的下一个结点 while(p->next!=L) p=p->next; LNode*q=L;//q指向需要被删除的元素结点 inte=L->i; p->next=L->next; free(q); printf("%d",e); return1;}intFindNode(LinkListL,intx){ LinkListp=L; LinkListq; for(inti=1;i<x;i++) p=p->next; q=p->next;//下一次循环的起始位置 x=p->data; if(ListDelete_L(p)) FindNode(q,x); returnp->i;}intmain(){ intn,m; LinkListL; printf("请输入人数和初始密码:"); scanf("%d%d",&n,&m); if(n<0||m<0) { printf("输入的人数和初始密码不能为负数!\n"); return0; } inta[100]; printf("请输入每个人的密码:"); for(inti=1;i<=n;i++) scanf("%d",&a[i]); if(CreateList(L,a,n)) { printf("\n"); printf("正确的出列顺序为："); FindNode(L,m); printf("\n"); } return0;}四、小结一、这次课程设计的心得体会通过实践我的收获如下：1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。4、通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。二、根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点：1、认真上好专业实验课，多在实践中锻炼自己。2、写程序的过程中要考虑周到，严密。3、在做设计的时候要有信心，有耐心，切勿浮躁。4、认真的学习课本知