大话数据结构03-线性表

本文最后更新于：2020年9月22日 上午

https://github.com/gaoyangu/paly-with-data-structure

3.2 线性表的定义

线性表（List）：零个或多个数据元素的有限序列

  • 序列：元素之间有顺序，第一个元素无前驱，最后一个元素无后继，其他元素有且只有一个前驱和后继

  • 有限：元素的个数是有限的

  • 线性表的长度：线性表元素的个数 n ( n >= 0)

  • 空表：n = 0

  • 在较复杂的线性表中，一个数据元素可以由若干个数据项组成

3.3 线性表的抽象数据类型

线性表应该有的操作：

  • 线性表的创建和初始化
  • 线性表重置为空表
  • 根据位序得到数据元素
  • 查找某个元素是否存在
  • 获得线性表长度
  • 插入数据和删除数据

对于实际问题中涉及的关于线性表的更复杂的操作，可以用这些基本操作的组合来实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ADT 线性表(List)
Data
    线性表的数据对象集合为{a1,a2,...,an}, 每个元素的类型均为 DataType。
    其中除第一个元素a1外，每一个元素有且仅有一个直接前驱元素，
    除了最后一个元素an外，每一个元素有且仅有一个直接后继元素。
    数据元素之间的关系是一对一的关系
Operation
    InitList(*L):          初始化操作，建立一个空的线性表 L。
    ListIsEmpty(L):        若线性表为空，返回 true, 否则返回false。
    ClearList(*L);         将线性表置空
    GetElem(L,i,*e):       将线性表 L 的第 i 个元素返回给 e。
    LocateElem(L, e):      在线性表 L 中查找与给定值 e 相等的元素，若查找成功，返回该元素在表中序号表示成功，否则返回0表示失败
    ListInsert(*L,i,e):    在线性表 L 中第 i 个位置插入新元素 e。
    ListDelete(*L,i,*e):   删除线性表中第 i 个位置的元素，并用 e 返回其值。
    ListLength(L):         返回线性表 L 的元素个数
endADT

3.4 线性表的顺序存储结构

1. 顺序存储定义

用一段地址连续的存储单元依次存储线性表的数据元素

线性表的顺序存储的结构代码：

1
2
3
4
5
#define MAXSIZE 20	//存储空间初始分配量
typedef struct  {
	int data[MAXSIZE] = {};		//数组存储数据元素
	int length = 0;					//线性表当前长度
}SqList;

2. 顺序存储结构需要三个属性

  • 存储空间的起始位置：数组 data，它的存储位置就是存储空间的存储位置
  • 线性表的最大存储容量：数组长度 MaxSize
  • 线性表的当前长度： length

可以用的一维数组来实现顺序存储结构

3. 数据长度和线性表长度区别

  • 数组长度：存放线性表的存储空间的长度，存储分配后一般是不变的

  • 线性表长度：线性表中数据元素的个数，随着线性表插入和删除操作的进行变化

  • 任意时刻，线性表的长度 <= 数组长度

4. 地址计算方法

  • 线性表的第 i 个元素存储在数组下标 i-1 的位置

  • 地址：存储器中的每个存储单元的编号

假设每个数据占用的是 c 个存储单元

$LOC(a_{i})=LOC(a_1)+(i-1)*c$

  • 存取时间性能：O(1)
  • 把具有这一特点的存储结构称为随机存取结构

3.5 顺序存储结构的插入与删除

1. 插入算法的思路

  • 如果插入位置不合理，抛出异常
  • 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量
  • 从最后一个元素开始向前遍历到第 i 个位置，分别将它们向后移动一个位置
  • 将要插入元素填入位置 i 处
  • 表长加 1

2. 删除算法的思路

  • 如果删除位置不合理，抛出异常
  • 取出删除元素
  • 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置
  • 表长减 1

3. 插入和删除的时间复杂度

  • 最好的情况，元素要插入到最后一个位置或删除最后一个元素，时间复杂度O(1)

  • 最坏的情况，元素要插入到第一个位置或删除第一个元素，时间复杂度为O(n)

  • 平均移动次数与最中间的那个元素的移动次数相等为(n-1)/2

  • 平均时间复杂度为O(n)

线性表：

  • 存、读数据的时间复杂度为O(1)
  • 插入或删除的时间复杂度为O(n)
  • 适合元素个数不太变化，更多是存取数据的应用

4. 线性表顺序存储结构的优缺点

优点：

  • 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
  • 可以快速存取表中任意位置的元素

缺点：

  • 插入和删除操作需要移动大量元素
  • 当线性表长度变化较大时，难以确定存储空间的容量
  • 造成存储空间的“碎片”

3.6 线性表的链式存储结构

  • 线性表的链式存储结构的特点：用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以不连续
  • 链式结构中除了要存数据元素信息，还要存储它的后继元素的存储地址
  • 数据域：存储数据元素信息的域
  • 指针域：存储直接后继位置的域，指针域中存储的信息称为指针或链
  • 节点：数据域和指针域组成的数据元素的存储映像
  • 单链表：链表的每个节点中只包含一个指针域
  • 头指针：链表中第一个节点的存储位置
  • 线性链表的最后一个节点指针为 “空”
  • 头节点：单链表的第一个节点前附设一个节点，数据域可以不存储任何信息，也可以存储线性表长度等附加信息，指针域存储指向第一个节点的指针
1
2
3
4
5
typedef struct Node {
	int data = 0;
	Node* next = NULL;
}Node;
typedef struct Node* LinkList;

3.7 单链表的读取

1. 获取链表第 i 个数据的算法思路

  • 声明一个结点 p 指向链表第一个节点，初始化 j 从 1 开始
  • 当 j < i 时，就遍历链表，让 p 的指针向后移动，不断指向下一个结点，j累加1
  • 若到链表末尾 p 为空，则说明第 i 个元素不存在
  • 否则查找成功，返回结点 p 的数据

最坏情况的时间复杂度为O(n)

单链表的结构中没有定义表长，不能事先知道要循环多少次，不方便使用 for 来控制循环

3.8 单链表的插入与删除

1. 单链表第 i 个数据插入结点的算法思路

  • 声明一结点 p 指向链表第一个结点，初始化 j 从 1开始
  • 当 j < i 时，就遍历链表，让 p 的指针向后移动，不断指向下一个结点，j累加1
  • 若到链表末尾 p 为空，则说明第 i 个元素不存在
  • 否则查找成功，在系统中生成一个空结点 s
  • 将数据元素 e 赋值给 s->data
  • 单链表的插入标准语句 s->next = p->next; p->next = s;
  • 返回成功

2. 单链表第 i 个数据删除结点的算法思路

  • 声明一结点 p 指向链表第一个结点，初始化 j 从 1开始
  • 当 j < i 时，就遍历链表，让 p 的指针向后移动，不断指向下一个结点，j累加1
  • 若到链表末尾 p 为空，则说明第 i 个元素不存在
  • 否则查找成功，将欲删除的结点 p->next 赋值给 q
  • 单链表的删除标准语句：p->next = q->next
  • 将 q 结点中的数据赋值给 e，作为返回
  • 释放 q结点
  • 返回成功

3. 总结

  • 插入和删除都由两部分组成：1.遍历查找第 i 个元素，2. 插入和删除元素
  • 时间复杂度为O(n)
  • 如果希望从第 i 个位置插入10个元素，对于顺序存储结构意味着每一次插入都需要移动 n-i 个元素，每次都是O(n)
  • 对于单链表，只需要在第一次时，找到第 i 个位置的指针，此时为 O(n)，接下来只是简单的通过赋值移动指针，时间复杂度都是O(1)
  • 对于插入或删除数据越频繁的操作，单链表的效率优势越明显

3.9 单链表的整表创建

  • 每个单链表占用空间的大小和位置不需要预先分配划定，可根据系统的情况和实际需求即时生成

1. 单链表整表创建的算法思路

  • 声明一结点 p 和计数变量 i
  • 初始化一空链表 L
  • 让 L 的头结点的指针指向 NULL，即建立一个带头结点的单链表
  • 循环
    • 生成一新节点赋值给 p
    • 随机生成一数字赋值给 p 的数据域 p->data
    • （头插法）将 p 插入到头结点与前一新结点之间
    • （尾插法）把每次新结点都插在终端结点的后面

3.10 单链表的整表删除

单链表整表删除的算法思路

  • 声明一结点 p 和 q
  • 将第一个结点赋值给 p
  • 循环
    • 将下一个结点赋值给 q
    • 删除 p
    • 将 q 赋值给 p

3.11 单链表结构与顺序存储结构优缺点

1. 存储方式

  • 顺序存储结构：一段连续的存储单元依次存储线性表的数据元素
  • 单链表：采用链式存储结构，用任意一组的存储单元存放线性表的元素

2. 时间性能

  • 查找
    • 顺序存储O(1)
    • 单链表O(n)
  • 插入与删除
    • 顺序存储结构：O(n)
    • 单链表：在找出某位置的指针后，插入和删除时间仅为O(1)
  • 空间性能
    • 顺序存储结构：预分配存储空间
    • 单链表：不需要分配空间

3. 总结

  • 顺序存储结构：需要频繁查找，很少进行插入和删除操作
  • 单链表：需要频繁插入和删除，线性表中的元素个数变化较大或者根本不知道有多大

3.12 静态链表

Basic，Fortran 等没有指针，用数组来代替指针，描述单链表叫做静态链表（游标实现法）

  • 让数组的元素都是由两个数据域组成：data（存访数据元素） 和 cur（存访该元素的后继在数组中的下标）
  • 备用链表：未被使用的数组元素
  • 数组第一个元素，即下标为0的元素的 cur 存访备用链表的第一个结点的下标

线性表的静态链表存储结构

1
2
3
4
5
6
#define MAXSIZE 1000

typedef struct{
	int data;
	int cur;		//游标(Cursor),为0时表示无指向
}Component,StaticLinkList[MAXSIZE];

1. 静态链表的插入操作

为了辨明数组中哪些分量未被使用，将所有未被使用过的及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新节点

2. 静态链表的删除操作

3. 静态链表的优缺点

优点：

  • 在插入和删除操作时，只需要修改游标，不需要移动元素

缺点：

  • 没有解决连续存储分配带来的表长难以确定的问题
  • 失去了顺序存储结构随机存取的特性

3.13 循环链表

circular linked list

当单链表中终端结点的指针端由空指针改为指向头节点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表

  • 为了使空链表与非空链表处理一致，通常设一个头结点

  • 用O(1)时间访问第一个结点，最后一个结点需要O(n)

  • 不用头指针，用指向终端结点的尾指针来表示循环链表，查找第一个和最后一个都是O(1)

3.14 双向链表

double linked list

在单链表的每个结点中，再设置一个指向其前驱结点的指针域

具有良好的对称性，使得对某个结点的前后结点的操作带来了方便，可以有效提高算法的时间性能，用空间换时间。

线性表的双向链表存储结构：

1
2
3
4
5
6
typedef struct DulNode
{
    int data;
    struct DuLNode *prior;	//直接前驱指针
    struct DuLNode *next;	//直接后继指针
}DulNode, *DuLinkList;

插入元素：

1
2
3
4
s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;

删除元素：

1
2
3
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);