约瑟夫环数据结构报告

一课程设计(论文)任务书信息学院计算机专业2013--2班一、课程设计(论文)题目约瑟夫环程序设计二、课程设计(论文)工作自2014年12月29日起至2015年1月10日止。三、课程设计(论文)地点:5-204四、课程设计(论文)内容要求：1．本课程设计的目的1、

使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。2、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；2．课程设计的任务及要求1）基本要求：1.

分析题目，查阅相关资料；2.

算法设计、数据结构设计；3.

编写代码并调试；4.

完成课程设计报告。2）创新要求：在基本要求达到后，可进行创新设计。3）课程设计论文编写要求（1）要按照书稿的规格打印誊写论文（2）论文包括目录、绪论、正文、小结、参考文献、谢辞、附录等（3）课程设计论文装订按学校的统一要求完成4）答辩与评分标准：（1）完成问题的解决方法分析：20分；（2）算法思想（流程）：20分；（3）数据结构：20分；（4）测试数据：20分（5）回答问题：20分。5）参考文献：《C程序设计》（第二版）谭浩强著清华大学出版社出版《C++程序设计》谭浩强著清华大学出版社出版《数据结构》（C语言版）严蔚敏、吴伟民著清华大学出版社出版6）课程设计进度安排内容天数地点构思及收集资料图书馆编程与调试实验室答疑 老师办公室学生签名：2014年12月29日课程设计(论文)评审意见（1）完成问题分析（20分）：优（）、良（）、中（）、一般（）、差（）；（2）算法思想（20分）：优（）、良（）、中（）、一般（）、差（）；（3）数据结构（20分）：优（）、良（）、中（）、一般（）、差（）；（4）测试数据（20分）：优（）、良（）、中（）、一般（）、差（）；（5）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（√）、否（）评阅人：赵海霞职称：讲师2015年1月11日目录TOC\o"1-3"\h\u25436一、综合软件设计目的 429808二、综合软件设计内容 4181221、课程设计的题目及简介 498992、设计说明 428633、程序截图 5302984、程序清单 515133三、测试数据： 2010425四、总结（写出心得和总结） 2141五、参考文献 21综合软件设计目的熟练掌握循环链表的建立删除，对一些实际问题的解决。解决一些特殊情况的漏洞。二、综合软件设计内容1、课程设计的题目及简介约瑟夫环

问题描述：编号为1，2„

n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。

基本要求：

1、利用单循环链表作为存储结构模拟此过程；

2、键盘输入总人数、初始报数上限值m及各人密码；

3、按照出列顺序输出各人的编号。设计说明通过对一些初始数据总人数N和初始报数上限m的输入并且对每个人的密码值输入，通过这些数据创建一个单循环链表。每个节点储存了每个人的密码值并且序号，已经下一个节点也的指针也就是下一个人的位置。通过遍历的次数达到报数的目的。出列后的人，就删除他所对应的节点，这样就又能进行下一次报数了。3、程序截图程序清单#include"LinkList.h"#defineERROR0#defineOK1#defineTRUE1#defineFLASE0typedefintElemType;typedefintStatus;Statuschulie(LinkList&L,intm);Statusmenu(LinkList&L);voidmain(){ LinkListL; while(1){if(menu(L))exit(1);};}/*对界面的打印并且输入*/Statusmenu(LinkList&L){ intn=0; intm; printf("\n**************约瑟环*********************"); printf("\n请输入总人数:"); scanf_s("%d",&n); if(n<=0){printf("\n输入错误");returnERROR;} printf("\n请输入初始报数上限值m:"); scanf_s("%d",&m); if(m<1){printf("\n输入错误");returnERROR;} CreateXHList_shun(L,n); if(n==1)printf("\n出列顺序为：\t1"); elsechulie(L,m); charchoose=NULL; //存放是否需要再来一次的y/n printf("\n是否再来一次(y/n)"); scanf_s("%c",&choose); while(1){ scanf_s("%c",&choose); fflush(stdin); if((choose=='y'||choose=='Y'||choose=='n'||choose=='N')) break; elseprintf("\n输入错误请重新输入(y/n)"); }// }while(!(choose=='y'||choose=='Y'||choose=='n'||choose=='N')); if(choose=='y'||choose=='Y')returnERROR; elsereturnOK;}Statuschulie(LinkList&L,intm) //对队伍出列的处理，{ if(!ListPankong(L))returnERROR; //若队伍为空或者未对线性链表初始化则退出 printf("\n出列顺序为："); LinkListp=L; //先将头指针赋值给p while(p!=p->next) //当p的指针指向自己的时候退出循环 { for(intls=0;ls<m-1;ls++) { p=p->next; } LinkListq=p->next; printf("\t%d",q->x); m=q->data; if(q==L->next&&p==L) { LinkListls=q; while(ls->next!=q) { ls=ls->next; } ls->next=q->next; } p->next=q->next; free(q); } printf("\t%d",p->x); //由于p指向自己的时候就退出循环所以p节点的编号还未打印 returnOK;}/* 此头文件写的是对线性链表的一些操作*/#include<stdio.h>#include<stdlib.h>#defineOK1#defineERROR0#defineTRUE1#defineFALSE0typedefintElemType;typedefintStatus;typedefstructLNode{ intx; ElemTypedata; //存放数据 structLNode*next; //用来指向下一节点，最后一个节点指向NULL}LNode,*LinkList;StatusCreateList_ni(LinkList&L,intn);StatusCreateXHList_shun(LinkList&L,intn);StatusCreateList_shun(LinkList&L,intn);StatusListInit(LinkList&L);StatusListInsert(LinkList&L,inti,ElemTypee);StatusListDelete(LinkList&L,inti,ElemType&e);StatusListPrintf(LinkList&L);StatusListFind(LinkList&L,int&i,ElemTypee);StatusListLength(LinkList&L);StatusListPankong(LinkList&L);StatusListPaixv(LinkList&L);StatusListNizhi(LinkList&L);StatusListChuchong(LinkList&L);voidListJiaoji(LinkList&LA,LinkList&LB);voidListBingji(LinkList&LA,LinkList&LB);voidListChaji(LinkList&LA,LinkList&LB);/*初始化线性链表给头结点开辟内存并给空值*/StatusListInit(LinkList&L) { L=(LinkList)malloc(sizeof(LNode)); if(L==NULL) { printf("\n开辟头结点失败"); returnERROR; } L->next=NULL; returnOK;}/*在线性链表中第i个元素前插入元素e成功返回ok*/StatusListInsert(LinkList&L,inti,ElemTypee) //{ LinkListp; intj=0; p=L; while(p&&j<i-1){p=p->next;j++;} if(!p||j>i-1)returnERROR; LinkLists=(LinkList)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; returnOK;}/*逆序创建输入长度为n的线性链表*/StatusCreateList_ni(LinkList&L,intn){ ListInit(L); for(intls=1;ls<=n;ls++) { ElemTypee; printf("\n请输入第%d个元素:",ls); scanf_s("%d",&e); ListInsert(L,1,e); } returnOK;}/*顺序创建输入长度为n的线性链表*/StatusCreateList_shun(LinkList&L,intn){ ListInit(L); LinkListq; q=L; for(intls=0;ls<n;ls++) { q->next=(LinkList)malloc(sizeof(LNode)); q=q->next;// q->x=ls+1;// printf("\t*****%d",q->x); printf("\n请输入第%d个元素:",ls+1); scanf_s("%d",&q->data); } q->next=NULL; returnOK;}/*顺序创建输入长度为n的循环线性链表*/StatusCreateXHList_shun(LinkList&L,intn){ ListInit(L); LinkListq; q=L; for(intls=0;ls<n;ls++) { q->next=(LinkList)malloc(sizeof(LNode)); q=q->next; q->x=ls+1; printf("\n请输入第%d个人的密码:",ls+1); scanf_s("%d",&q->data); } q->next=L->next; returnOK;}/*删除指定第i个节点并用e返回其值*/StatusListDelete(LinkList&L,inti,ElemType&e) { if(!L){printf("\n线性表未初始化");returnERROR;} LinkListp=L; intj=0; while(p&&j<i-1){p=p->next;j++;}; if(!(p->next||j>i-1))returnERROR; LinkListq=p->next; e=q->data; p->next=q->next; free(q); returnOK;}/*打印线性链表*/StatusListPrintf(LinkList&L){ if(L){printf("\n未初始化");returnERROR;} if(L->next==NULL){printf("\n线性链表中无元素");returnERROR;} printf("\n线性链表全部元素为："); LinkListp=L->next; while(p) { if(p->data) printf("\t%d",p->data); p=p->next; } returnOK;}/*若线性链表为空则返回ERROR，否则通过对线性链表中遍历比对线性链表中是否有该元素，找到返回OK,没找到返回ERROR*/StatusListFind(LinkList&L,int&i,ElemTypee) //查找元素e在线性链表中有没有{ if(L->next==NULL){printf("\n线性表为空");returnERROR;} LinkListp=L->next; intnum=1; while(p) { if(p->data==e) { i=num; returnOK; } else { p=p->next; num++; } } returnERROR;}/*返回当前线性链表的长度*/StatusListLength(LinkList&L) { intnum=0; LinkListp=L; while(p->next!=NULL) { p=p->next; num++; } returnnum;}/*先对头结点进行判断是否初始化，再判断线性链表是否为空若为空返回FALSE不是空返回TRUE*/StatusListPankong(LinkList&L){ if(!L){printf("\n线性表为初始化");returnERROR;} if(L->next==NULL){printf("\n线性表为空");returnFALSE;} elsereturnTRUE;}/*把线性链表中的元素都存到a这个数组里再对a数组进行排序后对线性链表重新存入值*/StatusListPaixv(LinkList&L) { if(!L){printf("\n未初始化");returnERROR;} if(L->next==NULL){printf("\n线性链表为空");returnERROR;} ElemTypea[100]; intnum=0; LinkListp=L->next; while(p!=NULL) { a[num++]=p->data; p=p->next; } for(inti=0;i<num;i++) for(intj=i;j<num;) { if(a[i]>a[j]) { intls=a[i]; a[i]=a[j]; a[j]=ls; } else j++; } p=L->next; for(intls=0;ls<num;ls++) { p->data=a[ls]; p=p->next; } returnOK;}/*把线性链表中的元素取出来存至数组中再逆序取出数组中的元素存入线性链表达到逆置的目的*/StatusListNizhi(LinkList&L) { if(L->next==NULL){printf("\n线性链表为空");returnERROR;} ElemTypea[100]; intnum=0; LinkListp=L->next; while(p!=NULL) { a[num++]=p->data; p=p->next; } p=L->next; while(num>0) { p->data=a[--num]; p=p->next; } returnOK;}/*对线性表进行除去重复元素的操作*/StatusListChuchong(LinkList&L){ ElemTypea[100]; intnum=0; LinkListp=L->next; if(p==NULL)returnERROR; while(p!=NULL) { a[num++]=p->data; p=p->next; } for(inti=0;i<num;i++) for(intj=i+1;j<num;) { if(a[i]==a[j]) { for(intls=i;ls<num-1;ls++) { a[ls]=a[ls+1]; } num--; ElemTypee; ListDelete(L,i+1,e); } elsej++; } p=L->next; for(intls=0;ls<num;ls++) { p->data=a[ls]; p=p->next; } returnOK;}/*销毁线性链表*/StatusListDestroy(LinkList&L){ if(L==NULL)returnERROR; LinkListp=L->next; LinkListq; while(p) { q=p; p=p->next; free(q); } returnOK;}/*对LA和LB进行进行比对有相同的元素就存放在a这个数组里，并且最后将a中的元素都打印出来*/voidListJiaoji(LinkList&LA,LinkList&LB){ ListChuchong(LA); ListChuchong(LB); inta[100]; intnum=0; LinkListp=LA->next; for(intls=0;ls<ListLength(LA);ls++) { inti; if(ListFind(LB,i,p->data)) { a[num++]=p->data; } p=p->next; } for(intls=0;ls<num;ls++) { printf("\t%d",a[ls]); }}/*对LA和LB求并集的操作*/voidListBingji(LinkList&LA,LinkList&LB){ inta[100]; ListChuchong(LA); LinkListp=LA; intnum=0; for(intls=0;ls<ListLength(LA);ls++) { p=p->next; a[num++]=p->data; } p=LB; for(intls=0;ls<ListLength(LB);ls++) { p=p->next; inti; if(!ListFind(LA,i,p->data)) { a[num++]=p->data