数据结构与算法-joseph环.doc

《数据结构与算法-joseph环.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构与算法课程设计joseph环152208100066张小莲10目录需求分析-------------------------------------------------------03算法分析-------------------------------------------------------04该单循环链表的逻辑结构------------------------------------------04删除出列的结点------------------------------------

2、-------------04判断是否所有人全部出列------------------------------------------04算法设计-------------------------------------------------------05PersonList结构体-----------------------------------------------05CreateList函数-------------------------------------------------05E

3、xports函数---------------------------------------------------05完整代码-------------------------------------------------------07结果说明-------------------------------------------------------09总结------------------------------------------------------------1010需求分析编号是1

4、，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。10算法分析1.该单循环链表的逻辑结构由于题目要求“从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如

5、此下去”，队伍中编号最大的人报数完毕后编号最小的人应紧接着报数，所以创建链表时链表中最后一个结点的next指针直接指向首结点而不是头结点比较合适。该单循环链表的逻辑结构如下：2.删除出列的结点某结点出列后，应将该结点从单循环链表里删除，则需要找到该结点的前一个结点，并由p指向它，通过修改指针域使结点p的直接后继为s的直接后继，即p->next=s->next。当m=1时，即将出列的结点的前一个结点就是还未进行移动的当前的s指针指向的结点。当要删除的结点恰好为head指向的结点时，删除前应修改head指向的结点

6、为s->next。3.判断是否所有人全部出列由于结点出列后的删除操作，整个单循环链表的表长是逐渐缩短的，直至单链表只剩下头结点和首结点：此时已经无法在进行删除结点操作，因为该结点的直接后继就是自己。但实际上，当只剩下一个人时无论m为何值此人直接出列就可以了。也就是说，当链表里只剩下最后一个结点时已经不必进行删除操作，直接输出该结点的编号即可。于是问题就转化成如何判断链表里只剩最后一个结点，判断head->next是否与head相等可以解决问题。10算法设计1.PersonList结构体每个结点包含编号，密码以

7、及指向下一个结点的指针域三个数据。typedefstructnode{intpassword;//密码intnumber;//编号structnode*next;//指针域}PersonList;2.CreateList函数该函数的功能是建立单循环链表，并从键盘读入每个编号的密码，入口参数n为单循环链表所包含的结点的个数，函数返回一个PersonList类型的指针。PersonList*CreateList(intn){PersonList*head,*s,*r;head=(PersonList*)mallo

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