数据结构 复习 – Part 1 线性表

数据结构:研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系(更多的是逻辑关系)和操作。

数据结构分成4种基本结构:
1、集合:结构中的数据元素之间除了“同属于一个集合”的关系外,别无其他关系。
2、线性结构:数据元素之间存在一对一的关系。
3、树:一对多
4、图或网状结构:多对多

数据在计算机中有两种不同的存储结构:顺序存储结构和链式存储结构。
1、顺序存储结构:用元素在存储器中的相对位置来表示数据元素之间的逻辑关系。例如,假设用两个字长的位串表示一个实数,则可以用地址相邻的4个字长的位串表示一个复数,上图左边表示复数 3.0-2.3i 和 -0.7+4.8i。
2、链式存储结构:用指示元素存储地址的指针来表示数据元素之间的逻辑关系。例如,上图右边,其中实部和虚部之间的关系用值为“0415”的指针(0415是虚部的存储地址)来表示。

任何一个算法的设计取决于选定的数据(逻辑)结构,而算法的实现依赖于采用的存储结构。


线性表

特点:在数据的非空有限集中,
1、存在唯一的“第一个”数据元素
2、存在唯一的“最后一个”数据元素
3、除第一个外,集合中的每个数据元素均只有一个前驱
4、除最后一个外,集合中的每个数据元素均只有一个后继

1、顺序表(线性表的顺序表示和实现)

顺序表:用一组地址连续的存储单元依次存储线性表的数据元素。

以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。所以只要确定了存储线性表的起始位置,线性表中任一数据元素都可随机存取(优点)

顺序表的插入:在任一位置 ai (i ≠ last_length) 插入新元素,使得数据元素 ai-1ai 之间的逻辑关系发生变化,必须移动插入位置之后的所有元素才能反映这个逻辑关系的变化(缺点)

顺序表的删除:删除任一位置 ai (i ≠ last_length) 的元素,使得数据元素 ai-1 和ai 之间的逻辑关系发生变化,同理也必须移动……

2、线性表链式表示和实现

又分为线性链表循环链表双向链表

线性链表:用一组任意的存储单元(可连续,也可不连续)存储线性表的数据元素。这里的数据元素包含两部分信息,数据域和指针域,如下图。

所以,数据元素之间的逻辑关系是通过结点中的指针来指示的。因为最后一个数据元素没有直接后继元素,所以其指针域为NULL;那我们怎么知道这条线性链表是从哪个数据元素开始呢?就需要一个头指针来指示链表中的第一个结点的存储位置;若头指针为NULL,则线性表为空表。

例如,若用线性链表表示下面这个线性表各数据元素的数据域和指针域为线性链表的逻辑状态可形象表示为

有时,我们在线性链表的第一个结点之前增加一个结点,叫“头结点”;头结点的数据域可不存储任何信息,也可存储如线性表的长度等附加信息;头结点的指针域指向第一个结点的存储位置(相当于头指针)。此时,头指针指向头结点头结点虽然不是链表必需的,但另加一个头结点是出于什么考虑呢?主要是为了
(1)统一对第 1 个结点的操作(插入或删除)和对其他结点的操作;
(2)无论链表是否为空,其头指针都是指向头结点的非空指针,统一对空表和非空表的操作。
下面会用伪代码详细解释。

线性链表中每个元素的存储位置都包含在其直接前驱结点的信息中,所以取得第 i 个数据元素必须从头指针出发寻找,所以它是非随机存取的存储结构。

线性链表的插入只需要改变两个红框内的指针,从而实现3个元素a、b和x之间逻辑关系的变化

假如我在第 1 个位置之前插入元素 e,若没有头结点,则上述部分代码需改为

线性链表的删除

只需要改变一个指针

假如我删除第 1 个元素 ,若没有头结点,则上述部分代码需改为

所以,加了头结点之后,插入、删除都是在后继指针next上进行操作,不用动头指针!

线性链表的创建:链表占用的空间无需预先分配划定,而是应需求即时生成。从“空表”开始,依次建立各元素结点,并逐个插入链表。从表尾到表头逆向建立线性链表的算法如下:

线性链表的合并:将两个有序非递减链表合并为一个有序非递减链表。

 

循环链表:表中最后一个结点的指针域指向头结点,整个链表形成一个环。因此,从表中任一结点出发均可找到表中其他结点。循环链表的插入和删除操作和线性链表基本一致,差别仅在算法中的循环条件改为

有的时候,也可以在循环链表中设立尾指针而不设头指针,可以使两个链表合并简化,仅需将一个表的表尾和另一个表的表头相接,仅改变两个指针值,如下。

 

双向链表:表中的结点有两个指针域,一个指向直接后继,另一个指向直接前驱。

双向链表的删除:需修改 2 个指针值。

双向链表的插入:需修改 4 个指针值。

Leave a Reply

Your email address will not be published. Required fields are marked *