线性表(Linear List)

线性表是具有相同数据类型，每个数据元素所占空间一样大的n个数据元素的有限序列(有次序)。

L=($a_1,a_2,…,a_i,a_{i+1},…,a_n$)

其中$a_i$是线性表中的“第i个”元素线性表中的位序

$a_1$是表头元素；$a_n$是表尾元素。

除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。

0x01 线性表的常用实现函数：

InitList(&L): 初始化表。构造一个空的线性表L，分配内存空间。
DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。
ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。
GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。

其他常用操作： Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。
PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。
Empty(L)：判空操作。若L为空表，则返回true，否则返回false。

0x02 顺序表

顺序表是用顺序存储的方式实现线性表。

顺序存储：

把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

顺序表的特点：

  1. 随机访问，即可在O(1)的时间内找到第 i 个元素。
  2. 存储密度高，每个节点之存储数据元素。
  3. 扩展容量不方便(即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高)。
  4. 插入、删除操作不方便，需要移动大量元素。

0x0201 顺序表–静态分配

静态分配方式：

1
2
3
4
5
#define MaxSize 10	//定义最大长度
typedef struct{						
  ElemType data[MaxSize];	//用静态的“数组”来存放数据元素
  int length;	//顺序表的当前长度
}SqList;	//顺序表的类型定义(静态分配方式)

举个栗子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
#define MaxSize 10 //定义最大长度

typedef struct {
    int data[MaxSize];
    int length;
}SqList;

/***
 * @description: 初始化顺序表 
 * @param {SqList&} L
 * @return {*}
 */
void InitList(SqList& L) {
    for (int i = 0;i < MaxSize; i++) {
        L.data[i] = 0;
    }
    L.length = 0;
}

int main() {
    SqList L; //声明一个顺序表
    InitList(L); //初始化顺序表
    for (int i = 0;i < L.length; i++) { //打印整个 data 数组
        printf("data[%d]=%d\n", i, L.data[i]);
    }
  	//最好使用 GetElem(L , i)这种方式来访问顺序表的数据元素
    return 0;
}

顺序表的静态分配的局限性在于顺序表的表长在开始时就要确定，然后就无法更改（存储空间是静态的）。

0x0202 顺序表–动态分配

为了动态分配存储空间，提高内存空间的使用效率，可以采用动态分配的分配方式。

动态分配方式：

1
2
3
4
5
6
7
#define InitSize 10 //顺序表的初始长度
typedef struct sqlist_dynamic //顺序表的类型定义
{
    ElemType* data; //指向动态分配数组的指针
    int MaxSize; //顺序表的最大容量
    int length; //顺序表的当前长度
};

动态分配：动态申请和释放内存空间。

  • 申请：malloc函数
  • 释放：free函数

举个栗子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<stdio.h>
#include<stdlib.h>
#define InitSize 10 //顺序表的初始长度

typedef struct//顺序表的类型定义
{
    int* data; //指向动态分配数组的指针
    int MaxSize; //顺序表的最大容量
    int length; //顺序表的当前长度
}Sqlist_dynamic;

/*** 
 * @description: 初始化顺序表 
 * @param {Sqlist_dynamic&} L
 * @return {*}
 */
void InitList(Sqlist_dynamic& L) {
    //用 malloc 函数申请一片连续的存储空间
    L.data = (int*)malloc(InitSize * sizeof(int));
    L.length = 0;
    L.MaxSize = InitSize;
}

/*** 
 * @description: 增加动态数组的长度 
 * @param {Sqlist_dynamic&} L
 * @param {int} len
 * @return {*}
 */
void IncreaseSize(Sqlist_dynamic& L, int len) {
    int* p = L.data;
    L.data = (int*)malloc((L.MaxSize + len) * sizeof(int));
    for (int i = 0; i < L.length; i++) {
        L.data[i] = p[i]; //将数据复制到新区域
    }
    L.MaxSize = L.MaxSize + len; //顺序表最大长度 + len
    free(p); //释放原来的内存空间
}

int main() {
    Sqlist_dynamic L;
    InitList(L);
    /* TODO: 随意插入几个元素 */
    IncreaseSize(L, 5);
    return 0;
}

0x0203 顺序表的插入

实现：

举第一个栗子🌰：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*** 
 * @description: 顺序表的插入，将元素e插入i处
 * @param {SqList&} L
 * @param {int} i
 * @param {int} e
 * @return {*}
 */
void ListInsert(SqList& L, int i, int e) {
    for (int j = L.length;j >= i;j--) { //将第i个元素及之后的元素后移
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e; //在位置i处放入e
    L.length++; //长度加1
}

此处省略：

  • 判断i是否合法，即 i 在[1,length+1]。
  • 判断顺序表是否存满，若存满则无法插入数据。
  • 返回是否操作成功的提示。

举第二个栗子🌰（改进后）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*** 
 * @description: 顺序表的插入，将元素e插入i处
 * @param {SqList&} L
 * @param {int} i
 * @param {int} e
 * @return {bool}
 */
bool ListInsert_better(SqList& L, int i, int e) {
    if (i<1 || i>L.length + 1) return false; //判断i的范围是否合法
    if (L.length >= MaxSize) return false; //判断当前空间是否能放下e
    for (int j = L.length; j >= i; j--) { //将第i个元素及之后的元素后移
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e; //在位置i处放入e
    L.length++; //长度加1
    return true; //插入成功，返回true
}

时间复杂度分析：

最好情况：新元素插入到表尾，不需要移动元素。
i = n + 1，循环0次；最好时间复杂度 = $O(1)$

最坏情况：新元素插入到表头，需要将n个元素全部向后移动
i = 1，循环n次；最坏时间复杂度 = $O(n)$

平均情况：新元素插入到任何一个位置的概率相同，即 i = 1,2,3,……,length+1 的概率都是$p = 1/(n+1)$
当i = 1，循环n次；当i = 2时，循环n - 1次；当i = 3时，循环n - 2次；……当i = n + 1时,循环0次。
平均循环次数 = $np+(n-1)p+(n-2)p+……+1·p = [\frac{n(n+1)}2]·[\frac{1}{n+1}]=\frac{n}2$
$\therefore$ 平均时间复杂度 = $O(n)$

0x0204 顺序表的删除

实现：

举个栗子🌰：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*** 
 * @description: 删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
 * @param {SqList&} L
 * @param {int} i
 * @param {int&} e
 * @return {bool}
 */
bool ListDelete(SqList& L, int i, int& e) {
    if (i<1 || i>L.length) return false; //判断i的范围是否有效
    e = L.data[i - 1]; //将被删除的元素值赋值给e
    for (int j = i;j < L.length;j++) { //将第i个位置后的元素前移
        L.data[j - 1] = L.data[j];
    }
    L.length--; //线性表长度减1
    return true; //返回ture，删除操作成功。
}

时间复杂度分析：

删除操作的时间复杂度和插入操作的时间复杂度相同。

0x0205 顺序表的查找(按位查找)

实现：

1
2
3
4
5
6
7
8
9
/*** 
 * @description: 查找第i个元素，返回给定值.
 * @param {SqList} L
 * @param {int} i
 * @return {int}
 */
ElemType GetElemByIndex(SqList L, int i) {
    return L.data[i - 1];
}

时间复杂度分析：

直接返回值，时间复杂度 = $O\left(1\right)$

0x0206 顺序表的查找(按值查找)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*** 
 * @description: 查找具有给定关键字值的元素
 * @param {SqList} L
 * @param {int} e
 * @return {*}
 */
int GetElemByValue(SqList L, int e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1; //数组下标为i的元素值等于e，返回其位序i+1
        }
        return 0; //退出了循环，说明查找失败
    }
}

ps：C语言中不能用==来直接比较两个结构体变量。

时间复杂度分析：

最好情况：目标元素在表头。
循环1次；最好时间复杂度 = $O(1)$

最坏情况：目标元素在表尾
循环n次；最坏时间复杂度 = $O(n)$

平均情况：假设目标元素出现在任何一个位置的概率相同，概率都是$p = \cfrac 1n$
平均循环次数 = $1\cdot\cfrac1n+2\cdot\cfrac1n+3\cdot\cfrac1n+……+n\cdot\cfrac1n = [\frac{n(n+1)}2]·[\frac{1}{n}]=\frac{n+1}2$
$\therefore$ 平均时间复杂度 = $O(n)$