数据结构个人复习
时隔好久，想复习一下整体的数据结构的知识，在此做一个记录
-
空间复杂度与时间复杂度：时间：程序运行的时间 空间：指令空间，数据空间还有环境栈空间，为分析程序性能的主要标准。
-
线性表（有序表，linearlist） 用i作为索引 ，这里明确一个概念：ADT（abstract data type）抽象数据类型，分为实例与操作。
操作有：empty();size();get(index);indexof(x);erase(index);insert(index,x);output()。
底层实现：可以是直接用数组描述或者用arraylist利用new实现，stl中的实现为vector（我在lc常用到的一种数据结构 doge）vector详细用法
一个数组表示的多重表还不是太懂，等以后用到再仔细看看 -
链表
由chainnode组成，链式描述的线性表在各方面的性能其实不是很好，只在知道前驱节点的情况下进行删除插入的时间复杂度为O1。循环链表：在firstnode前增加了一个头结点headnode使得尾结点指向headnode，利用headnode的好处是不需要再判断当前节点是否为NULL，例如indexof函数，只需将headnode的值赋值为所查值，最后检查满足条件的currentnode为其他节点还是headnode就可以轻松实现。
双向链表：每个chainnode里都有next指针与previous指针分别指向前后节点，有firstnode与lastnode
双向循环链表：上述的儿子。
-
栈stack LIFO（last in first out）
top为栈顶，bottom为栈底操作有：
empty() ; size() ; top() ; pop() ; push(x)。
用数组表示的栈：arraystack 利用stacktop作为索引值，并且栈为空时值设为-1。
用链表描述的栈：linkedstack -
队列 queue FIFO（first in first out）
队尾：back或rear（进行插入元素的那一端）
队首：front（进行删除元素的那一端）
操作有：
empty() ; size() ; front() ; back() ; pop() ; push(x) ;
数组描述的队列：两个公式两种描述，一种是让queuefront一直为0，而queueback在队列为空是为-1（这种在删除时要移动整个队列）；另一种是改变queuefront，但会浪费前面的空间，所以给他们弄成一个闭环，即采用取余%的方法，在这种表述里，queuefront改为指向首元素的下一个位置，即queue[0]，此时队列为空的情况下，queuefront等于queueback，但这种情况下允许的最大队列数为arraylength-1，因为不能使转一圈过后queuefront等于queueback。
链表描述的队列：采用从头至尾的连接方向（更适合删除操作），队列为空时，queuefront为NULL。 -
字典 dictionary （k,v）这种数对组成的集合，v是关键字k对应的值。
多重字典 dictionary with duplicate ，两个或以上的数对可以有共同的关键字。
操作： empty() ; size() ; find(k) ; insert(pair) ;erase(k)。 node->first 与 node->second -
跳表 skiplist （需要是有序的链表）
可以有好几级的链表，节点为skipnode 包含element域与skipnode**指针域，感觉就像二分查找那样的线性表一样，我可能还是更愿意选择线性表加上二分查找。 -
散列表（哈希表）散列：hashing
有些概念：桶（bucket），起始桶（home bucket），一般用的散列函数是除法散列函数，存在着冲突与溢出，还有均匀散列函数的概念，线性探察（linear probing）在用数组实现的哈希表中有用处，包括寻找下一个可用桶与在删除时对所有桶的检查，线性探察使得散列的平均性能要比线性表的平均性能优越很多。
链式散列：将每一个桶都弄成一个有序链表，性能比线性探查还好一些但散列的某些操作如找关键字最大最小的数对时花费时间比跳表的时间要长。
-
树 tree，非空的有限元素的集合，一个元素为根（root），其余的元素组成t的子树（subtree），树中没有孩子的元素称为叶子（leaf），级（level）：树根为1级，接下来递增；高度（height）与深度（depth）指的都是树中级的个数，一个元素的度（degree of an element）指的是其孩子的个数，一颗树的度指的是其元素的度的最大值。
-
二叉树（binary tree），可以为空，每个元素的子树都是有序的，有左子树和右子树之分，满二叉树（full binary tree）：高度为h的二叉树正好有2的h次方-1的元素； 完全二叉树（complete binary tree）：2i>n , 2i+1>n等描述了元素与左右孩子之间的关系；右斜二叉树（right-skewed binary tree）为除根节点外每个元素都为父节点的右孩子。
数组描述二叉树纯纯牛马，会补全编号，放到数组里，极其浪费空间。
链表描述：利用binarytreenode，其中包括一个element域及两个binarytreenode*指针分别指向左右孩子。
4种遍历（traversal）的方法，前序（prefix），中序（infix），后序（postfix），层次遍历，其中前三个用了递归而层次遍历用队列来实现。遍历图解
操作有：empty(); size(); preorder(visit); inorder(visit);postorder(visit);levelorder(visit);erase（）；其中visit是访问函数，具体实现可以分为对外接口和内部实现（当做方法用）。 -
优先级队列(priority queue) 可以按元素的优先权的值的顺序进行操作，优先级相同时，查找与删除可以按任意顺序处理。
操作：empty() ; size() ; pop() ; top() ; push(x)。大根树，小根树：每个节点的值都大于（小于）其子节点的值。
大根堆，小根堆：既是大根树，小根树，又是完全二叉树。maxheap用数组实现，根节点的索引为1，插入时是一个起泡过程，时间o（logn），删除时也是o（logn），而初始化大根堆要o（nlogn）。
外部节点（external node），代替了树中的空子树；其余节点叫做内部节点（internal node），增加了外部节点的二叉树被称为扩充二叉树（extended binary tree）
高度优先左高树（height-piased leftist tree, HBLT）:其任何一个内部节点的做孩子的s值都大于等于右孩子的s值，s为节点x到其子树的外部节点的所有路径的最短的一条。
若一颗左高树同时为大（小）根树，则为最大（小）HBLT（max HBLT）或min HBLT。
重量优先左高树（weight-piased leftist tree, WBLT）：w值，w为是以节点x为根的子树的内部节点的个数。 有max WBLT与min WBLT，HBLT与WBLT表示的两个优先级队列可在对数时间内合并成一个，用堆表示的优先级队列做不到这一点。
这两个数据结构的插入删除以及初始化操作与一项操作息息相关，即两个最大HBLT的合并，合并的时间复杂度为o（logn）,其中初始化操作通过创建一个队列，循环合并实现。合并：递归实现：通过改变此时子树根节点，调用递归函数，交换子树，更新s值实现。 -
竞赛树（tournament tree）：是完全二叉树，也称为选择树（selection tree）。分为赢者树（winner tree）与输者树（loser tree）。有最小赢者树和最大赢者树（min/max winner tree），分数相等时，左孩子胜。
操作：initialize（a）；winner（）；replay（i）。
能在o（logn）里更改最值。
输者树：当play[i]为当前赢者时replay的效率比赢者树高，不用再比较兄弟节点。 -
二叉搜索树（binary search tree）：便于找到最接近某关键字的元素。特点：为二叉树，可能为空，所有关键字都是唯一的，左子树中所有元素的关键字都小于其根节点的关键字，右子树中所有元素的关键字都大于其根节点的关键字。
操作：find（k）；insert（p）；erase（k）；ascend（）；前三个操作在随机插入时时间复杂度均为o（logn）。
关键字可以不唯一，条件为小于等于和大于等于，这样称为有重复值的二叉搜索树（binary search tree with duplicates）
索引二叉搜索树（indexed binary search tree）：每个节点中添加一个leftsize域，值为该节点左子树的元素个数，能找到关键字排名多少的元素。 -
平衡搜索树：按名次实施的查找删除操作或不按精确的关键字匹配的。是为了解决二叉搜索树可能出现的o（n）问题，有AVL搜索树，红黑树，分裂树，m叉搜索树，m阶B-树。
-
图：graph，图不能包含自连边，边可以有权，生成树，二分图，完全图，无向图的描述：邻接矩阵；邻接链表；邻接数组。加权图的描述：成本邻接矩阵；邻接链表。图的遍历：广度优先搜索（BFS）与深度优先搜索（DFS）
