数据结构名词解释.doc

该【数据结构名词解释 】是由【286919636】上传分享，文档一共【8】页，该文档可以免费在线阅读，需要了解更多关于【数据结构名词解释 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。。-可编辑修改-,是能够被计算机输入,识别,处理的各种符号,是计算机化的信息。,一个元素由若干个数据项构成。,是数据集合中的个体,在计算机程序中,通常作为一个整体进行考虑和处理。,是数据的一个子集。,插入,删除,合并,排序,统计以及简单计算等的操作过程。(即数据的逻辑结构和物理结构),并对这种结构定义相适应的运算,设计出相应的算法,且确保经过这些运算后所得到的新结构仍然是原来的结构类型。。。抽象数据类型的定义取决于它的一组逻辑特性,而与其在计算机内部如何表示和实现无关。。(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-(存储结构)物理结构又称为数据的存储结构,是指数据的逻辑结构在计算机中的映像(表示),即数据结构在计算机中的存储方法。,利用空余的指针指向二叉树某种遍历方式的结点的前驱和后继,这种指向前驱和后继的指针,叫线索。。线索化了的二叉树称为线索二叉树。,是零个或多个原子表所组成的有限序列。,称为有向图的强连通分量。。,每一步将下一个待排序的记录有序地插入到已排好序记录的子集上,直到将所有待排记录全部插入为止。。。。,它是一个首尾相接的链表,表中最后一个结点的指针域由null改为指向头结点或线性表的第一个结点,,必有N+1个空域,利用这些空域存放某种遍历的前驱和后继,。一般表示为一个二元组,即,图G=(V,E),各个顶点之间是多对多的关系。,先取中间位置的记录关键字与所给的关键字进行比较,若相等,则查找成功,否则,若给定的关键字比中间的关键字大,在原表的后半部分比较,反之,在原表的前半部分比较,如此反复,逐步缩小范围,直到找到为止,或找不到,最后查找范围为空.。-可编辑修改-,树权值最小的那棵生成树,(BFS)首先访问出发点v,接着依次访问v的所有邻接点w1,w2,…,wt,然后再依次访问与wl,w2,…,wt邻接的所有未曾访问过的顶点。依此类推,直至图中所有和源点v有路径相通的顶点都已访问到为止。此时从v开始的搜索过程结束。(若G是连通图,则遍历完成;否则,在图C中另选一个尚未访问的顶点作为新源点继续上述的搜索过程,直至G中所有顶点均已被访问为止。),从左到右进行依次进行编号,若有一棵二叉树的每一个结点都与深度为K的满二叉树中编号都一一对应时,只是最后一层不满,,,这种指针叫线索,线索后了的二叉树,,,,将一棵非空树的根结点删除,(WPL),其中WPL最小的那棵树,,构造哈付曼树,左孩子边做0,右孩子边做1,那么从根到叶子结点经过的0和1序列,。包括入度和出度两种。=(V,E)与图G1=(V1,E1),若V1包含于V,且E1包含于E,则G1是G的子图。。-可编辑修改-对于无向图,若V1到V2有路径,称V1V2是连通的,若图中任意两点都是连通的,则称该无向图是连通图。,称作权,带有权值的图称作网。(DFS)类似树的先序遍历,在图中任选一个顶点作为出发顶点V0,访问V0后,依次从V0的没被访问过的邻接点出发进行深度优先搜索。直到与V0所连通的所有顶点均被访问。如果,此时图中还有顶点尚未访问,则从剩余的顶点中再任选一个顶点作为出发顶点V0,重复上述过程,直到图中全部顶点均被访问为止。,其余顶点均不相同的回路称为简单回路。,若序列中没有相同的顶点重复出现,则称其为简单路径。,在特定的表中,确定一个其关键字与给定值相同的数据元素,并返回该数据元素在列表中的位置。这个过程叫查找。(ASL)为确定数据元素在表中的位置,需和给定值进行比较的关键字个数的数学期望值,成为查找算法在查找成功的平均查找长度。,或是有下面性质的树:若左或右子树不空,左子树所有结点值小于根结点,而右子树所有结点值大于根结点的值,其左右子树也是二叉排序树。,从线性表的第一个(或最后一个)元素开始,依次向后(或前)与元素的关键字比较,若某个记录的关键字与K相等,查找成功,否则失败。,或左右子树高度差的绝对值小于等于1而且,左右子树也是平衡二叉树。,每一步将下一个待排序记录插到已排好记录的子集上,使之重新有序,直到所有待排记录插完为止。(索引查找)分块查找以前两个为基础,将待查记录分成若干块,每块的关键字无序,但每块的关键字的最大值有序,查找时,先查找到待查记录所在的块,再在块内进行顺序查找。找块时,即可以用折半查找,也可用顺序查找。,这个操作叫做拓扑排序。,开始将每个元素当成是一个个单独的有序表,逐渐表个数以原来一半的速度递减,每个表的长度却是原来长度的2倍增加,不断重复,直到最后是一个表,而表的长度是元素个数为止。。-可编辑修改-,把文件中的各个记录依次排列起来,可使一个无序的数据元素序列变成一个有序的序列的操作。,又叫缩小增量排序,先按增量进行分组,组内插入排序,然后每次缩短增量,再进行分组和组内插入排序,直到增量为1时,进行最后一次排序止。;,以致内存一次不能容纳全部记录,在排序过程中对外存进行访问的排序过程。=Kj(1≤i≤n,1≤j≤n,i≠j),且在排序前的序列中Ri领先于Rj(即i<j)。若在排序后的序列中Rj领先于Ri,则称所用的排序方法是不稳定的。=Kj(1≤i≤n,1≤j≤n,i≠j),且在排序前的序列中Ri领先于Rj(即i<j)。若在排序后的序列中Ri仍领先于Rj,,将初始文件中的记录R1看作有序子文件,将R2插入这个子文件中。若R2的关键字小于R1的关键字,则R2插在R1的前面,否则R2插在R1的后面。第2遍,将R3插入前面的两个记录的有序子文件中,得到3个记录的有序子文件。依此类推,继续进行下去,直到将Rn插入到前面的n-1个记录的有序子文件中,最后得到n个记录的有序文件。。从第一记录开始,相邻的两个记录关键字进行比较,若顺序不对,立即交换,直至N-1个与第N个比较为止。得到一个最大(或最小)的关键字记录的结果位置。-i+1(i=1,2,3…n-1)个记录中选择关键字最小的记录作为有序序列中第i个记录。,存放到整个表排好序后,它应当在的最终位置上。将原来的待排序表分割成两部分,其中一部分表中的关键字均比另一部分表中的关键字小。然后,分别对两部分表用同样的方式进行排序,直到整个表排好序。,把交换后具有最大序号的记录输出,得到一个排序的结果。这时的树不再是堆树,排序暂时停止。然后,必须把树重新调整成堆树,再重复上述过程,直到所有记录都排好序。。把含有N个记录的无序表当成N个有序的子表,每个子表的的长度为1,然后,利用两两归并,。-可编辑修改-得到n/2个长度为2或1的有序子表。再两两归并直到得到长度为N的一个有序表。,每两个顶点之间都有路径,称该图为强连通图。,其极大连通子图叫做该图一个连通分量。“分配”和“收集”两种操作对单逻辑关键字进行排序的一种内排序方法。。-可编辑修改-THANKS!!!致力为企业和个人提供合同协议,策划案计划书,学****课件等等打造全网一站式需求欢迎您的下载,资料仅供参考