重点章节已更新完毕，其他章节持续更新中，最新版本可以查看语雀
考前须知
考核形式：闭卷笔试，不能使用电脑编程
试题类型 ： 填空、选择、判断、简答、算法设计
成绩占比：
- 按章节：
- 25%： 绪论 ， 串 ， 数组和广义表 ，排序
- 75%： 线性表 ， 栈和队列 ， 树和二叉树 ， 图 ， 查找
- 按能力：
- 30%：识记
- 50%：理解
- 20%：应用
绪论
数据：信息的载体，包括数字、字符、图像、声音等任何形式的数据
数据项：数据的基本单位,是不可分割的最小数据单元。例如，在一个学生记录中，学生的学号、姓名、年龄等都是数据项。
数据元素：数据元素是数据的基本单位，通常由多个数据项组成。例如，在一个学生记录中，一个学生的所有信息（学号、姓名、年龄等）组成一个数据元素。
数据对象：具有相同性质的数据元素的集合。例如，一个班级的所有学生记录可以组成一个数据对象。
数据结构：数据元素之间的关系以及对这些关系的操作的集合。例如，数组、链表、栈、队列、树、图等。
基本数据结构：
- 数组：适合随机访问，但插入和删除效率低。
- 链表：适合动态数据存储，但随机访问效率低。
- 栈和队列：适合特定的操作顺序（LIFO 或 FIFO）。
- 哈希表：适合快速查找，但需要处理哈希冲突。
- 树和图：适合表示层次关系和复杂网络。
算法效率：
- 时间复杂度：算法运行时间随输入规模增长的变化趋势
- 空间复杂度：算法在运行过程中所需的内存空间随输入规模增长的变化趋势
线性表❗
基本概念
- 线性表是一些元素的有序集合，这些元素具有相同的数据类型。
- 分类：
- 数组：查找快，物理地址相邻
- 链表：插入、修改快，逻辑地址相邻
- 特点：每个元素都有一个前驱和后继（除了第一个和最后一个元素），形成了一种线性的顺序关系。
- 前驱：元素前面的元素
- 后继：元素后面的元素
线性表的基本运算
对于线性表的操作主要包括以下几种：
- 创建：初始化一个空的线性表。
- 插入：在指定位置插入一个新的元素。
- 删除：移除指定位置的元素。
- 查找：根据给定条件（如值或索引）查找元素的位置。
- 访问：获取指定位置上的元素值。
- 更新：修改指定位置上的元素值。
- 遍历：按顺序访问所有元素。
- 清空：将线性表中的所有元素移除，使其变为一个空表。
- 获取长度：返回线性表中元素的数量。
线性表(数组)实现
常考：
#define ElemType int
#define MaxSize 100
// 线性表的存储结构
typedef struct {
ElemType data[MaxSize]; // 使用数组存储元素，ElemType为元素类型，MaxSize为数组最大长度
int length; // 当前线性表的长度
} SqList;
// 初始化线性表
void InitList(SqList &L) {
for (int i = 0; i < MaxSize; i++) {
L.data[i] = 0; // 将所有元素初始化为0
}
L.length = 0; // 初始化长度为0
printf("线性表初始化成功！\n");
}
// 插入元素
int ListInsert(SqList &L, int i, ElemType e) {
// 判断插入位置i是否合法
if (i < 1 || i > L.length + 1) {
printf("插入位置不合法！\n");
return 0;
}
// 判断线性表是否已满
if (L.length >= MaxSize) {
printf("线性表已满，无法插入！\n");
return 0;
}
// 将数组从插入位置整体后移一位
for (int j = L.length; j >= i; j--) {
L.data[j] = L.data[j - 1];
}
// 修改插入位置的元素
L.data[i - 1] = e;
L.length++; // 长度加1
printf("元素 %d 插入成功！\n", e);
return 1;
}
// 删除元素
int ListDelete(SqList &L, int i, ElemType &e) {
// 判断删除位置i是否合法
if (i < 1 || i > L.length) {
printf("删除位置不合法！\n");
return 0;
}
// 判断线性表是否为空
if (L.length == 0) {
printf("线性表为空，无法删除！\n");
return 0;
}
// 保存被删除的元素
e = L.data[i - 1];
// 将数组从删除位置整体前移一位
for (int j = i; j < L.length; j++) {
L.data[j - 1] = L.data[j];
}
L.length--; // 长度减1
printf("元素 %d 删除成功！\n", e);
return 1;
}
// 按值查找元素的位置
int LocateElem(SqList L, ElemType e) {
// 遍历线性表，查找值为e的元素
for (int i = 0; i < L.length; i++) {
if (L.data[i] == e) {
return i + 1; // 返回元素的位置（从1开始）
}
}
printf("未找到元素 %d！\n", e);
return -1; // 未找到返回-1
}
其他
// 判断线性表是否为空
int IsEmpty(SqList L) {
return L.length == 0; // 如果长度为0，则线性表为空
}
// 判断线性表是否已满
int IsFull(SqList L) {
return L.length == MaxSize; // 如果长度等于最大容量，则线性表已满
}
// 获取线性表的长度
int GetLength(SqList L) {
return L.length; // 返回当前长度
}
// 按位置查找元素
ElemType GetElem(SqList L, int i) {
// 判断位置i是否合法
if (i < 1 || i > L.length) {
printf("查找位置不合法！\n");
return -1;
}
return L.data[i - 1]; // 返回对应位置的元素
}
// 打印线性表
void PrintList(SqList L) {
if (IsEmpty(L)) {
printf("线性表为空！\n");
return;
}
printf("线性表内容：");
for (int i = 0; i < L.length; i++) {
printf("%d ", L.data[i]); // 打印每个元素
}
printf("\n");
}
链表的实现
链表是一种动态的数据结构，通过指针将一组零散的内存块连接起来
单链表
- 每个节点都包含两部分：
- 数据域（Data）：存放数据，头结点数据域为空
- 指针域（Next）：指针指向下一个节点，尾节点指针域为空
- 特点：只能从头到尾单向遍历；插入、删除操作只需改变相关节点的指针。
#define ElemType int
// 定义链表节点结构
typedef struct Node {
ElemType data;
struct Node *next;
} Node;
// 定义链表结构
typedef struct {
Node *head; // 头指针，指向链表的第一个节点
} LinkedList;
常考：
// 初始化链表
void InitList(LinkedList *L) {
L->head = NULL; // 头指针初始化为NULL
}
// 判断链表是否为空
int IsEmpty(LinkedList L) {
return L.head == NULL; // 头指针为NULL时链表为空
}
// 求非空节点数
int GetLength(LinkedList L) {
int count = 0;
Node *p = L.head; // 从头节点开始遍历
while (p != NULL) {
count++;
p = p->next;
}
return count;
}
// 插入新节点
int InsertNode(LinkedList *L, int pos, ElemType value) {
// 检查插入位置是否合法
if (pos < 1 || pos > GetLength(*L) + 1) {
printf("插入位置不合法！\n");
return 0;
}
// 创建新节点
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
// 在链表头部插入
if (pos == 1) {
newNode->next = L->head;
L->head = newNode;
} else {
// 找到插入位置的前一个节点
Node *p = L->head;
for (int i = 1; i < pos - 1; i++) {
p = p->next;
}
// 插入新节点
newNode->next = p->next;
p->next = newNode;
}
printf("节点 %d 插入成功！\n", value);
return 1;
}
// 获取某节点的值
ElemType GetNodeValue(LinkedList L, int pos) {
// 检查位置是否合法
if (pos < 1 || pos > GetLength(L)) {
printf("查找位置不合法！\n");
return -1;
}
// 找到对应位置的节点
Node *p = L.head;
for (int i = 1; i < pos; i++) {
p = p->next;
}
return p->data;
}
// 删除链表中节点
int DeleteNode(LinkedList *L, int pos) {
// 检查位置是否合法
if (pos < 1 || pos > GetLength(*L)) {
printf("删除位置不合法！\n");
return 0;
}
Node *temp;
// 删除头节点
if (pos == 1) {
temp = L->head;
L->head = L->head->next;
} else {
// 找到待删除节点的前一个节点
Node *p = L->head;
for (int i = 1; i < pos - 1; i++) {
p = p->next;
}
temp = p->next;
p->next = temp->next;
}
// 释放节点内存
printf("节点 %d 删除成功！\n", temp->data);
free(temp);
return 1;
}
其他：
// 清空链表
void ClearList(LinkedList *L) {
Node *p = L->head;
while (p != NULL) {
Node *temp = p;
p = p->next;
free(temp); // 释放节点内存
}
L->head = NULL; // 头指针置为NULL
printf("链表已清空！\n");
}
// 遍历节点
void TraverseList(LinkedList L) {
if (IsEmpty(L)) {
printf("链表为空！\n");
return;
}
printf("链表内容：");
Node *p = L.head;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
双向链表
- 节点包含三个部分
- 数据域（Data）：头节点的数据域为空
- 前驱指针（Prev)：头节点的前驱为空
- 后继指针（Next）：尾节点的后继为空
- 特点：可以从任一方向遍历链表；插入、删除操作需要同时更新前后两个节点的指针。
#define ElemType int
// 定义双向链表节点结构
typedef struct Node {
ElemType data; // 数据域
struct Node *prev; // 指向前驱节点的指针
struct Node *next; // 指向后继节点的指针
} Node;
常用：
// 初始化链表
Node* InitList() {
// 创建头结点
Node* guard = (Node*)malloc(sizeof(Node));
if(guard ==NULL){
printf("分配空间失败\n");
exit(-1);
}
guard->next = guard;
guard->prev = guard;
return guard;
}
// 判断链表是否为空
int IsEmpty(Node *L) {
return L->next == L; // 头节点的 next 指向自身时链表为空
}
// 获取链表长度
int GetLength(Node *L) {
int count = 0;
Node *p = L->next; // 从第一个节点开始遍历
while (p != L) { // 回到头节点时结束
count++;
p = p->next;
}
return count;
}
// 插入新节点
int InsertNode(Node *L, int pos, ElemType value) {
// 检查插入位置是否合法
if (pos < 1 || pos > GetLength(L) + 1) {
printf("插入位置不合法！\n");
return 0;
}
// 创建新节点
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
// 找到插入位置的前一个节点
Node *p = L;
for (int i = 1; i < pos; i++) {
p = p->next;
}
// 插入新节点
newNode->next = p->next;
newNode->prev = p;
p->next->prev = newNode;
p->next = newNode;
printf("节点 %d 插入成功！\n", value);
return 1;
}
// 删除节点
int DeleteNode(Node *L, int pos) {
// 检查位置是否合法
if (pos < 1 || pos > GetLength(L)) {
printf("删除位置不合法！\n");
return 0;
}
// 找到待删除节点
Node *p = L->next;
for (int i = 1; i < pos; i++) {
p = p->next;
}
// 调整前驱和后继节点的指针
p->prev->next = p->next;
p->next->prev = p->prev;
// 释放节点内存
printf("节点 %d 删除成功！\n", p->data);
free(p);
return 1;
}
// 尾插操作
int InsertAtTail(Node *L, ElemType value) {
// 创建新节点
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
printf("分配空间失败\n");
return 0;
}
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
// 找到链表的最后一个节点
Node *lastNode = L->prev;
// 插入新节点
newNode->next = L;
newNode->prev = lastNode;
lastNode->next = newNode;
L->prev = newNode;
printf("节点 %d 尾插成功！\n", value);
return 1;
}
// 尾删操作
int DeleteAtTail(Node *L) {
// 检查链表是否为空
if (IsEmpty(L)) {
printf("链表为空，无法删除！\n");
return 0;
}
// 找到链表的最后一个节点
Node *lastNode = L->prev;
// 调整指针
lastNode->prev->next = L;
L->prev = lastNode->prev;
// 释放节点内存
printf("节点 %d 尾删成功！\n", lastNode->data);
free(lastNode);
return 1;
}
// 获取某节点的值
int GetNodeValue(Node *L, int pos) {
// 检查位置是否合法
if (pos < 1 || pos > GetLength(L)) {
printf("查找位置不合法！\n");
return -1;
}
// 找到对应位置的节点
Node *p = L->next;
for (int i = 1; i < pos; i++) {
p = p->next;
}
return p->data;
}
其他：
// 清空链表
void ClearList(Node *L) {
Node *p = L->head;
while (p != NULL) {
Node *temp = p;
p = p->next;
free(temp); // 释放节点内存
}
L->head = NULL; // 头指针置为NULL
printf("链表已清空！\n");
}
// 遍历链表
void TraverseList(Node L) {
if (IsEmpty(L)) {
printf("链表为空！\n");
return;
}
printf("链表内容：");
Node *p = L.head;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
// 获取链表长度
int GetLength(Node L) {
int count = 0;
Node *p = L.head; // 从头节点开始遍历
while (p != NULL) {
count++;
p = p->next;
}
return count;
}
数组和链表对比
- 内存使用：
- 顺序存储结构需要连续的内存空间，可能存在内存碎片的问题；
- 链式存储结构则更加灵活，可以充分利用内存空间。
- 访问速度：
- 顺序存储结构支持随机访问，访问速度快；
- 链式存储结构需要顺序访问，访问速度相对较慢。
- 动态性：
- 链式存储结构更加灵活，易于动态插入和删除元素；
- 顺序存储结构的大小固定，不易动态改变。
- 应用场景
- 顺序存储：适用于元素数量固定、频繁访问元素的场景，如数组、栈等。
- 链式存储：适用于元素数量动态变化、频繁插入和删除元素的场景，如链表、队列等。
栈和队列❗
栈
概念：后进先出的线性表
基本操作：
- 在栈顶进行插入(入栈)和删除(出栈)
- 栈的初始化
- 判空
- 取顶元素
栈的形式：
- 顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针 top 指示栈顶元素在顺序栈中的位置
- 链栈：
- 采用单链表来存储栈中的元素
- 只在链表头部进行插入和删除，不必设头结点
- 链表的头指针就是栈顶指针
栈的实现(链栈)：
#include <stdio.h>
#include <stdlib.h>
typedef int elemtype;
typedef struct LinkedStackNode
{
elemtype data;
struct LinkedStackNode * next;
} LinkedStackNode, * LinkedStack;
LinkedStack top;
//初始化
LinkedStack Init_LinkedStack()
{
LinkedStack top=(LinkedStackNode * )malloc (sizeof( LinkedStackNode));
if(top!=NULL)//申请空间成功
top->next=NULL;//设置栈顶指针为空
return top;
}
//判栈空
int LinkedStack_Empty(LinkedStack top)
{
if(top->next==NULL)//检查栈顶指针的值
{
return 1;//栈S为空，函数返回1
}
else
{
return 0;
}
}
//入栈
int Push_LinkedStack(LinkedStack top,elemtype x)
//插入数据元素x为新的栈顶元素
{
LinkedStackNode * node;
node=(LinkedStackNode * )malloc(sizeof(LinkedStackNode));
if(node==NULL)
{
return 0;//申请结点空间失败,插入失败，函数返回0
}
else
{
node->data=x;//设置新结点的数据域
node->next=top->next;//设置新结点的指针城
top->next=node;//设置头结点指针城指向新的栈顶元素
return 1;//插入成功，函数返回1
}
}
//出栈
int Pop_LinkedStack(LinkedStack top, elemtype *x)
{ LinkedStackNode * node;
if(top->next==NULL)
{
return 0;
}
else
{
node=top->next;//将原栈顶数据元素弹出并赋给node
*x=node->data;//将原栈顶数据元素的数据赋值给x
top->next=node->next;//top指向链栈中的下一个数据元素
free (node);//释放原栈顶数据元素所占的空间
return 1;
}
}
//求栈长
int Length_LinkedStack(LinkedStack top)
{
int count = 0;
while(top->next!=NULL)
{
++count;
top=top->next;
}
return count;
}
//取栈顶元素
int GetTop_LinkedStack(LinkedStack top)
{
if(top->next)
{
return top->next->data;
}
return -1;
}
顺序栈：
#define ElemType char
#define MaxSize 100
//定义
typedef struct{
ElemType data[MaxSize];
int top;
int bottom;
}stack;
//初始化
stack *StackCreate(){
stack *p=(stack*)malloc(sizeof(stack));//分配新空间
if(p==NULL)//分配失败
return 0;
p->bottom = p->top = 0;//分配成功
return p;
}
//入栈
void StackInput(stack *p,ElemType e){
p->data[p->top] = e;//存入栈中
p->top++;//栈顶指针加1
}
//出栈
ElemType StackOutput(stack *p,ElemType e){
if(p->top!=p->bottom){//栈非空
e=p->data[p->top-1];//栈顶内容输出
p->top--;//栈顶减1
return e;
}
}
队列
概念：先进先出的线性表
基本操作：
- 入队：将元素添加到队列的尾部
- 出队：移除并返回队列的头部元素
- 返回队列的头部元素，但不移除
- 判断队列是否为空
- 判断队列是否已满（仅适用于固定大小的队列）
队列的形式：
- 数组队列
- 链表队列
特殊的队列–循环队列：
- 通过将队列的存储空间首尾相连，形成一个环形结构，从而解决普通数组实现的队列在出队操作后空间浪费的问题
- 判断队列空和满的条件：
- 队列空：
front == rear。 - 队列满：
(rear + 1) % size == front。
- 队列空：
实现示例(顺序队列)：
#include <stdio.h>
#define SIZE 5
int queue[SIZE];
int front = 0, rear = 0;
//入栈
void enqueue(int item) {
if ((rear + 1) % SIZE == front) {
printf("Queue is full!\n");
} else {
queue[rear] = item;
rear = (rear + 1) % SIZE;
}
}
//出栈
int dequeue() {
if (front == rear) {
printf("Queue is empty!\n");
return -1;
} else {
int item = queue[front];
front = (front + 1) % SIZE;
return item;
}
}
int peek() {
if (front == rear) {
printf("Queue is empty!\n");
return -1;
} else {
return queue[front];
}
}
int isEmpty() {
return front == rear;
}
int isFull() {
return (rear + 1) % SIZE == front;
}
链式存储队列：
// 定义队列节点结构
typedef struct QueueNode {
int data; // 数据域
struct QueueNode *next; // 指向下一个节点的指针
} QueueNode;
// 定义链式队列结构
typedef struct {
QueueNode *front; // 队头指针
QueueNode *rear; // 队尾指针
} LinkedQueue;
// 初始化队列
void InitQueue(LinkedQueue *Q) {
Q->front = Q->rear = NULL; // 队头和队尾指针初始化为NULL
printf("队列初始化成功！\n");
}
// 判断队列是否为空
int IsEmpty(LinkedQueue Q) {
return Q.front == NULL; // 队头指针为NULL时队列为空
}
// 入队
void Enqueue(LinkedQueue *Q, int item) {
// 创建新节点
QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
if (newNode == NULL) {
printf("分配空间失败\n");
return;
}
newNode->data = item;
newNode->next = NULL;
// 如果队列为空，队头和队尾都指向新节点
if (IsEmpty(*Q)) {
Q->front = Q->rear = newNode;
} else {
// 将新节点插入到队尾
Q->rear->next = newNode;
Q->rear = newNode;
}
printf("元素 %d 入队成功！\n", item);
}
// 出队
int Dequeue(LinkedQueue *Q) {
if (IsEmpty(*Q)) {
printf("队列为空，无法出队！\n");
return -1;
}
// 保存队头节点
QueueNode *temp = Q->front;
int item = temp->data; // 返回队头元素的值
Q->front = temp->next; // 更新队头指针
// 如果队列为空，队尾指针也置为NULL
if (Q->front == NULL) {
Q->rear = NULL;
}
free(temp); // 释放队头节点内存
printf("元素 %d 出队成功！\n", item);
return item;
}
// 获取队头元素
int GetFront(LinkedQueue Q) {
if (IsEmpty(Q)) {
printf("队列为空，无法获取队头元素！\n");
return -1;
}
return Q.front->data; // 返回队头元素的值
}
串
TODO 后续补充
数组和广义表
TODO 后续补充
树和二叉树❗
树
树的概念：树是一种 非线性数据结构，它由节点和边组成，具有层次关系
树的术语：
（1）节点
- 树的基本单位，包含数据元素和指向其他节点的指针（边）。
- 例如：
A、B、C等都是节点。（2）根节点
- 树的顶层节点，没有父节点。
- 例如：
A是根节点。（3）父节点
- 一个节点的直接上层节点。
- 例如：
A是B和C的父节点。（4）子节点
- 一个节点的直接下层节点。
- 例如：
B和C是A的子节点。（5）兄弟节点
- 具有相同父节点的节点。
- 例如：
B和C是兄弟节点。（6）叶子节点
- 没有子节点的节点。
- 例如：
G、H、I是叶子节点。（7）内部节点
- 至少有一个子节点的节点。
- 例如：
B、C是内部节点。（8）边
- 连接两个节点的线段，表示节点之间的关系。
- 例如：
A-B、A-C是边。（9）路径
- 从一个节点到另一个节点的节点序列，路径上的边数称为路径长度。
- 例如：
A -> B -> D是一条路径。（10）深度（Depth）
- 从根节点到该节点的路径长度。
- 例如：
A的深度为 0，B的深度为 1。（11）高度
- 从该节点到叶子节点的最长路径长度。
- 例如：
A的高度为 3，B的高度为 2。（12）层次
- 根节点为第 0 层，其子节点为第 1 层，以此类推。
- 例如：
A在第 0 层，B和C在第 1 层。（13）度
- 一个节点的子节点数量。
- 例如：
A的度为 2，B的度为 1。（14）子树
- 树中的任意节点及其后代节点构成的树。
- 例如：以
C为根的子树包含E、F、J。（15）森林
- 由多棵互不相交的树组成的集合。
二叉树
树的分类
- 二叉树：每个节点最多有两个子节点（左子节点和右子节点）
- 满二叉树：每个节点都有 0 或 2 个子节点
- 完全二叉树：除了最后一层，其他层都是满的，且最后一层的节点靠左
二叉树的存储结构
顺序*
链式
// 定义二叉树节点结构
typedef struct TreeNode {
int data; // 数据域
struct TreeNode *left; // 指向左子节点的指针
struct TreeNode *right; // 指向右子节点的指针
} TreeNode;
二叉树的遍历算法
前序遍历
遍历顺序：根节点 -> 左子树 -> 右子树
实现：
void PreOrderTraversal(TreeNode *root) {
if (root == NULL) {
return;
}
printf("%d ", root->data); // 访问根节点
PreOrderTraversal(root->left); // 递归遍历左子树
PreOrderTraversal(root->right); // 递归遍历右子树
}
中序遍历
遍历顺序：左子树 -> 根节点 -> 右子树
实现：
void InOrderTraversal(TreeNode *root) {
if (root == NULL) {
return;
}
InOrderTraversal(root->left); // 递归遍历左子树
printf("%d ", root->data); // 访问根节点
InOrderTraversal(root->right); // 递归遍历右子树
}
后序遍历
遍历顺序：左子树 -> 右子树 -> 根节点
实现：
void PostOrderTraversal(TreeNode *root) {
if (root == NULL) {
return;
}
PostOrderTraversal(root->left); // 递归遍历左子树
PostOrderTraversal(root->right); // 递归遍历右子树
printf("%d ", root->data); // 访问根节点
}
层次遍历
按层次顺序访问树的节点，从根开始，逐层向下访问每一层的节点
树和森林
哈夫曼树
具有最小带权路径长度的二叉树称为哈夫曼树，用于 数据压缩 和 编码。
构造原则：
- 权值越大的叶结点越靠近根结点。
- 权值越小的叶结点越远离根结点。
产生哈夫曼编码示例如下：
图❗
在现实世界中，人际关系网是十分复杂的，任何两个人都可能认识。把每个人当成一个“点”，当两个人是朋友时，就在他们之间画一条“线”。
这样一来，整个社交网络就可以被看作是由无数个点和线组成的结构，这种结构被称为图。
定义：图是点和线的集合， 用于模拟不同的东西是如何相连的 。
基本术语
- 无向图：图中的边没有方向性，两个顶点之间有双向关系
- 有向图：图中的边具有方向性，从一个顶点到另一个顶点有单向关系
下面两个图是等价的 ：
- 网：一种带权图，图中的边具有权重一种带权图，图中的边具有权重
- 子图：一个图中选取部分顶点和边组成的图
- 连通图：在无向图中，任意两个顶点之间都存在路径
- 强连通图：在有向图中，任意两个顶点之间都存在双向路径
- 连通子图：图中任意一个连通的子图
- 连通分量：极大的连通子图，子图不包含在更大的连通子图中
- 度：与该顶点相连的边的数量
- 入度：指向该顶点的边的数量
- 出度：从该顶点出发的边的数量
- 路径：从一个顶点到另一个顶点经过的顶点和边，路径的长度用边的数量来表示
上图中，顶点3的度为3，入度为1，出度为2
4到2的路径为：4->3->2或4->6->1->2或4->3->6->1->2,最短路径长度为2
- 环：一条路径的起点和终点是同一个顶点
- 稀疏图：边数相对顶点较少
- 稠密图：边数相对顶点较多
- 完全图：任意两个顶点之间都存在边
- 完全无向图的边=
n(n-1)/2，n为顶点数量 - 完全有向图的边=
n(n−1)
- 完全无向图的边=
图的存储结构
邻接矩阵
用一个二维数组来表示图的存储结构，适合于稠密图的存储
有向图的邻接矩阵
有向图的邻接矩阵如下，1表示有连接，0表示没有连接。例如 (0,1)=1，表示0->1有连接，(1,0)=0，表示1->0没有连接
无向图的邻接矩阵
无向图的邻接矩阵如下，例如 (0,1)=(1,0)=1，表示0->1有连接，(1,0)=0，表示1->0没有连接
由于无向图的邻接矩阵是对称的，只需要存储上三角或下三角部分即可，浪费了大量存储空间
带权有向图的邻接矩阵
带权有向图的邻接矩阵如下,非零自然数表示权重，无穷表示没有连接
像这样的稀疏表使用邻接矩阵存储也浪费了大量存储空间
邻接矩阵的实现：
#define INF 32767 //定义∞
#define MAXV 100 //最大顶点个数
typedef struct
{ int no; //顶点编号
InfoType info; //顶点其他信息
} VertexType;
typedef struct //图的定义
{ int edges[MAXV][MAXV]; //邻接矩阵
int n，e; //顶点数，边数
VertexType vexs[MAXV]; //存放顶点信息
} MatGraph;
邻接表
当一个图为稀疏图时，使用邻接矩阵会浪费大量的存储空间，邻接表可以解决这个问题
- 邻接表是用链表和数组来表示图的存储结构，记录的是每个顶点的出边，适合存储稀疏图
- 一个图的邻接表可能不唯一
有向图的邻接表如下：
无向图的邻接表如下，下面只表示了0这个节点的邻接表，可以看出一个图的邻接表不唯一
带权有向图的邻接表如下：
邻接表实现：
typedef struct ANode
{ int adjvex; //该边的终点编号
struct ANode *nextarc; //指向下一条边的指针
InfoType weight; //该边的权值等信息
} ArcNode;
typedef struct Vnode
{ Vertex data; //顶点信息
ArcNode *firstarc; //指向第一条边
} VNode;
typedef struct
{ VNode adjlist[MAXV]; //邻接表
int n，e; //图中顶点数n和边数e
} AdjGraph;
逆邻接表*：与邻接表相反，记录的是每个顶点的入边
图的遍历
深度优先搜索(DFS)
思路：
- 从起点开始，选择一条可能的路径向前探索。
- 在探索过程中，如果发现当前路径无法到达目标，退回上一步，选择另一条未探索的路径继续探索。
- 不断重复上述过程，直到找到目标路径或确定没有路径可达。
其中一种访问顺序：ABEGCFDHI
广度优先搜索(BFS)
广度优先搜索可以解决两类问题：
- 从一个节点到另一个节点有路径吗？
- 如果有多条路径，哪条路径最短？
思路：
- 首先访问初始节点的所有邻居，
- 然后再逐层对邻居的邻居进行遍历，
- 直到找到目标或者遍历完所有节点。
树的层次遍历可以看作是BFS在树这种特殊图上的应用
最小生成树
概念
- 一个连通图的生成树是一个极小连通子图，它含有图中全部n个顶点和构成一棵树的(n-1)条边
连通图和非连通图的生成树：
- 对于带权连通图，可能有多棵不同生成树，其中权值之和最小的生成树称为图的最小生成树
Prim算法
从一个顶点出发，在保证不形成环的前提下，每找到并添加一条最短的边，就把当前形成的连通子图当做一个整体看待，然后重复“找最短的边并添加”的操作。
以下图(a)为例，使用Prim算法构造生成树的步骤如下：
Kruskal算法
按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边
最短路径
求带权有向中，某指定顶点（称为源点）到其余各顶点的最短路径
- 要找出从某起点到某终点最快的路径 --> 狄克斯特拉(Dijkstra) 算法
- 要找出图中所有顶点对之间的最短路径 --> 佛洛伊德(Floyd)算法
Dijkstra算法
广度优先搜索找出的是段数最少的路径（如第一个图所示）。如果你 要找出从某起点到某终点最快的路径（如第二个图所示），该如何办呢？为此，可使用另一种算法——狄克斯特拉(Dijkstra) 算法
具体步骤：
- 准备距离表：
- 我们有一个表格，记录从家到每个地方的最短距离。
- 开始时，家的距离是0，其他地方的距离都写一个很大的数(无限大)，表示我们还没找到路。
- 选择最近的地方：
- 每次选择一个还没访问过的地方，且距离家最近的。
- 家到商店是2公里，家到公园是5公里，到商店的距离近，选择先去商店。
- 更新距离：
- 从商店出发，看看能到哪里。
- 从商店到学校是3公里，那家到学校的距离就是家到商店的2公里加上商店到学校的3公里，总共5公里。
- 从商店到公园是1公里，那家到公园的距离就变成家到商店的2公里加上商店到公园的1公里，总共3公里，比原来的5公里近，所以更新为3公里。
- 标记访问过的地方：
- 一旦选择了最近的地方，就标记它为已访问，表示我们已经找到了从家到这里的最短距离。
- 标记商店为已经访问，下次不在选择
- 重复步骤：
- 继续选择下一个最近的未访问地方，重复上述过程，直到所有地方都访问过。
| 终点 | 从家到各个目的的路径长度(km) | ||
|---|---|---|---|
| 第1 | 第2 | 第3 | |
| 商店(记作A) | 2 | ||
| 公园(记作B) | 5 | 3 | |
| 学校(记作C) | 无限 | 5 | 4 |
| 当前最短路径 | A | B |
Floyd算法
以下图为例，求各个顶点之间的最短距离
步骤：
- 初始时创建一个表格(二维数组)用来记录各个顶点之间的最短距离，对角线表示顶点到自己的距离，设置为0，其他设置为两个顶点的直接距离，如果没有就设置为无法到达(无限大)
- 试着在两个点的直接距离中，依次加入各个其他的顶点作为中间顶点，看看最短路径是否变短，如果变短就更新
- 直到所有顶点都被作为过中间顶点，算法结束
AOV和AOE网
- AOV网是顶点表示活动的网络，用于确定任务的执行顺序，确保先完成前置任务，即拓补排序问题。AOV网中不能有环。
- AOE网是边表示活动的网络。用拓扑排序来帮助确定活动的顺序，然后再计算每个活动的最早开始时间和最晚开始时间，找出那些没有机动时间的活动，也就是关键活动，这些活动组成的路径就是关键路径
拓补排序
问题
步骤：
- 在有向图中选一个没有被指向的顶点输出
- 删除该顶点和之前从它出发的线
- 重复上面步骤，直到所有顶点都已经输出，或者已经不存在没有被指的节点
- 如上图，可以按序号大小在图中找一个没有被指的顶点 C1，输出C1
- 删除C1和C1发出的线C1–>C4,C1–>C2,C1–>C3,C1–>C12
- 重复上面步骤…
拓补排序的应用：如果一个图的拓补序列不包含图的所有节点，说明该图里面有环
关键路径
关键路径：从起点到重点路径长度最长的路径
问题：
上表用图AOE网表示，如下：
事件和活动：
- 事件：像vn这样的在AOE网中的顶点为事件，是完成某个任务的时间点
- 活动：像A这样的在AOE网中的边为活动，是具体要做的任务，边上有数字表示任务所需的时间
- 活动是完成时间具体的动作，事件是这些动作完成的时间点
求关键路径的四个重要量：
- ve：事件的最早发生时间
- vl：事件的最迟发生时间
- e：活动的最早开始时间
- l：活动的最迟开始时间
关系：
即：
(1) 活动的最早开始时间 = 该活动前面发生的事件的最早发生时间
(2) 该活动的最晚开始时间 + 该活动的持续时间 = 该活动后面发生的事件的最晚发生时间
关键活动：关键路径上的活动，即 最早开始时间和最迟开始时间相同的(e(i)==l(i)) 活动
求关键路径：
查找❗
概念
- 查找是指在一个数据集合（如数组、链表、树、图等）中，根据给定的条件（如关键字、值或属性）找到目标元素的过程
- 若在查找的同时对表做修改操作（如插入和删除），则相应的表称之为动态查找表；否则称之为静态查找表。
- 平均查找长度ASL：是指在所有可能的查找情况下，查找目标元素所需的比较次数的平均值
线性表查找
顺序查找
定义：从数据集合的第一个元素开始，逐个比较，直到找到目标元素或遍历完整个集合。
适用场景：适用于无序数据集合。
顺序查找的实现：
typedef int KeyType; //指定关键字的数据类型为int
typedef struct
{ KeyType key; //KeyType为关键字的数据类型
InfoType data; //其他数据项
} RecType; //查找顺序表元素类型
int SeqSearch(RecType R[],int n,KeyType k)
{ int i=0;
while (i<n && R[i].key!=k) //从表头往后找
i++;
if (i>=n) //未找到返回0
return 0;
else
return i+1; //找到返回逻辑序号i+1
}
折半查找
定义：在有序数据集合中，通过不断将查找范围缩小一半来快速定位目标元素。折半查找也称为二分查找。
适用场景：适用于有序数组或列表。
二分查找过程可用二叉判定树来描述，把当前查找区间的中间位置上的元素作为根，左子表和右子表中的元素分别作为根的左子树和右子树
折半查找成功的平均查找长度 = (所有 相同查找频率的内部节点的个数 X 频率 之和) / 内部节点数
折半查找失败的平均查找长度 = (所有 相同查找频率的外部节点的个数 X 频率 之和) / 2外部节点数
树表查找
- 以二叉树或其他树作为查找表的组织形式，称为树表。
- 树表主要采用链式存储结构，不仅适合于查找，也适合于插入和删除操作，属于动态查找表。
二叉排序树
特征：
- 左子树永远小于根节点，右子树永远大于根节点
- 最左下节点最小，最右下节点最大
- 二叉排序树的中序序列是一个递增有序序列
二叉排序树的插入：
查找元素：
删除元素：
以下图为例：
- 被删除的结点是叶子结点：直接删去该结点。
- 被删除的结点只有左子树，用其左孩子替换它
- 被删除的结点只有右子树，用其右孩子替换它
- 被删除的结点既有左子树，也有右子树，以其中序前驱值替换之（值替换） ，然后再删除该前驱结点。
得到：
平均查找长度：
平衡二叉树*
- 平衡二叉树就是任何子树的高度差都在没有超过1的树
- 平衡二叉树就像一棵保持身体平衡的树，它的左右两边高度差不多
哈希表
概念：
哈希表是一种高效的数据结构，用于存储和查找键值对，其核心思想是通过哈希函数将键转换为数组的索引，从而实现快速的插入、删除和查找操作。
特点：
- 插入和删除：平均时间复杂度为O(1)，通过哈希函数可以直接定位存储位置。
- 查找：同样具有O(1)的平均时间复杂度。
构造哈希方法
1、直接定址法
- 哈希函数h(k)为：h(k) = a*k+c
2、除留余数法
- 哈希函数h(k)为：h(k)=k mod p (mod为求余运算，p≤m)
处理冲突
如果你去看电影，你发现你的位置被人坐了，怎么办？(哈希冲突)
一种方法就是找一个空位置坐，直到你有位置坐(开放定址法)；
另外一种方法就是直接坐他身上(链地址法)！
- 哈希冲突：两个元素的关键字不同，而对应的哈希函数值（存储地址）相同
- 例如使用前面的构造方法，多个关键字被填到了相同的格子，这就是发生了哈希冲突
1、开放定址法
冲突时找一个新的空闲的哈希地址。
两种方法：
- 线性探测：冲突时直接往后面移动一位，一直移动，直到找到空位
- 二次探测法：
- 冲突时先往后面移动一位，
- 如果没找到，在往前移动一位，
- 如果没找到，就向后移动i2位，即向后22移动4位
- 如果没找到，就向前移动i2位，即向前22移动4位
- 以此类推，直到找到空位
线性探测法：
二次探测法：
哈希表的平均查找效率ASL：
探索次数就是找位置所用次数
ASL成功 = 所有关键字k的探索次数之和 / 关键字个数
ASL不成功 = 哈希表每个下标对应的探索次数之和 / 哈希表长度
2、链地址法
拉链法是把所有发生冲突的关键词用单链表链接起来的方法。
需要查找1次的关键字有：54,29,43,31,46,60,74,88,77共9个；需要查找两次的有：16,90共2个；共11个关键字
ASL成功 = 所有关键字k的探索次数之和 / 关键字个数
= (9×1+2×2) / 11 = 13/11 = 1.182
查找地址为012的值需要的**次数为1**的有2,4,5,7,8,9,10共**7个**；**次数为2**的有3,12共**2个**，012；共13个地址
ASL不成功 = 哈希表每个下标对应的探索次数之和 / 哈希表长度
= (1×7+2×2) / 13 = 11/13 =0.846
排序
TODO 后续补充