追求卓越
hao3100590 · 共 47 篇文章
二叉堆的实现
1.堆的概念 这里只需要注意两点: a.堆的存储方式:就是顺序存储在数组中,在二叉树中表现为满二叉树 b.堆的用处:用于排序,查找最大最小都非常方便 2.堆的实现 heapexception.h #ifndef HEAPEXCEPTION_H #define HEAPEXCEPTION_H class ArrayOverFlowException{ public: const char* what() const throw() { return "array over flow exception!\n"; } }; class ParametersErrorException{ publ…
2012-08-12 11:35 · 算法学习 · 评论(0)
KMP算法解析
一.理论基础 1.什么是kmp算法 同BF算法一样,就是串的模式匹配算法。 前面已经学过,我想都应该明白BF算法,就是用一种最直观的方式进行模式匹配。 优点:非常容易理解,是我们常用的思维方式来编程; 缺点:效率比较低,在匹配不成功的时候,回朔做了许多无用功; 从而根据其缺点,KMP算法就在回朔的时候做了工作,减少其无用功,那么怎么去减少回朔的工作呢? 下面举例说明: 例如: s = abababc t = ababc 其匹配过程如下图: 从图中我们看到了具体的变换过程,就是在回朔的过程中做了许多工作,S的i不需要回朔到1,只需要T回朔就可以了,那么怎么知道T回朔到什么位置才好呢?而从上面的…
2012-08-12 11:35 · 算法学习 · 评论(0)
常见字符串操作大全
1.常见的字符串操作 如计算长度,求子串等都是考验基本功的,现在基本操作进行实现,如下 2.基本实现 mchar.h //串的基本操作(注意:里面的所有操作要求串必须以'\0'结束) #ifndef MCHAR_H #define MCHAR_H //注意:这里面的i都是位置,从1开始;而数组中对应于0,从0开始 class MChar{ public: int strLen(const char *s); //串长度(在输入串的时候,必须以'\0'结束) char* strCpy(char* s,const char* p); //串拷贝,p拷贝给s,原来的值被覆盖 char* strCa…
2012-08-12 11:34 · 算法学习 · 评论(0)
排序方法总结
这里面包含了所有常见的排序操作 1.性能等比较分析 2.代码实现 sort.h //各种排序方法总结 #ifndef SORT_H #define SORT_H template<class T> class Sort{ public: void insertSort(T r[], int n); //直接顺序排序 void shellSort(T r[], int n); //希尔排序 void bubbleSort(T r[], int n); //起泡排序 void quickSort(T r[], int first, int end); //快速排序 void selectSort…
2012-08-12 11:34 · 算法学习 · 评论(0)
set和map的简单实现
1.Set的简单实现 set是利用二叉查找树来实现的,而且为了查找方便,添加了另外两个指针,一个指向下一个最小结点,一个指向上一个最大结点。 iset.h //利用二叉查找树实现set #ifndef ISET_H #define ISET_H template<class T> struct Node{ T data; Node<T> *rchild, *lchild; //左右孩子 Node<T> *parent; //父结点 Node<T> *next, *pre; //下一个最小和上一个最大的结点 Node(){ rchild = lchild = parent = 0; next …
2012-08-10 11:35 · 算法学习 · 评论(0)
红黑树的插入总结
1.红黑树 这个在july的博客中有详尽的说明,我就不在赘述了 http://blog.csdn.net/v_JULY_v/article/details/6105630 2.红黑树的插入 插入见下图:
2012-08-10 11:25 · 算法学习 · 评论(0)
B-树实现
1.什么是B-树? 这个在我的前一篇博客中已经详细的阐释过: http://hao3100590.iteye.com/blog/1576846 具体的了解,好好看看这篇文章就可以了! 2.实现关键问题分析 a.B-树删除原则 见下图: 当然总结起来,大的方面就3点,具体的细节就没有做多大的说明,在下面具体实现的时候会说明 b.B-树的递归和非递归遍历 对于非递归遍历,比较麻烦,自己需要按照下面图中所示的方式来遍历B-树,输出的关键字大小从小到大排列,但是对于递归却相当简单,这里非递归没有利用栈来实现,所以注意! c.B-树删除伪代码 见下图: d.具体删除之借详细演示 如下图: 3.关键函数…
2012-08-10 11:03 · 算法学习 · 评论(0)
平衡二叉树
1.问题描述 什么是平衡二叉树?在此就不在赘述,下面主要就几个关键问题进行分析 2.关键问题 a.AVL树的非递归与递归插入 平衡二叉树的非递归的关键: 1.在寻找插入位置和旋转的时候设置其路径上的平衡因子,这个要特别注意 当然非递归比递归复杂的多,但是对于理解其执行过程很有帮助! 2.是旋转之后可能并没有产生效果(实际上是旋转成功,但是输出的树没有变),因为在修改的时候,并没有注意结点的改变,没有使用指针引用,修改原来树的指针,指向旋转之后的新的根结点。 这个在setBF(Node<T>* r);中分了两种情况:a.旋转结点是根结点; b.旋转结点非根结点,必须手动设置pre前序指针指向。…
2012-08-10 10:39 · 算法学习 · 评论(0)
二叉排序树
1.基本概念 二叉排序树,树的定义就不赘述了,主要就是想说明一下在设计类的过程中需要注意的问题。 a.问题引入? 设计插入,删除等操作的过程中,我们的二叉排序树根节点的指针有可能改变,如删除根结点的指针操作,那么root的指针指向已经不是原来的位置,而是新的位置,怎么样才能返回最新的位置呢? b.问题解决 在设计类中的函数就可以轻易的解决这个问题,这个在函数设计之初就必须详细的考虑这个问题,这里有两种办法 首先 ,通过返回值,返回最新的root结点; Node<T>* deleteBST(T x); Node<T>* insertBST(T x); 这样在使用的过程中就需要这样使用: BiS…
2012-08-10 10:25 · 算法学习 · 评论(0)
B-树
1.B-树的概念 是一种多路搜索树,适合在磁盘等直接存取设备上组织动态的查找表,可能部分数据不在内存中。它作为索引文件的一种重要存储结构(数据库索引) 对于m阶(m>=3)B-tree,满足如下特性: 1)树中每个节点至多有m个节点 2)根节点子树个数在:2---m(根非叶子节点) 3)非根节点子树个数在:m/2(向上取整)---m。 4)排列规则:所有叶节点在同一层,按照递增次序排列。 由于节点关键字个数比子树个数少1,故而关键字个数满足: 1)根节点关键字个数在:1---m-1(根非叶子节点) 2)非根节点 关键字 个数在:m/2(向上取整)-1---m-1。 2.B-tree的搜索特性…
2012-07-04 22:48 · 算法学习 · 评论(2)
构造哈夫曼树
1.算法说明 就是建造哈夫曼树树,从而使得构造出的树带权路径长度最小 2.步骤 输入叶子结点个数n; 创建长度为2*n-1的数组并初始化; while(i<n) 循环输入n个叶子结点的权值; while(n-1次循环建立树){ 在parent==-1的元素中查找权最小的两个结点; 合并两个叶子结点,并加入新结点到数组; } 3.代码 //构造haffman树 #include <iostream> using namespace std; const int MAX = 10000; struct Node{ int weight; //权值 int parent; //双亲 int lch…
2012-07-04 10:40 · 算法学习 · 评论(0)
线索二叉树
1.算法描述 就是简单的线索二叉树的建立,遍历,查找等基本操作,具体什么是线索二叉树,百度一下! 2.算法说明 具体说明有四点:如下图 注:尤其要注意第4点,我在写的时候就没注意这个问题,结果遍历的时候出现了无限循环,找了半天才找到!主要是建立二叉树判断的惯性思维,故而容易出现错误! 3.代码实现 头文件 #ifndef BITHRTREE_H #define BITHRTREE_H enum flag{CHILD, THREAD};//枚举类型,枚举常量Child=0,Thread=1 template<class T> struct Node{ //二叉线索树的结点结构 Node<T> …
2012-07-04 09:20 · 算法学习 · 评论(0)
二叉树基本操作大全
1.二叉树的基本操作 这里我有一个疑问: 在使用构造函数的时候,传参数的问题? 开始我是这么理解的------只使用指针(其实指针本身就是一个地址,相当于引用,也会改变root建立起二叉树),而2指针的引用,相当于就是对记录了指针的地址,采用了二次引用,其实是没有必要的,一次就够了。但是实际上用的时候并不是这样?根本不能建立二叉树,原因是因为开始指针指向的是一个不确定的位置?然后我又实验了,分配空间先,但是还是不行?所以不知道为什么一定要使用双重指针或指针引用?不知哪位高人能解答之,谢谢了 就是这样void creatTree(Node<T>* root); //声明类BiTree及定义结构…
2012-07-03 18:22 · 算法学习 · 评论(2)
多种队列的实现
1.算法描述 a.数据结构与算法(Mark Allen Weiss)3.28双端队列的实现,在队列的两端都可以进行插入和删除工作,每种操作复杂度O(1). b.没有头结点和尾结点的队列实现 c.循环数组的队列实现 2.算法实现 a.由于有复杂度的限制,和两端插入删除,故而使用数组是不适合的,必须使用链表,我这里使用的是双向链表,在两端操作的复杂度就一样的,非常方便 b.没有头尾结点实现队列,关键就是注意空队列的判断,在空队列情况下的插入删除操作。 c.循环数组就是在尾部循环的时候操作。 3.代码实现 a.双端队列 deque.h //双端队列(两头都可以插入删除,故而使用的双向链表) #if…
2012-06-29 10:09 · 算法学习 · 评论(0)
栈的各种实现
1.算法描述 a.实现二个栈,在一个数组里面,除非没有任何空间剩余,否则不能有溢出声明 b.实现一个没有头尾结点的栈(单链表) c.实现带有头结点的栈(单链表) 2.双栈 对于双栈,我们还可以添加resize()方法,当空间满了重新自动分配空间(new),就是将原来的两个栈,拷贝到新建立的数组上面去 a.dsexceptions.h #ifndef DSEXCEPTIONS_H #define DSEXCEPTIONS_H //栈溢出异常 class StackOverFlowException{ //public: exception public: const char* what() …
2012-06-28 16:34 · 算法学习 · 评论(0)