数据结构名词解释和时间复杂度
数据结构：
是相互之间存在一种或多种特定关系的数据元素的集合，是计算机存储和数据组织的方式，它分为三个方面，即数据的逻辑结构，数据的物理结构，数据的操作。
数据元素：
数据元素构成数据，也是数据的基本单位。
数据项：
是数据不可分割的最小单位，用它可以识别一个或一个组数据，一个数据元素可由若干数据项组成。
数据对象：
是性质相同的数据元素的集合，是数据的一个子集。
数据：
是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中被计算机程序处理的符号的总称，是计算机化的信息。
数据类型：
是一个值的集合以及定义在这个值集上的一组操作，可分为原子类型和结构类型。
抽象数据类型：
是基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。
物理结构（存储结构）
：是指数据的逻辑结构在计算机中的映像（又称表示），即数据结构在计算机中的存储方法。
算法
：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。
存储密度：
指结点数据本身所占存储量和整个结构所占存储量之比。
根据数据元素之间关系的不同特性，有四类基本的数据结构：
集合结构，线性结构，树形结构，图形结构（网状结构）。
数据的存储结构有：
顺序存储结构、链式（链接）存储结构、索引结构、散列存储结构
常用的两种存储结构：
顺序存储结构和链式存储结构。
算法的五个特性：
确定性、有穷性、可行性、输入和输出。（可以有零个或多个数据输入，但必须至少有一个输出数据。
算法设计的要求：
正确性、可读性、稳健性、高效率低存储量。
（算法分析）衡量算法的两个标准：
时间复杂度和空间复杂度。
结构化程序设计思想的要求
：自顶向下、逐步细化、模块化设计、结构化编程。
顺序存储结构的特点？（顺序存储和链式存储的优缺点）
1、结点中只存放数据元素本身的信息，无附加内容。（优点）
4、插入、删除数据元素时，由于需要保持数据元素之间的逻辑关系，必须大量移动元素，因此实现起来比较慢。（缺点）
5、顺序存储是一种静态结构、存储密度大，空间利用率低，预分配空间大小难以确定，（缺点）
链式存储结构的特点？（顺序存储和链式存储的优缺点）
1、结点中除存放数据元素本身的信息外，还需存放附加的指针。
2、不能直接存取数据元素，需顺链路查找，存取速度较慢。
3、插入、删除元素时不必移动其他元素，速度较快。（优点）
4、链式存储是一种动态存储结构，空间利用率高，存储密度小，不存在预分配空间问题。
线性结构的特点
：是除第一个元素和最后一个元素外，每个数据元素都有唯一的前驱和唯一的后继，第一个元素没有前驱，最后一个元素没有后继，关系是一对一的。
非线性结构的特点是：
表示结点间关系的前驱后继不具有唯一性，结点间是一对多或多对多的关系。
3、数据的物理结构是数据的逻辑结构在计算机中的映像。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合，是计算机存储和数据组织的方式，它分为三个方面，即数据的逻辑结构，数据的物理结构，数据的操作，它偏向于逻辑方面，而数据类型是一个值的集合以及定义在这个值上的一组操作，可分为原子类型和结构类型，它偏向于物理方面的线性表。
线性表：
是最常用，最简单的一种数据结构，一个线性表是n个数据元素的有限序列，除首尾元素外，每个元素有唯一的前驱和唯一的后继。
顺序表：
采用顺序存储结构的线性表通常称为顺序表。
结点：
由数据元素和指示其后继结点地址的信息组成的存储映像称为结点。
循环链表：
是另一种形式的链式存储结构，它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
双链表：
采用链式存储结构的线性表，每个结点除一个数据域外，还有两个指针域，其一指向直接前驱，另一指向直接后继。
静态单链表：
是利用一块连续的空间，按链表的存储方式组织数据，按顺序存储结构分配空间，所构成的一种链表。
头指针：
是指向链表表头结点的指针，只要链表存在，该指针始终不会改变，单链表由头指针唯一确定，因单链表可以用头指针的名字来命名。
头结点：
在链表的开始结点之前附加的一个结点，是链表的表头，当链表不空时，其内的指针指向链表的第一个结点，当链表是空链表时，该指针为空指针。
线性表的两种基本的存储结构：
顺序结构和链式存储结构。
从链接方式的角度看，链表可以分为单链表，循环链表，双链表。
优点：
1、无需为表示结点间的逻辑关系而增加额外的存储空间，存储密度大
缺点：
1．插入，删除运算不方便，需移动大量元素，效率较低
适用于需要大量增删元素，而对访问元素几乎无要求的程序
1．头指针是指向链表表头结点的指针，只要链表存在，该指针就不会变化，已知该指针便己知该链表
2．头结点是在链表的开始结点之前夫妇家的一个结点，当链表是空链表时，该指针为空指针，因此空表和非空表的处理也就统一了
在用头指针表示的单循环链表中，找开始结点a1的时间是O（1），然而要找终端结点an则需要从头指针开始遍历整个链表，其时间是O（n），在很多实际问题中，表的操作常常是在表尾进行的，此时头指针表示的单循环链表就显得不够方便，如果改用尾指针来表示单循环链表，则查找开始结点a1和终端结点an都很方便查找时间都是O（1）
栈：
也叫后进先出表，是限定仅在表尾进行插入和删除操作的线性表，表尾端称为栈顶，表头端称为栈底，不含元素的空表称为空栈
队列：
是一种先进先出的线性表，它只允许在表的一段进行插入，而另一端删除元素，允许插入的一端叫做队尾，允许删除的一端称为队首
链队列：
用链表示的队列，需要两个指针分别指示队头和队尾，为了操作方便，也给链队列添加一个哨兵结点
循环队列：
队列是＂先进先出表”，随着入队出队的进行，会使整个队列整体向后移动，当队尾指针移到最后，若再有元素入队就会出现“假溢出”，因为此时队头部分还有空间可用，循环队列是将队列的数据区看成头尾相接的循环结构，可解决“假溢出”
双端队列：
是限定插入，删除在表的两端进行的线性表，这两端分别称为端点。
满的判断条件：
s.top＝ stack.size
循环队列采用少用一个元素存储空间的办法下，判断队列满的条件：
循环队列判断队列满的方法有：
少用一个元素存储空间，增设一个标志量，使用计数器
栈的应用：
数制转换，括号匹配，表达式求值，汉诺塔（递归用栈实现）
在一个程序中经常会同时使用多个栈，使用顺序存储结构的栈．空间大小难以估计，这样使得有的栈已出，有的栈还有空闲空间，可以让多个栈共享一个足够大的连续向量空间（数组），通过利用栈的动态特性来使其存储空间互相补充，这就是多栈的共享技术，两个栈共享空间，主要利用了“栈底位置不变，栈顶位置动态变化”的特性
相同点：
都是线性结构，都是逻辑结构的概念，都可以用顺序存储或链式存储，栈和队列是两种特殊的线性表，即受限的线性表，只对插入和删除运算加以限制
不同点：
1，运算规则不同，线性表为随机存取，而栈只允许在一端进行插入、，删除运算，因而是后进先出表，队列只允许在一端进行插入，另一端删除运算，因而是先进先出表
2．用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理，指
子串：
串中任意个连续的字符组成的子序列称作该串的子串
子串在主串中的位置：
子串的第一个字符在主串中的位置表示
串的存储结构：顺序存储结构，链式存储结构，堆存存储结构
串的逻辑结构与线性表极为相似，区别仅在于串的数据对象约束为字符集，然而串的操作与线性表有很大的差别，在线性表基本操作中，大多以单个元素作为操作对象；而在串的基本操作中通常以“串的整体”作为操作对象
程序运行前被分配以一个给定大小的数组空间的顺序串称为静态顺序串，在程序
运行过程中，动态分配空间能以链表形式存在的顺序串称为动态顺序串，静态串在内存一片连续的数据区中，动态串在内存堆中．
串的链式存储与串顺序存储相比，在哪些操作上效率更高？
广义表：
是由零个或多个单元素或子表所构成的有限序列，是线性表的推广，也有人称其为列表
矩阵的压缩存储：
有的矩阵中有许多值相同元素或者是零元素，为了节省存储空间对这类矩阵采用多个值相同的元素只分配一个存储空间，有时零元素不存储的存储策略，称为矩阵的压缩存储
特殊矩阵：
值相同的元素或者零元素在矩阵中的分布有一定规律的矩阵称为特殊
稀疏矩阵
：非零的数据元素个数很少的矩阵称为稀疏矩阵
对称矩阵：
一个n阶方阵，若满足aij=aji，则称该矩阵为对称矩阵
三角矩阵：
主对角线上方和下方的元素（不包括对角线）均为常数或零元素的矩阵
行表：
记录稀疏矩阵中每行非零元素在三元组表中的起始位置的表
三元组表
：若线性表顺序存储的每一个结点均是三元组，则该线性表的存储结构称为三元组表
带状矩阵：
所有非零元素均集中在以主对角线为中心的带状区域的矩阵
1广义表是线性表的推广，是由零个或多个单元素或子表所构成的有限序列
2．线性表的成分都是结构上不可分制的单个数据元素，而广义表的成分既可以是单元素，也可以是有结构的表其定义是递归的定义
树：
是n个结点的有限集合，n≥0，有且只有一个称为根的结点，根结点无前驱
有序树
：树中结点的各子树看成是从左至右依次有序的，且不能交换
二叉树：
是一种树型的结构，它的特点是每个结点之多有两棵子树，且有左右之分，不可任意颠倒。
完全二又树：
深度为k的有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时
满二叉树：
是一棵深度为k的，且有（2^k）-1个结点的二又树
遍历二叉树：
是按照某种搜索路径巡访二叉树中的每个结点，使得这些结点均被访问一次
线索二叉树
：由每个结点中包含左指针，左标志位，数据域，右标志位，右指针五部分组成的二叉链表，叫做线索链表，指向前驱或后继的指针叫做线索，以二又树某种遍历顺序给空指针加线索的过程叫做线索化，线索化了的二叉树称为线索二叉树
哈夫曼树：
又称最优二叉树，是一类带权路径长度最短的树．
哈夫曼编码：
在哈夫曼树中，约定左分支代表0，右分支代表1，把叶子结点到根结点的路径上的左右分支代表的码从下至上一次连接起来，组成的字符串称为该叶子结点的哈夫曼编码，这就是哈夫曼编码
二又排序树：
或者是空树，或者是符合以下性质的二叉树
1若它的左子树不空，则左子树上所有结点均小于它的根结点值
2．若它的右子树不空则右子树上所有结点均大于它的根结点值．
平衡二叉排序树（AVL树）
：或者是空树，或者是符合一下性质的二又排序树
深度为k的二又树中，结点总数最多为（2^k）—1个
二叉树中，n0＝n2＋1，n2＝n0－1（no为二又树中度为0的结点的个数n2为二叉树中度为2的结点的个数）
有n个结点的完全二叉树，深度为k，则k＝[log2n]＋1（log以2为底括号是向下取整不是方括号）
二叉树的两种存储结构
：顺序存储结构和链式存储结构
树的三种常用的存储方法
：孩子表示法，双亲表示法和孩子兄弟表示法
表示结点间关系的前驱后继不具有唯一性，结点间是一对多或多对多的关系
因为二又树是有序树，所有有左右之分，这是五棵不同的二叉树，但若下列五棵是树，不是二叉树，则后面四种为同一棵树
图
：图G由两个集合V和E组成，记为G＝（V，E），其中V是顶点的有穷非空集合，E是由V中顶点的序偶组成的有穷集，这些序偶称为边或弧
完全图：
边数恰好等于n（n－1）/2的n个顶点的无向图称为完全图（无向图中任意两个顶点之间都有一条边相连，称该图为完全图）
有向完全图
：有n(n-1）条边的有向图称为有向完全图（图中每个顶点和其余n-1个顶点都有弧相连）
连通图：
在无向图中，任意两个顶点之间都有路径相通
强连通图：
在有向图中，任意两个顶点之间都有来回路径相通
生成树：
生成树是无向连通图的一个极小连通子图，它含有图中的全部顶点和使任意顶点都连通的最少的边
邻接矩阵：
表示图中结点之间关系的矩阵称为邻接矩阵
邻接表：
由顶点数据表和表示数据关系的边（弧）构成的表
十字链表：
可以把它看成是将有向图的
邻接表
和逆邻接表结合起来形成的一种存
图的遍历：
从某一顶点出发按序访问图中所有结点，且使每个结点仅被访问一次
拓扑排序：
由某个集合上的一个偏序得到该集合上一个全序的操作称为拓扑排序
关键路径：
在AOE网中，从源点到汇点的最长路径称为关键路径
AOE网：
用顶点表示事件，用弧表示活动，弧的权值表示活动所需的时间，构造的有向网称为AOE网
简单路径：
一条路径上除了开始顶点和结束顶点外，其余顶点均不相同
有向图中，所有顶点的入度与出度的和等于边个数的2倍
图的存储方法：邻接矩阵，邻接表，邻接多重表，十字链表和边集数组
1．对于无向图而言，它的邻接矩阵是对称矩阵，因此可以采用特殊矩阵的压缩存储法，但对于有向图而言，其中的弧是有方向的，因此有向图的邻接矩阵不一定是对称矩阵，对于有向图的邻接矩阵的存储则需要n*n个存储空间．
2．采用邻接矩阵表示法，便于判断图中任意两个顶点之间是否有边相连，即根据邻接矩阵中的信息来判断，另外还便于求得各个顶点的度，对于无向图而言，其邻接矩阵第i行元素之和就是图中第i个顶点的度
1．n个顶点，e条边的无向图，若采取邻接表作为存储结构，需要n个顶点数据和2e个表示边的结点，显然在边很稀疏的情况下，用邻接表存储所需的空间比邻接矩阵所需的空间少
2．无向图的度，在无向图的邻接表中，顶点Vi的度恰好就是第i个边链表上结点的
3．有向图的度，在有向图中，第i个边链表上结点的个数就是顶点Vi的出度，只需通过表头向量表中找到第i个顶点的边链表的头指针，实现顺链查找计数即可
假设初始状态是图中所有顶点均未被访问过，则深度优先搜索可从某个顶点V出发，首先访间此顶点（称此顶点为初始点），然后依次从V的任一个未被访问的邻接点出发进行深度优先搜索遍历，直到图中所有与有路径相通的顶点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作为初始点，重复上述步骤，直到图中所有顶点都被访问过为止
1．从图中某个顶点VO出发，首先访问VO，依次访问Vo的各个未被访间的邻接点
2．分别从这些邻接点（端结点）出发，依次访问各个未被访问的邻接点，访问时应保证：如果Vi和Vk为当前结点，且Vi在Vk之前被访问，则Vi的所有未被访问的邻接点应在Vk的所有未被访问的邻接点之前访问
3．重复步骤2，直到所有结点均没有未被访问的邻接点
4．若此时还有顶点未被访问，则选一个未被访问的顶点作为起始点，重复上述过程，直至所有顶点均被访问过为止
关键字：
是数据元素中某个数据项的值，用它可以识别一个或一组数据元素
査找：
根据给定的关键字的值，检索某个与该值相等的数据元素是否在查找表中
静态査找表：
査询某个特定的数据元素是否在査找表中，检素某个特定的数据元素的各种属性
动态査找表：
在查找过程中同时插入查找不存在的数据元素，或者从査找表中删除已存在的某个数据元素
平均査找长度（ASL）
：为确定数据元素在査找表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度．
冲突：
两个不同的关键字，其散列函数值相同，因而被映射到同一表位置的现象称为冲突
哈希函数的构造方法：
直接定址法，数字分析法，平方取中法，折叠法，除留余数法和随机数法
哈希函数处理冲突的方法：
开放地址法，再哈希法，链地址法和建立一个公共溢出区。
顺序查找的基本思路：
对于给定的关键字k，从线性表的第一个元素开始依次向后与记录的关鍵字域相比较，如果某个记录的关键字等于k，则查找成功，否则查找失败，平均查找长度ASL=3（n＋1）/4．
折半（二分）查找的基本思路：
先取表的中间位置的记录关键字和所给关键字进行此较，若相等，则查找成功，如果给定关键字比该记录的关键字小，则说明所要查找的记录只可能在表的前半部分，反之，则在后半部分，重复步骤，每一次比较就可以将查找范围缩小一半，直到找到给定的关键字的记录，查找成功，找不到为查找失败，平均查找长度 ASL＝log2（n＋1）-1
分块查找（索引顺序表查找）的基本思路：
先确定待査记录所在的块（子表）然后在块中顺序查找．平均查找长度ASL=1/2(n/s)+1]+s/2
哈希查找（散列查找）的基本思路：
在进行查找时，在记录的存储位置与它的关键字之间建立一个确定的对应关系h，以线性表中每个元素的关键字k为自变量通过函数h（k）计算出该元素的存储位置，我们将h函数称为散列函数或哈希函数，这种査找方法称为散列查找或哈希查找
排序：
就是按关键字值的递增或递减的次序，把文件中的各记录一次排列起来，可使一个无序文件变成有序文件的一种操作
排序算法的稳定性：
相同元素排序前后的相对位置没有发生变化，则为稳定，反之为不稳定
内部排序：
在排序过程中，所有待排序记录都放在内存中进行的排序称为内部排
外部排序：
当待排序的记录很多，排序时不仅要使用内存，而且还要使用外部存储器的排序方法称为外部排序
各排序方法的基本思想，时间复杂度，空间复杂度及稳定性？
直接插入排序的基本思想：
直接插入排序是一种最简单的排序方法，基本操作是将条记录插入到已排好的有序表中，从而得到一个新的，记录数量増一的有序表
时间复杂度O（n^2）．空间复杂度O（1）直接插入排序是稳定的
希尔排序的基本思想：
先将整个待排元素序列分割成若干子序列分别进行直接插
入排序，然后依次缩减增量再进行排序，使整个序列中的元素基本有序时，再对全体元素进行一次直接插入排序，实质就是分组直接插入排序时间复杂度O（n^2）
冒泡排序的基本思想：
先将第一个记录的关键字和第二个记录的关键字进行比较
若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字，以此类推，直至第n－1个记录和第n个记录的关键字进行过比较为止．时间复杂度O（n^2）．空间复杂度O（1）冒泡排序是稳定的
快速排序的基本思想
：通过一趟排序将要排序的数据分割成独立的两部分，其中
部分的所有数据都比另一部分的所有数据都要小然后再按此方法对这两部分数
据进行快速排序整个排序过程可以递归进行，以达到整个序列有序．时间复杂度
O（nlog2n）空间复杂度O（nlog2n）快速排序是不稳定的
直接选择排序的基本思想：
对于给定的一组记录，经过第一轮比较后得到最小的
记录，然后将该记录与第一个记录的位置交换，接着对不包括第一个记录以外的其他记录进行第二轮比较，得到最小的记录并与第二个记录的位置交换，重复该过程，直到进行比较的记录只有一个时为止．时间复杂度O（n^2）．空间复杂度O（1）．直接选择排序是不稳定的
堆排序的基本思想：
堆排序是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种，可以利用数组的特点快速定位索引的元素，堆分为大根堆和小根堆，是完全二叉树．时间复杂度o（nlog2n）．空间复杂度O（1）堆排序是不稳定的
归并排序的基本思想：
将待排序序列看成是n个长度为1的有序序列,将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序表再次归并，得到n/4个长度为4的有序序列；如此重复进行下去，最后得到一个长度为n的有序序列．时间复杂度O（nlog2n）．空间复杂度O（n）归并排序是稳定的
基数排序的基本思想：
是借助＂分配＂和＂收集＂两种操作对单逻辑关键字进行排序的一种内排序方法．时间复杂度o（d＊n）．空间复杂度O（n＋r）．基数排序是稳定的
标签:
