一、定义

线性表 ：零个或多个数据元素的 有限序列 ，是逻辑结构呈线性的 数据结构 。元素之间是有顺序的，元素的前一个元素称为 前驱 元素，后一个元素称为 后继 元素。一般表示为：

L = (a1, a2, …, an)

基本操作包括：

• 初始化空的线性表
• 清空线性表
• 获取线性表指定位置元素的值
• 在指定位置插入元素
• 删除指定位置的元素
• 返回线性表的元素个数

二、存储结构

1、顺序存储

可利用 数组 来实现，按逻辑顺序依次存放到数组 a 中，a[0]放第一个元素，a[1]放第二个元素，依次类推。

• 直接访问指定位置的元素（索引访问）
• 插入：插入新结点，之后结点后移
• 删除：删除节点，之后结点前移

2、链式存储

可利用 链表 来实现，数据域存放数据元素，指针域指向前驱和后继结点。

• 通过指针域递归查找访问元素
• 插入：修改前后结点的指针域
• 删除：连接前后结点的指针域，释放删除结点所占存储空间
  根据指针域的不同，可分为：
• 单向链表 （简称： 单链表 ）：指针域为后继结点地址
• 双向链表 ：指针域包括前驱和后继结点地址
• 循环链表 ：头结点作为尾结点的后继结点
• 静态链表 ：把指针转化为游标，和数据元素一起存放到数组中

静态链表存储空间虽然是连续的，但存储的元素是没有顺序的，所以属于链式存储

三、栈

1、定义

限定仅在一端进行插入和删除操作的线性表。这一端被称为 栈顶 ，相对地，把另一端称为 栈底 。向一个栈插入新元素称作 进栈 、 入栈 或压栈 ，从一个栈删除元素称作 出栈 或退栈 。没有元素的栈称为 空栈 ，栈元素总是 后进先出 ， 一般用数组实现

基本操作包括：

• 入栈 ：把新元素放到栈顶元素的上面，使之成为新的栈顶元素
• 出栈 ：取出栈顶元素，使其相邻的元素成为新的栈顶元素

2、分类

按存储方式的不同可分为两类：

• 顺序存储栈 ：顺序存储结构，用数组存储元素，数组最后一个元素为栈顶
• 链栈 ：链式存储结构，插入和删除操作仅限制在链头位置上进行，栈顶指针就是链表的头指针

四、队列

1、定义

限定在一端进行插入和另一端进行删除的线性表。插入的这端被称为 队尾 ，删除的这端称为 队头 。向一个队列插入新元素称作 入队 ，从一个队列删除元素称作 出队 。没有元素的队列称为 空队列 ，队列元素总是 先进先出

基本操作包括：

• 入队 ：把新元素放到队尾的后面，使之成为新的队尾
• 出队 ：取出队头元素，使下一个的元素成为新的队头

2、分类

按存储方式的不同可分为两类：

• 循环队列 ：顺序存储结构，
• 链队列 ：链式存储结构，在表尾插入新的元素，在表头进行删除操作

五、串

1、定义

串是零个或多个字符组成的有限序列，又称为 字符串 ，是数据元素为字符的线性表。线性表关注的是单个元素的操作，比如增删查一个元素，而串通常以整体作为操作对象，如在串中查找某个子串、求取一个子串等等。由于字符串的特殊性，一般直接 使用数组存储 。

2、基本操作

• 求串长 ：获取字符串长度
• 串连接 ：把两个字符串拼接成一个字符串
• 求子串 ：从指定位置截取 N 个字符作为新的字符串
• 子串查找 ：查找指定字串第一次出现的位置
• 串插入 ：在指定位置插入字符串
• 串删除：从指定位置删除 N 个字符