《数据结构(C语言版).ppt》由会员分享，可在线阅读，更多相关《数据结构(C语言版).ppt（30页珍藏版）》请在三一办公上搜索。
1、数 据 结 构（C语言版）,严蔚敏、吴伟民编著清华大学出版社学习网站：,第5章 数组和广义表,主要内容：一、数组的定义二、数组的表示和实现三、矩阵的压缩存储四、广义表的定义五、广义表的存储结构,第5章 数组和广义表,数组是由n(n1)个具有相同数据类型的数据元素a1，a2，an组成的有序序列。这n个数据元素占用一块地址连续的存储空间。数组中的数据元素具有相同数据类型。数组是一种随机存取结构，给定一组下标，就可以访问与其对应的数据元素。数组中的数据元素个数是固定的。数组是一种特殊的线性表，表中的元素可以是原子类型，也可以是一个线性表。,数组的定义,数组中的数据元素可以是原子类型的，如整型、字符型
2、、浮点型等，这种类型的数组称为一维数组；也可以是一个线性表。二维数组可以看成是线性表的线性表。,第5章 数组和广义表,二、数组的表示和实现1、数组类型特点1)数组除了初始化和销毁外，只有存取元素和修改元素值的操作，不对数组进行插入和删除操作。2)数组是多维的结构，而存储空间是一个一维的结构。2、两种顺序映像方式1)以行序为主序(低下标优先)；2)以列序为主序(高下标优先)。,第5章 数组和广义表,第5章 数组和广义表,以行序为主序的求址公式：假设每个数据元素占L个存储单元，则二维数组A中任一元素aij的存储位置可由下式确定：LOC(i,j)=LOC(0,0)+(ni+j)*L式中，LOC(i,
3、j)是aij的存储位置，LOC(0,0)是a00的存储位置，即二维数组A的起始存储位置，也称为基地址或基址。b2是数组第二维的长度，即数组A(mn)中的列数n。,思考题：设有数组Ai,j,数组每个元素长度为3字节，i的值为1到8，j的值为1到10，且数组从内存首地址BA开始顺序存放。以列序为主存放时，元素A5，8的存储首地址为（）以行序为主存放时，元素A5，8的存储首地址为（）。,以列序为主序的求址公式：LOC(i,j)=LOC(0,0)+(jm+i)*L,第5章 数组和广义表,三、矩阵的压缩存储所谓的压缩存储是指：为多个值相同的元只分配一个存储空间；对零元不分配存储空间。若值相同的元素或零元
4、素在矩阵中的分布有一定规律，则称此类矩阵为特殊矩阵；反之称为稀疏矩阵。,特殊矩阵,(1)对称矩阵：,定义 若n阶矩阵A中的元满足下述性质：aijaji1i，jn则称为n阶对称矩阵。,第5章 数组和广义表,压缩存储 由于对称矩阵中的元素关于主对角线对称，因此，在对矩阵存储时，可以只存储对称矩阵中的上三角或者下三角的元素，使得对称的元素共享一个存储单元，则可将n2 个元压缩存储到n(n+1)/2个元的空间中。我们以行序为主序存储其下三角（包括对角线）中的元。,第5章 数组和广义表,有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，A11为第一元素，其存储地址为1，每个元素占一个地址空间，
5、求A75和A56的地址。,随堂练习,对角矩阵的压缩存储,对角矩阵,也称带状矩阵，是另一类特殊的矩阵。所谓对角矩阵，就是所有的非零元素都集中在以主对角线两侧的带状区域内（对角线的个数为奇数）。也就是说除了主对角线和主对角线两边的对角线外，其他元素的值均为0.,第5章 数组和广义表,2、稀疏矩阵(1)定义：假设 m 行 n 列的矩阵含 t 个非零元素，则称 为稀疏因子。通常认为 0.05 的矩阵为稀疏矩阵。,第5章 数组和广义表,(2)稀疏矩阵的存储：若按常规方法进行存储，零值元素会占了很大空间因此对于稀疏矩阵的存储通常采用以下两种方式：三元组表和十字链表进行存储。,第5章 数组和广义表,第5章
6、数组和广义表,第5章 数组和广义表,第5章 数组和广义表,四、广义表的定义,广义表中所包含的元素(包括原子和子表)的个数称为表的长 度。广义表中括号的最大层数称为表深(度)。,2、广义表表示,（1）广义表常用表示 E=()E是一个空表，其长度为0。L=(a，b)L是长度为2的广义表，它的两个元素都是原子，因此它是一个线性表 A=(x，L)=(x，(a，b)A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L。B=(A，y)=(x，(a，b)，y)B是长度为2的广义表，第一个元素是子表A，第二个元素是原子y。,C=(A，B)=(x，(a，b)，(x，(a，b)，y)C的长度为2，两个元素
7、都是子表。D=(a，D)=(a，(a，(a，()D的长度为2，第一个元素是原子，第二个元素是D自身，展开后它是一个无限的广义表。（2）广义表的深度一个表的深度是指表展开后所含括号的层数。【例】表L、A、B、C的深度为分别为1、2、3、4，表D的深度为。,取广义表头的操作是getHead（）取表尾的操作是getTail()，,随堂练习,1.设广义表L=()，()，试问GetHead(L)，GetTail(L)的值，求L的长度和深度各为多少?,GetHead(L)和GetTail(L)的值是()和()。L的长度和深度都是2。,2.广义表(a,(a,b),d,e,(i,j),k)的长度是_，深度是_
8、 3.设广义表L=（a,b,c），则L的长度和深度分别为（）。A.1和1 B.1和3 C.1和2 D.2和3,5,3,c,3.求下列广义表运算的结果：,(1)GetHead(p，h，w)GetTail(b，k，p，h)GetHead(GetTail(a，b)，(c，d)GetTail(GetHead(a，b)，(c，d),【解答】(1)GetHead(p,h,w)=p(2)GetTail(b,k,p,h)=(k,p,h)(3)GetHead(GetTail(a，b)，(c，d)=GetHead(c,d)=(c,d)(4)GetTail(GetHead(a，b)，(c，d)=GetTail(a,
9、b)=(b),第5章 数组和广义表,思考题：1、广义表L=（a，（b，c），进行Tail（L）操作后的结果为（）。A.c B.b，c C.（b，c）D.（b，c）2、已知广义表：A=（a,b），B=（A，A），C=（a,(b,A),B），则tail(head(tail(C)的运算结果为（）；3、已知广义表LS=（a，b，c）,（d，e，f），则运用head和tail 函数取出LS中原子e的运算表达式为:,D,(A),(head(tail(head(tail(LS),4.已知二维数组A35，其每个元素占3个存储单元，并且A00的存储地址为1200。求元素A13的存储地址（分别对以行序和列序为主序存储进行讨论），该数组共占用多少个存储单元？,【解答】LOC(A13)=1200+(1*5+3)*3=1224(按行序存储)LOC(A13)=1200+(3*3+1)*3=1230(按列序存储),中国网页设计-数据结构,
