数据结构基础知识总结(数据结构知识整理)

谁给我详细讲一下关于数据结构

1．1 数据结构的概念 数据结构是计算机科学与技术专业的专业基础课，是十分重要的核心课程。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此，要想更好地运用计算机来解决实际问题，仅掌握几种计算机程序设计语言是难以应付众多复杂的课题的。要想有效地使用计算机、充分发挥计算机的性能，还必须学习和掌握好数据结构的有关知识。打好“数据结构”这门课程的扎实基础，对于学习计算机专业的其他课程，如操作系统、编译原理、数据库管理系统、软件工程、人工智能等都是十分有益的。 1.1.1 为什么要学习数据结构 在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。当我们使用计算机来解决一个具体问题时，一般需要经过下列几个步骤：首先要从该具体问题抽象出一个适当的数学模型，然后设计或选择一个解此数学模型的算法，最后编出程序进行调试、测试，直至得到最终的解答。例如，求解梁架结构中应力的数学模型的线性方程组，该方程组可以使用迭代算法来求解。 由于当时所涉及的运算对象是简单的整型、实型或布尔类型数据，所以程序设计者的主要精力是集中于程序设计的技巧上，而无须重视数据结构。随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题越来越显得重要。据统计，当今处理非数值计算性问题占用了90%以上的机器时间。这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。因此，解决这类问题的关键不再是数学分析和计算方法，而是要设计出合适的数据结构，才能有效地解决问题。下面所列举的就是属于这一类的具体问题。 [例1] 学生信息检索系统。当我们需要查找某个学生的有关情况的时候；或者想查询某个专业或年级的学生的有关情况的时候，只要我们建立了相关的数据结构，按照某种算法编写了相关程序，就可以实现计算机自动检索。由此，可以在学生信息检索系统中建立一张按学号顺序排列的学生信息表和分别按姓名、专业、年级顺序排列的索引表，如图1.1所示。由这四张表构成的文件便是学生信息检索的数学模型，计算机的主要操作便是按照某个特定要求（如给定姓名）对学生信息文件进行查询。 诸如此类的还有电话自动查号系统、考试查分系统、仓库库存管理系统等。在这类文档管理的数学模型中，计算机处理的对象之间通常存在着的是一种简单的线性关系，这类数学模型可称为线性的数据结构。 [例2] 八皇后问题。在八皇后问题中，处理过程不是根据某种确定的计算法则，而是利用试探和回溯的探索技术求解。为了求得合理布局，在计算机中要存储布局的当前状态。从最初的布局状态开始，一步步地进行试探，每试探一步形成一个新的状态，整个试探过程形成了一棵隐含的状态树。如图1.2所示（为了描述方便，将八皇后问题简化为四皇后问题）。回溯法求解过程实质上就是一个遍历状态树的过程。在这个问题中所出现的树也是一种数据结构，它可以应用在许多非数值计算的问题中。 [例3] 教学计划编排问题。一个教学计划包含许多课程，在教学计划包含的许多课程之间，有些必须按规定的先后次序进行，有些则没有次序要求。即有些课程之间有先修和后续的关系，有些课程可以任意安排次序。这种各个课程之间的次序关系可用一个称作图的数据结构来表示，如图1.3所示。有向图中的每个顶点表示一门课程，如果从顶点vi到vj之间存在有向边vi，vj，则表示课程i必须先于课程j进行。 由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。因此，可以说数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。 学习数据结构的目的是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。与此同时，通过算法训练来提高学生的思维能力，通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高。 1.1.2 有关概念和术语 在系统地学习数据结构知识之前，先对一些基本概念和术语赋予确切的含义。 数据（Data）是信息的载体，它能够被计算机识别、存储和加工处理。它是计算机程序加工的原料，应用程序处理各种各样的数据。计算机科学中，所谓数据就是计算机加工处理的对象，它可以是数值数据，也可以是非数值数据。数值数据是一些整数、实数或复数，主要用于工程计算、科学计算和商务处理等；非数值数据包括字符、文字、图形、图像、语音等。 数据元素（Data Element）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。例如，学生信息检索系统中学生信息表中的一个记录、八皇后问题中状态树的一个状态、教学计划编排问题中的一个顶点等，都被称为一个数据元素。 有时，一个数据元素可由若干个数据项（Data Item）组成，例如，学籍管理系统中学生信息表的每一个数据元素就是一个学生记录。它包括学生的学号、姓名、性别、籍贯、出生年月、成绩等数据项。这些数据项可以分为两种：一种叫做初等项，如学生的性别、籍贯等，这些数据项是在数据处理时不能再分割的最小单位；另一种叫做组合项，如学生的成绩，它可以再划分为数学、物理、化学等更小的项。通常，在解决实际应用问题时是把每个学生记录当作一个基本单位进行访问和处理的。 数据对象（Data Object）或数据元素类（Data Element Class）是具有相同性质的数据元素的集合。在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），属于同一数据对象（数据元素类），数据元素是数据元素类的一个实例。例如，在交通咨询系统的交通网中，所有的顶点是一个数据元素类，顶点A和顶点B各自代表一个城市，是该数据元素类中的两个实例，其数据元素的值分别为A和B。 数据结构（Data Structure）是指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着这样或那样的关系，这种数据元素之间的关系称为结构。根据数据元素间关系的不同特性，通常有下列四类基本的结构： ⑴集合结构。在集合结构中，数据元素间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构。 ⑵线性结构。该结构的数据元素之间存在着一对一的关系。 ⑶树型结构。该结构的数据元素之间存在着一对多的关系。 ⑷图形结构。该结构的数据元素之间存在着多对多的关系，图形结构也称作网状结构。

数据结构与算法基础知识

1.数据结构的逻辑结构

(1)集合结构

(2)线性结构(存在唯一的第一个元素与唯一的最后一个元素)(eg: 线性表、队列、栈、字符串、数组、链表)

(3)树形结构(一对多)

(4)图形结构(多对多)

2.数据结构的物理(存储)结构

(1).顺序存储结构(插入与删除低效因为要挪动其他元素的位置。但是遍历简单)

(2).链式存储结构(插入与删除高效，但是遍历低效)

3.大O表示法(注意大O表示法表达的是最坏的情况)

规则：

(1)用常数1取代其他所有的常数(注意常数0也当1算)(3 - 1, O(1))

(2) 只保留最高阶项(n^3+2n^2+5 -n^3, O(n^3))

(3) 若存在最高阶，省略与其想成的常数(2n^3 - n^3, O(n^3))

4. 时间复杂度类型

(1)常数阶

(2)线性阶

(3)平方阶

(4)对数阶

(5)立方阶

(6)nlog阶

(7)指数阶(O(2^n)或O(n!), 往往会造成噩梦般的时间消耗)

5. 空间复杂度(用大O表示法求解改算法的辅助空间即可，例如用于交换变量用的临时变量的数量)

六. 顺序存储的线性表

线性表结构特点：

(1) 存在唯一一个的被称作”第一个”的数据元素；

(2) 存在唯一一个的被称作”第二个”的数据元素；

(3) 除了第一个元素以外，结构中的每个数据元素均有一个前驱；

(4) 除了最后一个元素以外，结构中的每个数据元素均有一个后继。

七. 链式存储的线性表(单链表)

首元结点是链表中第一个值域不为空的结点。

头结点是一个值域为空且处于首位的结点。

首指针可指向首元结点也可指向头结点，但是如果指向头结点可以更加方便的处理单链表的插入和删除问题，不用再对首位做额外判断，并且指向头节点的指针永远不用变化。

*注意一下单链表的前插法和尾插法。尾插法更符合逻辑

数据结构基本知识

A错误，栈是线性结构线性结构是最简单最常用的一种数据结构,线性结构的特点是结构中的元素之间满足线性关系,按这个关系可以把所有元素排成一个线性序列.线性表,串,栈和队列都属于线性结构.而非线性结构是指在该类结构中至少存在一个数据元素,它具有两个或者两个以上的前驱或后继.如树和二叉树等.

数据结构知识点总结

线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。是随机存取的顺序存储结构。顺序存储指内存地址是一块的，随机存取指访问时可以按下标随机访问，存储和存取是不一样的。

用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。链表中结点的逻辑次序和物理次序不一定相同。

队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。先进先出。

串(String)是零个或多个字符组成的有限序列。长度为零的串称为空串(Empty String)，它不包含任何字符。通常将仅由一个或多个空格组成的串称为空白串(Blank String) 注意：空串和空白串的不同，例如“ ”和“”分别表示长度为1的空白串和长度为0的空串。

串的表示和实现

数组和广义表可看成是一种特殊的线性表，其特殊在于: 表中的元素本身也是一种线性表。内存连续。根据下标在O(1)时间读/写任何元素。

二维数组，多维数组，广义表，树，图都属于非线性结构

数组

数组的顺序存储：行优先顺序；列优先顺序。数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。

关联数组(Associative Array)，又称映射（Map）、字典（ Dictionary）是一个抽象的数据结构，它包含着类似于(键，值)的有序对。 不是线性表。

广义表

广义表（Lists，又称列表）是线性表的推广。广义表是n(n≥0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。若广义表LS（n=1)非空，则a1是LS的表头，其余元素组成的表(a2,…an)称为LS的表尾。广义表的元素可以是广义表，也可以是原子，广义表的元素也可以为空。表尾是指除去表头后剩下的元素组成的表，表头可以为表或单元素值。所以表尾不可以是单个元素值。

三个结论

考点

一种非线性结构。树是递归结构，在树的定义中又用到了树的概念。

基本术语

1.树结点：包含一个数据元素及若干指向子树的分支；

2.孩子结点：结点的子树的根称为该结点的孩子；

3.双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；

4.兄弟结点：同一双亲的孩子结点；

5.堂兄结点：同一层上结点；

6.结点层次：根结点的层定义为1；根的孩子为第二层结点，依此类推；

7.树的高（深）度：树中最大的结点层

8.结点的度：结点子树的个数，就是有几个孩子

9.树的度： 树中最大的结点度。

10.叶子结点：也叫终端结点，是度为0的结点；

11.分枝结点：度不为0的结点（非终端结点）；

12.森林：互不相交的树集合；

13.有序树：子树有序的树，如：家族树；

14.无序树：不考虑子树的顺序；

二叉树

二叉树可以为空。二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。

注意区分： 二叉树、二叉查找树/二叉排序树/二叉搜索树、二叉平衡(查找)树

二叉树遍历

先序遍历：根左右

中序遍历：左根右

后序遍历：左右根

层次遍历：一维数组存储二叉树，总是以层次遍历的顺序存储结点。层次遍历应该借助队列。

二叉树性质

1.在二叉树的第 i 层上至多有2的i次幂-1个结点

2.深度为 k 的二叉树上至多含 2的k次幂-1 个结点（k≥1）

3.树与转换后的二叉树的关系：转换后的二叉树的先序对应树的先序遍历；转换后的二叉树的中序对应树的后序遍历

一些概念

1.路径：从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径；

2.路径长度：路径上的分支数目称为路径长度；

3.树的路径长度：从根到每个结点的路径长度之和。

4.结点的权：根据应用的需要可以给树的结点赋权值；

5.结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积；

6.树的带权路径长度=树中所有叶子结点的带权路径之和；通常记作 WPL=∑wi×li

7.哈夫曼树：假设有n个权值(w1, w2, … , wn)，构造有n个叶子结点的二叉树，每个叶子结点有一个 wi作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树。最优二叉树。

图搜索-形成搜索树

1.穷举法

2.贪心法。多步决策，每步选择使得构成一个问题的可能解，同时满足目标函数

3.回溯法，根据题意，选取度量标准，然后将可能的选择方法按度量标准所要求顺序排好，每次处理一个量，得到该意义下的最优解的分解处理

无向图

1.回路或环：第一个顶点和最后一个顶点相同的路径。

2.简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路

3.连通：顶点v至v’ 之间有路径存在

4.连通图：无向图图 G 的任意两点之间都是连通的，则称G是连通图。

5.连通分量：极大连通子图，子图中包含的顶点个数极大

6.所有顶点度的和必须为偶数

有向图

1.回路或环：第一个顶点和最后一个顶点相同的路径。

2.简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。

3.连通：顶点v至v’之间有路径存在

4.强连通图：有向图G的任意两点之间都是连通的，则称G是强连通图。各个顶点间均可达。

5.强连通分量：极大连通子图

6.有向图顶点的度是顶点的入度与出度之和。邻接矩阵中第V行中的1的个数是V的出度

7.生成树：极小连通子图。包含图的所有n个结点，但只含图的n-1条边。在生成树中添加一条边之后，必定会形成回路或环。

8.完全图：有 n(n-1)/2 条边的无向图。其中n是结点个数。必定是连通图。

9.有向完全图：有n(n-1)条边的有向图。其中n是结点个数。每两个顶点之间都有两条方向相反的边连接的图。

10.一个无向图 G=(V,E) 是连通的，那么边的数目大于等于顶点的数目减一：|E|=|V|-1，而反之不成立。如果 G=(V,E) 是有向图，那么它是强连通图的必要条件是边的数目大于等于顶点的数目：|E|=|V|，而反之不成立。没有回路的无向图是连通的当且仅当它是树，即等价于：|E|=|V|-1。

图的邻接矩阵和邻接表

1.邻接矩阵和加权邻接矩阵

深度优先搜索利用栈

深度优先遍历类似于树的先序遍历，是树的先序遍历的推广

广度优先遍历

图的广度优先遍历就类似于树的层序遍历

每次遍历一个连通图将图的边分成遍历所经过的边和没有经过的边两部分，将遍历经过的边同图的顶点构成一个子图，该子图称为生成树。因此有DFS生成树和BFS生成树。

生成树是连通图的极小子图，有n个顶点的连通图的生成树必定有n-1条边,在生成树中任意增加一条边，必定产生回路。若砍去它的一条边，就会把生成树变成非连通子图

最小生成树：生成树中边的权值(代价)之和最小的树。最小生成树问题是构造连通网的最小代价生成树。

Kruskal算法 ：令最小生成树集合T初始状态为空，在有n个顶点的图中选取权值最小的边并从图中删去，若该边加到T中有回路则丢弃，否则留在T中；依次类推，知道T中有n-1条边为止

Prim算法： 它的基本思想是以顶点为主导地位，从起始顶点出发，通过选择当前可用的最小权值边把顶点加入到生成树当中来：

1.从连通网络N={V,E}中的某一顶点U0出发，选择与它关联的具有最小权值的边（U0,V）,将其顶点加入到生成树的顶点集合U中。

2.以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(U,V),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。

Prim算法，Kruskal算法和Dijkstra算法都属于贪心算法

Dijkstra算法适用于边权值为正的情况，如果边权值为负数就才用另一种最短路算法Bellman-Ford算法。该算法是指从单个源点到各个结点的最短路，该算法适用于有向图和无向图。复杂度O(n^2)

Dijkstra算法图文详解

若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为 重（双）连通图。

若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为 关节点。

没有关节点的连通图称为双连通图

1.生成树的根结点，有两个或两个以上的分支，则此顶点(生成树的根)必为关节点；

2.对生成树上的任意一个非叶“顶点”，若其某棵子树中的所有“顶点”没有和其祖先相通的回边，则该“顶点”必为关节点

拓扑排序。在用邻接表表示图时,对有n个顶点和e条弧的有向图而言时间复杂度为O(n+e)。一个有向图能被拓扑排序的充要条件就是它是一个有向无环图。

AOV网(Activity On Vertex)：用顶点表示活动，边表示活动的优先关系的有向图称为AOV网。AOV网中不允许有回路，这意味着某项活动以自己为先决条件。

拓扑有序序列：把AOV网络中各顶点按照它们相互之间的优先关系排列一个线性序列的过程。若vi是vj前驱，则vi一定在vj之前；对于没有优先关系的点，顺序任意。

拓扑排序：对AOV网络中顶点构造拓扑有序序列的过程。方法：

采用 深度优先搜索 或者 拓扑排序 算法可以判断出一个有向图中是否有环（回路）。

深度优先搜索只要在其中记录下搜索的节点数n，当n大于图中节点数时退出，并可以得出有回路。若有回路，则拓扑排序访问不到图中所有的节点，所以也可以得出回路。广度优先搜索过程中如果访问到一个已经访问过的节点，可能是多个节点指向这个节点，不一定是存在环。

拓扑算法描述 ：

AOE网：带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。在工程上常用来表示工程进度计划。

常用哈希函数

1.直接定址法。

2.数字分析法。

3.平方取中法。

4.折叠法。

5.除留余数法。

6.随机数法。

冲突解决

1.开放定址法：当发生冲突时，形成一个探查序列，沿此序列逐个地址探查，知道找到一个空位置，将发生冲突的记录放到该地址中。即Hi=(H(key)+di) % m，i=1,2,……k(k=m-1)，H(key)哈希函数，m哈希表长，di增量序列。

2.链地址法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针。

3.设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到Hash表中需要做n (n-1)/2次线性探测。如果使用二次探测再散列法将这n个关键字存入哈希表，至少要进行n (n+1)/2次探测

4.Hash查找效率：装填因子=表中记录数/表容量

5.开哈希表——链地址法；闭哈希表——开放地址法

B树的查找

时间复杂度O(logn)

B树的插入

例：用1，2，6，7，11，4，8，13，10，5，17，9，16，20，3，12，14，18，19，15构建5阶B树

因为构建5阶的B树，所以每个节点的关键字个数范围为[2,4]

插入11时，该节点的关键字个数超出范围，进行分裂

之后直接插入4，8，13

当插入10时，节点关键字个数再次超出范围

将子节点分裂

直接插入5，17，9，16，插入20

关键字个数超出范围，进行分裂

继续插入3

关键字个数超出范围，进行分裂

继续插入15

关键个数超出范围，进行分裂

这时候根节点关键字个数也超出范围，继续分裂

B+的优点

1.单一节点存储更多的元素，使得查询的IO次数更少。

2.所有查询都要查询叶到叶子节点，查询更加稳定

3.所有叶子节点形成有序链表，便于范围查询。

数据结构学习些什么内容，学习数据结构有什么意义，有哪些运用

数据结构学习的内容可以去百度。

作为一个已经进入公司程序员，我来告诉你学习数据结构有什么用。

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构在编程中的重要作用具体表现在：

1、数据结构是一门综合性较强的计算机软件、程序设计理论和技术相结合的重要基础知识。它主要讨论抽象数据关系和算法在计算机中的表示与实现,涉及到的数据在计算机中的表示、组织和处理 ,以及相应结构上的算法设计和算法性能上的分析技术。它所包含的知识与提倡的技术方法 ,无论对大家进一步学习计算机领域里的其他知识 ,还是对今后从事理论研究、应用开发及技术管理工作都起着重要的作用。

2、学习数据结构目的与要求是学会从问题入手 ,分析和研究计算机加工的数据结构特性 ,使大家能够为他们应用的数据选择适当的逻辑结构、存储结构及其相应的操作算法 ,并初步掌握算法的性能分析技术。同时 ,学习中还要进行复杂的程序设计训练 ,也培养了大家数据抽象能力、算法构造性思维方法能力及逻辑思维能力 ,这些能力也是软件系统开发过程中非常重要的一种创造性思维活动。

3、数据结构和程序设计语言本身虽然没有多大的联系 ,但数据结构是一种抽象数据 ,是实用程序语言去描述数据结构 ,通过程序设计语言可以将它在计算机中进行实现。学会了数据结构,就会用所学知识对实践任务进行充分分析、抽象 ,建立与之相适应的模式 ,使问题最终在计算机上得以实现。在这个过程中 ,大家不仅对所学知识加深了理解 ,更重要的是培养了大家分析问题、解决问题的能力 ,这对充分发挥大家的实践能力、创造能力起着重要的作用 ,也提高大家算法设计和程序设计能力。

所以说，数据结构在软件编程中有着举足轻重的作用，可以说一个系统的工程离不开数据结构的支持。一个优秀的软件开发人员，数据结构是其必备的基础知识。