基于C#实现十字链表

上一篇我们看了矩阵的顺序存储，这篇我们再看看一种链式存储方法“十字链表”，当然目的都是一样，压缩空间。

一、概念

既然要用链表节点来模拟矩阵中的非零元素，肯定需要如下 5 个元素(row,col,val,down,right)，其中：

row:矩阵中的行。
col:矩阵中的列。
val:矩阵中的值。
right:指向右侧的一个非零元素。
down：指向下侧的一个非零元素。

现在我们知道单个节点该如何表示了，那么矩阵中同行的非零元素的表示不就是一个单链表吗？比如如下：

那么进一步来说一个多行的非零元素的表示不就是多个单链表吗，是的，这里我把单链表做成循环链表，我们来看看如何用十字链表来表示稀疏矩阵。

从上面的十字链表中要注意两个问题：
第一：这里有一个填充色的节点，是十字链表中的总结点，它是记录该矩阵中的（row,col,value）和一个指向下一个头节点的 next 指针。
第二：每个链表都有一个头指针，总结点用 next 指针将它们贯穿起来。

二、操作

2.1、数据结构

刚才也说了，十字链表的总结点有一个 next 指针，而其他非零节点没有，所以为了方便，我们用一个 Unit 类包装起来。

 #region 单一节点/// <summary>/// 单一节点/// </summary>public class Node{//行号public int rows;//列号public int cols;//向下的指针域public Node down;//向右的指针域public Node right;//单元值（头指针的next和val）public Unit unit;}#endregion#region 统一“表头节点”和“非零节点”/// <summary>/// 统一“表头节点”和“非零节点”/// </summary>public class Unit{//表头节点的next域public Node next;//非零元素的值public int value;}#endregion

2.2、初始化

这一步，我们初始化总结点，并且用 next 指针将每个单链表的头节点链接成单链表（也就是上图中十字链表的第一行）

#region 十字链表中的“行数，列数，非零元素个数”/// <summary>/// 十字链表中的“行数，列数，非零元素个数”/// </summary>/// <param name="rows"></param>/// <param name="cols"></param>/// <param name="count"></param>public void Init(int rows, int cols, int count){var len = Math.Max(rows, cols) + 1;//从下标1开始算起nodes = new Node[len];//十字链表的总头节点nodes[0] = new Node();nodes[0].rows = rows;nodes[0].cols = cols;nodes[0].unit = new Unit(){value = count,next = null,};//down和right都指向自身nodes[0].right = nodes[0];nodes[0].down = nodes[0];var temp = nodes[0];//初始化多条链表的头结点for (int i = 1; i < len; i++){nodes[i] = new Node();nodes[i].rows = 0;nodes[i].cols = 0;nodes[i].unit = new Unit(){value = 0,next = temp.unit.next};//给上一个节点的next域赋值temp.unit.next = nodes[i];//将当前节点作为下一次循环的上一个节点temp = nodes[i];nodes[i].right = nodes[i];nodes[i].down = nodes[i];}}#endregion

2.3、插入节点

根据插入节点的 row 和 col 将节点插入到十字链表中指定的位置即可。

#region 插入十字链表中/// <summary>/// 插入十字链表中/// </summary>/// <param name="nums">矩阵</param>/// <param name="rows">矩阵的行数</param>/// <param name="cols">矩阵的列数</param>/// <param name="count">非0元素个数</param>/// <returns></returns>public Node[] Insert(int[,] nums, int rows, int cols, int count){//初始化操作Init(rows, cols, count);//插入操作for (int i = 0; i < rows; i++){for (int j = 0; j < cols; j++){//直插入"非0元素"if (nums[i, j] != 0){var node = new Node();node.rows = i + 1;node.cols = j + 1;node.unit = new Unit(){value = nums[i, j]};node.right = node;node.down = node;InsertNode(node);}}}return nodes;}#endregion

2.4、打印链表

我们只要遍历每行链表的 right 指针即可。

#region 打印十字链表/// <summary>/// 打印十字链表/// </summary>/// <param name="nodes"></param>public void Print(Node[] nodes){var head = nodes[0];//遍历每一行的rightfor (int i = 1; i < head.rows + 1; i++){var p = nodes[i];while (p.right != nodes[i]){Console.WriteLine("({0},{1})\tval => {2}",p.right.rows,p.right.cols,p.right.unit.value);//指向下一个节点p = p.right;}}}#endregion

2.5、总的代码：

 using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Diagnostics;using System.Threading;using System.IO;namespace ConsoleApplication2{public class Program{public static void Main(){Crosslist crosslist = new Crosslist();int[,] nums = {{2,0,4 },{0,3,0 },{0,0,9 }};var nodes = crosslist.Insert(nums, 3, 3, 4);crosslist.Print(nodes);Console.Read();}}/// <summary>/// 十字链表/// </summary>public class Crosslist{#region 单一节点/// <summary>/// 单一节点/// </summary>public class Node{//行号public int rows;//列号public int cols;//向下的指针域public Node down;//向右的指针域public Node right;//单元值（头指针的next和val）public Unit unit;}#endregion#region 统一“表头节点”和“非零节点”/// <summary>/// 统一“表头节点”和“非零节点”/// </summary>public class Unit{//表头节点的next域public Node next;//非零元素的值public int value;}#endregionNode[] nodes;#region 十字链表中的“行数，列数，非零元素个数”/// <summary>/// 十字链表中的“行数，列数，非零元素个数”/// </summary>/// <param name="rows"></param>/// <param name="cols"></param>/// <param name="count"></param>public void Init(int rows, int cols, int count){var len = Math.Max(rows, cols) + 1;//从下标1开始算起nodes = new Node[len];//十字链表的总头节点nodes[0] = new Node();nodes[0].rows = rows;nodes[0].cols = cols;nodes[0].unit = new Unit(){value = count,next = null,};//down和right都指向自身nodes[0].right = nodes[0];nodes[0].down = nodes[0];var temp = nodes[0];//初始化多条链表的头结点for (int i = 1; i < len; i++){nodes[i] = new Node();nodes[i].rows = 0;nodes[i].cols = 0;nodes[i].unit = new Unit(){value = 0,next = temp.unit.next};//给上一个节点的next域赋值temp.unit.next = nodes[i];//将当前节点作为下一次循环的上一个节点temp = nodes[i];nodes[i].right = nodes[i];nodes[i].down = nodes[i];}}#endregion#region 在指定的“行，列”上插入节点/// <summary>/// 在指定的“行，列”上插入节点/// </summary>/// <param name="node"></param>/// <returns></returns>public void InsertNode(Node node){//先定位行Node pnode = nodes[node.rows];//在指定的“行”中找，一直找到该行最后一个节点（right指针指向自己的为止）while (pnode.right != nodes[node.rows] && pnode.right.cols < node.cols)pnode = pnode.right;//将最后一个节点的right指向插入节点的right，以此达到是循环链表node.right = pnode.right;//将插入节点给最后一个节点的right指针上pnode.right = node;//再定位列pnode = nodes[node.cols];//同理while (pnode.down != nodes[node.cols] && pnode.down.rows < node.rows){pnode = pnode.down;}node.down = pnode.down;pnode.down = node;}#endregion#region 插入十字链表中/// <summary>/// 插入十字链表中/// </summary>/// <param name="nums">矩阵</param>/// <param name="rows">矩阵的行数</param>/// <param name="cols">矩阵的列数</param>/// <param name="count">非0元素个数</param>/// <returns></returns>public Node[] Insert(int[,] nums, int rows, int cols, int count){//初始化操作Init(rows, cols, count);//插入操作for (int i = 0; i < rows; i++){for (int j = 0; j < cols; j++){//直插入"非0元素"if (nums[i, j] != 0){var node = new Node();node.rows = i + 1;node.cols = j + 1;node.unit = new Unit(){value = nums[i, j]};node.right = node;node.down = node;InsertNode(node);}}}return nodes;}#endregion#region 打印十字链表/// <summary>/// 打印十字链表/// </summary>/// <param name="nodes"></param>public void Print(Node[] nodes){var head = nodes[0];//遍历每一行的rightfor (int i = 1; i < head.rows + 1; i++){var p = nodes[i];while (p.right != nodes[i]){Console.WriteLine("({0},{1})\tval => {2}",p.right.rows,p.right.cols,p.right.unit.value);//指向下一个节点p = p.right;}}}#endregion}}