数据结构-概念
数据（data ）
对客观事物的符号表示，在计算机科学中是指所有能办理入到计算机中并被计算机程序处理的符号的总称。
数据元素（data element）
数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象（data object）
是性质相同的数据元素的集合，是数据的一个子集。
结构（structure ）
数据元素相互之间的关系
数据结构（data structure）
是相互之间存在一种或多种特定关系的数据元素的集合。
线性结构（linear structure）
结构中的数据元素之间存在一个对一个的关系。
树形结构（tree structure）
结构中的数据元素之间存在一个对多个的关系。
图状结构或网状结构
结构中的数据元素之间存在多个对多个的关系。
逻辑结构
数据元素之间的逻辑关系。
物理结构或存储结构
数据结构在计算机中的表示（或映象）。
数据类型
是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型（ADT: abstract data type）
指一个数学模型以及定义在该模型上的一组操作。
原子类型（atomic data type）
变量的值是不可分解的。
固定聚合类型（fixed-aggregate data type）
值由确定数目的成分按某种结构组成，如复数
可变聚合类型（variable-aggregate data type）
值的数目不确定（可变）。
多形数据类型（polymorphic data type）
指其值的成分不确定的数据类型。
算法（algorithm ）
是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。
时间复杂度（time complexity）
算法执行时间的量度，是算法执行时间的增长率与问题规模n 的关系函数。 频度（frequency count）
语句重复执行的次数。
空间复杂度（space complexity）
算法所需要存储空间的量度。
线性表（linear list）
是n 个数据元素的有限序列，每个数据元素只有一个直接前驱（第一个数据元素除外）和一个后继（最后一个数据元素除外）。
前驱
某数据元素（逻辑关系中）前的数据元素。
后继
某数据元素（逻辑关系中）后的数据元素。
顺序存储结构
用一组地址连续的存储单元依次存储数据元素。
数据域
存储数据元素信息的域。
指针域
存储直接后继存储位置的域。
结点（node ）
由数据域和指针域构成的数据元素的存储映像。
链表（linked list）
由一系列结点按线性关系组成的数据结构。
头结点
链表中的第一个（没有前驱）结点。
尾结点
链表中的最后一个（没有后继）结点
静态链表
由数组描述的链表。
循环链表（circular linked list）
链表中最后一个结点的指针指向头结点。
双向链表（double linked list）
每个结点有两个指针域（直接后继指针域和直接前驱指针域）的链表。 栈（stack ）
仅在表尾进行插入或删除操作的线性表，或称后进先出（LIFO: last in first out）的线性表。
栈顶（top ）
表尾端。
栈底（bottom ）
表头端。
入栈（push ）
在栈顶插入元素的操作。
出栈（pop ）
删除栈顶元素的操作。
顺序栈
用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。
队列（queue ）
是一种先进先出（FIFO: first in first out）的线性表。
链队列
用链表表示的队列。
循环队列
将队列的头和尾相连。
串（string ）
由零个或多个字符组成的有限序列，也称字符串。
子串
串中任意个连续的字符组成的子序列。
主串
包含子串的串。
空串
不包含任何字符的串。
模式匹配
子串的定位操作。
KMP 算法
由D.E. Knuth, V.R. Pratt, J.H. Morris发现的快速求解模式匹配的算法。 树（tree ）
以分支关系定义的层次数据结构，每个结点只有一个直接前驱（根结点除外），但可能有多个直接后继。
叶子或终端结点
树中没有后继的结点。
根结点
树中没有前驱的结点。
结点的度
结点拥有子树的个数。
内部节点
度不为0的结点（除根外）。
树的深度
树中结点的最大层次
森林（forest ）
若干棵互不相交的树的集合。
二叉树（binary tree）
每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且子树有左右之分。
有序树
树中结点的各子树从左至右有次序。
无序树
树中结点的各子树无次序。
满二叉树
一棵深度为k 且有2k-1个结点的二叉树。
完全二叉树
深圳为k, 结点数为n 的二叉树，树中每个结点的编号与深度为k 的满二叉树相同。
遍历二叉树
按某条搜索路径巡方树中每个结点，使每个结点均被访问一次，且仅被访问一次。
先序（根）遍历二叉树
先访问（各树及子树）根节点，然后访问左子树，再访问右子树的遍历。 中序（根）遍历二叉树
先访问左子树，再访问根结点，最后访问右子树。
后序（根）遍历二叉树
先访问左子树，再访问右子树，最后访问根结点。
线索二叉树（threaded binary tree）
加上线索的二叉树。
最优二叉树
带权路径长度最小的二叉树。
树的路径长度
从树根到每一个结点的路径长度之和。
树的路径长度
任意两个有路径相通的结点之间分支的数目。
Huffman （赫夫曼）树
所有叶子结点带权路径长度之和最小的二叉树。
图（graph ）
图中所有结点的关系是任意的，即都有可能相关。
顶点（vertex ）
图中的数据元素。
弧（arc ）
从图中某顶点指向另一顶点的边。
边（edge ）
图中两个顶点有关系，则存在一条边。
有向图（digraph ）
图中的边（弧）有方向。
无向图（undigraph ）
图中的边无方向。
完全图（completed graph）
具有n 个结点的图中，存在n （n-1）/2条边。
子图（subgraph ）
如果一个图的顶点和边均是另一个图的顶点和边的子集，则称该图为另一图的子图。
图的路径（path ）
从图中某顶点到另一个顶点的边（或弧）的序列。
连通图（connected graph）
图中每个顶点都有路径相通。
连通图的生成树
是图的极小连通图，其结点个数与图中顶点个数相同，而边（分支）的数目为顶点数减一。
深度优先探索（depth first search）
是树的先根遍历的推广。
广度优先探索（breadth first search）
按层次进行图的遍历。
最小生成树（minimum cost spanning tree）
连通图中最小代价生成树，即生成树中各边的代价之和最小。
有向无环图（DAG: directed acycline graph）
是一种有向图，且图中没有回路。
拓扑排序（topological sort）
由某个集合上的一个偏序得到该集合上的一个全序的操作。
偏序（partial order）
集合中仅有部分成员之间可比较。
拓扑有序（topological order）
人为地在无关系的成员之间加上关系，使所有成员之间均可比较的操作。 AOV -网（activity on vertex network）
顶点表示活动的有向图。
AOE-网（activity on edge network）
边表示活动的有向图。
关键路径（critical path）
AOE-网中，路径长度最长的路径。
最短路径
从某顶点到另一顶点多个路径中，代价最小的路径。
查找（search ）
根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。
查找表（search table）
由同一类型的数据元素（或记录）构成的集合。
静态查找表（static search table）
查询某个“特定的”数据元素是否在查找表中，检索某个“特定的”数据元素的各种属性。
动态查找表（dynamic search table）
在查找过程中，同时插入查找表中不存在的数据元素，或者从查找表中删除某个已存在的数据元素。
关键字（key ）
数据元素（或记录）中鞭个数据项的值，用它可以标识（识别）一个数据元素（或记录）。
主关键字（primary key）
可以惟一标识一个数据元素（或记录）的关键字。
次关键字（secondary key）
用以识别若干记录的关键字。
顺序查找（sequential search）
从表中最后一个记录开始依次向前查找每个数据元素（或记录），找到则成功，否则不成功。
折半查找（binary search）
先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到指定记录为止。
分块查找
先用折半查找法找到记录所在的块，再在块中顺序查找。
二叉排序树（binary sort tree）
左子树上结点的值均小于根节点，右子树上结点的值均大于根结点。 平衡二叉树（balanced binary tree or height balanced tree）
又称AVL 树。是左子树、右子树深度之差的绝对值不超过1的二叉排序树。 哈希表（hash table）
根据设定的哈希函数和处理冲突的方法，将一组关键字映像到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置。 哈希函数（hash function）
将一组关键字映像到一个有限的连续的地址集合上的函数。
冲突（collision ）
不同的关键字通过哈希函数得到同一个地址的现象。
散列
哈希函数的映像过程。
排序（sort ）
将一组记录，按关键字的值的大小排列记录次序的过程。
内部排序
待排序记录存放在计算机随机存储器中进行的排序过程。
直接插入排序（straight insertion sort）
将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。
希尔排序（Shell’s sort）
先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
起泡排序（bubble sort）
依次比较相邻记录，如为“逆序”，则交换之，直到所有记录有序为止。 快速排序（quick sort）
通过一趟将待排记录分割成独立的两个部分，其中一部分记录的关键字均比另一部分记录的关键字小。再对两个部分分别进行快速排序。
简单选择排序（simple selection sort）
从未排序的记录中，选中最小（或最大）的记录，然后再选次小（或次大）的记录，直到所有记录有序为止。
归并排序（merging sort）
先将所有记录分成小组（一般每小组两个元素），先对小组内记录进行排序；然后将若干个小组（一般两个小组）归并成一个有序的大组。继续以上过程，直到所有记录归并到一个组中为止。
基数排序（radix sorting）
按关键字的值，先按最高位（或最低位）的值将记录排成有序序列；再按次高位（或次低位）的值将记录排成有序序列；直到最低位（或最高位）为止