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

,Click to edit Master title style,Click to edit Master text styles,数组 零基础学数据结构,7.1,数组,数组是一种特殊的线性表，表中的元素可以是原子类型，也可以是一个线性表。本节主要介绍数组的定义和数组的抽象数据类型。,7.1.1 数组的定义,数组是由n个类型相同的数据元素组成的有限序列。其中，这n个数据元素占用一块地址连续的存储空间。数组中的数据元素可以是原子类型的，如整型、字符型、浮点型等，这种类型的数组称为一维数组；也可以是一个线性表，这种类型的数组称为二维数组。二维数组可以看成是线性表的线性表。,7.1.2 数组的抽象数据类型,1数据对象集合,2基本操作集合,7.2 数组的顺序表示与实现,一般情况下，不对数组进行插入和删除操作。如果建立了数组，则数组的维数与各维的长度不再改变，因此，数组采用的是顺序存储方式。本节的主要学习内容包括数组的顺序存储结构及顺序存储结构下的操作实现。,7.2.1 数组的顺序存储结构,在计算机中，存储器的结构是一维（线性）的结构。数组是一个多维的结构，如果要将一个多维的结构存放在一个一维的存储单元里，就必须先将多维的数组转换成一个一维的线性序列，才能将其存放在存储器中。,7.2.1 数组的顺序存储结构,数组的顺序存储结构类型定义描述如下：,#define MaxArraySize 3,#include/*标准头文件，包含va_start、va-arg、va_end宏定义*/,typedef struct,DataType*base;/*数组元素的基地址*/,int dim;/*数组的维数*/,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）销毁数组操作。,void DestroyArray(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）返回数组中指定的元素。,int GetValue(DataType*e,Array A,),/*返回数组中指定的元素，将指定的数组的下标的元素赋值给e*/,va_list ap;,int offset;,va_start(ap,A);,if(LocateArray(A,ap,&offset)=0)/*找到元素在数组中的相对位置*/,return 0;,va_end(ap);,*e=*(A.base+offset);/*将元素值赋值给e*/,return 1;,7.2.2 数组的基本运算,（4）数组的赋值操作。,int AssignValue(Array A,DataType e,.),/*数组的赋值操作。将e的值赋给的指定的数组元素*/,va_list ap;,int offset;,va_start(ap,e);,if(LocateArray(A,ap,&offset)=0)/*找到元素在数组中的相对位置*/,return 0;,va_end(ap);,*(A.base+offset)=e;/*将e赋值给该元素*/,return 1;,7.2.2 数组的基本运算,（5）数组的定位操作。,int LocateArray(Array A,va_list ap,int*offset),/*根据数组中元素的下标，求出该元素在A中的相对地址offset*/,int i,instand;,*offset=0;,for(i=0;im=M-n=M-len=0;,7.4.4 稀疏矩阵的三元组实现,（3）稀疏矩阵的复制操作。,void CopyMatrix(TriSeqMatrix M,TriSeqMatrix*N),/*由稀疏矩阵M复制得到另一个矩阵N*/,int i;,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是m,1,n,1,的矩阵，N是m,2,n,2,的矩阵，如果矩阵M的列数与矩阵N的行数相等，即n,1,=m,2,，则两个矩阵M和N是可以相乘的。,7.5.1 稀疏矩阵的相乘三元组表示,7.5.1 稀疏矩阵的相乘三元组表示,7.5.1 稀疏矩阵的相乘三元组表示,#define MaxSize 200,typedef int DataType;,typedef struct/*三元组类型定义*/,int i,j;,DataType e;,Triple;,typedef struct/*矩阵类型定义*/,Triple dataMaxSize;,int rposMaxSize;/*用于存储三元组中的每一行的第一非零元素的位置*/,int m,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 稀疏矩阵的十字链表表示,十字链表的类型描述如下：,typedef struct OLNode,int i,j;,DataType e;,struct OLNode*right,*down;,OLNode,*OLink;,typedef struct,OLink*rowhead,*colhead;,int m,n,len;,CrossList;,7.6.2 十字链表的实现,下面给出稀疏矩阵的十字链表的基本操作的算法实现。算法实现保存在文件”CrossList.h”中。,7.6.2 十字链表的实现,（1）稀疏矩阵的初始化操作。,void InitMatrix(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 稀疏矩阵的十字链表实现应用举例,1十字链表表示的稀疏矩阵相加算法,2测试程序部分,7.8,小结,本章主要介绍了一种扩展的线性表-数组。,数组是由n个相同数据类型的数据元素(a,0,a,1,a,2,a,n-1,)组成的有限序列。,三元组顺序表在实现创建、复制、转置、输出等操作比较方便，但是在进行矩阵的相加和相乘的运算中，时间的复杂度比较高。十字链表在各种操作实现时比较麻烦，但是在进行稀疏矩阵的相加和相乘等操作时，主要是进行插入和删除操作，因此，时间复杂度较低。,本章重点介绍了特殊矩阵的压缩存储和稀疏矩阵的压缩存储，并针对一个实例进行了详细的讲解。,