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

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