中国市政建设局网站,上海网站建设聚众网络,网页升级访问狼在线观看,省级精品课程网站建设title: 双向链表实现约瑟夫问题 date: 2023-05-16 11:42:26 tags: **问题#xff1a;**知n个人围坐在一张圆桌周围。从编号为k的人开始报数#xff0c;数到m的那个人出列#xff1b;他的下一个人又从1开始报数#xff0c;数到m的那个人又出列#xff1b;依此规律重复下去**知n个人围坐在一张圆桌周围。从编号为k的人开始报数数到m的那个人出列他的下一个人又从1开始报数数到m的那个人又出列依此规律重复下去直到圆桌周围的人全部出列。 git地址https://github.com/944613709/HIT-Data-Structures-and-Algorithms 算法思想 \1. 构建n个结点的双向链表,初始化按照先后顺序给链表的每个节点data值赋值为i代表是链表第i个 \2. 执行search函数从Head开始寻找第P个节点while循环head head-next;直到来到第P个结点 \3. 执行Jump函数将从当前head的前m-1次结点进行正常报数然后返回第m个结点 \4. 对Jump函数返回来的第m个结点作为新head执行Delete语句删除当前的结点并且返回下一个节点进行下一轮报数 \5. 利用Delete函数返回来的结点作为新head重复34操作 \6. 上述重复操作总共执行n-1次出列之后剩下最后一个人 算法步骤 \1. 建立n个结点的双向链表 (1) 定义一个Node *head作为头结点data赋值1再定义一个Node *tail记录尾结点 (2) For循环n-1次for(int i2;ilen;i) ① 定义Node *node并且将data值赋值为当前的i ② 尾插法将node插入链表 \2. 执行search函数 (1) 执行while循环直到第k个结点while (head-data ! k) ① head head-next; (2) 返回第k个结点Return head \3. 利用while循环对jump和delete重复操作同时利用count记录出列次数 3.1 执行Jump函数 (1) int count0;利用count计数记录报数 (2) While循环直到countm-1 ① Count代表计数加1 ② Printf执行报数 ③ 让head指向下一位结点 \1) 如果head此时已经指向尾结点则while循环不断headhead-pre直到head再次指向链表第一个节点 \2) 如果head不指向尾结点则headhead-next;即可 (3) 返回结点Return head 3.2执行Delete语句 (4) Node *temphead; (5) 执行printf声明这个节点要被删除分三种情况讨论 ① 对于删除头节点(temp-pre NULL)直接 headhead-next;然后temp-nextNULLhead-preNULL;free(temp); return head; ② 对于删除尾结点if(temp-next NULL) 利用while循环headhead-pre;使得head跳到链表第一个然后执行删除原尾结点temp-pre-nextNULL;temp-preNULL;free(temp); ③ 对于删除中间结点headhead-next; temp-pre-nexttemp-next; temp-next-pretemp-pre; free(temp); 测试样例 具体代码 #includestdio.h **#includestdlib.h****#includemath.h****int delTime0;****typedef struct Node****{** **int data;** **struct Node \*pre;** **struct Node \*next;****}Node;****Node\* CreatNode(int data)//****新建结点并赋值** **{** **Node \*node(Node\*)malloc(sizeof(Node));** **node-datadata;** **node-preNULL;** **node-nextNULL;** **return node;****}****Node\* CreatList(int len)****{** **int num1;** **Node \*head CreatNode(1);** **Node \*tailhead;** **for(int i2;ilen;i)** **{** **Node \*nodeCreatNode(i);** **tail-nextnode;** **node-pretail;** **tailtail-next;** **}** **tail-nextNULL;** **return head;****}****Node\* Delete(Node \*head)//****删除当前的并且返回下一个节点进行下一轮报数** **{** **Node \*temphead;** **delTime;//****用以判断是否到删除的数** **printf(****本轮报数正好出列第%d****次执行删除编号为%d\n,delTime,temp-data);** **if(temp-pre NULL)//****对于删除头节点** **{** **headhead-next;** **temp-nextNULL;** **head-preNULL;** **free(temp);** **return head;** **}** **/\*****判断是否是尾节点\*/** **else if(temp-next NULL)//****对于删除尾结点** **{** **while(head-pre!NULL)** **headhead-pre;//****删除后head****跳到当前链表第一个** **temp-pre-nextNULL;** **temp-preNULL;** **free(temp);** **return head;** **}** **else//****删除中间结点** **{** **headhead-next;** **temp-pre-nexttemp-next;** **temp-next-pretemp-pre;** **free(temp);** **return head;** **}** **}** **Node \*Search(Node \*head, int k) { //****从Head****开始寻找第P****个节点** **while (head-data ! k) {** **head head-next;** **}** **return head;****}****Node \*Jump(Node \*head, int m)//****将head****前m-1****次正常报数然后返回第m****次** **{** **int count0;** **while(count!m-1)//****前m-1****个人都能正常报数** **{** **count;** **printf(****报数为-%d,****编号data****为-%d\n,count,head-data);//****报数** **if(head-nextNULL)** **{** **while(head-pre!NULL)** **headhead-pre;** **}//****换行** **else** **headhead-next;** **}** **return head;** **}****int main()//****已知n****个人围坐在一张圆桌周围。从编号为k****的人开始报数数到m****的那个人出列他的下一个人又从1****开始报数数到m****的那个人又出列依此规律重复下去直到圆桌周围的人全部出列。(****摘自百度百科)****{** **int n,k,m;** **int count0;** **printf(****按照n,k,m\n);** **while(scanf(%d,%d,%d,n,k,m)!3)** **{** **}** **Node \*headCreatList(n);** **headSearch(head,k);** **while(count!n-1)//****执行n-1****次出列来完成剩下最后一个人** **{** **count;** **headJump(head,m);//****将head****前m-1****次正常报数然后返回第m****次** **headDelete(head);//****删除当前的并且返回下一个节点进行下一轮报数** **}** **printf(****最后剩下的是编号为%d\n,head-data);****}**
