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

第7章数组数组是一种扩展的线性数据结构。线性表、栈、队列、串的数据元素都是不可再分的原子类型，而数组中的数据元素是可以再分的。数组可以分为一维数组和多维数组，一维数组中的元素是由原子构成的，多维数组中的元素又是一个线性表。因此，数组是一种特殊的线性表。7.1数组数组是一种特殊的线性表，表中的元素可以是原子类型，也可以是一个线性表。本节主要介绍数组的定义和数组的抽象数据类型。7.1.1数组的定义数组是由n个类型相同的数据元素组成的有限序列。其中，这n个数据元素占用一块地址连续的存储空间。数组中的数据元素可以是原子类型的，如整型、字符型、浮点型等，这种类型的数组称为一维数组；也可以是一个线性表，这种类型的数组称为二维数组。二维数组可以看成是线性表的线性表。a0,0a0,1…a0,n-1a1,0a1,1…a1,n-1am-1,0am-1,1…am-1,n-1………nmA=(qm-1q1q0…B)a0,0a0,1…a0,n-1a1,0a1,1…a1,n-1am-1,0am-1,1…am-1,n-1………nmAA=(p0p1…pn-1)7.1.2数组的抽象数据类型1．数据对象集合2．基本操作集合7.2数组的顺序表示与实现一般情况下，不对数组进行插入和删除操作。如果建立了数组，则数组的维数与各维的长度不再改变，因此，数组采用的是顺序存储方式。本节的主要学习内容包括数组的顺序存储结构及顺序存储结构下的操作实现。7.2.1数组的顺序存储结构在计算机中，存储器的结构是一维（线性）的结构。数组是一个多维的结构，如果要将一个多维的结构存放在一个一维的存储单元里，就必须先将多维的数组转换成一个一维的线性序列，才能将其存放在存储器中。a0,0a0,1a0,n-1a1,0a1,1a1,n-1am-1,0am-1,1am-1,n-1…………a0,0a1,0am-1,0a0,1a1,1am-1,1a0,n-1a1,n-1am-1,n-1…………以行为主序的数组存放形式以列为主序的数组存放形式第一行第二行第m行第一列第二列第n列7.2.1数组的顺序存储结构数组的顺序存储结构类型定义描述如下：#defineMaxArraySize3#includestdarg.h/*标准头文件，包含va_start、va-arg、va_end宏定义*/typedefstruct{DataType*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,&offset)==0)/*找到元素在数组中的相对位置*/return0;va_end(ap);*e=*(A.base+offset);/*将元素值赋值给e*/return1;}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数组的基本运算（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(instand0||instand=A.bounds[i])return0;*offset+=A.constants[i]*instand;}return1;}7.2.3数组的应用举例下面通过一个例子来说明数组基本操作的用法。例7_1利用数组的基本操作实现对数组的初始化、赋值、返回数组的值及定位操作。定义一个二维数组B，并将B初始化，然后将数组B的值依次赋值给数组A，并将数组A的元素输出。7.3特殊矩阵的压缩存储在许多科学与工程计算中会经常遇到矩阵运算的问题，在高级语言中，通常使用二维数组来存储矩阵。然而，在矩阵的运算中，往往在阶数很高的矩阵中存在许多相同的元素或值为零的元素。为了节省空间，需要将这些矩阵进行压缩存储。7.3.1对称矩阵的压缩存储如果一个n阶的矩阵A中的元素满足性质aij=aji(0≤i,j≤n-1)，则称这种矩阵为n阶对称矩阵。由于对称矩阵中的元素关于主对角线对称，因此，在对矩阵存储时，可以只存储对称矩阵中的上三角或者下三角的元素，使得对称的元素共享一个存储单元。a0,0a0,1…a0,n-1a1,0a1,1…a1,n-1an-1,0an-1,1…an-1,n-1………nnAa0,0a1,0a1,1an-1,0an-1,1…an-1,n-1……nnA对称阵下三角矩阵7.3.1对称矩阵的压缩存储jii2)1(*ijj2)1(k=当i≥j当ija00a10a11a20…an-1,0…an-1,n-1k=01232)1(*nn12)1(*nn7.3.2三角矩阵的压缩存储三角矩阵分为两种：上三角矩阵和下三角矩阵。其中，下三角元素均为常数c或零的n阶矩阵称为上三角矩阵，上三角元素均为常数c或零的n阶矩阵称为下三角矩阵。a0,0a0,1…a0,n-1a1,1…a1,n-1an-1,n-1…nnAa0,0a1,0a1,1an-1,0an-1,1…an-1,n-1……nnA上三角矩阵下三角矩阵CC7.3.2三角矩阵的压缩存储ijini2)12(*2)1(*nnk=当i≤j当ijjii2)1(*2)1(*nnk=当i≥j当ij上三角矩阵下三角矩阵7.3.3对角矩阵的压缩存储对角矩阵，也称带状矩阵，是另一类特殊的矩阵。所谓对角矩阵，就是所有的非零元素都集中在以主对角线两侧的带状区域内（对角线的个数为奇数）。也就是说除了主对角线和主对角线两边的对角线外，其他元素的值均为0.76000091011000057200004560000173000051366Aa00a01a10a11a12a21a22a23…an-1,n-1k=01233*3n矩阵45677.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。j-i=当ij当i=j-101当ij7.4稀疏矩阵的压缩存储稀疏矩阵中的大多数元素是零，因此也需要进行压缩存储。本节的主要学习内容包括稀疏矩阵的定义、稀疏矩阵的抽象数据类型、稀疏矩阵的三元组表示及算法实现。7.4.1稀疏矩阵的定义所谓稀疏矩阵，假设在m×n矩阵中，有t个元素不为零，令=，为矩阵的稀疏因子，如果，则称矩阵为稀疏矩阵。也就是说，矩阵中存在大多数为零的元素，只有很少的非零元素，这样的矩阵是稀疏矩阵。nmt0009000030000000720007000-2000047000000050076M05.005.07.4.2稀疏矩阵抽象数据类型1．数据对象集合2．基本操作集合7.4.3稀疏矩阵的三元组表示为了实现压缩存储，可以只存储稀疏矩阵的非零的元素。在存储稀疏矩阵中的非零元素时，还必须存储非零元素对应的行和列的位置(i,j)。也就是说存储一个非零元素需要存储元素的行号、列号和元素值，即通过存储(i,j,aij)唯一确定一个非零的元素。ije非零元素的行号非零元素的列号非零元素的值((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稀疏矩阵的三元组表示ije03911322723230734-2424437545123456780k7.4.3稀疏矩阵的三元组表示三元组顺序表的类型定义如下。#defineMaxSize200typedefstruct/*三元组类型定义*/{inti,j;DataTypee;}Triple;typedefstruct/*矩阵类型定义*/{Tripledata[MaxSize];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;iM.len;i++)/*把稀疏矩阵M的非零元素的行号、列号及元素值依次赋值给矩阵N的行号、列号及元素值*/{N-data[i].i=M.data[i].i;N-data[i].j=M.data[i].j;N-data[i].e=M.data[i].e;}}7.4.4稀疏矩阵的三元组实现（4）稀疏矩阵的相加操作。（5）稀疏矩阵的相减操作。7.4.4稀疏矩阵的三元组实现（6）稀疏矩阵的转置操作。ije03911322723230734-2424437545123456780kije30911322732203743-2244347455123456780kij转置前转置后(i,j,e)j,i,e矩阵M矩阵N7.4.4稀疏矩阵的三元组实现ije03911322723230734-2424437545123456780kije03711322724430932234743-2455123456780k三元组顺序表M三元组顺序表N7.4.4稀疏矩阵的三元组实现列号col0123456num[col]1123200position[col]0124799