如何做好网站关键词布局,做网站推广方法有哪些,免费一键生成短链接,南沙网站建设循环链表介绍
先不急着看约瑟夫问题是什么#xff0c;先了解循环链表的结构#xff0c;那什么是循环链表#xff1f;
循环#xff0c;顾名思义#xff0c;从链表中第一个节点出发#xff0c;还会遇到第一个节点#xff0c;形成循环的一环。也就是说链表中最后一个节点…循环链表介绍
先不急着看约瑟夫问题是什么先了解循环链表的结构那什么是循环链表
循环顾名思义从链表中第一个节点出发还会遇到第一个节点形成循环的一环。也就是说链表中最后一个节点的下一个节点是第一个节点但是头节点也是一个节点所以最后一个节点的下一个节点应该是头节点才对。
如下图有两种情况 其中更大的长方形是节点的数据域更小的长方形是节点的指针域指向链表中的下一个节点。
循环链表的代码实现
因为解决约瑟夫问题只需要初始化、插入、打印功能所以别的功能就没实现。
节点定义
首先循环链表和普通链表节点的结构体定义一模一样那就写出来吧。 typedef struct _LoopLinkList //循环链表
{int date;struct _LoopLinkList* next;
}LinkNode,LinkList; 循环链表的初始化
初始化循环链表其中函数的参数是一个指向头节点的指针如图所示 两个箭头有些重叠了不过无伤大雅。
函数参数中的取地址符 是引用的意思为C特有的相当于就在使用这个一级指针 L 无需使用二级指针来接收这个一级指针 L 的地址如果去掉这个 会发生什么事呢那就是 L 这个指针所指向的地址无法改变但是可以改变所指向的变量的值。 bool initLinkList(LinkList *L)
{L new LinkNode; //为头结点申请空间if (!L) return false; // L为空指针,生成头结点失败L-next L; //头结点指向自己L-date -1;return true;
} 如果上面那段话不太明白可以先跳过等写完所有代码然后把初始化函数参数中的 去掉在 IDE 中调试一下即可得出答案。
循环链表的插入尾插法
其中函数的参数节点指针 node 指向新加节点。 bool InsertBack(LinkList* L, LinkNode* node)
{if (!L || !node) return false; //如果链表头结点未创建或者传入的结点指针指向空//分两种情况,一是链表为空,只有头结点存在if (L-next L){node-next L;L-next node;}else{LinkNode* p L;while (p-next ! L){p p-next;} //找到最后一个节点p-next node;node-next L;}return true;
} 循环链表的打印
从头节点开始打印直到又为头节点。 bool LinkPrint(LinkList* L)
{if (!L) return false;LinkNode* p L;p L -next;while (p ! L){printf(%d , p-date);p p-next;}return true;
}约瑟夫问题
解决了循环链表就开始约瑟夫问题了哈哈这故事有很多的分支我之前听过的不是下面这种。 据说著名犹太历史学家Josephus有过以下的故事在罗马人占领乔塔帕特后39 个犹太人与Josephus及他的朋友躲到一个洞中39个犹太人决定宁愿死也不要被敌人抓到于是决定了一个自杀方式41个人排成一个圆圈由第1个人开始报数每报数到第3人该人就必须自杀然后再由下一个重新报数直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始越过k-2个人因为第一个人已经被越过并杀掉第k个人。接着再越过k-1个人并杀掉第k个人。这个过程沿着圆圈一直进行直到最终只剩下一个人留下这个人就可以继续活着。问题是给定了和一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从他将朋友与自己安排在第16个与第31个位置于是逃过了这场死亡游戏。 ——摘自约瑟夫问题_百度百科 不过看完这个故事应该大概了解了约瑟夫问题这个问题可以用循环链表解决每一个人都是链表中一个节点只要某个节点报数报到出圈的那个号码就把这个节点从链表中删除。
由于原问题的人数实在太多我这里就简化一下一共 10 人报数报到 9 的人出圈并且要求求出第五轮出圈的号码还有最后一个出圈的人的号码所以添加了两个整型变量 loops、num来记录。
首先在进入这个函数之前已经把 10 个节点插入了链表第 n 个节点的值为 n 例如第一个节点的数据域为 1 。
代码实现
其中函数参数 interval 为间隔也就是出圈的号码 9 。 bool Joseph(LinkList* L,int interval)
{if ( !L || L-next L) return false; // 头节点未初始化或者是空链表if (interval 1) return false; //报数的间隔也不能小于 1 1 的话还能玩也就是一报数就死LinkNode* p L , *q NULL ; // q 指向要删除的节点 p 指向要删除的节点的前一个节点int loops 0 , num 0 ; //loops表示进行到第几轮num保存着出圈的人的号码int j 1;while (L-next ! L) //不为空链表{while ( j interval ) //一直报数除非j等于出圈的数-1这时候指针p就指向了要删除的节点的前一个节点{if (p-next ! L){j;} p p-next;}if (p-next L) //如果p指向最后一个节点那肯定不能删除头节点应该删除第一个节点所以p赋值为头节点{p L;}//删除q p-next;num q-date;p-next q-next;delete q;j 1;loops;cout endl 这是第loops轮: ;LinkPrint(L);if (loops 5){printf(\n第5轮出圈的是:%d, num);}}printf(最后一个出圈的是:%d\n, num);return true;
} 可能有人会想为什么其中循环的条件不是 i j 呢因为在单向链表中你删除一个节点前必须要让删除节点的上一个节点的next 指针指向删除节点的下一个节点。
所以指向要删除的节点的上一个节点就方便很多了
如下图
完整代码以及运行结果 #define _CRT_SECURE_NO_WARNINGS 1#include iostreamusing namespace std;
//结点结构体
typedef struct _LoopLinkList
{int date;struct _LoopLinkList* next;
}LinkNode,LinkList;//初始化
bool initLinkList(LinkList* L)
{ L new LinkNode;if (!L) return false; L-next L; //指向自己L-date -1;return true;
}//尾插法
bool InsertBack(LinkList* L, LinkNode* node)
{if (!L || !node) return false; if (L-next L) //链表为空,只有头结点{node-next L;L-next node;}else{LinkNode* p L;while (p-next ! L){p p-next;}p-next node;node-next L;}return true;
}//打印
bool LinkPrint(LinkList* L)
{if (!L) return false;LinkNode* p L;p L -next;while (p ! L){printf(%d , p-date);p p-next;}return true;
}//解决joseph问题
bool Joseph(LinkList* L, int interval)
{if (!L || L-next L) return false; // 头节点未初始化或者为空链表if (interval 1) return false; //报数的间隔LinkNode* p L, * q NULL; int loops 0, num 0; //loops表示进行到第几轮num保存着最后一个出圈的人的号码int j 1;while (L-next ! L) {while (j interval) {if (p-next ! L){j;}p p-next;}if (p-next L) {p L;}//此时 p 指向要删除节点的前一个节点不为最后一个节点q p-next;num q-date;p-next q-next;delete q;j 1;loops;cout endl 这是第 loops 轮:;LinkPrint(L);if (loops 5){printf(\n第5轮出圈的是:%d, num);}}printf(最后一个出圈的是:%d\n, num);return true;
}
int main(void)
{LinkList* L NULL ;LinkNode* e NULL;//1.初始化循环链表initLinkList(L);//2.尾插循环链表for (int i 1; i 10; i){e new LinkNode;e-date i;e-next NULL;InsertBack(L, e);}//3.打印链表LinkPrint(L);Joseph(L, 9);return 0;
} ---------------------------------------------------------------------------------------------------------------------------------
