经典算法题每日演练——第二十一题 十字链表
by 一线码农
at 2013-04-02 13:44:00
original http://www.cnblogs.com/huangxincheng/archive/2013/04/02/2995343.html
上一篇我们看了矩阵的顺序存储，这篇我们再看看一种链式存储方法“十字链表”，当然目的都是一样，压缩空间。
一：概念
既然要用链表节点来模拟矩阵中的非零元素，肯定需要如下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 #endregion
23
24 #region 统一“表头节点”和“非零节点”
25 /// <summary>
26 /// 统一“表头节点”和“非零节点”
27 /// </summary>
28 public class Unit
29 {
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 = 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 = 0,
42 next = temp.unit.next
43 };
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 = 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 //遍历每一行的right
11 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
总的代码：
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 = 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 = 0,
116 next = temp.unit.next
117 };
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 #endregion
130
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 #endregion
165
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 = 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 #endregion
207
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 //遍历每一行的right
218 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 #endregion
235 }
236 }
