数据结构知识点总结

数据结构学习总结

壹、研究对象及基本概念

首先从数据结构是什么开始，数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。主要研究：1、数据的逻辑结构，即数据关系之间的逻辑关系；2、数据的存储结构（即物理结构），即数据的逻辑结构在计算机中的表示；3、操作算法，即插入、删除、修改、查询、排序等操作。

一、从数据的逻辑结构划分，即数据之间的逻辑关系从线性分析的角度划

分主要有线性结构和非线性结构。线性结构又可细分为线性表、栈、队列、串、数组。非线性结构又可细分为树型结构和图结构。

线性结构: 线性表、栈、队列、串、数组 树结构

逻辑结构 非线性结构 图结构 二、从存储结构划分 物理结构

顺序结构 链式结构 索引结构 散列结构 各自的定义及特点：

1、顺序存储：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来直接体现。

优点：随机存取表中元素。缺点：插入和删除操作需要移动大量结点。

2、链式存储：它不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系是由附加的指针字段表示的。

它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点.插入、删除灵活 (不必移动节点，只要改变节点中的指针)。查找结点时链式存储要比顺序存储慢。

3、索引存储：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。索引项的一般形式一般是关键字、地址。

4、散列存储：又称hash存储，是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。散列法存储的基本思想是：由节点的关键码值决定节点的存储地址。特点：散列是能一种快速实现访问的存储方式。 三、操作算法

1、算法定义：对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。 2、五个重要特性：

（1）有穷性；（2）确定性；（3）可行性；（4）输入；（5）输出。 3、算法设计要求：

（1）正确性；（2）可读性；（3）健壮性；（4）效率与低存储量需求。 效率的度量：

算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。 存储空间度量：

一个程序的空间复杂度是指运行完一个程序所需内存的大小。一个算法所需的存储空间用f(n)表示。

S(n)=O(f(n))

其中n为问题的规模，S(n)表示空间复杂度。 四、一些基本概念 1.数据

数据是用于描述客观事物的数值、字符，以及一切可以输入到计算机中的并由计算机程序加以处理的符号的集合。其范围随着计算机技术的发展而不断发展。 2.数据元素

数据的基本单位是数据元素，在计算机程序中通常作为一个整体进行考虑和处理。

3.数据项

是数据的不可分割的最小单位，一个数据元素可由若干个数据项组成。 4.数据对象

性质相同的元素的集合叫做数据对象。

贰、线性结构

一、线性表

1.1[定义] 线性表是由n(n≥0)个相同类型的元素组成的有序集合。

记为：

( a1,a2,a3,??ai-1,ai,ai+1,?? an )

其中：① n为线性表中元素个数，称为线性表的长度；

当n=0时，为空表，记为（ ）。 ② ai为线性表中的元素，类型定义为elemtype

③ a1为表中第1个元素，无前驱元素；an为表中最后一个元素，无后继元素；对于?ai-1,ai,ai+1?(1

④ 线性表是有限的，也是有序的。

抽象数据型线性表：

线性表 LIST = ( D , R)

D = { ai | ai ∈Elementset , i = 1, 2, ?, n, n ≥ 0 } R = { H }

H = { | ai-1, ai ∈ D , i = 2 , ? , n } 操作：设L的型为LIST线性表实例，x 的型为elemtype的元素 实例，p 为位置变量。所有操作描述为： ① Insert(x, p, L) ② Locate(x, L) ③ Retrieve(p, L) ④ Delete(p, L)

⑤ Previous(p, L), Next(p, L) ⑥ MakeNull( L) ⑦ First( L) ⑧End(L)

1.2线性表的实现：

① 顺序表： 把线性表的元素逻辑顺序依次存放在数组的连续单元内，再用一个整型量表示最后一个元素所在单元的下标。 特点：

元素之间的逻辑关系（相继/相邻关系）用物理上的相邻关系来表示（用物理上的连续性刻画逻辑上的相继性）； 是一种随机存储结构，也就是可以随机存取表中的任意元素，其存储位置可由一个简单直观的公式来表示。

② 单链表：一个线性表由若干个结点组成，每个结点均含有两个域： 存放元素的信息域和存放其后继结点的指针域，这样就形成一个 单向链接式存储结构，简称单向链表或单向线性链表。 结构特点：

逻辑次序和物理次序不一定相同；元素之间的逻辑关系用指针表示； 需要额外空间存储元素之间的关 系；非随机存储结构

一些操作：

③双向连表：在单向链表中，对每个结点增加一个域，用一指向该结点的前驱结点。线性表的这种存储结构称为双向链表。 优点：

实现双向查找（单链表不易做到）

表中的位置i 可以用指示含有第i 个结点的指针表示。 缺点：空间开销大。

④ 单向环形链表：在(不带表头结点)的单向链表中，使末尾结点的指 针域指向头结点，得到一个环形结构；用指向末尾结点的指针标识 这个表。

⑤双向环形链表的结构与双向连表结构相同，只是将表头元素 的空previous域指向表尾，同时将表尾的空next域指向表头结点， 从而形成向前和向后的两个环形链表，对链表的操作变得更加灵 活。

二、栈

栈是线性表的一种特殊形式，是一种限定性数据结构，也就是在对线性表的操作加以限制后，形成的一种新的数据结构。

定义：是限定只在表尾进行 插入和删除操作的线性表。 栈又称为后进先出 (Last In First Out ) 的线性表。简称LIFO结构。

即先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它

是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。

实现：顺序栈： 链栈：

三、队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一

样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素成为出队。因为队列只允许在一段插入，在另一端删除，所以只有最早进入队列的元素才能最先从队

列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

队列的指针实现：

队列的数组实现：

在顺序队列中，每次在队尾插入一个元素时，rear增1；每次在队头删除一个元素时，front增1。随着插入和删除操作的进行，队列元素的个数不断变化，队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时，队列中没有任何元素，称为空队列。 循环队列：

在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有Maxlength-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时front=rear，而队列判满的条件时

front=（rear+1）%Maxlength。 四、串

字符串或串(String)是由数字、字母、下划线组成的一串字符。一般记为 s=“a1a2···an”(n>=0)。它是编程语言中表示文本的数据类型。串(或字符串),是由零个或多个字符组成的有穷序列。含零个字符的串称为空串,用Ф表示。串中所含字符的个数称为该串的长度(或串长)。当且仅当两个串的长度相等并且各个对应位置上的字符都相同时,这两个串才是相等的。一个串中任意个连续字符组成的子序列(含空串,但不含串本身)称为该串的子串。例如,“a”、“ab”、“abc”和“abcd”等都是“abcde”的子串（平凡子串不包括自身）。

串的两种最基本的存储方式是顺序存储方式和链接存储方式。基本与线性表的存储一样，只是存储的内容是字符。

五、数组和广义表

1、数组是由下标（index）和值（value）组成的序对（index，value）的集合。也可以定义为是由相同类型的数据元素组成有限序列。数组在内存中是采用一组连续的地址空间存储的，正是由于此种原因，才可以实现下标运算。所有数组都是一个一维向量。 数组的顺序存储； 数组的压缩存储： ⑴ 特殊矩阵

若n 阶矩阵 A 中的元素满足下述性质 aij = aji 1 ≤ i, j ≤ n 则称 n 阶对称阵。对于对称矩阵, 为实现节约存储空间, 我们可以为每一对对称元素分配一个存储空间，这样,原来需要的n2个元素压缩存储到 n(n+1)/2 个元素空间。 对称关系：

设sa[ 0 . . n(n+1)/2 ] 做为 n 阶对称阵 A 的存储结构, 则 Sa[ k ] 和 aij 的一一对应关系为: i(i+1)/2+j 当 i ≥ j k =

j(j+1)/2+i 当 i < j

（2）、稀疏矩阵中，零元素的个数远远多于非零元素的个数。为 实现压缩存储，考虑只存储非零元素。

2、广义表

广义表(Lists，又称列表)是一种非线性的数据结构，是线性表的一种推广。 （1）广义表常用表示 ① E=()

E是一个空表，其长度为0。 ② L=(a，b)

L是长度为2的广义表，它的两个元素都是原子，因此它是一个线性表 ③ A=(x，L)=(x，(a，b))

A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L。 ④ B=(A，y)=((x，(a，b))，y)

B是长度为2的广义表，第一个元素是子表A，第二个元素是原子y。 ⑤ C=(A，B)=((x，(a，b))，((x，(a，b))，y)) C的长度为2，两个元素都是子表。 ⑥ D=(a，D)=(a，(a，(a，(?))))

D的长度为2，第一个元素是原子，第二个元素是D自身，展开后它是一个无限的广义表。

（2）广义表的深度

一个表的\深度\是指表展开后所含括号的层数。

叁、非线性结构

一、树

1、一个结点 x 组成的集{ x }是一棵树，这个结点 x 也是这棵树的根。 2、假设 x 是一个结点，T1，T2，?，Tk是 k 棵互不相交的树，我们可以构造一棵新树：令 x 为根，并有 k 条边由 x 指向树T1，T2，?，Tk。这些边也叫做分支，

T1，T2，?，Tk称作根 x 的树之子树（SubTree）。 树的逻辑结构特点： 除根结点之外，每株子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。即一对多的关系，反映了结点之间的层次关系。 森林是 n ≥ 0 株互不相交的树的集合。

二叉树: 一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点和两棵分别称为左子树和右子树的、互不相交的二叉树组成。

结构特点: 每个结点最多只有两个孩子结点，即结点的度不大于2 ,子树有左右之别，子树的次序（位置）不能颠倒。下图为其五种基本形态：

满二叉树：高度为K且有2K-1个结点的二叉树称为满二叉树。 完全二叉树：

设二叉树高度为K，称满足下列性质的二叉树为完全二叉树

（1）所有的叶都出现在K或K-1层；

（2）K-1层的所有叶都在非终结结点的右边；

（3）除了K-1层的最右非终结结点可能有一个（只能是左分支）或两个分支之外，其余非终结结点都有两个分支。 二叉树的性质：

1、二叉树的第 i 层最多有 2i-1 个结点。(i >=1)

2、高度为 K 的二叉树最多有 2K - 1个结点。(K>=1)

3、对任何一棵二叉树, 如果其叶结点有 n0个,度为2 的非叶结点有 n2 个,则有 n0 ＝ n2 ＋ 1

4、具有 n (n 0) 个结点的完全二叉树的高度为

┌ log2(n + 1)┐或

└log2 n ┘+ 1

5、完全（或满）二叉树的顺序存储结构及其性质 ：

如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号, 1,2,?,n，且使该编号对应于数组的下标，则有以下关系： 若i = 1, 则 i 是根结点，无父结点； 若i > 1, 则 i i/2

若 2*i n, 则 i 有左儿子且为 2*i；否则，i 无左儿子； 若2*i+1 n, 则 i 有右儿子且为2*i+1；否则，i 无右儿子； 若 i 为偶数, 且 i < n , 则有右兄弟，且为 i + 1；

若 i 为奇数, 且 i n && i != 1, 则其左兄弟，且为 i-1 ；

二叉树的遍历：

(1)先序遍历：根——>左——>右 (2)中序遍历：左——>根——>右 (3)后序遍历：左——>右——>根

哈弗曼树及其编码：

·术语：路径、路径的长度、树的路径长度（从根结点到每一个叶子结点

的路径长度之和）、带权路径长度（根结点到叶子结点的路径长度相乘权值和）

·构造：每次找两个权值最小的结点进行合并，得到的新节点的权值放到

最后，循环合并，直到只剩下一个结点的时候结束过程，这时候的二叉树就是所求的最优二叉树（哈夫曼树）。

·哈弗曼编码：左分支为0，右分支为1，从根结点到叶子结点所经过的边的编

码就是它所对应的哈弗曼编码。

二、图

1、图的存储结构 1.1 邻接矩阵

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中的边或弧的信息。

设图G有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：

看一个实例，下图左就是一个无向图。

从上面可以看出，无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴，右上角的元和左下角相对应的元全都是相等的。

从这个矩阵中，很容易知道图中的信息。

（1）要判断任意两顶点是否有边无边就很容易了；

（2）要知道某个顶点的度，其实就是这个顶点vi在邻接矩阵中第i行或（第i列）的元素之和；

（3）求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[i][j]为1就是邻接点；

而有向图讲究入度和出度，顶点vi的入度为1，正好是第i列各数之和。顶点vi的出度为2，即第i行的各数之和。

若图G是网图，有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：

这里的wij表示(vi,vj)上的权值。无穷大表示一个计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。下面左图就是一个有向网图，右图就是它的邻接矩阵。

1.2 邻接表

邻接矩阵是不错的一种图存储结构，但是，对于边数相对顶点较少的图，这种结构存在对存储空间的极大浪费。因此，找到一种数组与链表相结合的存储方法称为邻接表。 邻接表的处理方法是这样的：

（1）图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过，数组可以较容易的读取顶点的信息，更加方便。

（2）图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以，用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。 例如，下图就是一个无向图的邻接表的结构。

从图中可以看出，顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。

对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可。如下图所示。

1.3 十字链表

对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才知道，反之，逆邻接表解决了入度却不了解出度情况。下面介绍的这种有向图的存储方法：十字链表，就是把邻接表和逆邻接表结合起来的。 重新定义顶点表结点结构，如下所示。

其中firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout表示出边表头指针，指向该顶点的出边表中的第一个结点。 重新定义边表结构，如下所示。

其中，tailvex是指弧起点在顶点表的下表，headvex是指弧终点在顶点表的下标，headlink是指入边表指针域，指向终点相同的下一条边，taillink是指边表指针域，指向起点相同的下一条边。如果是网，还可以增加一个weight域来存储权值。

比如下图，顶点依然是存入一个一维数组，实线箭头指针的图示完全与邻接表相同。就以顶点v0来说，firstout指向的是出边表中的第一个结点v3。所以，v0边表结点hearvex = 3，而tailvex其实就是当前顶点v0的下标0，由于v0只有一个出边顶点，所有headlink和taillink都是空的。

重点需要解释虚线箭头的含义。它其实就是此图的逆邻接表的表示。对于v0来说，它有两个顶点v1和v2的入边。因此的firstin指向顶点v1的边表结点中headvex为0的结点，如上图圆圈1。接着由入边结点的headlink指向下一个入边顶点v2，如上图圆圈2。对于顶点v1，它有一个入边顶点v2，所以它的firstin指向顶点v2的边表结点中headvex为1的结点，如上图圆圈3。

十字链表的好处就是因为把邻接表和逆邻接表整合在一起，这样既容易找到以v为尾的弧，也容易找到以v为头的弧，因而比较容易求得顶点的出度和入度。

而且除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向图应用中，十字链表是非常好的数据结构模型。 2、图的遍历

图的遍历和树的遍历类似，希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫图的遍历。

对于图的遍历来说，如何避免因回路陷入死循环，就需要科学地设计遍历方案，通过有两种遍历次序方案：深度优先遍历和广度优先遍历。 2.1 深度优先遍历

深度优先遍历，也有称为深度优先搜索，简称DFS。其实，就像是一棵树的前序遍历。 它从图中某个结点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中的所有顶点都被访问到为止。 2.2 广度优先遍历

广度优先遍历，又称为广度优先搜索，简称BFS。图的广度优先遍历就类似于树的层序遍历了。

肆、查找与排序

一、查找

几种查找算法:顺序查找，折半查找，分块查找，散列表。

1、顺序查找的基本思想：从表的一端开始，向另一端逐个按给定值kx 与关键码进行比较，若找到，查找成功，并给出数据元素在表中的位置；若整个表检测完，仍未找到与kx 相同的关键码，则查找失败，给出失败信息。

2、有序表的折半查找基本思想：在有序表中，取中间元素作为比较对象，若给定值与中间元素的关键码相等，则查找成功；若给定值小于中间元素的关键码，则在中间元素的左半区继续查找；若给定值大于中间元素的关键码，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。

3、分块查找（索引查找）的基本思想：分块查找又称索引顺序查找，是对顺序查找的一种改进。分块查找要求将查找表分成 若干个子表，并对子表建立索引表，查找表的每一个子表由索引表中的索引项确定。索引 项包括两个字段：关键码字段(存放对应子表中的最大关键码值) ；指针字段(存放指向对 应子表的指针) ，并且要求索引项按关键码字段有序。查找时，先用给定值kx 在索引表中 检测索引项，以确定所要进行的查找在查找表中的查找分块(由于索引项按关键码字段有序，可用顺序查找或折半查找) ，然后，再对该分块进行顺序查找。 4、散列表-哈希表

二、排序

一、基本概念：

1、 排序：按照一定的关键字，将一个序列排列成想要得到的一个新的序列。

2、 内部排序和外部排序：整个排序过程完全在内存中进行，叫做内部排序。数据量较大需要借助外部存储设备才能完成，叫做外部排序。 3、 主关键字和此关键字：

4、 排序的稳定性：对于相同的元素来说，在排序之前和之后的书讯是一样的，那么这种排序就是稳定的排序，如果顺序发生了变化，那么就是不稳定排序。 二、插入类排序： 1、 直接插入排序：

① 思想：最基本的插入排序，将第i个插入到前i-1个中的适当位置。 ② 时间复杂度：T(n) = O(n2)。

本文来源：https://www.bwwdw.com/article/4fgf.html