数据数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据项是数据结构中讨论的最小单位，是数据记录中最基本的、不可分的数据单位。

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

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

数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。

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

（包括逻辑结构、存储结构和数据运算）I.逻辑结构：线性结构、非线性结构。

II.物理结构：又称为存储结构，是数据的逻辑结构在计算机中的表示（映像），包括顺序存储方法、链式存储方法、索引存储方法、散列存储方法。

数据类型数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。

算法解决一个问题的方法和步骤。

算法的特性：有穷性、确定性、输入、输出、可行性。

算法设计的目的：正确性、可读性、健壮性、高效率与低存储量需求。

时间复杂度T(n)＝ O(F(n))，它表示随问题规模Ｎ增大，算法执行时间增长率与F(n)的增长率相同．F(n)算法的时间复杂性。

原地工作算法执行时，若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。

线性表具有相同特性数据元素的一个有限序列。

是N(N>=0)个同质元素的有限序列，除首尾元素外，每个元素有唯一的前驱和唯一的后继。

顺序表把线性表中的所有元素按照其逻辑顺序，依次存储到指定的存储位置开始的一块连续的存储空间中。

单链表每一个数据元素，都需用两部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放直接后继结点的地址（指针），称为指针域，元素的存储空间可以连续，也可以是不连续的。

而数据元素之间的逻辑关系由指针域来确定。

双向链表线性表采用链式存储时，每个结点除一个数据域外，包含两个指针域，一个指向该结点的直接后继，一个指向该结点的直接前驱，这种方式构成的链表，即为双向链表。

单循环链表是单链表的另一种形式，它是一个首尾相接的链表，表中最后一个结点的指针域由NULL改为指向头结点或线性表的第一个结点，整个链表形成了一个环．栈一种只能在一端进行插入或删除操作的线性表。

队列是一种受限线性表，其限制为允许在表的一端进行插入，而在表的另一端进行删除。

（进行插入的一端称为队尾，进行删除的一端称为队头），先进先出的特点（FIFO）循环队列在队列的顺序存储结构中，把存储空间的首尾逻辑上相连，构成一个环，使得存储空间上只要有空余的地址，就可以继续进行入队列操作，极大利用了物理空间。

用头部和尾部两个指示器表示队列头和队列尾，插入在尾部进行，删除在头部进行。

串串是由零个或者多个字符组成的有限序列。

关键字数据元素的某个数据项的值，用它可以标识列表的一个或一组元素。

子串串中任意个连续的字符组成的子序列称作该串的子串。

模式匹配子串的定位操作称作串的模式匹配。

广义表广义表简称表，是零个或多个原子表所组成的有限序列。

树树(Tree) 的定义树是 n（n≥0）个结点的有限集。

在任意一棵非空树中：(1)有且仅有一个特殊的称为根 (Root) 的结点；(2)当 n>1时，其余结点可分成 m(m>0)个互不相交的有限集 T1,T2, …,T m，其中每一个集合本身又是一棵树，并且称为根的子树（Sub Tree）。

结点的度树的某个结点的分支（子树）个数叫做该结点的度。

树的度树的度是树中所有结点的最大度数。

树的高度树中所有结点的层次的最大值。

叶子结点度为 0 的结点 ,即没有后继的结点。

孩子结点与双亲结点树中某个结点的子树的根结点称为该结点的孩子结点。

相反，称该结点为孩子结点的双亲结点。

兄弟同一个双亲的孩子之间互为兄弟。

祖先一个结点的祖先是指从根结点到该结点的路径上的所有结点。

子孙子孙结点以某结点为根的子树中的任一结点都称为该结点的子孙。

堂兄弟同一层上不同双亲的结点，互称堂兄弟。

森林M 棵互相不相交的树构成的集合,将一棵非空树的根结点删除,树就变成了森林。

二叉树二叉树是每个结点至多有两个孩子结点的一种树。

其中两个孩子结点分别被称为左孩子结点和右孩子结点。

满二叉树深度为K，且有 2K-1个结点的二叉树。

完全二叉树对满二叉树的结点从上到下 ,从左到右进行依次进行编号 ,若有一棵二叉树的每一个结点都与深度为 K 的满二叉树中编号都一一对应时 ,只是最后一层不满 ,称做完全二叉树。

层次遍历按层次编历方式，从某一点V0开始遍历它的所有邻接点V1,V2…… ,再依次访问 V1,V2……的所有未被访问过的邻接点，直到所有的点均遍历完成。

线索在二叉树中，利用空余的指针指向二叉树某种遍历方式的结点的前驱和后继，这种指向前驱和后继的指针，叫线索。

线索二叉树对二叉树以某种次序进行遍历并加上线索的过程叫做线索化。

线索化了的二叉树称为线索二叉树。

路径从树中第一个结点到另一个结点的分支所构成的路线。

路径长度路径上的分支数目树的路径长度树中每个结点到根结点的路径长度之和。

结点的带权路径长度该结点到树根之间的路径长度与结点上权的乘积。

树的带权路径长度 (WPL):树中所有叶子结点的带权路径长度之和。

哈夫曼树设有 N 个权值的结点构造一棵有 N 个叶子结点的二叉树 ,其中 WPL 最小的那棵树,为哈夫曼树。

前缀编码任何一个字符的编码都不是另一个字符编码的前缀 ,这种编码叫做前缀编码 .哈夫曼编码一般以 N 种字符出现的频率做权值 ,构造哈付曼树 ,左孩子边做0,右孩子边做1,那么从根到叶子结点经过的 0 和 1 序列 ,构成了哈夫曼编码（哈夫曼编码是长度最短的前缀编码）平衡因子结点的左子树深度与右子树深度之差。

平衡二叉树或是一棵空树，或左右子树高度差的绝对值小于等于1而且,左右子树也是平衡二叉树。

二叉排序树它或是一棵空树，或是有下面性质的树：若左或右子树不空，左子树所有结点值小于根结点，而右子树所有结点值大于根结点的值，其左右子树也是二叉排序树。

B-树B+树图图（Graph）是顶点 (Vertex)与边 (Edge)的集合E组成的。

弧在有向图中，通常称边为弧。

图中顶点的度、入度、出度顶点 V 的度是图中和顶点 V 相关联的边的数目。

指向顶点v的边的个数称为入度和由顶点v出发的边的个数称为出度。

回路若第一个点和最后一个点相同，则这条路径是一条回路简单路径在用一个顶点序列表示一条路径时，若序列中没有相同的顶点重复出现，则称其为简单路径。

子图图 G = （V,E）与图 G1（V1,E1），若 V1包含于 V，且 E1包含于 E，则 G1是 G的子图。

连通图对于无向图，若 V1到 V2 有路径，称 V1V2是连通的，若图中任意两点都是连通的，则称该无向图是连通图。

连通分量对于一个无向图，其极大连通子图叫做该图一个连通分量。

强连通图对于一个有向图，每两个顶点之间都有路径，称该图为强连通图。

强连通分量有向图的极大强连通子图，称为有向图的强连通分量。

网图的弧或边有与它相关的有意义的数，称作权，带有权值的图称作网。

完全图任何一个有 N 个结点的无向图，若其边数为N(N-1)/2，则这个无向图就是完全图。

有向完全图任何一个有 N 个结点的有向图，若其弧个数为N(N-1)个，则这个有向图就是有向完全图。

深度优先搜索(DFS)类似树的先序遍历，在图中任选一个顶点作为出发顶点 V0，访问 V0后，依次从 V0的没被访问过的邻接点出发进行深度优先搜索。

直到与 V0所连通的所有顶点均被访问。

如果，此时图中还有顶点尚未访问，则从剩余的顶点中再任选一个顶点作为出发顶点V0，重复上述过程，直到图中全部顶点均被访问为止。

广度优先搜索(BFS)首先访问出发点 v，接着依次访问 v 的所有邻接点 w1， w2，…， w t，然后再依次访问与 w1，w2，…， w t邻接的所有未曾访问过的顶点。

依此类推，直至图中所有和源点 v有路径相通的顶点都已访问到为止。

此时从 v 开始的搜索过程结束。

(若 G 是连通图，则遍历完成；否则，在图 C 中另选一个尚未访问的顶点作为新源点继续上述的搜索过程，直至 G 中所有顶点均已被访问为止。

)生成树一个连通图的生成树是指一个极小连通子图，它含有图中的全部顶点，N-1 条边。

最小(代价)生成树在图 G 的所有生成树中 ,树权值最小的那棵生成树 ,称作最小生成树．查找根据给定的关键字值，在特定的表中，确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位臵。

这个过程叫查找。

平均查找长度(ASL)为确定数据元素在表中的位臵，需和给定值进行比较的关键字个数的数学期望值，成为查找算法在查找成功的平均查找长度。

顺序查找对于给定的关键字 K，从线性表的第一个(或最后一个)元素开始，依次向后(或前)与元素的关键字比较，若某个记录的关键字与K相等，查找成功，否则失败。

折半查找对于顺序存储的有序表，先取中间位臵的记录关键字与所给的关键字进行比较，若相等，则查找成功，否则，若给定的关键字比中间的关键字大，在原表的后半部分比较，反之，在原表的前半部分比较，如此反复，逐步缩小范围，直到找到为止，或找不到，最后查找范围为空．分块查找（索引查找）分块查找以前两个为基础，将待查记录分成若干块，每块的关键字无序，但每块的关键字的最大值有序，查找时，先查找到待查记录所在的块，再在块内进行顺序查找。

找块时，即可以用折半查找，也可用顺序查找。

排序根据关键字的递减或递增的次序，把文件中的各个记录依次排列起来，可使一个无序的数据元素序列变成一个有序的序列的操作。

插入排序在一个已排好序的基础上，每一步将下一个待排序记录插到已排好记录的子集上，使之重新有序，直到所有待排记录插完为止。

直接插入排序第1遍，将初始文件中的记录 R1看作有序子文件，将 R2插入这个子文件中。

若 R2的关键字小于 R1的关键字，则 R2插在 R1的前面，否则 R2插在 R1的后面。

第2遍，将 R3插入前面的两个记录的有序子文件中，得到 3 个记录的有序子文件。

依此类推，继续进行下去，直到将 R n插入到前面的 n-1个记录的有序子文件中，最后得到n 个记录的有序文件。

希尔排序是插入排序的一种，又叫缩小增量排序，先按增量进行分组，组内插入排序，然后每次缩短增量，再进行分组和组内插入排序，直到增量为 1 时，进行最后一次排序止。

交换类排序起泡排序起泡排序的过程很简单。

从第一记录开始，相邻的两个记录关键字进行比较，若顺序不对，立即交换，直至 N-1个与第 N 个比较为止。