?

? ? ?上一篇我們看了矩陣的順序存儲，這篇我們再看看一種鏈?zhǔn)酱鎯Ψ椒ā笆宙湵怼?#xff0c;當(dāng)然目的都是一樣，壓縮空間。

一：概念

? ? 既然要用鏈表節(jié)點(diǎn)來模擬矩陣中的非零元素，肯定需要如下5個(gè)元素(row,col,val,down,right)，其中：

row:矩陣中的行。

col:矩陣中的列。

val:矩陣中的值。

right:指向右側(cè)的一個(gè)非零元素。

down：指向下側(cè)的一個(gè)非零元素。

現(xiàn)在我們知道單個(gè)節(jié)點(diǎn)該如何表示了，那么矩陣中同行的非零元素的表示不就是一個(gè)單鏈表嗎？比如如下：

那么進(jìn)一步來說一個(gè)多行的非零元素的表示不就是多個(gè)單鏈表嗎，是的，這里我把單鏈表做成循環(huán)鏈表，我們來看看如何用十字鏈表

來表示稀疏矩陣。

從上面的十字鏈表中要注意兩個(gè)問題：

第一：這里有一個(gè)填充色的節(jié)點(diǎn)，是十字鏈表中的總結(jié)點(diǎn)，它是記錄該矩陣中的（row,col,value）和一個(gè)指向下一個(gè)頭節(jié)點(diǎn)的next指針。

第二：每個(gè)鏈表都有一個(gè)頭指針，總結(jié)點(diǎn)用next指針將它們貫穿起來。

?

二：操作

1：數(shù)據(jù)結(jié)構(gòu)

? ?剛才也說了，十字鏈表的總結(jié)點(diǎn)有一個(gè)next指針，而其他非零節(jié)點(diǎn)沒有，所以為了方便，我們用一個(gè)Unit類包裝起來。

1 #region 單一節(jié)點(diǎn) 2 /// <summary> 3 /// 單一節(jié)點(diǎn) 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 統(tǒng)一“表頭節(jié)點(diǎn)”和“非零節(jié)點(diǎn)” 25 /// <summary> 26 /// 統(tǒng)一“表頭節(jié)點(diǎn)”和“非零節(jié)點(diǎn)” 27 /// </summary> 28 public class Unit 29 { 30 //表頭節(jié)點(diǎn)的next域 31 public Node next; 32 33 //非零元素的值 34 public int value; 35 } 36 #endregion

2：初始化

? ?這一步，我們初始化總結(jié)點(diǎn)，并且用next指針將每個(gè)單鏈表的頭節(jié)點(diǎn)鏈接成單鏈表（也就是上圖中十字鏈表的第一行）

1 #region 十字鏈表中的“行數(shù)，列數(shù)，非零元素個(gè)數(shù)” 2 /// <summary> 3 /// 十字鏈表中的“行數(shù)，列數(shù)，非零元素個(gè)數(shù)” 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 //從下標(biāo)1開始算起 13 nodes = new Node[len]; 14 15 //十字鏈表的總頭節(jié)點(diǎn) 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 //初始化多條鏈表的頭結(jié)點(diǎn) 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 //給上一個(gè)節(jié)點(diǎn)的next域賦值 46 temp.unit.next = nodes[i]; 47 48 //將當(dāng)前節(jié)點(diǎn)作為下一次循環(huán)的上一個(gè)節(jié)點(diǎn) 49 temp = nodes[i]; 50 51 nodes[i].right = nodes[i]; 52 nodes[i].down = nodes[i]; 53 } 54 } 55 #endregion

3：插入節(jié)點(diǎn)

? ? ?根據(jù)插入節(jié)點(diǎn)的row和col將節(jié)點(diǎn)插入到十字鏈表中指定的位置即可。

1 #region 插入十字鏈表中 2 /// <summary> 3 /// 插入十字鏈表中 4 /// </summary> 5 /// <param name="nums">矩陣</param> 6 /// <param name="rows">矩陣的行數(shù)</param> 7 /// <param name="cols">矩陣的列數(shù)</param> 8 /// <param name="count">非0元素個(gè)數(shù)</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 //指向下一個(gè)節(jié)點(diǎn) 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 單一節(jié)點(diǎn) 37 /// <summary> 38 /// 單一節(jié)點(diǎn) 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 統(tǒng)一“表頭節(jié)點(diǎn)”和“非零節(jié)點(diǎn)” 60 /// <summary> 61 /// 統(tǒng)一“表頭節(jié)點(diǎn)”和“非零節(jié)點(diǎn)” 62 /// </summary> 63 public class Unit 64 { 65 //表頭節(jié)點(diǎn)的next域 66 public Node next; 67 68 //非零元素的值 69 public int value; 70 } 71 #endregion 72 73 Node[] nodes; 74 75 #region 十字鏈表中的“行數(shù)，列數(shù)，非零元素個(gè)數(shù)” 76 /// <summary> 77 /// 十字鏈表中的“行數(shù)，列數(shù)，非零元素個(gè)數(shù)” 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 //從下標(biāo)1開始算起 87 nodes = new Node[len]; 88 89 //十字鏈表的總頭節(jié)點(diǎn) 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 //初始化多條鏈表的頭結(jié)點(diǎn) 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 //給上一個(gè)節(jié)點(diǎn)的next域賦值 120 temp.unit.next = nodes[i]; 121 122 //將當(dāng)前節(jié)點(diǎn)作為下一次循環(huán)的上一個(gè)節(jié)點(diǎn) 123 temp = nodes[i]; 124 125 nodes[i].right = nodes[i]; 126 nodes[i].down = nodes[i]; 127 } 128 } 129 #endregion 130 131 #region 在指定的“行，列”上插入節(jié)點(diǎn) 132 /// <summary> 133 /// 在指定的“行，列”上插入節(jié)點(diǎn) 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 //在指定的“行”中找，一直找到該行最后一個(gè)節(jié)點(diǎn)（right指針指向自己的為止） 143 while (pnode.right != nodes[node.rows] && pnode.right.cols < node.cols) 144 pnode = pnode.right; 145 146 //將最后一個(gè)節(jié)點(diǎn)的right指向插入節(jié)點(diǎn)的right，以此達(dá)到是循環(huán)鏈表 147 node.right = pnode.right; 148 149 //將插入節(jié)點(diǎn)給最后一個(gè)節(jié)點(diǎn)的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">矩陣的行數(shù)</param> 172 /// <param name="cols">矩陣的列數(shù)</param> 173 /// <param name="count">非0元素個(gè)數(shù)</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 //指向下一個(gè)節(jié)點(diǎn) 230 p = p.right; 231 } 232 } 233 } 234 #endregion 235 } 236 }

?

總結(jié)

以上是生活随笔為你收集整理的经典算法题每日演练——第二十一题 十字链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。