数据结构（C语言版）

《数据结构（C语言版）》由会员分享，可在线阅读，更多相关《数据结构（C语言版）（30页珍藏版）》请在金锄头文库上搜索。

1、数 据 结 构 （C语言版）严蔚敏、吴伟民编著 清华大学出版社 学习网站： http:/ 第5章 数组和广义表 主要内容： 一、数组的定义 二、数组的表示和实现 三、矩阵的压缩存储 四、广义表的定义 五、广义表的存储结构中国网页设计 第5章 数组和广义表数组是由n(n1)个具有相同数据类型的数据 元素a1，a2，an组成的有序序列。这n 个数据元素占用一块地址连续的存储空间。 数组中的数据元素具有相同数据类型。 数组是一种随机存取结构，给定一组下标 ，就可以访问与其对应的数据元素。 数组中的数据元素个数是固定的。 数组是一种特殊的线性表，表中的元素可 以是原子类型，也可以是一个线性表。中国网页

2、设计 数组的定义数组中的数据元素可以是原子类型的，如整 型、字符型、浮点型等，这种类型的数组称 为一维数组；也可以是一个线性表。二维数 组可以看成是线性表的线性表。中国网页设计 第5章 数组和广义表 二、数组的表示和实现 1、数组类型特点 1)数组除了初始化和销毁外，只有存取元素和修 改元素值的操作，不对数组进行插入和删除操作 。 2) 数组是多维的结构，而存储空间是一个一维的 结构。 2、两种顺序映像方式 1)以行序为主序(低下标优先)； 2)以列序为主序(高下标优先)。中国网页设计 第5章 数组和广义表中国网页设计 第5章 数组和广义表以行序为主序的求址公式：假设每个数据元素占L个存储单元

3、， 则二维数组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的存储首地 址为（ ）。中国网页设计 以列序为主序的

4、求址公式： LOC(i, j) = LOC(0, 0) + (jm + i)*L中国网页设计 第5章 数组和广义表三、矩阵的压缩存储 所谓的压缩存储是指：为多个值相同的元只分 配一个存储空间；对零元不分配存储空间。若值相同的元素或零元素在矩阵中的分布有一 定规律，则称此类矩阵为特殊矩阵；反之称 为稀疏矩阵。中国网页设计 特殊矩阵(1)对称矩阵：定义若n阶矩阵A中的元满足下述性质：aijaji1i，jn 则称为n阶对称矩阵。中国网页设计 第5章 数组和广义表压缩存储由于对称矩阵中的元素关于主对角线对称，因此，在对矩阵存储时， 可以只存储对称矩阵中的上三角或者下三角的元素，使得对称的元素共 享一个

5、存储单元，则可将n2 个元压缩存储 到n(n+1)/2个元的空间中。我们以行序为主序存储其下三角（包 括对角线）中的元。中国网页设计 第5章 数组和广义表中国网页设计 有一个10阶的对称矩阵A，采用压缩存储方 式以行序为主序存储，A11为第一元素， 其存储地址为1，每个元素占一个地址空间 ，求A75和A56的地址。随堂练习中国网页设计 对角矩阵的压缩存储对对角矩阵阵,也称带状矩阵，是另一类特殊的矩阵。所谓对角矩阵，就 是所有的非零元素都集中在以主对角线两侧的带状区域内（对角线 的个数为奇数）。也就是说除了主对角线和主对角线两边的对角线 外，其他元素的值均为0.中国网页设计 第5章 数组和广义表

6、 2、稀疏矩阵 (1) 定义：假设 m 行 n 列的矩阵含 t 个非零元素，则称 为稀疏因子。 通常认为 0.05 的矩阵为稀疏矩阵。中国网页设计 第5章 数组和广义表(2) 稀疏矩阵的存储： 若按常规方法进行存储，零值元素会占了很大空 间 因此对于稀疏矩阵的存储通常采用以下两种方式： 三元组表和十字链表进行存储。中国网页设计 第5章 数组和广义表中国网页设计 第5章 数组和广义表中国网页设计 第5章 数组和广义表中国网页设计 第5章 数组和广义表 四、广义表的定义中国网页设计 广义表中所包含的元素(包括原子和子 表)的个数称为表的长 度。 广义表中括号的最大层数称为表深 (度 )。中国网页设

7、计 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）广义表的深度

8、一个表的“深度“是指表展开后所含括号的层数 。【例】表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和

9、3 C. 1和2 D. 2和35 3c中国网页设计 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章 数组和

10、广义表 思考题：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 (按列序存储)中国网页设计-数据结构 中国网页设计