数据结构C++自学相关
注:标题里边有括号或者空格访问页面会404 不知道为啥 先暂且把符号删了吧 （已解决 是中英文混用导致的问题 下了个插件解析url至拼音）
再注:连锁反应吧大概 引出了纯英文大小写转换的bug 干脆把url生成逻辑改成hash值了 一劳永逸 再见了url可读性
PPPs:最后采用了直接定义链接的方式
大学课程里有 但也充其量是个引子 顺势自学点真本事
大部分内容会从书上摘录 其余的自己找了网上的资料
数据结构通过抽象的方法研究一组有特定关系的数据的存储与处理
数据结构主要研究三个方面的内容:
1.数据之间的逻辑关系 即数据的逻辑结构
2.数据及其逻辑关系如何在计算机中存储与实现 即数据的存储结构
3.在某种存储模式下 对数据施加的操作是如何实现的 即数据的运算算法是对特定问题求解步骤的一种描述 是指令的有限序列
其中每条指令表示一个或多个操作 简单来说 算法就是解决特定问题的方法算法与数据结构的关系紧密 选择的数据结构是否恰当将直接影响算法的效率 而数据结构的优劣由算法的执行来体现
程序设计的实质是 对要处理的实际问题选择一种合适的数据结构 再设计一个好的算法
时间复杂度 和 空间复杂度
比较笼统地说 他们分别代表了一个算法运行所用的理论时间和占用的存储空间
时间复杂度的常用表现形式为O(n) 代表了该算法的耗时随着n的变化而变化
常见的时间复杂度量级
常数阶O(1)
对数阶O(logN)
线性阶O(n)
线性对数阶O(nlogN)
平方阶O(n^2)
立方阶O(n^3)
K次方阶O(n^k)
指数阶(2^n)上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。
空间复杂度代表一个算法在运行过程中临时占用空间大小的量度
空间复杂度基本上是O(1)或者O(N)，其它的空间复杂度不常见。假设开一个N*N的数组，那么它的空间复杂度是O(N^2)。结构体不讨论结构体个数，只看整体。不看具体，只看量级。
线性表是最简单 最基本 也是最常用的一种线性结构
简单来说 一个线性表是n个元素的有限序列 元素可以是各种各样的 但必须具有相同性质 属于同一种数据对象
一个有n个元素的线性表通常记为 a0,a1,a2,a3,a4,an-1 ( n≥0 )
在较为复杂的线性表中 一个元素可以由若干数据项组成 这种线性表中的元素也常称为记录
为了方便以后的使用 含有大量记录的线性表往往存放在外部存储介质上 称为文件
C 语言中，可以定义一个结构体来表示顺序表：
1
2
3
4
5
typedef struct{
int * head; //定义一个名为head的长度不确定的数组，也叫“动态数组”
int length; //记录当前顺序表的长度
int size; //记录顺序表的存储容量
}Table;
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
#include <stdio.h>
#include <stdlib.h>
#define Size 5 //对Size进行宏定义，表示顺序表的最大容量
typedef struct{
int* head;
int length;
int size;
}Table;
void initTable(Table * t) {
//构造一个空的顺序表，动态申请存储空间
t->head = (int*)malloc(Size * sizeof(int));
//如果申请失败，作出提示并直接退出程序
if (!t->head)
{
printf("初始化失败");
exit(0);
}
//空表的长度初始化为0
t->length = 0;
//空表的初始存储空间为Size
t->size = Size;
}
//输出顺序表中元素的函数
void displayTable(Table t) {
int i;
for (i = 0; i < t.length; i++) {
printf("%d ", t.head[i]);
}
printf("\n");
}
int main() {
int i;
Table t = { NULL,0,0 };
initTable(&t);
//向顺序表中添加{1,2,3,4,5}
for (i = 1; i <= Size; i++) {
t.head[i - 1] = i;
t.length++;
}
printf("顺序表中存储的元素分别是：\n");
displayTable(t);
free(t.head);//释放申请的堆内存
return 0;
}
输出结果:
1
2
顺序表中存储的元素分别是：
1 2 3 4 5
链表是一种物理存储结构上非连续 非顺序的存储结构 数据元素的逻辑顺序是通过链表中的指针链接次序实现的
结构类似下图
1
phead->phead[1|p2]->p2[2|p3]->p3[3|p4]->p4[4|end]
[]中的内容都是结构体 称之为结点
与顺序表不同的是 链表中的每个结点不是只单纯的存一个数据 而是一个结构体 结构体成员包括一个所存的数据 和下一个结点的地址 此外 顺序表中的地址是连续的 而链表中结点的地址是随机分配的
图中的phead指针中存放的是第一个结点的地址 那么根据该地址我们就能找到这个结构体 又因为该结构体中存放了指向下一个结构体的地址 由此又能找到第二个结构体 循环往复 直到存放空地址的结构体
相关概念/术语:
- 头指针——单链表中第一个结点的地址存放在一个指针变量中 这个指针变量称为头指针 它的作用是标识一个单链表 所以常用它来代表单链表的名字 例如phead既表示单链表的名字是phead 又表示单链表的第一个结点的地址存储在指针变量phead中
- 首元结点——指单链表中存储其第一个元素的结点 也称为第一元素结点
- 头结点——在整个单链表的第一个结点之前加入一个结点 称为头结点 他的数据域可以不存储任何信息 其中存放的是首元节点的地址
定义方式:
1
2
3
4
5
6
7
//单链表节点定义
struct Node {
int data; // 数据域
Node* next; // 指针域
Node(int x) : data(x), next(nullptr) {} // 构造函数
};
单链表的特性使得向下遍历很方便 但要向上遍历会很难 于是有了双链表
双链表的每个结点又追加了一个指向前驱的指针域prior 使链表可以进行双向查找
1
2
3
4
5
6
7
8
9
10
11
12
13
//双链表的定义
template <class elemType>
struct Node {
elemType data;
Node *prior, *next;
Node (const elemType &value,Node *p = NULL,Node *n = NULL){
data = value;
prior = p;
next = n;
}
Node():next(NULL),prior(NULL){}
~Node(){}
};
单链表只能从头结点开始遍历整个链表 若希望从任意一个结点开始遍历整个链表 则可以将单链表通过指针域首尾相接（即尾结点的指针域指向头结点） 形成一个单循环列表
1
2
3
4
5
//循环列表的定义
typedef struct Node {
int data; // 数据域
struct Node *next; // 指向下一个结点
} Node;
栈是只允许在表的一端进行插入、删除操作的线性表 具有后进先出/先进后出的特点 后进先出表示最晚进栈的最先被删除 先进后出表示最先进栈的元素最后被删除
栈的术语说明如下：
- 栈顶（Top）：允许进入插入和删除操作的表的一端称为栈顶
- 栈底（Bottom）：表的另一端称为栈底
- 进栈（Push）：在栈底位置插入元素 也叫入栈、压栈
- 出栈（Pop）：删除栈顶元素 也叫弹栈 退栈
- 空栈：不含元素的空表称为空栈
- 栈溢出：当栈满时 若再有元素进栈 则发生上溢;当栈空时 若再出栈 则发生下溢
利用顺序存储结构实现的栈称为顺序栈 类似于顺序表 顺序栈中的元素用一个一维数组来存储 栈底位置可以设置在数组的任意一个端点处 通常设在小下标的一段 栈顶是随着插入和删除操作而变化的
为方便操作 用一个整型变量top存放栈顶元素的位置（下标） top称为栈顶指针
初始时 top=-1 表示栈为空 元素进栈 top加1 然后将数据写入top所指向的存储单元中 出栈时 top减1
1
2
3
4
5
6
7
8
//最基础的 依数组实现的顺序栈
#define MAXSIZE 100
typedef struct {
int data[MAXSIZE]; // 存放元素
int top; // 栈顶指针（指向栈顶元素下标）
} Stack;
用链式存储结构实现的栈
1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct Node {
int data;
struct Node *next;
} Node;
typedef struct {
Node *top; // 栈顶
int length; // 可选
} LinkStack;
//初始化
LinkStack s;
s.top = NULL;
s.length = 0;
队列是一种只允许在表的一端插入 在另一端删除的 操作受限的线性表
像排队一样 入队时排在队尾 到达越早的节点离开的越早 所以队列的特点是先进先出
允许插入的一端称为队尾（rear） 允许删除的一端称为队头（front）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <queue>
#include <iostream>
// 基本队列定义
std::queue<int> intQueue; // 存储int类型的队列
std::queue<double> doubleQueue; // 存储double类型的队列
std::queue<std::string> stringQueue; // 存储string类型的队列
// 自定义类型的队列
struct Person {
std::string name;
int age;
};
std::queue<Person> personQueue;
串是字符串的简称 它是一种在元素的组成上具有一定约束条件的线性表 即要求组成线性表的所有元素都是字符
所以 人们经常这样定义串：由0个或多个字符顺序排列所组成的有限序列
串一般记作：S="S0,S1,...,Si,...,Sn-1"(n≥0,0≤i<n)
串的长度：一个串所包含的字符的个数 称为串的长度
空串：当串的长度为0时 串中没有任何字符 称为空串 如S=””
空格串：由空格字符组成的串 称为空格串 如S=” “
子串：串中任意个连续的字符组成的子序列称为该串的子串 空串是任意串的子串 任意串都是其自身的子串
真子串：非空且不为自身的子串 称为真子串
主串：包含子串的串 称为该子串的主串
子串定位：查找字串在主串中第一次出现的位置
串相等：若两个穿的长度相等 且各对应的字符也都相同 则称两个串相等
1
2
3
4
5
6
7
8
9
10
11
#include <cstring>
#include <iostream>
// 字符数组形式
char str1[] = "Hello"; // 自动计算长度，包含'\0'
char str2[6] = {'H', 'e', 'l', 'l', 'o', '\0'}; // 显式指定长度和结束符
char str3[] = {'H', 'i'}; // 不是字符串，没有'\0'
// 指针形式
char* str4 = "World"; // 指向常量字符串的指针
char* str5 = new char[10]; // 动态分配
这章重点讲了串模式匹配的BF算法和KMP算法
BF算法 俗称暴力破解算法 效率较低
它的思想是 由第一轮开始 将子串中的第一个字符和主串中的第一个字符进行比较 若相同则继续 若不同 则进入下个循环
不断重复 直至发现主串中与子串完全相符的部分
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
//主串的每一个字符与子串的开头进行匹配，匹配成功则比较子串与主串的下一位是否匹配，匹配失败则比较子串与主串的下一位，很显然，我们可以使用两个指针来分别指向主串和子串的某个字符，来实现这样一种算法
//匹配成功，返回子串在主串中第一次出现的位置，匹配失败返回 -1，子串是空串返回 0
int String::bfFind(const String &s, int pos) const {
//主串和子串的指针，i主串，j子串
int i, j;
//主串比子串小，匹配失败，curLenght为串的长度
if (curLength < s.curLenght)
return -1;
while (i < curLength && j < s.curLength) {
//对应字符相等，指针后移
if (data[i] == s.data[j])
i+, j++;
else { //对应字符不相等
i = i -j + 1; //主串指针移动
j = 0; //子串从头开始
}
//返回子串在主串的位置
if (j >= s.curLength)
return (i - s.curLength);
else return -1;
}
}
KMP算法相较于BF算法更为快速 核心思想为可以利用已经匹配成功的部分信息 跳过一些不必要的比较
流程很好理解 在已经遍历的部分中寻找与自己所查子串前几个字符相近的部分
其中需要我们定义一个next[]数组 来标注指针所需要回到的位置
原理便是将已遍历的部分倒序依次输出 寻找相同的部分（例如above 处理后输出 e ve ove bove above）
1
2
3
4
5
6
7
8
9
10
11
12
13
求next数组算法实现
void Stirng::getNext(const String &t, int *next) {
int i = 0, j = -1;
next[0] = -1;
while (i < t.curLength - 1) {
if ((j == -1) || t[i] == t[j]) {
++i, ++j;
next[i] = j;
}else{
j = next[j];
}
}
}
然后就能来实现KMP算法了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int String::kmpFind(const String &t, int pos) {
//不允许申请大小为0的数组
if (t,curLength == 0) return 0;
//如果主串比子串小，匹配失败
if(t.curLength < t.curLength) return -1;
//主串指针i，子串指针j
int i = 0, j = 0;
int *next = new int[t.curLrngth];
getNext(t,next);
while (i < curLength && j < t,curLength) {
if (j == -1 || data[i] == t.data[j]) //情况12
i++, j++;
else //情况3
j = next[j];
}
delete []next;
if (j > t.curLength)
return (i - t.curLength)
else
return -1;
}
数组是数据元素为线性表扩展的线性结构 可以看作线性结构的推广 是由类型相同的元素构成的有序集合 每个元素都可以看做下标和值的偶对
以数组为元素的数组即为多元数组
矩阵通常是用二维数组的形式来表示的 5.2介绍了对称矩阵 三角矩阵 对角矩阵可以通过压缩存储的方式来节省空间
树结构是一种重要的非线性结构 可以用来描述数据元素间的层次关系 图示如下
1
2
3
4
5
1
/ \
2 3
/ \ / \
4 5 6 7
树的概念和术语说明如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(1)树(Tree)是由n(n≥0)个结点构成的有限集合T 若T=0 则称为空树; 否则 一个非空树需要满足以下两个条件
① 有且只有一个特定的 称为根(Root)的结点
② 除根节点以外的其他结点被分成m(m≥0)个互不相交的有限集合T1,T2,...,Tm,其中每个集合又是一棵树 这些树称为子树
(2)结点(Node)包含数据项及指向其他结点的分支
(3)结点的度表示结点所拥有的子树的数目
(4)叶结点 也叫终端结点 指度为0的结点 叶结点没有后续
(5)分支结点 也叫非终端结点 指度不为0的结点 也就是除叶结点以外的结点
(6)结点的层次 结点头上有n道杠就是n+1层的结点
(7)儿子 爸爸 兄弟 堂兄弟 祖先 子孙结点
儿子：一个节点的直接下级节点，该节点是其父节点。
爸爸：一个节点的直接上级节点，该节点是其子节点的父节点。
兄弟：拥有同一个父节点的两个或多个节点，它们之间互为兄弟。
堂兄弟：在同一层且父节点互为兄弟的两个节点，它们之间互为堂兄弟。
祖先：从根节点到当前节点路径上的所有节点，都称为该节点的祖先。
子孙结点：以某个节点为根的子树中所包含的所有节点，都称为该节点的子孙结点。
(8)树的高度/深度:树中结点的最大层次
(9)有序/无序树:一个树的次序是否重要/可否进行交换决定了其有序性
(10)森林:m(m≥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
1
/ \
2 3
/ \ / \
4 5 6 7
1. 前序遍历
规则：根 → 左 → 右
1. 从根 1 开始，访问 1
2. 进入左子树 2（根为 2）
• 访问 2
• 进入左子树 4（根为 4）
◦ 访问 4（无左右孩子，返回）
• 回到 2，进入右子树 5（根为 5）
◦ 访问 5（无左右孩子，返回）
3. 回到 1，进入右子树 3（根为 3）
• 访问 3
• 进入左子树 6（根为 6）
◦ 访问 6（无左右孩子，返回）
• 回到 3，进入右子树 7（根为 7）
◦ 访问 7（无左右孩子，返回）
前序遍历结果：
1 → 2 → 4 → 5 → 3 → 6 → 7
2. 中序遍历
规则：左 → 根 → 右
1. 从根 1 开始，先遍历左子树 2
• 对 2 先遍历它的左子树 4
◦ 4 无左孩子，访问 4
◦ 回到 2（根），访问 2
◦ 遍历 2 的右子树 5
◦ 5 无左孩子，访问 5
2. 回到 1，访问 1
3. 遍历 1 的右子树 3
• 对 3 先遍历它的左子树 6
◦ 6 无左孩子，访问 6
◦ 回到 3（根），访问 3
◦ 遍历 3 的右子树 7
◦ 7 无左孩子，访问 7
中序遍历结果：
4 → 2 → 5 → 1 → 6 → 3 → 7
3. 后序遍历
规则：左 → 右 → 根
1. 从根 1 开始，先遍历左子树 2
• 对 2 先遍历它的左子树 4
◦ 4 无左右孩子，访问 4
• 遍历 2 的右子树 5
◦ 5 无左右孩子，访问 5
• 回到 2，访问 2
2. 回到 1，遍历右子树 3
• 对 3 先遍历它的左子树 6
◦ 6 无左右孩子，访问 6
• 遍历 3 的右子树 7
◦ 7 无左右孩子，访问 7
• 回到 3，访问 3
3. 回到 1，访问 1
后序遍历结果：
4 → 5 → 2 → 6 → 7 → 3 → 1
4. 层次遍历
规则：按层从左到右
• 第 1 层：1
• 第 2 层：2, 3
• 第 3 层：4, 5, 6, 7
层次遍历结果：
1 → 2 → 3 → 4 → 5 → 6 → 7
最终答案：
• 前序：1, 2, 4, 5, 3, 6, 7
• 中序：4, 2, 5, 1, 6, 3, 7
• 后序：4, 5, 2, 6, 7, 3, 1
• 层次：1, 2, 3, 4, 5, 6, 7
树转成二叉树具体步骤如下:
1.先给所有同层且相邻的兄弟之间加上虚线
2.保留树中每个结点和长子之间的连线 删除和其他孩子之间的连线
3.以树的根节点为轴心 将整棵树顺时针转动45° 使其结构更加分明
森林转化成二叉树同理 就是森林里的每个树单独处理一遍
二叉树转成树具体步骤如下:
1.若某结点是其双亲的左孩子 则把该结点的右孩子 右孩子的右孩子等与该节点的双亲用虚线链接起来
2.删除原二叉树中所有双亲结点与右孩子结点之间的连线
3.整理得到的树 逆时针转动45°
图由顶点的非空集合V和边或弧的集合E组成 表示为G=(V,E) V(G)和E(G)分别表示G的顶点集和边集
|V|表示顶点集中元素的个数 即顶点数 n个顶点的图称为n阶图 |E|表示边集中元素的个数 即边数
可以表示如下
G=(V,E)
V(G)={A,B,C,D}
E(G)={(A,B),(B,C),(C,D),(B,D)}
图的概念和术语如下:
- 图:由顶点的非空集合V和边或弧的集合E组成 表示为G=(V,E) V表示点的集合 E表示边的集合 按照图中的边是否有方向 可分为有向图/无向图
- 有向图:若图中顶点对是有序的 即边是有方向的 边集E为有向边的集合 则图G称为有向图
在有向图中 一般将边称为弧 以有序对<u,v>表示一条从顶点u出发到达顶点v的弧 其中u称为弧尾或起点 v称为弧头或终点 - 无向图:若图中定点对是无序的 即边是无方向的 边集E(G)为无向边的集合 则图G称为无向图
在无向图中 以无序对(u,v)表示u和v之间存在一条无向边 且边是对称的 (u,v)和(v,u)表示同一条边 - 无向完全图:在一个无向图中 如果两个任意顶点都有两条边直接相连 则称该图为无向完全图
有n个顶点的无向完全图有n(n-1)/2条边
深度优先遍历又称为深度优先搜索 类似于树的前序遍历 尽可能先对纵深方向进行搜索 其遍历过程如下:
（1）选定一个未被访问的顶点v 并给该顶点附上已访问的标志
（2）然后依次从顶点v的未被访问的邻接点出发深度优先遍历图
重复上列过程 直到所有和v有路径相通的顶点都被访问到 若还有顶点未被访问 则再选取其他未被访问的顶点 重复以上遍历过程 直到访问完所有顶点为止
广度优先遍历又称为广度优先搜索 类似于树的层次遍历 其遍历过程如下:
（1）首先选定一个未被访问的顶点v 并给该顶点附上已访问的标志
（2）依次访问与顶点v邻接的未被访问的全部邻接点 然后从这些访问过的邻接点出发 依次访问它们各自的未被访问的邻接点 并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问
重复上述过程 直至图中所有与v相连的顶点都被访问到 若图中还有其他顶点未被访问到 则任选一个作为源点 再次重复以上步骤 直到访问完所有顶点为止
Prim算法:从起始顶点出发 每次迭代选择当前可用的最小权值边 然后把边上依附的其他顶点加入最小生成树
Kruskal算法:每次迭代选择当前可用的最小权值边 且该边加入生成树的边集中不会产生环 直到图中所有顶点都能联通
折半查找 分块查找
散列表也被称为哈希表（Hash table）是根据关键字的值直接访问元素存储位置的存储结构.也就是说 在元素的存储地址和关键字之间建立一个确定的对应关系H 使每个关键字和
给加权图生成最小生成树的法子
Prim是先看指定的点 根据这个点选权最小的道路 然后不重复不走回环 生成一条道路
Krusal是在图中逐次确定权最小的边 只要不会产生环路就加入图中 形成一条道路
前序 中序 后序 层次遍历 深度优先 广度优先
从数组的第一个元素开始 与前面的元素比较 前面的元素比他大则前面的元素向右移动 比他小则在该元素的后面插入
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始(末尾)位置，
然后选出次小(或次大)的一个元素，存放在最大(最小)元素的下一个位置，
重复这样的步骤直到全部待排序的数据元素排完 。
两两元素相比，前一个比后一个大就交换，直到将最大的元素交换到末尾位置。这是第一趟
一共进行n-1趟这样的交换将可以把所有的元素排好。
这里以升序为例：
首先应该建一个大堆，不能直接使用堆来实现。可以将需要排序的数组看作是一个堆，但需要将数组结构变成堆。
我们可以从堆从下往上的第二行最右边开始依次向下调整直到调整到堆顶，这样就可以将数组调整成一个堆，且如果建立的是大堆，堆顶元素为最大值。
然后按照堆删的思想将堆顶和堆底的数据交换，但不同的是这里不删除最后一个元素。
这样最大元素就在最后一个位置，然后从堆顶向下调整到倒数第二个元素，这样次大的元素就在堆顶，重复上述步骤直到只剩堆顶时停止。
先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的元素进行排序。
然后将gap逐渐减小重复上述分组和排序的工作。
当到达gap=1时，所有元素在统一组内排好序。
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
若将两个有序表合并成一个有序表，称为二路归并。
迪杰斯特拉算法是一种用于在带权有向图中找到从一个源点到其他所有顶点的最短路径的贪心算法。其基本思想是：设置一个顶点集合 S，初始时 S中只包含源点 v0，然后不断从不在 S中的顶点中选择距离源点 v0最近的顶点 u加入 S，并更新从 v0到其他不在 S中顶点的最短距离。
会给你一套字母 和对应字母的出现次数
画一个带权的树 将最小的数不断相加（小的放左边 大的放右边）变成一个二叉树
最终结果要算对应的路径 左叉为0 右叉为1
例如下图
1
2
3
4
5
6
7
8
9
10
11
12
(136)
/ \
(64) (72)
/ \ / \
G29 (35) F31 (41)
/ \ / \
C17 H18 (18) A23
/ \
(9) E9
/ \
D4 B5
最终要算的**WQL（带权路径长度）*只需要每个字母的出现次数编码长度相加即可
很简单 前序最前面的是根 后序最后面的是根
按照根来把中序的左右两边划开来 然后再去前序/后续里找对应分叉的根 以此类推
先把整个树的中序遍历看下来 例如一个这样的树
1
2
3
4
5
6
7
A
/ \
B C
/ \ \
D E F
中序遍历后
D → B → E → A → C → F
随后标出空指针——没左孩子的左指针为空 没右孩子的右指针为空 以此类推
然后最后一步 若某结点 左指针为空 用虚线箭头指向它的中序前驱 若某结点 右指针为空 用虚线箭头指向它的中序后继
比如这我们判断d没左孩子也没右孩子 所以这里他左边有箭头指向NULL 后边有箭头指向中序遍历的后一项 B
以此类推 把整个树标完
c++课摸得有点多 得从比较基础的地方开始学起了
首先是搞懂每个部分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct
typedef
malloc
变量前面加上()
->next
insert
如何遍历创建出来的结构
用于定义一个可包含不同类型数据成员的结构体 具体格式如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 定义结构体
struct Student {
int id;
string name;
float score;
};
// 使用结构体
Student s1; // 声明变量
s1.id = 1001;
s1.name = "张三";
s1.score = 95.5;
// 也可以在定义时初始化
Student s2 = {1002, "李四", 88.0};
也可以在定义时便声明一些变量
1
2
3
4
5
6
7
8
9
10
// 定义结构体并同时声明变量
struct Student {
int id;
string name;
float score;
} student1, student2; // 这里声明了两个Student类型的变量
// 使用
student1.id = 1001;
student2.id = 1002;
用于为现有类型创建新的名称别名 例如typedef int Integer;便是创建了一个名为Integer 的变量
1
2
3
4
5
6
7
8
9
10
11
12
13
// 为基本类型创建别名
typedef int Integer;
Integer age = 25;
// 为结构体创建别名
typedef struct Node {
int data;
Node* next;
} Node, *LinkList; // Node是结构体类型，LinkList是指向Node的指针类型
// C++11之后更推荐使用using
using String = std::string;
String myStr = "Hello";
变量前边加上括号 括号中加上变量类型 这是尝试转化数据类型的标志
We are just another visitor in a transient world.