《数据结构及算法—joseph环》由会员分享，可在线阅读，更多相关《数据结构及算法—joseph环（10页珍藏版）》请在金锄头文库上搜索。
1、.数据结构与算法课程设计joseph环152208100066小莲目录需求分析-03算法分析-04该单循环链表的逻辑结构-04删除出列的结点-04判断是否所有人全部出列-04算法设计-05PersonList结构体-05CreateList函数-05Exports函数-05完整代码-07结果说明-09总结-10需求分析编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码正整数。一开始任选一个正整数作为报数上限值m，从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部
2、出列为止。设计一个程序来求出出列顺序。算法分析1. 该单循环链表的逻辑结构由于题目要求“从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，队伍中编号最大的人报数完毕后编号最小的人应紧接着报数，所以创建链表时链表中最后一个结点的next指针直接指向首结点而不是头结点比较合适。该单循环链表的逻辑结构如下：2. 删除出列的结点某结点出列后，应将该结点从单循环链表里删除，那么需要找到该结点的前一个结点，并由p指向它，通过修改指针域使结点p的直接后继为s的直接后继，即p-next=s-next。当m=1
3、时，即将出列的结点的前一个结点就是还未进行移动的当前的s指针指向的结点。当要删除的结点恰好为head指向的结点时，删除前应修改head指向的结点为s-next。3. 判断是否所有人全部出列由于结点出列后的删除操作，整个单循环链表的表长是逐渐缩短的，直至单链表只剩下头结点和首结点：此时已经无法在进行删除结点操作，因为该结点的直接后继就是自己。但实际上，当只剩下一个人时无论m为何值此人直接出列就可以了。也就是说，当链表里只剩下最后一个结点时已经不必进行删除操作，直接输出该结点的编号即可。 于是问题就转化成如何判断链表里只剩最后一个结点，判断head-next是否与head相等可以解决问题。算法设计
4、1. PersonList结构体每个结点包含编号，密码以及指向下一个结点的指针域三个数据。typedef struct nodeint password; /密码int number; /编号struct node *next; /指针域 PersonList;2. CreateList函数该函数的功能是建立单循环链表，并从键盘读入每个编号的密码，入口参数n为单循环链表所包含的结点的个数，函数返回一个PersonList类型的指针。PersonList *CreateList(int n)PersonList *head,*s,*r;head=(PersonList *) malloc(siz
5、eof(PersonList);head-next=NULL; head-number=1;printf(请输入编号为1的人的密码：); scanf(%d,&head-password); /从键盘中读取编号为1的人的密码getchar(); /接收回车r=head; for(int i=2;inext=NULL;s-number=i;printf(请输入编号为%d的人的密码：,i);scanf(%d,&s-password); /从键盘读入每个编号的密码getchar(); /接收回车r-next=s; /插入新结点r=s; /将尾指针指向新结点r-next=head; /将最后一个结点的指
6、针域指向首结点return head;3. Exports函数该函数的功能是模拟出列的过程，并按照出列的顺序输出每个人的编号，入口参数head为单循环链表，入口参数m为初始报数上限值。void Exports(PersonList *head,int m)PersonList *s,*p;s=head; m=m-1;printf(出列顺序为:); while(head!=head-next) /当链表里有一个以上的结点时if(m!=1) /假设m=1可跳过for循环 for(int i=1;inext;p=s; /p指向第m-1个结点s=s-next; /s指向第m个结点printf(%4d,
7、s-number); /输出第m个结点的编号m=s-password; /将第m个结点的密码作为新的m值 if(s=head) /假设要删除的结点恰好是首结点，移动head指针head=s-next;p-next=s-next; /删除第m个结点s=p; /s指向报数1结点的前一个结点，为下一次报数做准备 printf(%4d,s-number); /输出链表里剩下的唯一一个结点完整代码#include #include typedef struct nodeint password;int number;struct node *next; PersonList;PersonList *Cr
8、eateList(int n)PersonList *head,*s,*r;head=(PersonList *) malloc(sizeof(PersonList);head-next=NULL; head-number=1;printf(请输入编号为1的人的密码：);scanf(%d,&head-password);getchar();r=head; for(int i=2;inext=NULL;s-number=i;printf(请输入编号为%d的人的密码：,i);scanf(%d,&s-password);getchar();r-next=s;r=s;r-next=head;retur
9、n head;void Exports(PersonList *head,int m)PersonList *s,*p;s=head;m-;printf(出列顺序为:); while(head-next!=head)if(m!=1) for(int i=1;inext;p=s;s=s-next;printf(%4d,s-number);m=s-password;if(s=head)head=s-next;p-next=s-next;s=p;printf(%4d,s-number);void main()int m,n;printf(请输入报数上限值：);scanf(%d,&m);printf(
10、请输入参加报数的人数：);scanf(%d,&n);PersonList *q=CreateList(n);Exports(q,m);printf(n);结果说明第一轮报数 m=7 编号为7的人出列第二轮报数 m=4 编号为1的人出列第三轮报数 m=5 编号为6的人出列第四轮报数 m=4 编号为2的人出列第五轮报数 m=2 编号为4的人出列第六轮报数 m=1 编号为5的人出列第七轮报数 m=9 编号为8的人出列第八轮报数 m=7 编号为9的人出列第九轮报数 m=8 编号为3的人出列第十轮报数 m=3 编号为10的人出列总结 课本里提供了单循环链表的置空，建立，求表长，取结点，定位，插入，删除等操作代码，理解每个方法的原理便于面对实际问题时化繁为简灵活运用。-
