加载中...

第二十一题 十字链表

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

一：概念

    既然要用链表节点来模拟矩阵中的非零元素，肯定需要如下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. }

 

还没有评论.