首页 > 代码库 > 经典算法题每日演练——第二十一题 十字链表
经典算法题每日演练——第二十一题 十字链表
原文:经典算法题每日演练——第二十一题 十字链表
View Code
上一篇我们看了矩阵的顺序存储，这篇我们再看看一种链式存储方法“十字链表”，当然目的都是一样，压缩空间。
一：概念
既然要用链表节点来模拟矩阵中的非零元素，肯定需要如下5个元素(row,col,val,down,right)，其中：
row:矩阵中的行。
col:矩阵中的列。
val:矩阵中的值。
right:指向右侧的一个非零元素。
down：指向下侧的一个非零元素。
现在我们知道单个节点该如何表示了，那么矩阵中同行的非零元素的表示不就是一个单链表吗？比如如下：
那么进一步来说一个多行的非零元素的表示不就是多个单链表吗，是的，这里我把单链表做成循环链表，我们来看看如何用十字链表
来表示稀疏矩阵。
从上面的十字链表中要注意两个问题：
第一：这里有一个填充色的节点，是十字链表中的总结点，它是记录该矩阵中的（row,col,value）和一个指向下一个头节点的next指针。
第二：每个链表都有一个头指针，总结点用next指针将它们贯穿起来。
二：操作
1：数据结构
刚才也说了，十字链表的总结点有一个next指针，而其他非零节点没有，所以为了方便，我们用一个Unit类包装起来。
1 #region 单一节点 2 /// <summary> 3 /// 单一节点 4 /// </summary> 5 public class Node 6 { 7 //行号 8 public int rows; 9 10 //列号11 public int cols;12 13 //向下的指针域14 public Node down;15 16 //向右的指针域17 public Node right;18 19 //单元值（头指针的next和val）20 public Unit unit;21 }22 #endregion23 24 #region 统一“表头节点”和“非零节点”25 /// <summary>26 /// 统一“表头节点”和“非零节点”27 /// </summary>28 public class Unit29 {30 //表头节点的next域31 public Node next;32 33 //非零元素的值34 public int value;35 }36 #endregion
2：初始化
这一步，我们初始化总结点，并且用next指针将每个单链表的头节点链接成单链表（也就是上图中十字链表的第一行）
1 #region 十字链表中的“行数，列数，非零元素个数” 2 /// <summary> 3 /// 十字链表中的“行数，列数，非零元素个数” 4 /// </summary> 5 /// <param name="rows"></param> 6 /// <param name="cols"></param> 7 /// <param name="count"></param> 8 public void Init(int rows, int cols, int count) 9 {10 var len = Math.Max(rows, cols) + 1;11 12 //从下标1开始算起13 nodes = new Node[len];14 15 //十字链表的总头节点16 nodes[0] = new Node();17 18 nodes[0].rows = rows;19 nodes[0].cols = cols;20 nodes[0].unit = new Unit()21 {22 value =http://www.mamicode.com/ count,23 next = null,24 };25 26 //down和right都指向自身27 nodes[0].right = nodes[0];28 nodes[0].down = nodes[0];29 30 var temp = nodes[0];31 32 //初始化多条链表的头结点33 for (int i = 1; i < len; i++)34 {35 nodes[i] = new Node();36 37 nodes[i].rows = 0;38 nodes[i].cols = 0;39 nodes[i].unit = new Unit()40 {41 value = http://www.mamicode.com/0,42 next = temp.unit.next43 };44 45 //给上一个节点的next域赋值46 temp.unit.next = nodes[i];47 48 //将当前节点作为下一次循环的上一个节点49 temp = nodes[i];50 51 nodes[i].right = nodes[i];52 nodes[i].down = nodes[i];53 }54 }55 #endregion
3：插入节点
根据插入节点的row和col将节点插入到十字链表中指定的位置即可。
1 #region 插入十字链表中 2 /// <summary> 3 /// 插入十字链表中 4 /// </summary> 5 /// <param name="nums">矩阵</param> 6 /// <param name="rows">矩阵的行数</param> 7 /// <param name="cols">矩阵的列数</param> 8 /// <param name="count">非0元素个数</param> 9 /// <returns></returns>10 public Node[] Insert(int[,] nums, int rows, int cols, int count)11 {12 //初始化操作13 Init(rows, cols, count);14 15 //插入操作16 for (int i = 0; i < rows; i++)17 {18 for (int j = 0; j < cols; j++)19 {20 //直插入"非0元素"21 if (nums[i, j] != 0)22 {23 var node = new Node();24 25 node.rows = i + 1;26 node.cols = j + 1;27 node.unit = new Unit()28 {29 value =http://www.mamicode.com/ nums[i, j]30 };31 node.right = node;32 node.down = node;33 34 InsertNode(node);35 }36 }37 }38 39 return nodes;40 }41 #endregion
4：打印链表
我们只要遍历每行链表的right指针即可。
1 #region 打印十字链表 2 /// <summary> 3 /// 打印十字链表 4 /// </summary> 5 /// <param name="nodes"></param> 6 public void Print(Node[] nodes) 7 { 8 var head = nodes[0]; 9 10 //遍历每一行的right11 for (int i = 1; i < head.rows + 1; i++)12 {13 var p = nodes[i];14 15 while (p.right != nodes[i])16 {17 Console.WriteLine("({0},{1})\tval => {2}",18 p.right.rows,19 p.right.cols,20 p.right.unit.value);21 22 //指向下一个节点23 p = p.right;24 }25 }26 }27 #endregion
总的代码：
View Code 
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Diagnostics; 6 using System.Threading; 7 using System.IO; 8 9 namespace ConsoleApplication2 10 { 11 public class Program 12 { 13 public static void Main() 14 { 15 Crosslist crosslist = new Crosslist(); 16 17 int[,] nums = { 18 {2,0,4 }, 19 {0,3,0 }, 20 {0,0,9 } 21 }; 22 23 var nodes = crosslist.Insert(nums, 3, 3, 4); 24 25 crosslist.Print(nodes); 26 27 Console.Read(); 28 } 29 } 30 31 /// <summary> 32 /// 十字链表 33 /// </summary> 34 public class Crosslist 35 { 36 #region 单一节点 37 /// <summary> 38 /// 单一节点 39 /// </summary> 40 public class Node 41 { 42 //行号 43 public int rows; 44 45 //列号 46 public int cols; 47 48 //向下的指针域 49 public Node down; 50 51 //向右的指针域 52 public Node right; 53 54 //单元值（头指针的next和val） 55 public Unit unit; 56 } 57 #endregion 58 59 #region 统一“表头节点”和“非零节点” 60 /// <summary> 61 /// 统一“表头节点”和“非零节点” 62 /// </summary> 63 public class Unit 64 { 65 //表头节点的next域 66 public Node next; 67 68 //非零元素的值 69 public int value; 70 } 71 #endregion 72 73 Node[] nodes; 74 75 #region 十字链表中的“行数，列数，非零元素个数” 76 /// <summary> 77 /// 十字链表中的“行数，列数，非零元素个数” 78 /// </summary> 79 /// <param name="rows"></param> 80 /// <param name="cols"></param> 81 /// <param name="count"></param> 82 public void Init(int rows, int cols, int count) 83 { 84 var len = Math.Max(rows, cols) + 1; 85 86 //从下标1开始算起 87 nodes = new Node[len]; 88 89 //十字链表的总头节点 90 nodes[0] = new Node(); 91 92 nodes[0].rows = rows; 93 nodes[0].cols = cols; 94 nodes[0].unit = new Unit() 95 { 96 value =http://www.mamicode.com/ count, 97 next = null, 98 }; 99 100 //down和right都指向自身101 nodes[0].right = nodes[0];102 nodes[0].down = nodes[0];103 104 var temp = nodes[0];105 106 //初始化多条链表的头结点107 for (int i = 1; i < len; i++)108 {109 nodes[i] = new Node();110 111 nodes[i].rows = 0;112 nodes[i].cols = 0;113 nodes[i].unit = new Unit()114 {115 value = http://www.mamicode.com/0,116 next = temp.unit.next117 };118 119 //给上一个节点的next域赋值120 temp.unit.next = nodes[i];121 122 //将当前节点作为下一次循环的上一个节点123 temp = nodes[i];124 125 nodes[i].right = nodes[i];126 nodes[i].down = nodes[i];127 }128 }129 #endregion130 131 #region 在指定的“行，列”上插入节点132 /// <summary>133 /// 在指定的“行，列”上插入节点134 /// </summary>135 /// <param name="node"></param>136 /// <returns></returns>137 public void InsertNode(Node node)138 {139 //先定位行140 Node pnode = nodes[node.rows];141 142 //在指定的“行”中找，一直找到该行最后一个节点（right指针指向自己的为止）143 while (pnode.right != nodes[node.rows] && pnode.right.cols < node.cols)144 pnode = pnode.right;145 146 //将最后一个节点的right指向插入节点的right，以此达到是循环链表147 node.right = pnode.right;148 149 //将插入节点给最后一个节点的right指针上150 pnode.right = node;151 152 //再定位列153 pnode = nodes[node.cols];154 155 //同理156 while (pnode.down != nodes[node.cols] && pnode.down.rows < node.rows)157 {158 pnode = pnode.down;159 }160 161 node.down = pnode.down;162 pnode.down = node;163 }164 #endregion165 166 #region 插入十字链表中167 /// <summary>168 /// 插入十字链表中169 /// </summary>170 /// <param name="nums">矩阵</param>171 /// <param name="rows">矩阵的行数</param>172 /// <param name="cols">矩阵的列数</param>173 /// <param name="count">非0元素个数</param>174 /// <returns></returns>175 public Node[] Insert(int[,] nums, int rows, int cols, int count)176 {177 //初始化操作178 Init(rows, cols, count);179 180 //插入操作181 for (int i = 0; i < rows; i++)182 {183 for (int j = 0; j < cols; j++)184 {185 //直插入"非0元素"186 if (nums[i, j] != 0)187 {188 var node = new Node();189 190 node.rows = i + 1;191 node.cols = j + 1;192 node.unit = new Unit()193 {194 value =http://www.mamicode.com/ nums[i, j]195 };196 node.right = node;197 node.down = node;198 199 InsertNode(node);200 }201 }202 }203 204 return nodes;205 }206 #endregion207 208 #region 打印十字链表209 /// <summary>210 /// 打印十字链表211 /// </summary>212 /// <param name="nodes"></param>213 public void Print(Node[] nodes)214 {215 var head = nodes[0];216 217 //遍历每一行的right218 for (int i = 1; i < head.rows + 1; i++)219 {220 var p = nodes[i];221 222 while (p.right != nodes[i])223 {224 Console.WriteLine("({0},{1})\tval => {2}",225 p.right.rows,226 p.right.cols,227 p.right.unit.value);228 229 //指向下一个节点230 p = p.right;231 }232 }233 }234 #endregion235 }236 }
经典算法题每日演练——第二十一题 十字链表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。