数据结构知识点

第1章 绪 论

知识点归纳

一、数据结构概述

1. 数据结构的定义

（1） 基本概念

数据是描述客观事物的数和字符的集合，是计算机能操作的对象的总称，也是计算机处理信息的某种特定的符号表示形式。

（2） 相关术语

① 数据元素

数据元素又称元素、节点、顶点、记录等。数据元素是数据的基本单位。有时候，一个数据元素可以由若干个数据项组成。

② 数据项

数据项又称字段或域，它是具有独立含义的最小数据单位。

③ 数据对象

数据对象是性质相同的数据元素的集合，它是数据的子集。

（3） 数据结构的内容

① 数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前呈现的形式。

② 数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，又称数据的物理结构。

③ 施加在数据上的操作，即数据的运算。

（4） 逻辑结构

数据的逻辑结构是从逻辑关系（主要是指数据元素的相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

（5） 存储结构

数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示（又称映像），也就是逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。一般只在高级语言（例如C／C++语言）的层次上讨论存储结构。

数据的运算最终需在对应的存储结构上用算法实现。

总之，数据结构是一门讨论“描述现实世界实体的数学模型（通常为非数值计算）及其之上的运算在计算机中如何表示和实现”的学科。

（6） 数据结构的表示

对于一种数据结构，其逻辑结构总是惟一的，但它可能对应多种存储结构，并且在不同的存储结构中，同一运算的实现过程可能不同。

描述数据结构通常采用二元组表示：

B=（D，R）

其中，B是一种数据结构，它由数据元素的集合D和D上二元关系的集合R组成，即：

D={di | 1≤i≤n，n≥0}

R={rj | 1≤j≤m，m≥0}

《数据结构》复习重点知识点归纳

一．数据结构的章节结构及重点构成

数据结构学科的章节划分基本上为：概论，线性表，栈和队列，串，多维数组和广义表，

树和二叉树，图，查找，内排，外排，文件，动态存储分配。

对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大

多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。所以，大家在这三章上

可以不必花费过多的精力，只要知道基本的概念即可。但是，对于报考名校特别是该校又有

在试卷中对这三章进行过考核的历史，那么这部分朋友就要留意这三章了。

按照以上我们给出的章节以及对后三章的介绍，数据结构的章节比重大致为：

·概论：内容很少，概念简单，分数大多只有几分，有的学校甚至不考。

·线性表：基础章节，必考内容之一。考题多数为基本概念题，名校考题中，鲜有大型

算法设计题，如果有，也是与其它章节内容相结合。

·栈和队列：基础章节，容易出基本概念题，必考内容之一。而栈常与其它章节配合考

查，也常与递归等概念相联系进行考查。

·串：基础章节，概念较为简单。专门针对于此章的大型算法设计题很少，较常见的

是根据KMP进行算法分析。

·多维数组及广义表：基础章节，基于数组的算法题也是常见的，分数比例波动较大，

是出题的“可选单元”或“侯补单元”。一般如果要出题，多数不会作为大题出。数组常与

“查找，排序”等章节结合来作为大题考查。

·树和二叉树：重点难点章节，各校必考章节。各校在此章出题的不同之处在于，是

否在本章中出一到两道大的算法设计题。通过对多所学校的试卷分析，绝大多数学校在本章

都曾有过出大型算法设计题的历史。

·图：重点难点章节，名校尤爱考。如果作为重点来考，则多出现于分析与设计题型

当中，可与树一章共同构成算法设计大题的题型设计。

·查找：重点难点章节，概念较多，联系较为紧密，容易混淆。出题时可以作为分析

型题目给出，在基本概念型题目中也较为常见。算法设计型题中可以数组结合来考查，也可

以与树一章结合来考查。

第1章 绪 论

知识点归纳

一、数据结构概述

1. 数据结构的定义

（1） 基本概念

数据是描述客观事物的数和字符的集合，是计算机能操作的对象的总称，也是计算机处理信息的某种特定的符号表示形式。

（2） 相关术语

① 数据元素

数据元素又称元素、节点、顶点、记录等。数据元素是数据的基本单位。有时候，一个数据元素可以由若干个数据项组成。

② 数据项

数据项又称字段或域，它是具有独立含义的最小数据单位。

③ 数据对象

数据对象是性质相同的数据元素的集合，它是数据的子集。

（3） 数据结构的内容

① 数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前呈现的形式。

② 数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，又称数据的物理结构。

③ 施加在数据上的操作，即数据的运算。

（4） 逻辑结构

数据的逻辑结构是从逻辑关系（主要是指数据元素的相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

（5） 存储结构

数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示（又称映像），也就是逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。一般只在高级语言（例如C／C++语言）的层次上讨论存储结构。

数据的运算最终需在对应的存储结构上用算法实现。

总之，数据结构是一门讨论“描述现实世界实体的数学模型（通常为非数值计算）及其之上的运算在计算机中如何表示和实现”的学科。

（6） 数据结构的表示

对于一种数据结构，其逻辑结构总是惟一的，但它可能对应多种存储结构，并且在不同的存储结构中，同一运算的实现过程可能不同。

描述数据结构通常采用二元组表示：

B=（D，R）

其中，B是一种数据结构，它由数据元素的集合D和D上二元关系的集合R组成，即：

D={di | 1≤i≤n，n≥0}

R={rj | 1≤j≤m，m≥0}

数据结构的图知识点总结

图是一种重要的数据结构，它在计算机科学中有着广泛的应用。图是由节点和边组成的一种数据结构，用来表示各种复杂的关系和网络结构。在图中，节点表示实体或对象，而边表示节点之间的关系。图可以表示各种复杂的关系，比如社交网络中的朋友关系、交通网络中的路径、电子电路中的连接等等。

图的基本概念

图是由节点和边组成的一种数据结构。节点是图中的基本单位，它表示实体或对象。边是节点之间的连接关系，它表示节点之间的关系。图可以分为有向图和无向图两种。在有向图中，边有方向，表示一个节点指向另一个节点的关系；在无向图中，边没有方向，表示两个节点之间的相互关系。

图的表示方法

图可以用多种方法来表示。最常见的表示方法是邻接表和邻接矩阵。邻接表是一种以链表的形式存储图的表示方法，对于每个节点，用一个链表来存储与其相邻的节点。邻接矩阵是一种用二维数组来表示图的方法，对于每一对节点，用一个矩阵元素来表示它们之间的边。

图的遍历

图的遍历是指从图中的一个节点出发，按照一定规则依次访问图中的所有节点。图的遍历有两种常见的方式，深度优先搜索（DFS）和广度优先搜索（BFS）。深度优先搜索是一种递归的方式，从起始节点开始，依次访问其相邻的节点，直到所有可达的节点都被访问到为止。广度优先搜索是一种迭代的方式，从起始节点开始，依次访问其所有相邻的节点，直到所有可达的节点都被访问到为止。

图的最短路径算法

图的最短路径算法是解决图中节点之间最短路径的问题。最短路径算法包括迪杰斯特拉算法（Dijkstra算法）和弗洛伊德算法（Floyd算法）。迪杰斯特拉算法是一种用于解决单源最短路径的算法，它采用贪心策略，逐步确定所有节点的最短路径。弗洛伊德算法是一种用于解决所有节点之间最短路径的算法，它采用动态规划的策略，逐步确定所有节点之间的最短路径。

图的最小生成树算法

图的最小生成树算法是解决图中最小生成树的问题。最小生成树是指包含图中所有节点的树，并且具有最小的权值和。最小生成树算法包括克鲁斯卡尔算法（Kruskal算法）和普林算法（Prim算法）。克鲁斯卡尔算法是一种贪心算法，通过不断选择权值最小的边，来构建最小生成树。普林算法是一种贪心算法，通过不断选择与已构建的树相邻的节点，并且权值最小的边，来构建最小生成树。