12 数组与稀疏矩阵
知识结构：
1. 数组
1.1 数组的定义
数组是具有一定顺序关系的若干对象组成的集合，组成数组的对象称为数组元素。
例如：
向量对应一维数组
A=(a0,a1,⋯,an−1)A=(a_0,a_1,\cdots,a_{n-1}) A=(a0,a1,⋯,an−1)
矩阵对应二维数组
Am×n=[a00a01⋯a0n−1a10a11⋯a1n−1⋯⋯⋯⋯am−10am−11⋯am−1n−1]A_{m \times n} =\begin{bmatrix} a_{00}&a_{01} &\cdots &a_{0n-1}\\ a_{10}&a_{11} &\cdots &a_{1n-1}\\ \cdots& \cdots &\cdots &\cdots\\ a_{m-10}&a_{m-11}& \cdots &a_{m-1n-1}\\ \end{bmatrix} Am×n=⎣⎢⎢⎡a00a10⋯am−10a01a11⋯am−11⋯⋯⋯⋯a0n−1a1n−1⋯am−1n−1⎦⎥⎥⎤
数组名表示群体的共性，即具有同一种数据类型；
下标表示个体的个性，即各自占有独立的单元。
1.2 数组的存储
（1）nnn维数组的定义
下标由nnn个数组成的数组称为nnn维数组。
例如：
//一维数组（线）int[] a = new int[10]; //二维数组 （面）int[ , ] a = new int[2,3];//三维数组 （体），类比：书（体）【2.页码 3.行 4.列】 int[ , , ] a = new int[2,3,4];
（2）数组存储的特点
数组元素在内存中按顺序连续存储。数组的存储分配按照行（C、C++、C#等）或列（Forturn等）进行。数组名表示该数组的首地址，是常量。
（3）常用数组的存储
一维数组a[n]
各元素按下角标依次存放。
例：int[] a = new int[5];
二维数组a[m,n]
例：int[ , ] a = new int[2,3];
三维数组a[m,n,l]
第一维下标变化最慢，第三维（最后一维）下标变化最快。
例：int[ , , ] a = new int[2,3,4];
注意：
C#中int[,]与int[][]定义数组的区别
int[,]行数，列数确定
static void Main(string[] args){int[,] Arr = new int[2, 5] {{1, 2, 3, 5, 6 }, {1, 2, 3, 4, 5 } };for (int i = 0; i < 2; ++i){for (int j = 0; j < 5; ++j){Console.Write(Convert.ToString(Arr[i, j]) + " ");}Console.WriteLine();}// 1 2 3 5 6// 1 2 3 4 5}
int[][]行数确定，列数不定
static void Main(string[] args){int[][] Arr = new int[3][]; //表示含有三个一维数组的数组Arr[0] = new int[5] {1, 2, 3, 4, 5 };Arr[1] = new int[2] {0, 1 };Arr[2] = new int[0] {};for (int i = 0; i < Arr.Length; ++i){foreach (int j in Arr[i]){Console.Write(j + " ");}Console.WriteLine();}// 1 2 3 4 5// 0 1// }
1.3 数组的分类
数组可分为静态数组和动态数组两类。
（1）静态数组
在程序编译时分配空间的数组。
例：
//静态数组（声明之后数组长度不可改变）int[] a = new int[10];
（2）动态数组
在程序运行时分配空间的数组（声明之后数组长度可根据问题而调整）。
using System;namespace LinearStruct{/// <summary>/// 动态数组的抽象数据类型实现/// </summary>/// <typeparam name="T">动态数组中元素的类型</typeparam>public class DArray<T> where T : IComparable<T>{private T[] _array;/// <summary>/// 获取动态数组的当前长度/// </summary>public int Size {get; private set; }/// <summary>/// 初始化DArray类的新实例/// </summary>/// <param name="size">动态数组的初始长度</param>public DArray(int size){if (size <= 0)throw new ArgumentOutOfRangeException();Size = size;_array = new T[Size];}/// <summary>/// 改变动态数组的长度/// </summary>/// <param name="newSize">动态数组的新长度</param>public void ReSize(int newSize){if (newSize <= 0)throw new ArgumentOutOfRangeException();if (Size != newSize){T[] newArray = new T[newSize];int n = newSize < Size ? newSize : Size;for (int i = 0; i < n; i++){newArray[i] = _array[i];}_array = newArray;Size = newSize;}}/// <summary>/// 获取或设置指定索引处的元素/// </summary>/// <param name="index">要获得或设置的元素从零开始的索引</param>/// <returns>指定索引处的元素</returns>public T this[int index]{get{if (index < 0 || index > Size - 1)throw new IndexOutOfRangeException();return _array[index];}set{if (index < 0 || index > Size - 1)throw new IndexOutOfRangeException();_array[index] = value;}}}}
1.4 动态数组的应用
编写一段代码，要求输入一个整数N，用动态数组A来存放2~N之间所有5或7的倍数，输出该数组。
例如：N=100
则输出：5 7 10 14 15 20 21 25 28 30 35 40 42 45 49 50 55 56 60 63 65 70 75 77 80 84 85 90 91 95 98 100
参考界面如下：
static void Main(string[] args){Console.WriteLine("N=");string s = Console.ReadLine();int n;if (int.TryParse(s, out n)){DArray<int> arr = new DArray<int>(10);int j = 0;for (int i = 2; i <= n; i++){if (i % 5 == 0 || i % 7 == 0){if (j == arr.Size)arr.ReSize(arr.Size + 10);arr[j] = i;j++;}}for (int i = 0; i < j; i++){Console.Write(arr[i] + " ");}}}
2. 稀疏矩阵
2.1 稀疏矩阵的定义与操作
（1）稀疏矩阵的定义
若矩阵AAA中非零元素的个数远远小于零元素的个数，则称AAA为稀疏矩阵。
例：
A=[500001002000000−300−605]A = \begin {bmatrix} 50 & 0 & 0 & 0\\ 10 & 0 & 20 & 0\\ 0 & 0 & 0 & 0\\ -30 & 0 & -60 & 5 \end{bmatrix} A=⎣⎢⎢⎡50100−3000000200−600005⎦⎥⎥⎤
若用二维数组存储，则太浪费存储空间。
（2）稀疏矩阵的操作
获取矩阵的行数获取矩阵的列数获取或设置指定索引处的元素矩阵加法矩阵转置矩阵乘法
namespace LinearStruct{/// <summary>/// 矩阵的抽象数据类型/// </summary>public interface IMatrix<T>{/// <summary>/// 获取矩阵的行数/// </summary>int Rows {get; }/// <summary>/// 获取矩阵的列数/// </summary>int Cols {get; }/// <summary>/// 获取或设置指定索引处的元素/// </summary>/// <param name="i">要获取或设置的元素从零开始的行索引</param>/// <param name="j">要获取或设置的元素从零开始的列索引</param>/// <returns></returns>T this[int i, int j] {get; set; }/// <summary>/// 矩阵加法/// </summary>/// <param name="b">与之相加的另一个矩阵</param>/// <returns>相加后的新矩阵</returns>IMatrix<T> Add(IMatrix<T> b);/// <summary>/// 矩阵转置/// </summary>/// <returns>转置后的新矩阵</returns>IMatrix<T> Transpose();/// <summary>/// 矩阵乘法/// </summary>/// <param name="b">与之右乘的另一个矩阵</param>/// <returns>相乘后的新矩阵</returns>IMatrix<T> Multiply(IMatrix<T> b);}}
2.2 稀疏矩阵的存储与实现
可以利用（Row，Col，Value）的方式存储和定位稀疏矩阵中的非零元素，这种存储稀疏矩阵结点的方式称为三元组（Triple）。
利用顺序的方式进行存储：
利用链式的方式进行存储：
（1）对结点的封装
using System;namespace LinearStruct{/// <summary>/// 稀疏矩阵结点/// </summary>public class Triple : IComparable<Triple>{/// <summary>/// 获取结点所在矩阵中的行索引/// </summary>public int Row {get; }/// <summary>/// 获取结点所在矩阵中的列索引/// </summary>public int Col {get; }/// <summary>/// 获取或设置结点在矩阵中的值/// </summary>public double Value {get; set; }/// <summary>/// 初始化Triple类的新实例/// </summary>/// <param name="i">结点所在矩阵中的行索引</param>/// <param name="j">结点所在矩阵中的列索引</param>/// <param name="value">结点在矩阵中的值</param>public Triple(int i, int j, double value){if (i < 0 || j < 0)throw new Exception("数组元素位置无效.");Row = i;Col = j;Value = value;}/// <summary>/// Triple类的输出字符串/// </summary>/// <returns>Triple类的输出字符串</returns>public override string ToString(){return string.Format("({0},{1},{2})", Row, Col, Value);}/// <summary>/// 比较三元组中数据的大小/// </summary>/// <param name="other">被比较的三元组</param>/// <returns></returns>public int CompareTo(Triple other){if (Value < other.Value) return -1;if (Value > other.Value) return 1;return 0;}}}
（2）对稀疏矩阵的封装
using System;namespace LinearStruct{/// <summary>/// 矩阵抽象数据类型的实现--稀疏矩阵/// </summary>public class SparseMatrix : IMatrix<double>{private readonly DLinkList<Triple> _lst;/// <summary>/// 获取稀疏矩阵的行数/// </summary>public int Rows {get; }/// <summary>/// 获取稀疏矩阵的列数/// </summary>public int Cols {get; }/// <summary>/// 初始化SparseMatrix类的新实例/// </summary>/// <param name="rows">稀疏矩阵的行数</param>/// <param name="cols">稀疏矩阵的列数</param>public SparseMatrix(int rows, int cols){if (rows <= 0 || cols <= 0)throw new ArgumentOutOfRangeException();Rows = rows;Cols = cols;_lst = new DLinkList<Triple>();}private DNode<Triple> GetIndex(int i, int j){DNode<Triple> temp = _lst.PHead;while (temp != null){if (temp.Data.Row == i && temp.Data.Col == j)break;temp = temp.Next;}return temp;}private void RemoveNode(DNode<Triple> node){if (node.Next == null){_lst.Remove(_lst.Length - 1);}else if (node.Prior == null){_lst.Remove(0);}else{node.Prior.Next = node.Next;node.Next.Prior = node.Prior;}}/// <summary>/// 获取或设置指定索引处的元素/// </summary>/// <param name="i">要获取或设置的元素从零开始的行索引</param>/// <param name="j">要获取或设置的元素从零开始的列索引</param>/// <returns></returns>public double this[int i, int j]{get{if (i < 0 || i > Rows - 1 || j < 0 || j > Cols - 1)throw new IndexOutOfRangeException();DNode<Triple> node = GetIndex(i, j);return node == null ? 0.0 : node.Data.Value;}set{if (i < 0 || i > Rows - 1 || j < 0 || j > Cols - 1)throw new IndexOutOfRangeException();DNode<Triple> node = GetIndex(i, j);if (node == null){if (value != 0.0){_lst.InsertAtRear(new Triple(i, j, value));}}else{if (value != 0.0){node.Data.Value = value;}else{RemoveNode(node);}}}}/// <summary>/// 矩阵加法/// </summary>/// <param name="b">与之相加的另一个矩阵</param>/// <returns>相加后的新矩阵</returns>public SparseMatrix Add(SparseMatrix b){if (b == null)throw new ArgumentNullException();if (b.Rows != Rows || b.Cols != Cols)throw new Exception("两矩阵不能相加.");SparseMatrix temp = new SparseMatrix(Rows, Cols);for (int i = 0; i < Rows; i++)for (int j = 0; j < Cols; j++)temp[i, j] = this[i, j] + b[i, j];return temp;}/// <summary>/// 矩阵转置/// </summary>/// <returns>转置后的新矩阵</returns>public SparseMatrix Transpose(){SparseMatrix temp = new SparseMatrix(Cols, Rows);for (int i = 0; i < temp.Rows; i++)for (int j = 0; j < temp.Cols; j++)temp[i, j] = this[j, i];return temp;}/// <summary>/// 矩阵乘法/// </summary>/// <param name="b">与之右乘的另一个矩阵</param>/// <returns>相乘后的新矩阵</returns>public SparseMatrix Multiply(SparseMatrix b){if (b == null)throw new ArgumentNullException();if (Cols != b.Rows)throw new Exception("两矩阵不能相乘.");SparseMatrix temp = new SparseMatrix(Rows, b.Cols);for (int i = 0; i < Rows; i++){for (int j = 0; j < b.Cols; j++){double value = 0.0;for (int k = 0; k < Cols; k++)value += this[i, k] * b[k, j];temp[i, j] = value;}}return temp;}/// <summary>/// 矩阵加法运算/// </summary>/// <param name="a">第一个矩阵</param>/// <param name="b">第二个矩阵</param>/// <returns>相加后的新矩阵</returns>public static SparseMatrix operator +(SparseMatrix a, SparseMatrix b){if (a == null || b == null)throw new ArgumentNullException();return a.Add(b);}/// <summary>/// 矩阵乘法运算/// </summary>/// <param name="a">左边的矩阵</param>/// <param name="b">右边的矩阵</param>/// <returns>相乘后的新矩阵</returns>public static SparseMatrix operator *(SparseMatrix a, SparseMatrix b){if (a == null || b == null)throw new ArgumentNullException();return a.Multiply(b);}/// <summary>/// SparseMatrix类的输出字符串/// </summary>/// <returns>SparseMatrix类的输出字符串</returns>public override string ToString(){string str = string.Empty;DNode<Triple> temp = _lst.PHead;while (temp != null){str += temp.Data + "\n";temp = temp.Next;}return str;}IMatrix<double> IMatrix<double>.Add(IMatrix<double> b){return Add((SparseMatrix)b);}IMatrix<double> IMatrix<double>.Transpose(){return Transpose();}IMatrix<double> IMatrix<double>.Multiply(IMatrix<double> b){return Multiply((SparseMatrix)b);}}}
举例：
static void Main(string[] args){IMatrix<double> a = new SparseMatrix(2, 3);IMatrix<double> b = new SparseMatrix(3, 2);SparseMatrix c = new SparseMatrix(2, 2);a[0, 2] = 1;a[1, 0] = 1;b[1, 1] = 4;b[2, 0] = 1;c[0, 1] = 1;c[1, 0] = 1;SparseMatrix d = (SparseMatrix)a * (SparseMatrix)b + c;IMatrix<double> e = a.Multiply(b).Add(c);Console.WriteLine("D:\n{0}", d);Console.WriteLine("E:\n{0}", e);// D:// (0, 0, 1)// (0, 1, 1)// (1, 0, 1)// E:// (0, 0, 1)// (0, 1, 1)// (1, 0, 1)}
如果觉得《数据结构与算法：12 数组与稀疏矩阵》对你有帮助，请点赞、收藏，并留下你的观点哦！
