数据结构与算法系列2 线性表

数据结构与算法系列2 线性表

**

啥是线性表？

** 线性表是具有n个相同类型元素的有序序列，线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。

线性结构

在这里插入图片描述

常见的线性表有：数组，链表，栈，队列，哈希表

首节点，尾节点，前驱与后继

a1是首节点 an是尾节点 a1是a2的前驱 a2是a1的后继

在这里插入图片描述

前驱后继与直接前驱直接后继的区别

在这里插入图片描述

如用（a1，…，ai-1，ai，ai+1，…，an）表示一个顺序表，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2，…，n-1时，ai有且仅有一个直接后继，当i=2，3，…，n时，ai有且仅有一个直接前驱 [1] 。

数据元素数据项，记录和文件

在线性表中，无论数据本身由多少种数据类型（每一种被称为一个“数据项”）组成，每一条数据被称为“数据元素”。

如果数据元素本身包含的数据项非常多，就可以称这个数据元素为一个“记录”，多条记录组成一个“文件”。

在这里插入图片描述

线性表的特点

1. 存储的数据本身的类型一定保持相同，是int型就都是int型，是结构体就都是一种结构体。
2. 数据一旦用线性表存储，各个数据元素之间的相对位置就固定了。 相对位置，指的是各数据元素在逻辑结构上的前后次序。

线性表的分类

之前讲过，逻辑结构上相邻的数据在实际的物理存储中有两种形式：分散存储和集中存储。 考虑到这两种情况，线性表分为两种，分别解决两种情况下数据的存储问题： 数据元素在内存中集中存储，采用顺序表示结构，简称“顺序存储”； 数据元素在内存中分散存储，采用链式表示结构，简称“链式存储”。

生活中的线性表

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

上面这些都是有相同特征的“有序列”