数据结构复习数组和广义表.ppt
《数据结构复习数组和广义表.ppt》由会员分享,可在线阅读,更多相关《数据结构复习数组和广义表.ppt(6页珍藏版)》请在三一文库上搜索。
1、数据结构复习 (数组和广义表),一、数组 1、数组的顺序存储方式和地址计算方法 数组的存储方式有: (1)行优先存储方式 (2) 列优先存储方式 例5-1 二维数组 int a1010, 以行优先存储, 第1 个元素的首址是100, 每个元素的长度为2,求A45的存储首址。 A45的存储首址= 100 +(4*10+5)*2=100+45*2 =190,第5章 数组和广义表,2、特殊矩阵压缩存储存储及压缩时的下标变换 (1)对称矩阵和上(或下)三角矩阵的压缩存储。 例:下三角矩阵的存储,按行主序方式。 k=i(i+1)/2+j 当i=j时 0 当i=j)或为0(ij)。 (2)对角矩阵 例:以
2、三对角矩阵为例,按行主序方式存储, 仅存储非零部分。 将一个a100100的三对角矩阵以行主序存入一 维数组B298中,元素a6564在B数组中的位置k等 于 。,k=,3、稀疏矩阵的存储方式 三元组法 矩阵A中有非零元个数s远远小于矩阵元素的 总数,则称A为稀疏矩阵。 0 12 9 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 24 0 0 0,M=,i j v,1 2 12,1 3 9,3 1 -3,3 6 14,4 3 24,二、广义表 1、广义表的定义 广义表 ls=(d1,d2,dn)。其中每个元素可以是原子,也可以是子表。 称d1为表头,d2,dn为表尾。 n: 表示广义表的长度,括号层数表示广义表的深度。 2、广义表与线性表的区别 线性表(a1,a2,an)中每个元素都具有相同的类型,有两种存储结构:顺序表和链表。 广义表(d1,d2,dn)中每个元素可以是原子,也可以是子表。可以将广义表看作是线性表的推广。由于原子和子表的类型不同,所以只能用链式存储结构。,3、广义表的链式存储结构 表结点 原子结点,例5-2:A=( ),(e),(a,(b,c,d),
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习 数组 广义
链接地址:https://www.31doc.com/p-3185656.html