TIP

《数据结构》复习笔记

# 1 绪论

# 1.1 数据结构的三要素

  • 逻辑结构
    • 线性结构
    • 非线性结构
  • 存储结构
    • 顺序存储
    • 链式存储
    • 索引存储
    • 散列存储
  • 数据的运算

# 1.2 算法的基本概念

# 1.2.1 数据结构的基本概念

  • 数据
  • 数据元素 数据的基本单位,通常作为一个整体来考虑,可以由若干个数据项组成
  • 数据项 构成数据元素的不可分割的最小单位
  • 数据对象 具有相同性质的数据元素的集合,是数据的子集

# 1.2.1 算法的特性

  • 有穷性
  • 确定性
  • 输入
  • 输出
  • 可行性

# 1.2.2 效率的度量 !

  • 时间复杂度 将算法中基本操作的执行次数作为算法时间复杂度的度量
  • 空间复杂度 存储空间的度量

# 2 线性表(Linear List)

  • 顺序存储
    • 顺序表
  • 链式存储
    • 单链表
    • 双链表
    • 循环链表
    • 静态链表

# 2.1 定义

线性表是具有相同数据类型nn数据元素有限序列

# 2.2 顺序表示(Sequence List) !

  • 物理结构顺序与逻辑结构顺序相同
  • 排序后的更容易操作,不需要每次都全部搜索

TIP

这里用的位序是从 11nn 的,而真正物理结构数组的索引号是从 00n1n-1 的,注意区别

typedef int ElemType;
typedef struct {
  ElemType data[MaxSize];
  int length;
} SqNode, *SqList;
SqList Init();
void Print(SqList PtrL);
bool Insert(SqList PtrL, int i, ElemType e);
bool Delete(SqList PtrL, int i, ElemType &e);
int Locate(SqList PtrL, ElemType e);
int main() {
  SqList PtrL = Init();
  Insert(PtrL, 1, 100);
  Insert(PtrL, 2, 45);
  Print(PtrL);
  ElemType e;
  if (Delete(PtrL, 1, e)) {
    cout << "Delete successful, value is " << e << endl;
  };
  Print(PtrL);
  return 0;
}
SqList Init() {
  /**
   * 返回新建顺序表的指针
   */
  SqList PtrL;
  PtrL = (SqList)malloc(sizeof(SqNode));
  PtrL->length = 0;
  return PtrL;
}
void Print(SqList PtrL) {
  /**
   * 打印列表
   */
  if (PtrL->length == 0) {
    cout << "List is empty!" << endl;
    return;
  }
  cout << "Data:";
  for (int i=0; i < PtrL->length; i++) {
    cout << PtrL->data[i] << " ";
  }
  cout << endl;
}
bool Insert(SqList PtrL, int i, ElemType e) {
  /**
   * 将新的元素插入列表中
   */
  if (i > PtrL->length+1 || i < 1) {
    cout << "位置非法" << endl;
    return false;
  }
  if (PtrL->length >= MaxSize) {
    cout << "存储已满" << endl;
    return false;
  }
  for (int j=PtrL->length-1; j>=i; j--) {
    PtrL->data[j] = PtrL->data[j-1];
  }
  PtrL->data[i-1] = e;
  PtrL->length++;
  return true;
}
bool Delete(SqList PtrL, int i, ElemType &e) {
  /** 删除 PtrL 所指顺序表中第 i 个元素
   * 如果成功,则返回 true ,并使用引用变量 e 返回被删除元素的值
   * 否则返回 false
   */
  if (i < 1 || i > PtrL->length) {
    cout << "位置不合法";
    return false;
  }
  e = PtrL->data[i-1];
  for (int j=i; j<PtrL->length; j++) {
    PtrL->data[j-1] = PtrL->data[j];
  }
  PtrL->length--;
  return true;
}
int Locate(SqList PtrL, ElemType e) {
  /** 在查找顺序表第一个元素值等于 e 的元素,并返回其位序
   * 如果失败,返回 0
   */
  for (int i = 0; i < PtrL->length; i++) {
    if (PtrL->data[i] == e) {
      return i+1;
    }
  }
  return 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

# 2.3 链式表示(Linked List) !

  • 求长度和按 index 查找明显变慢,但是删除和插入操作明显变简单
  • 删除和插入要注意操作顺序

关于带不带头结点

如非明确说明,默认带头结点

# 2.3.1 单链表(Single Linked List)

typedef int ElemType;
typedef struct _node {
  ElemType data;
  struct _node *next;
} LinkNode, *LinkList;
LinkList Init();
void Print(LinkList PtrL);
void HeadInsert(LinkList PtrL, ElemType e);
void TailInsert(LinkList PtrL, ElemType e);
LinkList Get(LinkList PtrL, int i);
int Locate(LinkList PtrL, ElemType e);
bool Insert(LinkList PtrL, int i, ElemType e);
bool Delete(LinkList PtrL, int i, ElemType &e);
int Length(LinkList PtrL);
int main() {
  LinkList PtrL = Init();
  HeadInsert(PtrL, 1);
  TailInsert(PtrL, 2);
  Print(PtrL);
  LinkList PtrN = Get(PtrL, 2);
  if (PtrN) {
    cout << "Get successful, value is " << PtrN->data << endl;
  };
  cout << "Elem 2 is at " << Locate(PtrL, 2) << endl;
  Insert(PtrL, 2, 3);
  Print(PtrL);
  ElemType e;
  if (Delete(PtrL, 2, e)) {
    cout << "Delete successful, value is " << e << endl;
  };
  Print(PtrL);
  cout << "Total length is " << Length(PtrL) << endl;
  return 0;
}
LinkList Init() {
  LinkList PtrL;
  PtrL = (LinkList)malloc(sizeof(LinkNode));
  PtrL->next = NULL;
  return PtrL;
}
void Print(LinkList PtrL) {
  /**
   * 打印列表
   */
  if (PtrL->next == NULL) {
    cout << "List is empty!" << endl;
    return;
  }
  LinkList curr = PtrL;
  cout << "Data: ";
  while (curr->next) {
    cout << curr->next->data << " ";
    curr = curr->next;
  }
  cout << endl;
}
void HeadInsert(LinkList PtrL, ElemType e) {
  /** 头插法插入元素
   * 将新的元素插入头结点之后
   */
  LinkList PtrNewNode;
  PtrNewNode = (LinkList)malloc(sizeof(LinkNode));
  PtrNewNode->data = e;
  PtrNewNode->next = PtrL->next;
  PtrL->next = PtrNewNode;
}
void TailInsert(LinkList PtrL, ElemType e) {
  /** 尾插法插入元素
   * 将新的元素插入尾部
   */
  LinkList curr = PtrL;
  while (curr->next) {
    curr = curr->next;
  }
  curr->next = (LinkList)malloc(sizeof(LinkNode));
  curr->next->data = e;
  curr->next->next = NULL;
}
LinkList Get(LinkList PtrL, int i) {
  /** 获取表中第 i 个位置指针
   * 如果失败,返回 NULL
   */
  LinkList curr = PtrL->next;
  int j = 1;
  while (curr) {
    if (j == i) {
      return curr;
    }
    j++;
    curr = curr->next;
  }
  return NULL;
}
int Locate(LinkList PtrL, ElemType e) {
  /** 在查找顺序表第一个元素值等于 e 的元素,并返回其位序
   * 如果失败,返回 0
   */
  int i = 1;
  LinkList curr = PtrL->next;
  while (curr) {
    if (curr->data == e) {
      return i;
    }
    i++;
    curr = curr->next;
  }
  return 0;
}
bool Insert(LinkList PtrL, int i, ElemType e) {
  /**
   * 将新的元素到第 i 个位置
   */
  LinkList PtrFront = Get(PtrL, i-1);
  if (PtrFront == NULL) return false;
  LinkList PtrNewNode = (LinkList)malloc(sizeof(LinkNode));
  PtrNewNode->data = e;
  PtrNewNode->next = PtrFront->next;
  PtrFront->next = PtrNewNode;
  return true;
}
bool Delete(LinkList PtrL, int i, ElemType &e) {
  /** 删除 PtrL 所指顺序表中第 i 个元素
   * 如果成功,则返回 true ,并使用引用变量 e 返回被删除元素的值
   * 否则返回 false
   */
  LinkList PtrFront = Get(PtrL, i-1);
  if (PtrFront == NULL || PtrFront->next==NULL) return false;
  LinkList tmp = PtrFront->next;
  PtrFront->next = tmp->next;
  e = tmp->data;
  free(tmp);
  return true;
}
int Length(LinkList PtrL) {
  /** 获取列表长度
   */
  int i = 0;
  LinkList curr = PtrL;
  while (curr->next) {
    i++;
    curr = curr->next;
  }
  return 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

做题时经常遇到的问题

删除最后一个元素的话,即便是有尾指针也是没用的,因为需要将上一个结点 nextnextNULLNULL ,但是尾指针做不到,除非是双链表

# 2.3.2 双链表(Double Linked List)

typedef int ElemType;
typedef struct _node {
  ElemType data;
  struct _node *prior, *next;
} DNode, *DLinkList;
1
2
3
4
5

# 2.3.3 循环链表(Circular Linked List)

  • 循环单链表(Single Circular Linked List)

    最后一个结点指向第一个结点而不是 NULLNULL,即带头结点则指向头结点

  • 循环双链表(Double Circular Linked List)

# 2.3.4 静态链表(Static Linked List)

使用数组存储,指针域实际存储的是数组下标

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

# 2.3.5 多重链表(Multiple List)

  • 多重链表中结点的指针域会有多个
  • 但包含两个指针域的链表并不一定是多重链表,比如双向链表就不是多重链表。
  • 用途 基本上如树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储。

    稀疏矩阵的存储 -> 使用十字链表(一种典型的多重链表)存储,即使用两个指针域(Right、Down)将同行和同列串起来

矩阵的各种表示方法

  • 使用数组
    • 二维数组
    • 一维数组 用于存储某些特殊结构或者稀疏矩阵
      • 某些特殊结构(比如对角阵、三角阵,下标与二维数组的下标有着对应关系,根据对应关系进行存储)
      • 稀疏矩阵 使用三元组数组即可,三元组定义如下
        typedef struct {
           int val;    // 数值
           int i, j;   // 位置
        } Trimat;
        
        1
        2
        3
        4
  • 使用链表
    • 邻接表
    • 十字链表

# 2.4 广义表(Generalized List)

广义表是线性表的推广,其数据域不仅可以是单元素,也可以是另一个广义表

#define MaxSize 50
typedef ElemType int;
typedef struct _node {
  int tag;
  union {
    ElemType data;            // 用以标记该结点数据是另一个广义表还是单元素(0->单元素,1->广义表)
    struct _node *subList;    // 子表指针域subList与单元素数据域Data复用,即共用存储空间
  };
  struct _node *next;
} GNode, *GList;
1
2
3
4
5
6
7
8
9
10
11

# 3 堆栈(Stack)

  • 顺序栈
  • 链栈
  • 共享栈

# 3.1 基本概念 !

# 3.1.1 定义

一种只能在一端进行插入或删除操作的线性表

  • 栈顶:允许进行插入或删除操作的一端
  • 栈底:固定不变的一端

# 3.1.2 特点

先进后出(FILO)

# 3.1.3 数学性质

nn 个元素以某种顺序进栈,并且可在任意时刻出栈(在满足先进后出的前提下)时,所获得的元素排列的数目 NN 恰好满足函数 Catalan()Catalan() 的计算,即

N=1n+1C2nn N = \frac{1}{n+1}C_{2n}^n

# 3.2 顺序存储

使用顺序结构存储的栈










































 







 








 

















#include <iostream>
#define MaxSize 50
using namespace std;
typedef int ElemType;
typedef struct {
  ElemType data[MaxSize];
  int top;
} SNode, *SqStack;
SqStack InitStack();
bool isEmpty(SqStack PtrS);
bool Push(SqStack PtrS, ElemType x);
bool Pop(SqStack PtrS, ElemType &x);
bool GetTop(SqStack PtrS, ElemType &x);
void DestroyStack(SqStack PtrS);
int main() {
  ElemType x;
  SqStack PtrS = InitStack();
  Push(PtrS, 100);
  GetTop(PtrS, x);
  Pop(PtrS, x);
  cout << x << endl;
  cout << isEmpty(PtrS) << endl;
  DestroyStack(PtrS);
  return 0;
}
SqStack InitStack() {
  /** 初始化一个空栈 */
  SqStack PtrS = (SqStack)malloc(sizeof(SNode));
  PtrS->top = -1;
  return PtrS;
}
bool isEmpty(SqStack PtrS) {
  /** 判断一个栈是否为空
   * 若为空返回 true
   * 否则返回 false
   */
  return PtrS->top == -1;
}
bool Push(SqStack PtrS, ElemType x) {
  /** 进栈
   * 若栈未满,则将 x 加入使之成为新栈顶
   */
  if (PtrS->top == MaxSize-1) return false;
  PtrS->data[++(PtrS->top)] = x;
  return true;
}
bool Pop(SqStack PtrS, ElemType &x) {
  /** 出栈
   * 若栈非空,则弹出栈顶元素,并用 x 返回
   */
  if (isEmpty(PtrS)) return false;
  x = PtrS->data[PtrS->top--];
  return true;
}
bool GetTop(SqStack PtrS, ElemType &x) {
  /** 读栈顶元素
   * 若栈非空,则用 x 返回栈顶元素
   */
  if (isEmpty(PtrS)) return false;
  x = PtrS->data[PtrS->top];
  return true;
}
void DestroyStack(SqStack PtrS) {
  /** 销毁栈 */
  free(PtrS);
}
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

OOP 版:

#include <iostream>
#define MaxSize 50
typedef int ElemType;
class Stack {
public:
  Stack() {
    top = -1;
  }
  bool isEmpty() {
    return (top == -1);
  }
  ElemType peek() {
    return data[top];
  }
  ElemType push(ElemType value) {
    return data[++top] = value;
  }
  ElemType pop() {
    return data[top--];
  }
  int getSize() {
    return top+1;
  }
private:
  int data[MaxSize];
  int top;
};
int main() {
  Stack stack;
  for (int i = 0; i < 10; i++) {
    stack.push(i);
  }
  while (!stack.isEmpty()) {
    std::cout << stack.pop() << std::endl;
  }
  return 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
31
32
33
34
35
36
37
38
39

考题中如何使用


 
 

 

 

// 初始化
int stack[maxSize];
int top = -1
// 元素 x 进栈
stack[++top] = x;
// 元素 x 出栈
x = stack[top--];
1
2
3
4
5
6
7

关于 ++i 与 i++

具体区别不赘述,很明显 ++i 应当是比 i++ 效率高的,所以当他们等效的时候(不返回值),++i 会有更高的效率,但是值得注意的是,当两者等效的时候,编译器自然也会进行优化,对内建数据类型来说(如果是 C 的话,只有内建数据类型可以用,而 C++ 自定义类型可通过运算符重载获得 ++),两者完全没有区别(可以看得到的汇编代码),但如果是自定义类型的话,后缀式需要保存更改前的值并返回,这将引起极大的复制开销

  • 内建类型按你喜欢的来就好
  • 自定义类型建议使用前缀式

ref ++i 与 i++哪个效率更高?

# 3.2.1 共享栈

使用一个数组实现两个堆栈

一个栈底在左端,一个栈底在右端,可以充分利用数组空间

#define MaxSize 50
typedef int ElemType;
typedef struct {
  ElemType data[MaxSize];
  int top0;
  int top1;
} SNode, *SaStack;
1
2
3
4
5
6
7
8

TIP

  • 栈空 分别判断
    • 0 号栈 top0 = -1
    • 1 号栈 top1 = MaxSize
  • 栈满 top1 - top0 == 1

# 3.3 链式存储

使用链表结构存储的栈

如果使用链尾作为 Top,则难以实现 Pop 操作,故 Top 应在链头

#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct _node {
  ElemType data;
  struct _node *next;
} LinkNode, *LiStack;
LiStack InitStack();
bool isEmpty(LiStack PtrS);
bool Push(LiStack PtrS, ElemType x);
bool Pop(LiStack PtrS, ElemType &x);
bool GetTop(LiStack PtrS, ElemType &x);
void DestroyStack(LiStack PtrS);
int main() {
  ElemType x;
  LiStack PtrS = InitStack();
  Push(PtrS, 100);
  GetTop(PtrS, x);
  Pop(PtrS, x);
  cout << x << endl;
  cout << isEmpty(PtrS) << endl;
  DestroyStack(PtrS);
  return 0;
}
LiStack InitStack() {
  /** 初始化一个空栈 */
  LiStack PtrS = (LiStack)malloc(sizeof(LinkNode));
  PtrS->next = NULL;
  return PtrS;
}
bool isEmpty(LiStack PtrS) {
  /** 判断一个栈是否为空
   * 若为空返回 true
   * 否则返回 false
   */
  return PtrS->next == NULL;
}
bool Push(LiStack PtrS, ElemType x) {
  /** 进栈
   * 将 x 加入使之成为新栈顶
   */
  PtrS->next = (LiStack)malloc(sizeof(LinkNode));
  PtrS->next->data = x;
  PtrS->next->next = NULL;
  return true;
}
bool Pop(LiStack PtrS, ElemType &x) {
  /** 出栈
   * 若栈非空,则弹出栈顶元素,并用 x 返回
   */
  if (isEmpty(PtrS)) return false;
  LiStack curr = PtrS;
  while (curr->next->next) {
    curr = curr->next;
  }
  x = curr->next->data;
  free(curr->next);
  curr->next = NULL;
  return true;
}
bool GetTop(LiStack PtrS, ElemType &x) {
  /** 读栈顶元素
   * 若栈非空,则用 x 返回栈顶元素
   */
  if (isEmpty(PtrS)) return false;
  LiStack curr = PtrS;
  while (curr->next) {
    curr = curr->next;
  }
  x = curr->data;
  return true;
}
void DestroyStack(LiStack PtrS) {
  /** 销毁栈 */
  LiStack curr = PtrS;
  while (curr->next) {
    LiStack PtrDest = curr;
    curr = curr->next;
    free(PtrDest);
  }
}
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

# 3.4 应用

# 3.4.1 在括号匹配中的应用

bool match(char exp[], int n) {
   char stack[maxSize];
   int top = -1;
   for (int i=0; i<n; i++) {
      if (exp[i] == '(') {
         stack[++top] = '(';
      }
      else if (exp[i] == ')') {
         if (top == -1) return false;
         top--;
      }
   }
   if (top != -1) return false;
   return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  • '(' 压栈
  • ')' 出栈 若已空则不匹配
  • 最后校验栈是否为空

# 3.4.2 在表达式求值中的应用

由于后缀表达式比中缀表达式更容易处理(没有括号,不需考虑优先级,有固定的运算顺序),所以会先将中缀表达式转换成后缀表达式,再对后缀表达式进行求值

  • 中缀表达式转换成后缀表达式

    • 运算数 直接输出
    • 左括号 压栈
    • 右括号 将栈顶的运算符弹出输出直到遇到左括号(出栈,不输出)
    • 运算符
      • 优先级大于栈顶运算符时,则把它压栈
      • 优先级小于栈顶运算符时,将栈顶运算符弹出并输出,再比较新的栈顶运算符,直到该运算符大于栈顶运算符优先级为止,然后将该运算符压栈
    • 若各对象处理完毕,则把堆栈中存留的运算符一并弹出

      左括号 '(' 栈外优先级最高,栈内优先级最低

  • 对后缀表达式进行求值

    • 运算数 入栈
    • 运算符 Pop 适当个数运算数(二元运算符就是 2 个,一元就 1 个咯),计算结果入栈,注意出栈时操作数是反着来的

# 3.4.3 更多...

  • 函数调用
  • 递归 写起来更容易,但性能不佳,如非尾递归(尾递归编译器可自动优化为循环),尽量使用循环代替
  • 深度优先搜索
  • 回溯方法

# 4 队列(Queue)

  • 循环队列
  • 链式队列
  • 双端队列

# 4.1 基本概念 !

# 4.1.1 定义

只允许在标的一端进行插入,而在表的另一端进行删除

  • 队头 (Front) 允许删除的一端
  • 队尾 (Rear) 允许插入的一端

# 4.1.2 特点

先进先出(FIFO)

# 4.2 顺序存储

  • front 指向队首元素,也即即将出队元素的位置
  • rear 指向队尾元素的后一个位置,也即即将入队元素的位置(所以 rear 总空)

也可以 ,front 指向队首元素的前一个位置,也即刚出队元素的位置(此时 front 总空),指向队尾元素,也即刚入队元素的位置 rear 指向队尾元素的后一个位置,天勤以及浙大 MOOC 默认使用该方法,但本笔记参考王道以及网络上众多方案,使用前者,其实就是入队出队与指针移动的先后顺序问题,前者是先操作后移动,后者反之

  • 队空判据 front == rear
  • 队满判据 rear == MaxSize

很明显,此时的“队满”实际上是一种“假溢出”现象,明明队首前面那么多空间,可就是干巴巴看着用不了,为了充分利用数组空间,一般情况下会使用循环队列

# 4.2.1 循环队列

DS01.jpg{copyright:BaiduImage}

首尾相接,围一个圈圈,这样就可以更加充分地利用数组空间了,但是还有一个小问题,什么时候队空?什么时候队满?可以发现在空/真正的满的情况下,两个指针都是重合的,也就是 front == rear,究其原因,是因为不能用 nn 个队列的状态表示 n+1n+1 种状态,那么要如何解决呢?

  • 增加一个参数,用于记录 front == rear ,是因为增加元素导致的,还是因为删除元素导致的
  • 将数组空出来一个位置,使得队列减少一种状态

常采用后者





























 
 
 





 





 
 






 
 



#include <iostream>
#define MaxSize 50
using namespace std;
typedef int ElemType;
typedef struct {
  ElemType data[MaxSize];
  int front;
  int rear;
} QNode, *SqQueue;
SqQueue InitQueue();
bool isEmpty(SqQueue PtrQ);
bool EnQueue(SqQueue PtrQ, ElemType x);
bool DeQueue(SqQueue PtrQ, ElemType &x);
int main() {
  SqQueue PtrQ = InitQueue();
  ElemType x;
  EnQueue(PtrQ, 100);
  DeQueue(PtrQ, x);
  cout << x << endl;
  cout << boolalpha << isEmpty(PtrQ) << endl;
  return 0;
}
SqQueue InitQueue() {
  /** 初始化空队列 */
  SqQueue PtrQ = (SqQueue)malloc(sizeof(QNode));
  PtrQ->front = 0;
  PtrQ->rear = 0;
  return PtrQ;
}
bool isEmpty(SqQueue PtrQ) {
  /** 判断队列是否为空 */
  return PtrQ->front == PtrQ->rear;
}
bool EnQueue(SqQueue PtrQ, ElemType x) {
  /** 入队 */
  if ((PtrQ->rear+1)%MaxSize == PtrQ->front) return false;
  PtrQ->data[PtrQ->rear++] = x;   // 先入队,后移动指针
  PtrQ->rear %= MaxSize;          // 保证没“飞出去”
  return true;
}
bool DeQueue(SqQueue PtrQ, ElemType &x) {
  /** 出队 */
  if (isEmpty(PtrQ)) return false;
  x = PtrQ->data[PtrQ->front++];  // 先出队,后移动指针
  PtrQ->front %= MaxSize;         // 保证没“飞出去”
  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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

# 4.3 链式存储

DS02.jpg{copyright:BaiduImage}

和链栈一样,如若需要删除操作的 front 在链尾则难以继续对新的链尾进行操作,故 front 在链首

有没有头结点是要看题意要求的,一般来说,带头结点更容易操作,这里便使用“天生”带头结点进行示范

为什么带头结点更容易操作?

不带头结点的时候,初始情况 front 与 rear 都是 NULL,加第一个结点需要将两个指针都指向它,而之后再加结点就只需要操作 rear 了,也就是说入队操作需要判断是否是初始情况,相应的出队操作需要判断是否会回归初始情况,这将使得代码写起来更麻烦,所以一般都会使用带头结点的链队,这样无论是否是初始情况,操作都是统一的,没有头结点的话一般会建立临时头结点

另外要注意的是,链队需要定义两个结构体,这还是遇到的第一个,原因不难想到,因为他需要两个指针,链表本身的一个指针已经不能满足它了





































 
 
 





 
























#include <iostream>
using namespace std;
typedef int ElemType;
struct Node {
  ElemType data;
  struct Node *next;
};
typedef struct QNode {
  struct Node *front;
  struct Node *rear;
} LinkNode, *LinkQueue;
LinkQueue InitQueue();
bool isEmpty(LinkQueue PtrQ);
bool EnQueue(LinkQueue PtrQ, ElemType x);
bool DeQueue(LinkQueue PtrQ, ElemType &x);
int main() {
  LinkQueue PtrQ = InitQueue();
  ElemType x;
  EnQueue(PtrQ, 100);
  DeQueue(PtrQ, x);
  cout << x << endl;
  cout << boolalpha << isEmpty(PtrQ) << endl;
  return 0;
}
LinkQueue InitQueue() {
  /** 初始化空队列 */
  // 建立头结点
  struct Node *PtrHead = (struct Node *)malloc(sizeof(struct Node));
  PtrHead->next = NULL;
  // 建立队列
  LinkQueue PtrQ = (LinkQueue)malloc(sizeof(LinkNode));
  PtrQ->front = PtrHead;
  PtrQ->rear = PtrHead;
  return PtrQ;
}
bool isEmpty(LinkQueue PtrQ) {
  /** 判断队列是否为空 */
  return PtrQ->front == PtrQ->rear;
}
bool EnQueue(LinkQueue PtrQ, ElemType x) {
  /** 入队 */
  // 新建结点
  struct Node *PtrNode = (struct Node *)malloc(sizeof(struct Node));
  PtrNode->data = x;
  PtrNode->next = NULL;
  // 串起来
  PtrQ->rear->next = PtrNode;
  PtrQ->rear = PtrQ->rear->next;
  return true;
}
bool DeQueue(LinkQueue PtrQ, ElemType &x) {
  /** 出队 */
  if (isEmpty(PtrQ)) return false;
  struct Node *PtrNode = PtrQ->front->next;
  x = PtrNode->data;
  PtrQ->front = PtrQ->front->next;
  free(PtrNode);
  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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

# 4.3.1 双端队列

指允许两端都可以进行入队和出队操作的队列,可看做栈底连在一起的两个栈

  • 输入受限的双端队列 一端允许插入和删除,另一端只允许删除
  • 输出受限的双端队列 一端允许插入和删除,另一端只允许插入

# 4.4 应用

  • 层次遍历(广度优先搜索)
  • 计算机系统中
    • 解决主机与外部设备之间速度不匹配的问题
    • 解决由多用户引起的资源竞争问题

# 5 串(String)

# 5.1 串的定义

由零个或者多个字符组成的有限序列

与线性表的关系

  • 逻辑结构上极为相似,只是它所操作数据限定在字符集
  • 基本操作上有很大差别,线性表操作对象主要为单个元素,而串主要为子串

# 5.2 串的存储结构

# 5.2.1 定长顺序存储表示

用定长数组表示就好,可额外设一个变量表示长度

#define MaxSize 50
typedef struct {
   char ch[MaxSize];
   int length;
} SString;
1
2
3
4
5

WARNING

这里的 ch 只是个字符数组,并不是 C 语言中的字符串,所以也就没有 ‘\0’

当然,也可以使用 C 语言那种字符串,只不过那样长度会是隐含的,求起来会比较麻烦

# 5.2.2 堆分配存储表示

在堆区内动态分配,这样就不怕定长字符串的”截断“问题了

typedef struct {
   char *ch;
   int length;
} HString;
1
2
3
4

# 5.2.3 块链存储表示

每个 Node 存储一定位数的字符,尾结点需要补全。虽然联接等操作简单了,但因为一维模型化为二维了,操作不灵活,而且额外消耗大量存储空间

# 5.3 串的基本操作

基本操作集不少,但有五个原子操作,通过他们可完成其余复杂操作

  • 串赋值 StrAssign
  • 串比较 StrCompare
  • 求串长 StrLength
  • 串联接 Concat
  • 求子串 SubString

# 5.4 串的模式匹配

# 5.4.1 双指针循环迭代

ii jj 两指针分别指向模式串与主串,若不匹配,两指针均需回溯,最坏时间复杂度达到了 O(nm)O(nm)









 
 






int Index(SString S, SString T, int pos) {
   int i = pos, j = 1;
   while (i <= S.length && j <= T.length) {
      if (S.ch[i] == T.ch[j]) {
         i++;
         j++;
      }
      else {
         i = i - j + 2;    // 指针 i 回溯
         j = 1;            // 指针 j 回溯
      }
   }
   if (j > T.length) return i-T.length;
   else return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 5.4.2 KMP 算法 !

如何避免两个指针都进行回溯呢?

比如说如下两个串

string S = "abacaabacabacabaabb"
string T = "abacabac"
1
2

第一次匹配会出现这样的情况

abacaabacabacabaabb
abacax
1
2

然后如何?是要这样吗?

abacaabacabacabaabb
 x
  ax
   x
    ax
     ax
1
2
3
4
5
6

嗯,一步,两步……浪费了很多步

既然前五位已经完全匹配上了,那么之后的几步操作,在主串上的第二位、第三位、第四位、第五位不就是模式串自己局部与自己局部的匹配吗?

如下便是已经匹配上的主串与模式串部分,模式串的前五位尝试进行自匹配

abacaa
 x
  ax
   x
    ax
     abacaa
1
2
3
4
5
6

但是很明显,能够匹配上的条件其实是很苛刻的,这需要模式串前后有着相同的结构,上面只有最后一个是匹配上了的,其余都没有匹配上

很明显,如果这样的话,我们下次将模式串移到这个位置就可以了啊,部分模式串的自匹配结果说明,前四次匹配是完全没有必要的,但是有多个匹配的情况呢?要移到什么位置呢?下面我们看下前七位模式串是什么情况

abacaba
    abacaba
      abacaba
1
2
3

这里将不匹配的情况都过滤掉了,可以发现,第一种匹配上了 3 位,第二种匹配上了 1 位,虽然主串前 7 位已经确定了,但是第八位是还是未知的,如果后面是 caba 的话,那移到第一种就可以了呀,所以当然不能移到第二种啦,不然会错过第一种的,这在匹配长度上表现为最大的部分匹配长度,其实就是能够使得部分模式串自匹配的前提下,移动距离最短的情况

为什么要计算局部自匹配

因为指针 ii 之前的部分已经匹配上了,所以这部分主串与模式串的匹配相当于模式串的局部自匹配,如果模式串连局部自匹配都做不到的话,又何谈和主串匹配呢?所以无法局部自匹配的位置被直接跳过去了,也就是直接将模式串移动到了最可能与主串发生匹配的位置了

但是如何计算要移动到哪呢?这里要明确一点,虽然看起来是模式串的右移,但事实上是指针 jj 的回溯,比如说前面已经匹配上了 j1j-1 位,在第 jj 位发生了不匹配,而该 j1j-1 位模式串最大匹配长度为 tt那么我们 下一步 jj 就要指向 t+1t+1

abacaba
   ↑   ↑
    abacaba
       ↑
1
2
3
4

以前七位前面例子中的前七位为例,已经有 7 位匹配上,j=8j=8 (上图右上的那个指针),所以”模式串右移“就相当于指针 jj 指向模式串的第 4 位(上图下侧那个指针),也就是前七位最大匹配长度 3 再加 1,将该指针画在原图上就表现为了指针 jj 的回溯(上图左上那个指针)

为了方便之后的计算,可以事先计算好 jjt+1t+1 的一一对应关系,将其作为 next 数组

TT a b a c a b a c
jj 1 2 3 4 5 6 7 8
nextnext 0 1 1 2 1 2 3 4

注意

由于指针 jj 对应的是前 j1j-1 位已经匹配上,所以计算的时候不能带上 jj 所指那一位,比如 j=3j=3 时需要考虑的是前两位 abab ,由于它最长匹配长度 tt 为 0 ,所以 t+1t+1 为 1

另外,不移动时的匹配长度不算……所以 aa匹配长度应该为 0 (对应 j=2j=2

当第一位就没匹配上的时候,ii 向右移动,而 jj 不动,所以第一个值应该为 0

如何快速计算 next 数组

前面的描述人工计算比较方便,但计算机有着更加方便的运算方式

情况一:

我们看一下 j=7j=7 的情况,也就是前六位的匹配情况

      ↓
abacab
    abacab
      ↑
1
2
3
4

计算得到 next[j]=3 ,然后我们再看下一位,也就是 j=8j=8 的情况

       ↓
abacaba
    abacaba
       ↑
1
2
3
4

由于 j1j-1 所指处两字符相同(上图中重合的 aba 中最后一位新增的 a),所以 next[j]=next[j-1]+1=4

情况二:

但是如果不相同呢?此时指向下面字符串的指针就要回溯了

唔,感觉好熟悉,回溯……咦,这不就是模式匹配嘛?主串新的一位如果不匹配,则指向模式串的指针 jj 回溯,只不过因为我们这里因为求当模式串已经指在 jj 时,应当回溯几位,所以指针 jj 指在了“主串”新的一位位置,这里将“模式串”的指针称作 kk (本块中,上侧指针为 jj ,下侧指针为 kk

下面看 j=4j=4 的情况

   ↓
aba
  aba
   ↑
1
2
3
4

next[j]=2 ,下一步(j=5j=5)怎么办?

    ↓
abac
  abac
    ↑
1
2
3
4

嗯,指针 kk 需要回溯了,如何回溯?这不就是之前的问题嘛?在匹配上表现为向右滑动寻找最大匹配,而在计算上就是 k=next[k] ,由于我们是从左向右一步步计算过来的,且 k<j,所以 next[k] 一定是已知的

    ↓
abac
    abac
    ↑
1
2
3
4

回溯后 k=1k=1 ,但是回溯之后做什么呢?回溯之后我们还是要面对原问题,next[j] 要怎么求,虽然这样可能求不出来,但是至少我们改变了局面(再次考虑现在是情况一还是情况二呢?),改变了局面总能求出结果的,要注意,k=0k=0 时是要做情况一同样的操作的,所以可以归并在情况一里


有了上面的分析,我们就可以根据前 j1j-1next 数组计算出 next[j]

代码如下





 
 
 
 



 


void getnext(Str substr, int next[]) {
   int j = 1, k = 0;
   next[1] = 0;
   while (j < substr.length) {
      if (k==0 || substr.ch[j]==substr.ch[k]) {
         j++;
         k++;
         next[j] = k;
      }
   }
   else
      k = next[k];
}
1
2
3
4
5
6
7
8
9
10
11
12
13

有了 next 数组,我们在指针 jj 处发生不匹配时,只需要将指针 jj 移动到 next[j] 就好啦,也就是 j = next[j]

我们来看一下 KMPKMP 算法是如何工作的

abacaabacabacabaabb
abacax
    ax
     abacabac
1
2
3
4

可以看到,第一次匹配失败后,模式串根据自己与自己匹配的”经验“,直接向右匹配到前五位最大部分匹配的位置了,节省了四次没有必要的匹配

在指针的移动上表现为指针 ii 不需要回溯,模式串”向右滑动“(实际是 jj 的移动)一段距离,这使得其算法复杂度仅仅为 O(n+m)O(n+m)

为什么指针 i 不需要回溯

     ↓
abacaabacabacabaabb
abacax
     ↑
1
2
3
4

此时指针 ii 前面部分都已经匹配上了,也就是说模式串指针 jj 前面部分代表了主串指针 ii 前面那部分,而模式串的自匹配结果之前已经计算过了,我们可以根据自匹配结果移动指针 jj,移动后的结果是,此时模式串前 jj 位与主串匹配上,然后重新考虑下一位是否匹配,也就是回到了最初的问题,是移动指针 jj 以获得新的局面来尝试解决问题,这保证了新的前 kk 位依然匹配,所以不需要两个指针同时回溯来尝试解决

指针 i 不需要回溯所带来的优势

ii 不需要回溯意味着对于规模较大的外存中字符串的部分匹配操作可以分段进行

那么 KMP 算法的具体代码?




 
 
 


 







int KMP(Str str, Str substr, int next[]) {
   int i = 1, j = 1;
   while (i <= srt.length && j <= substr.length) {
      if (j==0 || str.ch[i] == substr.ch[j]) {
         i++;
         j++;
      }
      else
         j = next[j];
   }
   if (j > substr.length)
      return i - substr.length;
   else
      return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

另外,虽然 KMP 算法的时间复杂度降到了 O(m+n)O(m+n) ,但是在一般情况下,普通匹配方式也能近似达到 O(m+n)O(m+n) ,所以至今仍被采用,KMP 算法仅仅在主串与模式串有很多“部分匹配”时才会比普通算法快得多

# 6 树(Tree)

  • 二叉树
    • 概念 定义、存储结构
    • 操作
      • 三种遍历
      • 线索二叉树
    • 应用
      • 排序二叉树 —— 平衡二叉树
      • 哈夫曼树
  • 树和森林
    • 概念 定义、存储结构
    • 操作
      • 与二叉树的转化
      • 遍历
    • 应用
      • 并查集

# 6.1 基本概念

# 6.1.1 定义

树是 n(n0)n (n \geq 0) 个结点的有限集合, n=0n=0 时,称为空树

树可以用来表征层次关系

关于树是否可以为空

树的定义是一个有争议的问题,维基百科 明确说明树的结点数大于 0 ,然而严版教材却明确说明结点数为 0 的树为空树,由于本阶段主要面向考研,这里以后者为主,但是我更倾向于前者

在任意一棵非空树中应满足

  • 有且仅有一个特定的称为根的结点
  • n>1n > 1 时,其余结点可分为 m(m>0)m (m>0) 个互不相交的有限集合 T1,T2,,TmT_1, T_2, \cdots, T_m ,其中每个集合本身又是一棵树,并且称为根结点的子树

树是保证结点连通的边最少的连接方式

为什么要使用树

查找是指根据某个给定关键字 KK,从集合 RR 中找出关键字与 KK 相同的记录

  1. 静态查找 集合中记录是固定的 没有插入和删除操作,只有查找 实现:

    • 顺序查找 利用数组与指向该数组的结构体进行查找 时间复杂度为 O(n)O(n)

      可以建立哨兵,(index=0 处放 KK,倒序查找)

    • 二分查找(Binary Search)

      条件:有序、连续存放(数组)

      时间复杂度为 O(logN)O(logN)

      二分查找的判定树便是一个树结构,待查找元素所在层数便是该元素所需查找的次数,最坏情况为该树的深度log2n+1\lfloor log_2n \rfloor + 1

      平均成功查找次数 ASL=(44+43+22+1)/11=3ASL = (4*4 + 4*3 + 2*2 + 1)/11 = 3

      如果组织一个像判定树一样的结构,那么很容易达到二分查找的效率,而且很容易插入和删除结点,以实现动态查找

  2. 动态查找 集合中记录是动态变化的 除查找,还可能发生插入和删除

# 6.1.2 基本术语

  • 结点的度(Degree):结点的子树个数
  • 树的度:树的所有结点中最大的度数
  • 叶节点(Leaf):度为 0 的结点
  • 父结点(Parent):有子树的结点是其子树的根结点的父结点
  • 子结点(Child):若 A 结点是 B 结点的父结点,则称 B 结点是 A 结点的子结点;子结点也称孩子节点
  • 兄弟结点(Sibling):具有同一父结点的各结点彼此是兄弟结点
  • 路径和路径长度:从结点 n1n_1nkn_k路径为一个结点序列 n1,n2,...,nkn_1, n_2, ..., n_k , nin_ini+1n_{i+1} 的父结点。路径所包含边的个数为路径的长度
  • 祖先结点(Ancestor):沿树根到某一结点路径上的所有结点都是这个结点的祖先结点
  • 子孙结点(Descendant):某一结点的子树中所有结点是这个结点的子孙
  • 结点的层次(Level):规定根节点在 1 层,其它任一结点的层数是其父结点的层数加 1
  • 树的深度(Depth):树中所有结点中的最大层次是这棵树的深度
  • 有序树树中结点的子树从左到右是有次序的,不能交换
  • 无序树树中结点的子树没有顺序,可以任意交换

# 6.1.3 树的性质

  • 树中的结点数等于所有结点的度数加 1
  • 度为 mm 的树中第 ii 层上至多有 mi1m^{i-1} 个结点 (i1)(i \geq 1)
  • 高度为 hhmm 叉树至多有 (mh1)(m1)(m^h - 1)(m - 1) 个结点
  • 具有 nn 个结点的 mm 叉树的最小高度为 logm(n(m1)+1)\lceil \log_m(n(m-1)+1)\rceil

# 6.2 二叉树的概念

# 6.2.1 定义

二叉树是另一种树形结构,其特点是每个结点至多只有两棵子树(即二叉树中不存在度大于 2 的结点),并且二叉树的子树有左右之分,其次序不能任意颠倒

二叉树与度为 2 的有序树的区别

  • 二叉树可以为空,而度为 2 的树至少有三个结点

    关键在于二叉树可以为空,因为如果不按照考研定义的话,树是不可为空的

  • 度为 2 的有序树在两个孩子都存在的情况下才有序,在只有一个孩子的情况下是无所谓左右孩子的,而二叉树无论是否两个孩子都存在,都有左右孩子之分

# 6.2.2 特殊的二叉树

  • 斜二叉树(Skewed Binary Tree) 斜的
  • 满二叉树(Full Binary Tree)又称完美二叉树(Perfect Binary Tree) 每层都是满的
  • 完全二叉树(Complete Binary Tree) 只有最后一层右侧不满
    • 所以,若有度为 1 的结点,则只可能有一个,且该结点只有左孩子而无右孩子
    • 令根结点编号为 1,则若有左孩子,则左孩子为 2i2i ,若有右孩子,则右孩子为 2i+12i + 1,很明显,任何结点的父结点为 n/2\lfloor n / 2 \rfloor
    • 结点 ii 所在的层次 log2i+1\lfloor \log_2 i \rfloor + 1
    • 具有 nn 个结点的完全二叉树的高度为 log2(n+1)\lceil \log_2 (n+1) \rceil (或者用 log2n+1\lfloor \log_2 n \rfloor + 1 ,结果都一样)
  • 二叉排序树(二叉搜索树) 或者是空二叉树,或者是左子树都小于根结点,右子树都大于根结点,且左右子树又各是二叉排序树
  • 平衡二叉树 树上任一结点的左子树和右子树的深度之差不超过 1

# 6.2.3 二叉树的性质

  • 非空二叉树上的叶子结点数等于度为 2 的结点数加 1,即 n0=n2+1n_0 = n_2 + 1

    很明显

    • 结点总数 n=n0+n1+n2n = n_0 + n_1 + n_2
    • 又因为,除了根结点的其他所有结点都有一个入度,即结点数与总度数的关系为 n=d+1n = d + 1
    • 最后,由于度(出度)是各个结点贡献的,也就是 d=n1+2n2d = n_1 + 2n_2
    • 综上,n=n1+2n2+1=n0+n1+n2n = n_1 + 2n_2 + 1 = n_0 + n_1 + n_2 ,故 n0=n2+1n_0 = n_2 + 1
  • 非空二叉树上 kk 层上至多有 2k+12^{k+1} 个结点
  • 高度为 hh 的二叉树至多有 2h12^h - 1 个结点
  • 给定 nn 个结点,能构成 h(n)h(n) 种不同的二叉树,h(n)=C2nnn+1h(n) = \frac{C_{2n}^{n}}{n+1}

# 6.3 二叉树的存储结构

# 6.3.1 顺序存储结构

  • 完全二叉树 编号 对应于 ArrayArrayindexindex
    • 非根节点的父结点的序号是 i\lfloor i \rfloor
    • 结点 ii 的左孩子结点的序号是 2i2i,右孩子是 2i+12i+1
  • 一般二叉树 补充成完全二叉树,但是会浪费大量空间

# 6.3.2 链表存储

typedef struct _node {
   ElemType data;
   struct _node *left;
   struct _node *right;
} BTNode, *BinTree;
1
2
3
4
5

# 6.4 二叉树的遍历

# 6.4.1 先序、中序、后序遍历

  • 先序
    1. 访问根节点
    2. 先序遍历其左子树
    3. 先序遍历其右子树
  • 中序 类似先序,只不过是左根右
  • 后序 类似先序,只不过是左右根

其实真正遍历的时候,三种遍历方式是走的相同的路径,而且每个结点都遇到了三次,只不过访问的时机不一样,先序是在第一次遇到就访问,中序后序分别是第二次和第三次

DS03

根据定义,我们可以很容易地写出其递归实现,但是递归实现调用系统栈导致较大的开销,我们可以自己利用栈进行非递归的实现以提高效率

  • 递归实现
void PreOrderTraversal(BinTree BT) {
  /** 先序遍历的递归实现 */
  if (BT) {
    Visit(BT);
    PreOrderTraversal(BT->left);
    PreOrderTraversal(BT->right);
  }
}
1
2
3
4
5
6
7
8
void InOrderTraversal(BinTree BT) {
  /** 中序遍历的递归实现 */
  if (BT) {
    InOrderTraversal(BT->left);
    Visit(BT);
    InOrderTraversal(BT->right);
  }
}
1
2
3
4
5
6
7
8
void PostOrderTraversal(BinTree BT) {
  /** 后序遍历的递归实现 */
  if (BT) {
    PostOrderTraversal(BT->left);
    PostOrderTraversal(BT->right);
    Visit(BT);
  }
}
1
2
3
4
5
6
7
8

  • 非递归实现
void PreOrderTraversalNonRecursion(BinTree BT) {
  /** 先序遍历的非递归实现 */
  stack<BinTree> S;
  BinTree p = BT;
  while (p || !S.empty()) {   // 准备好了就出发!
    while (p) {               // 这里可以落脚,看看下一步往哪走!
      S.push(p);              // 嗯,在地图上标记一下这里(っ•̀ω•́)っ✎⁾⁾
      Visit(p);               // 逛一逛咯
      p = p->left;          // 逛完往左走走
    }                         // 噫,这里不能落脚啊!肿么办
    if (!S.empty()) {         // 拿起地图,看看有没有地方可以去
      p = S.top();            // 往回走,回到刚刚过来的地方
      S.pop();                // 地图上划掉刚刚那里~(っ•̀ω•́)っ✎⁾⁾
      p = p->right;          // 往右走试试看!
    }                         // 到啦!这是个什么样的地方呢?
  }                           // 既没有落脚点,也没退路了,不过这一路好开心的说!
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void InOrderTraversalNonRecursion(BinTree BT) {
  /** 中序遍历的非递归实现 */
  stack<BinTree> S;
  BinTree p = BT;
  while (p || !S.empty()) {   // 准备好了就出发!
    while (p) {               // 这里可以落脚,看看下一步往哪走!
      S.push(p);              // 嗯,在地图上标记一下这里(っ•̀ω•́)っ✎⁾⁾
      p = p->left;          // 今天没空,直接往左走,下次再逛
    }                         // 噫,这里不能落脚啊!肿么办
    if (!S.empty()) {         // 拿起地图,看看有没有地方可以去
      p = S.top();            // 往回走,回到刚刚过来的地方
      S.pop();                // 地图上划掉刚刚那里~(っ•̀ω•́)っ✎⁾⁾
      Visit(p);               // 我又来啦!这回好好逛一下!
      p = p->right;          // 逛完往右走试试看!
    }                         // 到啦!这是个什么样的地方呢?
  }                           // 既没有落脚点,也没退路了,不过这一路好开心的说!
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void PostOrderTraversalNonRecursion(BinTree BT) {
  /** 后序遍历的非递归实现
   * 基本上将大部分特殊情况都标出来了,三次遇到以及需要回退的空指针情况
   * 后序遍历之所以难是因为前序中序在第二次遇到就将结点抛出了,而后序就必须一直保留结点,
   * 直至第三次遇到,但是栈是容易保存两个状态(在栈中或者不在栈中)的,三个状态就比较难了,
   * 相应地,实现起来就比较麻烦
   * 在第二次遇到的时候仅仅是看看栈顶,而不取出(也可以拿出来再放回去),然后就去遍历右子树了,
   * 当卡在右侧空指针的时候,需要不断回退(前序和中序早就把没用的扔掉了),但是回退到哪呢?
   * 由于指针已经指在右侧了,所以左子树一定已经全部抛出过了,现在连续抛出的路径应该是一个右下到左上的过程,
   * 当回到左上角的时候,将指针指向右面的兄弟(也许是姐妹?)即可
   */
  stack<BinTree> S;
  BinTree p = BT;
  while (p || !S.empty()) {             // 准备好了就出发!
    if (!p) {                           // [右侧空指针]怎么这里不能落脚啊?
      while (p == S.top()->right) {    // 看看地图,之前走过哪里?
        p = S.top();                    // 那个方向,往回走~
        Visit(p);                       // [第三次遇到]唔,都第三次来了,逛一下吧~
        S.pop();                        // 地图上划掉刚刚那里~(っ•̀ω•́)っ✎⁾⁾
        if (S.empty()) return;          // 呀,没路啦,不过这一路收获好多,今天步数可以破 3w 啦~
      }                                 // 总算退回来了
      p = S.top()->right;              // 往右走走看
    }                                   // 到啦!这是个什么样的地方呢?
    while (p) {                         // 这里可以落脚,看看下一步往哪走!
      S.push(p);                        // 嗯,在地图上标记一下这里(っ•̀ω•́)っ✎⁾⁾
      // Visit(p);                      // [第一次遇到]今天没空,以后再逛
      p = p->left;                    // 直接往左走
    }                                   // [左侧空指针]噫,这里不能落脚啊!肿么办
    if (!S.empty()) {                   // 拿起地图,看看有没有地方可以去
      p = S.top();                      // 往回走,回到刚刚过来的地方
      // Visit(p);                      // [第二次遇到]我很忙哒!不逛!
      p = p->right;                    // 往右走试试看!
    }                                   // 到啦!这是个什么样的地方呢?
  }                                     // 既没有落脚点,也没退路了,不过这一路好开心的说!
}
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

# 6.4.2 层序遍历

逐层从左到右进行遍历,使二叉树线性化

  • 队列实现
    1. 根节点入队
    2. 循环:结点出队,访问该结点,其左右儿子入队
  • 堆栈实现 基本同上,只不过由于栈的特性,需要先右儿子入栈,后左儿子入栈
void LevelOrderTraversal(BinTree BT) {
  /** 层序遍历 */
  queue<BinTree> Q;   // 为了方便测试,这里直接使用 C++ STL 中的 queue
  BinTree p = BT;
  if (!p) return;
  Q.push(p);
  while (!Q.empty()) {
    // 简单地说,就是每次拿出来一个,放进去俩(如果有的话)
    p = Q.front();   // 该方法只返回不删除
    Q.pop();          // 该方法只删除不返回
    Visit(p);
    if (p->left) Q.push(p->left);
    if (p->right) Q.push(p->right);
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 6.4.3 遍历的应用

一般就是直接将“访问结点”,改成某个具体操作就好啦

  • 求叶子结点
  • 求二叉树高度 Height=max(HL,HR)+1Height = \max(H_L,H_R) + 1,可通过改造后序遍历实现
  • 二元运算表达式树及其遍历
    • 先序遍历变成前缀表达式
    • 中序遍历变成中缀表达式 但是会受到运算符优先级的影响,需要加括号
    • 后序遍历变成后缀表达式
  • 由两种遍历序列确定二叉树 前中可以,后中可以,但前后不可以,亦即必须包含中序遍历

    因为前序·根左右·,中序·左根右·,后序·左右根· 知道前序后序相当于知道·根(左右)·和·(左右)根·,·左右·从未被界定开来,很明显这样的二叉树并不唯一

# 6.4.4 线索二叉树

针对遍历算法,我们除了可以使用非递归实现以提高效率,还有没有其他方法呢?

每一个二叉树都有好多好多空指针(n+1n+1 个),我们是否可以将其充分利用起来呢?

每个叶子结点有两个空指针,每个度为 1 的结点有一个空指针,所以空指针的个数为 n1+2n2n_1 + 2n_2 ,又因为 n0=n2+1n_0 = n_2 + 1 ,所以总的空指针个数为 n0+n1+n2+1=n+1n_0 + n_1 + n_2 + 1 = n + 1

我们可以利用这些空指针将树改造成线索二叉树

  • 如果一个结点没有左子树,那么将其 left 指向其前驱结点
  • 如果一个结点没有右子树,那么将其 right 指向其后继结点

但是改造后怎么区分到底是前驱后继还是左右子树呢?这个没什么比较好的方法,一般需要添加两个标记,用于区分 left 和 right 是用来指示左右子树还是前驱后继,比如 ltag = 0 是指 left 指示左孩子,否则指示前驱,rtag 一样

typedef struct _node {
   ElemType data;
   struct _node *left;
   struct _node *right;
   int ltag;
   int rtag;
} ThreadNode, *ThreadTree;
1
2
3
4
5
6
7

这个改造的过程,又称为二叉树的线索化

对二叉树进行线索化的过程,实质上就是遍历一次二叉树,并在遍历的过程中,检查当前结点左、右指针域是否为空,若为空,将它们改为指向前驱结点或后继结点的线索

为什么这样进行线索化是有效的

首先要知道我们遍历二叉树为什么需要栈或者系统栈(递归),我们的遍历链路是沿着树的左右子树指针域前进的,当没有左右子树的时候自然要回溯,回溯问题毫无疑问会选栈,而线索二叉树消除了叶子结点处没有左右子树的问题,如果没有左右子树,它将会沿着线索走下一步,这样,就避免了回溯问题,提高了效率

另外,由于有着新的 tag 的增加,所以这也是一种空间换时间的方法,虽然避免了栈的使用,但是额外空间开销也是不小的

# 6.5 树和森林

# 6.5.1 树的存储结构

  • 双亲表示法 孩子指向双亲
  • 孩子表示法 将每个结点的孩子都用单链表链接起来形成一个线性结构
  • 孩子兄弟表示法 其实就是转换为二叉树咯

# 6.5.2 与二叉树的转换

  • 树转换为二叉树 二叉树左指第一个孩子,右指下一个兄弟
  • 森林转换为二叉树 首先将每棵树转换为二叉树,因为根结点没有兄弟,所以每棵转换后的二叉树就没有右子树,这样我们将第二棵树根结点放在第一棵树右子树处,第三棵树放在第二棵树右子树处……

# 6.5.3 树和森林的遍历

  • 树的遍历
    • 先根遍历 对应其相应二叉树的先序遍历
    • 后根遍历 对应其相应二叉树的中序遍历
  • 森林的遍历
    • 先序遍历 对应其相应二叉树的先序遍历
    • 中序遍历 对应其相应二叉树的中序遍历

# 6.5.4 树的应用

  • 并查集(Union Find Set)

    • 存储结构 双亲表示法,孩子指向双亲,可利用数组存储结构体

    • 常用操作

      • 查 Find 在并查集中查找并返回包含某元素的树的根
      • 并 Union 求两个不相交子集合的并集
    • 示例代码

      #include <iostream>
      #define MaxSize 50
      using namespace std;
      typedef int ElemType;
      typedef struct {
        ElemType data;
        int parent;
      } Set;
      void Initial(Set S[]);
      int Find(Set S[], int x);
      void Union(Set S[], ElemType x1, ElemType x2);
      int main() {
        Set S[MaxSize];
        Initial(S);
        Union(S, 1, 2);
        cout << Find(S, 1) << endl;
        return 0;
      }
      void Initial(Set S[]) {
        /** 初始化 MaxSize 个互不重合的子集 */
        for (int i = 0; i < MaxSize; i++) {
          S[i].data = i;
          S[i].parent = -1;
        }
      }
      int Find(Set S[], ElemType x) {
        /** 查找并返回包含元素 x 的树的根 */
        int idx = 0;
        for (; idx < MaxSize && S[idx].data != x; idx++);
        if (idx == MaxSize) return -1;
        for (; S[idx].parent != -1; idx = S[idx].parent);
        return idx;
      }
      void Union(Set S[], ElemType x1, ElemType x2) {
        /** 求两个不相交子集合的并集 */
        int root1 = Find(S, x1);
        int root2 = Find(S, x2);
        if (root1 != root2)
          S[root1].parent = root2;
      }
      
      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
    • 其他优化 由于简单的的 Union 很可能会导致树不断长高使得 Find 效率不断降低,所以就需要一种方法减缓树的增长

      • 按秩归并 在 Union 的时候判断两棵树哪个更高,将低的“嫁接”到高的那棵上面就好
      • 路径压缩 每一次 Find 的时候利用尾递归将该路径上的各结点贴到根结点上

# 6.6 树与二叉树的应用

# 6.6.1 二叉搜索树(Binary Search Tree)

BST ,也译作二叉查找树,有时也称二叉排序树(Binary Sort Tree),其可以为空,如果不空则满足:

  • 非空左子树的所有键值小于其根节点的键值
  • 非空右子树的所有键值大于其根节点的键值
  • 左、右子树都是二叉搜索树

其实就是二分搜索的判定树,但是它更利于动态查找(可以方便地插入和删除结点)

根据定义可以知道,BST 的中序遍历得到的是一个递增序列

相关操作:

BinTree Insert(BinTree BST, ElemType x) {
  /** 插入元素 x */
  if (!BST) {
    BST = (BinTree)malloc(sizeof(TNode));
    BST->data = x;
    BST->left = NULL;
    BST->right = NULL;
  }
  else {
    if (x < BST->data) BST->left = Insert(BST->left, x);
    else if (x > BST->data) BST->right = Insert(BST->right, x);
  }
  return BST;
}
BinTree FindMin(BinTree BST) {
  /** 获取最小结点(非递归) */
  if (BST)
    while (BST->left) BST = BST->left;
  return BST;
}
BinTree FindMax(BinTree BST) {
  /** 获取最大结点(非递归) */
  if (BST)
    while (BST->right) BST = BST->right;
  return BST;
}
BinTree Search(BinTree BST, ElemType x) {
  /** 搜索值为 x 的结点(非递归) */
  while (BST) {
    if (BST->data < x) BST = BST->left;
    else if (BST->data > x) BST = BST->right;
    else return BST;
  }
  return NULL;
}
BinTree Delete(BinTree BST, ElemType x) {
  /** 删除值为 x 的结点
   * 如果是叶子结点,直接删除
   * 如果只有一个孩子结点,只需要将其孩子放到其父结点上
   * 如果两个孩子都有,可以转化为将·左子树的最大值或者右子树的最小值·
   * 放在删除结点的位置上
  **/
  BinTree Tmp;
  if (!BST) throw "Not Found!";
  else if (x < BST->data) BST->left = Delete(BST->left, x);
  else if (x > BST->data) BST->right = Delete(BST->right, x);
  else {
    if (BST->left && BST->right) {
      Tmp = FindMin(BST->right);
      BST->data = Tmp->data;
      BST->right = Delete(BST->right, BST->data);
    }
    else {
      Tmp = BST;
      if (!BST->left) BST = BST->right;
      else if (!BST->right) BST = BST->left;
      free(Tmp);
    }
  }
  return BST;
}
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

# 6.6.2 平衡二叉树(Banlanced Binary Tree)

主要内容摘自AVL - 百度百科

为了避免树的增长过快,降低二叉搜索树的性能,我们规定在插入和删除二叉树结点时,要保证任意结点的左右子树高度的绝对值不超过 1,将这样的二叉树称为平衡二叉树

  • 平衡因子 BF :结点左子树与右子树的高度差,即 BF(T)=hLhRBF(T) = h_L - h_R ,很明显,平衡二叉树的 BF(T)1BF(T) \leq 1

平衡二叉树和二叉搜索树的关系

按照定义,平衡二叉树二叉搜索树并无直接关系,但是平衡二叉树主要是为了防止二叉搜索树高度过高导致查找效率退化为 O(logN)O(\log N) 的问题,所以,我们一般所说的平衡二叉树其实是平衡二叉搜索树(Banlanced BST, BBST),平衡二叉搜索树有着很多种实现方法,最先被发明出来的就是 AVL ,所以常称平衡二叉树为 AVL

常见的平衡二叉搜索树实现方法

  • AVL
  • 红黑树
  • Treap
  • SBT
  • Splay

书上与网络上在关于平衡二叉树概念部分大多语焉不详,一说平衡二叉树就是二叉搜索树、一说平衡二叉树和二叉搜索树相互并无关联,我更赞同后者,因为按照字面意思来说两者也并无关联(个人认为英文命名一般都比较严谨),而维基百科中直接将“平衡二叉树”词条重定向到了“平衡二叉搜索树”一词上,大概就是因为平衡二叉树主要的应用场景还是二叉搜索树上,所以狭义上所指的平衡二叉树便是平衡二叉搜索树吧

AVL 的具体实现

AVL 树基本的操作为 AVL 旋转,AVL 旋转操作分为左旋转 (left rotation) 和右旋转 (right rotation),可以用下图表示 其中 T1, T2T3 都是待旋转树的子树

     y                               x
    / \         右旋转 (y)           / \
   x   T3   – – – – – – – >        T1  y
  / \       < - - - - - - -           / \
 T1  T2         左旋转 (x)            T2  T3
1
2
3
4
5

AVL 旋转操作并不会改变二叉查找树 (BST) 应满足的性质,也就是说,keys(T1)<key(x)<keys(T2)<key(y)<keys(T3)keys(T1) < key(x) < keys(T2) < key(y) < keys(T3) 依然成立

假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点为 z(即 z 是离插入点最近,且平衡因子绝对值超过 1 的祖先结点),则失去平衡后进行进行的规律可归纳为下列四种情况:

  • 单向右旋平衡处理 (Left Left):由于在 z 的左子树根结点 y 的左子树(根节点为 x)上插入结点,z 的平衡因子由 1 增至 2 ,致使以 z 为根的子树失去平衡,则需进行一次右旋转操作,具体操作如下所示
         z                                    y
        / \                                  / \
       y   T4          右旋转 (z)            x    z
      / \          - - - - - - - - ->      / \  / \
     x   T3                               T1 T2 T3 T4
    / \
  T1   T2
1
2
3
4
5
6
7
  • 单向左旋平衡处理 (Right Right):由于在 z 的右子树根结点 y 的右子树(根节点为 x )上插入结点,z 的平衡因子由 -1 变为 -2 ,致使以 z 为根的子树失去平衡,则需进行一次左旋转操作,具体操作如下所示
  z                                y
 /  \                            /   \
T1   y         左旋转 (z)        z      x
    /  \   - - - - - - - ->    / \    / \
   T2   x                     T1  T2 T3  T4
       / \
     T3  T4
1
2
3
4
5
6
7
  • 双向旋转(先左后右)平衡处理 (Left Right):由于在 z 的左子树根结点 y 的右子树(根节点为 x)上插入结点,z 的平衡因子由 1 增至 2 ,致使以 z 为根的子树失去平衡,则需进行两次旋转(先左旋后右旋)操作,具体操作如下所示
     z                               z                          x
    / \                            /   \                       /  \
   y   T4      左旋转 (y)          x    T4      右旋转 (z)      y     z
  / \      - - - - - - - - ->    /  \      - - - - - - - ->  / \   / \
T1   x                          y    T3                    T1  T2 T3  T4
    / \                        / \
  T2   T3                    T1   T2
1
2
3
4
5
6
7
  • 双向旋转(先右后左)平衡处理 (Right Left):由于在 z 的右子树根结点 y 的左子树(根节点为 x)上插入结点,z 的平衡因子由 -1 变为 -2 ,致使以 z 为根的子树失去平衡,则需进行两次旋转(先右旋后左旋)操作,具体操作如下所示
   z                            z                           x
  / \                          / \                         /  \
T1   y       右旋转 (y)       T1   x        左旋转 (z)      z     y
    / \  - - - - - - - - ->     /  \   - - - - - - - ->  / \   / \
   x   T4                      T2   y                  T1  T2 T3 T4
  / \                              / \
T2   T3                           T3  T4
1
2
3
4
5
6
7

总结:

  • 破坏者在被破坏者右子树的右子树,需要 RR 旋转
  • 破坏者在被破坏者左子树的左子树,需要 LL 旋转
  • 破坏者在被破坏者左子树的右子树,需要 LR 旋转
  • 破坏者在被破坏者右子树的左子树,需要 RL 旋转

# 6.6.3 堆(Heap)

堆的逻辑结构是一棵有序的完全二叉树

有序性表现为堆的根大于(大根堆)或小于(小根堆)其左子树与右子树的值

另外,由于其本质上是一棵完全二叉树,所以可以使用数组进行存储,这样的话,利用完全二叉树使用数组保存时的性质,很容易得到大根堆有着如下的性质: L(i)L(2i)L(i) \leq L(2i)L(i)L(2i+1)L(i) \geq L(2i + 1)

为了描述方便,后续只会以大根堆为例,小根堆定义是完全相反的

二叉堆与二叉搜索树的区别

堆与二叉搜索树在有序性上很相似,二叉搜索树是 Left<Root<RightLeft< Root < Right ,而堆则是 R>Max(Left,Right)R > Max(Left, Right)

但是它们的应用方向是完全不同的,二叉搜索树主要是用来查找的,而主要是用来排序

显然,大根堆的根是整个堆的最大值,利用堆可以很容易地管理==优先级队列==问题

堆的每次操作都需要进行不断地调整,以维持堆自身的有序结构

  • 建堆

    • 一种最简单的方法是从空堆不断插入,但是这样所需要的时间复杂度达到了 O(nlogn)O(n \log n)

    • 如果直接使用未排序的数组初始化数据域,再进行调整的话,时间复杂度可降到 O(n)O(n)

      那么,怎么调整?我们可以从堆底依次向前进行调整,堆的最后一个结点是第 n/2\lfloor n / 2\rfloor 个结点的孩子,我们考察第 n/2\lfloor n / 2\rfloor 个结点及其两个孩子,将三个结点中最大的放到根的位置上,这个过程是将根结点向下调整的过程,所以也叫向下调整法,调整之后,继续考察第 n/21\lfloor n / 2 - 1\rfloor 个结点,依次类推,不过值得注意的是,当调整上层的时候可能会破坏下层,需要不断向下调整到堆底

      DS04{copyright:Wangdao}

  • 插入元素 将新的元素放在堆的末端,然后针对它向上调整即可

  • 删除堆顶元素 将堆末元素放在堆顶,然后针对根结点向下调整即可

向上调整法与向下调整法的区别

当不满足堆性质的元素在堆顶时,我们需要将堆顶这个不满足的元素逐渐向下移动,所以会使用向下调整法,因为根结点需要同时大于其左右孩子,所以需要同时考虑三个元素,需要将左右孩子中最大的那个和堆顶交换,这表现为在向下调整时需根据左右孩子大小不断调整路径

当不满足堆性质的元素在堆底时,我们需要将堆底这个不满足的元素逐渐向上移动,所以会使用向上调整法,而一个孩子结点只需要判断是否大于根结点就行了,不需要再判断与另一个兄弟结点的大小关系
























































 






















 
 

































 








 













#include <iostream>
#define MaxSize 50
#define EMPTY -1
using namespace std;
typedef int ElemType;
typedef struct {
  ElemType *data;
  int size;
  int capacity;
} HeapStruct, *MaxHeap;
void AdjustDown(MaxHeap H, int k);
void AdjustUp(MaxHeap H, int k);
MaxHeap Create(int size);
MaxHeap CreateFromArray(ElemType a[], int len);
ElemType Delete(MaxHeap H);
void Insert(MaxHeap H, ElemType x);
void Print(MaxHeap H);
void HeapSort(ElemType a[], int len);
int main() {
  int size = 9;
  ElemType a[MaxSize] = {EMPTY, 30, 50, 57, 77, 62, 78, 94, 80, 84};
  // MaxHeap H = Create(MaxSize);
  MaxHeap H = CreateFromArray(a, size);
  Insert(H, 100);
  Insert(H, 1);
  cout << Delete(H) << endl;
  Print(H);
  HeapSort(a, size);
  for (int i = 1; i <= size; i++) {
    cout << a[i] << " ";
  }
  return 0;
}
MaxHeap Create(int size) {
  /** 创建空堆 */
  MaxHeap H = (MaxHeap)malloc(sizeof(HeapStruct));
  H->data = (ElemType *)malloc(sizeof(ElemType) * (size+1));
  H->size = 0;
  H->capacity = size;
  return H;
}
MaxHeap CreateFromArray(ElemType a[], int len) {
  /** 根据数组元素初始化一个堆
   * 之后需要从堆底开始不断向下调整将整个堆调整成真正的堆
  **/
  MaxHeap H = (MaxHeap)malloc(sizeof(HeapStruct));
  H->data = a;
  H->size = len;
  H->capacity = MaxSize;
  for (int i = len/2; i > 0; i--) {
    AdjustDown(H, i);
  }
  return H;
}
void Print(MaxHeap H) {
  /** 打印堆内元素数组 */
  for (int i = 1; i <= H->size; i++) {
    cout << H->data[i] << " ";
  }
  cout << endl;
}
void AdjustDown(MaxHeap H, int k) {
  /** 向下调整
   * k 为需要向下调整的元素下标,也即在调整过程中的父结点
   * i 为下一步需要调整的位置,也即调整过程中的孩子结点,
   * 由于孩子有两个,所以在调整的过程中需要不断校正方向,
   * 调整为两个孩子比较大的那个方向(因为父结点与较大的孩子
   * 交换)
  **/
  H->data[0] = H->data[k];
  for (int i = 2*k; i <= H->size; i *= 2) {
    if (i < H->size && H->data[i] < H->data[i+1])
      i++;
    if (H->data[0] >= H->data[i]) break;
    else {
      H->data[k] = H->data[i];
      k = i;
    }
  }
  H->data[k] = H->data[0];
}
void AdjustUp(MaxHeap H, int k) {
  /** 向上调整
   * k 为需要向下调整的元素下标,也即在调整过程中的孩子结点
   * i 为下一步需要调整的位置,也即调整过程中的父结点
   * 向上调整只有一条可能的路径,不需要校正方向,可对比
   * 向下调整法记忆
  **/
  H->data[0] = H->data[k];
  for (int i = k/2; i > 0; i /= 2) {
    if (H->data[0] <= H->data[i]) break;
    else {
      H->data[k] = H->data[i];
      k = i;
    }
  }
  H->data[k] = H->data[0];
}
void Insert(MaxHeap H, ElemType x) {
  /** 向堆中插入元素 x
   * 只需要将元素插入堆底,然后针对堆底位置向上调整即可
  **/
  if (H->size == H->capacity) throw "Heap is full!";
  H->data[++H->size] = x;
  AdjustUp(H, H->size);
}
ElemType Delete(MaxHeap H) {
  /** 删除堆顶元素
   * 只需要将堆底元素放到堆顶处,然后针对堆顶位置向下调整即可
  **/
  if (H->size == 0) throw "Heap is empty!";
  swap(H->data[1], H->data[H->size--]);
  AdjustDown(H, 1);
  return H->data[H->size+1];
}
void HeapSort(ElemType a[], int len) {
  /** 堆排序
   * 建堆、不断删除堆顶元素(移到堆底)
  **/
  MaxHeap H = CreateFromArray(a, len);
  for (int i = len; i > 1; i--) {
    a[i] = Delete(H);
  }
}
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

# 6.6.4 哈夫曼树和哈夫曼编码

  • 带权路径长度 WPL:从树根结点到任意结点的路径长度(经过的边数)与该结点上权值的乘积,称为该结点的带权路径长度

哈夫曼树是 WPL 最小的树,又称最优二叉树

那么如何构造哈夫曼树呢?

我们可以每次把权值最小的两棵二叉树合并,得到的二叉树权值为两棵二叉树权值之和

但是如何最快地找到权值最小的两棵树呢?这可以利用最小堆,堆的数据域数组存储树结点,以权值为 key 进行初始化排序

DS05{copyright:BaiduImage}

  • 哈夫曼树的特点
    • 每个初始结点最终都成为叶子结点,且权值越小的结点到根结点的路径长度越大
    • 构造过程中共新建了 n1n - 1 个结点,因此哈夫曼树中的结点总数为 2n12n -1
    • 每次构造都选择 2 棵树作为新结点的孩子,因此哈夫曼树中不存在度为 1 的结点
    • 对同一组权值,可能存在不同构的两棵树的,比如 {1, 2, 3, 3},但是 WPL 是一样的

哈夫曼树是哈夫曼算法得到的二叉树吗?

根据定义,哈夫曼树是 WPL 最小的树,哈夫曼算法只是一种哈夫曼树的构造方法而已,哈夫曼树并不一定是通过哈夫曼算法得到的二叉树

  • 哈夫曼编码

    有效的编码可以节省存储空间,固定长度使用起来简单,但是编码后数据比较多,可以利用可变长度编码给频率高的字符较短的路径,而频率低的字符较长的路径,可以起到更好的数据压缩作用

    但是可变长度编码可能会出现二义性,这可以通过使用前缀码(任何字符的编码都不是另一个字符编码的前缀)进行解决,至于如何获得前缀码,我们可以利用二叉树==从根到叶子的路径==作为编码(向左为 0 、向右为 1,当然反过来也可)

    为了使得主算法代码更加清晰,使用 C++ 风格对 STL 中的堆封装了一下












     
     
     
     
     
     





    HuffmanTree Huffman(int a[], int len) {
      /** 建立哈夫曼树 */
      Node *n[len];
      for (int i = 0; i < len; i++) {
        n[i] = new Node(a[i]);
      }
      auto cmp = [](Node *T1, Node *T2) -> bool {
        return T1->weight > T2->weight;
      };
      Heap<HuffmanTree> H(n, len, cmp);
      for (int i = 0; i < len-1; i++) {
        Node *left = H.pop();
        Node *right = H.pop();
        HuffmanTree T = new Node(left->weight + right->weight);
        T->left = left;
        T->right = right;
        H.insert(T);
        H.print(true);
      }
      return H.pop();
    }
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21

# 7 图(Graph)

  • 图的定义
  • 图结构的存储
    • 邻接矩阵法
    • 邻接表法
    • 邻接多重表
    • 十字链表
  • 图的遍历
    • 深度优先遍历
    • 广度优先遍历
  • 图的相关应用
    • 最小生成树
      • Prim 算法
      • Kruskal 算法
    • 最短路径
      • Dijkstar 算法
      • Floyd 算法
    • 拓扑排序
      • AOV 网
    • 关键路径
      • AOE 网

# 7.1 基本概念

# 7.1.1 定义

GG 由顶点集 VV 和边集 EE 组成,记为 G=(V,E)G = (V, E) ,其中 V(G)V(G) 表示图 GG 中顶点的有限非空集,E(G)E(G) 表示图 GG 中顶点之间的关系(边)集合

  • 用于表示多对多的关系

  • 包含

    • 顶点(Vertex)
    • 边(Edge)(v, w)指无向边,<v, w>指 v 指向 w 的边
  • 有向图

  • 无向图

  • 简单图

    • 既不存在重复边
    • 又不存在自环
  • 多重图

    • 既允许重复边
    • 又允许自环
  • 完全图 任意两个顶点都存在边(有向图要求双向)

  • 子图

  • 连通 有路径

    • 连通图 图中任意两顶点均连通
    • 连通分量 包含子图中所有顶点相连的所有边
  • 强连通 有向图中存在双向路径的两顶点

    • 强连通图 有向图的中任意两顶点均强连通
    • 强连通分量 有向图的极大强连通子图
  • 生成树 连通图,极小连通子图

  • 生成森林 非连通图,各个连通分量的生成树共同构成了生成森林

  • 顶点的度 某顶点的度为以该顶点为端点的边数

    • 无向图的度为边数的两倍
    • 有向图的度分为入度和出度,度为两者总和
  • 边的权和网 带权图,也称网

  • 稠密图、稀疏图

  • 路径长度 指路径上边的数目

  • 简单路径、简单回路 顶点不重复出现

  • 距离 两顶点若存在最短路径,则该路径长度为距离,否则距离为 \infty

  • 有向树 一个顶点的入度为 0,其余顶点的入度均为 1 的有向图

# 7.2 图的存储及基本操作

# 7.2.1 邻接矩阵法

有边就是 1 ,无边就是 0 ,如果是无权图则用权重代替,非常简单的表示方法

#define MaxVertexNum 100
typedef char VertexType;
typedef struct {
  VertexType Vex[MaxVertexNum];               // 顶点表
  EdgeType Edge[MaxVertexNum][MaxVertexNum];  // 邻接矩阵,边表
  int vexnum, arcnum;                         // 图中的顶点数、边数
} MGraph;
1
2
3
4
5
6
7
8
  • 使用一个顶点表和一个边表,简单应用时可仅使用一个二维数组作为边表即可
  • 无向图的邻接矩阵是对称矩阵,可参考 2.3.5 进行压缩存储
  • 稠密图比较合适
  • 需存储空间 O(V+2E)O(|V| + 2 |E|)

# 7.2.2 邻接表法

每个顶点的各个边使用一个链表进行记录

#define MaxVertexNum 100
typedef char VertexType;
typedef int InfoType;
// 边结点,每条边指示下一条边
typedef struct _arcnode {
  int adjvex;
  struct _arcnode *next;
  InfoType info;
} ArcNode;
// 顶点结点,每个顶点有着第一条指向的边
typedef struct VNode {
  VertexType data;
  ArcNode *first;
} VNode, AdjList[MaxVertexNum];
// 图,记录着邻接表
typedef struct {
  AdjList vertices;
  int vexnum, arcnum;
} ALGraph;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
  • 需存储空间 O(V+E)O(|V| + |E|)
  • 足够稀疏才合适
  • 很多操作是很困难的,比如计算有向图的“入度”、检查任意一对顶点间是否存在边

# 7.2.3 十字链表

与邻接表不同的是,每个结点有两条链,一条用于表示入度的边,一条表示出度的边

具体实现

  • 边结点 5 个域
    • 头域和尾域 分别指示边两端顶点在图中的索引
    • 链域 hlink 和 tlink 分别指向下一个出度和入度的边结点
    • 信息域 info 顾名思义
  • 顶点结点 3 个域
    • 数据域 data
    • 入度首结点指针和出度首结点指针 headvex 和 tailvex

DS06{copyright:Wangdao}

#define MaxVertexNum 100
typedef char VertexType;
typedef int InfoType;
typedef struct _arcnode {
  int tailvex, headvex;
  struct _arcnode *hlink, *tlink;
  InfoType info;
} ArcNode;
typedef struct _vnode {
  VertexType data;
  ArcNode *firstin, *firstout;
} VNode;
typedef struct {
  VNode xlist[MaxVertexNum];
  int vexnum, arcnum;
} GLGraph;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
  • 由它的表示方式可知,它使得入度和出度都容易计算了

# 7.2.4 邻接多重表

每条边记录着与之关联的两个顶点

具体实现

  • 边结点 6 个域
    • 标志域 mark ,用于标记该条边是否被搜索过
    • ivex 和 jvex 分别为该边依附的两个顶点在图中的位置
    • ilink 和 jlink 分别指向下一条依附于 ivex 的边和下一条依附于 jvex 的边
    • 信息域 info
  • 顶点结点 2 个域
    • firstedge 指示第一条依附于该顶点的边
    • 数据域 data

DS07{copyright:Wangdao}

#define MaxVertexNum 100
typedef char VertexType;
typedef int InfoType;
typedef struct _arcnode {
  bool mark;
  int ivex, jvex;
  struct _arcnode *ilink, *jlink;
  InfoType info;
} ArcNode;
typedef struct VNode {
  VertexType data;
  ArcNode *firstedge;
} VNode;
typedef struct {
  VNode adjmulist[MaxVertexNum];
  int vexnum, arcnum;
} AMLGraph;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 7.3 图的遍历

从图中的某一顶点出发,按照某种搜索方法沿着图中的边对图中所有顶点访问一次且仅访问一次

主要有两种 —— BFS 和 DFS —— BFS 应用较早,比如在研究迷宫问题上,而 DFS 应用稍微晚一些,那时候主要应用在 AI

BFS 和 DFS 都可以抽象为优先级搜索,只不过 BFS 认为离起点越近优先级越高,DFS 反之

# 7.3.1 广度优先搜索(BFS)

广度优先搜索(Breadth-First-Search)

首先从结点 vv 开始,依次访问其邻接顶点,然后依次访问其邻接顶点的未被访问过的邻接顶点……

这就需要我们使用一个队列记录一下已经访问过的顶点

是不是很像二叉树的层序遍历算法呀?在层序遍历是一层一层遍历的,而 BFS 是一圈一圈扩散开来的~

DS08{copyright:https://www.jianshu.com/p/03de0db4b857}

由于我们不能像二叉树那样直观的知道哪个被访问过了,所以我们需要增加一个数组(visited[])用于标志哪个顶点被访问过了

void BFS(Graph G, Vertex v) {
  /** 从顶点 v 开始对图 G 进行广度优先遍历 */
  queue<Vertex> Q;
  visit(v);             // 注意,放进队列之前就已经访问了,而不是拿出来才访问
  visited[v] = true;
  Q.push(v);
  while (!Q.empty()) {
    Vertex v = Q.front();
    Q.pop();
    for (Vertex w = G.firstNeighbor(v); w >= 0; w = G.nextNeighbor(v, w)) {
      if (!visited[w]) {
        visit(w);
        visited[w] = true;
        Q.push(w);
      }
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 7.3.2 深度优先搜索(DFS)

深度优先搜索(Depth-First-Search)

它会尽可能深得搜索一个图,首先从结点 vv 开始,访问 vv 的邻接顶点 ww,然后继续访问 ww 的邻接顶点……直到当前顶点所有邻接顶点全部已经访问过,就需要回退回退~直到找到没被访问过的顶点继续~

其实很明显啦,用递归很容易实现的,不过这就需要一个递归工作栈,它其实很像二叉树的先序遍历

DS09{copyright:https://www.jianshu.com/p/03de0db4b857}

void DFS(Graph G, Vertex v) {
  /** 从顶点 v 开始对图 G 进行深度优先遍历 */
  visit(v);
  visited[v] = true;
  for (Vertex w = G.firstNeighbor(v); w >= 0; w = G.nextNeighbor(v, w)) {
    if (!visited[w]) {
      DFS(G, w);
    }
  }
}
1
2
3
4
5
6
7
8
9
10

# 7.3.3 性能分析

图的遍历实质就是对每个顶点查找其邻接点的过程

  • 空间复杂度 需要辅助队列(或者栈),最坏情况 O(V)O(|V|)
  • 时间复杂度
    • 邻接表 每个顶点均需搜索一次,而在搜索任一顶点的邻接点时,每条边至少访问一次,故总时间复杂度为 O(V+E)O(|V|+|E|)
    • 邻接矩阵 查找每个顶点的邻接点所需的时间为 O(V)O(|V|) ,故总时间复杂度为 O(V2)O(|V|^2)

# 7.3.4 如何遍历非连通图

简单地说,对各个连通分量逐一进行遍历就好啦

for (int i = 0; i < G.vexnum; i++) {
   if (!visited[i]) {
      BFS(G, i);    // or DFS
   }
}
1
2
3
4
5

不过,值得注意的是,上面的描述对有向图来说并不够准确,因为对有向图的非强连通分量遍历一次并不一定能将所有顶点遍历一遍,不过上面的算法是对每个顶点都查看了的,可以做到每个顶点都遍历一遍

# 7.4 图的应用

# 7.4.1 最小生成树(MST)

最小生成树(Minimum-Spanning-Tree, MST)

  • 首先肯定是一棵树
    • 无回路
    • V|V| 个顶点一定有 V1|V|-1 条边
  • 然后,它是一棵生成树
    • 包含全部顶点
    • V1|V|-1 条边都在图里
  • 最后,“最小”表示边的权重和最小
  • 当然,最小生成树并不是唯一的,但是权重和总是唯一的,而且是最小的

具体方法

  • Prim 算法

    (๑╹◡╹)ノ"""让一棵小树长大

    基本实现和下面的 Dijkstra 算法相似,都是从未收录 Vertex 中找 dist 最小的,将对应的边与顶点收入生成树中

    DS10{copyright:Wangdao}

    首先向空树 T=(VT,ET)T = (V_T, E_T) 中添加图 G=(V,E)G = (V, E) 的任一顶点 u0u_0 ,使 VT=u0V_T = u_0ET=E_T = \varnothing ,之后不断从图 GG 中选择满足 {(u,v)uVT,vVVT}\{(u, v)| u \in V_T, v \in V - V_T\} ,且具有最小权值的边 (u,v)(u, v),并置 VT=VT{v}V_T = V_T \cup \{v\}ET=ET{(u,v)}E_T = E_T \cup \{(u, v)\}

    void Prim(G, T) {
       T = emptySet;           // 初始化空树
       U = {w};                // 添加任一顶点 w
       while ((V - U) != emptySet) {(u, v) 是使 u in U 且 v in (V - U) , 且权值之最小的边;
          T = T 并 ((u, v));   // 边归入树
          U = U 并 {v};        // 顶点归入树
       }
    }
    
    1
    2
    3
    4
    5
    6
    7
    8
    9

    时间复杂度为 O(V2)O(|V|^2) ,不依赖于 E|E| ,适用于求解边稠密图的最小生成树

  • Kruskal 算法

    (๑╹◡╹)ノ"""将森林合并成树

    首先我们认为每一个 Vertex 都是一个树 Node,那么我们整个过程就是不断地将森林合并成树了

    DS11{copyright:Wangdao}

    首先令 VT=VV_T = VET=E_T = \varnothingTT 此时是一个仅含 V|V| 个顶点的森林,之后不断从 EETE - E_T 中选择权值最小的那条边,如果将该边加入 TT不构成回路,则将其加入 ETE_T ,否则舍弃,直到 ETE_T 中含有 n1n-1 条边

    void Kruskal(V, T) {
       T = V;                                 // 初始化树 T,仅含顶点
       numS = n;                              // 连通分量数
       while (numS > 1) {
          从 E 中取出权值最小的边 (v, u);        // 可利用最小堆
          if (v 和 u 属于 T 中不同的连通分量) {  // 可利用并查集
             T = T 并 {(v, u)};               // 将此边加入生成树中
             numS--;
          }
       }
    }
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11

    采用堆存放边的集合可将选择最小权值的边的时间降到 O(logE)O(\log |E|) ,这样总时间复杂度为 O(ElogE)O(|E| \log |E|) ,可以看出 Kruskal 算法很适合边稀疏而顶点较多的图

为什么 Prim 算法不需要判断是否会形成回路呢?

虽然 Prim 算法也是一个一个挑选边,但是在实际操作时是先考虑顶点,然后再考虑该顶点与已收录部分的生成树之间的边的,所以 Prim 算法相当于将一个一个顶点加入生成树中,这样是不会产生回路的,这也说明了为什么 Prim 算法的复杂度并不依赖于 E|E|

# 7.4.2 最短路径

  • 无权图的单源最短路径

    使用 BFS 对图上各顶点进行遍历,对每个未访问过的邻接点标记 dist[](记录从源点到各顶点的最短路径长度) 和 path[](表示从源点到该点的最短路径的前驱结点),由于 BFS 总是从近到远进行遍历,所以实现起来很简单

    void Unweighted(Vertex S) {
       Enqueue(S, Q);
       while (IsEmpty(Q)) {
          V = Dequeue(Q);
          for (V 的每个邻接点 W) {
             if (dist[W] == -1) {
                dist[W] = dist[V] + 1;
                path[W] = V;
                Enqueue(W, Q);
             }
          }
       }
    }
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
  • 有权图的单源最短路径

    使用 Dijkstra 算法

    首先令 SS 包含源点和已经确定了最短路径的顶点,令 dist[] 为各点到源点的距离,(初始值为该点到源点的边的权重,无边则为 \infty),path[] 仍为该点最短路径的前驱顶点

    之后从未收录顶点 VSV - S 中选取一条最短路径(dist[] 最小的那个),然后更新这个点周围的最短路径长度,如此反复,直到所有顶点都包含在 SS

    DS12{copyright:Wangdao}

    值得注意的是

    • 对于任何没收录的顶点,其最短路径必定只经过 S 内的顶点
    • 路径按照递增顺序生成
    • 不能解决有负边的情况
    void Dijkstra(Vertex s) {
       while (true) {
          V = 未收录顶点中 dist 最小者;
          if (这样的 V 不存在) {
             break;
          }
          S[V] = true;
          for (V 的每个邻接点 W) {
             if (S[W] == false) {
                if (dist[V] + E<V, W> < dist[W]) {
                   dist[W] = dist[V] + E<V, W>;
                   path[W] = V;
                }
             }
          }
       }
    }
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17

    与 Prim 算法类似,它的时间复杂度也为 O(V2)O(|V|^2) ,即便只需要找从源点到某个特定顶点,其复杂度与寻找该源点到所有顶点的复杂度基本相同,也是 O(V2)O(|V|^2)

    当我们想要求解任何两个顶点之间的最短路径的时候,如果用本算法就需要对每个顶点都用一遍,也就是 V3|V|^3 ,对于稀疏图效果还好,稠密图嘛,就不太好啦,下面介绍一种在该情况下时间复杂度更低的方案

  • 有权图的多源最短路径

    使用 Floyd 算法

    首先一个默认距离矩阵 DD ,然后每次多考虑一个顶点 kk ,将其作为中间顶点,如果某两个顶点以其作为中间顶点的路径总和比原路径长度更短,则更新,代码描述很简洁,直接看代码会更加清晰

    void Floyd() {
       for (int i = 0; i < N; i++) {
          for (int j = 0;j < N; j++) {
             D[i][j] = G[i][j];
             path[i][j] = -1;
          }
       }
       for (int k = 0; k < N; k++) {
          for (int i = 0; i < N; i++) {
             for (int j = 0;j < N; j++) {
                if (D[i][k] + D[k][j] < D[i][j]) {
                   D[i][j] = D[i][k] + D[k][j];
                   path[i][j] = k;
                }
             }
          }
       }
    }
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18

    很明显,这个时间复杂度还是 O(V3)O(|V|^3) 呀,可是这个三重循环很纯呀~没有多余的操作,即使在中等规模的输入时也是非常有效的

    另外, Floyd 算法允许图中有带负权值的边,但不允许有包含带负权值的边组成的回路

# 7.4.3 拓扑排序

若一个有向图中不存在环,则称为有向无环图,简称 DAGDAG

我们可以利用 DAGDAG 图表示一种前驱后继关系,将这种有向图称为顶点表示活动的网络,记为 AOVAOV

那么如何实现算法呢?

很简单,每次从图中选一个没有前驱顶点的顶点拿出来,并将以其为起点的有向边删除,如此反复,就得到一个拓扑排序序列啦

DS13{copyright:Wangdao}

void TopSort(){
    for (cnt = 0; cnt < |V|; cnt++){
        V = 未输出的入度为0的Vertex;
        if (这样的V不存在) {
            Error ("图中有回路");
            break;
        }
        输出V,或者记录V的输出序号;
        for (V 的每个邻接点W)
            Indegree[W]--;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

一般做法是,使用一个容器存放没有前驱结点的结点,这样,我们就不需要每次都查询整个图了,时间复杂度就降低了很多,时间复杂度为 O(V+E)O(|V| + |E|) (找顶点 + 删边)

# 7.4.4 关键路径

以顶点表示事件,以有向边表示活动,以边上的权值表示完成该网络的开销,则称这种有向图为用边表示活动的网络,简称为 AOEAOE

AOEAOE 网有什么性质呢?

  • 有向边的前驱后继关系
  • 只有在进入某一顶点的各有向边所代表的活动都已结束时,该顶点所代表的事件才能发生
  • AOEAOE 网中仅有一个入度为 0 的顶点,称为开始顶点(源点),相应地也只有一个结束顶点(汇点),他们分别代表了工程的开始和结束

因为所有活动都结束才算工程完成,所以只有所有路径上的活动都完成,整个工程才算结束,因此,所有源点到汇点的路径中,最长的那条被称为关键路径,关键路径上各个活动被称为关键活动

那么如何找出关键路径呢?

  1. 从前向后计算出各个事件的最早发生时间(源点最早发生时间为 0 )
  2. 从后向前计算出各个事件的最迟发生时间(汇点最迟发生时间等于其最早发生时间)
  3. 计算各个活动的最早发生时间与最迟发生时间
    • 活动的最早发生时间指该活动的起点所表示的事件的最早发生时间
    • 活动的最迟发生时间指该活动的终点所表示的事件的最早发生时间……减去其该活动所需时间(因为是发生时间嘛~)
  4. 计算各个活动的机动时间,即最迟开始时间和气最早开始时间的差额

如果一个活动的机动时间为 0 ,那么该活动必须如期完成,否则会拖延完成整个工程的进度,所以称机动时间为 0 的活动为关键活动,关键活动组成的路径即关键路径

很明显,关键路径决定了整个工程的完成时间,可通过加快关键活动来缩短整个工程的工期,当然,加快后可能使另一条成为关键路径

另外,网中的关键路径并不唯一,且对于有几条关键路径的网,只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期,需要同时提高这几条关键路径上的关键活动速度

# 8 查找(Search)

  • 基本概念
    • 静态查找
    • 动态查找
  • 线性结构
    • 顺序查找
    • 折半查找
    • 分块查找
  • 树形结构
    • 二叉排序树
    • 二叉平衡树
    • B 树、 B+ 树
  • 散列结构——散列表
    • 性能分析
    • 冲突处理
  • 效率指标——平均查找长度
    • 查找成功
    • 查找失败

# 8.1 顺序查找和折半查找

# 8.1.1 顺序 ��� 找

  • 一般线性表的顺序查找

    很简单的方法,不需要提前排序,直接从一端找到另一端就好了,虽然不难,但是有一个技巧,就是在另一端放一个“哨兵”(即待查找元素值),这样就不需要判断数组是否越界了

  • 有序表的顺序查找

    还是按一般的查找方式进行查找,但是一旦查找到一个当前位置比它大,下一个位置比它小的位置,那么就可以马上判定查找失败,降低失败的平均查找长度

# 8.1.2 折半查找

即二分查找,当然只适用于有序表

int Binary_Search(SeqList L, ElemType key) {
   int low = 0, high = L.TableSize - 1, mid;
   while (low <= high) {
      mid = (low + high) / 2;
      if (L.elem[mid] == key)
         return mid;
      else if (L.elem[mid] > key) {
         high = mid - 1;
      }
      else {
         low = mid + 1;
      }
   }
   return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 8.1.3 分块查找

结合了顺序查找和折半查找

将查找表分为若干子块,块内可以无序,块间需要有序,即后面的块每个元素都比前面的块里任意元素大

DS14.png{copyright:Wangdao}

比如上面的表,将前 6 个元素作为第一个块,所有元素均小于 24 ,第 7 到第 9 个元素为第二个块,所有元素均小于 54 ……这样查找的时候就可以根据大小去查找对应的区间块,大大缩小了搜索范围

# 8.2 二叉搜索树

# 8.3 B 树和 B+ 树

# 8.3.1 B 树及其基本操作

B 树,又称==多路平衡查找树==,B 树的度即其阶数,所以 B 树要么是空树,要么是满足以下特性的 mm 叉树

  • 除根结点外的所有非叶结点至少有 m/2\lceil m/2 \rceil 棵子树
  • 每个结点含有 kk 个关键字,这 nn 个关键字将该结点所表示的区间划分为 k+1k + 1 个子区间
  • 因为结点的子树个数也即划分的子区间个数范围为 [m/2,m][\lceil m/2 \rceil , m] ,所以关键字个数 kk 的范围为 [m/21,m1][\lceil m/2-1 \rceil , m-1]
  • 所有的叶节点都出现在同一层次上,并且不携带信息,即查找失败时结点

DS15.png{copyright:Wangdao}

比如上图就是一个 3 阶 B 树

B 树?B-树?

B 树即 B-tree ,B 是指 Balanced ,因为 B-tree 嘛,就有人将其译为 B-树了,不过还是不要使用这种写法了,容易被叫做 B 减树 😂

  • B 树的高度(磁盘存取次数)

    n1n \geq 1 ,则对任意一棵包含 nn 个关键字、高度为 hh 、阶数为 mm 的 B 树 h[logm(n+1),logm/2((n+1)/2)+1]h \in [\log_m(n + 1), \log_{\lceil m/2 \rceil}((n+1)/2) + 1]

  • B 树的查找

    每一层的查找都类似于分块查找,逐层进行查找即可

  • B 树的插入

    为了保证插入关键字之后仍然是一棵 B 树,需要按下列规则进行插入

    • 首先就是定位,看看插入哪里,直接按查找的方法即可,注意,是要插入在最低层非叶结点
    • 之后就是插入了,插入后关键字个数仍需满足 [m/21,m1][\lceil m/2-1 \rceil , m-1] ,当然这时候只需考虑有没有超过上限,如果超过了,则需对插入结点进行分裂
    • 至于如何分裂,可以将需要分裂的结点从中间拆开,中间关键字(m/2\lceil m/2 \rceil)放到父结点去,左右各分裂为一个结点,当然,现在父结点也变多了,这个时候就需要……继续查看是否要分裂咯~如果最后连根结点都分裂了,那么 B 树高度增加 1

    DS16.png{copyright:Wangdao}

  • B 树的删除

    • 若所删除的关键字不在终端结点

      • 看一下比该关键字大的子树和比该关键字小的子树哪个减少一个关键字之后还满足条件,就直接拿一个关键字上来,然后递归地删除那个拿上来的关键字
      • 如果都不满足,删掉该关键字,直接将两个子树合并 DS17.png{copyright:Wangdao}
    • 若所删除的关键字在终端结点

      • 如果直接删去仍满足,则直接删除
      • 如果兄弟有富余,则将其“调整”过来即可 DS18.png{copyright:Wangdao}
      • 如果兄弟没有富余,则需要删除之后将父结点中关键字放到兄弟那里 DS19.png{copyright:Wangdao}

# 8.3.2 B+ 树的基本概念

DS20.png{copyright:Wangdao}

很多地方和 B 树类似啦,只不过 B+ 树关键字只是辅助查找的,并不是真正要查找的对象,真正查找的都放在叶子结点啦,所以查找路径是等长哒~

另外, B+ 树设了两个头指针,分别指向根结点和关键字最小的叶结点,这使得 B+ 树不仅可以进行从最小关键字开始的顺序茶好,还可以进行从根结点开始的多路查找

# 8.4 散列表

前面所述的关键字与位置没有确定关系,所以查找需要基于比较,查找的效率也就取决于比较的次数

如果我们能用一个散列函数(记为 Hash(key)=AddrHash(key) = Addr)将一个关键字映射到它所在的地址,那么查找的时候可以说是”一步到位“了,查找的时间复杂度几乎是常量(O(1)O(1)

但是散列表的查找性能往往依赖于散列函数,设计一个优良的散列函数是非常有必要的

# 8.4.1 基本算法

  • 计算位置
  • 解决冲突

  • 存:
    1. 计算 h(key)h(key)
      • 如果 h(key)h(key) 空,则插入
      • 如果 h(key)h(key) 非空,则按冲突解决方案计算位置
    2. 返回 step2step2
  • 取:
    1. 计算 h(key)h(key)
      • 如果 h(key)h(key) 空,则返回不存在
      • 如果 h(key)h(key) 存储的是 keykey,则返回该位置
    2. 否则,按冲突解决方案计算新的位置
    3. 返回 step2step2

# 8.4.2 散列函数的构造方法

“好”的散列函数所需具备的因素

  • 计算简单,以便提高转换速度
  • 关键词对应的地址空间分布均匀,以尽量减少冲突

散列函数没有绝对的好与不好,只有合适不合适

  • 直接定址法

    取关键词的某个线性函数值为散列地址

    h(key)=a×key+bh(key) = a \times key + b
  • 除留余数法

    h(key)=key%ph(key) = key \% p
  • 数字分析法

    分析数字关键字在各位上的变化情况,取比较随机的位作为散列地址,拨入手机号可以取后四位作为地址,而身份证号可以取第 6, 10, 14, 16, 17, 18 位作为地址

  • 平方取中法

    对原来的数字进行平方,取中间的几位作为地址,因为中间的几位受更多的数字影响,比如 567935422=322550641290576456793542^2=3225506412905764 ,取 3225506412905764 中的中间三位641

  • 折叠法

    把关键词分割成位数相同的几个部分,然后叠加,还是举上面那个例子 5679354256793542 ,拆分为 542542793793056056 ,相加得 13911391,取后三位,即 h(56793542)=391h(56793542)=391

字符关键词的散列函数构造

前面所述均为数字关键词的散列函数构造,这里简单叙述下字符关键词的散列函数构造方法

  • ASCIIASCII 码加和法

    一种简单的算法,冲突较为严重

    h(key)=(key[i])modTableSizeh(key) = (\sum key[i])\ mod\ TableSize

  • 前 3 个字符移位法

    h(key)=(key[0]×272+key[1]×27+key[2])modTableSizeh(key) = (key[0]\times27^2+key[1]\times27+key[2])\ mod\ TableSize

  • 移位法

    涉及关键词所有 n 个字符,并且分布得很好

    h(key)=(i=0n1key[ni1]×32i)modTableSizeh(key)=(\sum_{i=0}^{n-1}key[n-i-1]\times32^i)\ mod\ TableSize

    就相当于将字符串看做 32 进制“数”

    • 可利用秦九韶算法减少乘法次数以加速运算
    • 另外可使用移位运算加速乘 32 的运算(这也是取 32 为底的原因)
    Index Hash(const char *Key, int TableSize){
       unsigned int h = 0; /* 散列函数值,初始化为0 */
       while (*Key != '\0') /* 位移映射 */
          h = (h << 5) + *Key++;
       return h % TableSize;
    }
    
    1
    2
    3
    4
    5
    6

# 8.4.3 处理冲突的方法

  • 开放定址法(Open Addressing)

    若发生了第 ii 次冲突,试探的下一个地址将增加did_i,基本公式是:hi(key)=(h(key)+di)modTableSize(1iTableSize)h_i(key) = (h(key)+d_i)\ mod\ TableSize\ (1\leq i \leq TableSize)

    did_i决定了不同的解决方案

    线性探测 平方探测 双散列 伪随机序列
    di=id_i=i di=±i2d_i=\pm i^2 di=ih2(key)d_i=i \ast h_2(key) di=randomd_i = random
    • 线性探测法(Linear Probing)

      以增量序列 1,2,,(TableSize1)1, 2, \cdots,(TableSize-1) 循环试探下一个存储地址

      这样很容易出现聚集现象

    • 平方探测法(Quadratic Probing)

      以增量序列12,12,22,22,,q2,q2(qTableSize/2)1^2,-1^2,2^2,-2^2,\cdots,q^2,-q^2\ (q\leq TableSize/2)循环试探下一个存储地址

      可能会出现无法探测全部散列表的现象,不过,当散列表长度 TableSize 是某个4k+3 形式的素数时,平方探测法就可以探查到整个散列表空间

    • 双散列探测法(Double Hashing)

      • did_iih2(key)i*h_2(key)h2(key)h_2(key)是另一个散列函数,探测序列长:h2(key),2h2(key),3h2(key),h_2(key),2h_2(key),3h_2(key),\cdots
      • 对任意的 key,h2(key)0h_2(key) \neq 0
      • 探测序列还应该保证所有的散列存储单元都应该能够被探测到,选择以下形式有良好的效果: h2(key)=p(keymodp)h_2(key) = p- (key\ \mod\ p) 其中p<TableSizep < TableSize, ppTableSizeTableSize 都是素数
    • 伪随机序列法(Pseudo-random Sequence)

      did_i 为伪随机序列

    再散列(Rehashing)

    当散列表元素太多(即装填因子α\alpha太大)时,查找效率会下降,解决的方法是加倍扩大散列表(全部重新计算放置到新表),这个过程叫做再散列

    实用最大装填因子一般取0.5α0.850.5\leq\alpha\leq0.85

    再散列的时机

    • 表满到一半就再散列
    • 插入失败再再散列
    • 达到某个装填因子时再散列

    懒惰删除

    开放定址法在删除时不能真的删除,如果真的删除会使之后的查找产生误判,之后的元素就找不到了,故可以使用一个标记以表示该元素已被删除,当然,这会导致散列表空间利用率急剧下降,所以开放定址法需要定期维护散列表

  • 分立链接法(Separate Chaining)

    也称拉链法、链接法(Chaining),把一个位置上冲突的所有关键词存储在同一个单链表里即可

    适用于经常插入删除的情况

# 8.4.4 散列表的性能分析

  • 平均查找长度(ASL)

    • 成功平均查找长度(ASLs):对表内数据枚举并取平均
    • 不成功平均查找长度(ASLu):认为要查找元素哈希值均匀分布在整个 Table 上,那么计算每个哈希值的查找长度(也就是遇到空的时候)计算取平均即可
  • 影响产生冲突多少的因素

    • 散列函数是否均匀
    • 处理冲突的方法
    • 散列表的装填因子 α\alpha
  • 散列表的优缺点

    • 选择合适的 h(key)h(key),散列法的查找效率期望是常数 O(1)O(1),它几乎与关键字的空间的大小 nn 无关!也适合于关键字直接比较计算量大的问题
    • 它是以较小的 α\alpha 为前提,因此,散列方法是一个以空间换时间
    • 散列方法的存储对关键字是随机的,不便于顺序查找关键字,也不适合于范围查找,或最大值最小值查找
  • 开放地址法和分立链接法的比较

    • 开放地址法
      • 散列表是一个数组,存储效率高,随机查找
      • 散列表有“聚集”现象
    • 分离链接法
      • 散列表是顺序存储和链式存储的结合,链表部分的存储效率和查找效率都比较低
      • 关键字删除不需要“懒惰删除”法,从而没有存储“垃圾”
      • 太小的 α\alpha 可能导致空间浪费,大的 α\alpha 又将付出更多的时间代价;不均匀的链表长度导致时间效率的严重下降

# 8.5 串的模式匹配

# 9 排序(Sort)

  • 基本概念
    • 稳定性 若待排序表中有两个元素对应的关键字相等,排序前后相对位置不变,则称该排序算法稳定
    • 衡量标准 时、空复杂度
  • 内部排序 大多基于比较移动(基数排序不基于比较)
    • 插入排序
      • 直接插入排序
      • 折半插入排序
      • 希尔排序
    • 交换排序
      • 冒泡排序
      • 快速排序
    • 选择排序
      • 简单选择排序
      • 堆排序
    • 归并排序
    • 基数排序
  • 外部排序——多路归并排序

# 9.1 插入排序

# 9.1.1 直接插入排序

template<typename T>
void Insertion_Sort(T a[], int N){
  int i;
  for (int P = 1; P < N; P++){
    T tmp = a[P];
    for (i = P; i > 0 && a[i-1] > tmp; i--){
      a[i] = a[i-1];
    }
    a[i] = tmp;
  }
}
1
2
3
4
5
6
7
8
9
10
11

类似于排扑克牌,将该牌与左面的所有牌比较

  • 空间复杂度 O(1)O(1)
  • 时间复杂度 O(n2)O(n^2)
  • 稳定性 稳定
  • 适用性 适用于顺序和链式存储

# 9.1.2 折半插入排序

因为排序过程中有一部分是有序的,所以就可以直接使用二分查找找到位置,当然,这不会减少移动的次数,但是减少了比较的次数

template<typename T>
void Half_Insertion_Sort(T a[], int N) {
  int i, low, high, mid;
  for (int P = 1; P < N; P++) {
    T tmp = a[P];
    low = 0;
    high = P;
    while (low <= high) {
      mid = (low + high) / 2;
      if (tmp < a[mid]) high = mid - 1;
      else low = mid + 1;
    }
    for (i = P; i > low; i--) {
      a[i] = a[i-1];
    }
    a[i] = tmp;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  • 空间复杂度 O(1)O(1)
  • 时间复杂度 O(n2)O(n^2)
  • 稳定性 稳定
  • 适用性 只适用于顺序存储

# 9.1.3 希尔排序

从简单插入排序可以看出,插入排序算法对于基本有序的排序表和数据量不大的排序表非常有效,希尔据此提出希尔排序,又称缩小增量排序

就是先定义一个增量序列(递减),根据增量序列进行插入排序,这就使得最终使用增量为 1 排序的时候整体上大体有序(递减的增量序列不会破坏之前排好的序列)

增量序列要互质才能体现其效果

template<typename T>
void Shell_Sort(T a[], int N) {
  int i;
  for (int D = N/2; D > 0; D /= 2) {
    for (int P = D; P < N; P++) {
      T tmp = a[P];
      for (i = P; i >= D && a[i-D] > tmp; i-=D) {
        a[i] = a[i-D];
      }
      a[i] = tmp;
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
  • 空间复杂度 O(1)O(1)
  • 时间复杂度 约为 O(n1.3)O(n^{1.3}) ,最坏 O(n2)O(n^2)
  • 稳定性 不稳定(当相同关键字划分到不同子表时,可能会改变其次序)
  • 适用性 只适用于顺序存储

# 9.2 交换排序

# 9.2.1 冒泡排序

template<typename T>
void Bubble_Sort(T a[], int N) {
  for (int P = N-1; P >= 0; P--) {
    bool flag = false;
    for (int i = 0; i < P; i++) {
      if (a[i] > a[i+1]) {
        swap(a[i], a[i+1]);
        flag = true;
      }
    }
    if (!flag)
      break;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

从左向右进行遍历,每次遍历比较相邻的元素,如果为逆序,则交换,这样一轮下来,最大值就到了最右面,下次只需要排剩下的元素即可

如果中途某次遍历已经得到排序好的数组,那么可通过一个 flag 直接退出

  • 空间复杂度 O(1)O(1)
  • 时间复杂度 O(n2)O(n^2)
  • 稳定性 稳定
  • 适用性 适用于顺序和链式存储,且其真正价值在于链表的排序

# 9.2.2 快速排序

  • 基本思想 分而治之

    • 从待排序列表中选一个主元
    • 对小于主元的列表递归的进行快速排序
    • 对大于主元的列表递归的进行快速排序

    通过一次排序后, pivot 左侧全部小于 pivot ,右侧全部大于 pivot ,即放在了最终的位置上,之后递归的对子表重复,更多的元素被放在了最终的位置上

  • 选主元

    主元如果是中间的值,才是最好的情况,但一旦选到了最小的值那可以说是非常糟糕了,所以,选主元很关键,不过要真么做呢?试试玄学用 random?那也很耗时间,通常,我们选取首中尾的中位数

template<typename T>
T Median3(T a[], int left, int right) {
  int center = (left + right) / 2;
  if (a[left] > a[center])
    swap(a[left], a[center]);
  if (a[left] > a[right])
    swap(a[left], a[right]);
  if (a[center] > a[right])
    swap(a[center], a[right]);
  swap(a[center], a[right-1]);
  // 只需考虑A[Left+1]...A[Right-2]
  return a[right-1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
  • 子集划分

    1. 设两个指针 i、j,分别指在左右两侧
    2. 一侧指针该位置处的值是否“应该”在该位置(与主元比较,比主元小应该在左侧,否则在右侧),如果对则继续移动,否则另外一个指针开始校验
    3. 当两个指针都指向不“应该”的值的时候,将两个指针所指的值交换,然后重复 2、3
    4. 如果 i < j,退出
    5. 然后将主元交换到 i 的位置,此时主元已经放到了最终的正确的位置,所以快速排序才能说是快速的排序方法

    TIP

    • 如果有元素等于 pivot,那么最好是交换,这样保证了最终的指针指在了正确的位置
    • 对小规模数据可以采用插入排序,因为用递归的话出栈入栈很废资源,也很慢
template<typename T>
void Quicksort(T a[], int left, int right) {
  if (right - left >= CUTOFF) {
    T pivot = Median3(a, left, right);
    int i = left;
    int j = right - 1;
    for (; ; ) {
      while (a[++i] < pivot) {}
      while (a[--j] > pivot) {}
      if (i < j)
        swap(a[i], a[j]);
      else break;
    }
    swap(a[i], a[right - 1]);
    Quicksort(a, left, i-1);
    Quicksort(a, i+1, right);
  }
  else
    Insertion_Sort(a+left, right-left+1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
  • 主函数
template<typename T>
void Quick_Sort(T a[], int N) {
  Quicksort(a, 0, N-1);
}
1
2
3
4
  • 空间复杂度 O(log2n)O(\log_2 n) (因为需要用递归工作栈)
  • 时间复杂度 最坏 O(n2)O(n^2) ,如果每次都能刚好将其划分为两个等大小的子集的话,则能降低到 O(nlog2n)O(n \log_2 n),另外它也是平均性能最优的排序算法
  • 稳定性 不稳定

# 9.3 选择排序

# 9.3.1 简单选择排序

遍历未排序部分寻找最小元,之后将最小元换到有序部分的后一个位置

template<typename T>
void Select_Sort(T a[], int N) {
  for (int i = 0; i < N; i++) {
    int idx_min = i;
    T ele_min = a[idx_min];
    for (int j = i; j < N; j++) {
      if (a[j] < ele_min) {
        ele_min = a[j];
        idx_min = j;
      }
    }
    swap(a[i], a[idx_min]);
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
  • 空间复杂度 O(1)O(1)
  • 时间复杂度 无所谓最好最坏情况,时间复杂度始终为 O(n2)O(n^2)
  • 稳定性 不稳定

# 9.3.2 堆排序

我们可以建立一个最小堆寻找最小元,但是那样额外需要一个数组,我们可以把所有的操作放在一个数组里

比如说,建立一个最大堆,那么 root 一定最大,将它和最后元素交换,之后将除了最后一个元素再调整为最大堆,如此反复

该方法虽然时间复杂度比较低,但是实际效果一般

使用 C++ 内置算法可以这样描述:

template<typename T>
void Heap_Sort(T a[], int N) {
  make_heap(a, a+N);
  for (int i = 0; i < N; i++) {
    pop_heap(a, a+N-i);
  }
}
1
2
3
4
5
6
7

更多详情见

  • 空间复杂度 O(1)O(1)
  • 时间复杂度 无所谓最好最坏情况,时间复杂度始终为 O(nlog2n)O(n \log_2 n)
  • 稳定性 不稳定

# 9.4 归并排序

这里使用二路归并

如何对一个表进行排序?对左半部分排好序,对右半部分排好序,因为左右都是有序的,合并起来就非常方便了(两个有序子串合并)

那……怎么对左半部分排序?使用同样的方法啦,也就是递归咯……

# 9.4.1 有序子列的归并

利用三个指针即可

template<typename T>
void Merge(T a[], T b[], int low, int mid, int high) {
  int i, j, k;
  for (k=low; k<=high; k++)
    b[k] = a[k];
  for (i=low, j=mid+1, k=i; i<=mid&&j<=high; k++) {
    if (b[i] <= b[j])
      a[k] = b[i++];
    else
      a[k] = b[j++];
  }
  while (i <= mid) a[k++] = b[i++];
  while (j <= high) a[k++] = b[j++];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 9.4.2 递归算法

先利用该算法解决两部分,然后 Merge,另外可以全程使用一个临时数组以减少反复开辟空间的开销

template<typename T>
void MergeSort(T a[], T b[], int low, int high) {
	if (low < high) {
    int mid = (low + high) / 2;
    MergeSort(a, b, low, mid);
    MergeSort(a, b, mid+1, high);
    Merge(a, b, low, mid, high);
  }
}
1
2
3
4
5
6
7
8
9
template<typename T>
void Merge_Sort(T a[], int N) {
  T b[N];         // 辅助数组,合并专用
  MergeSort(a, b, 0, N-1);
}
1
2
3
4
5

# 9.4.3 非递归算法

不断增加步长并 Merge

# 9.4.4 性能分析

  • 空间复杂度 O(n)O(n)
  • 时间复杂度 O(nlog2n)O(n \log_2 n)
  • 稳定性 稳定

# 9.5 表排序 ~

# 9.5.1 算法概述

就是用来排序比较复杂的结构,比如结构体,将整个数据进行改动比较复杂,所以可以使用一个 table 存储其指针,然后根据这个指针索引真正的数据,进行排序,并对 table 的内容进行排序,不需要移动原来的数据

# 9.5.2 物理排序

  • 当我们需要把复杂的数据结构排列到准确的位置的时候,我们可以在使用表排序之后再对数据进行排序
  • 我们可以发现,表排序之后,表和对应下标形成若干个独立的环,那么我们可以利用这个性质,对每个环进行物理排序

# 9.6 基数排序

# 9.6.1 桶排序 ~

就是创建一个所有取值的数组,下标就是要比较的 key,扫描输入的所有元素,把元素存入以 key 为下标的位置,不过存的是链表哦,因为该位置可能还存别的元素,等把所有元素读入后,按数组逐个扫描,如果有存指针则把该链表都读出来

比如,对关键字数组 {9, 28, 98, 17, 0, 8} 排序,可以 int a[100] ,然后将 9 存入 a[9] ……最后顺序读出即为按关键字排序好的序列

不过如果所有可能的取值太多,就尴尬了

# 9.6.2 多关键字的排序

继续前面的问题,我们如何如果可能的取值太多,难道我们要做那么多的“桶”吗,那会有很多的空桶的哦

如果我们排数字的话(假设 0-999),很明显最重要的是百位,其次看十位,最后看个位,我们可以将 10 作为基数,百位看做主关键字,十位个位为次关键字

  • LSD 次位优先,为优先级最低的关键字建立一组桶,并按读入顺序依次放入桶内,然后建立次低优先级的一组桶,并从前一组桶中顺序读入数据,以此类推,直到主关键字
  • MSD 主位优先,与上述过程相反

DS21.png{copyright:Wangdao}

  • 空间复杂度 O(r)O(r)
  • 时间复杂度 O(d(n+r))O(d(n + r))
  • 稳定性 稳定

# 9.7 内部排序算法的比较及应用

# 9.7.1 内部排序算法的比较

排序算法 最好情况下时间复杂度 平均时间复杂度 最坏情况下时间复杂度 空间复杂度 是否稳定
直接插入排序 O(n)O(n) O(n2)O(n^2) O(n2)O(n^2) O(1)O(1)
冒泡排序 O(n)O(n) O(n2)O(n^2) O(n2)O(n^2) O(1)O(1)
简单选择排序 O(n2)O(n^2) O(n2)O(n^2) O(n2)O(n^2) O(1)O(1)
希尔排序 O(1)O(1)
快速排序 O(nlog2n)O(n \log_2 n) O(nlog2n)O(n \log_2 n) O(n2)O(n^2) O(nlog2n)O(n \log_2 n)
堆排序 O(nlog2n)O(n \log_2 n) O(nlog2n)O(n \log_2 n) O(nlog2n)O(n \log_2 n) O(1)O(1)
归并排序 O(nlog2n)O(n \log_2 n) O(nlog2n)O(n \log_2 n) O(nlog2n)O(n \log_2 n) O(n)O(n)
基数排序 O(d(n+r))O(d(n+r)) O(d(n+r))O(d(n+r)) O(d(n+r))O(d(n+r)) O(n+r)O(n+r)

# 9.7.2 内部排序算法的应用

  • 若 n 较小,则可采用直接插入排序简单选择排序,由于直接插入排序所需移动操作更多,所以记录本身信息量较大时,简单选择排序更优
  • 若文件的初始状态已按关键字基本有序,则选用直接插入冒泡排序为宜
  • 若 n 较大,则应采用时间复杂度为 O(nlog2n)O(n \log_2 n) 的排序方法:快速排序堆排序归并排序
    • 待排序关键字随机分布时,快速排序平均时间最短
    • 堆排序所用辅助空间少于快速排序,且不会出现最坏情况
    • 若要求排序稳定,则可选用归并排序(可对较小的子段使用直接插入排序,因为它也是稳定的,所以最终仍然稳定)
  • 在基于比较的排序方法中,每次比较两个关键字的大小之后,仅出现两种可能的转移,因此可利用一棵二叉树来描述比较判定过程,由此可以证明:当文件的 n 个关键字随机分布时,任何借助于“比较”的排序算法,至少需要 O(nlog2n)O(n \log_2 n) 的时间
  • 若 n 很大,记录的关键字位数较少且可以分解时,采用基数排序较好
  • 当记录本身信息量较大时,为避免耗费大量时间移动记录,可用链表作为存储结构

# 9.8 外部排序

当需要排序的数据量很大时,甚至超过了内存大小,这就需要依次读入之后归并,也就是有点类似于内部排序的归并排序

外部排序的总时间 = 内部排序所需的时间 + 外存信息读写的时间 + 内部归并所需的时间

由于磁盘存取的时间远大于内部排序和内部归并的时间,所以应尽量降低 I/O 次数,可通过增大归并路数 mm 或减小初始归并段数 rr 来解决

# 9.8.1 多路平衡归并与败者树

虽然增大 mm 会减少 I/O,但是相应地会增加内部归并时间,因为每次归并都需要从 mm 个值中找到最小值,如果 mm 太大,将会抵消掉减少 I/O 所带来的增益

为了使得增大 mm 时不会过多地增加内部归并时间,需要对内部归并稍微作一下优化

这里引入了败者树的概念,将待比较的关键字放在叶结点,每个结点的父结点存储子结点较小值的索引,最终便可找到最小值

DS22.png{copyright:Wangdao}

上图便是一个五路归并示意,mm 路归并的败者树深度只有 log2m\lceil \log_2 m \rceil,大大降低了归并时的比较次数

虽然败者树方式可以降低 mm 带来的影响,但是 mm 增加时仍然会增加输入缓冲区的个数,如果内存空间不足的话,需要内存外存频繁交换数据,这仍然会增加外存读写次数

# 9.8.2 置换-选择排序

除去增大归并路数 mm ,减小初始归并段数 rr 也是可以有效的降低归并次数的,但是如果使用内部归并排序算法的话,每个记录都是一个初始归并段(即便已经有序或者局部有序),有没有什么更好的方法 生成初始归并段 呢?下面介绍就这种置换-选择排序~

直接用例子来讲解更清楚些

Step 输出文件 FO 工作区 WA 输入文件 FI
1 - - 17,21,05,44,10,12,56,32,29
2 - 17,21,05 44,10,12,56,32,29
3 05 17,21,44 10,12,56,32,29
4 05,17 10,21,44 12,56,32,29
5 05,17,21 10,12,44 56,32,29
6 05,17,21,44 10,12,56 32,29
7 05,17,21,44,56 10,12,32 29
8 05,17,21,44,56,# 10,12,32 29
9 10 29,12,32 -
10 10,12 29,-,32 -
11 10,12,29 -,-,32 -
12 10,12,29,32 - -
13 10,12,29,32,# - -

这里工作区最大容量为 3,首先从 FI 中读取 3 个记录到 WA,从中选取最小的为 MINIMAX,输出到 FO

FI 自动补足 WA 中的空缺,不赘述

之后,从 WA 中不断选取 MINIMAX (可利用败者树),并输出到 FO,MINIMAX 应当是 WA 中满足大于 FO 中所有记录的最小值(e.g. Step4 选取的就是 21,因为它满足大于 05 和 17,且是满足该条件的最小值)

如果某一步发现找不到满足条件的 MINIMAX 了,则将输出文件作为一个初始归并段,并输出一个归并段结束标志到 FO (e.g. Step7 找不到啦,输出了个 #),之后继续下一个初始归并段的选取,直到 WA 为空(e.g. Step8 开始了新的归并段的选取)

这样,就得到了全部的初始归并段啦,大大降低了初始归并段数~

# 9.8.3 最佳归并树

使用刚刚的置换-选择排序将会生成长度不等的初始归并段,那么应当如何组织归并顺序才能使 I/O 次数最少呢?

以长度分别为 9,30,12,18,3,17,2,6,24 的初始归并段为例,那么应该如何组织顺序呢?

DS23.png{copyright:Wangdao}

很容易想到哈夫曼树啦,将段长作为权值,则 WPL 最小的应该就是 I/O 次数最少的最佳归并树,当然,现在的哈夫曼树应当是 m 叉树了

DS24.png{copyright:Wangdao}

值得注意的是,如果初始归并段数不是严格的 m 叉树的话,直接使用哈夫曼树将得到错误的结果,比如将上面的长度为 30 的段去掉,就只有 8 个初始归并段了,这时候应当添加一个长度为 0 的虚段,以保证该结点只出现在离根结点最远处

# References

  1. 数据结构 - 浙江大学 - 中国大学 MOOC
  2. 2020 年数据结构考研复习指导 - 王道
  3. 2020 版数据结构高分笔记 - 天勤
  4. PTA | 程序设计类实验辅助教学平台
  5. 《数据结构 (C 语言版)》 严蔚敏 吴伟民 编著
  6. 《Introduction to Algorithms》 Thomas H.Cormen, Charles E.Leiserson 等