六、树
A.树的定义
1.树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中:(1)有且仅有一个特定的称为根(Root)的结点;(2)当n>1时,其余节点可分为m(m>0)个互不相交的有限集T1、T2……Tm,其中每一个集合本身又是一颗树,并且称为根的子树(SubTree)
2.强调:n>0时根结点是唯一的,不可能存在多个根结点;m>0时,子树的个数没有限制,但它们一定是互不相交的;
3.结点分类:结点拥有的子树数称为结点的度(Degree)。度为0的结点称为叶子节点(Leaf)或终端结点;度不为0的结点称为非终端结点或分支结点。除根结点外,分支结点也称为内部结点。树的度是树内部各结点的度的最大值
4.结点间关系:结点的子树的根称为该结点的孩子(Child),相应地,该结点称为孩子的双亲(Parent)。同一个双亲的孩子之间称为兄弟(Sibling)。结点的祖先是从根到该结点所经分支上的所有结点。以某结点为根的子树中的任一结点都称为该结点的子孙。
5.结点的层次(Level)从根开始定义,根为第一层,根的孩子为第二层。双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度(Depth)或高度
6.如果将树中结点的各子树从左至右是有次序的,不能互换的,则称该树为有序树,否则称为无序树
7.森林(Forest)是m(m>0)棵互不相交的树的集合
B.树的存储结构
1.双亲表示法
2.孩子表示法
3.孩子兄弟表示法:任意一颗树,它的结点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的。因此,我们设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟
C.二叉树
1.二叉树(Binary Tree) 是n(n>0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成
2.特点:
3.基本形态:空二叉树、只有一个根结点、根结点只有左子树、根结点只有右子树、根结点既有左子树也有右子树
4.特殊二叉树:
D.二叉树的的性质
1.在二叉树的第i层上至多有2i-1个结点(i>=1)
2.尝试为k的二叉树至多有2k-1个结点(k>=1)
3.对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1
4.具有n个结点的完全二叉树的深度为[log2n]+1([x]表示不大于x的最大整数)
5.如果对一棵有n个结点的完全二叉树(其深度为[log2n]+1)的结点按层序编号(从第1层到第[log2n]+1层,每层从左到右),对任一结点i(1<=i<=n)有:
E.二叉树的存储结构
1.顺序存储结构一般只用于完全二叉树
2.二叉树每个结点最多有两个孩子,所以为它设计一个数据域和两个指针域,这种链表称为二叉链表
F.二叉树的遍历
1.二叉树的遍历(traversing binary tree)是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点疲访问一次且仅被访问一次
2.遍历方法:
G.线索二叉树
1.我们把指向前驱和后继的指针称为线索,加上线索的二叉链表称为线索列表,相应的二叉树就称为线索二叉树(Threaded Binary Tree)
2.其实就是把一棵二叉树转成了一个双向链表,对二叉树以某种次序遍历使其变为线索二叉树的过程就称做是线索化。线索化的过程就是在遍历的过程中修改指针的过程。
3.如果使用的二叉树需要经常遍历或查找结点时需要某种遍历序列中的前驱和后继,那么采用线索二叉链表的存储结构就是非常不错的选择。时间复杂度为O(n)。
H.树、森林与二叉树的转换
1.树转换为二叉树:
2.森林转换为二叉树
3.二叉树转为树
4.二叉树转换为森林:判断根结点有没有右孩子
5.树的遍历
6.森林的遍历
I.赫夫曼树及其应用
1.从树中一个结点到另一个结点之间的分支构成两个结点之间的路径,路径上的分支数目称为路径长度。树的路径长度就是从树根到每一结点的路径长度之和。
2.赫夫曼算法描述
3.若要设计长短不等的编码,则必须是任一字符的编码都不是另一个字符编码的前缀,这种编码称为前缀编码。
4.赫夫曼编码:设需要编码的字符集为{d1,d2……dn},各个字符在电文中出现的次数或频率集合为{w1,w2……wn},以d1,d2……dn作为叶子节点,以w1,w2,……wn作为相应叶子结点的权值来构造一棵赫夫曼树。规定赫夫曼树的左分支代表0,右分支代表1,则从根结点到叶子节点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码,就是就赫夫曼编码
https://github.com/zhangyue0503/cproject/blob/master/shujujiegou/6.c
七、图
A.图的定义
1.图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。
2.注意:
3.各种图定义
4.图的顶点与边间关系
5.连通图相关术语
B.图的存储结构
1.邻接矩阵:图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
2.邻接表:将结点存入数组,并对结点的孩子进行存储,这种数组与链表相结合的存储方法称为邻接链表。
3.十字链表:将邻接表和逆邻接表结合在一起使用,在有向图的应用中,是非常好的数据结构模型
4.邻接多重表:与邻接表的差别,仅仅是在于同一条边在邻接表中用两个结点表示
5.边靠数组:由两个一维数组构成。一个是存储顶点的信息;另一个是存储边的信息,这个边数组每个数据元素由一条边的起点下标、终点下标和权组成
C.图的遍历
1.图的遍历和树的遍历类似,从图中某一顶点出发访遍图中其余观点,且使每一个顶点仅被访问一次,这一过程就叫做图的遍历(Traversing Graph)
2.尝试优先遍历(Depth_First_Search),也称为尝试优先搜索,简称GFS。
3.广度优先遍历(Breadth_First_Search):又称广度优先搜索,又称BFS。类似于树的层序遍历。
D.最小生成树
1.把构造连通网的最小代价生成树称为最小生成树(Minimum Cost Spanning Tree)
2.普里姆(Prim)算法
3.克鲁斯卡尔(Kruskal)算法
4.克鲁斯卡尔算法主要是针对边来展开,边数少时效率会非常高,所以对于稀疏图有很大的优势;而普里姆算法对于稠密图,即边数非常多的情况会更好一些
E.最短路径
1.对于网图来说,最短路径,是指两顶点之间经过的边上权值之和最少的路径,并且我们称路径上的第一个顶点是源点,最后一个顶点是终点
2.迪杰斯特拉(Dijkstra)算法
并不是一下就求出v1到vn的最短路径,而是一步步求出它们之间顶点的最短路径,过程中都是基于已经求出的最短路径的基础上,求得最远顶点的最短路径,最终得到结果
解决了从某个源点到其余各顶点的最短路径问题,时间复杂度为O(n^3)
3.费洛伊德(Floyd)算法
公式:D0[v][w]=min{D-1[v][w],D-1[v][0]+D-1[0][w]}
代码简洁,一个二重循环初始化加一个三重循环权值修正,时间复杂度也是O(n^3),如果面临需要求所有顶点至所有顶点的最短路径问题时,弗洛伊德(Floyd)算法应该是不错的选择
F.拓扑排序
1.在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称为AOC网(Activity On Vertex Network)
2.设G=(V,E)是一个具有n个顶点的有向图,V中的顶点序列v1……vn,满足若从顶点vi到vj有一条路径,则在顶点序列中顶点vi必在顶点vj之前。则我们称这样的顶点序列为一个拓扑序列
3.所谓拓扑排序,其实就是对一个有向图构造拓扑序列的过程
4.基本思路:从AOV网中选择一个入度为0的顶点输出,然后删去此顶点,并删除以此顶点为尾的弧,继续重复此步骤,走到输出全部顶点或者AOV网中不存在入度为0的顶点为止
5.整个算法的时间复杂度为O(n+e)
G.关键路径
1.在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,用边上的权值表示活动的持续时间,这种有向图的边表示活动的网,我们称之为AOE网(Activity On Edge Network)
2.路径上各个活动所持续的时间之和称为路径长度,从源点到汇点具有最大长度的路径叫关键路径,在关键路径上的活动叫关键活动
3.算法原理:只需要找到所有活动的最早开始时间和最晚开始时间,并且比较它们 ,如果相等就意味着此活动是关键活动,活动间的路径为关键路径,几个参数:
事件的最早发生时间etv(earliest time of vertex):即顶点vk的最早发生时间
事件的最晚发生暖意ltv(latest time of vertex):即顶点vk的最晚发生时间,也就是每个顶点对应的事件最晚需要开始的时间,超出此时间将会延误整个工期
活动的最早开工时间ete(earliest time of edge):即弧ak的最早发生时间
活动的最晚开工时间lte(latest time of edge):即弧ak的最晚发生时间,也就是不推迟工期的最晚开工时间
https://github.com/zhangyue0503/cproject/blob/master/shujujiegou/7.c
八、查找
A.查找概论
1.查找表(Search Table)是由同一类型的数据元素(或记录)构成的集合
2.关键字(Key)是数据元素中某个数据项的值,用它可以标识一个数据元素。也可以标识一个记录的某个数据项(字段),我们称为关键码。若此关键字可以唯一地标识一个记录,则称此关键字为为主关键字(Primary Key)。对于那些可以识别多个数据元素(或记录)的关键字,称为次关键字(Secondary Key)
3.查找(Searching)就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。
4.静态查找表(Static Search Table):只查找操作的查找表。操作有:
5.动态查找表(Dynamic Search Table):在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已经存在的某个数据元素。操作有:
B.顺序表查找
1.顺序查找(Sequential Search)又叫线性查找,是最基本的查找技术,它的查找过程是:从表中第一个(或最后一个)记录开始,逐个进行记录的关键字和给定值比较,若某个记录的关键字和给定值相等,则查找成功,找到所查的记录;如果直到最后一个(或第一个)记录,其关键字和给定值比较都不相等时,则表中没有所查的记录,查找不成功
2. 时间复杂度:O(n)
C.有序表查找
1.折半查找(Binary Search)技术,又称为二分查找。它的前提是线性表中的记录必须是关键码有序(通常从小到大有序),线性表必须采用顺序存储。折半查找的基本思想是:在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功;若给定值小于中间记录的关键字,则在中间记录的左半区继续查找;若给定值大于中间记录的关键字,则在中间记录的右半区继续查找。不断重复上述过程,直到查找成功,或所有查找区域无记录,查找失败为止。时间复杂度O(logn)
2.插值查找(Interpolation Search)是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法,其核心就在于插值的计算公式key-a[low]/a[high]-a[low]。
3.斐波那契查找:如果要查找的记录在左侧,则左侧的数据都不用再判断了,不断反复进行下去,对处于当中的大部分数据,其工作效率要高一些,折半查找是进行加法与除法运算,插值查找 进行按照那样的四则运算,而斐波那契查找只是最简单加减法运算。核心在于:
D.线性索引查找
1.索引就是把一个关键字与它对应的记录相关联的过程。所谓线性索引就是将索引项集合组织为线性结构,也称为索引表。
2.稠密索引:是指在线性索引中,将数据集中的每个记录对应一个索引项。对于稠密索引这个索引用来说,索引项一定是按照关键码有序的排列
3.分块索引:
4.倒排索引:
E.二叉排序树
1.二叉排序树(Binary Sort Tree),又称为二叉查找树。它或者是一棵空树,或者是具有下列性质的二叉树。
F.平衡二叉树(AVL树)
1.平衡二叉树(Self-Balancing Binary Search Tree或Height-Balanced Binary Search Tree),是一种二叉排序树,其中每一个节点的左子树和左子树的高度差至多等于1.
2.我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF(Balance Factor),平衡二叉树上所有结点的平衡因子只可能是-1,0和1.
3.距离插入结点最近的,且平衡因子的绝对值大于1的结点为根的子树,我们称为最小不平衡子树
4.实现原理:在构建二叉排序树的过程中,每当插入一个结点时,先检查是否因插入而破坏了树的平衡性,若是,则找出最小不平衡子树。在保持二叉排序树特性的前提下,调整最不不平衡子树中各结点之间的链接关系,进行相应的旋转,使之成为新的平衡子树。当最小不平衡子树根结点的平衡因子BF是大于1时,就右旋,小于-1时就左旋。插入结点后,最小不平衡子树的BF与它的子树的BF符号相反时,就需要对结点先进行一次旋转以使得符号相同后,再反向旋转一次才能够完成平衡操作。
G.多路查找树(B树)
1.多路查找 树(muitl-ray search tree),其每一个结点的孩子数可以多于两个,且每一个结点处可以存储多个元素
2.2-3树:其中的每一个结点都具有两个孩子(我们称它为2结点)或三个孩子(我们称它为3结点)
3.2-3-4树:其实就是2-3树的概念扩展,包括了4结点的使用。一个4结点包含小中磊三个元素和四个孩子(或没有孩子),一个4结点要么没孩子,要么有4个孩子
4.B树(B-tree):是一种平衡的多路查找树。2-3树和2-3-4树都是B树的特例。结点最大的孩子数目称为B树的阶(order)。一个m阶的B树具有如下属性:
5.B+树,在B树中,每一个元素在该树中只出现一次,有可能在叶子结点上,也有可能在分支结点上。而在B+树中,出现在分支结点中的元素会被当作它们在该分支结点位置的中序后继者(叶子结点)中再次列出。另外,每一个叶子结点都会保存一个指向后一路子结点的指针。一棵m阶的B+树和m阶的B树的差异在于:
H.散列表查找(哈希表)概述
1.散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f(key),f称为散列函数,又称为哈希(Hash)函数。采用散列技术将记录存储在一块连续的存储空间中,这块连续存储空间称为散列表或哈希表(Hash table)
2.散列技术既是一种存储方法,也是一种查找方法。最适合的求解问题是查找与给定值相等的记录。
3.散列技术不适合多同样关键字或范围查找
4.两个关键字key1!=key2,但是却有f(key1)==f(key2),这种现象称为冲突(collision),并把key1和key2称为这个散列函数的同义词(synonym)
I.散列函数的构造方法
1.好的散列函数:计算简单、散列地址分布均匀
2.直接定址法:f(key)=a*key+b(a,b为常数),适合查找表较小且连续的情况
3.数字分析法:制取使用关键字的一部分来计算散列存储位置的方法,适合处理关键字位数比较大的情况,且事先知道关键字的分布且关键字的若干位分布较均匀
4.平方取中法:适合不知道关键字的分布,而位数又不是很大的情况
5.折叠法:将关键字从左到右分割成位数相等的几部分(注意最后一部分位数不够时可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址。事先不需要知道关键字的分布,适合关键字位数较多的情况。
6.除留余数法:f(key) = key mod p(p<=m),最常用的,若散列表表长为m,通常p为小于或等于表长(最好接近m)的最小质数或不包含小于20质因子的合数
7.随机数法:f(key) = random(key)
J.处理散列冲突的方法
1.开放定址法:就是一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入。fi(key) = (f(key)+di) MOD m (di=1,2,3……,m-1)
2.再散列函数法:fi(key) = RHi(key) (I=1,2,……,k)
3.链地址法:将所有关键字为同义词的记录存储在一个单链表中,称这种表为同义词子表,在散列表中只存储所有同义词子表的头指针。
4.公共溢出区法:为所有冲突的关键字建立一个公共的溢出区来存放
K.散列表查找实现
1.散列查找的平均查找长度取决于:
https://github.com/zhangyue0503/cproject/blob/master/shujujiegou/8.c
九、排序
A.排序的基本概念与分类
1.假设含有n个记录的序列为{r1,r2……,rn},其相应的关键字分别为{k1,k2,……,kn},需确定1,2,……,n的一种排列p1,p2,……,pn,使其相应的关键字满足kp1<=kp2<=……<=kpn(非递减或非递增)关系,即使得序列成为一个按关键字有序的序列{rp1,rp2,……,rpn},这样的操作就称为排序
2.排序的稳定性:假设ki=kj(1<=i<=n,1<=j<=n,i!=j),且在排序前的序列中ri领先于rj(即i<j)。如果排序后ri仍依靠于rj,则称所用的排序方法是稳定的;反之,若可能使得排序后的序列中rj领先ri,则称所用的排序方法是不稳定的。
3.外排序:是由于排序的记录个数太多,不能同时放置在内存,整个排序过程需要在内外存之间多次交换数据才能进行。
4.内排序:是在排序整个过程中,待排序的所有记录全部被放置在内存中。
B.冒泡排序
1.冒泡排序(Bubble Sort)一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。
C.简单选择排序
1.简单选择排序法(Simple Selection Sort)就是通过n-i关键字间的比较,从n-i+1个记录中先出关键字最小的记录,并和第i(1<=i<=n)个记录交换之
D.直接插入排序算法
1.直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好的有序列表中,从而得到一个新的、记录数增1的有序表
E.希尔排序
1.将大量记录数的记录进行分组。分割成若干个子序列,在这些子序列内分别进行直接插入排序,当整个序列基本有序时,注意只是基本有序时,再对全体记录进行一次直接插入排序
2.所谓基本有序,就是小的关键字基本在前面,大的基本在后面,不大不小的基本在中间
3.跳跃分割:将相距某个“增量”的记录组成一个子序列,这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序
F.堆排序
1.堆是具有下列性质的完全二叉树:每个结点都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆
2.堆排序(Heap Sort)将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根结点。将它移走(其实就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素中的次小值。如此反复执行,便能得到一个有序序列。
G.归并排序
1.归并排序(Merging Sort)假设初始序列含有n个记录,则可以看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到[n/2]([x]表示不小于x的最小整数)个长度为2或1的有序子序列;两款两两归并,……,如此重复,直至得到一个长度为n的有序序列为止,这种排序方法称为2路归并排序
H.快速排序
1.快速排序(Quick Sort)的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的
https://github.com/zhangyue0503/cproject/blob/master/shujujiegou/9.c