01-顺序表

一、数据结构与算法

   数据结构与算法是一个程序员的基本功,技术日月更新,但数据结构和算法就相当于一个人的内功,这个人在编程的造诣高不高,就要看内功深厚不深厚。数据结构与算法是一个程序员的基本功,需要平时不断去积累。生活中许多都设涉及到数据结构与算法,数据库就是很典型的,只有认识到数据结构与算法,才能够从底层开发出轮子,让大家直接用轮子去造车子。

1、顺序表

将一组元素看成一个序列,元素在序列的位置和顺序。这样的一组序列元素的组织形式,我们可以抽象为线性表

根据线性表的实际存储方式,分为两种实现模型:

    1、顺序表:将元素顺序地存放在一块连续的存储区,元素间的顺序关系由它们的存储顺序自然表示。

    2、链表:将元素存放在通过连接构造起来的一系列存储快中。

2、顺序表的基本形式

内存:

01-顺序表

   由上图可知内存的基本单位是字节,而一字节占位8。内存存储的本质是存储二进制数据,如何让计算机分辨出存储的数据是各自的类型,int类型占4个字节,即上图的连续的4个内存单元。char类型占1个字节,即内存的一个单元。

01-顺序表

   图a表示顺序表的基本形式,数据元素是连续存储,每个元素所占的存储单元大小固定相同(同类型数据)元素的下标是逻辑地址,而元素的物理地址(实际内存地址,即在内存中的实际地址)可以通过存储区的起始地址L0加上逻辑下标与存储单元的大小(比如int是4个字节即乘4)的乘积计算可得出其物理地址。例如python中的列表Li = [1,2,45,78]的存储方式如下图:

01-顺序表

 故,访问指定的元素的时候无需从头遍历,通过计算便可获得对应的地址,时间复杂度为O(1),比以前(O(n))大大节约时间。

第二种情况,元素类型大小不统一,必须采用元素外置的形式,即图b的情况,将数据元素另行存储,而顺序表中各单元位置保存对应元素的地址信息(链接)。由于每个链接(元素的地址都是整数)所需要的存储量相同。通过上述公式计算元素地址信息存储位置,然后顺着链接找到需要的存储元素。图b这样的顺序表被称为对实际数据的索引,这是最简单的索引结构。

01-顺序表

 3、顺序表的结构与实现

顺序表结构:

01-顺序表

 顺序表的完整信息包括两部分:

1、一部分是表中的元素集合表头信息(表示存储区的容量和已经有元素个数两项)

2、另一部分元素存储区

顺序表的两种基本实现方式:

01-顺序表

 一体式结构:存储表信息的单元与元素存储区以连续的方式安排在一块存储区里,一体式结构整体性强,易与管理。但是由于数据元素存储区域是表对象的一部分。顺序表创建,元素存储区就固定了。

分离式结构:表对象只保存整个表有关的信息(容量,元素个数),实际数据元素存放在另外一个独立的元素存储区里,通过连接与基本表对象关联。

从以上看来一体式更换元素,表头与数据存储区都连在一起,若想更换数据存储区,则需要整体替换,即整个顺序表对象(存储顺序表的结构信息的区域)改变了。

分离式结构若想更换数据区,只需将表信息区的数据区连接地址更新就可以了,故该顺序表对象没有变化。

元素的存储区扩充:

1、每次扩充增加固定数目的存储位置,如每次扩充增加10个位置元素,这种策略称为线性增长。

特点:节省空间,但是扩充频繁,操作次数多,时间浪费比较多

2、每次扩充容量加倍,比如每次扩充一倍存储空间。

特点:减少了扩充操作的执行次数,但会浪费空间资源,用空间换时间这是最推荐的方式。

顺序表的操作

  增加元素:

01-顺序表

 a、尾端插入元素,时间复杂度O(1)

 b、非保序的加入元素(不常见),时间复杂度O(1)

 c、保序的元素加入,时间复杂度O(n)

删除元素:

01-顺序表

a. 删除表尾元素,时间复杂度为O(1)

b. 非保序的元素删除(不常见),时间复杂度为O(1)

c. 保序的元素删除,时间复杂度为O(n)

相关推荐