2017-12-20
数据结构复习
第二章 线性表
每个元素都依赖表中相对位置而唯一确定，第一个元素只有后继，最后一个元素只有前驱，其余元素各有一个前驱和后继。
实现：
1.顺序表 （随机访问，O(1)时间内找到指定元素，动静态两种分配方式）
2.链式表示(头插法,尾插法建立链表,链表的元素删除,双链表的插入和删除(1234,4步),循环链表(为空=prior和next均等于L),静态链表-游标表示)
顺序表与链表对比:随机存取-表头取元素;逻辑物理地址相连;按值查找时间异同,按序查找差别很大,删除元素链表简单
3.栈 (LIFO所有插入删除均在表的栈顶,共享栈结构为[0栈底---------]0栈顶[1栈顶----------]1栈底,栈的链式存储)
4.队列(FIFO 先进的先出去,结构 front出队列[a1 a2 a3 a4 a5]进队列rear,循环队列(队满条件----(队尾+1)取模=队首),链队列,双端队列,能由XX表示但是不能由XXX表示的队列输出是__)
5.串与串的匹配
6.数组
7.广义表
第三章 广义表
二叉树
基础概念:有序树 无序树 儿子 兄弟 双亲(其实是一个) 度 根节点 叶子节点 高 森林
二叉树,满二叉树
完全二叉树:叶节点在倒数第一或者第二层;倒数第二层的叶子节点都在非终结节点的右边
二叉树的三种顺序:
(1)先跟顺序:根节点-左-右
(2)中跟顺序:左-根节点-右;类似投影
(3)后跟顺序:左-右-根节点
二叉树的性质:
第i层节点数:最多2^(i-1)
i层总数目:最多2^i-1
二叉树的左右链表示,游标表示,线索树(没儿子了就找祖宗麻烦(中跟前导/后继),另外最左最右两个叶节点的
左右分别指向根节点)
堆
最大堆,最小堆
堆的插入:插到最后面,然后不停与爹进行比较
堆的删除:删除根节点,最后一个换上来,不停与较大儿子节点(最大堆反之相反就是)比较
选择树:类似归并排序
树
先根(根T1T2T3......)中根(T1根T2T3......)后根(根T1T2T3......根)
数组表示| 第几个 0 1 2 3 4 5 6 7 8 9 10|
|他的爹是谁 0 1 1 2 2 5 5 5 3 3 |
邻接表表示
0
1----2----3
2----4----5
.......
左右链表示
森林与二叉树
森林转二叉树:每棵树的各个兄弟相连,每个结点只要最左的第一个儿子,去掉与其他儿子的连线,最后旋转45°
森林的遍历:先根--[1树根节点,遍历1树的全部子树,遍历其他的树]
后根--[后根遍历1树的全部子树,1树根节点,后根遍历其他子树]
判定树
哈夫曼树
对二叉树中的空子树添加上特殊的节点;
内节点一定2儿子,外节点没儿子,外路长=内路长+2n;
第四章 图
G=(V,E) V表示顶点集,E表示边集
入度,出度,路径,连通图,强连通图(X到Y,Y到X都有)
邻接矩阵表示图,邻接表表示图
游标表示:用一个一维数组,标号代表节点号,数值first-head代表其指向的节点的二维数组编号,由编号再寻址
可以遍历其指向的全部节点P128
图的深度优先搜索(沿着一条线走到黑再出来),广度优先搜索(一圈一圈辐射)
深度优先生成/广度优先生成树
连通而无环路的无向图=开放树
最小生成树:所有边长的和(价)最小
1.prim算法
从一个节点开始,搜寻与之连接的权最小的边,将节点加入,再搜寻与这两个连的边中权最小的,
以此类推知道遍历所有节点,O(n^2)
2.Krusal算法
一直寻找最短的路径,并连接,但如果找到的路径会使两个树相连,那么丢弃,
直至所有节点通过了之前画的边
关节点:若拆除关节点,会把一个连通分量,拆成多个连通分量
双连通:没有关节点的无向图
双连通分量:三角定律
拓扑排序:先修课程,AOV;方法:拆除入度为0的节点以及经过拆除后暴露出来的节点,
直至所有的都拆完形成一个序列
关键路径:起始点-终点具有最大长度的路径;
最早开始时间从V点开始的距离最短的路径所需时间
最迟开始时间:不是整个工程完成拖延的最晚时间,从后往前减
单源最短路径:Dijkstra算法:输出其他顶点到该顶点的最短路径,层层扩大,步步比较三角与直连O(n^3)
每一对的最短路径:Floyd算法,Warshall算法