线性表

线性表的逻辑定义•

• 数据元素虽然不同，但是同一线性表中的元素必定具有相同的特性，即属于同一数据对象

• 相邻的数据元素之间存在着序偶关系

• 诸如此类由n(n>=0)个数据特性相同的元素构成的有限序列称为线性表

• 线性表中元素的个数n(n>=0)定义为线性表的长度，n=0时称为空表

• 非空的线性表或线性结构的特点：

  • 存在唯一的一个被称为“第一个”的数据元素
  • 存在唯一的一个被称为“最后一个”的数据元素
  • 除第一个数据元素之外，结构中的每个数据元素均只有一个前驱
  • 除最后一个数据元素之外，结构中的每个数据元素均只有一个后继

常见的线性表的基本运算•

InitList(&L)：构造一个空的线性表L，即表的初始化
ListLenght(L)：返回L中数据元素个数，即求表长
GetElem(L, i, &e)：用e返回L中第i个数据元素的值，1<=i<=ListLenght(L)LocateElem(L, e)：返回L中第1个值与e相同的元素在L中的位置，若不存在，则返回值为0
ListInsert(&L, i, e)：在L中第i个位置之前插入新的数据元素e，L的长度加1
ListDelete(&L, i)：删除L的第i个数据元素，L的长度减1

线性表的顺序存储结构•

顺序表的定义•

• 用一组地址连续的存储单元依次存储线性表的数据元素，也称作线性表的顺序存储结构或顺序映像

• 用顺序存储结构的线性表称为顺序表

• 逻辑上相邻的数据元素，其物理次序也是相邻的

地址的计算方式•

LOC(a_i+1)=LOC(a_i)+l

• l是每个元素需占用的存储单元

• LOC(a_i+1)是线性表的第i+1个数据元素的存储位置

• LOC(a_i)是第i个数据元素的存储位置

线性表的第i个数据元素a_i的存储位置为：

LOC(a_i)=LOC(a_i)+(i-1)xl

顺序表类型定义•

• 通常都是用数组来描述数据结构中的顺序存储结构

顺序表的基本操作•

• 1. 初始化：构造一个空的顺序表

• 2. 取值：顺序存储结构具有随机存取的特点，可以通过数组下标定位得到

  • 顺序表取值算法的时间复杂度为O(1)

• 3. 查找：根据指定的元素值e，查找顺序表中第一个与e相等的元素，成功返回该元素在表中的位置序号，失败返回0

  • 为确定元素在表中的位置，需和给定值进行比较的数据元素个数的期望值为查找算法在查找成功时的平均查找长度（ASL）
  • 顺序表按值查找算法的平均时间复杂度为O(n)

• 4. 插入：在表的第i(1<=i<=n+1)个位置插入一个新的数据元素e，使长度为n的线性表变成长度为n+1的线性表

  • 时间主要耗费在移动元素上，移动元素的个数取决于插入元素的位置
  • 顺序表插入算法的平均时间复杂度为O(n)

• 5. 删除：将表的第i(1<=i<=n)个元素删去，将长度为n的线性表变成长度为n-1的线性表

  • 时间主要耗费在移动元素上，移动元素的个数取决于删除元素的位置
  • 顺序表删除算法的平均时间复杂度为O(n)

线性表的链式存储结构•

• 顺序表可以随机存取，在插入和删除时，需移动大量元素，数组有长度相对固定的静态特性。

• 当表中数据元素个数较多且变化较大时操作过程相对复杂，必然导致存储空间的浪费

• 链式存储结构可以解决以上问题

单链表•

单链表的定义与表示•

• 用一组任意的存储单元存储的数据元素，这组存储单元可以是连续的，也可以是不连续的。

• 单链表的结点包含两个域：数据域和指针域

• 数据域用于存储数据元素信息

• 指针域用于存储直接后继的存储位置，指针域中存储的信息称作指针或链

• 单链表的每个结点中只包含一个指针链

• 链表增加头结点的作用：

  • 便于首元结点的处理。
  • 便于空表和非空表的统一处理。
    • 不设头结点时，判断空表的条件为：L == NULL
    • 增加头结点时，判断空表的条件为：L -> next == NULL

• 首元结点：链表中存储第一个数据元素a₁的结点

• 头结点：在首元结点之前附设的一个结点，其指针域指向首元结点。头指针的数据域可以存储与数据元素类型相同的其他附加信息，也可不存储任何信息

• 头指针：链表中第一个结点的指针。设有头结点，头指针指向结点为线性表的头结点；不设头结点，头指针指向结点为线性表的首元结点

单链表的基本操作•

• 1. 初始化：构造一个空表

• 2. 取值：从首元结点出发，顺着链域next逐个结点向下访问

  • 单链表的取值算法的平均时间复杂度为O(n)

• 3. 查找：按值查找，从链表的首元结点出发，依次将结点值和给定值e进行比较，返回查找结果

  • 单链表的查找算法的平均时间复杂度为O(n)

• 4. 插入：假如要在a和b之间插入数据元素x，首先要生成一个数据域为x的结点，然后插入到单链表中。需要修改结点a中的指针域，使其指向结点x，而结点x中的指针域应指向结点b

  • 语句描述：s -> next = p -> next; p -> next = s;
  • 如果表中有n个结点，则插入操作中合法的插入位置有n+1个，即1<=i<=n+1，当i=n+1时，新结点则插在链表尾部
  • 单链表的插入算法的时间复杂度为O(n)

• 5. 删除：首先要找到删除位置的元素的前驱结点，修改前驱结点的指针域，还要释放要删除结点的所占空间，所以，修改指针前，一个引入另一指针来临时保存要删除结点的地址以备释放

  • 语句描述：p -> next = p -> next -> next;
  • 单链表的删除算法的时间复杂度为O(n)

• 6. 创建单链表：根据结点插入的位置不同，链表的创建方法可分为前插法和后插法

  • 前插法：通过将新结点逐个插入链表的头部（头结点之后）来创建链表
  • 后插法：通过将新结点逐个插入到链表的尾部来创建链表，需要增加一个尾指针

循环链表•

• 将最后一个结点的指针域指向头结点，使整个链表形成一个环，这种首尾相接的链表就称为循环链表

单循环链表•

• 从任意一个结点出发都可以找到表中其他结点

• 单循环链表和单链表的操作区别：链表遍历时，判别当前指针p是否指向表尾结点的终止条件不同

• 单链表的判别条件：p != NULL或者p -> next != NULL

• 单循环链表的判别条件：p != L或者p -> next != L

双向链表•

• 在链表的每个结点中设置两个指针，一个指向后继结点，另一个指向前驱结点，就是双向链表，简称双链表

• p为指向某个结点的指针：p -> next -> prior = p -> prior -> next = p

顺序表和链表的比较•

• 空间性能的比较

  • 当线性表的长度变化较大，难以预估存储规模时，宜采用链表作为存储结构
  • 当线性表的长度变化不大，易于事先确定其大小时，宜采用顺序表作为存储结构

• 时间性能的比较

  • 若线性表的主要操作是和元素位置紧密相关的取值操作，很少做插入或删除时，宜采用顺序表作为存储结构
  • 对于频繁进行插入或删除操作的线性表，宜采用链表作为存储结构