0%

最近思绪有点乱,感觉要做的事情很多,但是不知道何从下手,所以我要从头缕一缕现在的问题。

首先是分析一下现阶段我要做的事情,按优先级进行分类:

  • 课程任务:(这几门课是这个学期的大头)
    • 离散数学:这个课我现在最大的问题就是没有明确的学习路线(对着书硬啃?找个网课学?)
    • 概率论:这个课我的进度很慢,但是有一高数的课程可以跟着学习,可以从现在开始每天学一点
    • 操作系统:这个课我学的还行,但是我对自己有一定的要求,不想只是简单学会
    • 计算机组成原理:这个课的应试考法我也不是很熟悉,对于数据的部分不是很熟悉,其他的还可以,但是我对自己也有一定的有要求
    • 数据结构:这门课学的还行,但是不熟悉应试的考法
    • 密码学:目前不清楚考试考察的方向,需要花时间巩固
    • Python:现在要开始准备大作业
    • Java:需要对着PPT再进一步学习,需要准备大作业
    • 毛思想:需要了解一下考什么,和题型。考前需要花时间学习一下
  • 课外任务:
    • 科研任务:科研训练从和开始入手,怎么去查看论文,怎么去找创新点,怎么去构建项目。
    • 个人任务:
      • 锻炼身体:需要加强身体的锻炼和饮食的均衡
      • 练习英语:提升英语水平
      • CTF二进制安全竞技水平
      • 学习新知识
      • 看书阅读

这里加粗的部分是需要着重注意的地方,那么我该怎么安排呢?

生活上的安排

首先是睡眠,每天十二点必须上床,手机最多玩到十二点半就要睡觉。有早八就七点一十起床,没早八就八点起床。周日可以休息久一点

每天早上至少喝一瓶牛奶,还有早餐。在寝室的期间要喝热水。平时尽量不喝奶茶喝其他饮料,也要控制自己的饮食,不能像以前一样想怎么吃就怎么吃。

平时要坚持锻炼,一周至少锻炼4次,两次耐力,两次力量。没事的时候可以在寝室举哑铃

每天要积极一点,心情不好就出去走一走,要开心。

节假日和周六晚上可以玩久一点游戏,平时尽量少玩一点。要珍惜现在的时间。

学习上的安排

除掉周日,单日学概率论,双日学离散数学,每天至少完成一个章节的学习。在什么课上学什么的知识,不能拆东墙补西墙。

这周之内要开始科研训练的内容,首先给出自己一个项目的框架,可行demo

课余的时间学什么由自己决定,优先课程的任务。

感情上的安排

别想太多 要接受分开的事实 继续走下去

上个学期也尝试了解过这些,但是那个时候还没有接触编译链接,对DWARF信息的理解不够深刻。最近有计划了解一下调试器的原理,所以重新捡起来好好学一遍。

我参考的教程是DWARF的官方介绍文档Debugging using DWARF,作为对其的简单了解

DWARF概述

一开始我并不知道怎么说明这一部分,AI给了我一个很好的比方。如果说程序是一个设计图纸(源代码),它事无巨细的包含一个城市的所有信息,那么编译器就是一个工程师,他根据设计图纸将建造出城市(可执行文件)。而DWARF信息,就相当于这个城市的地图,它告诉你每条街道(机器指令,数据信息)对应设计图中的哪个位置(源代码)。而调试器就是一个导游,它根据这个地图带你去任何地方。

现代的编程语言大多是块状结构的,一个实体往往包含着更多的实体,每个实体中可能都有若干个数据和函数定义,那么在这个实体中,就产生了词法的作用域。这个定义仅在被定义的作用域中有意义。

我们可以用一个常见的文件结构来描述这种特征:

1
2
3
4
5
6
7
8
9
10
源文件
├── 函数A
│ ├── 变量x
│ ├── 语句块1
│ │ ├── 变量y (只在当前块内有效)
│ │ ├── 函数C
│ │ └── ...
│ └── ...
└── 函数B
└── ...

对于数据和函数一类的内容,我们按照编译链接的习惯,称之为符号。一般情况下,一个符号的作用域属于当前块(也可以通过关键词指定作用域范围)。所以我们要查找特定符号的定义,先从当前作用域中查找定义,然后从连续的外层定义域中依次查找,直到找到该符号。

1
2
3
4
5
6
7
8
int global_var;          // 全局作用域
void my_function() { // 函数作用域
int local_var; // 函数内有效
if (condition) {
int block_var; // 只在if块内有效
}
// block_var 在这里结束
}

但是在编译链接的过程中,这些信息会被抛弃或者是简化。因为编译器只在乎对内存和寄存器的管理和操作,所以我们很难根据机器指令去恢复这些信息。

所以这里我们就需要DWARF信息来保存这些信息,DWARF和程序语义一样,通过树状结构来组织信息。DWARF中的所有描述性实体都包含在一个父条目中,且实体中还可以包含更多节点,这些节点可能表示类型,变量或是函数…一个常见的结构可以是下面这样的:

1
2
3
4
5
6
7
8
9
10
11
12
编译单元 (CU)
├── 函数: main
│ ├── 类型: int
│ ├── 变量: argc
│ ├── 变量: argv
│ └── 代码位置: 0x400500-0x400600
├── 函数: add
│ ├── 参数: a (int)
│ ├── 参数: b (int)
│ ├── 局部变量: result (int)
│ └── 代码位置: 0x400610-0x400650
└── 全局变量: global_counter

而接下来,我们将学习怎么去理解这些常见的DWARF信息

调试信息条目(DIE)

标签与属性

DWARF 中的基本描述实体是调试信息条目。一个 DIE 包含一个标签——用于指定该 DIE 描述的是什么,以及一个属性列表——用于填充细节并进一步描述该实体。除了最顶层的 DIE 外,每个 DIE 都包含在或归属于一个父 DIE,并且可能拥有兄弟 DIE 或子 DIE。属性可以包含各种值:常量(例如函数名)、变量(例如函数的起始地址),或者指向另一个 DIE 的引用(例如函数返回值的类型)

例如下图中就展示了一个简单的程序的DWARF信息:

image.png

最上面的是CU编译单元,它作为DWARF信息的根节点,包含了两个下级DIE。其中一个描述main的信息,如返回类型、行号、函数起始地址…另一个DIE描述的是int类型,通过子程序DIE中的Type属性而被引用。

DIE类型

DIE可以分为两种通用类型:

  • 一类用来描述数据的DIE
  • 另一类用来描述函数或者其他可执行代码

基础类型->数据类型

大多数语言都有复杂的数据类型体系,例如内置数据类型、指针、数据结构、自定义结构等类型。这些基于语言底层设计的主要类型我们称之为基础类型,其他的数据类型都由这些基础类型构造而成。

一个具名变量由一个拥有多种属性的 DIE 描述,其中一个属性是对类型定义的引用。下图就描述了一个名为x的整型变量:

image.png

int 的基础类型将其描述为一个占用四个字节的有符号二进制整数。用于变量 xDW_TAG_variable DIE 给出了它的名称和一个类型属性,该属性引用了基础类型 DIE。

同样的,DWARF 也可以使用基础类型通过组合来构建其他数据类型定义。一个新类型是作为对另一个类型的补充而创建的。以下面这个int* px的DIE信息为例:

image.png

这个 DIE 定义了一个指针类型,指明其大小为四个字节,并继而引用了 int 基础类型。

还可以更复杂的,比如加上关键词去限定这个变量的属性和类型,也可以将更多类型的DIE链接在一起以描述更复杂的数据类型,例如const char ** argv的DIE信息如下:

image.png

总的来说,在DWARF信息中,我们通过组合基本类型的方式来表示程序语言中的数据类型。这样我们无需了解所有程序语言的数据结构,也可以描述出数据类型的信息。

常见类型

数组

数组类型由DW_TAG_array_type表示,对于int arr[10],其一般DWARF结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
< 1><0x0000002e>    DW_TAG_array_type
DW_AT_type <0x00000045>
DW_AT_sibling <0x0000003e>
< 2><0x00000037> DW_TAG_subrange_type
DW_AT_type <0x0000003e>
DW_AT_upper_bound 9
< 1><0x0000003e> DW_TAG_base_type
DW_AT_byte_size 0x00000008
DW_AT_encoding DW_ATE_unsigned
DW_AT_name long unsigned int
< 1><0x00000045> DW_TAG_base_type
DW_AT_byte_size 0x00000004
DW_AT_encoding DW_ATE_signed
DW_AT_name int
< 1><0x0000004c> DW_TAG_variable
DW_AT_name arr
DW_AT_decl_file 0x00000001 /home/ylin/Program/test/./test.c
DW_AT_decl_line 0x00000001
DW_AT_decl_column 0x00000005
DW_AT_type <0x0000002e>
DW_AT_external yes(1)
DW_AT_location len 0x0009: 0x034040000000000000:
DW_OP_addr 0x00004040

其中DW_TAG_subrange_type用来存储描述数组维度的范围(下标范围),这里不仅指示了下标的上界DW_AT_upper_bound 9也指明了下标的数据类型DW_AT_type <0x0000003e>

我们可以看到左边的<1> <2>的符号,这代表当前条目在条目树结构中的深度。

理解了数据类型的结构分析之后,我们看到变量的定义信息:

  • DW_AT_name:变量名
  • DW_AT_decl_line:变量的定义行
  • DW_AT_decl_column:变量的定义列
  • DW_AT_type:变量定义类型
  • DW_AT_external:变量的作用域范围(全局符号)
  • DW_AT_location:变量在内存中的存储位置

通过这些信息,我们就可以还原出数组的数据类型、存储结构、以及在源代码中的定义位置等信息

结构、类、联合体、接口

大多数的语言都支持将各种数据类型的组合到一个结构体中,只不过不同的语言叫法不一样而已,这里的我们就简单的介绍一下结构体和类的标签。

结构体相较于类更加纯粹,它主要对数据进行封装,将不同的数据类型整合成一个大的结构体,在结构体中通过字段对这些数据进行索引,我们可以看下它的DWARF结构

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
< 1><0x0000002e>    DW_TAG_structure_type
DW_AT_byte_size 0x00000010
DW_AT_decl_file 0x00000001 /home/ylin/Program/test/./test.c
DW_AT_decl_line 0x00000001
DW_AT_decl_column 0x00000001
DW_AT_sibling <0x00000052>
< 2><0x00000037> DW_TAG_member
DW_AT_name age
DW_AT_decl_file 0x00000001 /home/ylin/Program/test/./test.c
DW_AT_decl_line 0x00000002
DW_AT_decl_column 0x00000009
DW_AT_type <0x00000052>
DW_AT_data_member_location 0
< 2><0x00000044> DW_TAG_member
DW_AT_name name
DW_AT_decl_file 0x00000001 /home/ylin/Program/test/./test.c
DW_AT_decl_line 0x00000003
DW_AT_decl_column 0x0000000b
DW_AT_type <0x00000059>
DW_AT_data_member_location 8
< 1><0x00000052> DW_TAG_base_type
DW_AT_byte_size 0x00000004
DW_AT_encoding DW_ATE_signed
DW_AT_name int
< 1><0x00000059> DW_TAG_pointer_type
DW_AT_byte_size 0x00000008
DW_AT_type <0x0000005f>
< 1><0x0000005f> DW_TAG_base_type
DW_AT_byte_size 0x00000001
DW_AT_encoding DW_ATE_signed_char
DW_AT_name char
< 1><0x00000066> DW_TAG_variable
DW_AT_name student
DW_AT_decl_file 0x00000001 /home/ylin/Program/test/./test.c
DW_AT_decl_line 0x00000004
DW_AT_decl_column 0x00000002
DW_AT_type <0x0000002e>
DW_AT_external yes(1)
DW_AT_location len 0x0009: 0x032040000000000000:
DW_OP_addr 0x00004020

结构体类型由DW_TAG_structure_type进行表示,这里我们定义的结构体如下:

1
2
3
4
struct{
int age;
char* name;
}student;

我们可以阅读到以下结构体的属性:

  • DW_TAG_member:结构体的成员
  • DW_AT_data_member_location:字段在结构体中偏移值,我们可以通过这个值访问结构体中的成员
  • DW_AT_byte_size:结构体的大小(这里可以看出内存对齐了)
  • 还有典型的一些属性…

然后是类的,类相当于结构体的plus版,既可以组合数据类型,也可以包含函数方法,不过对于类的内存分布,我暂时也不是很清楚。我们可以看看类的DWARF信息:

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
< 1><0x0000002a>    DW_TAG_class_type
DW_AT_name Student
DW_AT_byte_size 0x00000010
DW_AT_decl_file 0x00000001 /home/ylin/Program/test/test.cpp
DW_AT_decl_line 0x00000003
DW_AT_decl_column 0x00000007
DW_AT_sibling <0x0000006d>
< 2><0x00000037> DW_TAG_member
DW_AT_name ID
DW_AT_decl_file 0x00000001 /home/ylin/Program/test/test.cpp
DW_AT_decl_line 0x00000005
DW_AT_decl_column 0x0000000d
DW_AT_type <0x0000006d>
DW_AT_data_member_location 0
< 2><0x00000043> DW_TAG_member
DW_AT_name name
DW_AT_decl_file 0x00000001 /home/ylin/Program/test/test.cpp
DW_AT_decl_line 0x00000008
DW_AT_decl_column 0x0000000f
DW_AT_type <0x00000074>
DW_AT_data_member_location 8
DW_AT_accessibility DW_ACCESS_public
< 2><0x00000051> DW_TAG_subprogram
DW_AT_external yes(1)
DW_AT_name getID
DW_AT_decl_file 0x00000001 /home/ylin/Program/test/test.cpp
DW_AT_decl_line 0x00000009
DW_AT_decl_column 0x0000000d
DW_AT_linkage_name _ZN7Student5getIDEv
DW_AT_type <0x0000006d>
DW_AT_accessibility DW_ACCESS_public
DW_AT_declaration yes(1)
DW_AT_object_pointer <0x00000066>
< 3><0x00000066> DW_TAG_formal_parameter
DW_AT_type <0x00000080>
DW_AT_artificial yes(1)
< 1><0x0000006d> DW_TAG_base_type
DW_AT_byte_size 0x00000004
DW_AT_encoding DW_ATE_signed
DW_AT_name int
< 1><0x00000074> DW_TAG_pointer_type
DW_AT_byte_size 0x00000008
DW_AT_type <0x00000079>
< 1><0x00000079> DW_TAG_base_type
DW_AT_byte_size 0x00000001
DW_AT_encoding DW_ATE_signed_char
DW_AT_name char
< 1><0x00000080> DW_TAG_pointer_type
DW_AT_byte_size 0x00000008
DW_AT_type <0x0000002a>
< 1><0x00000085> DW_TAG_const_type
DW_AT_type <0x00000080>

类的类型由DW_TAG_class_type进行表示,这里我们定义的类是这样的:

1
2
3
4
5
6
7
8
9
10
class Student{
private:
int ID;

public:
char* name;
int getID(){
return ID;
}
};

我们可以阅读以下类的信息:

  • DW_TAG_subprogram:这里表示这是类的一个方法,之后会详细描述一下这个标签
  • DW_AT_accessibility:用来指出数据和方法的成员属性(公/私),默认为私有,DW_ACCESS_public为公有
  • DW_AT_object_pointer:这个是隐含得参数指向this指针参数。

类由还有很多标签,但是这里不过多进行讲解。

变量

变量通常相当简单。它们有一个名称,代表一块可以存储某种值的内存(或寄存器)。变量可以包含的值的种类,以及对其修改方式的限制(例如,是否为 const),都由变量的类型来描述。

区分变量的关键在于其值的存储位置和其作用域。变量的作用域定义了变量在程序中的哪些位置是已知的,并在某种程度上由变量声明的位置决定。在 C 语言中,在函数或块内声明的变量具有函数或块作用域。在函数外声明的变量具有全局或文件作用域。这允许在不同文件中定义同名的变量而不会冲突,也允许不同的函数或编译单元引用同一个变量。

DWARF 将变量分为三类:常量形式参数变量

  • 常量用于那些语言本身包含真正具名常量的情况,例如 Ada 参数。(C 语言本身没有将常量作为语言的一部分。声明一个 const 变量只是表示你不能在没有使用显式类型转换的情况下修改变量。)
  • 形式参数表示传递给函数的值。我们稍后再讨论这个。

大多数变量都有一个位置属性,用于描述变量的存储位置。

  • 在最简单的情况下,变量存储在内存中并具有固定地址
  • 但是许多变量,例如在 C 函数内声明的变量,是动态分配的,定位它们需要进行一些(通常简单的)计算。例如,一个局部变量可能在栈上分配,定位它可能简单到只需给帧指针加上一个固定偏移量。
  • 在其他情况下,变量可能存储在寄存器中。
  • 其他变量可能需要更复杂一些的计算来定位数据。作为 C++ 类成员的变量可能需要更复杂的计算来确定基类在派生类中的位置。

可执行代码段:函数与子程序

这里的函数和子程序实际上是同一个东西,硬要细分的话,函数是有返回值的,而子程序没有(我们更多是利用子程序的副作用)。我们可以看一下函数会包含的DWARF信息:

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
< 1><0x00000065>    DW_TAG_subprogram
DW_AT_external yes(1)
DW_AT_name hello
DW_AT_decl_file 0x00000001 /home/ylin/Program/test/test.c
DW_AT_decl_line 0x00000001
DW_AT_decl_column 0x00000005
DW_AT_prototyped yes(1)
DW_AT_type <0x0000005e>
DW_AT_low_pc 0x00001129
DW_AT_high_pc <offset-from-lowpc> 24 <highpc: 0x00001141>
DW_AT_frame_base len 0x0001: 0x9c:
DW_OP_call_frame_cfa
DW_AT_call_all_calls yes(1)
< 2><0x00000083> DW_TAG_formal_parameter
DW_AT_name x
DW_AT_decl_file 0x00000001
DW_AT_decl_line 0x00000001
DW_AT_decl_column 0x0000000f
DW_AT_type <0x0000005e>
DW_AT_location len 0x0002: 0x916c:
DW_OP_fbreg -20
< 2><0x0000008e> DW_TAG_formal_parameter
DW_AT_name y
DW_AT_decl_file 0x00000001
DW_AT_decl_line 0x00000001
DW_AT_decl_column 0x00000016
DW_AT_type <0x0000005e>
DW_AT_location len 0x0002: 0x9168:
DW_OP_fbreg -24

首先我们可以看到包含源代码位置信息的三元组(文件、行、列),然后是函数的高低内存范围,一般情概况下,我们默认函数的低内存地址(起始地址)为函数的入口。函数的返回类型,由类型属性指定。

这里需要注意的是DW_OP_call_frame_cfa指定的CFA0x9c。CFA就是函数执行时,其调用者的栈帧的栈顶位置,标志着一个函数栈帧的开始边界。以下图结构为例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(高地址)
+----------------------+
| ... |
| main 的局部变量 | <--- main 函数的栈帧
+----------------------+
| 返回地址 | <--- [!] hello 函数的 CFA 指向这里
+----------------------+------ hello 函数栈帧的“边界”
| 保存的 RBP (帧指针) | <--- 帧基址 (Frame Base) 常常指向这里
+----------------------+
| hello 的局部变量 |
| ... |
| 可能还有保存的寄存器 |
+----------------------+ <--- 当前 RSP 指向这里(栈顶)
(低地址)

在我们的示例中,DWARF信息指出DW_AT_frame_base : DW_OP_call_frame_cfa,所以这里我们的栈基址等于CFA值。基于栈基址,我们就可以对被调用栈帧中的变量进行访问。我们看到DW_AT_location的属性下,通常有DW_OP_fbreg - 偏移值的形式来计算参数在栈帧上的位置。

DWARF不定义函数的调用约定,这一部分有应用程序二进制接口规范确定(ABI)

编译单元

大多数的程序室友多个文件构成的,每个文件会被独立编译,然后与系统库链接成最终的程序,DWARF将每个独立编译的源文件称为一个编译单元

每个编译单元的DWARF数据,都会从一个编译单元调试信息项开始。该调试信息项包含编译过程中的通用信息

1
2
3
4
5
6
7
8
< 0><0x0000000c>  DW_TAG_compile_unit
DW_AT_producer GNU C17 13.3.0 -mtune=generic -march=x86-64 -g -O0 -fasynchronous-unwind-tables -fstack-protector-strong -fstack-clash-protection -fcf-protection
DW_AT_language DW_LANG_C11
DW_AT_name test.c
DW_AT_comp_dir /home/ylin/Program/test
DW_AT_low_pc 0x00001129
DW_AT_high_pc <offset-from-lowpc> 61 <highpc: 0x00001166>
DW_AT_stmt_list 0x00000000

包括:

  • 编译器和编译参数
  • 源文件的目录路径和文件名称
  • 编译单元在内存中的起始结束地址(如果编译单元在内存中是连续的)
  • 编译单元占用内存的地址列表(如果编译单元在内存中非连续)
  • 指向调试器行号的指针(DW_AT_stmt_list)

编译单元调试信息项是所有该编译单元调试信息的父项。一般情况下,调试信息会先描述数据类型,接着是全局数据,然后再是子函数。

至此基本的DWARF信息就介绍到这里。

也是好不容易水到第100篇了,我本来准备了好多台词的,但是不知道说什么。我就记录一下我的几个感悟吧

学会放弃

刚开始觉得只要努力学就会有所收获吧,如果没学会就是自己比较笨什么的。但事实不是这样的,认知一个领域的过程是循序渐进的,就像游戏里的科技树一样,解锁一个科技需要一大堆前置科技。有时候一些知识也是这样,所以一开始学不会一些东西很正常,这个时候应该先放一放,去试试其他的方向,或者是从前置的内容开始学。

关于这一点我的感受就很明显吧,我每次遇到学不会的东西,就会放弃然后去学其他的东西。但是过一段时间之后再来看这些内容反而有一种水到渠成的感觉,我猜测一个是知识体系上的补齐,还有一个是你对这个领域的认知能力也在慢慢变强。你能对一些内容做出自己的解释,能说服自己我认为是理解一个知识的开始吧。不管你的猜想是不是对的,只要他能补齐你对这方面的认识,你就可以视作自己理解了。之后随着需求和认知的提升,再一步步完善自己对这方面的理解吧。

我发现生活中也有很多这样的事情,给你一种无从下手或者无能为力的感觉。如果实在不行就放弃吧,可以之后再试试,先把其他的事情做好,也许很多事情时间会给出答案,因为我们每天都在慢慢长大。只要不放弃从头再来的决心,迟早有一天也能找到自己的答案。

主动学习

大家都在学习凭什么,也不存在谁比谁笨,为什么有的人能学会有的人不能呢?我认为这不是努不努力的事情,大家回宿舍都是打游戏,如果能认真学下去,活该他学的好。我觉得更多是对于这个知识的态度吧,有的人是被动的接受的,有的人是主动的接受的。主动接受的话你就会发现很多问题啥的,就是你的脑子里的东西和答案不一样,或者你脑子里没有这个东西。在这个不断碰撞思考的过程中,你的知识体系会被答案说服或者补全,这样你的认知体系就会慢慢完善,感觉这个就是高中老师说的框架/查漏补缺,这个就是主动学习。但是大多数人就是书上讲得是啥就是啥,老师说啥就是啥,一上来就记住正确答案,对知识很内容知其然不知其所以然,这种效率就很差。中国传统的应试教育就是这样的,所以大家都是这样的,我也是这样的。

这也是为什么比起看网课我更喜欢看书,看网课的时候,老师叽里咕噜讲个不停,你很难有自己思考的时间,更别说有时候发呆什么的。但是看书不一样,你不懂得时候可以对着书上得那句话发呆,等你发完呆它还在那里,你就有充分得时间去理解它,或者再来一遍。就是这个时候你的大脑是属于你自己的,你的想法不是跟着别人走的,更自由一点。这样你就能做出更多自己的思考。

我知道这样子很不好,但是有时候动脑子真的好累,偶尔主动学习一些重要的东西也还行。我的话有时候突然想做项目或者刷视频看到什么好帅的东西,我会迫不及待的去了解一下。主要是对游戏方面感兴趣一点

要有耐心

就是电视上和老师经常说的要坐的住冷板凳吧,有时候学一些东西确实挺牢的,就是很无聊,知识从脑袋里滑走了。这个时候就是看你有没有耐心了,感觉这个和我第一条说的是相反的,按道理这种情况是要放弃的,但是有时候就是不太想放弃,你就需要耐心一点。所以这么看来放弃是一件很理性的事情,坚持反而是一件很感性的事情。回到正题,我想说的是,人生的常态就是失败和无聊,但是不耐心去做一件事的话就会错过很多东西。什么时候放弃,什么时候坚持是一件很哲学的问题吧。我到这里也不知道说什么好了。

今天就暂时写到这些吧,希望之后的时间也能继续加油。现在虽然学了很多东西,但是没办法把知识串联在一起,也有点迷茫。有时候分析一些问题的时候,反而会因为知道的太多而被绕进去。就像之前不知道从哪里看到的三大境界:

  • 看山是山 看水是水
  • 看山不是山 看水不是水
  • 看山还是山 看水还是水

我现在可能介于一二之间吧,很难受,技术不到家,看很多东西都是残破不堪的,漏洞百出,我自己也知道。希望以后能慢慢解决这个这个问题吧。还有就是我现在也遇到了一些生活中难以解决的问题,我也不知道怎么做,在迷茫的时候还是要坚定的提升自己,也许以后时间会给出答案吧。之后也要继续加油。

今天接着来认识一下图,结束了图的学习,数据结构的部分就告一段落了。之后就是涉及到一些基本的算法问题,感觉也会越来越难。

认识图

和之前的数据结构不同,图是一种非线性的结构,由顶点和边组成,以下面为例,我们可以将图G抽象的表示成一组顶点和一组边的集合:

1
2
3
V = {1,2,3,4,5}
E = {(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(4,5)}
G = {V,E}

如果将顶点看作节点,将边看作连接各个节点的引用(指针),我们就可以将图看作一种从链表拓展而来的数 据结构。

image.png

图的常见类型和术语

结合不同的场景,我们可以从不同的角度对图进行分类:

  • 根据边是否具有方向,分为有向图和无向图
  • 根据顶点直接是否全部联通,分为联通图和非联通图
  • 根据边上的权重,非为无权图和有权图
  • ….

在不同的场景中我们选择合适的类型,来解决问题。

图的数据结构有以下常用术语:

  • 邻接:当两顶点之间存在边相连时,称这两个顶点邻接
  • 路径:从顶点A到顶点B经过的边构成的序列被称为从A到B的路径
  • 度:一个顶点拥有的边数。对有向图,根据边的方向,还分为入度和出度。

图的表示

图通常使用两种表示方式,我们这里均以无向图为例:

邻接矩阵

设图的顶点数量为𝑛,邻接矩阵使用一个n×n大小的矩阵来表示图,每一行(列)代 表一个顶点,矩阵元素代表边,用1或0表示两个顶点之间是否存在边。

设邻接矩阵为𝑀、顶点列表为𝑉 ,那么矩阵元素𝑀[𝑖,𝑗]=1表示顶点𝑉[𝑖]到顶点𝑉[𝑗] 之间存在边,反之𝑀[𝑖,𝑗]=0表示两顶点之间无边。

image.png

邻接矩阵有以下性质:

  • 在简单图中,顶点不能和自己相连,所以邻接矩阵主对角线上的元素是没有意义的
  • 对于无向图,两个方向的边等价,此时邻接矩阵关于主对角线对称
  • 将邻接矩阵的元素替换成权重就是有权图

邻接表

邻接表使用n个链表来表示图,链表节点表示顶点。第i个链表对应顶点i,其中存储了该顶点的所有邻接顶点(与该顶点相连的顶点)。如下图:

image.png

两种表示方法的比较

对于邻接矩阵,我们可以直接访问矩阵元素实现对边的CRUD,时间效率高达O(1)。但是矩阵存储的空间复杂度为O(n2)

对于邻接表,由于表中只存储实际已存在的边数,而边数通常小于n2,所以空间存储的效率上来看,邻接表要更加的节省空间。但是对于CRUD的操作,邻接表需要通过遍历搜索的方式来进行,所以时间效率更差。

但是结合先前的只是,对于这种链表较长的情况,我们可以将它优化成哈希表或者AVL树等结构,实现对时间效率的优化,所以对于大规模的图的使用场景,邻接表也更加普遍。

图的基本操作

图的操作主要可以分为对顶点和对边的操作,这里分别通过邻接矩阵和邻接表的方式进行实现。

基于邻接矩阵的实现

给定给一个顶点数量为n的无向图,我们需要完成以下操作:

  • 添加或删除边:直接在邻接矩阵修改指定的边,只不过要注意同时更新两个方向的边(无向图)
  • 添加顶点:在邻接矩阵的尾部添加一行一列,并初始化为0即可。
  • 删除顶点:在邻接举证中删除一行一列,将剩下的元素向左上补齐。对于最坏的情况(删除首行首列)需要移动(n − 1)2个元素
  • 初始化:传入n个顶点,初始化长度为n的顶点列表和nxn大小的邻接矩阵
image.png

我们的具体实现如下:

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
class GraphMap{
private:
vector<int> vertices; // 顶点列表
vector<vector<int>> adjMat; // 邻接矩阵

public:
GraphMap(const vector<int> &vertices, const vector<vector<int>> &edges){
for(int val : vertices)
addVertex(val);
for(const vector<int> &edge : edges)
addEdge(edge[0],edge[1]);
}

int size() const{
return vertices.size();
}

void addVertex(int val){
int n = size();
vertices.push_back(val);
// 向邻接矩阵中添加一行
adjMat.emplace_back(vector<int>(n,0));
for(vector<int> &row: adjMat)
row.push_back(0);
}

void removeVertex(int index){
if(index >= size())
throw out_of_range("顶点不存在");
vertices.erase(vertices.begin() + index);
// 删除行
adjMat.erase(adjMat.begin() + index);
// 删除列
for(vector<int> &row : adjMat)
row.erase(row.begin() + index);
}

void addEdge(int i,int j){
if(i<0 || i>=size() || j<0 || j>=size() || i==j)
throw out_of_range("顶点不存在");
adjMat[i][j] = 1;
adjMat[j][i] = 1;
}

void removeEdge(int i,int j){
if(i<0 || i>=size() || j<0 || j>=size() || i==j)
throw out_of_range("顶点不存在");
adjMat[i][j] = 0;
adjMat[j][i] = 0;
}
};

基于邻接表的实现

设无向图的顶点总数为n、边总数为m,我们需要完成以下操作:

  • 添加边:在顶点对应链表的末尾添加边就行了。但是要注意无向图要加两个方向的边
  • 删除边:在顶点管理的链表中查找并删除指定的边。无向图中删两个方向。
  • 添加顶点:在邻接表中添加一个链表,并将新增顶点作为链表头节点
  • 删除顶点:遍历整个邻接表,删除包含指定顶点的所有边
  • 初始化:在邻接表中创建n个顶点和2m条边
image.png

以下是邻接表的代码实现:

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
class GraphList{
private:
unordered_map<Vertex* ,vector<Vertex*>> adjList;

void remove(vector<Vertex*> &vec, Vertex* vet){
for(int i=0;i<vec.size();i++){
if(vec[i]==vet){
vec.erase(vec.begin()+i);
break;
}
}
}

public:
GraphList(const vector<vector<Vertex*>> &edges){
for(const vector<Vertex *> & edge: edges){
addVertex(edge[0]);
addVertex(edge[1]);
addEdge(edge[0],edge[1]);
}
}

int size(){
return adjList.size();
}

void addVertex(Vertex* vet){
if(adjList.count(vet))
return;
adjList[vet] = vector<Vertex*>();
}

void removeVertex(Vertex* vet){
if(!adjList.count(vet))
throw invalid_argument("不存在顶点");
adjList.erase(vet);
for(auto &adj : adjList)
remove(adj.second,vet);
}

void addEdge(Vertex* vet1, Vertex* vet2){
if(!adjList.count(vet1) || !adjList.count(vet2) || vet1==vet2)
throw invalid_argument("不存在顶点");
adjList[vet1].push_back(vet2);
adjList[vet2].push_back(vet1);
}

void removeEdge(Vertex* vet1, Vertex* vet2){
if(!adjList.count(vet1) || !adjList.count(vet2) || vet1==vet2)
throw invalid_argument("不存在顶点");
remove(adjList[vet1],vet2);
remove(adjList[vet2],vet1);
}
};

这里为了方便,我们使用动态数组代替了链表。用哈希表来表示邻接表结构。

同时需要注意在邻接表中我们使用Vertex类来表示顶点,也是为了方便。如果我们使用列表索引来区分不同德顶点的话,那么每当我们删除一个索引为i的顶点,就需要遍历整个邻接表,把所有索引大于i的顶点重新更新一遍,这样的话效率就很差。

图的遍历

树代表的是一对多的关系,图代表的是多对多的关系,所以我们可以将树视作图的一个特例。所以说树的遍历操作实际上也是图的遍历操作的一种特例。

和树类似的,我们有两种遍历方式实现对图的遍历操作:广度优先遍历和深度优先遍历

广度优先遍历

广度优先遍历是一种由近及远的遍历方式,从某个节点出发,始终优先访问距离最近的顶点,并一层层向外 扩张。以下图为例:

image.png

从左上角顶点出发,首先遍历该顶点的所有邻接顶点,然后遍历下一个顶点的所有邻 接顶点,以此类推,直至所有顶点访问完毕。

算法实现

BFS通常需要一个辅助队列来实现,通过队列先进先出的性质,实现BFS由近及远的思路。我们的实现流程如下:

  • 将遍历起始顶点startVet加入队列中,开始循环
  • 在每次迭代中,弹出队首顶点并访问,将该顶点的所有邻接点加入到队列尾部
  • 循环上一步,知道队列为空

同时我们还需要一个哈希集合visited来记录哪些节点被访问,以防止重复遍历顶点。

我们的具体实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<Vertex*> graphBFS(GraphList &graph, Vertex* startVet){
vector<Vertex*> res; // 返回的顶点序列
unordered_set<Vertex*> visited; // 哈希集合,用来记录被访问过的顶点
queue<Vertex*> que; // 辅助队列
que.push(startVet);
while(!que.empty()){
Vertex* vet = que.front();
que.pop();
res.push_back(vet);
for(auto adjVet : graph.adjList[vet]){
if(visited.count(adjVet))
continue; // 跳过已访问的顶点
que.push(adjVet);
visited.emplace(adjVet);
}
}
return res;
}

可以通过画图的方法帮助理解一下这个过程

深度优先遍历

深度优先遍历是一种优先走到底、无路可走再回头的遍历方式。以下图为例

image.png

算法实现

这种走到尽头并返回的样式,我们可以通过递归的方式实现。关键在于怎么设置边界条件,退出递归。我们的实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void dfs(GraphList &graph, unordered_set<Vertex*> &visited,
vector<Vertex*> &res, Vertex * vet){
// 记录访问节点
res.push_back(vet);
// 标记已访问节点
visited.emplace(vet);
// 遍历所有邻接顶点
for(Vertex* adjVet : graph.adjList[vet]){
if(visited.count(adjVet))
continue;
// 递归访问邻接顶点
dfs(graph,visited,res,adjVet);
}
}

vector<Vertex*> graphDFS(GraphList &graph, Vertex* startVet){
// 顶点遍历序列
vector<Vertex*> res;
// 以访问过的顶点
unordered_set<Vertex*> visited;
dfs(graph,visited,res,startVet);
return res;
}

可以自己尝试手推一下这个过程,加深理解。

学一种新的数据结构——“堆”,但是貌似和底层原理中的堆并不一样。之前总是略有耳闻,但是一直都很少仔细去了解。

堆是一种满足特定条件的完全二叉树,根据性质可以分为两种类型:

  • 小顶堆:任意节点的值 <= 子节点的值
  • 大顶堆:任意节点的值 >= 子节点的值
image.png

堆作为完全二叉树的一个特例,有以下规则:

  • 最底层的节点靠左排列,其他层被节点填满。
  • 二叉树的根节点被称为堆顶,二叉树底层靠右的节点称为堆底
  • 对于大(小)顶堆,堆顶元素的值是最大(小)的

堆的常用操作

有一种抽象的数据结构——优先队列,定义为具有优先级排序的队列。通常我们会使用堆来实现优先队列,大顶堆就相当于元素按大到小的顺序出队的优先队列。这里我们将其视作等价的数据结构。

这里我们先通过优先队列来认识一下堆的一些操作:

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
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main(){
priority_queue<int, vector<int>, greater<int>> minheap;
priority_queue<int, vector<int>, less<int>> maxheap;

maxheap.push(1);
maxheap.push(5);
maxheap.push(4);
maxheap.push(2);
maxheap.push(2);
maxheap.push(3);

cout << "The size is " << maxheap.size() << endl;
int top = maxheap.top();
cout << "The top is " << top << endl;

bool isEmpty = maxheap.empty();

return 0;
}

常用的可以总结为以下几类:

image.png

堆的实现

现在我们尝试从底层实现一个堆,这里我们用大顶堆演示,小顶堆只需要将所有的大小逻辑判断反转即可。

堆的存储和表示

堆是一种完全二叉树,我们之前提到过完全二叉树十分适合用数组来进行存储,所以这里我们的底层实现选择用数组,和之前的实现一样。我们使用索引的映射公式来代替节点指针:

1
2
3
4
5
6
7
8
9
10
11
int left(int i){
return 2*i+1;
}

int right(int i){
return 2*i+2;
}

int parent(int i){
return (i-1)/2;
}

访问堆顶元素

堆顶元素就是二叉树的根节点,也就是我们数组的首元素:

1
2
3
4
5
6
7
8
9
10
class Heap{
public:
...
int peek(){
return heap[0];
}
...
private:
vector<int> heap;
};

元素入堆

给定val,我们将其添加到堆底。但是此时插入的值可能会破坏当前到根节点的路径,导致堆的成立条件被破坏。所以我们需要遍历修复从插入节点到根节点路径上的所有节点,这个过程我们称之为堆化

从入堆节点开始,我们从底执行堆化。我们依次比较当前节点和父节点的大小,如果插入节点更大就讲他们交换,知道修复所有的节点关系。

image.png

我们可以通过以下方式实现这个过程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
      void push(int i){
heap.push_back(i);
// 从堆底开始堆化
siftUp(heap.size()-1);
}

// 堆化
void siftUp(int i){
while(true){
int p = parent(i);
if(p<0 || heap[i] <= heap[p])
break;

swap(heap[i],heap[p]);
// 向上堆化
i=p;
}
}

堆顶元素出栈

堆顶元素是二叉树的根节点,如果我们直接从数组中删除首元素,那么会破坏整个树的树状结构,这导致后续的堆化难以修复。所以我们采取以下步骤将堆顶元素出栈:

  • 交换堆顶元素(根节点)和堆底元素(最右元素)
  • 交换完成之后,我们将堆底删除
  • 从根节点开始自顶向底执行堆化

自顶向下的堆化和自底向上的堆化逻辑相反,我们将当前节点和较大的子节点进行比较,然后进行交换,直到没有子节点或者无需再交换了:

image.png

出堆的实现方式如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void pop(int i){
if(heap.empty())
throw out_of_range("堆为空");
swap(heap[i], heap[heap.size()-1]);
heap.pop_back();
siftDown(0);
}

void siftDown(int i){
while(true){
// ma为较大的节点
int l=left(i), r=right(i), ma = i;
if(l < heap.size() && heap[i] < heap[l])
ma = l;
if(r < heap.size() && heap[i] < heap[r])
ma = r;
// l,r越界或者i已经是最大节点 则退出堆化
if(ma==i)
break;
swap(heap[i],heap[ma]);
i = ma;
}
}

建堆操作

我们希望能直接根据一个列表中的所有元素来构建一个堆。我们有两种可行的方案:

  • 创建一个空堆,然后遍历列表,对每一个元素都进行入堆操作。但是对于n个元素执行复杂度为O(logn)的入堆操作,时间复杂度会增长到O(nlogn)
  • 另一个方法就是,将列表中的元素添加到完全二叉树中,尽管现在的堆的性质并没有被满足。接下来我们倒序遍历堆,并对每个非叶节点进行一次自顶向下的堆化。这样每当我们堆化一个节点之后,都会以该节点为根节点形成一个子堆。

这里我们着重分析一下第二种方法。我们可以通过以下方法实现:

1
2
3
4
5
6
Heap(vector<int> vec){
heap = vec;
// 倒序遍历的第一个非叶节点 就是最后一个叶节点的父节点
for(int i=parent(heap.size()-1); i>=0; i--)
siftDown(i);
}

这个方法下的复杂度被优化到了O(n),更加的便捷。

Top-k问题

所谓top-k问题,就是给定一个长度为n的无序数组nums,请返回数组中最大的k个元素。

对于这个问题我们有很多种解决方案:

遍历选择

我们可以像这样对一个长度为n的序列进行k次遍历,每轮遍历都提取出当前序列中的最大的数据。时间复杂度为O(nk)。当k接近n时,时间复杂度增长到O(n^2)

image.png

排序

先对数组nums进行排序,然后再返回最右边的k个数据。这个方法主要取决于对数组排序的时间复杂度,对于std::sort,这个方法的复杂度是O(nlogn)

我们可以基于堆更加高效的完成这个任务,我们遵循以下步骤实现:

  • 初始化一个小顶堆,此时其堆顶元素最小。
  • 然后将数组的前k个元素依次入堆
  • 从第k+1个元素开始,如果当前元素大于堆顶元素,我们就将堆顶出堆,并将当前元素入堆。
  • 遍历完成之后,堆中保存的就是最大的k个元素。

我们可以写出以下代码:

1
2
3
4
5
6
7
8
9
10
11
12
priority_queue<int, vector<int>, greater<int>> topHeap(vector<int> nums, int k){
priority_queue<int, vector<int>, greater<int>> heap;
for(int i=0;i<k;i++)
heap.push(nums[i]);
for(int i=k;i<nums.size();i++){
if(heap.top() < nums[i]){
heap.pop();
heap.push(nums[i]);
}
}
return heap;
}

总共进行了n轮入堆和出堆,由于堆大小是固定的k,所以我们只需要维护k个元素,所以实际上我们的计算复杂度只有O(nlogk),在k较小时,我们的时间复杂度约等于O(n)

由此可以看到通过堆的思路,对解决TopK问题的显著提升。尤其是对于这种方法,适用于动态数据流的使用场景。在不断加入数据时,我们可以持续维护堆内的元素,从而实现 最大的𝑘个元素的动态更新。

书接上回,接着研究一下AVL树。

AVL树

在二叉搜索树中,我们可以知道,在多次的插入和删除之后,二叉树的左右可能会失去平衡,从而导致退化成链表,在这样的情况下我们的算法的效率会从O(logn)退化到O(n)

image.png
image.png

但是我们接下来将要提到的AVL树,将解决这些问题

AVL树的常见术语

AVL树本质是二叉搜索树和二叉平衡树的结合,所以同时满足这两种树的性质:

  1. 节点高度

“节点高度”是指从该节点到它的最远叶节点的距离,即所经过的“边”的数量。这里我们让叶子节点的高度为0,把空节点的高度设置为-1。我们将根据这些性质来编写我们的数据结构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct TreeNode{
int val{};
int height = 0;
TreeNode* left{};
TreeNode* right{};
TreeNode() = default;
explicit TreeNode(int x): val(x) {}
};

// 获取高度
int height(TreeNode* node){
return node == nullptr ? -1 : node->height;
}

// 更新节点高度
void updateHeight(TreeNode* node){
// 当前节点的高度 = 最高子树高度 + 1
node->height = max(height(node->left),height(node->right)) + 1;
}
  1. 节点的平衡因子

节点的平衡因子定义为节点左子树的高度减去右子树的高度,同时规定空节点的平衡因子为0。对于AVL树,我们要求树中任意节点的平衡因子-1<=f<=1,否则这个树就进入了失衡状态。我们可以写出以下函数:

1
2
3
int balance(TreeNode* node){
return node == nullptr ? 0 : height(node->left) - height(node->right);
}

AVL树的旋转

AVL树的精髓就在于旋转操作,当我们的树中存在失衡节点时,我们可以通过“旋转”操作,在不影响中序遍历序列的前提下,使失衡的节点重新回到平衡的状态。

我们将|平衡因子| > 1的节点称为失衡节点,根据不同的失衡情况,我们有四种旋转操作:

右旋

image.png

结合这张图来看,从底至顶看,二叉树中首个失衡节点是“节点3”。我们关注以该失衡 节点为根节点的子树,将该节点记为 node ,其左子节点记为 child ,执行“右旋”操作。完成右旋后,子树 恢复平衡,并且仍然保持二叉搜索树的性质。

但是对于,当节点child有右节点(记作grand_child)的情况下,我们需在右旋中添加一步:将grand_child设置为node的左子节点。

image.png

我们可以通过修改节点指针的方法来实现:

1
2
3
4
5
6
7
8
9
10
11
TreeNode* rightRotate(TreeNode* node){
TreeNode* child = node->left;
TreeNode* grandChild = child->right;
child->right = node;
// 当grandChild为null时无影响
node->left = grandChild;
updateHeight(child);
updateHeight(node);
// 右旋后child作为左子树的根节点
return child;
}

左旋

左旋作为右旋的镜像版本,对应右节点失衡的情况,同样是下面的两种情况:

image.png
image.png

我们可以写出:

1
2
3
4
5
6
7
8
9
TreeNode* leftRotate(TreeNode* node){
TreeNode* child = node->right;
TreeNode* grandChild = child->left;
child->left = node;
node->right = grandChild;
updateHeight(child);
updateHeight(node);
return child;
}

先左旋后右旋

对于下面这种情况,我们需要先对child进行左旋,再对node进行右旋:

image.png

先右旋后左旋

这种情况依旧是上一种情况的镜像对称情况:

image.png

旋转的选择

讲完了四种旋转的操作,现在我们需要分析,在什么情况下需要对我们的树进行哪些操作了,这里的话我推荐看一个视频:平衡二叉树(AVL树)_哔哩哔哩_bilibili

我们的步骤总结如下:

  • 先检查失衡节点的子节点child的平衡因子,大于0则需要进行右旋操作,小于0则需要进行左旋操作。
  • 然后检查失衡节点node的平衡因子,大于1则需要进行右旋操作,小于1则需要左旋操作。
  • 最后比较对子节点chlid和失衡节点node的需要进行的操作,如果相同则合并,不同则先操作子节点后操作失衡节点。

我们也可以用一张表来进行这个判断:

image.png

现在我们可以写出AVL树的平衡函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
TreeNode* rotate(TreeNode* node){
int _balanceFactor = balance(node);
TreeNode* child = node->left;
if(_balanceFactor > 1){
// 右旋
if(balance(child)<-1)
// 先左旋
child = leftRotate(child);
return rightRotate(node);
}else if(_balanceFactor < -1){
// 左旋
if(balance(child)>1)
// 先右旋
child = rightRotate(child);
return leftRotate(node);
}else{
// 平衡
return node;
}
}

AVL树的常用操作

  1. 插入节点

AVL树的节点插入操作和二叉搜索树一样,只不过在AVL树插入节点之后,从这个节点到根节点的路径上可能会出现一系列的失衡节点。所以我们需要从这个节点开始,自底向上的执行平衡操作,知道所有的失衡节点都恢复平衡。我们的实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
TreeNode* _insert(TreeNode* node, int num){
if(node==nullptr)
return new TreeNode(num);
if(num < node->val)
node->left = _insert(node->left,num);
else if(num > node->val)
node->right = _insert(node->right,num);
else
return node;

updateHeight(node);
return rotate(node);
}
  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
TreeNode* _remove(TreeNode* node, int num){
if(node==nullptr)
return nullptr;
if(num < node->val)
node->left = _remove(node->left,num);
else if(num > node->val)
node->right =_remove(node->right,num);
else{
if(node->left==nullptr||node->right==nullptr){
TreeNode* child = node->left==nullptr ? node->right : node->left;
delete node;
return child;
}else{
TreeNode* tmp = node->right;
while(tmp->left !=nullptr)
tmp = tmp->left;
int val = tmp->val;
node->right = _remove(node->right,tmp->val);
node->val = val;
}
}
updateHeight(node);
return rotate(node);
}
  1. 查找操作

和二叉搜索树一样,没有变化

十一月份已经过去了一半。回顾这个月我都做了什么,做到了什么呢?仔细一想是没有的,感觉时间过的好快,转眼间就过去了大半个学期,自己也是没什么收获,定下的很多目标都没有做到。

马上就要期中考试了,我希望能在各科都拿到一个比较好的成绩吧,因为这个学期对我的绩点来说是十分重要的。所以一定要好好加油,尤其是408相关的课程,一定要好好学,不能只是满足于书上的内容,不仅要掌握概念,也要会做题。要做好考研的准备吧,因为推免资格对我而言还是有点困难的,所以一定要好好加油。

这个月接触到了各种语言吧,学的很杂,接触到了Lua和他的游戏开发引擎,我之前说过想做一个游戏,但是思路上仍然是一头雾水,做一个什么样的游戏呢,要做哪些内容呢?我一点idea也没有,所以只能慢慢积累了,还有一些游戏开发相关的技术。所以我选择去了解一下星露谷物语的mod制作,它是用C#进行编写的,语法结构和Java差不多,所以我勉强能看懂一些,但是对于整个项目结构一点也不够了解。

我发现自己总是半途而废,我经常会突然想做什么,但是没办法一直做下去,我感觉要做的事情太多了,我不知道该怎么安排过来,所以也比较晕头转向的。接下来的一个月里,我打算好好夯实一下课内的知识吧,比如操作系统和数据结构,目前学习的过程中也明显感受到了清晰的需求。争取在这个学期把王道的课程也看掉一部分,感觉他讲的还是十分详细的。然后是概率论和离散数学,我也打算好好学一下了,每天坚持做一点题目,因为到现在为止,我对这两门科目都是不太了解。

还有的就是密码学 信息安全基础 程序设计一类的课程了,要想办法把平时分搞高一点,争取一下满绩吧。拉一拉我上上个学期拖得后腿。我发现密码学的很多知识还是比较有用的,因为会涉及到一些简单的数论和密码学体制。我以前总是抗拒听老师的课,但是其实我自己也不知道要做什么,何妨不听一听呢。

然后感觉最近心态好了很多吧,平时不会想那么多了。以后有空的话我也想试试出去旅游,然后玩一点剧情类的游戏。有空的话想拍一点游戏视频。尝试各种各样的事情。我想自己的人生开阔一点,可是我总是半途而废,总是做不到,但是既然有这样的想法就试一试吧。希望未来会越来越好,有很多开心的事在等着我。

我也想坚持锻炼身体,希望能健健康康的

打算系统性的学一下数据结构与算法,这个就相当于笔记做一下记录了。 # 树

二叉树

二叉树的基本单元是节点,每个节点包含值、左子节点引用和右子节点引用。我们可以用以下数据结构表示:

1
2
3
4
5
6
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};

这里每个节点都有两个引用,分别为左右子节点,中间的节点为这两个节点的父节点。左右子树的概念也可以类推。在二叉树中,除叶节点外,其他所有节点都包含子节点和非空子树。

二叉树常用的术语

二叉树中的性质较为复杂,所以我们需要记住许多相关的术语:

  • 根节点:位于二叉树顶层的节点,没有父节点。
  • 叶节点:没有子节点的节点,其两个指针均指向 None
  • 边:连接两个节点的线段,即节点引用(指针)
  • 节点所在的层:从顶至底递增,根节点所在层为1。
  • 节点的度:节点的子节点的数量。在二叉树中,度的取值范围是0、1、2。
  • 二叉树的高度:从根节点到最远叶节点所经过的边的数量
  • 节点的深度:从根节点到该节点所经过的边的数量。
  • 节点的高度:从距离该节点最远的叶节点到该节点所经过的边的数量。
image.png

二叉树的基本操作

  1. 初始化二叉树

​ 初始化节点,并构造引用:

1
2
3
4
5
6
7
8
9
10
11
12
int main(){
TreeNode* n1 = new TreeNode(1);
TreeNode* n2 = new TreeNode(2);
TreeNode* n3 = new TreeNode(3);
TreeNode* n4 = new TreeNode(4);
TreeNode* n5 = new TreeNode(5);

n1->left = n2;
n1->right = n3;
n2->left = n4;
n2->right = n5;
}
  1. 插入与删除节点

​ 二叉树中的插入与删除节点可以通过修改指针实现,效果见下图:

image.png

二叉树的类型

完美二叉树

完美二叉树的所有层的节点都被完全填满。且在完美二叉树中,叶节点的度为0,其余所有节点的度都为2;若树的高度为ℎ,则节点总数为2ℎ+1−1,呈现标准的指数级关系:

image.png

关于完美二叉树,我们需要注意到它的几个性质:

  • 第i层的节点数量: 2i − 1
  • 高度为h的树的叶节点数量:2h
  • 高度为h的树的节点总数: 2h + 1 − 1
  • 节点总数为n的树的高度:log2(n + 1) − 1

完全二叉树

完全二叉树只有最底层的节点未被填满,且最底层的节点尽量靠左边。

注:完美二叉树是一种特殊的完全二叉树

image.png

完满二叉树

完满二叉树除了叶子节点之外,其余所有节点都有两个子节点:

image.png

平衡二叉树

平衡二叉树中的任意节点的左子树和右子树的高度之差的绝对值不超过1,|左子树高度-右子树高度|<=1

image.png

二叉树遍历

常见的二叉树遍历有:层序遍历、前序遍历、中序遍历和后序遍历

层序遍历

层序遍历是从顶部到底部逐层遍历二叉树,并在每一层按照从左到右的顺序访问节点。这种遍历方式本质上属于广度优先遍历,我们也称之为广度优先搜索:

image.png

其代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> BFS(TreeNode* root){
queue<TreeNode*> q; // 用于存放遍历序列
q.push(root);
vector<int> vec;
while(!q.empty()){
TreeNode* node = q.front();
q.pop(); // 将需要处理的节点出列
vec.push_back(node->val);
if(node->left!=nullptr)
q.push(node->left);
if(node->right!=nullptr)
q.push(node->right);
}
return vec;
}

前中后序遍历

相应的这种遍历方式实际上是一种深度优先的遍历,我们称之为深度有限的搜索。这里我们有三种不同的遍历顺序,我们可以通过简单的递归来实现,具体实现如下。就不做过多的说明,因为很直观:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 前序
void preOrder(TreeNode* root){
if(root==nullptr)
return;
cout << root->val << endl;
preOrder(root->left);
preOrder(root->right);
}
// 中序
void inOrder(TreeNode* root){
if(root==nullptr)
return;
inOrder(root->left);
cout << root->val << endl;
inOrder(root->right);
}
// 后序
void pastOrder(TreeNode* root){
if(root==nullptr)
return;
pastOrder(root->left);
pastOrder(root->right);
cout << root->val << endl;
}

二叉树的数组表示

我们先前对二叉树的实现是通过链表进行实现的,节点之间则通过指针连接。但是实际上我们也可以通过数组实现二叉树的结构。

表示完美二叉树

对于一颗完美二叉树,我们可以将所有的节点按照层序遍历的顺序存储一个数组中,则每个节点都对应唯一的数组索引,根据层序遍历的特性,我们也可以推导出父子节点之间的索引关系:

若某节点的索引为𝑖, 则该节点的左子节点索引为2𝑖+1,右子节点索引为2𝑖+2

这里的映射关系就相当于先前的指针,我们只需要知道当前的索引,就能找到其对应的左右节点

image.png

表示任意二叉树

完美二叉树是一个特例,在实际情况中,我们的二叉树中间层有很多None,如果层序遍历不包含这些None,那么我们就无法根据一个数组来还原二叉树的形态:

image.png

所以我们尝试在层序遍历的序列中显式的写出所有的None:

image.png

就可以清晰的表示一个二叉树的结构。当然需要注意的是,完全二叉树十分适合用数组来表示,我们知道其None只会出现在最底层的右边,一定出现在层序遍历序列的末尾。这意味着当我们对完全二叉树进行存储时,我们可以忽略所有的None

二叉树的数组实现

现在我们尝试用数组实现二叉树的结构,我们需要支持以下操作:

  • 给定某节点,获取其值、左右子节点、父节点
  • 获取前序、中序、后序遍历、层序遍历序列
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
#include <vector>
#include <iostream>

using namespace std;

class ArrayBinaryTree{
public:
ArrayBinaryTree(vector<int> arr){
tree = arr;
}

int size(){
return tree.size();
}

int val(int i){
if(i<0 || i>=size())
return -1;
return tree[i];
}

int left(int i){
return 2*i+1;
}

int right(int i){
return 2*i+2;
}

int parent(int i){
return (i-1)/2;
}

vector<int> BFS(){
vector<int> res;
for(int i=0;i<size();i++)
if(val(i)!=-1)
res.push_back(val(i));
return res;
}

void preOrder(int index){
if(val(index)==-1)
return;
cout << val(index) << endl;
preOrder(left(index));
preOrder(right(index));
}

void inOrder(int index){
if(val(index)==-1)
return;
inOrder(left(index));
cout << val(index) << endl;
inOrder(right(index));
}

void pastOrder(int index){
if(val(index)==-1)
return;
pastOrder(left(index));
pastOrder(right(index));
cout << val(index) << endl;
}

private:
vector<int> tree;
};

二叉搜索树

如下图所示,二叉搜索树需要满足以下条件:

  • 对于根节点,左子树中所有节点的值 < 根节点的值 < 右子树所有节点的值
  • 任意节点的左右子树也时二叉搜索树,满足上一个条件
image.png

二叉搜索树的操作

我们将二叉搜索树封装为一个类BinarySerchTree,并声明一个成员变量root,指向树的节点。

  1. 查找节点

给定一个目标节点值num,我们可以很快的根据二叉搜索树的性质来查找,我们可以声明一个节点cur,从二叉树的根节点root出发,循环比较值,知道找到对应的节点。

二叉搜索树的查找操作实际上和二分查找差不多,循环次数最多为树的高度:

1
2
3
4
5
6
7
8
9
10
11
12
TreeNode* search(int num){
TreeNode* cur = root;
while(cur != nullptr){
if(cur->val < num)
cur = cur->right;
else if(cur->val > num)
cur = cur->left;
else
break;
}
return cur;
}
  1. 插入节点

给定一个等待插入的元素num,为了保持二叉树的性质,我们进行以下步骤:

  • 查找插入位置:和查找操作相似,从根节点出出发,直到越过叶节点时退出循环。
  • 在该位置插入节点:初始化节点num,将该节点置于none的位置。
image.png

在编写的过程中我们需要注意两点:

  • 如果插入的数值已经存在,那么则不插入。
  • 使用pre节点保存cur的上一个位置,以为我们指定插入位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void insert(int num){
if(root == nullptr) return;
TreeNode* cur = root;
TreeNode* pre = nullptr;
while(cur != nullptr){
if(cur->val == num)
return;
pre = cur;
if(cur->val < num)
cur = cur->right;
else
cur = cur->left;
}
TreeNode* node = new TreeNode(num);
if(num > pre->val)
pre->right = node;
else
pre->left = node;
}
  1. 删除节点

在二叉树中查找到目标节点,并将其删除,和插入节点类似,我们需要保证在删除操作完成之后仍然保持着二叉树的性质。所以我们需要根据目标子节点的数量,分为0\1\2三种情况进行相应的处理。

对于度为0的情况,我们只需要简单的删除:

image.png

当度为1时,我们需要将待删除的节点替换成其子节点:

image.png

对于度为2的节点,我们则需要谨慎处理。首先我们需要找到一个能替换它的节点(左子树的最大值或是右子树的最小值),并将其删除,覆盖待删除的节点:

  • 找到待删除节点在中序遍历序列中的下一个节点,记为tmp
  • tmp的值覆盖待删除节点的值,并在书中递归删除节点tmp
image.png

代码实现如下:

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
void remove(int num){
if(root == nullptr) return;
TreeNode* cur = root;
TreeNode* pre = nullptr;
while(cur != nullptr){
if(cur->val == num)
break;
pre = cur;
if(cur->val < num)
cur = cur->right;
else
cur = cur->left;
}
if(cur == nullptr) return;
// 度为0/1
if(cur->left==nullptr || cur->right==nullptr){
TreeNode* child = cur->left==nullptr?cur->right:cur->left;
if(cur!=root){
if(pre->left==cur)
pre->left = child;
else
pre->right = child;
}else{
root = child;
}
delete cur;
}else{
TreeNode* tmp = cur->right;
// 寻找后继节点
while(tmp->left!=nullptr)
tmp = tmp->left;
// 递归删除后继节点
remove(tmp->val);
cur->val = tmp->val;
}
}
  1. 中序遍历有序

由于搜索二叉树的性质,当我们对其进行中序遍历时,总是会优先遍历下一个最小节点,所以我们知道:搜索二叉树的中序遍历时升序的。所以我们可以直接得到搜索二叉树的有序数据。

AVL树

之后单独开一篇讲 感觉比较复杂

在上一章中,我们完成了对函数体的解析,现在我们需要进一步解析函数体中的语句,还有程序中的表达式。我们需要将程序中的语句解析成我们的虚拟机能直接执行的语句,所以这一章中会有一点难度:

语句

我们的编译器中识别以下六种语句:

  • if(...) <statement>; [else <statement>;]
  • while (...) <statement>;
  • {<statement>;}
  • return xxx;
  • <;(empty statement)>
  • expression(这个我们稍后单独讨论)

现在我们要将这些语句转换成对应的汇编代码:

IF语句

IF语句的作用是跳转,根据条件表达式决定跳转的位置:

1
2
3
4
5
6
7
8
9
if (...) <statement> [else <statement>]

if (<cond>) <cond>
JZ a
<true_statement> ===> <true_statement>
else: JMP b
a: a:
<false_statement> <false_statement>
b: b:

对应的流程就是:

  • 先执行条件表达式<cond>
  • 如果条件失败,则跳转到a的位置,执行else语句
  • 如果条件成功,则在执行<true_statement>之后,无条件跳转到b,结束判断。

我们的实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if(token==If){
match(If);
match('(');
expression();
match(')');
*++text = JZ;
b = ++text;
statement();
if(token==Else){
match(Else);
*b = (int)(text + 2);
*++text = JMP;
b = ++text;
statement();
}
*b = (int)(text);
}

我们可以从栈的视角进行解释,text始终是指向下一条要执行的指令的。我们希望JZ后面跟着的是else的代码块的入口或是if判断之后的地址。

这里我们使用了延迟绑定地址的方式,我们来看看以下两种情况:

  • 只有if,我们将在执行完if_statement之后,将JZ之后的跳转地址设置成下一条指令的地址text
  • else,我们希望能够跳转到else的起始地址,我们需要在当前text指向的地址基础上+2,因为我们需要跳过JMP出口地址所占用的指令空间。同时我们需要将if_statement之后的地址设置成判断的出口,即else_statement的后一条指令

While语句

While语句的汇编代码更加简单,如下:

1
2
3
4
5
6
a:                     a:
while (<cond>) <cond>
JZ b
<statement> <statement>
JMP a
b: b:

我们的实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
else if(token==While){
match(While);
a = text;
match('(');
expression();
match(')');
*++text = JZ;
b = ++text;
statement();
*++text = JMP;
*++text = (int)a;
*b = (int)(text);
}

在跳转之前用a保存expression开始的指令,用于重新计算cond。然后延迟绑定地址b,作为while逻辑的出口

Return 语句

遇到Return语句则代表函数将要退出了,这一部分很简单,实现如下:

1
2
3
4
5
6
7
else if(token==Return){
match(Return);
if(token!=';'){
expression();
}
*++text = LEV;
}

其他语句

其他语句并不生成汇编代码,所以简单的匹配消耗即可:

1
2
3
4
5
6
7
8
9
10
11
12
else if(token=='{'){
match('{');
while(token!='}'){
statement();
}
match('}');
}else if(token==';'){
match(';');
}else{
expression();
match(';');
}

expresion

我们已经完成了对语句的解释,现在我们需要实现对表达式的解释,在此之前我们要明确什么是表达式?怎么解析我们的表达式,并计算他们。

怎么计算表达式

对于表达式中的运算符,每一个符号都有自己的优先级,在进行运算的时候,我们希望运算符优先级高的子式先被计算。例如在2 + 3 * 4中,我们希望*先被计算,然后再是+。对于我们生成的汇编代码而言,我们应该优先为优先级高的运算符生成目标代码,所以如何确定一个表达式的优先运算顺序十分重要。

这里我们使用递归下降的方法实现对表达式运算符的解析,我们在一开始定义标识符时,实际上就对运算符的优先级进行了排序:

1
2
3
4
5
enum {
Num = 128, Fun, Sys, Glo, Loc, Id,
Char, Else, Enum, If, Int, Return, Sizeof, While,
Assign, Cond, Lor, Lan, Or, Xor, And, Eq, Ne, Lt, Gt, Le, Ge, Shl, Shr, Add, Sub, Mul, Div, Mod, Inc, Dec, Brak
};

我们首先明确,一元运算符的优先级始终是高于二元运算符的,所以这里我们需要,首先完成对一元运算符的解析,这里先罗列几个较为特殊的:

  • Num 当我们遇到一个数字时 要返回它的数值
  • "..." 当我们遇到一个字符串时 要返回它的指针
  • PTR 当我们遇到一个指针类型时 我们要正确的解析它的解引用
  • Func 当我们遇到一个函数调用时,我们要正确的执行它,并返回返回值
  • Id 当我们遇到一个变量时,需要返回它的存储的值

然后,对一元预算符的判断结束后,我们需要对二元运算符的解析,但是对于二元运算符,我们需要考虑运算符号的优先级。我们给每一个运算符都设置一个当前的level,每次只对高于/等于当前level的运算符进行解析,每次解析完一个运算符之后,都将当前的优先级提高。这样我们就实现了对运算符的递归下降分析,我们的框架代码如下:

1
2
3
4
5
6
7
8
9
10
11
int expression(int level){
// 解析一元运算符
{
... // 解析顺序按一元运算符优先级进行解析
}

// 解析二元运算符
while(token>=level){
...
}
}

接下来,我们给出具体的实现:

常量

NumIMM指令将其加载到ax中即可:

1
2
3
4
5
if(token==Num){
*++text = IMM;
*++text = token_val;
expr_type = INT;
}

然后是字符串常量

1
2
3
4
5
6
7
8
else if(token=='"'){
*++text = IMM;
*++text = token_val;
expr_type = PTR;
// while(token=='"') match('"');
// 对data段进行地址对齐
data = (char*)(((int)(data) + sizeof(int)) & (-sizeof(int)));
}

这里有两点需要注意,如果你想支持"Hello""World" = "HelloWorld"的语法,那么你要设置while(token=='"') match('"');,这里我不想支持就不开了。

然后是data = (char*)(((int)(data) + sizeof(int)) & (-sizeof(int)));,这一部分的作用是将数据段进行对齐,我们希望每次的data指针都是四字节对齐的,这样可以方便我们进行索引,或是避免了字符串访问越界的可能。

sizeof

这个关键字我们也将其作为一元运算符进行处理,我们需要根据后面参数的类型,并返回它的大小。这里我们只支持Int Char Ptr三种类型,其中Ptr类型的大小同int

实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
else if(token==Sizeof){
match(Sizeof);
match('(');
if(token==Int){
match(Int);
expr_type = INT;
}else if(token==Char){
match(Char);
expr_type = CHAR;
}
while(token==Mul){
match(Mul);
expr_type = expr_type + PTR;
}
match(')');
*++text = IMM;
*++text = (expr_type==CHAR) ? sizeof(char) : sizeof(int);
expr_type = INT;
}

变量与函数调用

由于我们将函数和变量的值的词法分析都是以Id开头,所以我们对他们的目标代码生成也放在一起:

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
else if(token==Id){
match(Id);
id = current_id;
// 函数调用
if(token=='('){
match('(');
tmp = 0;
while(token!=')'){
expression(Assign);
*++text = PUSH;
tmp++;
if(token==',') match(',');
}
match(')');
if(id->class==Sys){
*++text = id->value;
}else if(id->class==Fun){
*++text = CALL;
*++text = id->value;
}else{
printf("%d: 错误的函数调用\n",line);
exit(-1);
}
// 清除栈上的变量
if(tmp>0){
*++text = ADJ;
*++text = tmp;
}
expr_type = id->type;
}else if(id->class == Num){
*++text = IMM;
*++text = id->value;
expr_type = INT;
}else{
if(id->class = Glo){
*++text = IMM;
*++text = id->value;
}else if(id->class == Loc){
*++text = LEA;
*++text = -id->value;
}else{
printf("%d: 未知变量类型\n", line);
exit(-1);
}
expr_type = id->type;
*++text = (expr_type==CHAR) ? LC : LI;
}
}

指针取值

说实话有点写不下去了,最近有点忙,心情也不好,写这个的过程中断断续续的,所以先到此为止吧。

我们完成了对词法分析的获取函数next(),现在我们尝试根据token分析,和我们的语法规则,进行简单的语法分析。

解析变量

我们的解释器的语法结构,可以用下面的EBNF的表示法直观的体现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
program ::= {global_declaration}+

global_declaration ::= enum_decl | variable_decl | function_decl

enum_decl ::= 'enum' [id] '{' id ['=' 'num'] {',' id ['=' 'num'} '}'

variable_decl ::= type {'*'} id { ',' {'*'} id } ';'

function_decl ::= type {'*'} id '(' parameter_decl ')' '{' body_decl '}'

parameter_decl ::= type {'*'} id {',' type {'*'} id}

body_decl ::= {variable_decl}, {statement}

statement ::= non_empty_statement | empty_statement

non_empty_statement ::= if_statement | while_statement | '{' statement '}'
| 'return' expression | expression ';'

if_statement ::= 'if' '(' expression ')' statement ['else' non_empty_statement]

while_statement ::= 'while' '(' expression ')' non_empty_statement

对于我们的程序而言,一切都是从对global_delartion开始:

  • 变量定义
  • 类型定义(目前只支持enum)
  • 函数定义

我们的program()作为语法解析函数,框架如下:

1
2
3
4
5
6
void program() {
next();
while(token > 0){
global_declaration();
}
}

global_declaration

即全局定义的语句,我们通过递归下降的方法,来判断当前的定义类型,具体实现如下:

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
void global_declaration(){
int type;
int i;
basetype = INT;
if(token == Enum){
match(Enum);
if(token != '{') match(Id);
else{
match('{');
enum_declaration();
match('}');
}
match(';');
return;
}else if(token==Int){
match(Int);
}else if(token==Char){
match(Char);
basetype = CHAR;
}

while(token != ';' && token != '{' && token != '}'){
type = basetype;
// 指针处理
while(token==Mul){
match(Mul);
type = type + PTR;
}
if (token!=Id){
printf("%d: bad global declaration\n", line);
exit(-1);
}
if (current_id->class != 0){
printf("%d: duplicate global declaration\n", line);
exit(-1);
}
match(Id);
current_id->type = type;

if (token=='('){
current_id->class = Fun;
current_id->value = (int)(text);
function_declaration();
}else{
current_id->class = Glo;
current_id->value = (int)(data);
data += sizeof(int);
}
if(token==','){
match(',');
}
}
next();
}

这里我们使用的依旧是lookahead的思想,我们无法根据一个token信息就实现对这一部分的语法功能解析,所以我们需要结合之后的信息,来对定义进行判断。

我们的解释器同时也支持指针类型,我们这里使用type = type+PTR的方式,来表示其包含指针的信息。

enum_declaration

主要用来解析用,分隔的变量,这里我们需要注意编译器对枚举变量的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void enum_declaration(){
int i=0;
while(token!='}'){
if(token!=Id){
printf("%d: 错误的枚举变量声明\n", line);
exit(-1);
}
next();
if(token=='='){
match('=');
if(token!=Num){
printf("%d: 枚举变量赋值错误\n", line);
exit(-1);
}
i = token_val;
next();
}
current_id->class = Num;
current_id->type = INT;
current_id->value = i++;
if(token==',') next();
}
}

辅助函数match

这里我们使用match来匹配并获取下一个token:

1
2
3
4
5
6
7
8
void match(int tk){
if(token == tk){
next();
}else{
printf("%d: 语法错误, 缺少 %c\n", line, tk);
exit(-1);
}
}

函数定义的解析

我们在先前的函数Id判断中:

1
2
3
4
5
6
7
...
if (token == '(') {
current_id[Class] = Fun;
current_id[Value] = (int)(text);
function_declaration();
} else {
...

在确定是函数类型之后,我们开始对函数结构的解析,我们对函数体的解析结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void function_declaration(){
match('(');
function_parameters();
match(')');
match('{');
function_body();
// match('}');
while(current_id->token){
if(current_id->class==Loc){
current_id->class=current_id->Bclass;
current_id->type=current_id->Btype;
current_id->value=current_id->Bvalue;
}
current_id++;
}
}

这里需要注意两个点:

  • 一是在对函数体的分析结束之后,不需要match("}"),因为函数体解析的函数会匹配他
  • 二是在函数解析完毕之后,我们需要将用到的token信息还原。这是因为在函数体解析的过程中,同名的局部变量会把原来定义的全局变量信息覆盖。

进一步的实现,则分别是对参数和函数体的内容的解析,首先是对参数的解析:

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
void function_parameters(){
int type;
int params = 0;
type = basetype = INT;
while(token!=')'){
if(token==Int) match(Int);
else if(token==Char){
match(Char);
type = CHAR;
}
while(token==Mul){
match(Mul);
type = type + PTR;
}
if(token!=Id){
printf("%d: 错误的函数参数声明\n", line);
exit(-1);
}
if (current_id->class != 0){
printf("%d: 重复定义了局部变量-^-\n", line);
exit(-1);
}
match(Id);

current_id->Bclass = current_id->class;
current_id->Btype = current_id->type;
current_id->Bvalue = current_id->value;
current_id->class = Loc;
current_id->type = type;
current_id->value = ++params;

if(token==',') match(',');
}
}

这里我们需要注意两点,首先是index_of_bp,这个变量用于确定参数在栈上的偏移值,因为从bp到函数传参之间隔着一个返回地址,所以在计算时需要将index_of_bp加一。

其次是,当我们遇到一个Id类型的token,我们将其所有的信息都备份一遍,并且将值赋值为参数的索引

然后是对函数体的解析,我们可以进一步分成局部变量声明和语句部分:

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
void function_body(){
int pos_local = 0;
int type;

while(token==Int||token==Char){
basetype = (token==Int ? INT : CHAR);
match(token);
while(token!= ';'){
type = basetype;
while(token==Mul){
match(Mul);
type = type + PTR;
}
if (token!=Id){
printf("%d: 错误的局部变量声明\n", line);
exit(-1);
}
if (current_id->class != 0){
printf("%d: 重复定义了局部变量-^-\n", line);
exit(-1);
}
match(Id);
current_id->Bclass = current_id->class;
current_id->Btype = current_id->type;
current_id->Bvalue = current_id->value;
current_id->class = Loc;
current_id->type = type;
current_id->value = ++pos_local;
if(token==',') match(',');
}
match(';');
}
*++text = ENT; // 函数入口指令
*++text = pos_local; // 局部变量大小
// 语句处理
while(token != '}'){
statement();
}
*++text = LEV; // 函数返回指令
}

这一部分需要注意的就是*++text的含义,相当于我们在栈上为局部变量预留了空间,后面的LEV则是用来返回函数调用。

至此我们对全局变量和函数定义的解析完成了,之后我们将着重实现对语句的实现,并为他们生成可用的字节码指令。