数据结构(2)循环链表与双链表

数据结构(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;

} 

备注:

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

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