数据结构与算法-02-线性表

线性表

定义

相同数据类型的 n 个数据元素 的有限序列
- 每个元素所占空间一样大
- 有次序
- 数据元素的位序从 1 开始
- n 叫作表长
  - n=0 时，线性表是空表
- 除表头元素每个元素都有一个直接前驱
- 除表尾元素每个元素都有一个直接后继

基本操作

初始化线性表
- 分配内存空间
销毁线性表
- 释放内存空间
插入
删除
按值查找
按位查找
什么时候需要传入参数的引用 “&” 【 c++ 中支持】
- 对参数的修改结果需要 “带回来”

顺序表

用顺序存储方式实现的线性表，逻辑相邻物理也相邻

定义

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

实现方式

静态分配

1
2
3
4
5
6


#define MaxSize 10	// 定义最大长度

typedef struct{
    ElemType data[MaxSize];  // 用静态的 数组 存放数据 ，ElemType 指的是数据类型 int...
    int length;    // 顺序表的当前长度 可以看存放了几个元素
}SqList;   // 顺序表的类型定义(静态分配方式)

定义后表长无法修改，顺序表的大小、容量不可变，存储空间是静态的

动态分配

1
2
3
4
5
6


#define InitSize 10     // 顺序表的初始长度
typedef struct{
    ElemType *data;     // 指示动态分配 数组的指针
    int MaxSize;    // 顺序表的最大容量
    int length;     // 顺序表的当前长度
}SqList;

c 语言中使用 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


#define InitSize 10

typedef struct{
	int *data;
	int MaxSize;
	int length;
}SqList;

void InitList(SqList &L){
    // 使用malloc 函数 申请一片连续的存储空间
	L.data = (int *)malloc(sizeof(int)*InitSize));
	L.length = 0;
	L.MaxSize = InitSize;
}

void IncreaseSize(SqList &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 L;
    InitList(L);
    // ... 给顺序表随便插入几个元素
    IncreaseSize(L,5);
    
    return 0;
}

顺序表的特点

优点
- 随机访问，可在 O(1) 时间内找到第 i 个元素
- 存储密度高
缺点
- 拓展容量不方便
- 插入、删除操作不方便

基本操作

基于静态分配实现的顺序表

插入操作

在表 L 的第 i 个位置插入指定元素

 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


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

void InitList(SqList &L){
    for(int i=0; i< MaxSize; i++){
        L.data[i]=0;  // 将所有元素设置为默认的初始值 0 
    }
    L.length = 0; // 顺序表初始长度 为 0 
}

//  提升代码的 健壮性  增加输入数据限制和操作反馈
bool ListInsert(SqList &L, int i , int e){
    /* 在顺序表 L 的 第i个位置 插入元素 e */
    if(i<1 || i>L.length+1) // 判断i的输入是否有效
        return false;
    if(L.length >= MaxSize) // 顺序表 已满时 不允许插入
        return false;
    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++;
    return true;
}

int main(){
    SqList L;   // 声明 顺序表  
    InitList(L);  // 初始化 顺序表
    // ... 在顺序表中 插入几个元素
    ListInsert(L,3,2) // 顺序表的 第 i 处 插入 元素 2
}

插入操作的时间复杂度
- 最坏 O(n)
- 最好 O(1)
- 平均 O(n)

删除操作

删除表 L 的第 i 个位置的元素，并用e返回删除元素的值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


bool ListDelete(SqList &L, int i, int &e){
    if(i<1 || i>L.length) // 判断i的范围是否有效
        return false;
    e = L.data[i-1];  // 将被删除的元素 复制给 e
    for(int j=i; j<L.length; j++){ // 被删除元素 位置之后的元素 前移
        L.data[j-1] = L.data[j];
    }
    L.length--;
    return true;
}

删除操作的时间复杂度
- 最坏 O(n)
- 平均 O(n)
- 最好 O(1)

链表

链表是用链式存储的顺序表

单链表

每个结点除了存放数据元素还要存储指向下一个元素的指针
优点：不要求大片连续空间，改变容量方便
缺点：不支持随机存储，要耗费一定空间存放指针
头结点是一个空节点，不存放数据的空结点
- 只能在头结点之后插入和删除

代码定义：

1
2
3
4


typedef struct LNode{   // 定义单链表 结点类型
    ElemType data;      // 数据域：每个结点 存放一个数据元素
    struct LNode *next; // 指针域：指针指向 下一个结点
} LNode, *LinkList; // 别名 第一个是 结点LNode, 第二个是 指向结点的指针类型 的别名 

链表增加新的结点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


// 增加一个新的结点
struct LNode *p = (struct LNode*)malloc(sizeof(struct LNode));
// 申请一片内存空间，并用指针 p 指向这个结点
// 使用了 typedef 后  struct LNode 就用它的别名 LNode 即可
// 等价于
LNode *p = (struct LNode*)malloc(sizeof(LNode));

// typedef 等价于
typedef struct LNode LNode;
typedef struct Lnode *LinkList;

LNode * 强调这是一个结点
LinkList 强调这是一个链表

不带头结点的单链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


typedef struct LNode{
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

bool InitList(LinkList &L){
    L = Null;   // 空表  暂时没有任何结点  防止脏数据
    return true;
}

bool Empty(LinkList L){
    return (L==Null);
}

void test(){
    LinkList L; // 声明一个指向链表的指针; 注意 此处并没有创建一个结点
    // 初始化一个空表
    InitList(L);
}

带头结点的单链表

 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


typedef struct LNode{
    ElemType data;  // 数据域
   	struct LNode *next; // 指针域
} LNode, *LinkList;

// 初始化一个带头结点的单链表
bool InitList(LinkList &L){
    L = (LNode *)malloc(siezeof(LNode)); // 分配一个头结点
    if(L==NULL)
        return false;  // 内存不足 分配失败
    L->next = NULL;    // 头结点 之后 暂无 结点
    return true;
}

void test(){
    LinkList L; // 声明一个指向链表的指针
    InitList(L); // 初始化 空 链表
}

// 判断带头结点 的单链表 是否为空
bool empty(Linklist L){
    if(L->next == NULL)
        return true;
    else
        return false;
}

带头结点的链表写代码更方便插入、删除等基本操作更好写

插入

按位序插入

带头结点

->（箭头运算符）的本质是：通过指向结构体的指针，访问该结构体内部的成员

 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


typedef struct LNode{
    ElemType data;
    struct LNode * next;
}LNode, *LinkList;

/*
在第i个位置插入元素e

本质：先找到第i-1个元素 
把新插入的节点的后继 指向第i-1个元素的后继
再将第i-1个元素的 后继 指向插入的节点

*/
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
        return false;
    LNode *p;  // 指针p 当前扫描到的结点
    int j=0;   // while 循环中  当前的 p 指向哪个结点
    p = L; //L指向头结点，头结点是第0个结点（不存放数据）
    while(p!=NULL && j<i-1){ // 找到第i个结点
        p = p->next;
        j++;
    }
    if(p==NULL){   // i值不合法：第 i-1 个结点不存在的情况
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s; // 将结点s连到p之后
    return true;
}

不带头结点

插入和删除第一个元素时，需要更改头指针。

 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


typeded struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

bool ListInsert(LinkList &L, int i, Elemtype e){
    if(i<1)
        return false;
    if(i==1){
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;
        L = s;    // 头指针 指向新结点
        return true;
    }
    LNode *p;
    int j=1;
    p=L;
    while(p!=NULL && j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL)
        return fals;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return ture;
}

指定节点后插操作

带头结点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

bool InsertNextNode(LNode *p, ElemType e){
    if(p==NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if(s==NULL)   // 某些情况可能会分配失败 （内存不足）
        return false;  // 考试可以不写
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

指定节点前插操作

不传入头结点，虽然前驱结点未知但是可以插入在其之后交换其存放的数据的值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


bool InsertPriorNode(LNode *p, Elemtype e){
    if(p==NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if(s==NULL)
        return false;
    /*
    新结点 连接到p之后，把p原来的值赋给新节点, 再把插入新节点的值赋给p
    */
    s->next = p->next;
    p->next = s;
    s->data = p->data;
    p->data = e;
    return true;
}

删除

按位序删除（带头结点）

 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


typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

bool ListDelete(LinkList &L, int i, ElemType e){
    if(i<1)
		return false;
    LNode *p;
    int j = 0;
    p = L;   // L指向头结点， 头结点是 第 0 个结点（不存放数据）
    
    while(p!=NULL && j<i-1){ // 循环找到 第 i-1个结点
        p=p->next;
        j++;
    }
    if(p==NULL)
        return false;
    if(p->next == NULL)  // 第i个结点后 已经无其他结点
        return false;
    LNode *q = p->next; // 令 q 指向 需要被删除的结点
    e = q->data;   // 用 e 返回被删除元素的值
    p->next = q->next;  // 将*q结点 从链表断开
    free(q);   // 释放结点 的 存储空间
    return true;    // 删除成功
}

删除指定节点

类似于前插操作的实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


bool DeleteNode(LNode *p){
	if(p==NULL)
		return false;
	LNode *q = p->next;
    p->data = q->data;
    p->next = q->next;
    free(q);
    return ture;
}
// 但是如果 删除的结点是 最后一个结点 就会报错

双链表

在单链表的基础上增加一个指针域，指向前驱结点

1
2
3
4


typedef struct DNode{
    ElemType data;
    struct DNode *prior, *next;
}DNode, *LinkList;

双链表的初始化(带头结点)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


bool InitDLinkList(DlinkList &L){
    L = (DNode *)malloc(sizeof(DNode)); //分配一个头结点
    if(L==NULL) // 内存不足分配失败
        return false;
    L->prior = NULL; // 头结点的 前驱指针 永远指向NULL
    L->next = NULL;  // 头结点 之后 暂时没有节点
    return true;
}

void test(){
    DLinkList L;  // 声明双链表
    InitDLinkList(L);  // 初始化 双链表
	// ...
}

双链表的后插操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


// 在p结点  之后 插入 s结点
bool InsertNextDNode(DNode *p, DNode *s){
	if(p==NULL || s== NULL)
        return false;
    s->next = p->next;
    if(p->next != NULL)
        p->next->prior = s;
    s->prior = p;
    p->next = s;
    return true;
}

双链表的删除

需要注意边界条件

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


// 删除在p结点 的后继结点q
bool DeleteNextDNode(DNode *p){
	if(p==NULL)
        return false;
     DNode *q = p->next; // 找到p的后继 q
    if(q==NULL)
        return false;
    p->next = q->next;
    if(q->next != NULL)
    	q->next->prior = p;
	free(q);
    return true;
}

void DestoryDLinkList(DLinkList &L){
    while(L->next != NULL)
        DeleteNextDNode(L);
    free(L);
    L=NULL;
}

双链表的遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


// 后向遍历
while(p!=NULL)
    p=p->next;

// 前向遍历
while(p!=NULL)
    p=p->prior;

// 前向遍历 跳过 头结点
while(p->prior != NULL)
    p=p->prior;

双链表不可随机存取；按位查找、按值查找操作都只能用遍历的方式实现

循环链表

循环单链表

表尾结点的 next 指针指向头结点
从一个结点出发可以找到其它任何一个结点

 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


typedef struct LNode{
	ElemType data;
	struct LNode *next;
} LNode, *LinkList;

// 初始化一个循环单链表
bool InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LNode));
    if(L==NULL)
        return false;
    L->next = L;
    return ture;
}

// 判断循环单链表是否为空
bool empty(LinkList L){
    if(L->next == L)
        return true;
    else
        return false;
}
// 判断结点p 是否为循环单链表的表尾结点
bool isTail(LinkList L, LNode *p){
    if(p->next == L)
        return ture;
    else
        return false;
}

循环双链表

表头结点的 prior 指向表尾结点
表尾结点的 next 指向表头结点

 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


typedef struct DNode{
    ElemType data;
    struct DNode *prior, *next;
} DNode, *DLinkList;

// 循环双链表的初始化
bool InitDlinkList(DLinkList &L){
    L = (DNode *)malloc(sizeof(DNode));
    if(L==NULL)
        return false;
    L->prior = L;
    L->next = L;
    return true;
}

void test(){
    DLinkList L;
    InitDlinkList(L);
    // ...
}

// 插入操作
// 在p结点之后插入s
bool InsertNextDNode(DNode *p, DNode *s){
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;
    return true;
}

// 删除p 的后继结点s
p->next=q->next;
q->next->prior = p;
free(q);

静态链表

用数组方式实现的链表

分配一整片的连续内存空间，各个结点集中安置

优点
- 增删操作不需要大量移动元素
缺点
- 不能随机存取，只能从头结点开始依次往后查找
- 容量固定不变
适用场景
- 不支持指针的低级语言
- 数据元素固定不变的场景
  - 如操作系统的文件分配表 FAT

静态链表定义

1
2
3
4
5
6
7
8
9


#define MaxSize 10  // 静态链表的最大长度

struct Node{        // 静态链表结构类型的定义
    ElemType data;  // 存储数据元素
    int next;       // 下一个元素的数组下标（游标）
}
// } SLinkList[MaxSize];  较少用这个别名进行定义

// SLinkList 可以用来定义 “一个长度为 MaxSize 的Node 型数组”

插入位序为i的结点

找到一个空的结点，存入数据元素
- 判断结点为空，可以在初始化的时候把游标设置为一个特殊值比如都赋值 -2
从头结点出发找到位序为 i-1的结点
修改新结点的 next
修改 i-1号结点的 next

顺序表和链表的对比

逻辑结构

都是线性表

物理结构（存储结构）

顺序表随机存取存储密度高
- 大片连续空间分配不方便
链表离散的小空间分配，改变容量方便
- 不可随机存取存储密度低

基本操作

创建
- 线性表需预分配大片连续空间
  - 静态分配内存大小不可变
  - 动态分配如需改变需要移动大量元素
- 链表
  - 只需要分配一个头结点(也可不分配，只声明一个头指针)，方便拓展
销毁
- 链表依次删除 free
- 顺序表先修改表长
  - 静态分配系统自动回收
  - 动态数组手动free
增删
- 时间复杂度都是 O(n)
  - 但链表的开销更小
查找
- 按位查找
  - 顺序表 O(1)
  - 链表 O(n)
- 按值查找
  - 顺序表无序O(n) 有序 O(log_2 n)
  - 链表 O(n)

表长难以估计、经常需要增加/删除用链表

表长可预估查询(搜索) 操作较多用顺序表

如顺序表和链表的开放式问题的答题思路
- 从逻辑结构、存储结构、运算操作三个方便阐述各自特点再给出结论

线性表

定义

基本操作

顺序表

定义

实现方式

静态分配

动态分配

顺序表的特点

基本操作

插入操作

删除操作

链表

单链表

不带 头结点 的单链表

带头结点 的 单链表

插入

按位序插入

指定节点后插操作

指定节点前插操作

删除

按位序删除（带头结点）

删除指定节点

双链表

双链表的初始化(带 头结点)

双链表的后插操作

双链表的删除

双链表的遍历

循环链表

循环单链表

循环双链表

静态链表

静态链表定义

插入位序为i的结点

顺序表 和 链表的对比

逻辑结构

物理结构（存储结构）

基本操作

不带头结点的单链表

带头结点的单链表

双链表的初始化(带头结点)

顺序表和链表的对比