数据结构基础之双链表与循环链表各类操作、思想与实现

本是古典何须时尚 2022-08-05 13:07 38阅读 0赞

双链表 相较于 单链表 其结点多了一个前向指针域，首尾结点互连；

循环链表 相较于 单链表 其尾结点多了一个指向头结点的指针；

双链表常见操作  
其操作 如 创建，插入，删除，排序，输出，测长，逆置 除添加一个前向指针域外与单链表基本相似 ；  
循环链表常见操作  
解决实际问题实例，即，约瑟夫问题、魔术师发牌问题、拉丁方阵。

单链表、双链表、循环链表代码实现，可依次参考：

http://blog.csdn.net/cfan0801/article/details/7350537  
http://blog.csdn.net/cfan0801/article/details/7350541  
http://blog.csdn.net/cfan0801/article/details/7350890  
  
约瑟夫问题：  
已知N个人（以编号1，2，3...N分别表示）围坐在一张圆桌周围。从编号为1的人开始报数，数到M的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。  
约瑟夫 代码实现 ，可参考：  
http://blog.csdn.net/jw903/article/details/38962587  
魔术师发牌问题

魔术师手中有A、2、3……J、Q、K十三张黑桃扑克牌。在表演魔术前，魔术师已经将他们按照一定的顺序叠放好（有花色的一面朝下）。魔术表演过程为：一开始，魔术师数1，然后把最上面的那张牌翻过来，是黑桃A；然后将其放到桌面上；第二次,魔术师数1、2；将第一张牌放到这些牌的最下面，将第二张牌翻转过来，正好是黑桃2；第三次，魔术师数1、2、3；将第1、2张牌依次放到这些牌的最下面，将第三张牌翻过来正好是黑桃3；……直到将所有的牌都翻出来为止。问原来牌的顺序是如何的。  
魔术师发牌 代码实现 ，可参考：  
http://blog.csdn.net/u014236167/article/details/38304875  
拉丁方阵问题  
例如：构造 NXN 阶的拉丁方阵(2<=N<=9)，使方阵中的每一行和每一列中数字1到N只出现一次。如N=4时：  
　　1 2 3 4  
　　2 3 4 1  
　　3 4 1 2  
　　4 1 2 3  
　　\*问题分析与算法设计  
　　构造拉丁方阵的方法很多，这里给出最简单的一种方法。观察给出的例子，可以发现：若将每 一行中第一列的数字和最后一列的数字连起来构成一个环，则该环正好是由1到N顺序构成；对于第i行，这个环的开始数字为i。按照 此规律可以很容易的写出程序。下面给出构造6阶拉丁方阵的程序。  
拉丁方阵 代码实现 ，可参考：  
http://blog.csdn.net/u012411003/article/details/17229191