数据结构名词解释.doc

,是能够被计算机输入,识别,处理的各种符号,是计算机化的信息。,一个元素由若干个数据项构成。,是数据集合中的个体,在计算机程序中,通常作为一个整体进行考虑和处理。,是数据的一个子集。,插入,删除,合并,排序,统计以及简单计算等的操作过程。(即数据的逻辑结构和物理结构),并对这种结构定义相适应的运算,设计出相应的算法,且确保经过这些运算后所得到的新结构仍然是原来的结构类型。。。抽象数据类型的定义取决于它的一组逻辑特性,而与其在计算机内部如何表示和实现无关。。(N)=O(F(N)),它表示随问题规模N增大,算法执行时间增长率与F(N)的增长率相同,F(N)算法的时间复杂性。,若额外空间相对于输入数据量来说是常数,则称此算法为原地工作。,是N(N>=0)个同质元素的有限序列,除首尾元素外,每个元素有唯一的前驱和唯一的后继。,,把存储空间的首尾逻辑上相连,构成一个环,使得存储空间上只要有空余的地址,就可以继续进行入队列操作,极大利用了物理空间。用头部和尾部两个指示器表示队列头和队列尾,插入在尾部进行,删除在头部进行。,都需用两部分来存储:一部分用于存放数据元素值,称为数据域;另一部分用于存放直接后继结点的地址(指针),称为指针域,元素的存储空间可以连续,也可以是不连续的。而数据元素之间的逻辑关系由指针域来确定。,每个结点除一个数据域外,包含两个指针域,一个指向该结点的直接后继,一个指向该结点的直接前驱,这种方式构成的链表,即为双向链表。,又叫缩小增量排序,先按增量进行分组,组内插入排序,然后每次缩短增量,再进行分组和组内插入排序,直到增量为1时,进行最后一次排序止。,若其边数为N(N-1)/2,,若其弧个数为N(N-1)个,则这个有向图就是有向完全图。,从某一点V0开始遍历它的所有邻接点V1,V2……,再依次访问V1,V2..的所有未被访问过的邻接点,,用它可以标识列表的一个或一组元素。。。,是插入和删除操作在同一端进行的,是后进先出的线性表。(n>=0)个结点的有限集。在任意一棵非空树中:(1)有且仅有一个特殊的称为根的结点;(2)当n>1时,其余结点可分成m(m>0)个互不相交的有限集T1,T2,...,Tm,其中每一个集合本身又是一棵树,并且称为根的子树。。其中两个孩子结点分别被称为左孩子结点和右孩子结点。。。相反,称该结点为孩子结点的双亲结点。(子树)个数叫做该结点的度。。。,它含有图中的全部顶点,N-1条边。,且有2K-(存储结构)物理结构又称为数据的存储结构,是指数据的逻辑结构在计算机中的映像(表示),即数据结构在计算机中的存储方法。,利用空余的指针指向二叉树某种遍历方式的结点的前驱和后继,这种指向前驱和后继的指针,叫线索。。线索化了的二叉树称为线索二叉树。,是零个或多个原子表所组成的有限序列。,称为有向图的强连通分量。。,每一步