我是荔园微风,作为一名在IT界整整25年的老兵,今天总结一下Visual C++环境下调试数据结构——线性表之顺序存储结构。
线性表线性表(Linear List):有限多个相同类型的数据元素类(集合)线性表是最简单、最基本的数据结构。通俗地讲,线性表就是所有的节点按“一个连着一个”的方式组成的一个整体。
线性表主要的存储结构有顺序存储结构和链式存储结构。线性表的基本运算主要有创建线性表、求线性表长度、取第i个节点、插入数据元素、删除数据元素、按值查找数据元素。在实际的算法实现中,这些基本运算一般会放入程序头部进行说明,供程序员进行调用。
顺序存储结构常采用数组方式实现。一维数组形式的顺序存储结构具体如下所示。顺序表使用一个连续存储空间相继存放线性表的各个节点。
a1 a2 a3 a4 ...... an ...... ......数组是一种把相同类型的若干元素,有序地组织起来的集合。集合名就是数组名。组成数组的各个元素称为数组元素。通过数组元素的位置序号(下标),可获得某数组元素的地址,进而得到该数组元素的值。数组在数据结构中常常用来实现向量和矩阵。
数据结构中,数组的运算通常有两个:
(1)给定数组的下标,存取相应的数据元素
(2)给定数组的下标,修改对应的数据元素的值。
数组的运算通常不涉及插入和删除运算。
一维数组即数组中每个元素都只有一个下标的数组。两个一维数组组成二维数组,n个一维数组组成n维数组。假定a是数组的首地址,L是数组元素的长度,行优先存储(先存储第一行,然后存储第二行,……,直至最后一行),则数组某元素的地址对应关系见下。
数组类型 数组表示形式 某元素对应的存储地址 一维数组 a[n] 元素a[i]的存储地址:a+(i-1)*L 二维数组 a[m][n](m行n列) 元素a[i][j]的存储地址:a+(i*n+j)*L2.稀疏矩阵稀疏矩阵即矩阵中0元素个数远远多于非0元素,并且非0元素分布没有规律。稀疏矩阵可以采用三元组数组和十字链表两种存储方式,两种方式均只存储非0元素。
三元组数组:非0元素用三元组(行号、列号、值)表示,并全部存储在数组中。这也完成了稀疏矩阵的压缩。下面给出了一个稀疏矩阵用三元组数组表示的例子。
0 0 6 0 9 0
7 0 0 0 0 0
0 0 0 0 0 0
0 0 6 0 0 0
0 3 0 0 2 0
0 0 0 0 0 1
以上矩阵用三无组表示为:
(1 3 6)
(1 5 9)
(2 1 7)
(4 3 6)
(5 2 3)
(5 5 2)
(6 6 1)
十字链表:非0元素均为十字链表的一个节点,节点有5个域(行号、列号、值、行和列的后继指针)。 常见的特殊稀疏矩阵有上三角、下三角和三对角矩阵。具体特点见下。
上三角矩阵(当i>j时,矩阵元素aij=0)
a11 a12 a13 a14 a15
0 a22 a23 a24 a25
0 0 a33 a34 a35
0 0 0 a44 a45
0 0 0 0 a55
矩阵元素aij对应一维数组下标:(2n-i+2)*(i-1)/2+j-i+1 化简为 (2n-i)*(i-1)/2+j下三角矩阵(当i a11 0 0 0 0 a21 a22 0 0 0 a31 a32 a33 0 0 a41 a42 a43 a44 0 a51 a52 a53 a54 a55 三对角矩阵 a11 a12 0 0 0 a21 a22 a23 0 0 0 a32 a33 a34 0 0 0 a43 a44 a45 0 0 0 a54 a55 顺序表的特点是:逻辑相邻的数据元素,物理结构必相邻。 作者简介:荔园微风,1981年生,高级工程师,浙大工学硕士,软件工程项目主管,做过程序员、软件设计师、系统架构师,早期的Windows程序员,Visual Studio忠实用户,C/C++使用者,是一位在计算机界学习、拼搏、奋斗了25年的老将,经历了UNIX时代、桌面WIN32时代、Web应用时代、云计算时代、手机安卓时代、大数据时代、ICT时代、AI深度学习时代、智能机器时代,我不知道未来还会有什么时代,只记得这一路走来,充满着艰辛与收获,愿同大家一起走下去,充满希望的走下去。 你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网页标题:VisualC++环境下调试数据结构——线性表(顺序存储结构)-创新互联
网页URL:http://bjjierui.cn/article/ieegg.html