C#實(shí)現(xiàn)十字鏈表的使用示例

更新時(shí)間：2023年11月27日 15:11:07 作者：神仙別鬧

十字鏈表是一種將數(shù)據(jù)存儲(chǔ)在節(jié)點(diǎn)中的數(shù)據(jù)結(jié)構(gòu),每個(gè)節(jié)點(diǎn)包含兩個(gè)指針,分別指向下一個(gè)節(jié)點(diǎn)和上一個(gè)節(jié)點(diǎn),通過(guò)定義節(jié)點(diǎn)類和鏈表類,實(shí)現(xiàn)十字鏈表的創(chuàng)建、遍歷、插入和刪除等操作,本文就來(lái)實(shí)現(xiàn)一下

一、概念

既然要用鏈表節(jié)點(diǎn)來(lái)模擬矩陣中的非零元素，肯定需要如下 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)一步來(lái)說(shuō)一個(gè)多行的非零元素的表示不就是多個(gè)單鏈表嗎，是的，這里我把單鏈表做成循環(huán)鏈表，我們來(lái)看看如何用十字鏈表來(lái)表示稀疏矩陣。

從上面的十字鏈表中要注意兩個(gè)問(wèn)題：
第一：這里有一個(gè)填充色的節(jié)點(diǎn)，是十字鏈表中的總結(jié)點(diǎn)，它是記錄該矩陣中的（row,col,value）和一個(gè)指向下一個(gè)頭節(jié)點(diǎn)的 next 指針。
第二：每個(gè)鏈表都有一個(gè)頭指針，總結(jié)點(diǎn)用 next 指針將它們貫穿起來(lái)。

二、操作

2.1、數(shù)據(jù)結(jié)構(gòu)

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

 #region 單一節(jié)點(diǎn)
 /// <summary>
 /// 單一節(jié)點(diǎn)
 /// </summary>
 public class Node
 {
     //行號(hào)
     public int rows;

     //列號(hào)
     public int cols;

     //向下的指針域
     public Node down;

     //向右的指針域
     public Node right;

     //單元值（頭指針的next和val）
     public Unit unit;
 }
 #endregion

 #region 統(tǒng)一“表頭節(jié)點(diǎn)”和“非零節(jié)點(diǎn)”
 /// <summary>
 /// 統(tǒng)一“表頭節(jié)點(diǎn)”和“非零節(jié)點(diǎn)”
 /// </summary>
 public class Unit
 {
     //表頭節(jié)點(diǎn)的next域
     public Node next;

     //非零元素的值
     public int value;
 }
 #endregion

2.2、初始化

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

#region 十字鏈表中的“行數(shù)，列數(shù)，非零元素個(gè)數(shù)”
 /// <summary>
 /// 十字鏈表中的“行數(shù)，列數(shù)，非零元素個(gè)數(shù)”
 /// </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;

     //從下標(biāo)1開始算起
     nodes = new Node[len];

     //十字鏈表的總頭節(jié)點(diǎn)
     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];

     //初始化多條鏈表的頭結(jié)點(diǎn)
     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
         };

         //給上一個(gè)節(jié)點(diǎn)的next域賦值
         temp.unit.next = nodes[i];

         //將當(dāng)前節(jié)點(diǎn)作為下一次循環(huán)的上一個(gè)節(jié)點(diǎn)
         temp = nodes[i];

         nodes[i].right = nodes[i];
         nodes[i].down = nodes[i];
     }
 }
 #endregion

2.3、插入節(jié)點(diǎn)

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

#region 插入十字鏈表中
 /// <summary>
 /// 插入十字鏈表中
 /// </summary>
 /// <param name="nums">矩陣</param>
 /// <param name="rows">矩陣的行數(shù)</param>
 /// <param name="cols">矩陣的列數(shù)</param>
 /// <param name="count">非0元素個(gè)數(shù)</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];

     //遍歷每一行的right
     for (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);

             //指向下一個(gè)節(jié)點(diǎn)
             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 單一節(jié)點(diǎn)
         /// <summary>
         /// 單一節(jié)點(diǎn)
         /// </summary>
         public class Node
         {
             //行號(hào)
             public int rows;
 
             //列號(hào)
             public int cols;
 
             //向下的指針域
             public Node down;
 
             //向右的指針域
             public Node right;
 
             //單元值（頭指針的next和val）
             public Unit unit;
         }
         #endregion
 
         #region 統(tǒng)一“表頭節(jié)點(diǎn)”和“非零節(jié)點(diǎn)”
         /// <summary>
         /// 統(tǒng)一“表頭節(jié)點(diǎn)”和“非零節(jié)點(diǎn)”
         /// </summary>
         public class Unit
         {
             //表頭節(jié)點(diǎn)的next域
             public Node next;
 
             //非零元素的值
             public int value;
         }
         #endregion
 
         Node[] nodes;
 
         #region 十字鏈表中的“行數(shù)，列數(shù)，非零元素個(gè)數(shù)”
         /// <summary>
         /// 十字鏈表中的“行數(shù)，列數(shù)，非零元素個(gè)數(shù)”
         /// </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;
 
             //從下標(biāo)1開始算起
             nodes = new Node[len];
 
             //十字鏈表的總頭節(jié)點(diǎn)
             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];
 
             //初始化多條鏈表的頭結(jié)點(diǎn)
             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
                 };
 
                 //給上一個(gè)節(jié)點(diǎn)的next域賦值
                 temp.unit.next = nodes[i];
 
                 //將當(dāng)前節(jié)點(diǎn)作為下一次循環(huán)的上一個(gè)節(jié)點(diǎn)
                 temp = nodes[i];
 
                 nodes[i].right = nodes[i];
                 nodes[i].down = nodes[i];
             }
         }
         #endregion
 
         #region 在指定的“行，列”上插入節(jié)點(diǎn)
         /// <summary>
         /// 在指定的“行，列”上插入節(jié)點(diǎn)
         /// </summary>
         /// <param name="node"></param>
         /// <returns></returns>
         public void InsertNode(Node node)
         {
             //先定位行
             Node pnode = nodes[node.rows];
 
             //在指定的“行”中找，一直找到該行最后一個(gè)節(jié)點(diǎn)（right指針指向自己的為止）
             while (pnode.right != nodes[node.rows] && pnode.right.cols < node.cols)
                 pnode = pnode.right;
 
             //將最后一個(gè)節(jié)點(diǎn)的right指向插入節(jié)點(diǎn)的right，以此達(dá)到是循環(huán)鏈表
             node.right = pnode.right;
 
             //將插入節(jié)點(diǎn)給最后一個(gè)節(jié)點(diǎn)的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">矩陣的行數(shù)</param>
         /// <param name="cols">矩陣的列數(shù)</param>
         /// <param name="count">非0元素個(gè)數(shù)</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];
 
             //遍歷每一行的right
             for (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);
 
                     //指向下一個(gè)節(jié)點(diǎn)
                     p = p.right;
                 }
             }
         }
         #endregion
     }
 }