halo~我是bay_Tong桐小白
本文内容是桐小白个人对所学知识进行的总结和分享，知识点会不定期进行编辑更新和完善，了解最近更新内容可参看更新日志，欢迎各位大神留言、指点
数据结构总体综合概述
【更新日志】
最近更新：
- 暂无编辑内容，持续更新中……
计算机统考408考纲要求
2021计算机统考408考纲数据结构学科考察目标
- 掌握数据结构的基本概念、基本原理和基本方法
- 掌握数据结构的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析
- 能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力
2021计算机统考408数据结构考纲变动情况
综述
数据结构：计算机存储、组织数据的方式
不同的数据结构具有各自对应的适用场景，旨在降低各种算法计算的时间与空间复杂度，达到最佳的任务执行效率
基本分类：
线性数据结构：非空集；仅有一个开始和一个终端；所有结点都最多只有一个直接前驱和一个直接后继。【简单说即逻辑关系上一对一】
非线性数据结构：非空集；每个结点可能有多个直接前驱或多个直接后继。【简单说即逻辑关系上一对多或多对多】
常见线性数据结构
数组
数组：相同类型的元素存储于连续内存空间的数据结构，可通过数组下标随机存取，数组大小固定
可变数组：基于数组和扩容机制实现，相比普通数组更加灵活。常用操作有：访问元素、添加元素、删除元素
//C
int array[1] = {0};
//添加元素并扩充数组大小
array = (int*)realloc(array,sizof(int)*5);
array[1] = 10;
/* realloc()函数语法：
指针名=（数据类型*）realloc（要改变内存大小的指针名，新的大小）
对于新申请的数组大小，如果新的大于原内存大小，则新分配部分不会被初始化；如果新的大小小于原内存大小，可能会导致数据丢失
头文件：#include <stdlib.h> 有些编译器需要#include <malloc.h>
*/
//C++
vector<int> array;
//向尾部添加元素
array.push_back(10);
链表
链表：以结点为单位，每个数据元素除存储自身信息外还需存储它的直接前驱或直接后继的地址信息
//C
struct ListNode {
int data; // 结点数据
ListNode* next; // 后继结点地址
};
struct ListNode* n1 = (struct ListNode*)calloc(1,sizeof(struct ListNode));
struct ListNode* n2 = (struct ListNode*)calloc(1,sizeof(struct ListNode));
struct ListNode* n3 = (struct ListNode*)calloc(1,sizeof(struct ListNode));
n1->data = 1; n1->next = n2;
n2->data = 10; n2->next = n3;
n3->data = 100; n3->next = NULL;
//C++
struct ListNode {
int data; // 结点数据
ListNode* next; // 后继结点地址
ListNode(int x) : data(x) , next(NULL) {} //构造函数
};
ListNode* n1 = new ListNode(1);
ListNode* n2 = new ListNode(10);
ListNode* n3 = new ListNode(100);
n1->next = n2; n2->next = n3;
【数组与链表详细知识内容可见本栏文章《线性表总结——基本知识要点汇总》】
栈
栈：只在一端（栈顶）做插入删除操作（称为入栈与出栈）的数据结构，具有先进后出【FILO】，后进先出【LIFO】的特点。可以由数组或链表实现
//C++
stack<char> s;
s.push('A'); s.push('B'); s.push('C');
s.pop();
队列
队列：只在一端（队尾）插入在另一端（队头）删除（称为入队与出队）的数据结构，具有先进先出【FIFO】，后进后出【LILO】的特点。可以由数组或链表实现
//C++
queue<int> q;
q.push(0); q.push(1); q.push(2); q.push(3); q.push(4); q.push(5);
q.pop();
【栈与队列详细知识内容可见本栏文章《栈和队列总结——基本知识要点汇总》】
常见非线性数据结构
树
常用的树型结构为二叉树，每个结点包含结点值、左孩子结点地址、右孩子结点地址
//C
struct TreeNode {
char data; // 结点值
TreeNode* left; // 左孩子结点
TreeNode* right; // 右孩子结点
};
struct TreeNode* n1 = (struct TreeNode*)calloc(1, sizeof(struct TreeNode));
struct TreeNode* n2 = (struct TreeNode*)calloc(1, sizeof(struct TreeNode));
struct TreeNode* n3 = (struct TreeNode*)calloc(1, sizeof(struct TreeNode));
struct TreeNode* n4 = (struct TreeNode*)calloc(1, sizeof(struct TreeNode));
struct TreeNode* n5 = (struct TreeNode*)calloc(1, sizeof(struct TreeNode));
n1->data = 'A'; n1->left = n2; n1->right = n3;
n2->data = 'B'; n2->left = n4; n2->right = n5;
n3->data = 'C'; n3->left = NULL; n3->right = NULL;
n4->data = 'D'; n4->left = NULL; n4->right = NULL;
n5->data = 'E'; n5->left = NULL; n5->right = NULL;
//C++
struct TreeNode {
char data; // 节点值
TreeNode* left; // 左子节点
TreeNode* right; // 右子节点
TreeNode(int x) : data(x), left(NULL), right(NULL) {}//构造函数
};
TreeNode* n1 = new TreeNode('A');
TreeNode* n2 = new TreeNode('B');
TreeNode* n3 = new TreeNode('C');
TreeNode* n4 = new TreeNode('D');
TreeNode* n5 = new TreeNode('E');
n1->left = n2; n1->right = n3;
n2->left = n4; n2->right = n5;
【树型结构详细知识内容可见本栏文章《树和二叉树总结——基本知识要点汇总》】
堆
堆：一种基于完全二叉树的数据结构，可使用数组实现。堆分为大顶堆和小顶堆，大（小）顶堆：任意节点的值不大于（小于）其父节点的值
以 leetcode 《图解算法数据结构》中的例子为例：
如下图所示，为包含 1, 4, 2, 6, 8 元素的小顶堆。将堆（完全二叉树）中的结点按层编号，即可映射到右边的数组存储形式
//C++
// 初始化小顶堆
priority_queue<int, vector<int>, greater<int>> heap;
// 元素入堆
heap.push(1);
heap.push(4);
heap.push(2);
heap.push(6);
heap.push(8);
// 元素出堆（从小到大）
heap.pop(); // -> 1
heap.pop(); // -> 2
heap.pop(); // -> 4
heap.pop(); // -> 6
heap.pop(); // -> 8
作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/50e446/
来源：力扣（LeetCode）
散列表
散列表：通过利用 Hash 函数将指定的键（key）映射至对应的值（value），以实现高效的元素查找
以 leetcode 《图解算法数据结构》中的例子为例：
设想一个简单场景：小力、小特、小扣的学号分别为10001、10002、10003；现需求从「姓名」查找「学号」
可通过建立姓名为 key ，学号为 value 的散列表实现此需求
作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/50e446/
来源：力扣（LeetCode）
图
图：由节点（顶点）和边组成，每条边连接一对顶点
邻接矩阵表示法：二维数组来表示，如G[ i ][ j ]表示 i 到 j 的一条边，无权图中若有边则G[ i ][ j ]的值为1否则为0，有权图中若有边则该值可以是边的权重，若无边则为无穷大，以一个很大的数来表示
//C++
int vertices[5] = { 0, 1, 2, 3, 4 };
int edges[5][5] = { {0, 1, 0, 1, 0},
{1, 0, 1, 0, 1},
{0, 1, 0, 1, 1},
{1, 0, 1, 0, 0},
{0, 1, 1, 0, 0} };
邻接表表示法：用一个数组存储图中所有顶点，每一个顶点（数组单元）有一个单链表，存储所有和它关联的边
【图结构详细知识内容可见本栏文章《图的总结——基本知识要点汇总》】
持续更新中……
我是桐小白，一个摸爬滚打的计算机小白