C#實(shí)現(xiàn)十字鏈表的使用示例
上一篇我們看了矩陣的順序存儲,這篇我們再看看一種鏈?zhǔn)酱鎯Ψ椒?ldquo;十字鏈表”,當(dāng)然目的都是一樣,壓縮空間。
一、概念
既然要用鏈表節(jié)點(diǎn)來模擬矩陣中的非零元素,肯定需要如下 5 個元素(row,col,val,down,right),其中:
- row:矩陣中的行。
- col:矩陣中的列。
- val:矩陣中的值。
- right:指向右側(cè)的一個非零元素。
- down:指向下側(cè)的一個非零元素。
現(xiàn)在我們知道單個節(jié)點(diǎn)該如何表示了,那么矩陣中同行的非零元素的表示不就是一個單鏈表嗎?比如如下:
那么進(jìn)一步來說一個多行的非零元素的表示不就是多個單鏈表嗎,是的,這里我把單鏈表做成循環(huán)鏈表,我們來看看如何用十字鏈表來表示稀疏矩陣。
從上面的十字鏈表中要注意兩個問題:
第一:這里有一個填充色的節(jié)點(diǎn),是十字鏈表中的總結(jié)點(diǎn),它是記錄該矩陣中的(row,col,value)和一個指向下一個頭節(jié)點(diǎn)的 next 指針。
第二:每個鏈表都有一個頭指針,總結(jié)點(diǎn)用 next 指針將它們貫穿起來。
二、操作
2.1、數(shù)據(jù)結(jié)構(gòu)
剛才也說了,十字鏈表的總結(jié)點(diǎn)有一個 next 指針,而其他非零節(jié)點(diǎn)沒有,所以為了方便,我們用一個 Unit 類包裝起來。
#region 單一節(jié)點(diǎn) /// <summary> /// 單一節(jié)點(diǎn) /// </summary> public class Node { //行號 public int rows; //列號 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 指針將每個單鏈表的頭節(jié)點(diǎn)鏈接成單鏈表(也就是上圖中十字鏈表的第一行)
#region 十字鏈表中的“行數(shù),列數(shù),非零元素個數(shù)” /// <summary> /// 十字鏈表中的“行數(shù),列數(shù),非零元素個數(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 }; //給上一個節(jié)點(diǎn)的next域賦值 temp.unit.next = nodes[i]; //將當(dāng)前節(jié)點(diǎn)作為下一次循環(huán)的上一個節(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元素個數(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); //指向下一個節(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 { //行號 public int rows; //列號 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ù),非零元素個數(shù)” /// <summary> /// 十字鏈表中的“行數(shù),列數(shù),非零元素個數(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 }; //給上一個節(jié)點(diǎn)的next域賦值 temp.unit.next = nodes[i]; //將當(dāng)前節(jié)點(diǎn)作為下一次循環(huán)的上一個節(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]; //在指定的“行”中找,一直找到該行最后一個節(jié)點(diǎn)(right指針指向自己的為止) while (pnode.right != nodes[node.rows] && pnode.right.cols < node.cols) pnode = pnode.right; //將最后一個節(jié)點(diǎn)的right指向插入節(jié)點(diǎn)的right,以此達(dá)到是循環(huán)鏈表 node.right = pnode.right; //將插入節(jié)點(diǎn)給最后一個節(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元素個數(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); //指向下一個節(jié)點(diǎn) p = p.right; } } } #endregion } }
到此這篇關(guān)于C#實(shí)現(xiàn)十字鏈表的使用示例的文章就介紹到這了,更多相關(guān)C# 十字鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- C#數(shù)據(jù)結(jié)構(gòu)之單鏈表(LinkList)實(shí)例詳解
- C#實(shí)現(xiàn)的簡單鏈表類實(shí)例
- C#雙向鏈表LinkedList排序?qū)崿F(xiàn)方法
- C#定義并實(shí)現(xiàn)單鏈表實(shí)例解析
- C#數(shù)據(jù)結(jié)構(gòu)之雙向鏈表(DbLinkList)實(shí)例詳解
- C#數(shù)據(jù)結(jié)構(gòu)之循環(huán)鏈表的實(shí)例代碼
- C#數(shù)據(jù)結(jié)構(gòu)與算法揭秘四 雙向鏈表
- C#集合之鏈表的用法
- C#通過鏈表實(shí)現(xiàn)隊(duì)列的方法
- C#集合本質(zhì)之鏈表的用法詳解
- C#模擬鏈表數(shù)據(jù)結(jié)構(gòu)的實(shí)例解析
相關(guān)文章
C# Oracle數(shù)據(jù)庫操作類實(shí)例詳解
這篇文章主要介紹了C# Oracle數(shù)據(jù)庫操作類實(shí)例,進(jìn)行數(shù)據(jù)庫操作時很有實(shí)用價值,需要的朋友可以參考下2014-07-07C# 如何在WINForm程序中創(chuàng)建XML文件
這篇文章主要介紹了C# 如何在WINForm程序中創(chuàng)建XML文件,幫助大家更好的理解和學(xué)習(xí)使用c#,感興趣的朋友可以了解下2021-02-02用C#實(shí)現(xiàn)啟動另一程序的方法實(shí)例
一段實(shí)例代碼,程序的目的是使用C#實(shí)現(xiàn)啟動另一程序的方法。技術(shù)總監(jiān)給出了我們這樣一個有效的啟動程序的有效方法,現(xiàn)在和大家分享下2013-07-07