数据结构课程设计joseph环

Joseph环1. 课程设计目的 通过独立解决某个课程设计问题，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。 深刻理解、牢固掌握数据结构和算法设计技术， 提高分析和解决实际问题的能力。 在程序设计方法以及上机操作等基本技能和科学作风方面进行比较系统和严格的训练。2. 设计方案论证2.1 设计思路首先,定义两个结构体,将个人的信息写入其中内容包括个人的顺序号(Num),个人的密码m (随机输入的值)及指针.第二,再将每个人的信息存储于一个单向循环链表内.第三,根据题目要求编写程序,开始随机把一个数赋给m,开始报数(查找)则将顺序号为m的人的编号提出列,并将其的密码(随机输入的)赋给m.最后,m有了新值,再从出列的人的下一个位置开始重复上面第三步,直到所有人的顺序号都被调出,结束程序。2.2设计方法：2.2.1 结构设计利用单向循环链表存储结构模拟此过程,按照出列的顺序输出各个人的编号。输入数据：建立输入函数处理输入数据,输入m值和n值，存放在由DATA结构体为存储元素的顺序存储结构里。再建立单向循环链表，节点结构为NODE结构体，将所有信息存在链表里。输出形式：建立一个输出函数,将正确的输出序列。2.3算法设计2.3.1 线性表的单链表存储结构typedef struct node int num; /成员编号int m; /每个成员的唯一编码struct node *next; NODE,*LINK;2.3.2 线性表的动态分配顺数存储结构typedef struct data /输入函数中数据存储节点结构int num;int m; DATA;2.3.3 数据输入函数 DATA InputData（）输入函数采用线性表的顺序存储结构，线性表的顺序存储结构是一种随机存取的存储结构。特点是存储空间连续，用一组地址连续的存储单元依次存储线性表的数据元素。并且逻辑位置相邻的两个元素其物理位置也相邻。每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数，由此，只要确定了存储线性表的起始位置，线性表中的任一数据元素都可以随机存取。由于高级程序设计语言中的数组类型也有随机存取的特性，因此，通常都用数组来描述数据结构中的顺序存储结构。线性表的顺序存储结构需要预先分配存储空间。输入函数算法设计如下：DATA *InputData (int *n) /数据输入函数，n 是节点的个数DATA *d, *p, *s; /d用来存放数组空间的首地址int i; printf(How many people there are?n);printf(Please Input length:);scanf(%d,n); / 输入节点数d=(DATA *)malloc(*n*sizeof(DATA); /申请内存空间函数malloc返回首地址存放在DATA类型的d变量里 p=d; for(i=1;im); p-num=i; p+; return(d); /返回内存空间的首地址输入函数流程图如下：开始输入nd=(DATA *)malloc(*n*sizeof(DATA);p=d ; i=1inum=i;p+return(d)结束YN图1 输入函数流程图2.3.4 单向循环链表的建立 LINK CreateLinklist ( DATA *d, int n )单向循环链表是一种链式存储结构，它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环，由此，从表中任意结点出发均可找到表中其他结点。单向循环链表的构造类似于单向链表的构造，但是不同的是最后一个元素的指针指向的是首元素。循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是p或p-next是否为空，而是他们是否指向头指针，但有的时候，若在循环链表中设置尾指针而不设头指针，即带尾指针的单向循环链表，可使某些程序简化。单链表和顺序存储结构不同，它是一种动态结构，整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而可由系统应需求直接生成，因此，建立线性表线性存储结构的过程就是一个动态生成链表的过程。在单链表中任何两个元素的存储位置之间没有固定的联系。但每个元素的存储位置都包含在其直接前驱节点的信息之中。假设p是指向线性表中第i个数据元素（节点ai）的指针，则p-next是指向第i+1个数据元素（节点ai+1）的指针。换句话说，若p-data=ai，则p-next-data=ai+1。由此，在单链表中，取得第i个数据元素必须从头指针出发寻找，因此，单链表是非随机存取的存储结构。建立单向循环链表的算法设计：LINK CreateLinklist (DATA *d，int n) /单向循环链表的建立，d 输入函数返回值，n 节点个数； NODE *l，*p，*s； / l 用来存放不带头结点的单链表的首节点的地址 ；int i; p=l=(NODE *)malloc(sizeof(NODE); / 申请节点空间，p 指向第i+1个节点；p-num=d-num; /将第一个节点的信息转存在链表节点中；p-m=d-m; d+; /依次访问下一个数组元素；for(i=1;inum=d-num; s-m=d-m; p-next=s; p=s; d+; s-next=l; /将首节点的地址存放在最后一个节点的next域形成环return(l); / 返回单链表的首地址链表建立流程图：开始int i;p=l=(NODE *)malloc(sizeof(NODE);p-num=d-m;p-m=d-m;d+;inext=lreturn(l)结束YNi=1s=(NODE *)malloc(sizeof(NODE);s-num=d-m;s-m=d-m;d+;i+图2 建立单向循环链表流程图2.3.5 Joseph环的构造 void Joseph ( LINk l, int n, int m)Joseph函数的作用是第一次从第一个节点开始，在循环链表中依次走过m个节点，将第m个节点的编号输出，并将第m 个节点中的m值付给m 。再从下一个节点出发，依次数m 个节点、如此循环直到所有节点编号都被输出时结束。该算法可理解为对特定结点进行删除，并将所删结点的值进行输出。在线性表链表中删除元素时，仅需改变所删除元素前个结点的指针，如p-next=p-nexe-next，可见，在单链表中删除结点时，只需修改指针而不需要移动元素。删除链表中的结点e，并由系统收回其占用的存储空间，其过程如下：（1） 设定两个指针p和q。p指针指向被删除结点，q为跟踪指针，指向被删除结点的直接前驱结点。（2） p从表头指针head指向的第一个结点开始依次向后搜索。当p-data等于e时，被删除结点找到。（3） 修改p的前驱结点q的指针域。使p结点删除，然后释放存储空间。在带头结点的单链线性表L中，删除第i个元素，并由e返回其值的算法如下：Status ListDelete_L(LinkList &L,int i,ElemType &e) p=L;j=0; While (p-next & jnext;+j; If ( ! ( p-next) | ji-1) return ERROR; / 删除位置不合理q=p-next;p-next=q-next; /删除并释放节点e=q-data;free(q);return OK; / ListDelete_LJoseph 环构造函数void Joseph ( LINK l，int n，int m ) / l为单链表首节点地址，m是初始报数上限LINK p，q，s； int i，j；p=l； printf(n); for(i=0;in;i+) /n次循环输出n个节点的编号 for(j=1;jnext; / p指向第m个节点 printf(%dt,p-num); /输出第m个节点的编号m=p-m; q-next=p-next; /删除已经输出编号的节点p=p-next; /从相邻的下一个节点开始下一次循环 约瑟夫构造函数的流程图如下：开始int i,j; p=li=0inj=1jnext输出p-mm=p-m; q-next=p-nextp=p-next;结束YNYNj+图3约瑟夫环构造函数流程图3源程序#include#includetypedef struct node int num; int m; struct node *next; NODE,*LINK; typedef struct data int num;int m; DATA; DATA * InputData(int *n) DATA *d,*p,*s; int i; printf(How many people there are?n);printf(Please Input length:);scanf(%d,n); d=(DATA *)malloc(*n*sizeof(DATA); p=d; for(i=1;im); p-num=i; p+; return(d); LINK CreateLinklist ( DATA *d, int n) NODE *l,*p,*s ;int i; p=l=( NODE * ) malloc ( sizeof (NODE) ); p-num=d-num; p-m=d-m; d+; for(i=1;inum=d-num; s-m=d-m; p-next=s; p=s; d+; s-next=l; return(l); void Joseph ( LINK l, int n, int m) LINK p,q,s; int i,j;p=l; printf(n); for(i=0;in;i+) for(j=1;jnext; printf(%dt,p-num);m=p-m; q-next=p-next; p=p-next; main() int n,m;DATA *d; LINK l; d= InputData ( &n);l= CreateLinklist (d,n);printf(*nPlease Input the initial value of m:n* );scanf(%d,&m);Joseph(l,n,m);4运行结果及分析4.1 运行结果 在main()主函数中，首先输出提示语句“How many people there are?nPlease Input length: ”,这是输入人数n的值。接着调用输入数据函数InputDtata（），根据提示输入每个人的唯一密码m的值，编号默认为从1到n。输入完数据调用单链表建立函数CreateLinklist（）建立链表并将输入的人员信息存入链表里。这是界面显示语句“Please input the initial value of m:”,提示输入m的初始值。最后再调用约瑟夫环构造函数Joseph（），输出依次出列的人员编号，程序运行结束。截图如下。图4 为每个人分配唯一密码图5 输入m的初始值图6 输出人员编号 为验证程序的正确性，再次输入一组很苛刻的数据，并运行分析。首先确定人数n的值为5，将所有人的唯一密码都设为0，初始m值也设为0。该组数据的理论输出序列为1，2，3，4，5。程序运行截图如下所示：图7输入密码图8 输出序列4.2运行结果分析 首先输入人员个数为n=10,然后依次输入每个人的唯一编码，依次为2，9，0，3，7，5，11，23，46，17。m的初始值为65，从第一个人开始数最先输出的是编号为5的人，然后将该人的信息m值7付给m，从编号为6的人再开始数，输出的是编号为2的人,然后依此类推，输出编号为3，4，8，1，7，10，6，9的人。这与运行结果相吻合，也证实了结论的正确性。 第二组验证数据里，因为初始密码和每个人的密码均为0，所以指针p第一次指向的结点的编号即是要输出的编号，所以其输出序列和输入序列相同，为1，2，3，4，5。4.3程序评价 本程序先建立一个顺序表，用来存储数据。再构造单向循环链表，将数据存入链表节点里，之后依次为各个节点赋密码，并根据提示输入初始密码，然后，构造约瑟夫环函数，目的是对特定的节点进行删除，并将其值提取并输出。本程序满足算法的5个重要特征，即有穷性、确定性、可行性、输入、输出。程序不含语法错误，程序对于几组输入数据能够得出满足规定要求的结果，程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格要求的结果，程序对于一切合法的输入数据都能产生满足规格要求的结果。算法可读性较高，并在某些位置做了注释。当输入数据非法时，算法也能适当地做出反应进行处理，而不会产生莫名其妙的输出结果。本程序的效率较高，时间复杂度为O（n）。以上为本程序的一些优点，但是本程序还有一些不足之处，比如在单链表之外为玩家赋密码，还有引用data结构体等问题，这使得程序较为繁琐，希望下次设计时能够避免这些问题的发生。5 设计体会在这次课程设计中，我利用了链表一章的知识，解决了约瑟夫环问题，首先构造了单向循环链表，利用每个结点来模拟每一个玩家，又通过链表的赋值模拟为各人提供密码，借鉴链表的删除构造了约瑟夫环函数，并成功解决了问题。这个设计的特点是程序源代码较少，但是思路复杂，根据题意我选则的是用循环链表解决问题，其实应用顺序表也可以解决这个问题，不过后者较为复杂。在完成任务的过程中我遇到了很过困难，比如如何构造约瑟夫环函数，但是我还是通过了手边的资料和同学的帮助克服了困难，我明白了成功的来之不易，以及成功之后的欣喜。6 参考文献1 李春葆 数据结构教程M. 北京：清华大学出版社， 2006.10：P56592 严蔚敏等数据结构题集M北京：清华大学出版社， 2006.8：P89903 朱国进程序设计与问题求解M.上海：东华大学出版社，2007，1 ：P34504 梁翎.语言程序设计实用技巧与程序实例M.上海:上海科普出版社,2006.5 ：P46505 陈国章. Turbo C程序设计技巧M. 天津:天津科学技术出版社, 2007.5：P78906 王士元C高级实用程序设计M北京：清华大学出版社，20076 ：P29437 陈明. 数据结构(C语言版)M.北京：清华大学出版社,2006.3:P53-648 张群哲. 数据结构（C语言版）M. 西安： 西安电子科技大学出版社，2008.2：P28-439 顾为兵, 尹东， 袁平波， 朱明.数据结构及应用算法M. 合肥： 中国科学技术大学出版社， 2008.9：P33-3610 李春葆.数据结构教程上机实验指导M.北京：清华大学出版社,2006.7：P103-110