数据结构名词解释归纳

相关推荐

数据结构名词解释归纳

第一章：

1. 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合

2. 存储结构：数据结构在计算机中的表示成为数据的物理结构，又称存储结构

3. 逻辑结构：是用来描述数据元素之间的逻辑关系

4. 算法：算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或者多个操作

第三章：

1. 栈：栈是限定仅在表尾进行插入或删除操作的线性表

2. 队列：队列是一种先进先出的线性表，它只允许在表的一端进行插入，而在另一端删除元素。

第六章：

1. 完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树

2. 满二叉树：一棵深度为k且有2k-1个结点的二叉树称为满二叉树

3. 哈夫曼树：假设有n个权值{w1，w2，……，wn}，试构造一棵有n个叶子节点的

二叉树，每个叶子结点带权为wi，则其中带权路径长度WPL最小二叉树，称为

最优二叉树或哈夫曼树。

第七章：

1. 完全图：有（1/2）n（n-1）条边的无向图称为完全图

2. 路径：路径是顶点的序列V={Vi0,Vi1,……Vin}，满足(Vij-1,Vij)E 或 <Vij-1,Vij>E,(1<jn)

3. 回路：第一个顶点和最后一个顶点相同的路径称为回路或环

4. 连通图：在无向图中，如果对于图中任意两个顶点vi，vj∈V，vi和vj都是连通的，则称该无向图是连通图

5. 连通分量：连通分量指的是无向图中的极大连通子图。

6. 生成树：一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边

第九章：

1. 二叉排序树：或者是一棵空树；或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

2. 平衡二叉树：又被称为AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。

第十章：

1. 堆：n个元素的序列{k1,k2,…,ki,…,kn}当且仅当满足下关系时，称之为堆。"

ki<=k2i,ki<=k2i+1;或ki>=k2i,ki>=k2i+1." 其中，ki为序列中第i个元素，k2i为第2*i个元素，i>=0 && i<=n/2

数据结构资料(名词解释)2017-04-09 06:54 | #2楼

数据：描述客观事物的数字、字符、图像、语音等可以用符号表示，能输入到计算机内并被计算机处理的信息的总称。

数据元素：数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项组成。数据项是具有独立含义的最小标识单位。数据元素又称为元素、结点、记录。

数据结构：是指同一类数据元素及个数据元素之间存在的关系，数据只有存储在计算机中才能被计算机处理，因此数据结构主要研究在计算机上数据的组织、存储以及基于数据的运算，我们称为数据的逻辑结构、数据的存储结构、数据运算。

数据的逻辑结构：是指对是要处理的数据经过抽象，提取一定特征后，从逻辑上进行描述并形成数据模型。它可以用数据元素的集合和数据元素之间若干关系进行表示。分为线性结构和非线性结构（集合、树形结构、图形结构）

数据的存储结构（物理结构）：逻辑结构和数据元素在计算机内存储方式或方法称为数据的存储结构。数据的存储结构常见有顺序存储和链式存储。

数据类型：一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称.

算法：对给定的待求解问题的一种处理方法或一个求解过程步骤的表述，是有限的指令系列。（一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列）

五个特征：有穷性，确定性，可行性，输入，输出。

时间复杂度：算法所有被执行的语句中，处于最深层循环内的语句被执行的次数。往往与问题的规模n有关，记作为T（n）

c < log2N < n < n * Log2N < n^2 < n^3 < 2^n < 3^n < n!

顺序查找：O（n）二分查找（折半查找）：O（log2n）分块查找：log2(n/2+1)+s/2) 空间复杂度：执行算法所需要的辅助空间的大小定义为空间复杂度，也成为空间代价。线性表：线性表是n(≥0)个数据元素的有限序列，记作（a1, a2, …, an）ai是表中数据元素，n是表长度。

《数据结构名词解释归纳》全文内容当前网页未完全显示，剩余内容请访问下一页查看。

线性表的顺序存储：是用一组地址连续的存储单元依次存储现行表的数据元素。顺序表就是现行表的顺序存储的实现。

顺序表：将线性表中的元素相继存放在一个连续的存储空间中。可利用一维数组描述存储结构。特点：逻辑上相邻的数据元素，其物理存储位置也是相邻的。

单链表：用一组任意的存储单元来依次存储线性表中的各个数据元素，这些存储单元可以是连续的，也可以是不连续的。每个结点只有一个链域的链表称为单链表。

循环链表：循环链表是单链表的变形。最后一个结点的 link 指针不为 NULL，而是指向了表的前端，使整个链表形成一个循环结构。

双向链表：双向链表是指在前驱和后继方向都能游历（遍历）的线性链表。

静态链表：为数组中每一个元素附加一个链接指针，就形成静态链表结构。每个结点由两个数据成员构成：data域存储数据，link域存放链接指针。

栈：限制为仅仅能在表的一端插入和删除的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)。特点：后进先出。

递归：若一个对象部分地包含它自己，或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。

队列：队列是只允许在一端删除，在另一端插入的线性表。允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。

循环队列：队列存放数组被当作首尾相接的表处理。

串(字符串)：是由零个或多个字符构成的有限序列。

Made by zxj

子串：串中任意个连续字符组成的子序列称为该串的子串。主串：包含子串的串相应地称为主串。

数组：是n(n>1)个相同类型的数组元素a1,a2,…an构成的有限序列，且该有限序列存储在一块地址连续的内存单元中。

一维数组：数组是相同类型的数据元素的集合，而一维数组的每个数组元素是一个序对，由下标和值组成。

多-维数组：多-维数组是一维数组的推广。特点是每一个数据元素可以有多个直接前驱和多个直接后继。

特殊矩阵：特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。

树：是由n(n>=0)个结点组成的有限集合。

分支结点：度不为0的结点即为分支结点，亦称为非终端结点。

叶结点：度为0的结点即为叶结点，亦称为终端结点。

结点的度：每个结点足有的子树数或者说后继结点数被定义为该节点的度。

树的度：所有结点的度的最大值为树的度。

二叉树的定义：二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。

满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。特点：每层上的结点数都是最大结点数。完全二叉树一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。特点：所有的叶节点都出现在第k层或k-1层。对任一结点，如果其右子树的最大层次为i，则其左子树的最大层次为i或i+1。

二叉树的顺序存储：所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。

哈夫曼树：最优二叉树，也称哈夫曼树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。

图：图是由非空的顶点集合和一个描述顶点之间关系——边（或者弧）的集合组成，其形式化定义为： G＝（V，E）

无向图：在一个图中，如果任意两个顶点构成的偶对（vi, vj）∈E是无序的，即顶点之间的连线没有方向，则称该图为无向图。

有向图：在一个图中，如果任意两个顶点构成的偶对（vi, vj）∈E是有序的，即顶点之间的连线是有方向的，则称该图为有向图。

无向完全图：在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。

有向完全图：在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。

度：顶点的度（degree）是指依附于某顶点v的边数。

权：与边有关的数据信息称为权。网：带权的图称为网。

连通：在无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连通的。

生成树:对于连通的无向图或者强连通的有向图，从任一定点出发，一次遍历能够访问到图中所有的定点。遍历时经过的边加上所有的定点构成了图的一个连通子图，称为图的一棵生成树。

Made by zxj