数据结构和算法

所需积分/C币:10 2013-01-08 17:22:59 8.88MB PDF
4
收藏 收藏
举报

计算机相关算法,c语言描述,数据结构,pdf文档,非常好的一本书
大彭两 j2,…,n),每个下标的取值范围是0≤j;≤b-1,b称为第i维的长度(i=1,2,…,n)。显 然,当n=1时,n维数组就退化为定长的线性表。反之,n维数组也可以看成是线性表的om 推广。由此,我们也可以从另一个角度来定义n维数组。 我们可以把二维数组看成是这样一个定长线性表:它的每个数据元素也是一个定长 线性長。例如。图5.1(a)所示是…个二维数组.以m行n列的矩阵形式表示。它可以看 成是一个线性表 A=(a,a1,…,a)(p=m-1或n-1) 其中每个数据元素a是一个列向量形式的线性表 a=(ao,a1;,…,am1,)0≤j≤n-1 (如图5.1(b)所示)或者a,是一个行向量形式的线性表 a iv ,dil, )0≤i≤m-1 (如图5.1(c)所示)。在C语言中,一个二维数组类型可以定义为其分量类型为一维数组 类型的一维数组类型,也就是说, type「 Clem A rave m n i 等价」 peclet Elcm'Type Array[n] typedef Arrayl Array2[m] 同理.一个n维数组类型可以定义为其数据元素为n-1维数组类型的一维数组类型。 tL d 4m1,0d-1,la1,2 (b) 4mxn=((doa1…ao,n1),( aidIl…an,n-1),…,(am-1,0am-1.,…am-1,n-1)) 图5.1二维数组图例 (a)矩阵形式表示;(b)列向量的一维数组;(c)行向量的一维数组 数组一旦被定义,它的维数和维界就不再改变。因此,除了结构的初始化和销毁之 外,数组只有存取元素和修改元素值的操作 5.2数组的顺序表示和实现 由于数组一般不作插入或删除操作,也就是说,一旦建立了数组,则结构中的数据元 素个数和元素之间的关系就不再发生变动。因此,采用顺序存储结构表示数组是自然的 事了。 由于存储单元是一维的结构,而数组是个多维的结构,则用一组连续存储单元存放数 组的数据元素就有个次序约定问题。例如图5.1(a)的二维数组可以看成如图5.1(c)的 www.topsage.com 维数组,也可看成如图5.1(b)的一维数组。对应地,对二维数组可有两种存储方式: 种以列序为主序( column major order)的存储方式,如图5.2(a)所示;一种是以行序为主 序( row major order)的存储方式,如图5.2(b)所示。在扩展 BASIC、PL/1、 COBOL、 PASCAL和C语言中,用的都是以行序为主序的存储结构,而在 FORTRAN语言中,用 的是以列序为主序的存储结构。 LOC(AO-LoC(aoo) LOC(AD loc(aoo) 01 A (1) loC(A=LoC(aon a01 LOC(AI)LOC(ato) a10 1 LOC(AM1FLOC(aon-1) LOC(Amb-LOC(am-lo A(1 A am-1.n-1 A(2=(A8,A1),…不(1) 1) A(2)=(A8),A A 1) 图5.2二维数组的两种存储方式 (a)以列序为主序;(b)以行序为主序 由此,对于数组,旦规定了它的维数和各维的长度,便可为它分配存储空间。反之, 只要给出一组下标便可求得相应数组元素的存储位置。下面仅用以行序为主序的存储结 构为例予以说明。 假设每个数据元素占L个存储单元,则二维数组A中任一元素a;的存储位置可由 下式确定 LOC(i, j)=LOC(0, 0)+(62 Itil (5-1) 式中,LOC(i,)是a的存储位置;LOC(0,0)是ao的存储位置,即二维数组A的起始存 储位置,也称为基地址或基址 将式(5-1)推广到一般情况,可得到n维数组的数据元素存储位置的计算公式: 92 www.topsage.com 大彭两 LOC(j1,j2,…,n)=LOC(0,0,…,0)+(b×…×b×j+b3×…×b×j2 +…+bn×jn-1+jn)L S age. com =LOC(0,0,…,0)+(∑Ⅱb+jn)L 可缩写成 LOC(1,j2,…,jn)=LOC0,0,…,0)+∑cj (5-2) 其中cn=L,c-1=bXc;,1<in 式(5-2)称为n维数组的映像函数。容易看出,数组元素的存储位置是其下标的线性 函数,一旦确定了数组的各维的长度,c就是常数。由于计算各个元素存储位置的时间相 等,所以存取数组中任一元素的时间也相等。我们称具有这一特点的存储结构为随机存 储结构。 下面是数组的顺序存储表示和实现。 ----数组的顺序存储表示 E include <stdarg.h>> ∥标准头文件,提供宏va- start,va.arg和va.end, ∥用于存取变长参数表 # define max.ARY.DM8∥假设数组维数的最大值为8 typedef struct base手 ∥数组元素基址由 InitArray分配 dim ∥数组维数 int bounds ∥数组维界基址由 InitArray分配 int constants; ∥数组映像函数常量基址,由 InitArray分配 Array ∥ 基本操作的函数原型说明-- Status InitArray(Array &A, int dim,.) ∥若维数dim和随后的各维长度合法,则构造相应的数组A并返回OK Status DestroyArray(Array &A); ∥销毁数组A。 Status Value(Array A, ElemType &e,); ∥A是n维数组,e为元素变量,随后是n个下标值。 ∥若各下标不超界,则e赋值为所指定的A的元素值,并返回O区。 Status Assign( Array &A, Elem Type e,.+); ∥A是n维数组,e为元素变量,随后是n个下标值 ∥若下标不超界则将e的值赋给所指定的A的元素,并返回oK。 ∥ 基本操作的算法描述 Status InitArray( Array &A, int dim,.)( ∥若维数dim和各维长度合法,则构造相应的数组A,并返回OK if (dim<1 dim MAX- ARRAY. DIM) return ERROR A dim= dim; A bounds =(int )malloc(dim sizeof(int)); if (! A bounds) exit(OVERFLOW); ∥若各维长度合法,则存入A. bounds,并求出A的元素总数 elemtotal elemtotal= 1 93 www.topsage.com va- start(ap, dim); ∥ap为va.1ist类型,是存放变长参数表信息的数组 for(1=0; i<dim; ++i)t unds[i]=va arg(ap, int); if(A bounds]<o) return UNDERFLOW elemtotal *=A bounds[i]; va- end( ap) A base =(ElemType )malloc(elemtotal Sizeof(Elem Type)); if( A base) exit(OVERFLOW) ∥求映像函数的常数c3,并存入A. constants-1],i=1,…,dim A constants=(int *)malloc(dim sizeof(int)); if ( A constants)exit(OVERFLOW); A constants[dim-1]=1;∥L=1,指针的增减以元素的大小为单位 for(主=dim-2;i>=0 1) A constants[ i]= A bounds[ i+1]* A. constantsLi+1]; return O Array &A)( ∥销毁数组A if (!A base ) return ErrOR A base =, NULL; if !(A bounds) return ERROR; Eree(A bounds), A bounds NULL if !(A constants) return ERROR; A constants= NULL; eturn OK Status Locate( Array A, va- list ap, int &off)i ∥若ap指示的各下标值合法,则求出该元素在A中相对地址off off =0 for(i=0: i<A dim; ++i)t ind= va- arg (ap, int); f(ind<o ind>>= A. boundsLi]) return OVERFLOW off+=A. constants订兴ind return OK Status value( Array A, ElemType &e, ..)i ∥A是n维数组,e为元素变量,随后是n个下标值。 ∥若各下标不超界,则e赋值为所指定的A的元素值,并返回OK。 va. start(ap, e); if ((result= Locate(A, ap, off))<=0)return result; e=*(A base+ off) return OK ·94· www.topsage.com 大彭两 Top Sage. com Status Assign( Array &A, ElemType e,.)( ∥A是n维数组,e为元素变量,随后是n个下标值。 ∥若下标不超界,则将e的值赋给所指定的A的元素,并返回oK。 va start(ap, e): if ((result= Locate(A, ap, off))<=0)return result: 并(A,base+off)=e; return OK 5.3矩阵的压缩存储 矩阵是很多科学与工程计算问题中研究的数学对象。在此,我们感兴趣的不是矩阵 本身,而是如何存储矩阵的元,从而使矩阵的各种运算能有效地进行。 通常,用高级语言编制程序时,都是用二维数组来存储矩阵元。有的程序设计语言中 还提供了各种矩阵运算,用户使用时都很方便。 然而,在数值分析中经常出现一些阶数很高的矩阵,同时在矩阵中有许多值相同的元 素或者是零元素。有时为了节省存储空间,可以对这类矩阵进行压缩存储。所谓压缩存 储是指:为多个值相同的元只分配一个存储空间;对零元不分配空间。 假若值相同的元素或者零元素在矩阵中的分布有一定规律,则我们称此类矩阵为特 殊矩阵;反之,称为稀疏矩阵。下面分别讨论它们的压缩存储。 5.3.1特殊矩阵 若n阶矩阵A中的元满足下述性质 1≤i,≤ 则称为n阶对称矩阵。 对于对称矩阵,我们可以为每一对对称元分配一个存储空间,则可将n2个元压缩存 储到n(n+1)/2个元的空间中。不失一般性,我们可以行序为主序存储其下三角(包括对 角线)中的元。 假设以一维数组sa[n(n+1)/2]作为n阶对称矩阵A的存储结构,则sa[k]和矩阵元 a之间存在着一一对应的关系: i(i-1) 2+j-1当i≥j k (5-3) 2 +i-1当i<j 对于任意给定一组下标(i,j),均可在sa中找到矩阵元aa,反之,对所有的k=0,1,2,…, (n+1) 2 1,都能确定sa[k]中的元在矩阵中的位置(i,j)。由此,称sa[n(n+1)/2]为n 阶对称矩阵A的压缩存储(见图5.3) www.topsage.com 11 21 31 an.] n(n (n+1) 2 图5.3对称矩阵的压缩存储 这种压缩存储的方法同样也适用于三角矩阵。所谓下(上)三角矩阵是指矩阵的上 (下)三角(不包括对角线)中的元均为常数c或零的n阶矩阵。则除了和对称矩阵一样, 只存储其下(上)三角中的元之外,再加一个存储常数c的存储空间即可。 在数值分析中经常出现的还有另一类特殊矩阵是对角矩阵。在这种矩阵中,所有的 非零元都集中在以主对角线为中心的带状区域中。即除了主对角线上和直接在对角线 上、下方若干条对角线上的元之外,所有其他的元皆为零。如图5.4所示。对这种矩阵 我们也可按某个原则(或以行为主,或以对角线的顺序)将其压缩存储到一维数组上。 a条对角线 0“11 行 (b) 图5.4对角矩阵 (a)一般情形;(b)三对角矩阵 在所有这些我们统称为特殊矩阵的矩阵中,非零元的分布都有一个明显的规律,从而 我们都可将其压缩存储到一维数组中,并找到每个非零元在一维数组中的对应关系 然而,在实际应用中我们还经常会遇到另一类矩阵,其非零元较零元少,且分布没有 定规律,我们称之为稀疏矩阵。这类矩阵的压缩存储就要比特殊矩阵复杂。这就是下 节我们要讨论的问题 5.3.2稀疏矩阵 什么是稀疏矩阵?人们无法给出确切的定义,它只是一个凭人们的直党来了解的概 念。假设在mXn的矩阵中,有t个元素不为零。令δt,称δ为矩阵的稀疏因子。 m×n 通常认为δ≤0.05时称为稀疏矩阵。矩阵运算的种类很多,在下列抽象数据类型稀疏矩 阵的定义中,只列举了几种常见的运算。 抽象数据类型稀疏矩阵的定义如下 ADT SparseMatrix( 数据对象:D={ai=1,2,…,m;j=1,2,…,n; a,∈ Elem set,m和n分别称为矩阵的行数和列数} 96 www.topsage.com 大彭两 数据关系:R={Row,Co1} Row={<a,a,+1>|1≤还≤m,1≤j≤n-1 Top Sage. com ={<a,,a1,1≤≤m-1,1≤j≤n 基本操作: CreateSMatrix(&M) 操作结果:创建稀疏矩阵 Destroy SMatrix( &M); 初始条件:稀疏矩阵M存在。 操作结果:销毁稀疏矩阵M PrintsMatrix(M); 初始条件:稀疏矩阵M存在。 操作结果:输出稀疏矩阵M。 CopySMatrix(M, &T); 初始条件:稀疏矩阵M存在。 操作结果:由稀疏矩阵M复制得到T AddSMatrix(M,N,&Q) 初始条件:稀疏矩阵M与N的行数和列数对应相等。 操作结果:求稀疏矩阵的和Q=M+N SubtMatrix(M,N,&Q) 初始条件:稀疏矩阵M与N的行数和列数对应相等。 操作结果:求稀疏矩阵的差Q=M-N MultsMatrix(M,N,&0) 初始条件:稀疏矩阵M的列数等于N的行数。 操作结果:求稀疏矩阵乘积Q=MxN TransposeSMatrix(M, &T), 初始条件:稀疏矩阵M存在。 操作结果:求稀疏矩阵M的转置矩阵T。 JADT SparseMatrix 如何进行稀疏矩阵的压缩存储呢? 按照压缩存储的概念,只存储稀疏矩阵的非零元。因此,除了存储非零元的值之外, 还必须同时记下它所在行和列的位置(i,j)。反之,一个三元组(i,j,a6)惟一确定了矩阵 A的一个非零元。由此,稀疏矩阵可由表示非零元的三元组及其行列数惟一确定。例如, 下列三元组表 ((1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4, 加上(6,7)这一对行、列值便可作为图5.5中矩阵M的另一种描述。而由上述三元组表 的不同表示方法可引出稀疏矩阵不同的压缩存储方法。 00-30015 01290000 12000180 0000000 30000140 9002400 T 00000 0024 0000 01800000 001400 1500 7000 7000 000 图5.5稀疏矩阵M和T 97 www.topsage.com 1.三元组顺序表 假设以顺序存储结构来表示三元组表,则可得稀疏矩阵的一种压缩存储方式—我 们称之为三元组顺序表 ∥ 稀疏矩阵的三元组顺序表存储表示 # define MAXSIzE12500∥假设非零元个数的最大值为12500 typedef struct f int 1·J ∥该非零元的行下标和列下标 ElemType TRiple E struct Triple data[ MAXSIZE+1];∥非零元三元组表,ata0未用 int mu, nu, tu: ∥矩阵的行数、列数和非零元个数 3 SMAtrix 在此,data域中表示非零元的三元组是以行序为主序顺序排列的,从下面的讨论中读者 容易看出这样做将有利于进行某些矩阵运算。下面将讨论在这种压缩存储结构下如何实 现矩的转置运算 转置运算是一种最简单的矩阵运算。对于…个m×n的矩阵M,它的转置矩阵T是 一个n×m的矩阵.且T(j)=M(,),1≤n,1≤jm。例如,图5.5中的矩阵M和 r互为转置矩阵。 显然,一个稀疏矩阵的转置矩阵仍然是稀疏矩阵。假设a和b是TSMaττiκ型的变 量,分别表示矩阵M和T。那么,如何由a得到b呢? 从分析a和b之间的差异可见只要做到:(1)将矩阵的行列值相互交换;(2)将每个三 元组中的i和j相互调换;(3)重排三元组之间的次序便可实现矩阵的转置。前二条是容 易做到的,关键是如何实现第三条。即如何使b.data中的三元组是以T的行(M的列) 为主序依次排列的。 v 12 3 15 14 18 24 2 24 6 4 7 63 14 a. data b data 可以有两种处理方法: (1)按照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置。换句话 说,按照矩阵M的列序来进行转置。为了找到M的每一列中所有的非零元素,需要对其三 元组表 a data从第一行起整个扫描一遍,由于a.data是以M的行序为主序来存放每个非零 元的,由此得到的恰是b.data应有的顺序。其具体算法描述如算法5.1所示。 98 www.topsage.com

...展开详情
试读 110P 数据结构和算法
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
xiaweijia123 这个数据结构算法很用,我收藏了。
2013-01-10
回复
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 领英

    绑定领英第三方账户获取
  • GitHub

    绑定GitHub第三方账户获取
  • 签到新秀

    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 技术圈认证(专家版)

    博客专家完成年度认证,即可获得
关注 私信
上传资源赚积分or赚钱
最新推荐
数据结构和算法 10积分/C币 立即下载
1/110
数据结构和算法第1页
数据结构和算法第2页
数据结构和算法第3页
数据结构和算法第4页
数据结构和算法第5页
数据结构和算法第6页
数据结构和算法第7页
数据结构和算法第8页
数据结构和算法第9页
数据结构和算法第10页
数据结构和算法第11页
数据结构和算法第12页
数据结构和算法第13页
数据结构和算法第14页
数据结构和算法第15页
数据结构和算法第16页
数据结构和算法第17页
数据结构和算法第18页
数据结构和算法第19页
数据结构和算法第20页

试读结束, 可继续阅读

10积分/C币 立即下载 >