苏州网站建设推广案例,个人网站备案容易吗,企业邮箱格式范本,辽阳做网站公司前言 哈喽#xff0c;宝子们#xff01;本期为大家带来一道C语言循环链表的经典算法题#xff08;约瑟夫环#xff09;。 目录 1.什么是约瑟夫环2.解决方案思路3.创建链表头结点4.创建循环链表5.删除链表6.完整代码实现 1.什么是约瑟夫环 据说著名历史学家Josephus有过以下… 前言 哈喽宝子们本期为大家带来一道C语言循环链表的经典算法题约瑟夫环。 目录 1.什么是约瑟夫环2.解决方案思路3.创建链表头结点4.创建循环链表5.删除链表6.完整代码实现 1.什么是约瑟夫环 据说著名历史学家Josephus有过以下的故事在罗马人占领乔塔帕特后39个犹太人与Josephus及他的朋友躲到一个洞中39个犹太人决定宁愿死也不要被人抓到于是决定了一个自杀方式41个人拼成一个圆圈由第一个人开始报数每报数到第三人该人就必须自杀然后再由下一个重新报数直到所有人都自杀身亡为止。 然而Josephus和他的朋友并不想遵从Josephus要他的朋友先假装遵从他将朋友与自己安排在第16个与第31个位置于是逃过了这场死亡游戏。 这道题的原理也是一样的来看看这道题长什么样吧。 描述 编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数报到 m 的人离开。下一个人继续从 1 开始报数。 n - 1 轮结束以后只剩下一个人问最后留下的这个人编号是多少 示例1 输入5, 2 返回值3 说明 开始5个人 12345 从1开始报数1-12-2编号为2的人离开。 1345从3开始报数3-14-2编号为4的人离开。 135从5开始报数5-11-2编号为1的人离开。 35从3开始报数3-15-2编号为5的人离开。 最后留下人的编号是3。 2.解决方案思路 既然是循环的报数那我们就可以用我们所学过的单链表来解决这道题。 那假设我们有n个人就要创建n个节点,首先创建一个节点然后同时用两个指针指向这个节点这个节点既是头指针head也是尾指针ptail然后把这个创建的过程用一个函数封装起来调用函数来创建剩下的几个节点每次调用完就让ptail的next指针指向我们新创建的节点然后更新ptail指针的位置。此时我们的节点已经全部创建完成了但是最重要的一步就是要让我们的链表形成一个环最后让尾指针的next指针指向我们的head接着就是报数的实现需要有循环报数要用一个计数器count来记录当count等于m的时候就要删除当前这个节点然后更改头指针和尾指针的位置最后直到头指针指向自己此时指针里val的值就是最终留下来的值。 3.创建链表头结点
//创建头链表
ListNode* ListBuyNode(int x)
{ListNode* newhead (ListNode*)malloc(sizeof(ListNode));//动态申请内存失败if (newhead NULL){exit(1);}//申请成功newhead-val x;newhead-next NULL;return newhead;
}4.创建循环链表
//创建带环链表
ListNode* CreateCircle(int n)
{//先创建第一个节点ListNode* head ListBuyNode(1);ListNode* ptail head;for (int i 2; i n; i){//用尾插的方式把节点连接起来ptail-next ListBuyNode(i);ptail ptail-next;//更新尾节点位置}//收尾相连链表成环ptail-next head;return ptail;
}5.删除链表
//当链表中只有一个节点的情况就是循环的终止条件
while (pcur-next ! pcur)
{if (count m){//销毁pcur节点prev-next pcur-next;free(pcur);pcur prev-next;count 1;}else{//此时不需要销毁节点prev pcur;pcur pcur-next;count;}
}6.完整代码实现
//定义节点
struct ListNode
{int val;struct ListNode* next;
};
typedef struct ListNode ListNode;//类型重定义
//创建头链表
ListNode* ListBuyNode(int x)
{ListNode* newhead (ListNode*)malloc(sizeof(ListNode));if (newhead NULL){exit(1);}newhead-val x;newhead-next NULL;return newhead;
}
//创建带环链表
ListNode* CreateCircle(int n)
{//先创建第一个节点ListNode* head ListBuyNode(1);ListNode* ptail head;for (int i 2; i n; i){ptail-next ListBuyNode(i);ptail ptail-next;}//收尾相连链表成环ptail-next head;return ptail;
}
int ysf(int n, int m)
{//1.根据n创建带环链表ListNode* prev CreateCircle(n);//尾指针ListNode* pcur prev-next;//头指针int count 1;//当链表中只有一个节点的情况就是循环的终止条件while (pcur-next ! pcur){if (count m){//销毁pcur节点prev-next pcur-next;free(pcur);pcur prev-next;count 1;}else{//此时不需要销毁节点prev pcur;pcur pcur-next;count;}}//此时剩下的最后一个节点里的值就是要返回的值return prev-val;
}
int main()
{//测试用例int winysf(5, 2);printf(%d, win);return 0;
}如果对你有所帮助的话别忘了点赞关注哟❤️!
