循环链表的存在很难想象他的应用范围到底是哪里,本文主要介绍的是通过循环链表处理解决约瑟夫问题,让大家更深刻的理解循环链表的使用和应用场景。
例题:n 个人围成一个圆圈,首先第 1 个人从 1 开始一个人一个人顺时针报数,报到第 m 个人,令其出列。然后再从下一 个人开始从 1 顺时针报数,报到第 m 个人,再令其出列,…,如此下去,求出列顺序。
假设: m = 8,n=3
最后我们得出的结果便是 : 3 6 1 5 2 8 4 7
很明显,如果用循环链表来处理这个问题,将非常简单。大致的思路如下:
- 生成一个有 8 个数据的循环链表
- 无限循环遍历链表
- 无限循环中增加for循环,每次循环 n – 1 次,每循环一次移动一次游标,将for循环完成后游标指向的数据删除
- 依次执行,直到链表为空为止
【实现代码】
注意:需要用到上一篇文章我们编写的 CircleList.h 和 CircleList.c 文件。
#include <stdio.h> #include <stdlib.h> #include <string.h> #include "circlelist.h" //定义结构体,存储数据 typedef struct tag_value { CircleListNode header; int v; }Value; void joseph_question() { int i; //定义结构体数组 Value val[8]; //创建循环链表 CircleList* list = CircleList_Create(); //判断链表是否创建成功 if (list == NULL) { printf("链表创建失败\n"); return; } //初始化结构体数组 for (i = 0; i < sizeof(val) / sizeof(Value); ++i) { val[i].v = i+1; //往循环链表中插入数据 CircleList_Insert(list, (CircleListNode*)&val[i], i); } //遍历循环链表 printf("插入数据:\n"); for (i = 0; i < CircleList_Length(list); ++i) { //获取游标指向的元素然后下移 Value* pVal = (Value*)CircleList_Get(list, i); printf("%d\t", pVal->v); } //重置游标 CircleList_Reset(list); //循环删除指定位置的元素 printf("\n\n依次删除的节点为:\n"); while (CircleList_Length(list) > 0) { //定义结构体指针变量,指向符合条件的元素 Value* pVal = NULL; //根据条件查找指定位置的元素 for (i = 0; i < 3-1; ++i) //3为案例中的m { //向后移动游标 pVal = (Value*)CircleList_Next(list); } //保存符合条件的节点 pVal = (Value*)CircleList_Current(list); //打印节点信息 printf("%d\t", pVal->v); //从链表中删除符合条件的节点 CircleList_DeleteNode(list, (CircleListNode*)pVal); } printf("\n"); //销毁循环链表 CircleList_Destroy(list); } void main() { joseph_question(); }