第7章数组 零基础学数据结构

第7章数组,数组是一种扩展的线性数据结构。线性表、栈、队列、串的数据元素都是不可再分的原子类型，而数组中的数据元素是可以再分的。数组可以分为一维数组和多维数组，一维数组中的元素是由原子构成的，多维数组中的元素又是一个线性表。因此，数组是一种特殊的线性表。,7.1数组,数组是一种特殊的线性表，表中的元素可以是原子类型，也可以是一个线性表。本节主要介绍数组的定义和数组的抽象数据类型。,7.1.1数组的定义,数组是由n个类型相同的数据元素组成的有限序列。其中，这n个数据元素占用一块地址连续的存储空间。数组中的数据元素可以是原子类型的，如整型、字符型、浮点型等，这种类型的数组称为一维数组；也可以是一个线性表，这种类型的数组称为二维数组。二维数组可以看成是线性表的线性表。,7.1.2数组的抽象数据类型,1数据对象集合2基本操作集合,7.2数组的顺序表示与实现,一般情况下，不对数组进行插入和删除操作。如果建立了数组，则数组的维数与各维的长度不再改变，因此，数组采用的是顺序存储方式。本节的主要学习内容包括数组的顺序存储结构及顺序存储结构下的操作实现。,7.2.1数组的顺序存储结构,在计算机中，存储器的结构是一维（线性）的结构。数组是一个多维的结构，如果要将一个多维的结构存放在一个一维的存储单元里，就必须先将多维的数组转换成一个一维的线性序列，才能将其存放在存储器中。,7.2.1数组的顺序存储结构,数组的顺序存储结构类型定义描述如下：#defineMaxArraySize3#include/*标准头文件，包含va_start、va-arg、va_end宏定义*/typedefstructDataType*base;/*数组元素的基地址*/intdim;/*数组的维数*/int*bounds;/*数组的每一维之间的界限的地址*/int*constants;/*数组存储映像常量基地址*/Array;,7.2.2数组的基本运算,在顺序存储结构中，数组的基本运算实现如下所示。（1）数组的初始化操作。va_list的用法：（1）首先在函数里定义一个va_list型的变量，这个变量是指向参数的指针;（2）然后用va_start初始化变量刚定义的va_list变量，该函数的第二个参数是第一个可变参数的前一个参数，它是一个固定的参数;（3）然后用va_arg返回可变的参数，va_arg的第二个参数是要返回的参数的类型;（4）最后用va_end结束可变参数的获取。,7.2.2数组的基本运算,（2）销毁数组操作。voidDestroyArray(Array*A)/*销毁数组。将动态申请的内存单元释放*/if(A-base)free(A-base);if(A-bounds)free(A-bounds);if(A-constants)free(A-constants);A-base=A-bounds=A-constants=NULL;/*将各个指针指向空*/A-dim=0;,7.2.2数组的基本运算,（3）返回数组中指定的元素。intGetValue(DataType*e,ArrayA,)/*返回数组中指定的元素，将指定的数组的下标的元素赋值给e*/va_listap;intoffset;va_start(ap,A);if(LocateArray(A,ap,7.2.2数组的基本运算,（4）数组的赋值操作。intAssignValue(ArrayA,DataTypee,.)/*数组的赋值操作。将e的值赋给的指定的数组元素*/va_listap;intoffset;va_start(ap,e);if(LocateArray(A,ap,7.2.2数组的基本运算,（5）数组的定位操作。intLocateArray(ArrayA,va_listap,int*offset)/*根据数组中元素的下标，求出该元素在A中的相对地址offset*/inti,instand;*offset=0;for(i=0;i=A.boundsi)return0;*offset+=A.constantsi*instand;return1;,7.2.3数组的应用举例,下面通过一个例子来说明数组基本操作的用法。例7_1利用数组的基本操作实现对数组的初始化、赋值、返回数组的值及定位操作。定义一个二维数组B，并将B初始化，然后将数组B的值依次赋值给数组A，并将数组A的元素输出。,7.3特殊矩阵的压缩存储,在许多科学与工程计算中会经常遇到矩阵运算的问题，在高级语言中，通常使用二维数组来存储矩阵。然而，在矩阵的运算中，往往在阶数很高的矩阵中存在许多相同的元素或值为零的元素。为了节省空间，需要将这些矩阵进行压缩存储。,7.3.1对称矩阵的压缩存储,如果一个n阶的矩阵A中的元素满足性质aij=aji(0i,jn-1)，则称这种矩阵为n阶对称矩阵。由于对称矩阵中的元素关于主对角线对称，因此，在对矩阵存储时，可以只存储对称矩阵中的上三角或者下三角的元素，使得对称的元素共享一个存储单元。,7.3.1对称矩阵的压缩存储,7.3.2三角矩阵的压缩存储,三角矩阵分为两种：上三角矩阵和下三角矩阵。其中，下三角元素均为常数c或零的n阶矩阵称为上三角矩阵，上三角元素均为常数c或零的n阶矩阵称为下三角矩阵。,7.3.2三角矩阵的压缩存储,7.3.3对角矩阵的压缩存储,对角矩阵，也称带状矩阵，是另一类特殊的矩阵。所谓对角矩阵，就是所有的非零元素都集中在以主对角线两侧的带状区域内（对角线的个数为奇数）。也就是说除了主对角线和主对角线两边的对角线外，其他元素的值均为0.,7.3.3对角矩阵的压缩存储,因此，k=Loc(0,0)+3*(i-1)-1+j-i=1=Loc(0,0)+2*(i-1)+j-1。则k=2*(i-1)+j-1。,7.4稀疏矩阵的压缩存储,稀疏矩阵中的大多数元素是零，因此也需要进行压缩存储。本节的主要学习内容包括稀疏矩阵的定义、稀疏矩阵的抽象数据类型、稀疏矩阵的三元组表示及算法实现。,7.4.1稀疏矩阵的定义,所谓稀疏矩阵，假设在mn矩阵中，有t个元素不为零，令=，为矩阵的稀疏因子，如果，则称矩阵为稀疏矩阵。也就是说，矩阵中存在大多数为零的元素，只有很少的非零元素，这样的矩阵是稀疏矩阵。,7.4.2稀疏矩阵抽象数据类型,1数据对象集合2基本操作集合,7.4.3稀疏矩阵的三元组表示,为了实现压缩存储，可以只存储稀疏矩阵的非零的元素。在存储稀疏矩阵中的非零元素时，还必须存储非零元素对应的行和列的位置(i,j)。也就是说存储一个非零元素需要存储元素的行号、列号和元素值，即通过存储(i,j,aij)唯一确定一个非零的元素。,(0,3,9),(1,1,3),(2,2,7),(2,3,2),(3,0,7),(3,4,-2),(4,2,4),(4,3,7),(5,4,5),7.4.3稀疏矩阵的三元组表示,7.4.3稀疏矩阵的三元组表示,三元组顺序表的类型定义如下。#defineMaxSize200typedefstruct/*三元组类型定义*/inti,j;DataTypee;Triple;typedefstruct/*矩阵类型定义*/TripledataMaxSize;intm,n,len;/*矩阵的行数，列数和非零元素的个数*/TriSeqMatrix;,7.4.4稀疏矩阵的三元组实现,下面给出稀疏矩阵的基本操作的算法实现。算法实现保存在文件”TriSeqMatrix.h”中。（1）创建稀疏矩阵操作。（2）销毁稀疏矩阵操作。voidDestroyMatrix(TriSeqMatrix*M)/*销毁稀疏矩阵操作.因为是静态分配，所以只需要将矩阵的行数，列数和个数置为0*/M-m=M-n=M-len=0;,7.4.4稀疏矩阵的三元组实现,（3）稀疏矩阵的复制操作。voidCopyMatrix(TriSeqMatrixM,TriSeqMatrix*N)/*由稀疏矩阵M复制得到另一个矩阵N*/inti;N-len=M.len;/*修改稀疏矩阵N的非零元素的个数*/N-m=M.m;/*修改稀疏矩阵N的行数*/N-n=M.n;/*修改稀疏矩阵N的列数*/for(i=0;idatai.i=M.datai.i;N-datai.j=M.datai.j;N-datai.e=M.datai.e;,7.4.4稀疏矩阵的三元组实现,（4）稀疏矩阵的相加操作。（5）稀疏矩阵的相减操作。,7.4.4稀疏矩阵的三元组实现,（6）稀疏矩阵的转置操作。,7.4.4稀疏矩阵的三元组实现,7.4.4稀疏矩阵的三元组实现,7.5稀疏矩阵的应用举例,在上一节学习了稀疏矩阵的定义及稀疏矩阵的三元组顺序存储的算法实现，这一节主要通过分析并实现两个矩阵的相乘的算法，来加强对稀疏矩阵知识的学习。,7.5.1稀疏矩阵的相乘三元组表示,两个矩阵相乘是矩阵的一种常用的运算。假设矩阵M是m1n1的矩阵，N是m2n2的矩阵，如果矩阵M的列数与矩阵N的行数相等，即n1=m2，则两个矩阵M和N是可以相乘的。,7.5.1稀疏矩阵的相乘三元组表示,7.5.1稀疏矩阵的相乘三元组表示,7.5.1稀疏矩阵的相乘三元组表示,#defineMaxSize200typedefintDataType;typedefstruct/*三元组类型定义*/inti,j;DataTypee;Triple;typedefstruct/*矩阵类型定义*/TripledataMaxSize;intrposMaxSize;/*用于存储三元组中的每一行的第一非零元素的位置*/intm,n,len;/*矩阵的行数，列数和非零元素的个数*/TriSeqMatrix;,7.5.2稀疏矩阵的相乘三元组实现,1算法的测试部分2两个矩阵相乘的算法实现,7.6稀疏矩阵的十字链表表示与实现,采用三元组顺序表在进行两个稀疏矩阵的相加和相乘运算时，需要移动大量的元素，算法的时间复杂度也大大增加。因此，本节来学习稀疏矩阵的另一种存储结构-链式存储。,7.6.1稀疏矩阵的十字链表表示,稀疏矩阵的链式存储，就是利用链表来表示稀疏矩阵，链表中的每个结点存储稀疏矩阵中的每个非零元素。每个结点包含5个域：3个数据域和两个指针域。其中3个数据域是i，j和e，分别表示非零元素的行号、列号和元素值；2个指针域是right域和down域，right指向同一行中的下一个非零元素，down指向同一列的非零元素。,7.6.1稀疏矩阵的十字链表表示,7.6.1稀疏矩阵的十字链表表示,十字链表的类型描述如下：typedefstructOLNodeinti,j;DataTypee;structOLNode*right,*down;OLNode,*OLink;typedefstructOLink*rowhead,*colhead;intm,n,len;CrossList;,7.6.2十字链表的实现,下面给出稀疏矩阵的十字链表的基本操作的算法实现。算法实现保存在文件”CrossList.h”中。,7.6.2十字链表的实现,（1）稀疏矩阵的初始化操作。voidInitMatrix(CrossList*M)/*初始化稀疏矩阵*/M-rowhead=M-colhead=NULL;M-m=M-n=M-len=0;,7.6.2十字链表的实现,（2）稀疏矩阵的创建操作。（3）稀疏矩阵的插入操作。（4）稀疏矩阵的销毁操作。,7.7稀疏矩阵的十字链表实现应用举例,十字链表在稀疏矩阵的相加、相减和相乘操作是比较恰当的。本节通过两个稀疏矩阵的相加操作来说明稀疏矩阵的十字链表的使用。,7.7稀疏矩阵的十字链表实现应用举例,例7_3例如有两个稀疏矩阵A和B，相加得到C，如图7.21所示。请利用十字链表实现两个稀疏矩阵的相加，并输出结果。,7.7稀疏矩阵的十字链表实现应用举例,7.7稀疏矩阵的十字链表