数据结构与算法——joseph环.docVIP

. . 数据结构与算法课程设计 joseph环 152208100066 张小莲 目录 需求分析-------------------------------------------------------03 算法分析-------------------------------------------------------04 该单循环链表的逻辑结构------------------------------------------04 删除出列的结点-------------------------------------------------04 判断是否所有人全部出列------------------------------------------04 算法设计-------------------------------------------------------05 PersonList结构体-----------------------------------------------05 CreateList函数-------------------------------------------------05 Exports函数---------------------------------------------------05 完整代码-------------------------------------------------------07 结果说明-------------------------------------------------------09 总结------------------------------------------------------------10 需求分析 编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 算法分析 1. 该单循环链表的逻辑结构 由于题目要求“从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去”，队伍中编号最大的人报数完毕后编号最小的人应紧接着报数，所以创建链表时链表中最后一个结点的next指针直接指向首结点而不是头结点比较合适。该单循环链表的逻辑结构如下： 2. 删除出列的结点 某结点出列后，应将该结点从单循环链表里删除，则需要找到该结点的前一个结点，并由p指向它，通过修改指针域使结点p的直接后继为s的直接后继，即p-next=s-next。当m=1时，即将出列的结点的前一个结点就是还未进行移动的当前的s指针指向的结点。当要删除的结点恰好为head指向的结点时，删除前应修改head指向的结点为s-next。 判断是否所有人全部出列 由于结点出列后的删除操作，整个单循环链表的表长是逐渐缩短的，直至单链表只剩下头结点和首结点： 此时已经无法在进行删除结点操作，因为该结点的直接后继就是自己。但实际上，当只剩下一个人时无论m为何值此人直接出列就可以了。也就是说，当链表里只剩下最后一个结点时已经不必进行删除操作，直接输出该结点的编号即可。 于是问题就转化成如何判断链表里只剩最后一个结点，判断head-next是否与head相等可以解决问题。 算法设计 PersonList结构体 每个结点包含编号，密码以及指向下一个结点的指针域三个数据。 typedef struct node { int password; //密码 int number; //编号 struct node *next; //指针域 } PersonList; CreateList函数 该函数的功能是建立单循环链表，并从键盘读入每个编号的密码，入口参数n为单循环链表所包含的结点的个数，函数返回一个PersonList类型的指针。 PersonList *CreateList(int n) { PersonList *head,*s,*r; head=(PersonList *) malloc(sizeof(PersonList)); head-next=NULL; head-number=1; printf(请输入编号为1的人的密码：); scanf(%d,head-password