经典算法题每日演练——第二十一题 十字链表

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

一：概念

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

row:矩阵中的行。

col:矩阵中的列。

val:矩阵中的值。

right:指向右侧的一个非零元素。

down：指向下侧的一个非零元素。

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

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

来表示稀疏矩阵。

从上面的十字链表中要注意两个问题：

第一：这里有一个填充色的节点，是十字链表中的总结点，它是记录该矩阵中的（row,col,value）和一个指向下一个头节点的next指针。

第二：每个链表都有一个头指针，总结点用next指针将它们贯穿起来。

二：操作

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：初始化

   这一步，我们初始化总结点，并且用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

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

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);

                    //指向下一个节点
                    p = p.right;
                }
            }
        }
        #endregion

总的代码：

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;
        }
        #endregion

        Node[] 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];

            //遍历每一行的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);

                    //指向下一个节点
                    p = p.right;
                }
            }
        }
        #endregion
    }
}