数据结构

1,静态链表:用数组描述的链表,用cur维护数组中的位置信息,起到和指针相同的效果
2,循环链表和线性链表操作基本一致,区别在于一般算法中的循环条件不是p||p->next==NULL而是是否等于头指针
3,双向链表在插入和删除的时候要考虑前驱和后继两个指针
4,top()=0表示空栈,栈:链栈、顺序栈,应用:数制转换,括号匹配,迷宫,多项式求值
5,双端队列,限定插入和删除操作在表两端进行的线性表,是一种具有队列和栈的性质的数据结构.双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行
6,循环队列,用两个指针front和rear分别指向队头和队尾,插入新元素,尾指针加一,删除队头元素,头指针加1。约定以队头指针在队尾指针的下一位作为队列满的标志
7,串的堆分配存储就是用malloc和free来动态管理存储空间
8,串的块链存储中,存在节点大小的问题,即每个节点可以存放一个字符,也可以存储多个字符
9,KMP算法,串的模式匹配,在O(m+n)时间上,匹配过程中指针i不回溯http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
10,假若值相同的元素或者零元素在矩阵中的分布有一定规律,我们称此类矩阵为特殊矩阵,反之称为稀疏矩阵
11,一个三元组唯一确定了矩阵的一个非零元,由此,稀疏矩阵可有表示非零元的三元组及其行列数唯一确定。倘若以顺序存储结构来表示三元组表,则可得稀疏矩阵的一种压缩存储方式,即三元组顺序表
12,十字链表:除了非零元的三个维度外,再加一个right指向同一行中下一个非零元和一个down指向同一列中下一个非零元
13,广义表,线性表的推广,列表
14,森林是m棵互不相交的树的集合
15,波兰式,表达式的前缀表示
16,线索二叉树,若有左子树指向左孩子否则指示其前驱。若有右子树,指向右孩子,否则指向后继。至于前驱后继是啥看是什么遍历方法。一定要注意线索是在没有孩子节点的情况下才画的
17,树的存储结构:双亲表示法,孩子表示法,孩子兄弟表示法(链表中的节点的两个链域分别指向第一个孩子和下一个兄弟)
18,树,先根遍历和后根遍历。森林,先序遍历和中序遍历。
19,赫夫曼树,又称最优树,是一类带权路径长度最短的树。
20,前缀编码,若要设计长短不等的编码,则必须是任一个字符的编码都不是另一个字符的编码的前缀,这种编码叫做前缀码。利用赫夫曼树的叶节点可以实现前缀编码
21,赫夫曼树中没有度为1的节点,这类树又称为严格的或正则的二叉树
22,带权图通常称为网
23,序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路称为简单回路或简单环
24,无向图中如果对于图中任意两个顶点都是连通的,则称是连通图。连通分量指的是无向图中的极大联通子图。有向图中,所有点都有来回的路径,则称是强连通图,有向图中的极大强连通子图叫做有向图的强连通分量。
25,图的存储:邻接矩阵,邻接表,十字链表,邻接多重表
26,图存储的十字链表中,多两个链分别指向弧尾和弧头相同的点。邻接表和逆邻接表的结合
27,对于一个连通网(V,E),U是顶点集的一个真子集,如果有一条一个端点在U中一个端点在V中的边,最小生成树一定包含此边。
28,Prime算法和Kruskal算法构造最小生成树
29,最小生成树,即连通网的最小代价生成树
30,关节点,如果删去v和与v关联的边之后,将图的一个连通分量分割成两个/或两个以上。则称v为关节点。没有关节点的连通图,称为重连通图
31,DAG图,有向无环图
32,拓扑排序,由某个集合上的一个偏序得到该集合上的一个全序
33,AOV网,用顶点表示活动,用弧表示活动间的优先关系的有向图称为表示活动的网,即AOV网(有向)。AOE网,用边表示活动的网,AOE网是一个带权的有向无环图
34,关键路径,路径长度最长的路径叫做关键路径。最早开始时间,从v1到vi的最长路径的长度叫做最早开始时间。最迟开始时间,不推迟整个工程完成的前提下,活动最迟必须开始进行的时间。最早开始时间与最迟开始时间相等的点就是关键活动。
35,求最短路径,dijkstra(通过松弛更新数据,得到一个点到其他点的最短路径,N2)和floyd(核心判断e[i][j]>e[i][k]+e[k][j],N3)
36,查找表,由同一类型的数据元素构成的集合
37,平均查找长度,概率和比较个数的加权和
38,分块查找又叫索引顺序查找
39,二叉排序树,即二叉搜索树BST。或者是一棵空树,或者是1,如果左子树不空,则左子树上所有节点均小于它的根节点2,右边大于
40,平衡二叉树AVL,左右子树都是平衡二叉树,深度之差不超过1
41,B-树,是一种平衡的多路查找树,应用在数据库索引,所有叶子结点出现在同一层,不包含信息。B+树所有的叶子结点中包含所有关键字的信息
42,键树,度>=2,数字查找树
43,哈希表处理冲突,开放定址法,顺着向后找到第一个不冲突的地方。再哈希
44,胜者树和败者树:胜者树和败者树都是完全二叉树,是树形选择排序的一种变型。每个叶子结点相当于一个选手,每个中间结点相当于一场比赛,每一层相当于一轮比赛。不同的是,胜者树的中间结点记录的是胜者的标号;而败者树的中间结点记录的败者的标号。胜者树与败者树可以在log(n)的时间内找到最值。任何一个叶子结点的值改变后,利用中间结点的信息,还是能够快速地找到最值。在k路归并排序中经常用到。败者树的根结点记录的是败者,需要加一个结点来记录整个比赛的胜利者。采用败者树可以简化重构的过程。败者树的重构跟胜者树是不一样的,败者树的重构只需要与其父结点比较
45,顺串即归并段