W.T.的博客

Every day to be a little better

数据结构与算法分析-线性表

发表于 更新于 分类于
本文字数： 22k 阅读时长 ≈ 20 分钟
顺序表，单链表，双链表，循环链式，静态链表

视频讲解，习题讲解，思维导图，PPT资源

链接: https://pan.baidu.com/s/1iprTv68hPqAS3-YmF1oVWw 提取码: b8hx

1. 线性表总览

数据结构三要素——逻辑结构、数据的运算、存储结构(物理结构)

存储结构不同，运算的实现方式不同

1.1. 线性表的定义-逻辑结构

Linear List：

Line 线 Eg:Sky line baby 天线宝宝

List 列表 Eg:a list of 一连串、一系列的

线性表是具有相同 数据类型的n(n≥0)个数据元素的有限序列，其中n为表长，当n = 0时线性表是一个空表。若用L命名线性表

其一般表示为 L = (a1, a2, … , ai, ai+1, … , an)

1.1.1. 线性表特点

$\circledast$ 表中元素的个数有限

$\circledast$ 表中元素具有逻辑上的顺序性，表中元素有其先后次序

$\circledast$ 表中元素都是数据元素，每个元素都是单个元素

$\circledast$ 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间

$\circledast$ 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容

所有的整数按递增次序排列，因长度不定，不是线性表

1.1.2. 线性表概念

  • ai 是线性表中的“第i个”元素线性表中的位序
  • a1是表头元素；an 是表尾元素。 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继

1.2. 线性表的基本操作-数据的运算

为什么要实现对数据结构的基本操作?

  1. 团队合作编程，你定义的数据结构要让别人能够很方便的使用(封装)
  2. 将常用的操作/运算封装成函数，避免重复工作，降低出错风险

Tips:比起学会“How”， 更重要的是想明白 “Why”

1.2.1. 创销

InitList(&L):初始化表。构造一个空的线性表L，分配内存空间。

DestroyList(&L):销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

1.2.2. 增、删

ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。

ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

1.2.3. 改、查

LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。

GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。

1.2.4. 其他常用操作

Length(L):求表长。返回线性表L的长度，即L中数据元素的个数。

PrintList(L):输出操作。按前后顺序输出线性表L的所有元素值。

Empty(L):判空操作。若L为空表，则返回true，否则返回false。

1.2.5. Tips

  1. 对数据的操作(记忆思路) —— 创销、增删改查
  2. C语言函数的定义 —— <返回值类型> 函数名 (<参数1类型> 参数1，<参数2类型> 参数2，……)
  3. 实际开发中，可根据实际需求定义其他的基本操作
  4. 函数名和参数的形式、命名都可改变(Reference:严蔚敏版《数据结构》) 一一Key:命名要有可读性
  5. 什么时候要传入引用“&” —— 对参数的修改结果需要“带回来”

1.3. 总结

2. 顺序表

2.1. 顺序表的定义

线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列 L = (a1, a2, … , ai, ai+1, … , an)

顺序表—用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

线性表L逻辑结构：a1—>a2—>a3—>a4—>a5

内存 线性表第一个元素的存放位置是LOC (L) LOC-location
a1 LOC(L)
a2 LOC(L)+数据元素的大小
a3 LOC(L)+数据元素的大小*2
a4 LOC(L)+数据元素的大小*3
a5 LOC(L)+数据元素的大小*4

ElemType 就是顺序表中存放的数据元素类型

如何知道一个数据元素大小

C语言 sizeof(ElemType)

1
2
3
4
typedef struct {
  int num; //号数 
  int people; //人数
} Customer;

sizeof(int) = 4B

sizeof(Customer) = 8B

2.2. 线性表的实现

2.2.1. 静态分配

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

给各个数据元素分配连续的存储空间，大小为MaxSize*sizeof(ElemType)

2.2.1.1. 实战

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
#include<stdio.h>
#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;
}

int main(){
  //声明一个顺序表
  SqList L;
  //初始化顺序表
  InitList(L);
  //遍历
  for(int i=0;i<L.length;i++){
    printf("%d\n",L.data[i]);
  }
  return 0;
}

内存分配

内存
data[0] 1. 内存中分配存储顺序表L的空间。包括：MaxSize*sizeof(ElemType)和存储length的空间
data[1] 2. 把各个数据元素的值设为默认值(可省略)
data[2]
data[3]
data[4]
data[5]
data[6]
data[7]
data[8]
data[9]
length 3. length值为0

Q：如果“数组”存满了怎么办?

A：可以放弃治疗，顺序表的表长刚开始确定后就无法更改(存储空间是静态的)

思考：如果刚开始就声明一个很大的内存空间呢?存在什么问题?

A：浪费空间

2.2.2. 动态分配

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

Key：动态申请和释放内存空间需要强制转型为你定义的数据元素类型指针

  • C - malloc、free函数

    头文件 #include<stdlib.h>

    L.data = (ElemType *) malloc (sizeof(ElemType) * InitSize);

    malloc 函数会申请一整片连续的存储空间

    返回一个指针，需要强制转型为你定义的数据元素类型指针

    返回的是申请的空间的首地址

  • C++ - new、delete 关键字

    L.data = new ElemType[InitSize];

2.2.2.1. 实战

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
#include<stdlib.h>
#define InitSize 10
typedef struct{
    int *data;
    int MaxSize;
    int length;
} SeqList;

//初始化
void InitList(SeqList &L){
  L.data = (int *)malloc(InitSize*sizeof(int));
  L.length=0;
  L.MaxSize = InitSize;
}
//增加动态数组的长度
void IncreaseSize(SeqList &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;
  //释放原来的内存空间
  free(p);
}
int main(){
  SeqList L;
  InitList(L);
  
  //扩容
  IncreaseSize(L,5);
  return 0;
}

内存分配

2.3. 顺序表的特点

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

静态分配、动态分配都一样

2.4. 顺序表的基本操作

2.4.1. 插入-O(n)

1$\leqslant$ i $\leqslant$ L.length+1

用存储位置的相邻来体现数据元素之间的逻辑关系

ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define MaxSize 10
typedef struct{
  int data[MaxSize];
  int length;
}SqList;

bool ListInsert(SqList &L,int i,int e){
  if(i<1||i>L.length+1){
    return false;
  }
  //存储空间已满
  if(L.length>=MaxSize){
    return false;
  }
  //第i个元素及之后的元素后移
  for(int j=L.length;j>=i;j--){
    L.data[j]=L.data[j-1];
  }
  L.data[i-1]=e;
  L.length++;
  return true;
}

问题规模 n = L.length (表长)

  • 最好情况：新元素插入到表尾，不需要移动元素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{1}{n+1}$ $\sum_{i=1}^{n+1}(n-i+1)$=$\frac{n(n+1)}{2}$ $\frac{1}{n+1}$=$\frac{n}{2}$

    平均时间复杂度 = O(n)

2.4.2. 删除-O(n)

1$\leqslant$ i $\leqslant$ L.length

ListDelete(&L,i,&e) 删除操作。删除表L中第i个位置的元素， 并用e返回删除元素的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool ListDelete(SqList &L,int i,int &e){
  if(i<1||i>L.length){
    return false;
  }
  e = L.data[i-1];
  for(int j=i;j<L.length;j++){
    L.data[j-1]=L.data[j];
  }
  L.length--;
  return true;
}

int main(){
  SqList L;
  InitList(L);
  
  int e = -1;
  if(ListDelete(L,3,e)){
    printf("已删除第3个元素，删除的元素值为%d\n",e);
  }else{
    printf("删除失败!");
  }
  return 0;
}

问题规模 n = L.length (表长)

  • 最好情况：删除表尾元素，不需要移动其他元素 i = n，循环 0 次;最好时间复杂度 = O(1)

  • 最坏情况：删除表头元素，需要将后续的 n-1 个元素全都向前移动 i = 1，循环 n-1 次;最坏时间复杂度 = O(n);

  • 平均情况：假设删除任何一个元素的概率相同，即 i=1,2,3, … , length 的概率都是 p = 1/n

    i=1,循环n-1次；i=2时,循环n-2次；i=3，循环n-3次 ……i=n时，循环0次

    平均循环次数 = (n-1)p + (n-2)p + …… + 1⋅p = $\frac{1}{n}$ $\sum_{i=1}^{n}(n-i)$=$\frac{n(n-1)}{2}$ $\frac{1}{n}$=$\frac{n-1}{2}$

    平均时间复杂度 = O(n)

2.4.3. 查找

2.4.3.1. 按位查找-O(1)

GetElem(L,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
//静态分配
#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];
    int length;
}SqList;

//定义最大长度
ElemType GetElem(SqList L, int i){ 
  return L.data[i-1];
}

//动态分配
#define InitSize 10
typedef struct{
    ElemType *data;
    int MaxSize;
    int length;
} SeqList;
 
ElemType GetElem(SeqList L, int i){ 
   //和访问普通数组的方法一样
   return L.data[i-1]; 
}

时间复杂度：O(1)

由于顺序表的各个数据元素在内存中连续存放,因此可以根据起始地址和数据元素大小立即找到第i个元素–“随机存取”

2.4.3.2. 按值查找-O(n)

LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//顺序表的初始长度
#define InitSize 10
typedef struct{
  //指示动态分配数组的指针
    ElemType *data;
  //顺序表的最大容量
    int MaxSize;
  //顺序表的当前长度
    int length;
} SeqList; //顺序表的类型定义(动态分配方式)

//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SeqList L,ElemType e){
	for(int i=0;i<L.length;i++){
    if(L.data[i]==e){
      //数组下标为i的元素值等于e，返回其位序i+1
      return i+1;
    }
  }
  return 0; //退出循环，说明查找失败
}

基本数据类型:int、char、double、 float 等可以直接用运算符“==”比较

Q：结构类型的数据元素也这样吗?

A：C语言中，结构体的比较不能直接用 “== ”，需要依次对比各个分量来判断两个结构体是否相等

Tips:

《数据结构》考研初试中，手写代码可以直接用“==”，无论 ElemType 是基本数据类型还是结构类型

手写代码主要考察学生是否能理解算法思想，不会严格要求代码完全可运行 有的学校考《C语言程序设计》，那么，也许就要语法严格一些

时间复杂度

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

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

  • 平均情况：假设目标元素出现在任何一个位置的概率相同，都是1/n

    目标元素在第1位，循环1次；在第2位，循环2次；…… ;在第n位，循环n次

    平均循环次数=1$\frac{1}{n}$+2$\frac{1}{n}$+3$\frac{1}{n}$+……+n$\frac{1}{n}$= $\frac{1}{n}$ $\sum_{i=1}^{n}i$=$\frac{n(n+1)}{2}$ $\frac{1}{n}$=$\frac{n+1}{2}$

    平均时间复杂度=O(n)

2.5. 总结

3. 单链表

3.1. 什么是单链表

逻辑结构：线性表 a1 - a2 - a3 - a4

顺序存储 链式存储
顺序表 L->a1 - a2 - a3 - a4 单链表 L->a1 -> a2 -> a3 -> a4
优点 可随机存取，存储密度高 不要求大片连续空间，改变容量方便
缺点 要求大片连续空间，改变容量不方便 不可随机存取，要耗费一定空间存放指针

3.2. 代码定义单链表

1
2
3
4
5
6
7
8
struct LNode{
  //数据域
  ElemType data;
  //指针域
  struct LNode *next;
}
//增加一个新的结点:在内存中申请一个结点所需空间，并用指针p指向这个结点
struct LNode *p = (struct LNode *) malloc(sizeof(struct LNode));

别名：typedef关键字 typedef <数据类型> <别名>

1
2
3
typedef int zhangsan;
zhangsan x = 1;
printf("%d",x); //1

故重命名：

1
2
3
4
5
6
7
8
9
struct LNode{
  //数据域
  ElemType data;
  //指针域
  struct LNode *next;
}
typedef struct LNode LNode;
typedef struct LNode *LinkList;
LNode *p = (LNode *) malloc(sizeof(LNode));

单链表定义

1
2
3
4
typedef struct LNode{
  ElemType data;
  struct LNode *next;
}LNode,*LinkList;

要表示一个单链表时，只需声明一个头指针 L ，指向单链表的第一个结点LNode *L,LinkList L

LNode *L 强调返回的是一个结点

``LinkList L `强调是一个单链表

3.3. 单链表的实现

3.3.1. 带头结点

引入头结点：

  1. 由于第一个数据点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理
  2. 无论链表是否为空，其头指针都指向头结点的非空指针(空表中头结点的指针域为空)，因此空表和非空表的处理也就得到统一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 = NULL;
  return true;
}

int main(){
  LinkList L;
  InitList(L);
  
  return 0;
}

内存

3.3.2. 不带头结点

不带头结点，写代码更麻烦。对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑。对空表和非空表的处理需要用不同的代码逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef struct LNode{
  ElemType data;
  struct LNode *next;
}LNode,*LinkList;

bool InitList(LinkList &L){
  L=NULL;//防止脏数据
  return true;
}
//判空
bool Empty(LinkList L){
  if(L==NULL){
    return true;
  }else{
    return false;
  }
}

int main(){
  LinkList L;
  InitList(L);
  
  return 0;
}

内存

3.4. 单链表基本操作

3.4.1. 插入

3.4.1.1. 按位序插入(带头结点)-O(n)

ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e. 找到第 i-1 个结点,将新结点插入其后

头结点可以看作 “第0个”结点

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
typedef struct LNode{
  ElemType data;
  struct LNode *next;
}LNode,*LinkList;
//插入
bool ListInsert(LinkList &L,int i,ElemType e){
  if(i<1)
    return false;
  //指针p指向当前扫描到的结点
  LNode *p;
  //当前p指向的是第几个结点
  int j=0;
  //L指向头结点，头结点第0个结点(不存数据)
  p=L;
  //循环找到第i-1个结点
  while(p!=NULL&&j<i-1){
    p = p->next;
    j++;
  }
  //i值不合法
  if(p==NULL){
    return false;
  }
  LNode *s = (LNode *)malloc(sizeof(LNode));
  s->data = e;
  //后插
  s->next = p->next;
  p->next = s;
  return true; 
}

平均时间复杂度:O(n)

i=1时，p指向头结点

i=5时,插在表尾

如果 i = 6(i>Lengh)

1
2
3
4
//i值不合法
if(p==NULL){
  return false;
}

3.4.1.2. 按位序插入(不带头结点)-O(n)

不存在 “第0个” 结点，因此i=1时，需要特殊处理

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
typedef 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;
    //初始化时L=NULL
    s->next = L;
    L=s;
    return true;
  }
  //指针p指向当前扫描到的结点
  LNode *p;
  //当前p指向的是第几个结点
  int j=1;
  //L指向第1个结点
  p=L;
  //循环找到第i-1个结点
  while(p!=NULL&&j<i-1){
    p = p->next;
    j++;
  }
  //i值不合法
  if(p==NULL){
    return false;
  }
  LNode *s = (LNode *)malloc(sizeof(LNode));
  s->data = e;
  //后插
  s->next = p->next;
  p->next = s;
  return true; 
}

i=1时，

如果i > 1，后续逻辑和带 头结点的一样

3.4.1.3. 指定结点的后插操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}

3.4.1.4. 指定结点的前插操作

  1. 从头指针开始遍历，求p前插结点 – O(n)

    bool InsertPriorNode(LinkList L,LNode *p,ElemType e)

  2. p后插结点，交换两者数据 – O(1)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    bool InsertPriorNode(LNode *p,ElemType e){
      if(p==NULL){
        return false;
      }
      LNode *s = (LNode *)malloc(sizeof(LNode));
      //内存分配失败
      if(s==NULL){
        return false;
      }
      //s插到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
    bool InsertPriorNode(LNode *p,LNode *s){
      if(p==NULL||s==NULL){
        return false;
      }
      s->next = p->next;
      p->next = s;
      //交换两者值
      ElemType temp = p->data;
      p->data = s->data;
      s->data = temp;
      return true;
    }

3.4.2. 删除

3.4.2.1. 按位序删除(带头结点)-O(n)

ListDelete(&L,i,&e):删除操作。

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

找到 i-1个结点，将其指针指向第i+1个结点，并释放第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
34
35
36
37
38
typedef struct LNode{
  ElemType data;
  struct LNode *next;
}LNode,*LinkList;

//删除
bool ListDelete(LinkList &L,int i,ElemType &e){
  if(i<1)
    return false;
  //指针p指向当前扫描到的结点
  LNode *p;
  //当前p指向的是第几个结点
  int j=0;
  //L指向第1个结点
  p=L;
  //循环找到第i-1个结点
  while(p!=NULL&&j<i-1){
    p = p->next;
    j++;
  }
  //i值不合法
  if(p==NULL){
    return false;
  }
  //第i-1结点后已无结点
  if(p->next==NULL){
    return false;
  }
  //q记录被删除结点
  LNode *q = p->next;
  //e返回元素值
  e = q->data;
  //q结点从链表中断开
  p->next = q->next;
  //释放结点存储空间
  free(q);
  return true; 
}

最坏、平均时间复杂度：O(n) 最好时间复杂度：O(1)

3.4.2.2. 按位序删除(不带头结点)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool ListDelete(LinkList &L,int i,ElemType &e){
  if(i<1){
    return false;
  }
  if(i==1){
    LNode *s = L;
    L = L->next;
    free(s);
  }
  LNode *p;
  int j=1;
  p = L;
  //same
  return true;
}

3.4.2.3. 指定结点的删除

bool DeleteNode(LNodwe *p)删除结点p，需要修改其前驱结点的next指针

  1. 传入头指针，循环寻找p的前驱结点

  2. 偷天换日-后插后交换值-O(1)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    bool DeleteNode(LNode *p){
      if(p==NULL){
        return false;
      }
      //q指向p后继
      LNode *q = p->next;
      if(p->next!=NULL){
        //交换p，q的值
        p->data = p->next->data;
        p->next = q->next;
      }
      free(q);
      return true;
    }

单链表的局限性：无法逆向检索，有时候不太方便

3.4.3. 查找

本节只探讨“带头结点”的情况

3.4.3.1. 按位查找 -O(n)

GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。 平均时间复杂度:O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
LNode* GetElem(LinkList L,int i){
  if(i<0){
    return NULL;
  }
  LNode *p;
  int j=0;
  p=L;
  while(p!=NULL&&j<i-1){
    p=p->next;
    j++;
  }
  return p;
}

王道版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LNode* GetElem(LinkList L,int i){
 	LNode *p = L->next;
  int j=1;
  if(i==0){
    return L;
  }
  if(i<1){
    return NULL;
  }
  while(p!=NULL&&j<i-1){
    p=p->next;
    j++;
  }
  return p;
}

3.4.3.2. 按值查找 - O(n)

LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。

1
2
3
4
5
6
7
8
LNode* LocateElem(LinkList L,ElemType e){
  //从第1个结点开始查找数据
  LNode *p = L->next;
  while(p!=NULL&&p->data!=e){
    p=p->next;
  }
  return p;
}

3.4.4. 求表长 - O(n)

1
2
3
4
5
6
7
8
9
int Length(LinkList L){
  int len = 0;
  LNode *p = L;
  while(p->next!=NULL){
    p=p->next;
    len++;
  }
  return len;
}

3.5. 建立单链表

如果给你很多个数据元素(ElemType)，要把它们存到一个单链表里边，怎么做?

  1. 初始化一个单链表
  2. 每次取一个数据元素，插入到表尾/表头

头插法、尾插法：核心就是初始化操作、指定结点的后插操作

3.5.1. 尾插法

初始化链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 = NULL;
  return true;
}

int main(){
  LinkList L;
  InitList(L);
  
  return 0;
}

尾插法建立单链表：初始化单链表，设置变量 length 记录链表长度

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
/*
While 循环 { 
  每次取一个数据元素 e;
  ListInsert (L, length+1, e) 插到尾部;
  length++; 
}
*/

//插入-每次都从头开始之后遍历，时间复杂度为O(n*n)
bool ListInsert(LinkList &L,int i,ElemType e){
  if(i<1)
    return false;
  //指针p指向当前扫描到的结点
  LNode *p;
  //当前p指向的是第几个结点
  int j=0;
  //L指向头结点，头结点第0个结点(不存数据)
  p=L;
  //循环找到第i-1个结点
  while(p!=NULL&&j<i-1){
    p = p->next;
    j++;
  }
  //i值不合法
  if(p==NULL){
    return false;
  }
  LNode *s = (LNode *)malloc(sizeof(LNode));
  s->data = e;
  //后插
  s->next = p->next;
  p->next = s;
  return true; 
}

建立尾指针，后插

3.5.1.1. 带头结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
LinkList TailInsert(LinkList &L){
  int x;
  L = (LinkList)malloc(sizeof(LNode));
  LNode *s,*r;
  r = L;
  scanf("%d",&x);
  while(x!=999){
    s = (LNode *)malloc(sizeof(LNode));
    s->data = x;
    
    r->next = s;
    //r指向新的表尾结点-永远保持r指向最后一个结点
    r = s;
    scanf("%d",&x);
  }
  r->next = NULL; 
  return L;
}

3.5.1.2. 不带头结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
LinkList TailInsert(LinkList &L){
  int x;
  L = (LinkList)malloc(sizeof(LNode));
  scanf("%d",&x);
  L->data = x;
  
  LNode *s,*r;
  r = L;
  
  while(x!=999){
    s = (LNode *)malloc(sizeof(LNode));
    s->data = x;
    
    r->next = s;
    r = s;
    scanf("%d",&x);
  }
  r->next = NULL; 
  return L;
}

3.5.2. 头插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
While 循环 { 
	每次取一个数据元素 e;
	InsertNextNode (L, e);
}
*/
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
16
17
18
19
//逆向建立单链表
LinkList List_HeadInsert(LinkList &L){ 
  LNode *s;
  int x; 
  //创建头结点
  L=(LinkList)malloc(sizeof(LNode)); 
  ////初始为空链表
  L->next=NULL;
  scanf("%d",&x); 
  while(x!=9999){
    //创建新结点
    s=(LNode*)malloc(sizeof(LNode)); 
    s->data=x;
    s->next=L->next;
    L->next=s;
    scanf("%d",&x); 
  }
  return L; 
}

不带头结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//逆向建立单链表
LinkList List_HeadInsert(LinkList &L){ 
  LNode *s;
  int x; 
  //创建头结点
  L=(LinkList)malloc(sizeof(LNode)); 
  ////初始为空链表
  L=NULL;
  scanf("%d",&x); 
  while(x!=9999){
    //创建新结点
    s=(LNode*)malloc(sizeof(LNode)); 
    s->data=x;
    s->next=L->next;
    L=s;
    scanf("%d",&x); 
  }
  return L; 
}

3.5.3. 删除[s,t]之间的结点

法一：从头扫描

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LNode *pre,*q,*p;
pre = L;
p = L->next;
while(p!=null){
  if(p->data>=s&&p->data<=t){
    q = p;
    p = p->next;
    //将pre的指针指向p的后继
    pre->next = p;
    free(q);
  }else{
    pre = p;
    p = p->next;
  }
}

法二：用尾插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
LNode *r,*q,*p;
r = L;
p = L->next;
while(p!=null){
  if(p->data<s||p->data>t){
    //不满足条件的链接到L尾部
    r->next = p; 
    r = p;
    //继续扫描
    p = p->next;
  }else{
    q = p;
    p = p->next;
    //满足条件的释放其空间
    free(q);
  }
}

3.6. 总结

4. 双链表

单链表:无法逆向检索，有时候不太方便

双链表:可进可退，存储密度更低一丢丢

4.1. 初始化

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

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
typedef struct DNode{
  ElemType data;
  struct DNode *prior,*next;
}DNode,*DlinkList;

bool InitDLinkList(DlinkList &L){
  L = (DNode*)malloc(sizeof(DNode));
  L->prior = NULL;
  l->next = NULL;
  return true;
}
//判空带头结点
bool Empty(DLinkList L){
  if(L->next == NULL){
    return true;
  }
  else{
    return false;
  }
}

int main(){
  DLinkList L;
  InitDLinkList(L);
  
  return 0;
}

4.2. 插入

1
2
3
4
5
6
7
8
9
10
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;
}

4.3. 删除

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
bool DeleteNextDNode(DNode *p){
  if(p==NULL)
    return false;
  DNode *q = p->next;
  // 删除的元素不存在
  if(q==NULL){
    return false;
  }
  p->next = q->next;
  if(q->next!=NULL){
    q->next->prior = p;
  }
  free(q);
  qNULL;
  return true;
}

//删除整个链表
void DestoryList(DLinkList &L){
  while(L->next!=NULL){
    DeleteNextNode(L);
  }
  free(L);
  L=NULL;
}

4.4. 遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//后向遍历
while (p!=NULL){ 
  //对结点p做相应处理，如打印 
  p = p->next;
}

//前向遍历
while (p!=NULL){ 
  //对结点p做相应处理 
  p = p->prior;
}

//前向遍历(跳过头结 点)
while (p-> prior != NULL){ 
  //对结点p做相应处理 
  p = p->prior; 
}

双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现。时间复杂度 O(n)

4.5. 建立双链表

4.5.1. 头插法

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
typedef struct DNode{
  ElemType data;
  struct DNode *next, *prior;
}DNode,*DLinkList;

DlinkList InitList(DLinkList &DL){
  DL = (DLinkList)malloc(sizeof(DNode));
  DL->next = NULL;
  DL->prior = NULL;
  
  int x;
  scanf("%d",&x);
  while(x!=9999){
    DNode *s=(DNode*)malloc(sizeof(DNode));
    s->data = x;
    s->next = DL->next;
    if(DL->next!=NULL){
      DL->next->prior=s;
    }
    s->prior=DL;
    DL->next=s;
    scanf("%d",&x);
  }
  return DL;
}

4.5.2. 尾插法

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
typedef struct DNode{
  ElemType data;
  struct DNode *next, *prior;
}DNode,*DLinkList;

DlinkList InitList(DLinkList &DL){
  DL = (DLinkList)malloc(sizeof(DNode));
  DL->next = NULL;
  DL->prior = NULL;
  
  DNode *r = DL;
  
  int x;
  scanf("%d",&x);
  while(x!=9999){
    DNode *s=(DNode*)malloc(sizeof(DNode));
    s->data = x;
    
    r->next = s;
    s->prior=r;
    r=s;
    scanf("%d",&x);
  }
  return DL;
}

4.6. 总结

5. 循环链表

5.1. 循环单链表


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;

//===============初始化=================
bool InitList(LinkList &L){
  L = (LNode*)malloc(sizeof(LNode));
  if(L==NULL){
    return false;
  }
  //头结点next指向头结点
  L->next = L;
  return true;
}
//================判空==================
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 true;
  }else{
    return false;
  }
}

从头结点找到尾部，时间复杂度为O(n)

从尾部找到头部，时间复杂度为O(1)

很多时候对链表的操作都是在头部或尾部，可以让L指向表尾元素 (插入、删除时可能需要修改L)

5.2. 循环双链表


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
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;
  }
  //头结点prior指向头结点
  L->prior = L;
  //头结点的next指向头结点
  l->next = L;
  return true;
}
//================判空==================
bool Empty(DLinkList L){
  if(L->next == L){
    return true;
  }
  else{
    return false;
  }
}
//============判断结点p是否为循环单链表的表尾结点============
bool isTail(DLinkList L,LNode *p){
  if(p->next == L){
    return true;
  }else{
    return false;
  }
}

5.2.1. 插入

1
2
3
4
5
6
7
bool InsertNextDNode(DNode *p,DNode *s){
  //s插入到p之后
  s->next=p->next;
  p->next->prior = s;
  s->prior = p;
  p->next = s;
}

5.2.2. 删除

1
2
3
4
5
6
7
bool DeleteNextDNode(DNode *p){
  DNode *q = p->next;
  p->next = q->next;
  q->next->prior = p;
  free(q);
  return true;
}

5.3. 总结

6. 静态链表

6.1. 什么是静态链表

单链表：各个结点在内存中星罗棋布、散落天涯。

静态链表：分配一整片连续的内存空间，各个结点集中安置。用数组的方式实现的链表

初始化静态链表: 把a[0]的next设为-1，把其他结点的 next 设为一个特殊值用来表示结点空闲，如 -2

每个数据元素4B，每个游标4B(每个结点共 8B) 设起始地址为 addr，e1的存放地址为 addr + 8*2

6.2. 用代码定义一个静态链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define MaxSize 10
struct Node{
  //数据元素
  ElemType data;
  //下一个元素数组下标
  int next;
};
//可用SLinkList定义一个长度为MaxSize的Node型数组
typedef struct Node SLinkList[MaxSize];

void testLinkList(){
  //数组a作为静态链表
  struct Node a[MaxSize];
}

王道

1
2
3
4
5
6
7
8
9
#define MaxSize 10
typedef struct{
  ElemType data;
  int next;
}SLinkList[MaxSize];

void testSLinkList(){
  SLinkList a;
}

SLinkList a ——相当于定义了一个长度为 MaxSize 的 Node型数组

6.3. 基本操作

6.3.1. 查找

从头结点出发挨个往后遍历结点

6.3.2. 插入位序为 i 的结点

  1. 找到一个空的结点，存入数据元素
  2. 从头结点出发找到位序为 i-1 的结点
  3. 修改新结点的 next
  4. 修改 i-1 号结点的 next

6.3.3. 删除某个结点

  1. 从头结点出发找到前驱结点
  2. 修改前驱结点的游标
  3. 被删除结点 next 设为 -2

6.4. 总结

优点：增、删 操作不需要大量移动元素

缺点：不能随机存取，只能从头结点开始依次往后查 找;容量固定不可变

适用场景:

  1. 不支持指针的低级语言;
  2. 数据元素数量固定不变的场景(如操作系统的文件分配表FAT)

7. 顺序表 V.S.链表

7.1. 逻辑结构

都属于线性表，都是线性结构

7.2. 物理结构

顺序表是顺序存储，链表是链式存储

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

7.3. 数据的运算-创销增删改查

顺序表 链表
创 需要预分配大片连续空间。 若分配空间过小，则之后不方便拓展容量;若分配空间过大，则浪费内存资源
静态分配：静态数组 - 容量不可变
动态分配：动态数组(malloc、free) - 容量可变，扩容时间代价高		 只需分配一个头结点(也可以不要头结点，只声明一个头指针)，之后方便拓展
销 修改 L.length = 0
静态分配：静态数组 - 系统自动回收空间
动态分配：动态数组(malloc、free) - 手动free		 依次删除各个 结点(free)
增删 插入/删除元素要将后续元素都后移/前移
时间复杂度 O(n)，时间开销主要来自移动元素
若数据元素很大，则移动的时间代价很高		 插入/删除元素只需修改指针即可
时间复杂度 O(n)，时间开销主要来自查找目标元素
查找元素的时间代价更低
查 按位查找:O(1)
按值查找:O(n) 若表内元素有序，可在 O(log2n) 时间内找到		 按位查找:O(n)
按值查找:O(n)
弹性(可扩容) 静态不可扩容，动态可扩容 可扩容

表长难以预估、经常要增加/删除元素 ——链表

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

7.4. 如何抉择

请描述顺序表和链表的… 实现线性表时，用顺序表还是链表好?

顺序表和链表的逻辑结构都是线性结构，都属于线性表。 但是二者的存储结构不同，顺序表采用顺序存储…(特点，带来的优点缺点)；链表采用链式存储…(特点、导致的优缺点)。

由于采用不同的存储方式实现，因此基本操作的实现效率也不同。当初始化时…;当插入一个数据元素时…;当删除一个数据元素时…;当查找一个数据元素时…

本文结束  感谢您的阅读
  • 本文作者： Wang Ting
  • 本文链接： /zh-CN/2020/02/07/数据结构-线性表/
  • 发布时间： 2020-02-07 14:56
  • 更新时间： 2023-03-10 22:13
  • 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！