数据结构与算法——joseph环

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-&

3、gt;next。当m=1时，即将出列的结点的前一个结点就是还未进行移动的当前的s指针指向的结点。当要删除的结点恰好为head指向的结点时，删除前应修改head指向的结点为s->next。3. 判断是否所有人全部出列由于结点出列后的删除操作，整个单循环链表的表长是逐渐缩短的，直至单链表只剩下头结点和首结点：此时已经无法在进行删除结点操作，因为该结点的直接后继就是自己。但实际上，当只剩下一个人时无论m为何值此人直接出列就可以了。也就是说，当链表里只剩下最后一个结点时已经不必进行删除操作，直接输出该结点的编号即可。 于是问题就转化成如何判断链表里只剩最后一个结点，判断head->next

4、是否与head相等可以解决问题。算法设计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=(Pers

5、onList *) malloc(sizeof(PersonList);head->next=NULL; head->number=1;printf("请输入编号为1的人的密码："); scanf("%d",&head->password); /从键盘中读取编号为1的人的密码getchar(); /接收回车r=head; for(int i=2;i<=n;i+)s=(PersonList *) malloc(sizeof(PersonList);s->next=NULL;s->number=i;printf(&

6、quot;请输入编号为%d的人的密码：",i);scanf("%d",&s->password); /从键盘读入每个编号的密码getchar(); /接收回车r->next=s; /插入新结点r=s; /将尾指针指向新结点r->next=head; /将最后一个结点的指针域指向首结点return head;3. Exports函数该函数的功能是模拟出列的过程，并按照出列的顺序输出每个人的编号，入口参数head为单循环链表，入口参数m为初始报数上限值。void Exports(PersonList *head,int m)PersonLis

7、t *s,*p;s=head; m=m-1;printf("出列顺序为:"); while(head!=head->next) /当链表里有一个以上的结点时if(m!=1) /若m=1可跳过for循环 for(int i=1;i<=m-1;i+) /报数直到第m-1个结点s=s->next;p=s; /p指向第m-1个结点s=s->next; /s指向第m个结点printf("%4d",s->number); /输出第m个结点的编号m=s->password; /将第m个结点的密码作为新的m值 if(s=head) /

8、若要删除的结点恰好是首结点，移动head指针head=s->next;p->next=s->next; /删除第m个结点s=p; /s指向报数1结点的前一个结点，为下一次报数做准备 printf("%4d",s->number); /输出链表里剩下的唯一一个结点完整代码#include <stdio.h>#include <stdlib.h>typedef struct nodeint password;int number;struct node *next; PersonList;PersonList *CreateLis

9、t(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;i<=n;i+)s=(PersonList *) malloc(sizeof(PersonList);s->next=NULL;s->

10、number=i;printf("请输入编号为%d的人的密码：",i);scanf("%d",&s->password);getchar();r->next=s;r=s;r->next=head;return 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;i<=m-1;i+)s=s-&g

11、t;next;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("请输入参加报数的人数：");scanf("%d",&n);PersonList *q=CreateList(n);Exports(q,m);printf("n");结果说明第一轮报数 m=7 编号为7的人出列第二轮报数 m=4 编号为1的人出列第三轮报数 m=5 编号为6的人出列第四轮报数 m=4 编号为2的人出列第