大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

VisualC++环境下调试数据结构——线性表(顺序存储结构)-创新互联

成都网站建设、成都做网站的开发,更需要了解用户,从用户角度来建设网站,获得较好的用户体验。创新互联建站多年互联网经验,见的多,沟通容易、能帮助客户提出的运营建议。作为成都一家网络公司,打造的就是网站建设产品直销的概念。选择创新互联建站,不只是建站,我们把建站作为产品,不断的更新、完善,让每位来访用户感受到浩方产品的价值服务。

我是荔园微风,作为一名在IT界整整25年的老兵,今天总结一下Visual C++环境下调试数据结构——线性表之顺序存储结构。 

线性表

线性表(Linear List):有限多个相同类型的数据元素类(集合)线性表是最简单、最基本的数据结构。通俗地讲,线性表就是所有的节点按“一个连着一个”的方式组成的一个整体。

线性表主要的存储结构有顺序存储结构和链式存储结构。线性表的基本运算主要有创建线性表、求线性表长度、取第i个节点、插入数据元素、删除数据元素、按值查找数据元素。在实际的算法实现中,这些基本运算一般会放入程序头部进行说明,供程序员进行调用。


顺序存储结构

顺序存储结构常采用数组方式实现。一维数组形式的顺序存储结构具体如下所示。顺序表使用一个连续存储空间相继存放线性表的各个节点。

a1   a2   a3   a4   ......   an   ......  ......

1.数组

数组是一种把相同类型的若干元素,有序地组织起来的集合。集合名就是数组名。组成数组的各个元素称为数组元素。通过数组元素的位置序号(下标),可获得某数组元素的地址,进而得到该数组元素的值。数组在数据结构中常常用来实现向量和矩阵。

数据结构中,数组的运算通常有两个:
(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)*L

2.稀疏矩阵

稀疏矩阵即矩阵中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

矩阵元素aij对应一维数组下标: (i+1)*i/2+j

三对角矩阵

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

矩阵元素aij对应一维数组下标: (i-1)*3-1+j-i+2 化简后为 2*i+j-2

3.顺序表的查找、插入和删除

顺序表的特点是:逻辑相邻的数据元素,物理结构必相邻。

(1)顺序表的查找。顺序表的查找需要比较元素大小。若顺序表有N个元素,每个元素被找到的概率都是1/N;针对不特定的数据元素,查找第M个元素需要比较M次。故而比较次数的平均次数为:(1+…+N)/N=(N+1)/2,这也是顺序表的平均查找长度。 (2)顺序表的插入。若顺序表有N个元素,在顺序表的任何位置插入数据的概率相等,总的插入位置有N+1种可能,当插入在第M个元素前时,需要往后移动N-M+1个位置。插入一个元素,需移动的次数平均数为:[N+(N-1)+…+1]/(N+1)=N/2,这就是顺序表的插入平均移动长度。 (3)顺序表的删除。在顺序表的任何数据元素位置删除数据元素的概率相等,被删除的概率都是1/N,针对不特定的数据元素,删除第M个元素后,需要移动后面(N-M)元素往前一位。 删除一个元素,比较次数的平均数为:[(N-1)+(N-2)+…+1]/N=(N-1)/2,也就是顺序表的平均删除长度。

作者简介:荔园微风,1981年生,高级工程师,浙大工学硕士,软件工程项目主管,做过程序员、软件设计师、系统架构师,早期的Windows程序员,Visual Studio忠实用户,C/C++使用者,是一位在计算机界学习、拼搏、奋斗了25年的老将,经历了UNIX时代、桌面WIN32时代、Web应用时代、云计算时代、手机安卓时代、大数据时代、ICT时代、AI深度学习时代、智能机器时代,我不知道未来还会有什么时代,只记得这一路走来,充满着艰辛与收获,愿同大家一起走下去,充满希望的走下去。

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


文章题目:VisualC++环境下调试数据结构——线性表(顺序存储结构)-创新互联
文章转载:http://dzwzjz.com/article/ieegg.html
在线咨询
服务热线
服务热线:028-86922220
TOP