常见数据结构与算法整理总结（上） 常见数据结构与算法整理总结（下） Java - 集合框架完全解析 关于Java集合的小抄 Java - 虚拟机学习笔记1 自动内存管理机制 Java - 虚拟机学习笔记2 类加载机制 Java - 网络编程完全总结 Java - 数据库学习笔记 Java - 设计模式学习总结 Java - 并发编程必知必会 如何理解面向对象思想 NIO 入门 Java动态性之:反射机制(Reflection) Java动态性之:动态编译(DynamicCompile) Java动态性之:脚本引擎执行javascript代码 JVM核心机制 JVM的栈上分配与逃逸分析 深入 JVM 内核—原理、诊断与优化之: GC 算法与种类 Hadoop框架基础（一） Hadoop框架基础（二） 关于数据科学的笔试和面试(BAT) hive优化总结 hadoop面试45题 java面试基础 多线程面试 红黑树 Hadoop深入面试问答题 hadoop面试原理性问题 Java内存模型深入讲解 《深入理解Java虚拟机》学习笔记（九）（Java内存模型与线程） 十种排序算法及其比较（java实现） Java内存模型与volatile关键字解析 Storm 性能优化 15道使用频率极高的基础算法题 二叉树相关算法题 链表相关算法题 经典算法题每日演练——第四题 最长公共子序列 经典算法专题 Java性能优化指南1.8版，及唯品会的实战 优秀博客 花钱的年华 骊骅 为梦码一生
数据结构与算法之: 查找 第二部分 (十)
多路查找树(multi-way search tree) 多路查找树的特点是其每一个节点的孩子数可以多余两个,且每一个节点处可以存储多个元素 所有元素之间存在某种特定的排序关系 存储 当在磁盘的很多文件中查找一个文件时,会把磁盘中的内容加载到内存中,加载几千次和几次的差别是非常大的,多路查找树在减少磁盘io操作能起到很好的作用 2-3树 一个节点拥有两个孩子和一个元素我们称之为2节点,它跟二叉排序树类似,左子树包含的元素小于节点的元素,右子树包含的元素大于节点的元素.不过与二叉排序树不同的是,这个2节点要么没有孩子,要么就应该有两个孩子,不能只有一个孩子 3节点拥有2个数据元素和3个指针 2-3-4树 与2-3树类似 B树 B树(B-tree)是一种平衡的多路查找树,2-3树和2-3-4树都是B树的特例 我们把节点最大的孩子树目称为B树的阶(order),因此2-3树是3阶B树,2-3-4树是4阶B树 一个m阶的B树具有如下属性: 如果根结点不是叶结点,则其至少有两颗子树 每一个非根的分支结点都有k-1个元素(关键字)和k个孩子,其中k满足ceil(m/2)<=k<=m 所有叶子结点都位于同一层次 每一个分支结点包含下列信息数据:n,A0,K1,K2,A2,K3,A3...... 其中K为关键字,且Ki<Ki+1 Ai为指向子树根节点的指针 散列表(哈希表)查找 介绍 我们要在a[]中查找key关键字的记录 书序查找:挨个比较 有序表查找:二分查找 散列表查找:记录的存储位置=f(关键字) 散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f(key) 在这里我们把这种对应关系f称为散列函数,又称为哈希(Hash)函数.采用散列技术将记录存储在一块连续的存储空间中,这块连续存储空间称为散列表或哈希表(Hash table) 散列表的查找步骤 当存储记录时,通过散列函数计算出记录的散列地址 当查找记录时,我们通过同样的散列函数计算记录的散列地址,并按此散列地址访问该记录 构造散列函数的两个基本原则 计算简单 分布均匀 直接定址法 例一:有一个从1到100岁的人口统计表,其中年龄作为关键字,哈希函数取关键字自身 即f(key)=key 例二:如果现在要统计的是1980年以后出生的人口数,那么我们对出生年份这个关键字可以变换为:用年份减去1980的值作为地址 即:f(key) = key - 1980 我们可以取关键字的某个线性函数值为散列地址,即:f(key)=a*key+b 适合查找表比较小,并且连续的情况 数字分析法 数字分析法通常适合处理关键字位数比较大的情况,例如我们现在要存储某家公司员工登记表,如果用手机号作为关键字,那么我们发现抽取后面四位数字作为散列地址是不错的选择 平方取中法 平方取中法是将关键字平方之后取中间若干位数字作为散列地址 适合数字较小的情况 折叠法 折叠法是将关键字从左到右分割成位数相等的几部分,然后将这几部分叠加求和,并按散列表表长取后几位作为散列地址 比如表长为3,关键字为9876543210,分割补齐:987|654|321|000,相加取后3位,得962 除留余数法 此方法为最常用的构造散列函数方法,对于散列表长度为m的散列函数计算公式为:f(key) = ley mod p(p<=m) 事实上,这个方法不仅可以对关键字直接取模,也可以通过折叠,平方取中后再取模 例如下表,我们对有12个记录的关键字构造散列表时,就可以用f(key) = key mod 12的方法 p的选择是关键,如果对于这个表格的关键字,p还选12的话,那么的到的情况未免也太糟糕了 p的选择很重要,如果我们把p改为11,那结果就另当别论了 随机数法 选择一个随机数,取关键字的随机函数值为它的散列地址 即:f(key) = random(key) 这里的random是随机函数,当关键字的长度不等时,采用这个方法构造散列函数是比较合适的 视不同的情况采用不同的散列函数 计算散列地址所需的时间 关键字的长度 散列表的大小 关键字的分布情况 记录查找的频率 处理散列冲突的方法 开放地址法 所谓开放地址法就是一旦发生了冲突,就寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入 公式 fi(key) = (f(key)+di) MOD m (di=1,2,...,m-1) 例:假设关键字集合为{12,67,56,16,25,37,22,29,15,47,48,34},使用除留余数打法(m=12)求散列表 可以修改di的取值方式,例如使用平方运算来尽量解决堆积问题: fi(key) = (f(key)+di) MOD m (di=1^2,-1^2,2^2,-2^2,...,q^2,-q^2,q<=M/1) 还有一种方法是,在冲突时,对于位移量di,采用随机函数计算得到,我们称之为随机探测法: fi(key) = (f(key)+di) MOD m (di是由一个随机函数获得的数列) 再散列函数法 fi(key) = RHi(key) (i=1,2,3,...,k) 每个i对应一个散列函数,如果使用当前散列函数发生冲突则使用下一个散列函数 链地址法 假设关键字集合为{12,67,56,16,25,37,22,29,15,47,48,34},同样使用除留余数发求散列表 有同样hash值得元素放在同一个地方的链表里 公共溢出区法 假设关键字集合为{12,67,56,16,25,37,22,29,15,47,48,34},同样使用除留余数发求散列表 散列表查找的代码实现 #define HASHSIZE 12 #define NULLKEY -32768 typedef struct { int *elem; //数据元素的基址,动态分配数组 int count; //当前数据元素的个数 }HashTable; void InitHashTable(HashTable *H) { int i; H->count = HASHSIZE; H->elem = (int *)malloc(HASHSIZE * sizeof(int)); if(!H->elem) { return -1; } for(i=0;i<HASHSIZE;i++) { H->elem[i] = NULLKEY; } return 0; } //使用除留余数发 int Hash(int key) { return key % HASHSIZE; } //插入关键字到散列表 void InsertHash(HashTable *H,int key) { int addr; addr = Hash(key); while(H->elem[addr]!=NULLKEY)//如果冲突 { addr = (addr + 1) % HASHSIZE; //开发定址法的线性探测 } H->elem[addr] = key; } int SearchHash(HashTable H,int key,int *addr) { *addr = Hash(key); while(H.elem[*addr] != key) { *addr = (*addr + 1) % HASHSIZE; if(H.elem[*addr] == NULLKEY || *addr == Hash(key)) { return -1; } } return 0; }
平衡二叉树的实现代码如下 #include <stdio.h> #include <stdlib.h> #define TRUE 1 #define FALSE 0 // 定义平衡二叉树的结点结构 typedef struct BiTNode { int data; int bf; // 平衡因子 BiTNode *lchild, *rchild; }BiTNode, *BiTree; typedef int Status; // 右旋处理，即LL调整 void R_Rotate( BiTree *p ) { BiTree L; L = (*p)->lchild; (*p)->lchild = L->rchild; L->rchild = *p; *p = L; } // 左旋处理，即RR调整 void L_Rotate( BiTree *p ) { BiTree R; R = (*p)->rchild; (*p)->rchild = R->lchild; R->lchild = *p; *p = R; } // 左平衡旋转处理，包括 LL 和 LR 调整 void LeftBalance( BiTree *T ) { BiTree L, Lr; L = (*T)->lchild; switch( L->bf ) { case 1: // 新结点插入在T的左孩子的左子树上，为LL型，作右旋处理即LL调整 (*T)->bf = L->bf = 0; R_Rotate( T ); break; case -1: // 新结点插入在T的左孩子的右子树上，为LR型，作双旋处理 Lr = L->rchild; switch( Lr->bf ) { case 1: (*T)->bf = -1; L->bf = 0; break; case 0: (*T)->bf = L->bf = 0; break; case -1: (*T)->bf = 0; L->bf = 1; break; } Lr->bf = 0; L_Rotate( &(*T)->lchild ); // 先对T的左子树进行左旋处理即RR调整 R_Rotate( T ); // 再对T进行右旋处理即LL调整 } } // 右平衡旋转处理，包括 RR 和 RL 调整 void RightBalance( BiTree *T ) { BiTree R, Rl; R = (*T)->rchild; switch( R->bf ) { case -1: // 新结点插入在T的右孩子的右子树上，为RR型，作左旋处理即RR调整 (*T)->bf = R->bf = 0; L_Rotate( T ); break; case 1: // 新结点插入在T的右孩子的左子树上，为RL型，作双旋处理 Rl = R->lchild; switch( Rl->bf ) { case 1: (*T)->bf = 0; R->bf = -1; break; case 0: (*T)->bf = R->bf = 0; break; case -1: (*T)->bf = 1; R->bf = 0; break; } Rl->bf = 0; R_Rotate( &(*T)->rchild ); // 先对T的左子树进行左旋即RR调整 L_Rotate( T ); // 再对T进行右旋即LL调整 } } // 若在平衡二叉树T中不存在和 e 具有相同数据的结点，则插入数据元素为 e 的新结点， // 若因插入使二叉排序树失去平衡，则要作平衡调整， // 布尔变量taller表示 T 的深度是否增加，TRUE表示增加，FALSE表示没有增加 Status InsertAVL( BiTree *T, int e, Status *taller ) { if( !*T ) { *T = (BiTree)malloc(sizeof(BiTNode)); (*T)->data = e; (*T)->lchild = (*T)->rchild = NULL; (*T)->bf = 0; *taller = TRUE; } else { // 树中已有和e具有相同数据的结点，则不再插入 if( e == (*T)->data ) { *taller = FALSE; return FALSE; } if( e < (*T)->data ) // 继续在T的左子树进行搜索 { if( !InsertAVL( &(*T)->lchild, e, taller ) ) // InsertAVL( &(*T)->lchild, e, taller )得到的是T的左孩子结点(*T)->lchild的 data,bf 等相关信息 { return FALSE; } // 如果e已插入到T的左子树中，且左子树深度增加 if( *taller ) { switch( (*T)->bf ) // 检查T的平衡因子 { case 1: // 原本左子树比右子树高，再加上此结点，导致不平衡，需要作LL或LR调整 LeftBalance( T ); *taller = FALSE; break; case 0: // 原本左右子树等高，再加上此结点，左子树增高 (*T)->bf = 1; *taller = TRUE; break; case -1: // 原本右子树比左子树高，再加上此结点，左右子树变为等高 (*T)->bf = 0; *taller = FALSE; break; } } } else // 在T的右子树进行搜索 { if( !InsertAVL( &(*T)->rchlid, e, taller ) ) { return FALSE; } if( *taller ) { switch( (*T)->bf ) { case 1: // 原先左子树比右子树高，现在左右子树等高 (*T)->bf = 0; *taller = FALSE; break; case 0: // 原先左右子树等高，现在右子树增高 (*T)->bf = -1; *taller = TRUE; break; case -1: // 原先右子树比左子树高，现在再加上此结点，导致不平衡，需要作 RR 或 RL 调整 RightBalance( T ); *taller = FALSE; break; } } } } return TRUE; } // 对于实例，我们可以这样创建平衡二叉树 void CreateAVL() { int i; int a[10] = {2,1,0,3,4,5,6,9,8,7}; BiTree T = NULL; Status taller; for( i=0; i<10; i++ ) { InsertAVL( &T, a[i], &taller ); } } 转自 吴小宝的博客
选取一组数据分别为2，1，0，3，4，5，6，9，8，7的10个结点来构造平衡二叉树。 (1)首先数据为2的结点作为根结点插入，接着插入1，仍是平衡的，再插入0是，2的平衡因子变为2，此时出现了不平衡，因此需要进行调整，最低不平衡结点为2，属于LL型，根据上述网址的内容，则调整过程如图1所示。 图 1 (2)接着插入3，是平衡的，再插入4，此时出现了不平衡，结点 1 和 2 的平衡因子都为 -2，结点2为最低不平衡结点，属于RR型，调整过程如图2所示。 图 2 (3)接着插入5，此时结点 1 的平衡因子为 -2，导致不平衡，结点1为最低不平衡结点，属于RR型，调整如图3所示。 图 3 (4)接着插入6，此时结点4的平衡因子为 -2，导致不平衡，结点4为最低不平衡结点，属于RR型，调整如图4所示。 图 4 (5)接着插入9，是平衡的，再插入8，此时结点 3、5、6 的平衡因子都为 -2，导致不平衡，结点6为最低不平衡结点，属于RL型，调整如图5所示。 图 5 (6)插入7，此时结点3、5的平衡因子为 -2，导致不平衡，最低不平衡结点为5，属于RL型，调整如图6所示。 转自 吴小宝的博客 图 6
概念 平衡二叉树建立在二叉排序树的基础上，目的是使二叉排序树的平均查找长度更小，即让各结点的深度尽可能小，因此，树中每个结点的两棵子树的深度不要偏差太大。 平衡二叉树的递归定义：平衡二叉树是一棵二叉树，其可以为空，或满足如下2个性质：①左右子树深度之差的绝对值不大于1。②左右子树都是平衡二叉树。 平衡因子的概念：结点的平衡因子 = 结点的左子树深度 — 结点的右子树深度。 最低不平衡结点的概念：用A表示最低不平衡结点，则A的祖先结点可能有不平衡的，但其所有后代结点都是平衡的。 平衡化的实现 整个实现过程是通过在一棵平衡二叉树中依次插入元素(按照二叉排序树的方式)，若出现不平衡，则要根据新插入的结点与最低不平衡结点的位置关系进行相应的调整。分为LL型、RR型、LR型和RL型4种类型，各调整方法如下(下面用A表示最低不平衡结点)： LL型调整 由于在A的左孩子(L)的左子树(L)上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由1增至2。下面图1是LL型的最简单形式。显然，按照大小关系，结点B应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡，A结点就好像是绕结点B顺时针旋转一样。 图1 最简单的LL型调整 LL型调整的一般形式如下图2所示，表示在A的左孩子B的左子树BL(不一定为空)中插入结点(图中阴影部分所示)而导致不平衡( h 表示子树的深度)。这种情况调整如下：①将A的左孩子B提升为新的根结点；②将原来的根结点A降为B的右孩子；③各子树按大小关系连接(BL和AR不变，BR调整为A的左子树)。 图2 一般形式的LL型调整 RR型调整 由于在A的右孩子(R)的右子树(R)上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由-1变为-2。图3是RR型的最简单形式。显然，按照大小关系，结点B应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡，A结点就好像是绕结点B逆时针旋转一样。 图3 最简单的RR型调整 RR型调整的一般形式如下图4所示，表示在A的右孩子B的右子树BR(不一定为空)中插入结点(图中阴影部分所示)而导致不平衡( h 表示子树的深度)。这种情况调整如下：①将A的右孩子B提升为新的根结点；②将原来的根结点A降为B的左孩子；③各子树按大小关系连接(AL和BR不变，BL调整为A的右子树)。 图4 一般形式的RR型调整 LR型调整 由于在A的左孩子(L)的右子树(R)上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由1变为2。图5是LR型的最简单形式。显然，按照大小关系，结点C应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡。 图5 最简单的LR型调整 LR型调整的一般形式如下图6所示，表示在A的左孩子B的右子树(根结点为C，不一定为空)中插入结点(图中两个阴影部分之一)而导致不平衡( h 表示子树的深度)。这种情况调整如下：①将C的右孩子B提升为新的根结点；②将原来的根结点A降为C的右孩子；③各子树按大小关系连接(BL和AR不变，CL和CR分别调整为B的右子树和A的左子树)。 图6 一般形式的LR型调整 RL型调整 由于在A的右孩子(R)的左子树(L)上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由-1变为-2。图7是RL型的最简单形式。显然，按照大小关系，结点C应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡。 图7 最简单的RL型调整 RL型调整的一般形式如下图8所示，表示在A的右孩子B的左子树(根结点为C，不一定为空)中插入结点(图中两个阴影部分之一)而导致不平衡( h 表示子树的深度)。这种情况调整如下：①将C的右孩子B提升为新的根结点；②将原来的根结点A降为C的左孩子；③各子树按大小关系连接(AL和BR不变，CL和CR分别调整为A的右子树和B的左子树)。 图8 一般形式的RL型调整 平衡二叉树的深度接近log2n的数量级，从而保证在二叉排序树上插入、删除和查找等操作的平均时间复杂度为O(log2n)。 平衡二叉树的实现原理.docx 转自 吴小宝的博客
数据结构与算法之: 查找 第一部分 (九)
静态查找和动态查找 静态查找:数据集合稳定,不需要添加,删除元素的查找操作 动态查找:数据集合在查找的过程中需要同时添加或删除元素的查找操作 对于静态查找来说,我们不妨可以用线性表结构组织数据,这样可以使用顺序查找算法,如果我们再对关键字进行排序,则可以使用折半查找算法或斐波那契查找算法等来提高查找的效率 对于动态查找来说,我们则可以考虑使用二叉排序树的查找技术,另外我们还可以使用散列表结构来解决一些查找问题 顺序查找 顺序查找又叫做线性查找,是最基本的查找技术,它的查找过程是:从第一个(或最后一个)记录开始,逐个进行记录的关键字和给定值进行比较,若某个记录的关键字和给定值相等,则查找成功.如果查找了所有记录仍然找不到与给定值相对的关键字,则查找不成功 折半查找 如果待查找的记录是有序的,可以用折半查找 折半查找的基本思想:减小查找序列的长度,分而治之的进行关键字的查找 折半查找的实现过程:先确定待查找记录的所在范围,然后逐渐缩小这个范围,查找到该记录或查找失败为止 Code int bin_search(int str[],int n,int key) { int low,high,mid; low = 0; high = n - 1; while(low <= high) { mid = (low + high)/2; if(str[mid] == key) { return mid; } if(str[mid]<key) { low = mid + 1; } if(str[mid] > key) { high = mid - 1; } } return -1; } 复杂度O(log2n) 插值查找(按比例查找) 插值查找就像在查字典的时候,如果单词以a开头,一定会去前面找 如果数据变化的比较均匀,差值查找的效率比折半查找的效率高很多,如果不均匀可能会比折半查找慢很多 Code Code int bin_search(int str[],int n,int key) { int low,high,mid; low = 0; high = n - 1; while(low <= high) { mid = low + (key-a[low]/(a[high]-a[low])*(high-low)); if(str[mid] == key) { return mid; } if(str[mid]<key) { low = mid + 1; } if(str[mid] > key) { high = mid - 1; } } return -1; } 斐波那契查找(黄金分割查找) 黄金比例 0.618:1 斐波那契数列(F[k]):1 1 2 3 5 8 13 21 34 55 89 ...... 比例越来越接近0.612 Code #include <stdio.h> #include <stdlib.h> #define MAXN 20 /* *产生斐波那契数列 * */ void Fibonacci(int *f) { int i; f[0] = 1; f[1] = 1; for (i = 2; i < MAXN; ++i) f[i] = f[i - 2] + f[i - 1]; } /* * 查找 * */ int Fibonacci_Search(int *a, int key, int n) { int i, low = 0, high = n - 1; int mid = 0; int k = 0; int F[MAXN]; Fibonacci(F); while (n > F[k] - 1) //计算出n在斐波那契中的数列 ++k; for (i = n; i < F[k] - 1; ++i) //把数组补全 a[i] = a[high]; while (low <= high) { mid = low + F[k - 1] - 1; //根据斐波那契数列进行黄金分割 if (a[mid] > key) { high = mid - 1; k = k - 1; } else if (a[mid] < key) { low = mid + 1; k = k - 2; } else { if (mid <= high) //如果为真则找到相应的位置 return mid; else return -1; } } return 0; } int main() { int a[MAXN] = { 5, 15, 19, 20, 25, 31, 38, 41, 45, 49, 52, 55, 57 }; int k, res = 0; printf("请输入要查找的数字:\n"); scanf("%d", &k); res = Fibonacci_Search(a, k, 13); if (res != -1) printf("在数组的第%d个位置找到元素:%d\n", res + 1, k); else printf("未在数组中找到元素:%d\n", k); return 0; } 线性索引查找 稠密索引 建立和\相同大小的索引表 应用于数据量比较小的,如果数据量比较大就必须放在硬盘上,增加了io 分块索引 块内无序,块间有序 倒排索引 二叉排序树 无序的顺序表在删除表中的元素的时候可以把后面的元素覆盖待删除的元素,这样效率较高 构建二叉排序树:小于根节点的放在左面,大于根节点的放在右边 二叉排序树(Binary Sort Tree)又称为二叉查找树,它或者是一颗空树,或者是具有下列性质死亡二叉树: 若它的左子树不为空,则左子树上所有结点的值均小于它的根结点的值 若它的右子树不为空,则右子树上所有结点的值均大于它的根结点的值 它的左,右子树也分别为二叉排序树(递归) Code //二叉树的二叉链表结点结构定义 typedef struct BiTNode { int data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //递归查找二叉排序树 T 中是否存在 key //指针f指向T的双亲,其初始值调用值为NULL //若查找成功,则指针p指向该数据元素结点,并返回TRUE //否则指针p指向查找路径上访问的最后一个结点,并返回FALSE Status SearchBST(BiTree T,int key,BiTree f,BiTree *p) { if(!T)//查找不成功 { *p = f; return FALSE; } else if(key == T->data)//查找成功 { *p = T; return TRUE; } else if(key < T->data) { return SearchBST(T->lchild,key,T,p); //在左子树继续查找 } else { return SearchBST(T->rchild,key,T,p); //在右子树继续查找 } } //当二叉排序树T中不存在关键字等于key的数据元素时 //插入key并返回TRUE,否则返回FALSE Status InsertBST(BiTree *T,int key) { BiTree p,s; if(!SearchBST(*T,key,NULL,&p)) { s = (BiTree)malloc(sizeof(BiTNode)); s->data = key; s->lchild = s->rchild = NULL; if(!p) //查找不到key { *T = s; //插入s为新的根节点 } else if(key < p->data) { p->lchild = s; //插入s为左孩子 } else { p->rchild =s; //插入s为右孩子 } } else { return FALSE; //树中有关键字相同的结点,不再插入 //如果想要保存多份相同的可以做个标记 } } Status DeleteBST(BiTree *T,int key) { if(!*T) { return FALSE; } else { if(key == (*T)->data) { return Delete(T); } else if(key < (*T)->data) { return DeleteBST(&(*T)->lchild,key); } else { return DeleteBST(&(*T)->rchild,key); } } } Status Delete(BiTree *p) { BiTree q,s; if((*p)->rchild == NULL) { q = *p; *p = (*p)->lchild; free(q); } else if((*p)->lchild == NULL) { q = *p; *p = (*p)->rchild; free(q); } else { q = *p; s = (*P)->lchild; while(s->rchild) { q = s; s = s->rchild; } (*p)->data = s->data; if(q!=*p) { q->rchild = s ->lchild; } else { q->lchild = s->lchild; } free(s); } return TRUE; } 平衡二叉排序树 如果元素有序,就会生成一个斜二叉树,查找的时间会变长 平衡二叉树:要么它是一颗空树,要么它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1 平衡因子:左右子树深度差的绝对值 Code //左子树高 #define LH 1 //左右子树等高 #define EH 0 //右子树高 #define RH -1 typedef struct BiTNode { int data; int bf;//平衡因子 struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; void R_Roate(BiTree *p) { BiTree L; L = (*P)->lchild; (*P)->lchild = L->rchild; L->child = (*p); *p = L; } void LefBalance(BiTree *T) { BiTree L,Lr; L = (*T)->lchild; switch(L->bf) { case LH: (*T)->bf = L->bf = EH; R_Rotate(T); break; case RH: Lr = L->rchild; switch(Lr->bf) { case LH: (*T)->bf = RH; L->bf = RH; break; case EH: (*T)->bf = L->bf = EH; break; case RH: (*T)->bf = EH; L->bf = LH; break; } Lr->bf = EH; L_Roate((*T)->lchild); R_Roate(T); } } void RightBalance(BiTree *T) { } //taller表示释放长高了 int InsertAVL(BiTree *T,int e,int *taller) { if(!*T) { *T = (BiTree)malloc(sizeof(BiTNode)); (*T)->data = e; (*T)->lchild = (*T)->rchild = NULL; (*T)->bf = EH; *taller = TRUE; } else { if(e == (*T)->data) { *taller = FALSE; return FALSE; } if(e<(*T)->data) { if(!InsertAVL(&(*T)->lchild,e,taller)) { return FALSE; } if(*taller) { switch((*T)->bf) { case LH: LefBalance(T); *taller = FALSE; break; case EH: (*T)->bf = LH; break; case RH: (*T)->bf = EH; *taller = FALSE; break; } } } else { if(!InsertAVL(&(*T)->rchild,e,taller)) { return FALSE; } if(*taller) { switch((*T)->bf) { case LH: (*T)->bf = EH; *taller = FALSE; break; case EH: (*T)->bf = RH; *taller = TRUE; break; case RH: RightBalance(T); *taller = FALSE; break; } } } } } 静态查找和动态查找 静态查找:数据集合稳定,不需要添加,删除元素的查找操作 动态查找:数据集合在查找的过程中需要同时添加或删除元素的查找操作 对于静态查找来说,我们不妨可以用线性表结构组织数据,这样可以使用顺序查找算法,如果我们再对关键字进行排序,则可以使用折半查找算法或斐波那契查找算法等来提高查找的效率 对于动态查找来说,我们则可以考虑使用二叉排序树的查找技术,另外我们还可以使用散列表结构来解决一些查找问题 顺序查找 顺序查找又叫做线性查找,是最基本的查找技术,它的查找过程是:从第一个(或最后一个)记录开始,逐个进行记录的关键字和给定值进行比较,若某个记录的关键字和给定值相等,则查找成功.如果查找了所有记录仍然找不到与给定值相对的关键字,则查找不成功 折半查找 如果待查找的记录是有序的,可以用折半查找 折半查找的基本思想:减小查找序列的长度,分而治之的进行关键字的查找 折半查找的实现过程:先确定待查找记录的所在范围,然后逐渐缩小这个范围,查找到该记录或查找失败为止 Code int bin_search(int str[],int n,int key) { int low,high,mid; low = 0; high = n - 1; while(low <= high) { mid = (low + high)/2; if(str[mid] == key) { return mid; } if(str[mid]<key) { low = mid + 1; } if(str[mid] > key) { high = mid - 1; } } return -1; } 复杂度O(log2n) 插值查找(按比例查找) 插值查找就像在查字典的时候,如果单词以a开头,一定会去前面找 如果数据变化的比较均匀,差值查找的效率比折半查找的效率高很多,如果不均匀可能会比折半查找慢很多 Code Code int bin_search(int str[],int n,int key) { int low,high,mid; low = 0; high = n - 1; while(low <= high) { mid = low + (key-a[low]/(a[high]-a[low])*(high-low)); if(str[mid] == key) { return mid; } if(str[mid]<key) { low = mid + 1; } if(str[mid] > key) { high = mid - 1; } } return -1; } 斐波那契查找(黄金分割查找) 黄金比例 0.618:1 斐波那契数列(F[k]):1 1 2 3 5 8 13 21 34 55 89 ...... 比例越来越接近0.612 Code #include <stdio.h> #include <stdlib.h> #define MAXN 20 /* *产生斐波那契数列 * */ void Fibonacci(int *f) { int i; f[0] = 1; f[1] = 1; for (i = 2; i < MAXN; ++i) f[i] = f[i - 2] + f[i - 1]; } /* * 查找 * */ int Fibonacci_Search(int *a, int key, int n) { int i, low = 0, high = n - 1; int mid = 0; int k = 0; int F[MAXN]; Fibonacci(F); while (n > F[k] - 1) //计算出n在斐波那契中的数列 ++k; for (i = n; i < F[k] - 1; ++i) //把数组补全 a[i] = a[high]; while (low <= high) { mid = low + F[k - 1] - 1; //根据斐波那契数列进行黄金分割 if (a[mid] > key) { high = mid - 1; k = k - 1; } else if (a[mid] < key) { low = mid + 1; k = k - 2; } else { if (mid <= high) //如果为真则找到相应的位置 return mid; else return -1; } } return 0; } int main() { int a[MAXN] = { 5, 15, 19, 20, 25, 31, 38, 41, 45, 49, 52, 55, 57 }; int k, res = 0; printf("请输入要查找的数字:\n"); scanf("%d", &k); res = Fibonacci_Search(a, k, 13); if (res != -1) printf("在数组的第%d个位置找到元素:%d\n", res + 1, k); else printf("未在数组中找到元素:%d\n", k); return 0; } 线性索引查找 稠密索引 建立和\相同大小的索引表 应用于数据量比较小的,如果数据量比较大就必须放在硬盘上,增加了io 分块索引 块内无序,块间有序 倒排索引 二叉排序树 无序的顺序表在删除表中的元素的时候可以把后面的元素覆盖待删除的元素,这样效率较高 构建二叉排序树:小于根节点的放在左面,大于根节点的放在右边 二叉排序树(Binary Sort Tree)又称为二叉查找树,它或者是一颗空树,或者是具有下列性质死亡二叉树: 若它的左子树不为空,则左子树上所有结点的值均小于它的根结点的值 若它的右子树不为空,则右子树上所有结点的值均大于它的根结点的值 它的左,右子树也分别为二叉排序树(递归) Code //二叉树的二叉链表结点结构定义 typedef struct BiTNode { int data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //递归查找二叉排序树 T 中是否存在 key //指针f指向T的双亲,其初始值调用值为NULL //若查找成功,则指针p指向该数据元素结点,并返回TRUE //否则指针p指向查找路径上访问的最后一个结点,并返回FALSE Status SearchBST(BiTree T,int key,BiTree f,BiTree *p) { if(!T)//查找不成功 { *p = f; return FALSE; } else if(key == T->data)//查找成功 { *p = T; return TRUE; } else if(key < T->data) { return SearchBST(T->lchild,key,T,p); //在左子树继续查找 } else { return SearchBST(T->rchild,key,T,p); //在右子树继续查找 } } //当二叉排序树T中不存在关键字等于key的数据元素时 //插入key并返回TRUE,否则返回FALSE Status InsertBST(BiTree *T,int key) { BiTree p,s; if(!SearchBST(*T,key,NULL,&p)) { s = (BiTree)malloc(sizeof(BiTNode)); s->data = key; s->lchild = s->rchild = NULL; if(!p) //查找不到key { *T = s; //插入s为新的根节点 } else if(key < p->data) { p->lchild = s; //插入s为左孩子 } else { p->rchild =s; //插入s为右孩子 } } else { return FALSE; //树中有关键字相同的结点,不再插入 //如果想要保存多份相同的可以做个标记 } } Status DeleteBST(BiTree *T,int key) { if(!*T) { return FALSE; } else { if(key == (*T)->data) { return Delete(T); } else if(key < (*T)->data) { return DeleteBST(&(*T)->lchild,key); } else { return DeleteBST(&(*T)->rchild,key); } } } Status Delete(BiTree *p) { BiTree q,s; if((*p)->rchild == NULL) { q = *p; *p = (*p)->lchild; free(q); } else if((*p)->lchild == NULL) { q = *p; *p = (*p)->rchild; free(q); } else { q = *p; s = (*P)->lchild; while(s->rchild) { q = s; s = s->rchild; } (*p)->data = s->data; if(q!=*p) { q->rchild = s ->lchild; } else { q->lchild = s->lchild; } free(s); } return TRUE; } 平衡二叉排序树 如果元素有序,就会生成一个斜二叉树,查找的时间会变长 平衡二叉树:要么它是一颗空树,要么它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1 平衡因子:左右子树深度差的绝对值 平衡二叉树的实现原理 平衡二叉树实现的实例 平衡二叉树的实现代码 Code //左子树高 #define LH 1 //左右子树等高 #define EH 0 //右子树高 #define RH -1 typedef struct BiTNode { int data; int bf;//平衡因子 struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; void R_Roate(BiTree *p) { BiTree L; L = (*P)->lchild; (*P)->lchild = L->rchild; L->child = (*p); *p = L; } void LefBalance(BiTree *T) { BiTree L,Lr; L = (*T)->lchild; switch(L->bf) { case LH: (*T)->bf = L->bf = EH; R_Rotate(T); break; case RH: Lr = L->rchild; switch(Lr->bf) { case LH: (*T)->bf = RH; L->bf = RH; break; case EH: (*T)->bf = L->bf = EH; break; case RH: (*T)->bf = EH; L->bf = LH; break; } Lr->bf = EH; L_Roate((*T)->lchild); R_Roate(T); } } void RightBalance(BiTree *T) { } //taller表示释放长高了 int InsertAVL(BiTree *T,int e,int *taller) { if(!*T) { *T = (BiTree)malloc(sizeof(BiTNode)); (*T)->data = e; (*T)->lchild = (*T)->rchild = NULL; (*T)->bf = EH; *taller = TRUE; } else { if(e == (*T)->data) { *taller = FALSE; return FALSE; } if(e<(*T)->data) { if(!InsertAVL(&(*T)->lchild,e,taller)) { return FALSE; } if(*taller) { switch((*T)->bf) { case LH: LefBalance(T); *taller = FALSE; break; case EH: (*T)->bf = LH; break; case RH: (*T)->bf = EH; *taller = FALSE; break; } } } else { if(!InsertAVL(&(*T)->rchild,e,taller)) { return FALSE; } if(*taller) { switch((*T)->bf) { case LH: (*T)->bf = EH; *taller = FALSE; break; case EH: (*T)->bf = RH; *taller = TRUE; break; case RH: RightBalance(T); *taller = FALSE; break; } } } } }
图的遍历 深度优先遍历 深度优先遍历(Depth First Search),也称为深度优先搜索,简称DFS 它的具体思是:无论从哪个定点开始都可以遍历所有顶点 现在要遍历这样一个图: 我们约定右手原则:在没有碰到重复顶点的情况下,分叉路口始终是向右手边走,没路过一个顶点就做一个记号 我们走过的路就是对这颗蓝色的树进行前序遍历! 马踏棋盘算法 马踏棋盘问题(又称骑士周游或骑士漫游问题)是算法设计的经典问题之一 国际象棋的棋盘为8*8的方格棋盘,现将"马"放在任意指定的方格中,按照"马"走棋的规则将"马"进行移动.要求每个方格只能进入一次,最终使得"马"走遍棋盘64个方格 要求用1-64来标注"马"移动的路径 最多搜索8^64次 一些相关知识点 回溯法 思想很简单,就是一条路走到黑,碰壁了再回来一条路走到黑......一般和递归还有深度优先搜索(DFS)可以很好的搭配使用 哈密尔顿路径: 哈密尔顿路径是指经过图中的每个顶点,且只经过一次的一条轨迹.如果这条轨迹是一条闭合的路径(从起点出发不重复的遍历所有点后仍能回到起始点),那么这条路径称为哈密尔顿路径 Code #include <stdio.h> #include <time.h> #define X 8 #define Y 8 int chess[X][Y]; //找到基于(x,y)位置的下一个可走的位置 int nextxy(int *x,int *y,int count) { switch(count) { case 0: if(*x+2 <= X-1 && *y-1 >= 0 && chess[*x+2][*y-1]==0) { *x = *x + 2; *y = *y - 1; return 1; } break; case 1: if(*x+2 <= X-1 && *y+1 <= Y-1 && chess[*x+2][*y+1]==0) { *x = *x + 2; *y = *y + 1; return 1; } break; case 2: if(*x+1 <= X-1 && *y-2 >= 0 && chess[*x+1][*y-2]==0) { *x = *x + 1; *y = *y - 2; return 1; } break; case 3: if(*x+1 <=X-1 && *y+2 <= Y-1 && chess[*x+1][*y+2]==0) { *x = *x + 1; *y = *y + 2; return 1; } break; case 4: if(*x-2 >= 0 && *y-1 >= 0 && chess[*x-2][*y-1]==0) { *x = *x - 2; *y = *y - 1; return 1; } break; case 5: if(*x-2 >= 0 && *y+1 <= Y-1 && chess[*x-2][*y+1]==0) { *x = *x - 2; *y = *y + 1; return 1; } break; case 6: if(*x-1 >= 0 && *y-2 >= 0 && chess[*x-1][*y-2]==0) { *x = *x - 1; *y = *y - 2; return 1; } break; case 7: if(*x-1 >= 0 && *y+2 <= Y-1 && chess[*x-1][*y+2]==0) { *x = *x - 1; *y = *y + 2; return 1; } break; default: break; } return 0; } void print() { int i,j; for(i=0;i<X;i++) { for(j=0;j<Y;j++) { printf("%2d\t",chess[i][j]); } printf("\n"); } printf("\n"); } //深度优先遍历棋盘 //(x,y)为位置坐标 //tag是标记遍历.每走一次,tag+1 int TravelChessBoard(int x,int y,int tag) { int x1 = x,y1 = y, flag = 0, count = 0; chess[x][y] = tag; if(X*Y==tag) { print(); return 1; } //找到马的下一个可走的坐标(x1,y1),如果找到flag=1.否则为0 flag = nextxy(&x1,&y1,count); while(0==flag && count<7) { count++; flag = nextxy(&x1,&y1,count); } while(flag) { if(TravelChessBoard(x1,y1,tag+1)) { return 1; } //继续找到马的下一步可走的坐标(x1,y1),如果找到flag=1.否则为0 x1 = x; y1 = y; count++; flag = nextxy(&x1,&y1,count); while(0==flag && count<7) { count++; flag = nextxy(&x1,&y1,count); } } if(0 == flag) { chess[x][y] = 0; } return 0; } int main() { int i,j; clock_t start,finish; start = clock(); for(i=0;i<X;i++) { for(j=0;j<Y;j++) { chess[i][j]=0; } } if(!TravelChessBoard(2,0,1)) { printf("马踏棋盘是失败!"); } finish = clock(); printf("\n本次耗时: %f秒\n\n",(double)(finish-start)/CLOCKS_PER_SEC); return 0; } 广度优先搜索 广度优先遍历(Breadth First Search),又称为广度优先搜索,简称BFS 图的广度优先类似于树的层次遍历 要实现对图的广度优先遍历,我们可以利用队列来实现 邻接矩阵的广度优先遍历思路 从一个顶点开始,将其入队列,将它连接的节点入队列,将它弹出队列,后面依次这样做 //邻接矩阵的广度遍历算法(代码没有验证) void BFSTraverse(MGraph G) { int i,j; Queue Q; for(i=0;i<G.numVertexes;i++) { visited[i] = FALSE; } initQueue(&Q); for(i=0;i<G.numVertexes;i++) { if(!visited[i]) { printf("%c ",G.vex[i]); visited[i] = TRUE; EnQueue(&Q,i); while(!QueueEmpty(Q)) { Deque(&Q,&i); for(j=0;j<G.numVertexes;j++) { if(G.art[i][j]==1 && !visited[j]) { printf("%c ",G.vex[j]); visited[j] = TRUE; EnQueue(&Q,j); } } } } } } 最小生成树-普里姆(Prim)算法 void MiniSpanTree_Prim(MGraph G) { int min,i,j,k; int adjvex[MAXVEX]; //保存相关顶点下标 int lowcost[MAXVEX]; //保存相关顶点间边的值 lowcost[0] = 0; //V0作为最小生成树的根开始遍历,权值为0 adjvex[0] = 0; //V0第一个加入 //初始化操作 for(i=1;i<G.numVertexes;i++) { lowcost[i] = G.arc[0][i]; //将邻接矩阵第0行所有权值先加入数组 adjvex[[i] = 0; //初始化全部先为V0的下标 } //真正构造最小生成树的过程 for(i=1;i<G.numVertexes;i++) { min = INFINITY; //初始化最小权值为65535等不可能数值 j = 1; k = 0; //遍历全部顶点 while(j < G.numVertexes) { //找出lowcost数组已存储的最小权值 if(lowcost[j]!=0 && lowcost[j] < min) { min = lowcost[j]; k = j; //将发现的最小权值的下标存入k,以待使用 } j++; } //打印当前顶点边中权值最小的边 printf("(%d,%d)",adjvex[k],k); lowcost[k] = 0; //将当前顶点的权值这只为0,表示此顶点已经完成任务,进行下一个顶点的遍历 //邻接矩阵k行逐个遍历全部顶点 for(j=1;j<G.numVertexes;j++) { if(lowcost[j]!=0 && G.arc[k][j]<lowcost[j]) { lowcost[j] = C.arc[k][j]; adjvex[j] = k; } } } } 最小生成树-克鲁斯卡尔(Kruskal)算法 无论是普里姆算法还是克鲁斯卡尔算法,他们考虑问题的出发点都是:为使生成树上边的权值之和达到最小,则应使生成树中每一条边的权值尽可能的小 * 普里姆算法是以某顶点为起点，逐步找各个顶点上最小权值的边来构建最小生成树的 克鲁斯卡尔算法的思想是直接去找最小权值的边来构建生成树 边集数组 Code int Find(int *parent,int f) { while(parent[f] > 0) { f = parent[f]; } return f; } void MiniSpanTree_Kruskal(MGraph G) { int i,n,m; Edge edges[MAGEDGE]; //定义边集数组 int parent[MAXVEX]; //定义parent数组用来判断边与边是否形成环路 for(i=0;i<G.numVertexes;i++) { parent[i] = 0; } for(i=0;i<G.numEdges;i++) { n = Find(parent,edges[i].begin); m = Find(parent,edges[i].end); if(n!=m) //如果n==m,则形成环路,不满足 { parent[n] = m; //将此边的结尾顶点放入下标为起点的parent数组中,表示此顶点已经在生成树集合中 printf("(%d,%d) %d ",edges[i].begin,edges[i].end,edges[i].weight); } } } 最后的parent数组 当一个图边数少时克鲁斯卡尔算法效率会比较高,也就是说对稀疏图有很大优势;当一个图顶点数多时普里姆算法效率会比较高,也就是说对稠密图有很大优势 最短路径-迪杰斯特拉(Dijkstra)算法 在网图和非网图中,最短路径的含义是不同的 网图是两顶点经过的边上权值之和最少的路径 非网图是两顶点之间经过的边数最少的路径 其实非网图就是权值都为1的网图 我们把路径起始的第一个顶点称为源点,最后一个顶点称为终点 求v0到v8的最短路径 它并不是一下子就求出了v0到v8的最短路径,而是一步步求出它们之间顶点的最短路径,过程中都是基于已经求出的最短路径的基础上,求得更远顶点的最短路径 最短路径-弗洛伊德(Floyd)算法 迪杰斯特拉算法的时间复杂度为O(n^2),弗洛伊德算法的时间复杂度为O(n^3) 迪杰斯特拉算法求得是一个顶点到所有顶点的最短路径,弗洛伊德算法求得是所有顶点到所有顶点的最短路径 P数组用来存储前驱结点 D10=min{D00,D00+D1} #define MAXEX 9 #define INFINITY 65535 typedef int Pathmatrix[MAXEX][MAXEX]; typedef int ShortestPathTable[MAXEX][MAXEX]; void ShortestPath_Floyd(MGraph G,Pathmatrix *p,ShortestPathTable *D) { int v,w,k; //初始化D和P for(v=0;v<G.numVertexes;v++) { for(w=0;w<G.numVertexes;w++) { (*D)[v][w] = G.matrix[v][w]; (*P)[v][w] = w; } } for(k=0;k<G.numVertexes;k++) { for(v=0;v<G.numVertexes;v++) { for(w=0;w<G.numVertexes;w++) { if((*D)[v][w] > (*D)[v][k] + (*D)[k][w]) { (*D)[v][w] = (*D)[v][k] + (*D)[k][w]; (*P)[v][w] = (*P)[v][k]; } } } } } 拓扑排序 一个有向无环图称为无环图(Directed Acyclic Graph),简称DAG图 所有的工程或者某种流程都可以分为若干个小的工程或者阶段,我们称这些小的工程或阶段为"活动" 在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称之为AOV网(Active On Vertex Network) AOV网中的弧表示活动之间存在的某种制约关系 AOV网不能存在回路! 拓扑序列:设G=(V,E)是一个具有n个顶点的有向图,V中的顶点序列V1,V2,......,Vn满足若从顶点Vi到Vj有一条路径,则再顶点序列中顶点vi必在顶点vj之前.则我们称这样的顶点序列为一个拓扑序列 拓扑排序:所谓的拓扑排序,其实就是对一个有向图构造拓扑序列的过程 AOV网图 其中一种拓扑序列:1,13,4,8,14,15,5,2,3,10,11,12,7,6,9 对AOV网进行拓扑排序的方法和步骤如下: 从AOV网中选择一个没有前驱的结点(该节点的入度为0)并且输出它 从网中删除该点,并且删除从该点出发的全部有向变 重复上述两步,知道剩余网中不再存在没有前驱的顶点为止 code //边表结点声明 typedef struct EdgeNode { int adjvex; struct EdgeNode *next; }EdgeNode; //顶点表结点声明 typedef struct VertexNode { int in; int data; EdgeNode *firstdege; }VertexNode,AdjList[MAXVEX]; typedef struct { AdjList adjList; int numVertexes,numEdges; }graphAdjList,*GraphAdjList; //拓扑排序算法 //若GL无回路,则输出拓扑排序序列并返回OK,否则返回ERROR Satus TopologcalSort(GraphAdjList GL) { EdgeNode *e; int i,k,gettop; int top = 0;//用于栈指针下标索引 int count = 0;//用于统计输出顶点的个数 int *stack; //用于存储入度为0的顶点 stack = (int*)malloc(GL->numVertexes*sizeof(int)); for(i=0;i<GL->numVertexes;i++) { if(0==GL->adjList[i].in) { stack[++top] = i; } } while(0!=top) { gettop = stack[top--];出栈 printf("%d-> ",GL->adjList[gettop].data); count++; for(e=GL->adjList[gettop].firstdege;e;e=e->next) { k = e->adjvex; //将k号顶点邻接点的入度置为-1,因为他们的前驱已经消除 //接着判断-1后入度是否为0,如果为0则也入栈 if(!(--GL->adjList[k].in)) { stack[++top] = k; } } } if(count<GL->numVertexes) { return ERROR; } } 算法时间复杂度 对一个具有n个顶点,e条边的网来说,初始建立入度为零的顶点栈,要检查所有顶点一次,执行时间为O(n) 排序中,若AOV网无回路,则每个顶点入,出栈各一次,每个表结点被检查一次,因而执行时间为O(n+e) 所以,整个算法的时间复杂度为O(n+e) 关键路径 AOE网:在一个表示工程的带权有向图中,用顶点表示事件,用又向边表示活动,用边上的权值表示活动的持续时间,这种有向图的表示活动的网,我们称之为AOE网(Activity On Edge Network) 我们把AOE网中没有入边的顶点称为始点或源点,没有出边的顶点称为终点或汇点 AOV没有权值,AOE有权值
图基础 图的定义 图(Graph)是由定点的又穷非空集合和定点之间边的集合组成,通常表示为:G(V,E),其中G表示一个图,V是图G顶点的集合,E是图G中边的集合 线性表中我们把数据元素叫元素,树中叫结点,在图中数据元素我们则称之为顶点(Vertex) 线性表可以没有数据元素,称为空表,树中可以没有结点,叫做空树,大部分国内教材强调图的顶点集合V要又穷非空,而国外允许空 线性表中,相邻的数据元素之间具有线性关系,树结构中,相邻两层的结点具有层次关系,而图结构中任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边来表示,边集可以是空的 图的各种定义 无向边:若顶点Vi到Vj之间的边没有方向,则称这条边为无向边(Edge),用无序偶(Vi,Vj)来表示 上图G1是一个无向图,G1={V1,E1},其中 V1={A,B,C,D} E1={(A,B),(B,C),(C,D),(D,A),(A,C)} 有向边:若从顶点Vi到Vj的边有方向,则称这条边为有向边,也称为弧(ArC),用有序偶<Vi,Vj>来表示,Vi称为弧尾,Vj称为弧头 上图G2是一个有向图,G2={V2,E2},其中 V2={A,B,C,D} E2={<B,A>,<B,C>,<C,A>,<A,D>} 简单图:在图结构中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图 以下两个不属于简单图 无向完全图:在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图.含有n个顶点的无向完全图有n*(n-1)/2条边 有向完全图:在有向图中,如果任意两个顶点之间都存在方向护卫相反的两条弧,则称该图为有向完全图.含有n个顶点的有向完全图有n*(n-1)条边 稀疏图和稠密图:这里的稀疏图和稠密图是模糊的概念,都是相对而言的,通常认为边或弧度数小于n*logn(n是顶点个数)的图称为稀疏图,反之称为稠密图 有些图的边或弧带有与它相关的数字,这种与图的边或弧相关的数叫做权(Weight),带权的图通常称为网(Network) 假设有两个图G1=(V1,E1)和G2(V2,E2),如果V2∈V1并且E2∈E1,则称G2位G1的子图(Subgraph) 图的顶点与边之间的关系 对于无向图G=(V,E),如果边(V1,V2)∈E,则称顶点V1和V2互为邻接点(Adjacent),即V1和V2相邻接.边(V1,V2)依附(incident)于顶点V1和V2,或者说边(V1,V2)与顶点相关联 顶点V的度(Degree)是和V相关联的边的数目,记为TD(V),如下图,顶点A与B互为邻接点,边(A,B)依附于顶点A与B上,顶点A的度为3 对于有向图G=(V,E),如果有<V1,V2>∈E则称顶点V1邻接到顶点V2,顶点V2邻接自顶点V1 以顶点V为头的弧的数目称为V的入度(InDegree),即为ID(V),以V为尾的弧的数目称为V的出度(OutDegree),记为OD(V),因此顶点V的度为TD(V)=ID(V)+OD(V) 下图顶点A的入度是2,出度是2,所以顶点A的度是3 无向图G=(V,E)中从顶点V1到顶点V2的路径(Path) 下图用红线列举了从顶点B到顶点D的四种不同路径 如果G是有向图,则路径也是有向的 下图用红线列举顶点B到顶点D的两种路径,而顶点A到顶点B就不存在路径 路径的长度是路径上的边或弧的数目 第一个顶点到最后一个顶点相同的路径称为回路或环(Cycle) 序列中顶点不重复出现的路径称为简单路径,除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简单环 下图左侧是简单环,右侧不是简单环 连通图 在无向图G中,如果从顶点V1到顶点V2有路径,则称V1和V2是连通的,如果对于图中任意两个顶点Vi和Vj都是连通的,则称G是连通图(ConnectedGraph) 下图左侧不是连通图,右侧是连通图 无向图中的极大连通子图称为连通分量 注意以下概念: 首先要是子图,并且子图是要连通的 连通子图含有极大顶点数 具有极大顶点数的连通子图包含依附于这些顶点的所有边 在有向图G中,如果对于没一对Vi到Vj都存在路径,则称G是强连通图 有向图中的极大强连通子图称为有向图的强连通分量 下图左侧并不是强连通图,右侧是.并且右侧是左侧的极大连通子图,也是左侧的强连通分量 连通图的生成树:连通图的生成树是一个极小的连通子图,它含有图中全部的n个顶点,但只有足以构成一棵树的n-1条边 图: 其中一种生成树: 如果一个有向图恰有一个顶点入度为0,其余顶点的入度均为1,则是一颗有向树 图的存储结构 邻接矩阵(无向图) 图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图.一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息 我们可以设置两个数组,定点数组为vertex4={v0,v1,v2,v3},边数组arc4位对称矩阵(0表示不存在顶点间的边,1表示顶点间存在边) 对称矩阵:所谓对称矩阵就是n阶矩阵的元满足a[i][j]=a[j]i.即从矩阵的左上角到右下角的主对角线为轴,右上角的元素与左下角相对应的元全都是相等的 有了这个二维数组组成的对称矩阵,我们就可以很容易的知道图中的信息: 要判定任意两顶点是否有边无边就非常容易了 要知道某个顶点的度,其实就是这个顶点vi在邻接矩阵中第i行(或第i列)的元素之和 求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1就是邻接点 邻接矩阵(有向图) 可见顶点数组vertex4={v0,v1,v2,v3},弧数组arc4也是一个矩阵,但因为是有向图,所以这个矩阵并不对称,例如由v1到v0有弧,得到arc[1][0]=1,而v0到v1没有弧,因此arc0=0 另外有向图是有讲究的,要考虑入度和出度,顶点v1的入度为1,正好是v1列的各数之和,顶点v1的出度为2,正好是第v1行的各数之和 邻接矩阵(网) 每条边上带有权的图就叫网 (v1,v1)为0 这里的无穷表示一个计算机允许的,大于所有边上权值的值 邻接表 对于边数相对顶点较少的图,邻接矩阵会极大的浪费空间,因此我们可以考虑另外一种存储结构方式,例如把数组与链表结合一起来存储,这种方式在图结构也适用,我们成为邻接表(AdjacencyList) 邻接表的处理方法是这样的: 图中顶点用一个一维数组存储,当然,顶点也可以用单链表来存储,不过数组可以比较容易的读取顶点信息,更加方便 图中每个顶点vi的所有邻接点构成一个线性表,由于连接点的个数不确定,所以我们选择用单链表来存储 若是有向图,邻接表结构也是类似的,我们先来看下把顶点当弧尾建立的邻接表,这样很容易就可以得到每个顶点的出度 但有时为了便于确定顶点的入度或以顶点为弧头的弧,我们可以建立一个有向图的逆邻接表: 此时我们很容易就可以算出某个顶点的入度或出度是多少,判断两顶点是否存在弧也很容易实现 对于带权值得网图,可以在邻接表结点定义中再增加一个数据域来存储权值即可 十字链表 邻接表固然优秀,但也有不足,例如对有向图的处理上,有时候需要再建立一个逆邻接表 有没有可能把邻接表和逆邻接表结合起来呢,那就是十字链表(Orthognal List) 重新定义定点表结构: data | firstIn | firstOut 重新定义定边表结构: tailVexa | headVex | headLink | tailLink 十字链表的好处就是把邻接表和逆邻接表整合在一起了,这样既容易找到vi为尾的弧,也容易找到一vi为头的弧,因而容易求得顶点的出度和入度 十字链表除了结构复杂一点外,其实创建图算法的时间复杂度是和邻接表相同的,因此,在有向图的应用中,十字链表也是非常好的数据结构模型 邻接多重表 如果我们在无向图的应用中,关注的重点是定点的话,那么邻接表是不错的选择,但如果我们更关注的是边的操作,比如对已经访问过的边做标记,或者删除某一条边等操作,邻接表就显得不那么方便了 因此我们也仿照十字链表的方式,对边表结果进行改装,重新定义的边表结构如下 iVex | iLink | jVex | jLink 其中iVex和jVex是某条边依附的两个定点在顶点表中的下标.iLink指向依附顶点iVex的下一条边,jLink指向依附顶点jVex的下一条边 也就是说在邻接多重表中，边表存放的是一条边，而不是一个定点 边集数组 边集数组是由两个一维数组构成,一个是存储定点的信息,另一个是存储边的信息,这个边数组每个数据元素由一条边的起点下标(begin),终点下标(end)和权(weight)组成
树的定义 树(Tree)是n(n>=0)个结点的有限集.当n=0时称为空树,在任意一颗非空树中: 有且仅有一个特定的称为根(Root)的结点 当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2....Tm,其中每个集合本身又是一棵树,并且称为根的子树(SubTree) 结点分类 结点拥有的子树的个数称为结点的度(Degree),树的度取树内各结点的度的最大值. 度为0的结点称为叶结点(Leaf)或终端结点 度不为0的结点称为分之结点或非终端结点,除根节点外,分支结点也成为内部节点 结点间的关系 结点的子树的根称为结点的孩子(Child),相应的,该节点称为孩子的双亲(Parent),同一双亲的孩子之间互称为兄弟(Sibling) 结点的祖先是从根到该节点所经分支上的所有节点 结点的层次 结点的层次(Level)从根开始为第一层,根的孩子为第二层 其双亲在同一层的结点互为堂兄弟 树中结点的最大层次称为树的深度(Depth)或高度 其他概念 如果将树中结点的各个子树看成从左至右是有次序的,不能互换的,则称该树为有序树,否则称为无序树 森林(Forest)是m(m>0)棵互不相交的树的集合.对树中每个结点而言,其子树的集合即为森林 树的存储结构 孩子双亲表示法 #define MAX_TREE_SIZE typedef char ElemType; //孩子结点 typedef struct CTNode { //孩子结点的下标 int child; struct CTNode *next; }*ChildPtr; //表头结构 typedef struct { //存放在树中的结点的数据 ElemType data; //双亲的下标 int parent; //指向第一个孩子的结构 ChildPtr firstchild; }CTBox; //树结构 typedef struct { //结点数组 CTBox nodes[MAX_TREE_SIZE]; } 二叉树 二叉树的定义 二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根节点和两颗互不相交的,分别称为根节点的左子树和右子树的二叉树组成 这个定义显然是递归形式的 二叉树的特点 每个结点最多有两颗子树,所以二叉树中不存在度大于2的结点 左子树和右子树是有顺序的,次序不能颠倒 即使树中某结点只有一颗子树,也要区分它是4左子树还是右子树 特殊二叉树 斜树 满二叉树 在一颗二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子结点都在同一层上,这样的二叉树称为满二叉树 叶子结点只能出现在最下一层 非叶子结点的度一定是2 在同样深度的二叉树中,满二叉树的结点个数一定最多,同时叶子结点也是最多 完全二叉树 对一颗树具有n个结点的二叉树按层序编号,如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点位置完全相同,则这颗二叉树称为完全二叉树 叶子结点只能出现在最下两层 最下层的叶子一定集中在左部连续位置 倒数第二层,若有叶子结点,一定都在右部连续位置 如果结点度为1,则该节点只有左孩子 同样节点数的二叉树,完全二叉树的深度最小 满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树 二叉树的性质 在二叉树的第i层至多有2^(i-1)个结点(i>=1) 深度为k的二叉树至多有2^k-1个结点(k>=1) 对任何一颗二叉树T,如果其终端节点数为n0,度为2的结点数为n2,则n0=n2+1 具有n个结点的完全二叉树的深度为floor(log2n)+1 满二叉树的深度为k=log2(n+1) 对于倒数第二层的满二叉树我们同样很容易回推它的节点数为n=2^(k-1)-1 所以完全二叉树的节点数的取值范围是:2^(k-1)<n<2^k-1 二叉树的存储结构 typedef struct BiTNode { ElemType data; struct BiTNode *lchild,*rchild; }BiTnode,*BiTree; 二叉树的遍历 二叉树的遍历(traversing binary tree)是指从根节点出发,按照某种次序依次访问二叉树中所有节点,使得每个结点被访问一次且仅被访问一次 二叉树的遍历方法 二叉树的遍历方式可以很多,如果我们限制了从左到右的习惯方式,那么主要就分为以下四种: 前序遍历 中序遍历 后序遍历 层次遍历 前序遍历: 若二叉树为空,则返回,否则县访问根节点,然后前序遍历左子树,再前序遍历右子树 中序遍历 若树为空,则返回,否则从根节点开始(并不是访问根节点),中序遍历根节点的左子树,然后是访问根节点,最后中序遍历右子树 后序遍历 若树为空,则返回,否则从左到右先叶子后结点的方式遍历访问左右子树,左后访问根节点 层次遍历 若树为空,则返回,否则从树的第一层,也就是根节点开始访问,从上而下逐层遍历,在同一层中,按从左到右的顺序对结点逐个访问 #include <stdio.h> #include <stdlib.h> typedef char ElemType; typedef struct BiTNode { ElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //创建一颗二叉树,约定用户遵照前序遍历的方式输入数据 void CreateBiTree(BiTree *T) { char c; scanf("%c",&c); if(' '==c) { *T = NULL; } else { *T = (BiTNode *)malloc(sizeof(BiTNode)); (*T)->data = c; CreateBiTree(&(*T)->lchild); CreateBiTree(&(*T)->rchild); } } //访问二叉树结点的具体操作 void visit(char c,int level) { printf("%c位于第%d层\n",c,level); } //前序遍历二叉树 void PreOrderTraverse(BiTree T,int level) { if(T) { visit(T->data,level); PreOrderTraverse(T->lchild,level+1); PreOrderTraverse(T->rchild,level+1); } } //中序遍历二叉树 void InOrderTraverse(BiTree T,int level) { if(T) { InOrderTraverse(T->lchild,level+1); visit(T->data,level); InOrderTraverse(T->rchild,level+1); } } //后序遍历二叉树 void PostOrderTraverse(BiTree T,int level) { if(T) { PostOrderTraverse(T->lchild,level+1); PostOrderTraverse(T->rchild,level+1); visit(T->data,level); } } int main() { int level = 1; BiTree T = NULL; CreateBiTree(&T); PreOrderTraverse(T,level); return 0; } 线索二叉树 由于二叉树的叶子节点会有很多指针被浪费了,我们考虑能不能把浪费的空间利用起来 二叉树只能从双亲结点找到孩子节点,我们可以把指针利用起来,哪种遍历方式可以更好的利用叶子节点的指针呢? 前序遍历:A B D H I E C F G 中序遍历:H D I B E A F C G 我们可以看出来中序遍历可以更好的利用指针,两个指针分别指向前驱和后继节点 黑色的线指向前驱节点,红色的线指向后继节点 将定义好的结构扩容: lchild ltag data rtag rchild ltag为0时指向该节点的左孩子,为1时指向该节点的前驱 rtag位0时指向该节点的右孩子,为1时指向该节点的后继 #include <stdio.h> #include <stdlib.h> typedef char ElemType; //线索存储标志位 //Link(0):表示指向左右孩子的指针 //Thread(1):表示指向前驱后继的线索 typedef enum {Link,Thread} PointerTag; typedef struct BiThrNode { ElemType data; struct BiThrNode *lchild,*rchild; PointerTag ltag; PointerTag rtag; }BiThrNode,*BiThrTree; //全局变量,始终指向刚刚访问过的结点 BiThrTree pre; //创建一颗二叉树,约定用户遵照前序遍历的方式输入数据 void CreateBiThrTree(BiThrTree *T) { char c; scanf("%c",&c); if(' '==c) { *T = NULL; } else { *T = (BiThrNode *)malloc(sizeof(BiThrNode)); (*T)->data = c; (*T)->ltag = Link; (*T)->rtag = Link; CreateBiThrTree(&(*T)->lchild); CreateBiThrTree(&(*T)->rchild); } } void InThreading(BiThrTree T) { if(T) { //递归左孩子线索化 InThreading(T->lchild); //处理结点 //如果该节点没有左孩子,设置ltag为Thread //并把lchild指向刚刚访问的结点 if(!T->lchild) { T->ltag = Thread; T->lchild = pre; } if(!pre->rchild) { pre->rtag = Thread; pre->rchild = T; } pre = T; //递归右孩子线索化 InThreading(T->rchild); } } void InOrderThreading(BiThrTree *p,BiThrTree T) { *p = malloc(sizeof(BiThrTree)); (*p)->ltag = Link; (*p)->rtag = Thread; (*p)->rchild = *p; if(!T) { (*p)->lchild = *p; } else { (*p)->lchild = T; pre = *p; InThreading(T); pre->rchild = *p; pre->rtag = Thread; (*p)->rchild = pre; } } void visit(char c) { printf("%c",c); } //中序遍历二叉树,非递归 void InOrderTraverse(BiThrTree T) { BiThrTree p; p = T->lchild; while(p!=T) { while(p->ltag==Link) { p = p->lchild; } visit(p->data); while(p->rtag == Thread && p->rchild != T) { p = p->rchild; visit(p->data); } p = p->rchild; } } int main() { //ABC^^D^^E^F^^^ BiThrTree P,T = NULL; CreateBiThrTree(&T); InOrderThreading(&P,T); printf("中序遍历结果为:"); InOrderTraverse(P); printf("\n"); return 0; } 树,森林以及二叉树的相互转换 普通树转换为二叉树 加线:在所有兄弟结点之间加一条线 去线:对树中每个结点,只保留它与第一个孩子结点的连线,删除它与其他孩子结点之间的连线 层次调整:以树的根节点为轴心,将整棵树顺时针旋转一定角度,使之结构层次分明 森林转换为二叉树 把每棵树转换为二叉树 第一棵二叉树不动,从第二棵二叉树开始,依次把后一颗二叉树的根节点作为前一棵二叉树的根节点的右孩子,用线连接起来 二叉树转换为树,森林 二叉树转换为普通树是刚才的逆过程,步骤是反过来做 判断一颗二叉树能够转换成一棵树还是森林,标准很简单,那就是只要看这颗二叉树的根节点有没有右孩子,有的话就是森林,没有的话就是一棵树 树与森林的遍历 树的遍历分为两种方式:一种是先根遍历,另一种是后根遍历 先跟遍历:先访问树的根节点,然后再依次先根遍历根的每棵子树 后根遍历:先依次遍历每棵子树,然后再访问根节点 森林的遍历也分为前序遍历和后序遍历,其实是按照树的先根遍历和后根遍历依次访问森林的每一棵树 我们发现:树,森林的前根遍历和二叉树的前序遍历结果相同,树,森林的后根遍历和二叉树的中序遍历结果相同 我们找到了对树和森林遍历这种复杂问题的简单解决方案 赫夫曼树 在数据膨胀,信息爆炸的今天,数据压缩的意义不言而喻.谈到数据压缩,就不能不提赫夫曼(Huffman)编码,赫夫曼编码是首个实用的压缩编码方案,即使在今天的许多知名压缩算法里,依然可以见到赫夫曼编码的影子 另外,在数据通信中,用二进制给每个字符进行编码时,不得不面对的一个问题是如何使电文总长最短且不产生二义性.根据字符出现频率,利用赫夫曼编码可以构造出一种不等长的二进制,使编码后的电文长度最短,且保证不产生二义性 赫夫曼树定义与原理 我们先把这两棵二叉树简化成叶子结点带权的二叉树(注:树结点间的连线相关的数叫做权,Weight) * 结点的路径长度:从根结点到该结点的路径上的连接数 * 树的路径长度:树中每个叶子结点的路径长度之和 * 结点带权路径长度:结点的路径长度与结点权值的乘积 * 树的带权路径长度:WPL(Weighted Path Length)是树中所有叶子结点的带权路径长度之和 WPL的值越小,说明构造出来的二叉树性能越优 WPL值最小的二叉树为最优二叉树 赫夫曼编码
数据结构与算法之:字符串和KMP算法(五)
字符串 串(String)是由零个或多个祖父组成的有限序列,又叫做 字符串 传可以使空串 子串与主串,例如 "Matrix" 是 "Matrix42" 的子串,反之"Matrix42" 为 "Matrix" 的主串 字符串的比较 字符串比较大小跟传统的数字比较大小有点差别,很容易我们可以知道2比1要大,可是"matrix" 和 "Matrix42"呢?,要怎么比较呢?比长短还是比大小? 比大小!逼得就是字符串里每个字符的ASCII码的大小,因为'M'== 77 , 'f'==109,所以"matrix" > "Matrix42" 其实这样的比较大小没有多大意义,字符串的比较我们更重视是否相等! 字符串的存储结构 字符串的存储结构与线性表相同,也分顺序存储结构和链式存储结构 字符串的顺序存储结构使用一组地址连续的存储单元来存储串中的字符串序列的 按照预定义的大小,为每个定义的字符串变量分配一个固定长度的存储区,一般用定长数组来定义 与线性表相似,既然是固定长度的存储区,就存在一个空间分配不灵活的问题,那么会考虑用链式存储结构 不同的是字符串我们一般都是连在一起表述的,"断章取义"的情况并不多,所以习惯上我们通常还是会直接定义一个足够长度的存储区来存储的 BF(Brute Force)算法 BF算法属于朴素的模式匹配算法,它的核心思想是: 有两个字符串S和T,长度为N和M,首先S[1]和T[1]比较,若相等,则再比较S[2]和T[2],一直到T[M];若S[1]和T[1]不等,则T向右移动一个字符的位置,再依次进行比较 该算法最坏情况下要进行M*(N-M+1)次比较,时间复杂度为O(M*N) 在这里S是主串,T是子串,这种子串的定位操作通常称作串的模式匹配 KMP算法 KMP算法是三位老前辈(D.E.Knurh,J.HMorris和V.R.Paratt)的研究结果,大大的避免重复遍历的情况,全称叫做克努特-莫里斯-普拉特算法,简称KMP算法 KMP算法的核心是避免不必要的回溯,问题由模式串决定,不是由目标串决定 KMP算法之next数组代码原理分析 next数组:当模式匹配串T失配的时候,next数组对应的元素指导应该用T串的哪个元素进行下一轮匹配 j= 0; i = 1; next[1] = 0; //T[0]为串的长度 while(i<T[0]) { //匹配上了 if(j==0 || T[i] == T[j]) { //前缀 i++; //后缀 j++; next[i] = j; } //失配 else { //j回溯 j = next[j]; } } KMP算法之实现及优化 typedef char* String; void get_next(String T,int *next) { int j = 0; int i = 1; next[1] = 0; while(i<T[0]) { if(0==j || T[i] == T[j]) { i++; j++; if(T[i]!=T[j]) { next[i] = j; } else { next[i] = next[j]; } } else { j = next[j]; } } } //返回子串T在主串S第POS个字符之后的位置 //若不存在,则返回0 int Index_KMP(String S,String T,int pos) { int i = pos; int j = 1; int next[255]; get_next(T,next); while(i<S[0] && j<=T[0]) { if(0==j || S[i]==T[j]) { i++; j++; } else { j = next[j]; } } if(j>T[0]) { return i-T[0]; } else { return 0; } }