约瑟夫循环链表程序框图_约瑟夫环c语言数组

目录

前言

一、用循环链表实现

二、用数组实现

三、用数组模拟链表实现

前言

题目描述：

编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。

下一个人继续从 1 开始报数。

n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

数据范围：​

进阶：空间复杂度 O(1)，时间复杂度 O(n)

示例 1：

输入：5,2    

返回值：3    

说明：

开始5个人 1，2，3，4，5 ，从1开始报数，1->1，2->2编号为2的人离开

1，3，4，5，从3开始报数，3->1，4->2编号为4的人离开

1，3，5，从5开始报数，5->1，1->2编号为1的人离开

3，5，从3开始报数，3->1，5->2编号为5的人离开

最后留下人的编号是3      

示例 2：

输入：1,1

返回值：1

一、用循环链表实现

typedef struct Node { int id; // 编号（从 1 开始） struct Node* next; }Node; int ysf(int n, int m) { // 采用尾插法构造编号为 1 ~ n 的循环链表 Node* phead = (Node*)malloc(sizeof(Node)); // 头指针 phead->id = 1; Node* tail = phead; // 尾指针 for (int i = 2; i <= n; ++i) { Node* newnode = (Node*)malloc(sizeof(Node)); newnode->id = i; newnode->next = NULL; tail->next = newnode; tail = newnode; } tail->next = phead; // 让最后一个节点的 next 域指向第一个节点 // 开始 Node* cur = phead; Node* prev = tail; int count = 1; // 计数器 while (cur != prev) { if (count == m) { prev->next = cur->next; free(cur); cur = prev->next; count = 1; // 重置为 1 } else { prev = cur; cur = cur->next; ++count; } } int ret = cur->id; free(cur); return ret; }

二、用数组实现

int ysf(int n, int m) { int* is_out = (int*)calloc(n, sizeof(int)); // 0 表示在圈内，1 则表示退出 int number = n; int count = 1; // 计数器 int i = 0; while (number > 1) { if (is_out[i] == 0) // 圈内的人报数 { if (count == m) { is_out[i] = 1; // 退出 --number; count = 1; // 重置为 1 } else { ++count; } } // 法一： ++i; if (i >= n) { i = 0; } // 法二： // i = (i + 1) % n; } for (i = 0; i < n; ++i) { if (is_out[i] == 0) { break; } } free(is_out); // 释放动态开辟的内存空间 return i + 1; // 返回编号 }

三、用数组模拟链表实现

int ysf(int n, int m) { int* next = (int*)calloc(n, sizeof(int)); for (int i = 0; i < n - 1; ++i) { next[i] = i + 1; } // next[n - 1] == 0 int cur = 0; int prev = n - 1; int count = 1; // 计数器 while (cur != prev) { if (count == m) { next[prev] = next[cur]; next[cur] = -1; // 退出 cur = next[prev]; count = 1; // 重置为 1 } else { prev = cur; cur = next[cur]; ++count; } } free(next); // 释放动态开辟的内存空间 return cur + 1; // 返回编号 }

创作不易，可以点点赞，如果能关注一下博主就更好了~ 

今天的文章
约瑟夫循环链表程序框图_约瑟夫环c语言数组分享到此就结束了，感谢您的阅读。