数据结构（2）循环链表与双链表

了解循环链表，双向链表（这一部分真的不想贴代码了，跟单链表感觉没啥区别，都是操作指针。

没啥特别的，单链表尾指针指向头节点。

插入：

和单链表一样，需要辅助链表定位插入的前后结点，操作基本与单链表相同，只是多调整一个前指针而已。

删除：

参考单链表删除，调整结点指针，释放目标空间。

下面玩个有意思的：约瑟夫和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，自杀方法是，大家轮流报数，报到7的人自杀，直到所有人死去。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。

事实上，我们可以通过循环链表解决这个问题。

完整源码：

#include <iostream>

#include <stdio.h> 

#include <stdlib.h>

using namespace std;

typedef struct node {

 int data;

 node* next;

}node, * linklist;

//创建循环链表

linklist create() {

 node* p;

 p = new node;

 p->next = NULL;

 p->data = 41;

 for (int i = 1; i < 41; i++) {

  node* q = new node;

  q->next = p->next;

  q->data = 41 - i;

  p->next = q;

  if (i == 1) {

   q->next = p;

  }

 }

 return p;

}

int main() {

 node* joseph = new node;

 joseph = create();

 node* t = joseph;

 node* tmp = joseph;

 node* tmp2;

 int num = 0;

 int count = 0;

 //开始递进

 for (int i = 0; ; i++) {

  tmp2 = tmp;

  tmp = tmp->next;

  num = num + 1;

  //到7删除

  if (num == 7) {

   tmp2->next = tmp->next;

   free(tmp);

   tmp = tmp2->next;

   num = 1;

   count++;

  }

  //剩两人跳出

  if (count == 39) {

   break;

  }

 }
 
 //结果输出
 cout << tmp->data << " " << tmp->next->data;

} 

备注：

上面的代码可能并不是很简单，但符合我的编写习惯，欢迎大家给我提意见。

约瑟夫环事实上可以使用递归求解，当然理解难度较大，有兴趣的同学可以查一下。