软件设计师考试 | 第三章 数据结构 | 数组、矩阵和广义表

2020-10-14  本文已影响0人  Levi_moon

数组与广义表可看作是线性表的推广,其特点是数据元素仍然是一个表。

(一)数组

1.数组的定义及基本运算

(1)数组的定义

数组是定长线性表在维数上的扩展,即线性表中的元素又是一个线性表。
n维数组是一种“同构”的数据结构,其每个数据元素类型相同、结构一致。

数组的特点:

(2)数组的两个基本运算

2.数组的顺序存储

数组一般不做插入和删除运算,一旦定义了数组,则结构中的数据元素个数和元素之间的关系就不再发生变动,因此数组适合于采用顺序存储结构。

二维数组的存储结构可分为以行为主序和以列为主序的两种方法:


二维数组的两种存储方式

地址计算公式:

Loc(aij)=Loc(a11)+((i-1)*n+(j-1))*L
Loc(aij)=Loc(a11)+((j-1)*m+(i-1))*L

(二)矩阵

为了节省存储空间,对有相同的元素或是0的元素的矩阵进行压缩,即多个值相同的元素只分配一个存储单元,对0不分配存储单元。
假如值相同的元素或0元素在矩阵中的分布有一定的规律,则称此类矩阵为特殊矩阵,否则称其为稀疏矩阵。

1.特殊矩阵

特殊矩阵:矩阵中元素(或非0元素)的分布有一定的规律的矩阵。

常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵等。

2.稀疏矩阵

稀疏矩阵:非0元素的个数远远少于0元素的个数,且非0元素的分布没有规律的矩阵。

在存储非0元素时必须同时存储其位置(行号和列号),所以三元组(i,j,aij)可唯一确定矩阵A中的一个元素。


(三)广义表

广义表是线性表的推广,是由0个或多个单元素或子表组成的有限序列。

广义表于线性表的区别:线性表的元素都是结构上不可分的单元素,而广义表的元素既可以是单元素,也可以是有结构的表。

广义表一般记为:

LS=(a1,a2,...,an)

其中,ai(1<=i<=n)既可以是单个元素,又可以是广义表,分别称为原子和子表。

广义表的长度是指广义表中元素的个数。
广义表的深度是指广义表展开后所含的括号的最大层数。

1.广义表的基本操作

包括:查找、插入、删除等操作。
取表头:非空广义表的第一个元素称为表头,它可以是一个单元素,也可以是一个子表。
取表尾:在非空广义表中,除表头元素之外,由其余元素所构成的表称为表尾。(非空广义表的表尾必定是一个表。)

2.广义表的特点

3.广义表的存储结构

由于广义表中的元素本市又可以具有结构,它是一种带有层次的非线性结构,因此通常采用链式存储结构。


广义表(a,(b,c,d))的存储结构示意图
上一篇 下一篇

猜你喜欢

热点阅读