# cpp数据结构与算法

**Repository Path**: wei13013451000/Cpp-Data-Structures

## Basic Information

- **Project Name**: cpp数据结构与算法
- **Description**: c++数据结构与算法
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 1
- **Created**: 2024-09-23
- **Last Updated**: 2025-01-09

## Categories & Tags

**Categories**: Uncategorized

**Tags**: Cpp, 数据结构, 算法

## README

[数据结构笔记地址](https://ghjayce.github.io/p/book/080901/02142/chapter2/)
[数据结构目录](https://blog.csdn.net/weixin_30051655/article/details/118951545)
[c++笔记地址](https://www.yuque.com/unityalvin/self-study/hlfup01gu2h9a6ns)
[华夏大地视频](https://www.bilibili.com/video/BV1C541127Nj?p=8&vd_source=f3f44d906db1a0fb2477daf8ce30918a)
[王道数据结构](https://www.bilibili.com/video/BV1b7411N798/?p=12&vd_source=f3f44d906db1a0fb2477daf8ce30918a)
[数据结构代码(C语言版)](https://www.bilibili.com/video/BV1qK411n75U?p=11&vd_source=f3f44d906db1a0fb2477daf8ce30918a)
[配合题目的视频](https://www.bilibili.com/video/BV1nx4y1K7nT?p=15&spm_id_from=pageDriver&vd_source=f3f44d906db1a0fb2477daf8ce30918a)

# 一章.概论

## 概览

![image-20240925151804433](README/image-20240925151804433.png)

## 第一节.引言
## 第二节.基本概念和术语
## 第三节.算法及描述
## 第四节.算法分析
## 典型考题

![image-20240925152922016](README/image-20240925152922016.png)

# 二章.线性表

![image-20240925163150649](README/image-20240925163150649.png)

![image-20240925164857513](README/image-20240925164857513.png)

![image-20240926104318900](README/image-20240926104318900.png)

## 本章概览
## 第一节-线性表的基本概念

![image-20241016144908557](README/image-20241016144908557.png)

### 1.定义

![image-20241016143622637](README/image-20241016143622637.png)

### 2.基本运算

![image-20241016144527430](README/image-20241016144527430.png)

## 第二节-线性表的顺序存储(顺序表)

```c
/*
顺序表
概念
顺序存储：将结点依次存放在计算机内存中一组连续的存储单元中，逻辑结构中相邻的结点它的存储位置也相邻。
顺序表：用顺序存储实现的线性表，一般使用数组来表示顺序表。
 */
#include <stdio.h>

#define Maxsize 10

typedef struct
{
	int num;      // 学号
	char name[8]; // 姓名
	int age;      // 年龄
} DataType;       // 定义节点类型

typedef struct
{
	DataType data[Maxsize]; // 存放数据的数组
	int length;             // 顺序表实际长度
} SeqList;                  // 顺序表的类型

//插入元素
void InsertSeqList(SeqList* L, DataType data, int no)
{
	// 判断满了不可以插入
	if (L->length >= Maxsize)
	{
		printf("表满了,不可以再插入!\n");
		return;
	}
	if (no < 1 || no > L->length + 1)
	{
		printf("插入位置不合法!\n");
	}
	for (int i = L->length; i >= no; i--)
	{
		L->data[i] = L->data[i - 1];
	}
	L->data[no - 1] = data;
	L->length++;

}

//删除元素
void deleteSeqList(SeqList* L, int no)
{
	// 判断删除位置是否合法
	if (no < 1 || no > L->length)
	{
		printf("删除位置不合法!\n");
		return;
	}
	for (int i = no; i < L->length; i++)
	{
		L->data[i - 1] = L->data[i];
	}
	L->length--;

}

//定位元素位置
int locateSeqList(SeqList* L, DataType data) {
	for (int i = 0; i < L->length; i++) {
		if (L->data[i].num == data.num) {
			return i + 1;
		}
	}

	return 0;
}
//打印元素
void PrintSeqList(SeqList* L)
{
	if (L->length == 0)
	{
		printf("顺序表为空!\n");
		return;
	}
	for (int i = 0; i < L->length; i++)
	{
		printf("学号: %d, 姓名: %s, 年龄: %d\n", L->data[i].num, L->data[i].name, L->data[i].age);
	}

}
int main()
{
	// 定义一个顺序表
	SeqList list;
	list.length = 0;
	DataType student1 = { 1001, "李四1", 21 };
	DataType student2 = { 1002, "王五2", 22 };
	DataType student3 = { 1003, "王五3", 23 };
	DataType student4 = { 1004, "王五4", 24 };
	DataType student5 = { 1005, "王五5", 25 };
	DataType student6 = { 1006, "王五6", 26 };
	DataType student7 = { 1007, "王五7", 27 };
	DataType student8 = { 1008, "王五8", 28 };
	DataType student9 = { 1009, "王五9", 29 };
	DataType student10 = { 10010, "王五10", 20 };

	// 插入元素
	InsertSeqList(&list, student1, 1);
	InsertSeqList(&list, student2, 2);
	InsertSeqList(&list, student3, 3);

	// 打印顺序表中的所有数据
	PrintSeqList(&list);

	//定位元素位置
	int res = locateSeqList(&list, student1);
	printf("res=%d\n", res);

	return 0;
}

```



## 第三节-线性表的链接存储(链表)



### 1.单链表

![image-20241016200544156](README/image-20241016200544156.png)

#### 1.单链表插入与删除

![image-20241016200838796](README/image-20241016200838796.png)

```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int DataType;
typedef struct Node
{
    DataType data;     // 数据域
    struct Node *next; // 指针域
} Node, *LinkList;

/**
 * 初始化带头结点的单链表
 */
void initListWithHead(LinkList *L)
{
    *L = (Node *)malloc(sizeof(Node));
    if (*L == NULL)
    {
        fprintf(stderr, "内存分配失败\n");
        exit(1);
    }
    (*L)->next = NULL;
}

/**
 * 初始化不带头结点的单链表
 */
void initListWithoutHead(LinkList *L)
{
    *L = NULL; // 不带头结点的链表初始为空
}

/**
 * 带头结点的单链表按照位序插入元素,时间复杂度O(n)
 */
bool insertListWithHead(LinkList *L, int i, DataType e)
{
    if (i < 1)
    {
        return false;
    }

    int j = 0;
    Node *p = *L;

    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }

    if (p == NULL)
    {
        return false;
    }

    Node *q = (Node *)malloc(sizeof(Node));
    if (q == NULL)
    {
        fprintf(stderr, "内存分配失败\n");
        return false;
    }

    q->data = e;
    q->next = p->next;
    p->next = q;

    return true;
}

/**
 * 不带头结点的单链表按照位序插入元素,时间复杂度O(n)
 */
bool insertListWithoutHead(LinkList *L, int i, DataType e)
{
    if (i < 1)
    {
        return false;
    }
    //===============此处有区别start====================
    if (i == 1)
    {
        Node *q = (Node *)malloc(sizeof(Node));
        if (q == NULL)
        {
            fprintf(stderr, "内存分配失败\n");
            return false;
        }
        q->data = e;
        q->next = *L;
        *L = q;
        return true;
    }

    int j = 1;
    //==============end=====================
    Node *p = *L;

    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }

    if (p == NULL)
    {
        return false;
    }

    Node *q = (Node *)malloc(sizeof(Node));
    if (q == NULL)
    {
        fprintf(stderr, "内存分配失败\n");
        return false;
    }

    q->data = e;
    q->next = p->next;
    p->next = q;

    return true;
}

/**
 * 单链表后插操作,在p节点之后插入元素e,时间复杂度O(1)
 */
bool InsertNextNode(Node *p, DataType e)
{
    if (p == NULL)
    {
        return false;
    }
    Node *s = (Node *)malloc(sizeof(Node));
    if (s == NULL)
    {
        printf("分配内存失败\n");
        return false;
    }
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}
/**
 * 单链表前插操作,在p节点之前插入元素e,时间复杂度O(1)
 */
bool InsertPriorNode(Node *p, DataType e)
{
    if (p == NULL)
    {
        return false;
    }
    Node *s = (Node *)malloc(sizeof(Node));
    if (s == NULL)
    {
        return false;
    }
    s->next = p->next;
    p->next = s;
    s->data = p->data; // 交换数据
    p->data = e;       // 交换数据
    return true;
}

/**
 * 单链表前插操作,在p节点之前插入节点s,时间复杂度O(1)
 */
bool InsertPriorNode1(Node *p, Node *s)
{
    if (p == NULL || s == NULL)
    {
        return false;
    }
    s->next = p->next;
    p->next = s;
    DataType temp;
    temp = s->data;
    s->data = p->data;
    p->data = temp;
    return true;
}

/**
 * 按位序删除带头节点,最坏,平均时间复杂度O(n),最好时间复杂度O(1)
 */
bool ListDelete(LinkList *L, int i, DataType *e)
{
    if (i < 1)
    {
        return false;
    }
    int j = 0;    // 指针位序
    Node *p = *L; // p指针指向头结点
    while (p != NULL && j < i - 1)
    { // 找到要删除的节点的前一个节点
        p = p->next;
        j++;
    }
    if (p == NULL)
    {
        return false;
    }
    if (p->next == NULL)
    {
        return false;
    }
    Node *q = p->next; // q指向被删除的节点
    *e = q->data;      // 把要删除的数据赋值给传进来的e

    p->next = q->next; // 要删除的节点的 前一个节点连接后一个节点

    free(q); // 释放要删除的q节点

    return true;
}

/**
 * 删除指定节点
 */
bool DeleteNode(Node *p)
{
    if (p == NULL)
    {
        return false;
    }
    Node *q = p->next; // 令q指向p的后继结点
    p->data = q->data; // 后一个节点的值赋值给要删除的节点
    p->next = q->next; // 上一个节点指向删除节点的后一个节点
    free(q);           // 释放q
    return true;
}

/**
 * 打印单链表
 */
void printList(LinkList L)
{
    Node *current = L;
    while (current != NULL)
    {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

int main()
{
    LinkList L1, L2;

    // 初始化带头结点的链表
    initListWithHead(&L1);
    // 测试插入函数
    insertListWithHead(&L1, 1, 100);
    insertListWithHead(&L1, 2, 200);
    insertListWithHead(&L1, 3, 300);
    insertListWithHead(&L1, 1, 1100);

    printf("带头结点的链表:\n");
    printList(L1->next); // 从头结点的下一个节点开始打印
    int e;
    ListDelete(&L1, 5, &e);
    printf("带头结点的链表删除后:\n");
    printf("e: %d\n", e);
    printList(L1->next); // 从头结点的下一个节点开始打印

    // 初始化不带头结点的链表
    initListWithoutHead(&L2);
    // 测试插入函数
    insertListWithoutHead(&L2, 1, 100);
    insertListWithoutHead(&L2, 2, 200);
    insertListWithoutHead(&L2, 3, 300);
    insertListWithoutHead(&L2, 1, 1100);

    printf("不带头结点的链表:\n");
    printList(L2);

    return 0;
}
```

#### 2.单链表查找

![image-20241017120314375](README/image-20241017120314375.png)

![image-20241017135237776](README/image-20241017135237776.png)

```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/**
 * 单链表查找
 */

typedef int DataType;

typedef struct Node
{
    DataType data;     // 数据域
    struct Node *next; // 指针域
} Node, *LinkList;

// 初始化带头结点单链表
void InitList(LinkList *L)
{
    *L = (Node *)malloc(sizeof(Node));
    (*L)->next = NULL;
}
// 按位置查找节点 平均时间复杂度O(n)
Node *getNode(LinkList L, int i)
{
    if (i < 0)
    {
        return NULL;
    }
    Node *p = L;
    int j = 0;
    while (p != NULL && j < i)
    {
        p = p->next;
        j++;
    }

    return p;
}
/**
 * 单链表后插操作,在p节点之后插入元素e,时间复杂度O(1)
 */
bool InsertNextNode(Node *p, DataType e)
{
    if (p == NULL)
    {
        return false;
    }
    Node *s = (Node *)malloc(sizeof(Node));
    if (s == NULL)
    {
        printf("分配内存失败\n");
        return false;
    }
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}
// 带头结点的单链表按照位序插入元素
bool insertListWithHead(LinkList *L, int i, DataType e)
{
    if (i < 1)
    {
        return false;
    }

    // Node *p = *L;
    // int j = 0;
    // while (p != NULL && j < i - 1)
    // {
    //     p = p->next;
    //     j++;
    // }

    Node *p = getNode(*L, i - 1); // 找到第i-1个节点

    // if (p == NULL)
    // {
    //     return false;
    // }

    // Node *s = (Node *)malloc(sizeof(Node));
    // s->data = e;
    // s->next = p->next;
    // p->next = s;
    return InsertNextNode(p, e); // 后插操作
}
// 按值查找节点
Node *locateData(LinkList L, DataType e)
{
    Node *p = L->next; // 从第一个节点开始查找
    while (p != NULL && p->data != e)
    {
        p = p->next;
    }
    return p;
}
// 求表长度
int listLength(LinkList L)
{
    int len = 0;
    Node *p = L;
    while (p->next != NULL)
    {
        p = p->next;
        len++;
    }
    return len;
}
// 打印单链表
void PrintList(LinkList L)
{
    Node *p = L;
    while (p != NULL)
    {
        printf("%d -> ", p->data);
        p = p->next;
    }
    printf("NULL\n");
}
int main()
{
    LinkList L1;
    InitList(&L1);
    // 测试插入函数
    insertListWithHead(&L1, 1, 100);
    insertListWithHead(&L1, 2, 200);
    insertListWithHead(&L1, 3, 300);
    insertListWithHead(&L1, 1, 1100);

    printf("带头结点的链表:\n");
    PrintList(L1->next);

    int i = 3; // 尝试查找一个不存在的节点
    Node *node = getNode(L1, i);
    if (node != NULL)
    {
        printf("找到的第 %d 个节点数值为 : %d\n", i, node->data);
    }
    else
    {
        printf("第 %d 个节点不存在 (NULL)\n", i);
    }

    int data = 200;
    Node *node2 = locateData(L1, data);
    if (node2 != NULL)
    {

        printf("查找值为:%d的节点的值为:%d\n", data, node2->data);
    }
    else
    {
        printf("查找值为:%d的节点未找到\n", data);
    }

    // 链表长度
    int length = listLength(L1);
    printf("单链表长度为: %d\n", length);

    return 0;
}

```

#### 3.单链表的建立

![image-20241017135524799](README/image-20241017135524799.png)

![image-20241017145915459](README/image-20241017145915459.png)

```c
/**
尾插法建立单链表:
初始化单链表
设置变量length 记录链表长度
While 循环{每次取一个数据元素e;Listinsert (L, length+1, e)插到尾部;length++;
头插法建立单链表:
就是每次都在头结点后面插入元素
 */
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

typedef int DataType;
typedef struct Node
{
    DataType data;
    struct Node *next;
} Node, *LinkList;

// 尾插法建立单链表
LinkList List_TailInsert(LinkList *L)
{
    DataType x;
    *L = (LinkList)malloc(sizeof(Node)); // 建立头结点
    Node *s, *r = *L;                    // r为表尾指针
    scanf("%d", &x);                     // 输入节点的值
    while (x != 9999)
    {
        s = (Node *)malloc(sizeof(Node));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x); // 输入节点的值
    }
    r->next = NULL;
    return *L;
}
// 头插法建立单链表
LinkList List_HeadInsert(LinkList *L)
{
    Node *s;
    DataType x;
    *L = (Node *)malloc(sizeof(Node)); // 创建头结点
    (*L)->next = NULL;                 // 初始化头结点
    scanf("%d", &x);
    while (x != 9999)
    {
        s = (Node *)malloc(sizeof(Node)); // 创建新结点
        s->data = x;
        s->next = (*L)->next;
        (*L)->next = s;
        scanf("%d", &x);
    }
    return *L;
}
// 链表逆置
LinkList ReverseList(LinkList L)
{
    // 取出每个节点的值用头插法插入链表
    if (L == NULL)
    {
        return NULL;
    }
    Node *s, *p = L;
    LinkList newL;
    newL = (Node *)malloc(sizeof(Node)); // 创建头结点
    newL->next = NULL;
    while (p != NULL)
    {
        // printf("%d ", p->data);
        //=======================
        s = (Node *)malloc(sizeof(Node)); // 创建新结点
        s->data = p->data;
        s->next = newL->next;
        newL->next = s;
        //=======================
        p = p->next;
    }
    return newL;
}
// 打印链表
void printList(LinkList L)
{
    Node *p = L;
    while (p != NULL)
    {
        printf("%d -> ", p->data);

        p = p->next;
    }
    printf("NULL\n");
}
int main()
{
    LinkList L1, L2;
    List_TailInsert(&L1);
    printList(L1->next);
    // List_HeadInsert(&L2);
    // printList(L2->next);

    printf("链表逆置\n");
    L2 =  ReverseList(L1->next);
    printList(L2->next);
    return 0;
}
```

#### 4.链表逆置

```c
// 链表逆置
LinkList ReverseList(LinkList L)
{
    // 取出每个节点的值用头插法插入链表
    if (L == NULL)
    {
        return NULL;
    }
    Node *s, *p = L;
    LinkList newL;
    newL = (Node *)malloc(sizeof(Node)); // 创建头结点
    newL->next = NULL;
    while (p != NULL)
    {
        // printf("%d ", p->data);
        //=======================
        s = (Node *)malloc(sizeof(Node)); // 创建新结点
        s->data = p->data;
        s->next = newL->next;
        newL->next = s;
        //=======================
        p = p->next;
    }
    return newL;
}
```

### 2.双链表

![image-20241017152038058](README/image-20241017152038058.png)

![image-20241017162238240](README/image-20241017162238240.png)

![image-20241017152133003](README/image-20241017152133003.png)

#### 1.双链表插入

![image-20241017161406739](README/image-20241017161406739.png)

![image-20241017162215719](README/image-20241017162215719.png)

### 3.循环链表

![image-20241017162506284](README/image-20241017162506284.png)

![image-20241017162547468](README/image-20241017162547468.png)

### 4.循环双链表

### 5.静态链表

![image-20241017163543431](README/image-20241017163543431.png)

![image-20241017163847062](README/image-20241017163847062.png)

![image-20241017164315907](README/image-20241017164315907.png)

![image-20241017164348051](README/image-20241017164348051.png)

## 第四节-其他运算在单链表上的实现
## 第五节-其他链表
## 第六节-顺序实现与链接实现的比较
## 本章典型考题
# 三章.栈,队列和数组
## 本章概览



## 第-节-栈

![image-20241018125701810](README/image-20241018125701810.png)

#### 1.栈的定义

![image-20241018125143037](README/image-20241018125143037.png)

![image-20241018125311542](README/image-20241018125311542.png)

#### 2.栈的基本操作

![image-20241018125511012](README/image-20241018125511012.png)

#### 3.顺序栈

![image-20241018125810005](README/image-20241018125810005.png)

![image-20241018133526473](README/image-20241018133526473.png)

```c
/**
 *
 */
#include <stdio.h>
#include <stdbool.h>

#define MaxSize 10 // 定义栈中元素的最大个数
typedef int DataType;
typedef struct
{
    DataType data[MaxSize]; // 静态数组存放栈中元素
    int top;                // 栈顶指针
} SqStack;

// 初始化栈
void InitStack(SqStack *s)
{
    s->top = -1; // 初始化栈顶指针
}

// 判断栈空
bool StackEmpty(SqStack s)
{
    if (s.top == -1)
    {
        return true;
    }
    else
    {
        return false;
    }
}

// 进栈
bool Push(SqStack *s, DataType data)
{
    if (s->top == MaxSize - 1)
    { // 栈满
        return false;
    }
    s->data[++s->top] = data; // 指针+1,新元素入栈
    return true;
}
// 出栈
bool Pop(SqStack *s, DataType *data)
{
    if (s->top == -1)
    {
        return false; // 空栈
    }

    *data = s->data[s->top--];
    return true;
}

// 获得栈顶元素
bool getStackTop(SqStack *s, DataType *data)
{
    if (s->top == -1)
    {
        return false; // 空栈
    }

    *data = s->data[s->top];
    return true;
}

int main()
{
    SqStack s;
    InitStack(&s);
    Push(&s, 10);
    Push(&s, 20);
    Push(&s, 30);
    // 获得栈顶元素
    DataType data;
    Pop(&s, &data);
    getStackTop(&s, &data);
    printf("栈顶元素为: %d\n", data);
    return 0;
}
/**
 *为什么入栈2次栈顶元素还是10呢?
 */
```



#### 4.链式栈

![image-20241018133624781](README/image-20241018133624781.png)



![image-20241018134410286](README/image-20241018134410286.png)

#### 5.栈在括号匹配中的应用

![image-20241018171259627](README/image-20241018171259627.png)

```c
//{[(([{}]))]}
// 匹配括号是否成对

#include <stdio.h>
#include <stdbool.h>

// 定义一个顺序栈====================================
#define MaxSize 20
typedef char DataType;
typedef struct
{
    DataType data[MaxSize];
    int top;
} Stack;

// 空栈
bool isEmpty(Stack *s)
{
    if (s->top == -1)
    {
        return true;
    }
    else
    {
        return false;
    }
}
// 进栈
bool push(Stack *s, DataType data)
{
    if (s->top == MaxSize - 1)
    {
        return false; // 栈已经满了
    }
    s->data[++s->top] = data;
    return true;
}
// 出栈
bool pop(Stack *s, DataType *data)
{
    if (s->top == -1)
    {
        return false; // 栈为空
    }
    *data = s->data[s->top--];

    return true;
}
// 获得栈顶元素
DataType getTopData(Stack *s)
{
    if (s->top == -1)
    {
        return false; // 栈为空
    }
    return s->data[s->top];
}

// 定义处理括号函数
bool bracketCheck(DataType str[])
{
    // 创建栈,初始化
    Stack s;
    s.top = -1;
    int i = 0;
    DataType temp;
    while (str[i] != '\0')
    {
        if (str[i] == '{' || str[i] == '[' || str[i] == '(')
        {
            push(&s, str[i]);
        }
        else
        {
            pop(&s, &temp);
            if (temp == '{' && str[i] != '}')
            {
                return false;
            }
            if (temp == '[' && str[i] != ']')
            {
                return false;
            }
            if (temp == '(' && str[i] != ')')
            {
                return false;
            }
        }
        i++;
    }
    return isEmpty(&s);
}

int main()
{
    DataType str[] = "({[({})]})";
    if(bracketCheck(str)==1){
        printf("匹配成功!");
    }else{
        printf("匹配失败!");
    }
    return 0;
}
```

#### 6.栈在表达式求值中的应用

![image-20241018171802952](README/image-20241018171802952.png)

```c

```





## 第二节-队列

![image-20241018140936126](README/image-20241018140936126.png)

![image-20241018141047050](README/image-20241018141047050.png)

![image-20241018141145907](README/image-20241018141145907.png)

![image-20241018141203093](README/image-20241018141203093.png)

#### 1.顺序循环队列



![image-20241018154834721](README/image-20241018154834721.png)

![image-20241018163811850](README/image-20241018163811850.png)

```c
#include <stdio.h>
#include <stdbool.h>

#define MaxSize 10
typedef int DataType;
typedef struct
{
    DataType data[MaxSize];
    int front, real; // 队头指针,队尾指针
} SqQueue;

// 初始化
void InitQueue(SqQueue *Q)
{
    Q->front = Q->real = 0;
}
// 判空
bool isEmpty(SqQueue Q)
{
    if (Q.front == Q.real)
    {
        return true;
    }
    return false;
}
// 入队
bool EnQueue(SqQueue *Q, DataType data)
{
    if ((Q->real + 1) % MaxSize == Q->front)
    {
        return false; // 队列已满
    }
    Q->data[Q->real] = data;
    Q->real = (Q->real + 1) % MaxSize;
    return true;
}

// 出队
bool DeQueue(SqQueue *Q, DataType *data)
{
    if (Q->real == Q->front)
    {
        return false; // 队空
    }
    *data = Q->data[Q->front];
    Q->front = (Q->front + 1) % MaxSize;
    return true;
}
// 获取队头元素
DataType getQueue(SqQueue *Q)
{
    if (Q->front == Q->real)
    {
        return -1;
    }
    return Q->data[Q->front];
}
// 队列元素个数
int length(SqQueue *Q)
{
    return (Q->real + MaxSize - Q->front) % MaxSize;
}

int main()
{
    SqQueue Q;
    InitQueue(&Q);
    EnQueue(&Q, 11);
    EnQueue(&Q, 22);
    EnQueue(&Q, 33);
    EnQueue(&Q, 44);
    DataType data;
    DeQueue(&Q, &data);
    printf("出队元素: %d\n", data);
    // DeQueue(&Q, &data);
    // printf("出队元素: %d\n", data);
    if (isEmpty(Q) == 1)
    {
        printf("队列为空\n");
    }
    else
    {
        printf("队列满\n");
    }
    DataType d = getQueue(&Q);
    printf("此时队头元素为: %d\n", d);
    int len = length(&Q);
    printf("此时队列元素个数为: %d\n", len);
    return 0;
}
```

![image-20241018170526472](README/image-20241018170526472.png)

## 第三节-数组



## 本章典型考题
# 四章.树和二叉树
## 本章概览

![image-20241019172852907](README/image-20241019172852907.png)

## 第一节-树的基本概念

![image-20241020102842678](README/image-20241020102842678.png)

![image-20241020103023089](README/image-20241020103023089.png)

![image-20241020103123860](README/image-20241020103123860.png)

![image-20241020103244290](README/image-20241020103244290.png)

![image-20241020103452679](README/image-20241020103452679.png)

![image-20241020103618847](README/image-20241020103618847.png)

![image-20241020103758224](README/image-20241020103758224.png)

![image-20241020104022678](README/image-20241020104022678.png)

![image-20241020104153021](README/image-20241020104153021.png)

![image-20241020105659900](README/image-20241020105659900.png)

![image-20241020110218073](README/image-20241020110218073.png)

![image-20241020110231218](README/image-20241020110231218.png)

![image-20241020110447436](README/image-20241020110447436.png)

![image-20241020110533386](README/image-20241020110533386.png)

## 第二节-二叉树

![image-20241020110554938](README/image-20241020110554938.png)

![image-20241020110856469](README/image-20241020110856469.png)

![image-20241020110931849](README/image-20241020110931849.png)

![image-20241020111643873](README/image-20241020111643873.png)

![image-20241020111721279](README/image-20241020111721279.png)

![image-20241020112005813](README/image-20241020112005813.png)

![image-20241020112412018](README/image-20241020112412018.png)

![image-20241020112515383](README/image-20241020112515383.png)

![image-20241020113737581](README/image-20241020113737581.png)

![image-20241020113914875](README/image-20241020113914875.png)

![image-20241020113945175](README/image-20241020113945175.png)

![image-20241020114831303](README/image-20241020114831303.png)

![image-20241020115029074](README/image-20241020115029074.png)

![image-20241020115226848](README/image-20241020115226848.png)



## 第三节-二又树的存储结构

### 1.二叉树顺序存储

### 2.二叉树的链式存储





## 第四节-二叉树的遍历

#### 1.递归遍历

![image-20241020140725945](README/image-20241020140725945.png)

![image-20241020140941554](README/image-20241020140941554.png)

![image-20241020141815983](README/image-20241020141815983.png)

![image-20241020142830328](README/image-20241020142830328.png)

![image-20241020143002201](README/image-20241020143002201.png)

![image-20241020143130602](README/image-20241020143130602.png)

![image-20241020143147355](README/image-20241020143147355.png)

![image-20241020143200676](README/image-20241020143200676.png)

![image-20241020143558741](README/image-20241020143558741.png)

![image-20241020143703287](README/image-20241020143703287.png)

![image-20241020144317197](README/image-20241020144317197.png)

#### 2.层次遍历

![image-20241020144900790](README/image-20241020144900790.png)

![image-20241020145052698](README/image-20241020145052698.png)

#### 3.由遍历序列构造二叉树

![image-20241020145515193](README/image-20241020145515193.png)



## 第五节-树和森林

### 1.树的存储结构



## 第六节-判定树和哈夫曼树

![image-20241021161950363](README/image-20241021161950363.png)

#### 1.带权路径长度

![image-20241021162218117](README/image-20241021162218117.png)



#### 2.哈夫曼树定义

![image-20241021162452158](README/image-20241021162452158.png)





#### 3.哈夫曼树构造

![image-20241021162541455](README/image-20241021162541455.png)

![image-20241021162612016](README/image-20241021162612016.png)

#### 4.哈弗曼编码



## 
# 五章.图
## 本章概览
## 第-节-图的基本概念
## 第二节-图的存储结构

### 1.邻接矩阵

### 2.邻接表



## 第三节-图的遍历

### 1.连通图的深度优先搜索

### 2.连通图的广度优先搜索

## 第四节-图的应用

### 1.最小生成树(最小代价树)



![image-20241021154529146](README/image-20241021154529146.png)

![image-20241021154725724](README/image-20241021154725724.png)

![image-20241021154811942](README/image-20241021154811942.png)

#### 1.prim(普里姆)算法

![image-20241021155113130](README/image-20241021155113130.png)

![image-20241021155059646](README/image-20241021155059646.png)

![image-20241021155155476](README/image-20241021155155476.png)





#### 2.kruskal(克鲁斯卡尔)算法

![image-20241021155515505](README/image-20241021155515505.png)

![image-20241021155742790](README/image-20241021155742790.png)

![image-20241021155838700](README/image-20241021155838700.png)

### 2.拓扑排序

## 本章典型考题
# 六章.查找
## 本章概览
## 第一节-基本概念



## 第二节-静态查找表

### 1.顺序表上的查找

![image-20241022140544775](README/image-20241022140544775.png)

![image-20241022154043296](README/image-20241022154043296.png)





### 2.有序表上的查找

#### 1.二分查找(折半查找)

![image-20241021170708873](README/image-20241021170708873.png)

![image-20241021171015135](README/image-20241021171015135.png)



![image-20241021171142923](README/image-20241021171142923.png)

![image-20241021171639217](README/image-20241021171639217.png)



![image-20241021172120617](README/image-20241021172120617.png)

![image-20241021172257187](README/image-20241021172257187.png)

![image-20241021172345379](README/image-20241021172345379.png)



### 3.索引顺序表上的查找(分块查找)



## 第三节-二叉排序树

![image-20241021143843684](README/image-20241021143843684.png)

![image-20241021144433054](README/image-20241021144433054.png)

![image-20241021144555803](README/image-20241021144555803.png)



![image-20241021144750047](README/image-20241021144750047.png)







## 第四节-散列表(散列查找)

![image-20241021210616976](README/image-20241021210616976.png)

![image-20241021211242473](README/image-20241021211242473.png)



![image-20241021211344911](README/image-20241021211344911.png)

![image-20241021211453731](README/image-20241021211453731.png)

![image-20241021212732312](README/image-20241021212732312.png)

![image-20241021213046906](README/image-20241021213046906.png)

![image-20241021213202665](README/image-20241021213202665.png)

![image-20241021213323770](README/image-20241021213323770.png)

![image-20241021213437361](README/image-20241021213437361.png)

![image-20241021213949876](README/image-20241021213949876.png)



## 本章典型考题
# 七章.排序
## 本章概览
## 第-节-概述
## 第二节-插入排序
## 第三节-交换排序
## 第四节-选择排序
## 第五节-归并排序

## 第六节-冒泡排序

## 第六节-快速排序

## 第六节-堆排序

## 第六节-归并排序

## 本章典型考题