【愚公系列】软考中级-软件设计师 014-数据结构（考点简介）

🏆 作者简介，愚公搬代码 🏆《头衔》：华为云特约编辑，华为云云享专家，华为开发者专家，华为产品云测专家，CSDN博客专家，CSDN商业化专家，阿里云专家博主，阿里云签约作者，腾讯云优秀博主，腾讯云内容共创官，掘金优秀博主，51CTO博客专家等。 🏆《近期荣誉》：2023年华为云十佳博主，2022年CSDN博客之星TOP2，2022年华为云十佳博主等。

🏆《博客内容》：.NET、Java、Python、Go、Node、前端、IOS、Android、鸿蒙、Linux、物联网、网络安全、大数据、人工智能、U3D游戏、小程序等相关领域知识。

🏆🎉欢迎 👍点赞✍评论⭐收藏

🚀前言

数据结构是一种组织和存储数据的方式，它涉及如何在计算机中存储和访问数据的方法和技术。数据结构可以用来解决不同类型的问题，包括搜索、排序、插入和删除等操作。常见的数据结构包括数组、链表、栈、队列、树、图等。不同的数据结构有不同的特点和适用场景，选择合适的数据结构可以提高算法的效率和性能。

🚀一、完整数据结构

🔎1.线性结构

• 线性表
• 栈和队列
• 串

🔎2.数组、矩阵和广义表

🔎3.树

• 树和二叉树的定义
• 二叉树的性质与存储结构
• 二叉树的遍历
• 线索二叉树
• 最优二叉树(哈夫曼树)
• 树和森林

🔎4.图

• 图的定义和存储
• 图的遍历
• 深度优先搜索
• 广度优先搜索
• 生成树和最小生成树
• 拓扑结构和关键路径

🔎5.查找

• 查找基本概念
• 静态查找表的查找方法
• 顺序查找
• 折半查找
• 分块查找
• 动态查找表
• 二叉排序树
• 平衡二叉树
• 哈希表

🔎6.排序

• 排序基本概念
• 简单排序
• 希尔排序

改进的插入排序

• 快速排序
• 堆排序
• 归并排序
• 基数排序
• 外部排序

🚀二、数据结构（10-12分）（重点）

🔎1.线性结构

线性结构是一种数据结构，它的元素之间存在线性的顺序关系。线性结构包括以下几种常见的数据结构：

1. 数组(Array)：是一种线性结构，它由一组连续的内存空间组成，可以通过下标快速访问其中的元素。
2. 链表(LinkedList)：是一种使用指针将一组节点按顺序连接起来的线性结构，每个节点包含一个数据和指向下一个节点的指针。
3. 栈(Stack)：是一种具有后进先出(LIFO)特性的线性结构，只能在一端进行插入和删除操作，这一端被称为栈顶。
4. 队列(Queue)：是一种具有先进先出(FIFO)特性的线性结构，只能在一端插入元素，在另一端删除元素。
5. 双端队列(Deque)：是一种可以在两端进行插入和删除操作的线性结构，可以在队头和队尾同时进行插入和删除。
6. 线性表(List)：是一种包含一组元素的线性结构，可以通过下标访问元素，线性表包括顺序表和链表。

🔎2.数组、矩阵和广义表

数组、矩阵和广义表都是数据结构中常用的数据表示方式。

1. 数组（Array）是一种线性数据结构，用于存储相同数据类型的元素的连续内存空间。数组可以通过索引来访问和操作其中的元素，索引从0开始。数组的长度是固定的，即在创建数组时就需要指定其大小。常用的操作包括插入、删除和查找元素等。
2. 矩阵（Matrix）是二维数组的一种特殊形式。矩阵用于表示有序的元素集合，其中的元素按照行和列的方式排列。矩阵通常用于表示二维空间或进行线性代数运算。矩阵可以进行基本的矩阵运算，如加法、乘法和转置等。
3. 广义表（Generalized List）是一种扩展了线性表概念的数据结构。广义表可以包含原子元素（如整数、字符等）和子表，子表又可以嵌套包含原子元素和更多的子表。广义表可以表示各种复杂的数据结构，如树、图等。广义表的操作包括插入、删除和遍历等。

数组和矩阵常用于存储和处理大量的数据，如图像处理、数值计算等；广义表则常用于表示复杂的数据结构和递归算法的实现。了解这些数据结构的特点和操作，对于设计和实现有效的算法非常重要。

🔎3.树

树是一种非线性的数据结构，它由节点和边组成。树的节点可以有 0 个或多个子节点，每个节点都有一个父节点，除了根节点没有父节点。根节点是整个树的顶部节点，它没有父节点。

树的节点可以有任意数量的子节点，但每个子节点只能有一个父节点。子节点和父节点之间的关系被称为父子关系。一个节点的子节点称为它的直接子节点，直接子节点的子节点称为该节点的间接子节点。

树的常见术语有：

• 节点：树的元素，包含数据和指向子节点的指针。
• 根节点：树的顶部节点，没有父节点。
• 叶节点：没有子节点的节点。
• 子树：由一个节点和它的所有子节点组成的树。
• 祖先节点：沿着树的路径由根节点到该节点的所有节点。
• 子孙节点：从一个节点到树的末端节点的路径上的所有节点。
• 节点的度：一个节点拥有的子节点的数量。
• 树的度：所有节点中的最大度数。

树的常见应用包括文件系统、组织结构图、网络路由等。不同类型的树包括二叉树、二叉搜索树、平衡二叉树、B树等，每种树的结构和特性不同，适用于不同的应用场景。

🔎4.图

图是一种用于表示对象和对象之间关系的数据结构。它由一组节点和一组边组成，节点表示对象，边表示对象之间的关系。图可以用于解决许多现实世界中的问题，如网络拓扑分析、社交网络分析、路径规划等。

图可以分为有向图和无向图。有向图的边有方向性，而无向图的边没有方向性。图还可以分为带权图和不带权图。带权图的边具有权重，用于表示对象之间的关系的强度或距离。

图的节点可以是任意类型的对象，并且节点之间可以有多条边相连。图的表示方法有多种，包括邻接矩阵和邻接表。邻接矩阵是一个二维数组，用于表示节点之间的连接关系。邻接表则是一个链表数组，用于表示每个节点的邻接节点。

图的常见操作包括添加节点、添加边、删除节点、删除边、查找节点、查找边、遍历节点等。常见的图算法包括深度优先搜索（DFS）和广度优先搜索（BFS），用于遍历图中的节点。

图的应用非常广泛，可以应用于各种领域，如计算机网络、社交网络、地理信息系统等。

🔎5.查找

查找是数据结构中常用的操作之一，用来在一个数据集合中寻找特定的元素或者满足特定条件的元素。常见的查找算法包括线性查找、二分查找、哈希查找等。

1. 线性查找：线性查找是最简单的查找算法，逐个遍历数据集合中的元素，直到找到目标元素或者遍历完所有元素。时间复杂度为O(n)。
2. 二分查找：二分查找是一种高效的查找算法，要求数据集合有序。通过比较目标元素与数据集合中间元素的大小关系，可以将查找范围缩小一半，直到找到目标元素或者查找范围为空。时间复杂度为O(log n)。
3. 哈希查找：哈希查找利用哈希函数将元素映射到一个固定的哈希表索引位置，通过索引位置快速找到目标元素。哈希查找的平均时间复杂度为O(1)，但需要额外的空间来存储哈希表。

除了以上三种常见的查找算法，还有其他一些特定场景下的查找算法，如树结构的查找（二叉查找树、红黑树等）、图结构的查找（深度优先搜索、广度优先搜索等）等。选择合适的查找算法取决于数据集合的特点以及查找的要求。

🔎6.排序

在数据结构中，排序是将一组元素按照特定的规则进行排列的过程。排序可以根据不同的规则进行，常见的排序算法有以下几种：

1. 冒泡排序（Bubble Sort）：通过依次比较相邻的两个元素，将较大（或较小）的元素放到右侧（或左侧），直到所有元素都排好序。
2. 选择排序（Selection Sort）：每次从待排序的元素中选择最小（或最大）的元素，放到已排序部分的末尾，直到所有元素都排好序。
3. 插入排序（Insertion Sort）：将待排序的元素依次插入到已排序部分的合适位置，直到所有元素都排好序。
4. 快速排序（Quick Sort）：选择一个基准元素，将小于等于基准的元素放到左侧，大于基准的元素放到右侧，然后对左右两侧的元素分别递归地进行快速排序。
5. 归并排序（Merge Sort）：将待排序的元素递归地拆分成两个子序列，分别对子序列进行排序，然后将排好序的子序列进行合并。
6. 堆排序（Heap Sort）：利用堆这种数据结构，通过不断调整堆的结构，将堆顶的元素与最后一个元素交换，并将堆的大小减一，然后再调整堆，直到堆中的元素排好序。
7. 希尔排序（Shell Sort）：将待排序的元素按照一定的间隔进行分组，分别对每组进行插入排序，然后逐渐缩小间隔，直到间隔为1，最后进行一次完整的插入排序。

我正在参与2024腾讯技术创作特训营第五期有奖征文，快来和我瓜分大奖！