Matrix42 - 数据结构与算法
type: channel
link: http://www.sundeqiang.cn/category/algorithm
items: 学习资料
items: 数据结构与算法之: 排序 (十一)
items: 数据结构与算法之: 查找 第二部分 (十)
items: 平衡二叉树的实现代码
items: 平衡二叉树实现的实例
items: 平衡二叉树的实现原理
items: 数据结构与算法之: 查找 第一部分 (九)
items: 数据结构与算法之: 图 第二部分 (八)
items: 数据结构与算法之: 图 第一部分 (七)
items: 数据结构与算法之: 树 (六)

学习资料
type: item
date: 2017-05-26T18:23:00+08:00
description: 常见数据结构与算法整理总结（上） 常见数据结构与算法整理总结（下） 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版，及唯品会的实战 优秀博客 花钱的年华 骊骅 为梦码一生

数据结构与算法之: 排序 (十一)
type: item
date: 2017-02-02T11:02:00+08:00
description: 影响排序算法性能的几个要素 时间性能 辅助空间 算法的复杂性 冒泡排序 冒泡排序的基本思想 两两相邻记录的关键字,如果反序则交换,直4到没有反序的记录为止 Code void BubbleSort(int k[],int n) { int i,j,temp; for(i=0;i<n-1;i++) { for(j=n-1;j>i;j--) { if(k[j-1] > k[j]) { temp = k[j-1]; k[j-1] = k[j]; k[j] = temp; } } } } 冒泡排序的要点 两两注意是相邻的两个元素的意思 如果有n个元素需要比较n-1次,每一轮减少1次比较 优化 void BubbleSort(int k[],int n) { int i,j,temp,flag; flag = 1; for(i=0;i<n-1&&flag;i++) { flag = 0; for(j=n-1;j>i;j--) { if(k[j-1] > k[j]) { temp = k[j-1]; k[j-1] = k[j]; k[j] = temp; flag = 1; } } } } 选择排序 选择排序的基本思想 选择排序算法就是通过n-i次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1<=i<=n)个记录交换 Code #include <stdio.h> void SelectSort(int k[],int n) { int i,j,min,temp; for(i=0;i<n-1;i++) { min = i; for(j=i+1;j<n;j++) { if(k[j]<k[min]) { min = j; } } if(min!=i) { temp = k[min]; k[min] = k[i]; k[i] = temp; } } } 直接插入排序 直接插入排序的基本思想 直接插入排序算法(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的,记录数增加1的有序表 Code void InsertSort(int k[],int n) { int i,j,temp; for(i=1;i<n;i++) { if(k[i] < k[i-1]) { temp = k[i]; for(j=i-1;k[j] > temp;j--) { k[j+1] = k[j]; } k[j+1] = temp; } } } 希尔排序 Code void ShellSort(int k[],int n) { int i,j,temp; int gap = n; do { gap = gap/3 + 1; for(i=gap;i<n;i++) { if(k[i] < k[i-gap]) { temp = k[i]; for(j=i-gap;k[j] > temp;j-gap) { k[j+gap] = k[j]; } k[j+gap] = temp; } } }while(gap > 1) } 堆排序 要点 根节点一定是堆中所有节点最大或者最小的,如果按照层序遍历的方式给节点从1开始编号,则结点之间满足如下关系 ki >= k2i ki <= k2i 或 (1<=i<=floor(n/2)) ki >= kv(2i+1) ki <= kv(2i+1) 堆排序(Heap Sort)就是利用堆进行排序的算法,它的基本思想是: 将待排序的序列构造成一个大顶堆(或小顶堆) 此时,整个序列的最大值就是堆顶的根节点.将它移走(就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值) 然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素中的最大值 如此反复执行,便能得到一个有序序列 Code void swap(int k[],int i,int j) { int temp; temp = k[i]; k[i] = k[j]; k[j] = temp; } void HeapAdjust(int k[],int s,int n) { int i; for(i=2*s;i<=n;i*=2) { if(i<n && k[i]<k[i+1]) { i++; } if(temp >= k[i]) { break; } k[s]= k[i]; s = i; } k[s] = temp; } //数组从1开始 void HeapSort(int k[],int n) { int i; for(i=n/2;i>0;i--) { HeapAdjust(k,i,n); } for(i=n;i>1;i--) { (k,1,i); HeapAdjust(k,1,i-1); } } 归并排序 归并…

数据结构与算法之: 查找 第二部分 (十)
type: item
date: 2017-01-20T11:54:00+08:00
description: 多路查找树(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^…

平衡二叉树的实现代码
type: item
date: 2017-01-20T10:57:20+08:00
description: 平衡二叉树的实现代码如下 #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 等相关信息 { r…

平衡二叉树实现的实例
type: item
date: 2017-01-20T10:47:00+08:00
description: 选取一组数据分别为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

平衡二叉树的实现原理
type: item
date: 2017-01-20T10:22:00+08:00
description: 概念 平衡二叉树建立在二叉排序树的基础上，目的是使二叉排序树的平均查找长度更小，即让各结点的深度尽可能小，因此，树中每个结点的两棵子树的深度不要偏差太大。 平衡二叉树的递归定义：平衡二叉树是一棵二叉树，其可以为空，或满足如下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 转自 吴小宝的博客

数据结构与算法之: 查找 第一部分 (九)
type: item
date: 2017-01-17T11:21:00+08:00
description: 静态查找和动态查找 静态查找:数据集合稳定,不需要添加,删除元素的查找操作 动态查找:数据集合在查找的过程中需要同时添加或删除元素的查找操作 对于静态查找来说,我们不妨可以用线性表结构组织数据,这样可以使用顺序查找算法,如果我们再对关键字进行排序,则可以使用折半查找算法或斐波那契查找算法等来提高查找的效率 对于动态查找来说,我们则可以考虑使用二叉排序树的查找技术,另外我们还可以使用散列表结构来解决一些查找问题 顺序查找 顺序查找又叫做线性查找,是最基本的查找技术,它的查找过程是:从第一个(或最后一个)记录开始,逐个进行记录的关键字和给定值进行比较,若某个记录的关键字和给定值相等,则查找成功.如果查找了所有记录仍然找不到与给定值相对的关键字,则查找不成功 折半查找 如果待查找的记录是有序的,可以用折半查找 折半查找的基本思想:减小查找序列的长度,分而治之的进行关键字的查找 折半查找的实现过程:先确定待查找记录的所在范围,然后逐渐缩小这个范围,查找到该记录或查找失败为止 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 …

数据结构与算法之: 图 第二部分 (八)
type: item
date: 2017-01-14T11:11:00+08:00
description: 图的遍历 深度优先遍历 深度优先遍历(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(…

数据结构与算法之: 图 第一部分 (七)
type: item
date: 2017-01-05T09:45:00+08:00
description: 图基础 图的定义 图(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)存储方式是用两个数组来表示图.一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中…

数据结构与算法之: 树 (六)
type: item
date: 2017-01-01T09:48:00+08:00
description: 树的定义 树(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)是指从根节点出发,按照某种次序依次访问二叉树中所有节点,使得每个结点被访问一次且仅被访问一次 二叉树的遍历方法 二叉树的遍历方式可以很多,如果我们限制了从左到右的习惯方式,那么主要就分为以下四种: 前序遍历 中序遍历 后序遍历 层次遍历 前序遍历: 若二叉树为空,则返回,否则县访问根节点,然后前序遍历左子树,再前序遍历右子树 中序遍历 若树为空,则返回,否则从根节点开始(并不是访问根节点),中序遍历根节点的左子树,然后是访问根节点,最后中序遍历右子树 后序遍历 若树为空,则返回,否则从左到右先叶子后结点的…