article / aiznoyer
C语言与数据结构
数据结构：
数据结构：
第二章：线性表
线性表的结构（顺序存储、链式存储）
散列表
第五章：
赫夫曼树与赫夫曼编码
前中后序遍历
排序算法时间复杂度、稳定性、实现流程（重点堆排序、冒泡、折半）
图遍历序列&序列转图
构造哈希函数的方法
C语言：
C语言特点、命名规则、函数调用过程
值传递与地址传递
指针、指针运算、不同指针的内存占用
Union特征
文件操作
引用区别
C语言一些常见的问题：
1、32个关键字全是小写，常见的数据类型：short int long char double float unsigned 7，以及结构类型、系统标识：auto enum typedef volatile static struct void const register default extern signed sizeof union return 15，以及循环体结构：while if else break case switch continue do for goto 10
尤其注意的是 bool 类型不是关键字，bool定义在头文件stdbool.h中
2、标识符：标识符由字母、数字和下划线组成，且第一个字符不能是数字，标识符区分大小写
3、常量：以0开头默认为8进制；以0x（0X）开头默认16进制；以0b（0B）开头默认2进制；常量后面加l/L为long格式；常量后面加u/U为unsigned 格式；
关于浮点数常量，下面举例一些错误描述就能懂了：
52.0e1314 -- e前面有小数点只能有1位
5.2e 1314 -- e后面有空格
e1314 -- e前面必须有数字
2e -- e后面必须有数字
5.2e13.14 -- e后面必须为正负整型
4、一些奇怪的转义字符：常见的为 \n、\r、\"、\'、?
\a 声音警铃 \b 退格 \f 表单 \t 水平制表 \v 垂直制表
5、优先级：括号、引用 > 单目运算 > 算数运算 > 移位运算 > 关系运算 > 逻辑运算 > 三目运算 > 赋值运算
常见问题判断：a+=a-=a+a，+=、-=都属于赋值运算，不属于算术运算
%只能进行整数运算
& 位与 | 位或 ^ 异或 ~ 取补 << 左移 >> 右移
6、初始化数组
int a[N] = {0}; -- 全部初始化为0；
int a[N]; -- 随机初始化，没有填充的时候忌用
char c[] = "qwq !";
7、结构体与结构体指针
结构体是由一组数据元素构成的数据类型，可以将不同类型的数据组合在一起形成一个新的类型。而结构体指针是指向结构体变量的指针，它保存着该结构体变量的地址。
在C语言中，结构体和结构体指针的区别在于它们的数据类型。结构体是一种数据类型，而结构体指针则是指向该数据类型的指针类型。使用结构体指针可以访问结构体中的各个成员，并对其进行修改，而使用结构体变量则需要使用.或->符号来访问其成员。以下面结构为例：
typedef struct BTNode {
int data;
int path;
struct BTNode *lchild, *rchild;
}BTNode, *BiTree;
使用上述代码声明的结构体和结构体指针类型时，需要注意以下几点：
BTNode用于表示二叉树的节点类型，BiTree用于表示指向二叉树节点的指针类型。- 在访问
BTNode类型的成员时，使用.符号；在访问BiTree类型的结构体成员时，使用->符号。 - 在声明和初始化变量时，需要根据变量的类型使用相应的方式进行。
例如，在声明指向BTNode类型的指针变量时，可以使用以下方式：
BTNode* node1; // 声明指向BTNode类型的指针变量
node1 = (BTNode*)malloc(sizeof(BTNode)); // 动态分配内存空间
node1->data = 1; // 使用->符号访问结构体成员
node1->path = 0;
node1->lchild = NULL;
node1->rchild = NULL;
而在声明指向BiTree类型的指针变量时，可以使用以下方式：
BiTree tree; // 声明指向BTNode类型的指针变量
tree = node1; // node1为指向BTNode类型的指针变量
**在实际编程中，通常使用指向结构体的指针来表示数据结构，这样可以节省内存空间，且能够动态地分配内存，有效地支持动态数据结构的操作。但在某些情况下，如果没有特殊需要，也可以直接使用结构体变量来表示数据。**使用指针变量更适合处理嵌套结构。当然，如果在具体的应用场景中，不需要动态内存分配或者没有特殊需求，使用结构体变量也是可以的。
8、结构化程序设计方法
- 自顶向下：先考虑总体步骤，再考虑步骤的细节；先考虑全局目标，后考虑局部目标。
- 逐步求精：对于复杂的问题，大的操作步骤应该将其分解为一些子步骤的序列，逐步实现。
- 函数实现：全局目标分解为局部目标，再进一步分解为具体的小目标，把最终的小目标用函数实现。
9、递归
递归的实质是把问题简化成形式相同、但较简单的一些情况，程序书写时只给出统一的形式，到运行时再展开。程序每一次递归，问题就进一步简化，比如把n！的问题简化成（n - 1）！的计算。
10、宏
宏定义#define是C语言中常用的功能，用宏来定义一些符号常量。宏定义在编译预处理中起作用，不是真正的C语句，因此行尾无需分号。
#define PI 3.1 4 159 26
#define 宏名 宏定义字符串
如上所见，宏名中间不能有空格，但是宏定义字符串可以任意书写，但是必须在一行内。宏定义只是对字符串相同的内容进行替换，不会进行运算。如下：
#define P 3
#define S(a) P*a*a
S(3 + 5)
// 等效为 3 * 3 + 5 * 3 + 5 = 9 + 15 + 5 = 29
11、文件包含
#include "需包含的文件名"
#include <需包含的文件名>
< >使用的是C语言标准的头文件，查找的是默认include文件夹下的文件；" "先查找当前文件夹下的文件，找不到再查找默认include文件夹下的文件。简而言之：< > > " "
12、少见常考文件操作函数
| 函数名 | 函数定义格式 | 函数功能 | 返回值 |
|---|---|---|---|
| feop | int feop(FILE *fp) | 检查fp文件是否结束 | 是：非0 失败：0 |
| rewind | void rewind(FILE *fp) | 移动fp所指文件读写位置到文件头 | |
| fseek | int fseek(FILE *fp, long n, unsigned int posi) | 移动fp所指文件读写位置，n为位移量，posi决定起始位置 | 成功：0 失败：非0 |
| ftell | long ftell(FILE *fp) | 求当前位置到文件头的字节数 | 成功：所求字节数 失败：EOF |
fseek（*1， *2， *3）中，*3位置有常见定义SEEK_SET、SEEK_CUR、SEEK_END，分别表示常量0、1、2，表示起始位置为：文件首部、当前位置、文件尾部
13、文件打开方式
| 文本文件 | ASCII | 二进制文件 | Binary |
|---|---|---|---|
| 使用方式 | 含义 | 使用方式 | 含义 |
| r | 打开文件只读 | rb | 打开文件只读 |
| w | 新建文件只写 | wb | 新建文件只写 |
| a | 打开文件追加 | ab | 打开文件追加 |
| r+ | 打开文件读/写 | rb+ | 打开文件读/写 |
| w+ | 新建文件读/写 | wb+ | 新建文件读/写 |
| a+ | 打开文件读/写/追加 | ab+ | 打开文件读/写/追加 |
*可见其实二进制文件和文本文件的差别只是操作指令加了个b，这个b就是binary二进制的意思。
14、常见字符串操作函数：
| 函数名 | 函数定义格式 | 函数功能 | 返回值 |
|---|---|---|---|
| strcat | char * strcat(char *s, char * t) | 把字符串t连接到s，使s成为包含t的结果串 | 字符串s |
| strcmp | int strcmp(char *s, char * t) | 逐个比较字符串s和t中的对应字符，直到对应字符不等或比较到串尾 | 相等：0 不等：不等字符串的差值 |
| strcpy | char * strcpy(char *s, char * t) | 把字符串t复制到s中 | 字符串s |
| strlen | unsigned int strlen(char *s) | 计算字符串s的长度（不包括'\0'） | 字符串长度 |
| strchr | char * strchr(char *s, char c) | 在字符串s中查找字符c首次出现的地址 | 找到：相应地址 找不到：NULL |
| strstr | char * strstr(char *s, char *t) | 在字符串s中查找字符串t首次出现的地址 | 找到：相应地址 找不到：NULL |
*strcmp = str compare || strcpy = str copy || strlen = str length
数据结构一些常见的问题：
1、算法 + 数据结构 = 程序
2、一个算法必须满足以下五个重要特性： 有穷性、 确定性 、 可行性、 输入 、输出
3、评价算法优劣的基本标准 ：正确性 、 可读性 、 健壮性 、 高效性