数据结构C语言版.ppt

中国网页设计 ,数 据 结 构 （C语言版）,严蔚敏、吴伟民编著 清华大学出版社 学习网站：/list.asp?id=301,中国网页设计 ,第5章 数组和广义表,主要内容： 一、数组的定义 二、数组的表示和实现 三、矩阵的压缩存储 四、广义表的定义 五、广义表的存储结构,中国网页设计 ,第5章 数组和广义表,数组是由n(n1)个具有相同数据类型的数据元素a1，a2，an组成的有序序列。这n个数据元素占用一块地址连续的存储空间。 数组中的数据元素具有相同数据类型。 数组是一种随机存取结构，给定一组下标，就可以访问与其对应的数据元素。 数组中的数据元素个数是固定的。 数组是一种特殊的线性表，表中的元素可以是原子类型，也可以是一个线性表。,中国网页设计 ,数组的定义,数组中的数据元素可以是原子类型的，如整型、字符型、浮点型等，这种类型的数组称为一维数组；也可以是一个线性表。二维数组可以看成是线性表的线性表。,中国网页设计 ,第5章 数组和广义表,二、数组的表示和实现 1、数组类型特点 1)数组除了初始化和销毁外，只有存取元素和修改元素值的操作，不对数组进行插入和删除操作。 2) 数组是多维的结构，而存储空间是一个一维的结构。 2、两种顺序映像方式 1)以行序为主序(低下标优先)； 2)以列序为主序(高下标优先)。,中国网页设计 ,第5章 数组和广义表,中国网页设计 ,第5章 数组和广义表,以行序为主序的求址公式： 假设每个数据元素占L个存储单元，则二维数组A中任一元素aij的存储位置可由下式确定： LOC(i, j) = LOC(0, 0) + (ni + j)*L 式中，LOC(i, 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章 数组和广义表,三、矩阵的压缩存储 所谓的压缩存储是指：为多个值相同的元只分配一个存储空间；对零元不分配存储空间。 若值相同的元素或零元素在矩阵中的分布有一定规律，则称此类矩阵为特殊矩阵；反之称为稀疏矩阵。,中国网页设计 ,特殊矩阵,(1)对称矩阵：,定义 若n阶矩阵A中的元满足下述性质： aijaji 1i，jn 则称为n阶对称矩阵。,中国网页设计 ,第5章 数组和广义表,压缩存储 由于对称矩阵中的元素关于主对角线对称，因此，在对矩阵存储时， 可以只存储对称矩阵中的上三角或者下三角的元素，使得对称的元素共享一个存储单元，则可将n2 个元压缩存储 到n(n+1)/2个元的空间中。我们以行序为主序存储其下三角（包 括对角线）中的元。,中国网页设计 ,第5章 数组和广义表,中国网页设计 ,有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，A11为第一元素，其存储地址为1，每个元素占一个地址空间，求A75和A56的地址。,随堂练习,中国网页设计 ,对角矩阵的压缩存储,对角矩阵,也称带状矩阵，是另一类特殊的矩阵。所谓对角矩阵，就是所有的非零元素都集中在以主对角线两侧的带状区域内（对角线的个数为奇数）。也就是说除了主对角线和主对角线两边的对角线外，其他元素的值均为0.,中国网页设计 ,第5章 数组和广义表,2、稀疏矩阵 (1) 定义：假设 m 行 n 列的矩阵含 t 个非零元素， 则称 为稀疏因子。 通常认为 0.05 的矩阵为稀疏矩阵。,中国网页设计 ,第5章 数组和广义表,(2) 稀疏矩阵的存储： 若按常规方法进行存储，零值元素会占了很大空间 因此对于稀疏矩阵的存储通常采用以下两种方式： 三元组表和十字链表进行存储。,中国网页设计 ,第5章 数组和广义表,中国网页设计 ,第5章 数组和广义表,中国网页设计 ,第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，两个元素都是子表。 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)的长度是_ ，深度是_ 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,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.