前言

前置知识：学完C语言中的顺序结构、选择结构、循环结构、数组、指针、地址

第一章 结构体和typedef自定义数据类型

1.1 结构体类型

结构体是一个数据类型，允许用户在里面定义其他的数据类型，例如：

struct student
{
	long long no;
	char name[50];
};

这里定义了一个学生的结构体，学号为8字节整型，姓名为字符型数组，大小为50*sizeof(char)

1.2 结构体的使用

结构体直接访问内部成员变量用点号运算符.，指针访问内部成员变量用箭头运算符->，例如有以下结构体

struct test01
{
	int no;
	char* name;
};

要使用结构体类型数据，首先要将结构体数据实例化：

struct test01 t1;

然后有一个结构体指针类型指向原来的t1：

struct test01* pT1 = &t1;

这时候，访问结构体变量就可以用点号运算符和箭头运算符

pT1->name = "Alice"; //等价于t1.name = "Alice";
pT1->no = 1; //等价于t1.no = 1;

其实，pT1->no是(*pT1).no的简略形式 ，二者在作用上完全等价。

1.3 typedef自定义数据类型

自定义数据类型允许用户自己定义数据类型的名称，从而达到精简代码的作用

例如：

typedef struct test02
{
	int a;
	char ch;
	float b;
}T,*pT;

然后我们就可以用T代替struct test02，用pT代替struct test02*了

具体怎么用呢？再来看个例子

T t2;
pT pT2 = &t2;
//...

(其实以上例子就是自定义了一个数据类型T，等价于struct test02）

第二章 线性表

2.1 数组

数组是一个内存连续的线性表，因为其内存连续的性质，数组的增删操作较为麻烦（时间复杂度为$O(n)$），改查操作较为简单（时间复杂度为$O(1)$）

2.2 链表

链表的内存通常是不连续的，一个链表的节点通常包含至少两个信息，第一个是当前节点的值，第二个是指向下一个节点的指针，由此，我们可以编写出如下所示的代码

typedef struct Node
{
    int data;
    struct Node* next;
} Node;

为了方便，我们可以再定义Node的指针为node

typedef Node* node;

接下来，创建一个链表

int main() {
    // 创建三个节点
    node n1 = (node)malloc(sizeof(Node));
    node n2 = (node)malloc(sizeof(Node));
    node n3 = (node)malloc(sizeof(Node));

    // 初始化数据
    n1->data = 1;
    n1->next = n2;
    
    n2->data = 2;
    n2->next = n3;
    
    n3->data = 3;
    n3->next = NULL;

    // 遍历打印
    for(node temp = n1; temp != NULL; temp = temp->next) {
        printf("%d ", temp->data);
    }

    // 释放内存（重要！）
    free(n3);
    free(n2);
    free(n1);

    return 0;
}

2.3 栈

栈（Stack）是一个后入先出（LIFO）的数据结构，可以用数组或链表模拟
这里提供一个数组模拟的代码

typedef struct stk
{
	int* arr;
	int length;
}stack;

在栈里面添加元素可以这样操作

arr[length++]=data;

删除操作直接length--;就可以了。
查看栈顶直接return arr[length-1]。

2.4 队列

队列（Queue）是一个先入先出（FIFO）的数据结构，它的操作代码和栈类似，也可以用数组或链表模拟，这里不再提供代码过程。

第三章 树

3.1 树

树是一种非线性的数据结构，由节点和边组成，有一个根节点，每个节点可以有多个子节点，但每个子节点只能有一个父节点。

这里，Child 1、Child 2、Child 3是Root的子节点，Child 1’s Child和Child 2’s Child分别是Child 1和Child 2的子节点

2.2 二叉树

首先说一句重点，二叉树不是树！（因为树的同级节点是没有方向的，但是二叉树的左子节点和右子节点是有方向的）

2.3.1 二叉树的结构

有一个根节点，每个节点下面最多有两个子节点（其中只有左子节点和只有右子节点的二叉树一定不相等，即使它们的数值相等）

2.3.2 二叉树的遍历

深度优先搜索（DFS）
先序遍历： 根节点->左子节点->右子节点
中序遍历： 左子节点->根节点->右子节点
后序遍历： 左子节点->右子节点->根节点
广度优先搜索（BFS）
按层从上到下、从左到右访问节点