数据结构第五章 数组和广义表.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章,数组和广义表,本章主要介绍下列内容：,数组的定义、基本运算和存储结构,特殊矩阵的压缩存储,广义表的基本概念,5.1,多维数组,5.2,矩阵压缩存储,5.3,广义表,章节安排,5.1,数组,5.1.1,数组的定义和基本运算,数组的特点是每个数据元素又可以是一个线性表结构。因此，数组结构可以简单地定义为：若线性表中的数据元素为非结构的简单元素，则称为一维数组，即为,向量,；若一维数组中的数据元素又是一维数组结构，则称为二维数组；依次类推，若二维数组中的元素又是一个一维数组结构，则称作三维数组。,结论：线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。举例：,图,4-3,其中，,A,是数组结构的名称，整个数组元素可以看成是由,m,个行向量,或,n,个列向量,组成，其元素总数为,m,n,。在,C,语言中，二维数组中的数据元素可以表示成,a,表达式,1,表达式,2,，表达式,1,和表达式,2,被称为下标表达式，比如，,aij,。,数组结构在创建时就确定了组成该结构的行向量数目和列向量数目，因此，在数组结构中不存在插入、删除元素的操作。,二维数组结构的基本操作：,（,1,）给定一组下标，修改该位置元素的内容,Assign(A,item,index1,index2),（,2,）,给定一组下标，返回该位置的元素内容,Value(A,item,index1,index2),5.1.2,数组的存储结构,从理论上讲，数组结构也可以使用两种存储结构，即,顺序存储结构,和,链式存储结构,。然而，由于数组结构没有插入、删除元素的操作，所以使用顺序存储结构更为适宜。换句话说，一般的数组结构不使用链式存储结构。,组成数组结构的元素可以是多维的，但存储数据元素的,内存单元地址是一维的,，因此，在存储数组结构之前，需要解决将多维关系映射到一维关系的问题。举例：,第,0,行 第,1,行 第,m-1,行,a),按行存储,第,0,列 第,1,列 第,n-1,列,b),按列存储,二维数组,(,Amn,),loc(a,ij,)=loc(a,00,)+(i*n+j)*d,三维数组,(,Amnp,),loc(a,ijk,)=loc(a,000,)+(i*n*p+j*,p+k,)*d,多维数组,地址确定,5.2,矩阵的压缩存储,矩阵是在很多科学与工程计算中遇到的数学模型。在数学上，矩阵是这样定义的：它是一个由,mn,个元素排成的,m,行（横向）,n,列（纵向）的表。下面就是一个矩阵：,5.2.1,对称（三角）矩阵的存储,(1),三角矩阵链式存储,下三角,三角矩阵,5.2.1,对称（三角）矩阵的存储,(2),三角矩阵顺序存储,n-1,元素个数,:i+1,n(n+1)/2,i,0,上三角？,5.2.1,对称（三角）矩阵的存储,对称矩阵,1 5 1 3 7,5 0 8 0 0,1 8 9 2 6,3 0 2 5 1,7 0 6 1 3,a,00,a,10,a,11,a,20,a,21,a,22,a,n-1 0,a,n-1 1,a,n-1 2,a,n-1 n-1,5.2.2,稀疏矩阵的压缩存储,表示稀疏矩阵的三元组,(0,2,11),，,(0,4,17),，,(1,1,20),，,(3,0,19),，,(3,5,28),，,(4,4,50),行号,列号,元素值,row,column,value,稀疏矩阵,5.2.2,稀疏矩阵的压缩存储,（,1,）稀疏矩阵的三元组顺序表实现,（,2,）三元组链表实现,三元组单链表,行,/,列的单链表,（,3,）,十字链表,5.3,广义表,线性表,N,个,(n=0),元素,a1,、,a2,、,an,的有限序列，其中元素是原子项。,广义表,线性表的推广,N,个,(n=0),元素,a1,、,a2,、,an,的有限序列，其中,ai,或是原子项或是一个广义表。,5.3,广义表,5.3.1,广义表抽象数据类型,GList,=(,a,0,a,1,a,n-1,),中国,(,北京,上海,江苏,(,南京,苏州,),浙江,(,杭州,),广东,(,广州,),5.3.2,广义表的存储结构,广义表的双链表示,习 题 五,什么是广义表？请简述广义表与线性表的区别？,一个广义表是,(a,(a,b),d,e,(a,(i,j),k),，,请画出该广义表的链式存储结构。,设有二维数组,a68,，每个元素占相邻的,4,个字节，存储器按字节编址，已知,a,的起始地址是,1000,，试计算：,数组,a,的最后一个元素,a57,起始地址；,按行序优先时，元素,a46,起始地址；,按行序优先时，元素,a46,起始地址。,0 3 0 0 0 0 0 0,0 0 0 0 0 0 0 0,-3 0 0 0 0 0 0 4,0 0 2 0 0 2 0 0,0 18 0 0 0 0 0 0,0 0 0 0 4 0 5 0,A=,0 0-3 0 0 0 0 0,设,A,和,B,是稀疏矩阵，都以三元组作为存储结构，请写出矩阵相加的算法，其结果存放在三元组表,C,中，并分析时间复杂度。,设有稀疏矩阵,B,如下图所示，请画出该稀疏矩阵的三元组表和十字链表存储结构。,