12 数组与稀疏矩阵 知识结构:
图1 知识结构 1. 数组 1.1 数组的定义 数组是具有一定顺序关系的若干对象组成的集合,组成数组的对象称为数组元素。
例如:
数组名表示群体的共性,即具有同一种数据类型;
下标表示个体的个性,即各自占有独立的单元。
1.2 数组的存储 (1) 维数组的定义
下标由 个数组成的数组称为 维数组。
例如:
//一维数组(线) 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];
图2 一维数组存储 二维数组a[m,n]
例:int[ , ] a = new int[2,3];
图3 二维数组存储 三维数组a[m,n,l]
第一维下标变化最慢,第三维(最后一维)下标变化最快。
例:int[ , , ] a = new int[2,3,4];
图4 三维数组的存储 注意:
C#中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 }
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)动态数组
在程序运行时分配空间的数组(声明之后数组长度可根据问题而调整)。
图5 动态数组类图 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
参考界面如下:
图6 动态数组实验界面 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)稀疏矩阵的定义
若矩阵 中非零元素的个数远远小于零元素的个数,则称 为稀疏矩阵。
例:
若用二维数组存储,则太浪费存储空间。
(2)稀疏矩阵的操作
图7 矩阵接口 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)。
图8 稀疏矩阵结点的存储 利用顺序的方式进行存储:
图9 顺序方式存储稀疏矩阵 利用链式的方式进行存储:
图10 链式方式存储稀疏矩阵 (1)对结点的封装
图11 稀疏矩阵结点类图 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)对稀疏矩阵的封装
图12 稀疏矩阵类图 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) }