数据结构课程设计-joseph环

课程设计说明书NO.1沈阳大学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线性表的单链表存储结构课程设计说明书NO.2沈阳大学typedefstructnode{intnum;//成员编号intm;//每个成员的唯一编码structnode*next;}NODE,*LINK;2.3.2线性表的动态分配顺数存储结构typedefstructdata//输入函数中数据存储节点结构{intnum;intm;}DATA;2.3.3数据输入函数DATAInputData（）输入函数采用线性表的顺序存储结构，线性表的顺序存储结构是一种随机存取的存储结构。特点是存储空间连续，用一组地址连续的存储单元依次存储线性表的数据元素。并且逻辑位置相邻的两个元素其物理位置也相邻。每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数，由此，只要确定了存储线性表的起始位置，线性表中的任一数据元素都可以随机存取。由于高级程序设计语言中的数组类型也有随机存取的特性，因此，通常都用数组来描述数据结构中的顺序存储结构。线性表的顺序存储结构需要预先分配存储空间。输入函数算法设计如下：DATA*InputData(int*n)//数据输入函数，n是节点的个数{DATA*d,*p,*s;//d用来存放数组空间的首地址课程设计说明书NO.3沈阳大学inti;printf(Howmanypeoplethereare?\n);printf(PleaseInputlength:);scanf(%d,n);//输入节点数d=(DATA*)malloc(*n*sizeof(DATA));//申请内存空间函数malloc返回首地址存放在DATA类型的d变量里p=d;for(i=1;i=*n;i++)//动态输入各节点信息{printf(Number%d----inputm:(mmeansthesecretofthem!)：,i);scanf(%d,&p-m);p-num=i;p++;}return(d);//返回内存空间的首地址}课程设计说明书NO.4沈阳大学输入函数流程图如下：图1输入函数流程图2.3.4单向循环链表的建立LINKCreateLinklist(DATA*d,intn)单向循环链表是一种链式存储结构，它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环，由此，从表中任意结点出发均可找到表中其他结点。单向循环链表的构造类似于单向链表的构造，但是不同的是最后一个元素的指针指向的是首元素。循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是p或p-next开始输入nd=(DATA*)malloc(*n*sizeof(DATA));p=d;i=1i=*n输入mp-num=i;p++return(d)结束YN课程设计说明书NO.5沈阳大学是否为空，而是他们是否指向头指针，但有的时候，若在循环链表中设置尾指针而不设头指针，即带尾指针的单向循环链表，可使某些程序简化。单链表和顺序存储结构不同，它是一种动态结构，整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而可由系统应需求直接生成，因此，建立线性表线性存储结构的过程就是一个动态生成链表的过程。在单链表中任何两个元素的存储位置之间没有固定的联系。但每个元素的存储位置都包含在其直接前驱节点的信息之中。假设p是指向线性表中第i个数据元素（节点ai）的指针，则p-next是指向第i+1个数据元素（节点ai+1）的指针。换句话说，若p-data=ai，则p-next-data=ai+1。由此，在单链表中，取得第i个数据元素必须从头指针出发寻找，因此，单链表是非随机存取的存储结构。建立单向循环链表的算法设计：LINKCreateLinklist(DATA*d，intn)//单向循环链表的建立，d输入函数返回值，n节点个数；{NODE*l，*p，*s；//l用来存放不带头结点的单链表的首节点的地址；inti;p=l=(NODE*)malloc(sizeof(NODE));//申请节点空间，p指向第i+1个节点；p-num=d-num;//将第一个节点的信息转存在链表节点中；p-m=d-m;d++;//依次访问下一个数组元素；for(i=1;in;i++){s=(NODE*)malloc(sizeof(NODE));//申请下一个节点空间，节点地址存放在s中；s-num=d-num;s-m=d-m;p-next=s;p=s;d++;}课程设计说明书NO.6沈阳大学s-next=l;//将首节点的地址存放在最后一个节点的next域形成环return(l);//返回单链表的首地址}链表建立流程图：图2建立单向循环链表流程图开始inti;p=l=(NODE*)malloc(sizeof(NODE));p-num=d-m;p-m=d-m;d++;ins-next=lreturn(l)结束YNi=1s=(NODE*)malloc(sizeof(NODE));s-num=d-m;s-m=d-m;d++;i++课程设计说明书NO.7沈阳大学2.3.5Joseph环的构造voidJoseph(LINkl,intn,intm)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返回其值的算法如下：StatusListDelete_L(LinkList&L,inti,ElemType&e){p=L;j=0;While(p-next&&ji-1){//寻找第i个节点，并令p指向其前趋p=p-next;++j;}If(!(p-next)||ji-1)returnERROR;//删除位置不合理q=p-next;p-next=q-next;//删除并释放节点e=q-data;free(q);returnOK;}//ListDelete_L课程设计说明书NO.8沈阳大学Joseph环构造函数voidJoseph(LINKl，intn，intm)//l为单链表首节点地址，m是初始报数上限{LINKp，q，s；inti，j；p=l；printf(\n);for(i=0;in;i++)//n次循环输出n个节点的编号{for(j=1;jm;j++)//每次循环要经过m-1个节点{q=p;p=p-next;//p指向第m个节点}printf(%d\t,p-num);//输出第m个节点的编号m=p-m;q-next=p-next;//删除已经输出编号的节点p=p-next;//从相邻的下一个节点开始下一次循环}}约瑟夫构造函数的流程图如下：课程设计说明书NO.9沈阳大学图3约瑟夫环构造函数流程图开始inti,j;p=li=0inj=1jmq=p;p=p-next输出p-mm=p-m;q-next=p-nextp=p-next;结束YNYNj++课程设计说明书NO.10沈阳大学3源程序#includestdio.h#includemalloc.htypedefstructnode{intnum;intm;structnode*next;}NODE,*LINK;typedefstructdata{intnum;intm;}DATA;DATA*InputData(int*n){DATA*d,*p,*s;inti;printf(Howmanypeoplethereare?\n);printf(PleaseInputlength:);scanf(%d,n);d=(DATA*)malloc(*n*sizeof(DATA));p=d;for(i=1;i=*n;i++){printf(Number%d----inputm:(mmeansthesecretofthem!)：,i);scanf(%d,&p-m);p-num=i;p++;}课程设计说明书NO.11沈阳大学return(d);}LINKCreateLinklist(DATA*d,intn){NODE*l,*p,*s;inti;p=l=(NODE*)malloc(sizeof(NODE));p-num=d-num;p-m=d-m;d++;for(i=1;in;i++){s=(NODE*)malloc(sizeof(NODE));s-num=d-num;s-m=d-m;p-next=s;p=s;d++;}s-next=l;return(l);}voidJoseph(LINKl,intn,intm){LINKp,q,s;inti,j;p=l;printf(\n);for(i=0;in;i++)课程设计说明书NO.12沈阳大学{for(j=1;jm;j++){q=p;p=p-next;}printf(%d\t,p-num);m=p-m;q-next=p-next;p=p-next;}}main(){intn,m;DATA*d;LINKl;d=InputData(&n);l=CreateLinklist(d,n);printf(************************************\nPleaseInputtheinitialvalueofm:\n************************************);scanf(%d,&m);Joseph(l,n,m);}课程设计说明书NO.13沈阳大学4运行结果及分析4.1运行结果在main()主函数中，首先输出提示语句“Howmanypeoplethereare?\nPleaseInputlength:”,这是输入人数n的值。接着调用输入数据函数InputDtata（），根据提示输入每个人的唯一密码m的值，编号默认为从1到n。输入完数据调用单链