Chinaunix首页 | 论坛 | 博客
  • 博客访问: 279520
  • 博文数量: 82
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 874
  • 用 户 组: 普通用户
  • 注册时间: 2015-03-21 09:58
个人简介

traveling in cumputer science!!

文章分类

全部博文(82)

文章存档

2016年(13)

2015年(69)

我的朋友

发布时间:2016-03-13 13:44:08

1.KMP算法理解
1.1次方法是一种常用的提高字符串匹配效率的算法,由作者Knuth–Morris–Pratt得名。但实际意义是字符串匹配过程中,省略不必要操作的一种方法。
最基础的方法是令匹配模板pattern,从待匹配string的头开始,逐位后移进行操作。如下:
a b c a b a c c a b c a b a c c a b c a b a c c a b c a b a c c a b c a b a c c
| | \ \ \ | | | \ \......【阅读全文】

阅读(1365) | 评论(0) | 转发(0)

发布时间:2016-02-21 21:16:59

1.归并排序理论
基本思想是将两个已排序的表归并为一个有序表。归并排序也是分治策略的思想体现。
(1)按递归的方法,从上向下的角度来思考,把待排序表一分为二,然后将分割后的两个表再次平分,直到分割后只剩下一个元素为止,然后将分割的结果进行两两归并,直到递归程序结束,排序完成
(2)按迭代的方法,从下向上的角度来思考,首先把待排序表中每个元素都看作一个有序表,然后将元素两两归并,然后把操作后的表中元素每对儿看作是一个有序表,然后再以对儿为基础两两归并,同理直到将所有元素归并为一个有序表,排序结束
3.总结
?(1)思考了递归与迭代的两种逆向思维
?(2)理解了分治策略的实践
?(3)程序中尝试了C++中I/O文件操作方法
? 参考链接:http://blog.csdn.net/mak0000/article/details/3230199......【阅读全文】

阅读(2561) | 评论(0) | 转发(0)

发布时间:2016-02-21 11:01:43

1.堆排序理论
?本方法采用最大堆结构,最大堆是一棵完全二叉树也是一棵最大树,最大树是指在树中,若一个结点有儿子结点则其关键字值都不小于其儿子结点的关键字值。
?根据需要排序的序列list,
?(1)把list创建为最大堆结构,这一步不用添加额外存储空间,以list本身为堆的存储结构,从首元素开始逐个将元素加入堆中,每加入一个就要重新调整为最大堆,这样直到最后一个元素加入调整成与原list对应的最大堆;
?(2)取堆顶元素,也就是(1)调整后的list的首元素,使其与堆list的末尾元素交换,这样就形成了除去最大元素的一个新堆,调整新堆为新的最大堆,这一过程中就不再考虑交换到末尾的旧的最大堆的堆顶元素,调整后就形成了比原list缺省了最大元素的新最大堆,按照这个规则每次都取新的最大堆的堆顶元素与新的最大堆的末尾元素交换,然后调整为比上一最大堆少一个元素的新最大堆,直到所有list元素取完,原list就形成了一个升序的排列

3.总结
?(1)最大堆的父节点与子节点间的关系挺有意思,依据这个关系很方便的进行堆调整
? ......【阅读全文】

阅读(1810) | 评论(0) | 转发(0)

发布时间:2016-02-20 17:27:31

1.快排序理论:
快速排序是一种平均时间性能非常好的方法。一般排序算法,每次循环之后只能减少一个数据量因此复杂度是O(N2),而快排序是选定基准元素,一般取第一个,每次安排完一个数据后还能将其余数据分成一组比它大和一组比它小的两组数据,按此方法,再依次分别对分好类的数据进行排序操作,下面以一组数据举例。
3.总结
?这次实现代码过程中遇到的问题
?(1)遇到“segmentation fault”错误,段错误,经过查资料,知道是指针误操作导致,错误原因:程序中指针没有初始化就进行相应操作
?(2)压栈操作压入数据异常,此处也属于指针操作错误,指针操作前应先初始化,C++ 用new关键字, C里面用malloc函数
? 使用实例:
? new:
? int *p = new int(10);
? 注意使用结束时使用delete释放:
? delete p;
? malloc:
? ......【阅读全文】

阅读(2698) | 评论(0) | 转发(0)

发布时间:2015-03-27 21:08:07

my learn process of CS algorithm!! The first KMP!!......【阅读全文】

阅读(972) | 评论(0) | 转发(0)
给主人留下些什么吧!~~
留言热议
请登录后留言。

登录 注册