muyu0098 发表于 2013-6-28 23:19:56

约瑟夫问题中,循环单链表是不是没有头结点?

初学者,如果问题小白请勿怪
根据书上的定义(书是清华版的严蔚敏的数据结构c语言版),循环链表也是有头结点的,例如下面的含头结点和另外5个结点的循环链表:
0   1   2   3   4   5
这里我用0代表头结点。如果我理解的没有错,5这个结点的next是指向结点0的


如果求解约瑟夫问题,假设队伍长度不是41人是5个人,解决思想是从第一个元素(1)开始每隔2个后去掉一个元素,循环着来。
比如:
第一次报数1,2,3,所以去掉3;
第二次从4开始,那么应该是4,5,1,也就是说5之后,循环到头部,指向1

但根据书上的定义,5之后是指向5头结点0的,这样的话。。。。虽然理论上每次循环到头结点可以多用个next,但感觉好麻烦。。。。


小甲鱼的视频上好像回避了这个问题,他建立的链表,第一个结点的data就是1,代表着第一个人,一共41个结点,第41个结点(人)的next指向结点1
整个链表是41个元素,而非(头结点+41)=42个元素。不仅约瑟夫问题,基本上视频里的所有的和循环单链表相关的问题都貌似没有头结点的存在————因为头结点的存在的确是使问题复杂化了

既然除此,为什么循环单链表要有一个头结点呢????

请高手大牛解惑

lsh華 发表于 2013-6-29 00:50:42

无回帖,不论坛,这才是人道。

muyu0098 发表于 2013-7-1 00:48:14

:(:(:(怎么没人回呢?高手呢?

日出日落 发表于 2013-7-1 08:58:00

发现好多东东要学哦..

佐少love 发表于 2013-8-28 15:48:01

个人观点头结点:
   1、只是人为定义的,表示这个地方是头,你可以随便定义
   2、在创建完循环链表的时候知道头在哪,并把头和尾连起来
   3、再循环链表的时候用头结点来判读是否循环完毕
头结点:如果循环链表没有头结点你怎么知道哪个地方是头?哪个地方是尾?
自己的理解可能说的也不是很对

junpeng003 发表于 2013-9-11 20:47:48

楼主加油,鱼C加油

血色熊猫 发表于 2013-9-23 18:29:27

建立链表的时候是有头结点的,但是链表的最后一个节点是连接到头结点下一个节点(就是第一个数据节点),此时链表的循环部分是没有头结点的。
页: [1]
查看完整版本: 约瑟夫问题中,循环单链表是不是没有头结点?