济南大学数据结构 第五章Word文档格式.docx
- 文档编号:7823944
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:13
- 大小:264.19KB
济南大学数据结构 第五章Word文档格式.docx
《济南大学数据结构 第五章Word文档格式.docx》由会员分享,可在线阅读,更多相关《济南大学数据结构 第五章Word文档格式.docx(13页珍藏版)》请在冰点文库上搜索。
αj=(a0j,a1j,……,am-1j)T
5.2数组的表示和实现
数组一旦被定义,其维数和维界就不再改变,故通常采用顺序存储结构。
如何将多维数组结构转换对应一组连续的存储单元?
以列序为主序
以行序为主序
对于数组,一旦规定了维数和维界,如何计算数组元素的存储位置?
设数组以行序为主序。
二维数组A[m][n]
数组元素aij的存储位置为
LOC(i,j)=LOC(0,0)+(n×
i+j)L
LOC(0,0)是a00的存储位置;
L是每个数组元素占用的存储单元数;
例,LOC(1,1)=LOC(0,0)+(n×
1+1)L
三维数组A(b1,b2,b3)
LOC(0,0,0)是a000的存储位置;
LOC(1,1,1)=LOC(0,0,0)+(b2×
b3×
1+b3×
1+1)L
数组元素aijk的存储位置为:
LOC(i,j,k)=LOC(0,0,0)+(b2×
i+b3×
j+k)L
n维数组A(b1,b2,…,bn)的元素存储位置可计算为:
LOC(j1,j2,……,jn)
=LOC(0,0,……,0)+
(b2×
……×
bn×
j1+b3×
j2+……+bn×
jn-1+jn)L
5.3矩阵的压缩存储
矩阵元素如何存储?
通常利用二维数组来存储矩阵元素。
B[m][n]
aijbi-1,j-1
实际中,存在许多特殊矩阵,例如在矩阵中有许多值相同的元素或者零元素。
用定长数组存储造成浪费。
为了节省存储空间,需要对这类矩阵进行压缩存储。
压缩存储是指为多个值相同的元素只分配一个存储空间;
对零元素不分配空间。
Ø
对称矩阵
三角矩阵
对角矩阵
稀疏矩阵
n阶对称矩阵
n阶矩阵A满足:
aij=aji
通常表示为:
n2个矩阵元素只需占用n(n+1)/2个存储空间
设计用一维数组SA[n(n+1)/2]存储n阶对称矩阵A。
关键问题:
如何建立数组元SA[k]和矩阵元aij之间的一一对应关系。
K一定是i,j的函数
ai+bj+c
=ai+j+c
=an+1+c
=
a=
b=1,c=-1
三角矩阵
所谓下(上)三角矩阵是指矩阵的上(下)三角(不包括对角线)中的元均为常数c的n阶矩阵。
下三角矩阵
和对称矩阵基本一样,只需除存储其下(上)三角中的元之外,再增加一个存储单元存放c。
对角矩阵
所有的非零元都集中在以主对角线为中心的带状区域中。
一般情况三对角矩阵
=a(n-1)+(n-2)+c
=3n-7
代入解得:
a=2,b=1,c=-3
K=2i+j-3
(|i-j|≤1)
作业:
五对角矩阵
稀疏矩阵
非零元很少的矩阵。
稀疏因子:
设m×
n的矩阵,有t个非零元,令
通常认为δ≤0.05时称为稀疏矩阵。
稀疏矩阵的压缩存储
三元组顺序表
行逻辑链接顺序表
十字链表
三元组顺序表
三元组(i,j,aij)表示非零元素
i行数,j列数,aij非零元。
5.4广义表的定义
广义表(列表)LS=(a1,a2,,an)
LS:
列表名称
n:
列表长度(元素的个数)
ai:
可以是单个数据,也可以是子列表,分别称为原子和子表。
a1:
LS的表头(第一个元素)。
(a2,a3,,an):
LS的表尾(列表)。
列表的举例:
(1)A=()——A是一个空列表,长度为0。
(2)B=(e)——B中只有一个原子e,长度为1。
(3)C=(a,(b,c,d))——C有两个元素,原子a和子表(b,c,d),长度为2。
(4)D=((),(e),(a,(b,c,d)))——D有三个元素,都是子表,长度为3。
(5)E=(a,E)——E为一个递归的表,长度为2。
例E=(a,(a,(a,……)))。
列表的性质:
(1)列表是一个多层次的结构。
例D=((),(e),(a,(b,c,d)))
(2)列表可为其它列表的子表所调用。
例,D=(A,B,C)
(3)列表可以是一个递归的表。
例,E=(a,E)
(4)任何一个非空列表,其表头可能是原子或列表,而表尾一定是列表。
例,B=(e)表头为原子e;
表尾为空表()。
例,B=((a,b),c)表头为列表(a,b);
表尾为列表(c)。
(5)()==(())?
()为空表,长度0;
(())长度为1的列表,可分解得到表头、表尾。
5.5广义表的存储结构
由于广义表中的数据元素可以具有不同的结构(原子、列表),难以用顺序存储结构表示,通常采用链式存储结构。
结点结构:
tag:
标志域,1为表结点,0为原子结点。
hp:
指向表的表头元素结点。
atom:
原子结点的值域。
tp:
指向下一个元素域。
作业:
求((a,b),(c,d),(e,f))的表头和表尾
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 济南大学数据结构 第五章 济南 大学 数据结构 第五