赞
踩
单链表有一个缺点,无法快速访问前驱结点,当查找到某一个元素时,如果想查找其前驱结点,需要再次从头遍历。因此,有人提出在结点中再添加一个指向前驱的指针,如此便构成了双向链表。
上图为一个双向链表,表中第一个结点的前驱指针pre指向了NULL,最后一个结点的后继结点next指向了NULL。在双向链表中,通过一个结点可以找到它的后继结点, 也可以找到它的前驱结点。
双向链表在结构和算法描述上与单链表相同,只是某些算法实现比单链表复杂一些,例如,双向链表的插入。
循环链表是首尾相接的一种链表,它尾结点的后继指针又指向链表的第一个结点,这样形成了一个环。对于循环链表,从表中的任何一个结点触发,能找到其它所有的结点。
循环链表在实现上大多操作都与单链表相同,如创建、查找等,这些部分在单链表与双向链表中都有详细的讲解及代码实现,此处就不再重复,接下来主要讲解其插入与删除元素时与单链表的异同。
在插入新元素时,先判断链表是否为空,如果为空,则将元素插入到头结点后,然后将其指针指向自身;如果不为空,根据插入的位置作出相应操作。
约瑟夫问题是循环链表的一个典型应用,其描述如下:m个人围成了一圈,从其中任一个人开始,按顺时针顺序使所有人依次从1开始报数,报到n的人出列;然后使n之后的人接着从1开始报数,再次使报到n的人出列……如此下去,求算出列的顺序,及最后留下来的人的编号。
将m与n设定为具体数字,使m=8,n=3模拟约瑟夫问题。
关注微信公众号“嵌入式软件开发学习圈”获取更多嵌入式学习资讯
如需获取其他学习资料,直接在微信公众号留言
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。