数组 零基础学数据结构.pptx

7.1 7.1 数组数组数组是一种特殊的线性表，表中的元素可以是原子类型，也可以是一个线性表。本节主要介绍数组的定义和数组的抽象数据类型。第1页/共50页7.1.1 7.1.1 数组的定义数组的定义数组是由n个类型相同的数据元素组成的有限序列。其中，这n个数据元素占用一块地址连续的存储空间。数组中的数据元素可以是原子类型的，如整型、字符型、浮点型等，这种类型的数组称为一维数组；也可以是一个线性表，这种类型的数组称为二维数组。二维数组可以看成是线性表的线性表。第2页/共50页7.1.2 7.1.2 数组的抽象数据类型数组的抽象数据类型1数据对象集合2基本操作集合第3页/共50页7.2 7.2 数组的顺序表示与实现数组的顺序表示与实现一般情况下，不对数组进行插入和删除操作。如果建立了数组，则数组的维数与各维的长度不再改变，因此，数组采用的是顺序存储方式。本节的主要学习内容包括数组的顺序存储结构及顺序存储结构下的操作实现。第4页/共50页7.2.1 7.2.1 数组的顺序存储结构数组的顺序存储结构在计算机中，存储器的结构是一维（线性）的结构。数组是一个多维的结构，如果要将一个多维的结构存放在一个一维的存储单元里，就必须先将多维的数组转换成一个一维的线性序列，才能将其存放在存储器中。第5页/共50页7.2.1 7.2.1 数组的顺序存储结构数组的顺序存储结构数组的顺序存储结构类型定义描述如下：#defineMaxArraySize3#include/*标准头文件，包含va_start、va-arg、va_end宏定义*/typedefstructDataType*base;/*数组元素的基地址*/intdim;/*数组的维数*/int*bounds;/*数组的每一维之间的界限的地址*/int*constants;/*数组存储映像常量基地址*/Array;第6页/共50页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页/共50页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;第8页/共50页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;第9页/共50页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;第10页/共50页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;第11页/共50页7.2.3 7.2.3 数组的应用举例数组的应用举例下面通过一个例子来说明数组基本操作的用法。例7_1利用数组的基本操作实现对数组的初始化、赋值、返回数组的值及定位操作。定义一个二维数组B，并将B初始化，然后将数组B的值依次赋值给数组A，并将数组A的元素输出。第12页/共50页7.3 7.3 特殊矩阵的压缩存储特殊矩阵的压缩存储在许多科学与工程计算中会经常遇到矩阵运算的问题，在高级语言中，通常使用二维数组来存储矩阵。然而，在矩阵的运算中，往往在阶数很高的矩阵中存在许多相同的元素或值为零的元素。为了节省空间，需要将这些矩阵进行压缩存储。第13页/共50页7.3.1 7.3.1 对称矩阵的压缩存储对称矩阵的压缩存储如果一个n阶的矩阵A中的元素满足性质aij=aji(0i,jn-1)，则称这种矩阵为n阶对称矩阵。由于对称矩阵中的元素关于主对角线对称，因此，在对矩阵存储时，可以只存储对称矩阵中的上三角或者下三角的元素，使得对称的元素共享一个存储单元。第14页/共50页7.3.1 7.3.1 对称矩阵的压缩存储对称矩阵的压缩存储第15页/共50页7.3.2 7.3.2 三角矩阵的压缩存储三角矩阵的压缩存储三角矩阵分为两种：上三角矩阵和下三角矩阵。其中，下三角元素均为常数c或零的n阶矩阵称为上三角矩阵，上三角元素均为常数c或零的n阶矩阵称为下三角矩阵。第16页/共50页7.3.2 7.3.2 三角矩阵的压缩存储三角矩阵的压缩存储第17页/共50页7.3.3 7.3.3 对角矩阵的压缩存储对角矩阵的压缩存储对角矩阵，也称带状矩阵，是另一类特殊的矩阵。所谓对角矩阵，就是所有的非零元素都集中在以主对角线两侧的带状区域内（对角线的个数为奇数）。也就是说除了主对角线和主对角线两边的对角线外，其他元素的值均为0.第18页/共50页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。第19页/共50页7.4 7.4 稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵中的大多数元素是零，因此也需要进行压缩存储。本节的主要学习内容包括稀疏矩阵的定义、稀疏矩阵的抽象数据类型、稀疏矩阵的三元组表示及算法实现。第20页/共50页7.4.1 7.4.1 稀疏矩阵的定义稀疏矩阵的定义所谓稀疏矩阵，假设在mn矩阵中，有t个元素不为零，令=，为矩阵的稀疏因子，如果 ，则称矩阵为稀疏矩阵。也就是说，矩阵中存在大多数为零的元素，只有很少的非零元素，这样的矩阵是稀疏矩阵。第21页/共50页7.4.2 7.4.2 稀疏矩阵抽象数据类型稀疏矩阵抽象数据类型1数据对象集合2基本操作集合第22页/共50页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)第23页/共50页7.4.3 7.4.3 稀疏矩阵的三元组表示稀疏矩阵的三元组表示第24页/共50页7.4.3 7.4.3 稀疏矩阵的三元组表示稀疏矩阵的三元组表示三元组顺序表的类型定义如下。#defineMaxSize200typedefstruct/*三元组类型定义*/inti,j;DataTypee;Triple;typedefstruct/*矩阵类型定义*/TripledataMaxSize;intm,n,len;/*矩阵的行数，列数和非零元素的个数*/TriSeqMatrix;第25页/共50页7.4.4 7.4.4 稀疏矩阵的三元组实现稀疏矩阵的三元组实现下面给出稀疏矩阵的基本操作的算法实现。算法实现保存在文件”TriSeqMatrix.h”中。（1）创建稀疏矩阵操作。（2）销毁稀疏矩阵操作。voidDestroyMatrix(TriSeqMatrix*M)/*销毁稀疏矩阵操作.因为是静态分配，所以只需要将矩阵的行数，列数和个数置为0*/M-m=M-n=M-len=0;第26页/共50页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;第27页/共50页7.4.4 7.4.4 稀疏矩阵的三元组实现稀疏矩阵的三元组实现（4）稀疏矩阵的相加操作。（5）稀疏矩阵的相减操作。第28页/共50页7.4.4 7.4.4 稀疏矩阵的三元组实现稀疏矩阵的三元组实现（6）稀疏矩阵的转置操作。第29页/共50页7.4.4 7.4.4 稀疏矩阵的三元组实现稀疏矩阵的三元组实现第30页/共50页7.4.4 7.4.4 稀疏矩阵的三元组实现稀疏矩阵的三元组实现第31页/共50页7.5 7.5 稀疏矩阵的应用举例稀疏矩阵的应用举例在上一节学习了稀疏矩阵的定义及稀疏矩阵的三元组顺序存储的算法实现，这一节主要通过分析并实现两个矩阵的相乘的算法，来加强对稀疏矩阵知识的学习。第32页/共50页7.5.1 7.5.1 稀疏矩阵的相乘三元组表示稀疏矩阵的相乘三元组表示两个矩阵相乘是矩阵的一种常用的运算。假设矩阵M是m1n1的矩阵，N是m2n2的矩阵，如果矩阵M的列数与矩阵N的行数相等，即n1=m2，则两个矩阵M和N是可以相乘的。第33页/共50页7.5.1 7.5.1 稀疏矩阵的相乘三元组表示稀疏矩阵的相乘三元组表示第34页/共50页7.5.1 7.5.1 稀疏矩阵的相乘三元组表示稀疏矩阵的相乘三元组表示第35页/共50页7.5.1 7.5.1 稀疏矩阵的相乘三元组表示稀疏矩阵的相乘三元组表示#defineMaxSize200typedefintDataType;typedefstruct/*三元组类型定义*/inti,j;DataTypee;Triple;typedefstruct/*矩阵类型定义*/TripledataMaxSize;intrposMaxSize;/*用于存储三元组中的每一行的第一非零元素的位置*/intm,n,len;/*矩阵的行数，列数和非零元素的个数*/TriSeqMatrix;第36页/共50页7.5.2 7.5.2 稀疏矩阵的相乘三元组实现稀疏矩阵的相乘三元组实现1算法的测试部分2两个矩阵相乘的算法实现第37页/共50页7.6 7.6 稀疏矩阵的十字链表表示与实现稀疏矩阵的十字链表表示与实现采用三元组顺序表在进行两个稀疏矩阵的相加和相乘运算时，需要移动大量的元素，算法的时间复杂度也大大增加。因此，本节来学习稀疏矩阵的另一种存储结构-链式存储。第38页/共50页7.6.1 7.6.1 稀疏矩阵的十字链表表示稀疏矩阵的十字链表表示稀疏矩阵的链式存储，就是利用链表来表示稀疏矩阵，链表中的每个结点存储稀疏矩阵中的每个非零元素。每个结点包含5个域：3个数据域和两个指针域。其中3个数据域是i，j和e，分别表示非零元素的行号、列号和元素值；2个指针域是right域和down域，right指向同一行中的下一个非零元素，down指向同一列的非零元素。第39页/共50页7.6.1 7.6.1 稀疏矩阵的十字链表表示稀疏矩阵的十字链表表示第40页/共50页7.6.1 7.6.1 稀疏矩阵的十字链表表示稀疏矩阵的十字链表表示十字链表的类型描述如下：typedefstructOLNodeinti,j;DataTypee;structOLNode*right,*down;OLNode,*OLink;typedefstructOLink*rowhead,*colhead;intm,n,len;CrossList;第41页/共50页7.6.2 7.6.2 十字链表的实现十字链表的实现下面给出稀疏矩阵的十字链表的基本操作的算法实现。算法实现保存在文件”CrossList.h”中。第42页/共50页7.6.2 7.6.2 十字链表的实现十字链表的实现（1）稀疏矩阵的初始化操作。voidInitMatrix(CrossList*M)/*初始化稀疏矩阵*/M-rowhead=M-colhead=NULL;M-m=M-n=M-len=0;第43页/共50页7.6.2 7.6.2 十字链表的实现十字链表的实现（2）稀疏矩阵的创建操作。（3）稀疏矩阵的插入操作。（4）稀疏矩阵的销毁操作。第44页/共50页7.7 7.7 稀疏矩阵的十字链表实现应用举例稀疏矩阵的十字链表实现应用举例十字链表在稀疏矩阵的相加、相减和相乘操作是比较恰当的。本节通过两个稀疏矩阵的相加操作来说明稀疏矩阵的十字链表的使用。第45页/共50页7.7 7.7 稀疏矩阵的十字链表实现应用举例稀疏矩阵的十字链表实现应用举例例7_3例如有两个稀疏矩阵A和B，相加得到C，如图7.21所示。请利用十字链表实现两个稀疏矩阵的相加，并输出结果。第46页/共50页7.7 7.7 稀疏矩阵的十字链表实现应用举例稀疏矩阵的十字链表实现应用举例第47页/共50页7.7 7.7 稀疏矩阵的十字链表实现应用举例稀疏矩阵的十字链表实现应用举例1十字链表表示的稀疏矩阵相加算法2测试程序部分第48页/共50页7.8 7.8 小结小结本章主要介绍了一种扩展的线性表-数组。数组是由n个相同数据类型的数据元素(a0,a1,a2,an-1)组成的有限序列。三元组顺序表在实现创建、复制、转置、输出等操作比较方便，但是在进行矩阵的相加和相乘的运算中，时间的复杂度比较高。十字链表在各种操作实现时比较麻烦，但是在进行稀疏矩阵的相加和相乘等操作时，主要是进行插入和删除操作，因此，时间复杂度较低。本章重点介绍了特殊矩阵的压缩存储和稀疏矩阵的压缩存储，并针对一个实例进行了详细的讲解。第49页/共50页谢谢您的观看！第50页/共50页