《数据结构C语言版第五章课件严蔚敏.pptx》由会员分享，可在线阅读，更多相关《数据结构C语言版第五章课件严蔚敏.pptx（37页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、l数组是n(n1)个相同类型数据元素a0,a1,an-1构成的有限序列,且该有限序列存储在一块地址连续的内存单元中。l数组的定义类似于采用顺序存储结构的线性表，是线性表在维数上的扩张，也就是线性表中的元素又是一个线性表。ln维数组，bi是第i维的长度，则n维数组共有 个数据元素，每个元素受n个关系的制约，就单个关系而言，这n个关系仍然是线性的。1.数组的定义和运算 第1页/共37页l数组具有以下性质：(1)(1)数组中的数据元素数目固定。一旦定义了一个 数组,其数据元素数目不再有增减变化。(2)(2)数组中的数据元素具有相同的数据类型。(3)(3)数组中的每个数据元素都和一组惟一的下标值对 应
2、。(4)(4)数组是一种随机存储结构。可随机存取数组中的 任意数据元素。l数组的基本操作 (1)取值 Value(A,&e,index1,.,indexn)(2)赋值Assign(&A,e,index1,indexn)第2页/共37页2.2.数组的存储结构l一维数组中,LOC(aLOC(a0 0)确定,每个数据元素占用L L个存储单元,则任一数据元素a ai i的存储地址LOC(aLOC(ai i)就可由以下公式求出：LOC(aLOC(ai i)=LOC(a)=LOC(a0 0)+i*L(0in-1)+i*L(0in-1)l二维数组,由于计算机的存储结构是线性的,如何用线性的存储结构存放二维数
3、组元素就有一个行列次序排放问题。第3页/共37页二维数组通常可以描述为两种形式 :以行序为主序:PASCAL、C可以看成 A=(0，1，m-1-1 ).其中 i 是一个行向量形式的线性表，0im-1-1 i =(ai0，ai1，ai n-1-1).a00 a01 a02 a0,n-1-1a10 a11 a12 a1 1,n-1-1am-1-1,0 am-1-1,1 1 am-1-1,2 am-1-1,n-1-1.Amn =第4页/共37页可以看成 A=(0，1，n-1-1 ).其中 j 是一个列向量形式的线性表，0jn-1-1 j =(a0j，a1j，am-1-1j ).a00 a01 a02
4、 a0,n-1-1a10 a11 a12 a1 1,n-1-1am-1-1,0 am-1-1,1 1 am-1-1,2 am-1-1,n-1-1.Amn =以列序为主序:FORTRAN第5页/共37页对于数组，一旦规定了维数和维界，如何计算数组元素的存储位置。a00a01a0,n-1-1a10a11a1 1,n-1-1am-1-1,0 0am-1-1,n-1-1am-1-1,1 1 0 1 m-1-1设数组以行序为主序。设二维数组 A(mn)其数组元素 aij 的存储位置为LOC(i，j)=LOC(0，0)其中，LOC(0，0)是a00的存储位置；L是每个数组元素占用的存储单元数；L例，LOC
5、(1，1)=LOC(0，0)+(n1+1)L+(ni+j)L第6页/共37页ln维数组每一元素对应下标(j1,j2,jn)，0jibi-1，bi为第i维的长度。以行序为主序。LOC(j1,j2,jn)=LOC(0,0,0)+(bnb2j1+bnb3j2+bnjn-1+jn)L第7页/共37页l例:对二维数组float a54float a54计算：(1)(1)数组a a中的数组元素数目；(2)(2)若数组a a的起始地址为2000,2000,且每个数组元素长度为3232位(即4 4个字节),),数组元素a32a32的内存地址。元素数目共有5*4=20个。C语言采用行序为主序的存储方式,则有：L
6、OC(a3,2)=LOC(a0,0)+(i*n+j)*k =2000+(3*4+2)*4=2056。第8页/共37页3.矩阵的压缩存储 l特殊矩阵（对称矩阵、三角矩阵、对角矩阵）特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵,为了节省存储空间,特别是在高阶矩阵的情况下,可以利用特殊矩阵的规律,对它们进行压缩存储,也就是说,使多个相同的非零元素共享同一个存储单元,对零元素不分配存储空间。第9页/共37页l对称矩阵的压缩存储若一个n n阶方阵A A中的元素满足ai,j=aj,i(1i,jn),则称其为n n阶对称矩阵。（1 1）只存储对称矩阵中上三角或下三角中的元素,（2 2）将n2个元素压缩
7、存储到n(n+1)/2个元素的空间中，以一个一维数组作为A A的存储空间。第10页/共37页 n2个元素 n(n+1)/2个元素 aij(1i,jn)Bn(n+1)/2 l1+2+(i-1)+j-1；laij aji a11a21a22a31anna12=a13=k=0123n(n+1)2-1第11页/共37页l下三角矩阵的压缩存储 Bn(n+1)/2+1 Ck=0123n(n+1)2-1a11a21a22a31annca12,a13 第12页/共37页l对角矩阵：所有的非零元都集中在以主对角线为中心 的带状区域内。半带宽为半带宽为b b的对角矩阵的对角矩阵 第13页/共37页共有3n-2个非
8、零元。主对角线左下方的元素下标有关系式：i=j+1 k=3(i-1)-1+1-1=3(i-1)-1=2(i-1)+i-2=2(i-1)+j-1.主对角线上的元素下标有关系式：i=j k=3(i-1)-1+2-1=3(i-1)=2(i-1)+i-1=2(i-1)+j-1.主对角线右上方的元素下标有关系式：i=j-1 k=3(i-1)-1+3-1=3(i-1)+1=2(i-1)+i=2(i-1)+j-1.l三对角矩阵B3n-2;k=2(i-1)+j-1;第14页/共37页l稀疏矩阵 非零元较零元少，且没有一定规律。mn的矩阵，有t个非零元，矩阵的稀疏因子：=t/(m*n)，当0.05时为稀疏矩阵。
9、压缩存储，只存储非零元三元组顺序表(i，j，ai,j)行逻辑链接的顺序表十字链表(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)第15页/共37页#define MaxSize 100 /*矩阵中非零元素最多个数矩阵中非零元素最多个数*/typedef struct int i;/*行号行号*/int j;/*列号列号*/ElemType e;/*元素值元素值*/Triple;/*三元组定义三元组定义*/typedef struct int rows;/*行数行数*/int cols;/*列数列数*/i
10、nt nums;/*非零元素个数非零元素个数*/Triple dataMaxSize+1;/*data0未用未用*/TSMatrix;/*三元组顺序表定义三元组顺序表定义*/第16页/共37页l用三元组表实现稀疏矩阵的转置运算 一个6*7的矩阵A，以行序为主序顺序排列第17页/共37页l矩阵的转置，方法一：第18页/共37页l Status TransposeSMatrix(TSMatrix A,TSMatrix&B)B.rows=A.cols;B.cols=A.rows;B.nums=A.nums;if(B.nums!=0)q=1;/*q为B.data的下标*/for(col=1;col=A
11、.cols;col+)for(p=1;p=A.nums;p+)/*p为A.data的下标*/if(A.datap.j=col)B.dataq.i=A.datap.j;B.dataq.j=A.datap.i;B.dataq.e=A.datap.e;q+;return OK;第19页/共37页方法1时间复杂度：O(cols*nums)当非零元个数nums和cols*rows同数量级时，O(rows*cols2)仅适用于numsrows*cols.常规存储方式时，实现矩阵转置的经典算法如下：for(i=0;im;i+)for(j=0;j n;j+)Ti j=Mji;O(cols*rows)第20页/
12、共37页l方法二：依次按三元组表A(6*7)的次序进行转置，转置后直接放到三元组表B的正确位置上。这种转置算法称为快速转置算法。col 1 2 3 4 5 6 7 numcolcpotcol22210101357889numcol:A中第col列非零元的个数。cpotcol:B中第col行第一个非零元 在B中的位置第21页/共37页lStatus FastTranSMatrix(TSMatrix A,TSMatrix&B)B.rows=A.cols;B.cols=A.rows;B.nums=A.nums;if(B.nums)for(col=1;col=A.cols;+col)numcol=0;
13、for(t=1;t=A.nums;+t)+numA.datat.j;cpot1=1;for(col=2;col=A.cols;+col)cpotcol=cpotcol-1+numcol-1;for(p=1;p=A.nums;+p)col=A.datap.j;q=cpotcol;B.dataq.i=A.datap.j;B.dataq.j=A.datap.i;B.dataq.e=A.datap.e;+cpotcol;return OK;O(cols+nums)当nums和cols*rows同数量级时O(rows*cols)第22页/共37页 row col e12345678 1 3 -3 3 1
14、 9 2 1 12 cpot1cpot2cpot2cpot3cpot3cpot4cpot6 6 3 14 3 4 24 2 5 18 1 6 15 4 6 -7 第23页/共37页小结小结基本学习要点如下：基本学习要点如下：(1)理解数组和一般线性表之间的差异。理解数组和一般线性表之间的差异。(2)重重点点掌掌握握数数组组的的顺顺序序存存储储结结构构和和元元素素地地址址计计算算方法。方法。(3)掌掌握握各各种种特特殊殊矩矩阵阵如如对对称称矩矩阵阵、上上、下下三三角角矩矩阵和对角矩阵的压缩存储方法。阵和对角矩阵的压缩存储方法。(4)掌掌握握稀稀疏疏矩矩阵阵的的各各种种存存储储结结构构以以及及基基
15、本本运运算算实实现算法。现算法。(5)灵灵活活运运用用数数组组这这种种数数据据结结构构解解决决一一些些综综合合应应用用问题。问题。第24页/共37页l练习：将一个A1.100,1.100的三对角矩阵，按行优先存入一维数组B1.298，A中元素a66,65在B数组中的位置k=?。在主对角线左下方，65*3-1+1=195。第25页/共37页l作业：5.2 5.25第26页/共37页1.广义表的定义（列表）广义表是线性表的推广，是由零个或多个单元素或子表所 组成的有限序列。LS=(a1,a2,ai,an)ai：是单个数据元素,则ai是广义表的原子；如果ai是一个广义表,则ai是广义表的子表。规定用
16、小写字母表示原子,用大写字母表示广义表的 表名。l广义表与线性表的区别：线性表的成份都是结构上不可分的单个数据元素，而广义表的成份即可以是单元素，也可以是有结构的表，其定义是递归的定义。5.4 广义表第27页/共37页l广义表的长度：广义表中所含元素的个数n,n0。l广义表的深度：广义表展开后所含的括号的最大层数。（广义表中括号嵌套的最大次数，广义表中括弧的重数）第28页/共37页lD=()空表，长度为0，深度为1。lA=(a,(b,c)长度为2，第一个元素为原子a，第二个元素为子表(b,c)，深度为2。lB=(A,A,D)长度为3，其前两个元素为表A，第三个元素为空表D，深度为3。lC=(a
17、,C)长度为2递归定义的广义表，C相当于无穷表C=(a,(a,(a,)，深度无限。递归表的深度是无穷值,长度是有限值。lF=(a,(a,b),(a,b),c)长度为1，深度为4。第29页/共37页l广义表的表头(Head)和表尾(Tail)：当广义表非空时，称第一个元素a1为广义表的表头，其余元素组成的表(a2,a3,an)称为广义表的表尾。表头可能是原子，也可能是广义表，但表尾一定是广义表。l广义表的图形表示 用方框表示原子，用圆圈表示广义表。第30页/共37页A=();B=(e);C=(a,(b,c,d)D=(A,B,C);E=(a,(a,b),(a,b),c)第31页/共37页2.广义表
18、的基本操作l取表头 GetHead(LS)=a1。l取表尾 GetTail(LS)=(a2,a3,an)。B=(e)GetHead(B)=e;GetTail(B)=().A=(a,(b,c),d,e)GetHead(GetHead(GetTail(A)=GetHead(GetHead(b,c),d,e)=GetHead(b,c),d,e)=(b,c).A=();B=()A空表，长度0，深度1，无表头和表尾；B长度1，深度2，表头()，表尾()。第32页/共37页3.广义表的存储结构 广义表是一种递归的数据结构,因此很难为每个广义表分配固定大小的存储空间,所以其存储结构只好采用动态链式结构。l广义表的头尾链表存储表示l广义表的扩展线性链表存储表示第33页/共37页C=(a,(b,c,d)(a,(b,c,d)(b,c,d)(b,c,d)(c,d)(d)l广义表的头尾链表存储表示第34页/共37页C=(a,(b,c,d)(b,c,d)l广义表的扩展线性链表存储表示（带表头结点）第35页/共37页l作业：5.10 第36页/共37页感谢您的观看！第37页/共37页