顺序表

这节课我们主要探讨顺序存储结构以及对应的运算算法的实现。

采用顺序存储是表示线性表最简单的方法，具体做法是：将线性表中的元素一个接一个的存储在一块连续的存储区域中，这种顺序表示的线性表也成为顺序表。

实际上，在上一部分的动态数组就是一个顺序表结构。

顺序表

顺序表是在计算机内存中以数组形式保存的线性表，其特点是逻辑上相邻的元素在物理存储位置上也相邻。常见的数据结构里，顺序表有以下几种：

• 数组：是最典型的顺序表。它在内存中占用连续的存储单元，通过下标可以直接访问任意位置的元素。例如在Python中[1, 2, 3, 4, 5]这样的列表本质上是对数组的封装，在C语言里则可以直接定义数组，像int arr[5] = {1, 2, 3, 4, 5};。
• 静态数组实现的顺序表：在一些静态语言中，会用静态数组来实现顺序表，这种顺序表在创建时就需要确定大小，之后不能动态改变。

非顺序表

有些线性结构并非顺序表，它们的元素在物理存储位置上不一定相邻，常见的有：

• 链表：由一系列节点组成，每个节点包含数据域和指向下一个节点的指针（单链表）。节点在内存中的存储位置是随机的，通过指针来实现元素之间的线性逻辑关系。例如单链表、双向链表和循环链表。
• 栈（链式栈）：栈是一种后进先出（LIFO）的线性结构。链式栈使用链表来实现，栈中的元素通过链表的节点连接，不要求在内存中连续存储。
• 队列（链式队列）：队列是一种先进先出（FIFO）的线性结构。链式队列同样基于链表实现，队列元素通过链表节点连接，物理存储位置不连续。