- 博客(51)
- 资源 (4)
- 收藏
- 关注
RSS订阅原创 分治法
分治法：1） 将问题的实例划分为同一个问题的几个较小的实例，最好拥有同样的规模2） 对这些较小的实例求解（一般使用对贵方法，但在问题规模足够小的时候，有时候会利用另一个算法）。3） 如果必要的话，合并这些较小问题的求解，已得到原始问题的解1. 归并排序算法：mergeSort(A,n)//用对贵调用对数组 A进行排序//输入：一个待排序的数组
2011-11-03 11:04:53
881
原创 蛮力法
蛮力法：是一种简单直接地解决问题的方法，常常直接给予问题的描述和所涉及的概念定义。1. 选择排序算法：SelectionSort(Array a)//该算法用选择排序对给定数组排序//输入：一个可排序数组 A[0,1,….n-1]//输出：一个已排序数组 A[0,1,….n-1](升序)for i min
2011-11-01 16:21:32
1344
1
原创 算法学习1
时间过得挺快，一晃就快毕业了。工作找好了，最近也闲的无聊，所以买了本算法书，想好好的看看算法。话不多说从最基本的算法开始：1. 求小于根号n的最大整数。算法： for m if m*m return m实现：int sqrtN(int n){
2011-10-27 10:33:52
580
原创 http服务器的实现3_http响应
在实现http响应包头之前，我们来看下http响应的格式：HTTP/version 应答码消息Content-Type： MINE……………………. 正文 例子：HTTP/1.1 200 OKContent-Type: text/html
2011-09-01 22:35:03
896
原创 http服务器的实现2_http请求的包头解析
http请求包的基本格式如下：方法 /资源路径 ？参数1&参数2 HTTP/version…………..……………例如：GET/jianli.pdf HTTP/1.1Host:127.0.0.1Connection:keep-aliveUser-A
2011-09-01 22:31:42
2435
原创 http服务器的实现1_网络服务器的实现
前段时间看了《深入理解计算机系统》，在网络编程这一章看到了一个http服务器的简单实现，然后也想自己在windows下面实现一个简单的http服务器。 为了方面叙述，下面从实现的角度来一步步的说明怎么实现这个http服务器。其实说到http服务器也就是从浏览器发送
2011-09-01 22:30:19
1607
1
原创 关于内联函数
看c++primer时看到一句话“把内联函数放到头文件中”。当时看了后觉的挺奇怪，如果把内联函数放到头文件中 岂不是在链接时要报错？因为会产生重复定义的错误。但是测试了下面的代码：test.h#ifndef ___TEST_H_#define ___TEST_H
2011-09-01 11:09:27
684
原创 串口调试程序的实现
由于需要用到串口读写程序,然后就简单的实现了个串口读写程序(基于MFC）。首先是串口的读写，基本的函数就是CreateFile，ReadFile，WriteFile,SetCommState和GetCommState。所以首先为了更好的调用这些函数我对这些函数
2011-07-05 16:49:11
1846
1
原创 wcout不能输出中文的解决方法
<br />当然我也是从网上找的资料，原理不懂。<br />基本上，如果wcout不能输出中文，只需要加上这句语句就可以：<br />wcout.imbue(locale(locale(),"",LC_CTYPE));<br />原理有待以后再深究，现在就记下解决方案。
2011-05-25 15:37:00
1094
原创 快速排序的实现
<br />快速排序的思想跟归并排序的思想是一致的,也就是把一个大的问题,分成2个小的问题,然后再合并.<br />概念简单来讲就是,首先在待排序队列里面找到一个数,比这个数小的放到这个数的左边,比这个数大的放到数的右边,然后分别对左右两边进行递归排序.<br />代码如下:QuickSort.h<br /><br />/******************************************************<br />* 快速排序步骤：QuickSort<br />*
2011-05-19 00:48:00
514
原创 归并排序的实现(again)
<br />归并排序也就是把一个数列分成两份,首先分别对2份进行排序,然后把这2份一起排序,典型的递归实现.<br />实现代码: MergeSort.h：<br /><br />//归并排序时间复杂度：NlogN，但是由于存在<br />// for(inti=0;i!=length;++i)<br />// *first++=*(assistSpace+i);<br />//数据的复制需要额外的时间，
2011-05-18 00:09:00
489
原创 堆排序的实现
<br />堆排序也就是一个简单的完全二叉树，满足的规则是每个父节点大于（小于）子节点，一般通过线性队列来实现，所以一般是通过数组来实现的。<br />基本的排序步骤是：<br />1.创建堆 CreateHeap<br />2.依次的取出头节点（也就是最大值或者最小值） deleteMax<br />3.把取出的值放到一个新的容器中，当然我们为了空间复杂度较小 可以直接在原有的容器末尾插入。<br /><br /><br />实现：<br />HeapSort.h<br /><br />//堆排序的实现，
2011-05-16 21:01:00
401
原创 希尔排序的实现
希尔排序，也就是对于一列数据，对间隔为k的数据进行排序，也就是对于 1、1+k、1+2×k....；2、2+k、2+2×k、....；..... 分别进行排序，这样 间隔为k 的数据就是有序的了，然后逐渐减小k的值，知道k为1的时候，也就是对整个数列进行完整的排序了。希尔排序关键的地方是 k值怎么确定，k为多少的时候效率最高，一般来说 是2n-1,2n-1-1,.......1 这样的k比较好。关键代码如下：templatevoid __shellSort(Iterator first,Iterator
2011-05-12 00:08:00
520
原创 插入排序的实现
<br />插入排序，就是吧第p位置的数据，插入到容量为p的有序容器中。<br />当然，一般来说，我们可以重新分配一块新的空间，用来存放有序的数据。但是下面的例子是在就的空间上进行排序，每次插入操作就是把第p位置的数据插入到0～p的位置上：<br /><br />template<typename Obj,typenameIterator_><br />void _insert_sort(Iterator_ first,Iterator_last,Obj)<br />{<br /> f
2011-05-11 23:58:00
406
原创 线程管理_1
<br />这里先来进行线程的入门，没有涉及到任何同步的问题，关于同步的问题后面再说。<br />主要函数：<br />_beginthreadex (注意一般不要用 CreateThread,以为这个函数在调用c库函数的时候不是线程安全的，具体细节我也不明白，不过微软都这样建议 那么就这样了，以后我不会用到CreateThread）<br />_endthreadex<br />细节不说，可以自己看msdn上的参数说明，基本上就是，给线程提供一个入口地址，提供一些参数，然后得到线程id和线程句柄。<br
2011-04-29 16:17:00
432
原创 进程管理
<br />进程管理（这里不涉及到进程间通讯）<br />主要函数：<br />CreateProcess。<br />直接来看刚才写的一段程序。<br />2个进程，（主）进程创建5个子进程并给他传递打开文件的句柄，让5个子进程分配对文件进行写数据。<br />子进程：<br /><br />#include<windows.h><br />#include<tchar.h><br />#include<iostream><br />using namespace std;<br />int _tmain
2011-04-28 19:21:00
468
原创 内存管理_3
<br />内存映射文件实例——dll<br />（本文只是为了自己需要以帮助自己以后能很快的回顾，不适合其他人来阅读，如果您需要学习dll的编写或者dll 的2种调用方式 那么请继续google）<br />动态库的好处在前面说过，可以动态调用，节约内存空间，以及动态的改变dll而不需要重新编译我们调用dll 的客户端程序。<br />动态的库的调用有2中方式，一种是显式的一种隐式的，这里我只考虑显式的，隐式的调用跟静态库的调用类似，需要提供声明文件和库文件（lib）所以我们在隐式调用dll 的时候需要提
2011-04-28 15:51:00
450
原创 内存管理_2
<br /><br />(本文只适合本人以后复习使用，如果你想要学习知识点，可能会浪费你的时间）<br />内存映射文件： 我们知道dll是通过内存映射来实现动态的内存访问的，这样可以让多个进行同时访问同一内存空间。<br />其实dll就是利用的内存映射的原理。我们每个进程都有自己独立的虚拟内存空间，所以不同进程指向的dll的虚拟内存空间是不同的，但是dll 的不同进程的虚拟内存空间映射的却是同一物理内存地址，所以我们可以利用dll 来进行进程间通讯。<br />所以内存映射文件的本质就是让进程的虚拟内存
2011-04-27 17:17:00
504
原创 内存管理_1
<br />(本文只适合本人以后复习的需要，不适合其他人的学习，如果你不小心进来了，那么不好意思浪费您的时间了）<br />几个重要的函数：<br />GetProcessHeap//得到当前进程的主堆，注意这个失败返回的是NULL而不是INVALID_HANDLE_VALUE<br />HeapCreate//创建一个堆<br />HeapDestroy//删除某个堆<br />HeapAlloc//在某个堆上分配内存空间，跟malloc（calloc）是一致的<br />HeapFree//释放到某个堆
2011-04-27 16:36:00
719
原创 异常处理
<br />（下面的内容主要是让自己以后在使用中能够很快的想起并使用，不适合别人来学习知识点的，所以如果你不小心Google进来了，那么浪费你时间了）<br />在windows里面异常处理主要是通过：<br />_try,_except,_finally<br />这3个模块来处理的，当然里面会用到GetExceptionCode来得到异常代码，一般是在<br />_except(filter(GetExceptionCode()))<br />{<br /> ....<br />}<br />里面用
2011-04-27 10:31:00
619
原创 文件管理_2
<br />这里主要提到的是注册表的注册，如果你不小心google到了这里想知道操纵注册表的一系列函数的使用，那么请看这篇文章：<br />http://dev.firnow.com/course/3_program/c++/cppxl/20090821/169471.html<br />上面这篇文章里面对注册表的相关函数整理的很清晰。<br /> <br />因为前段时间看COM，里面要注册自己的组件的时候需要 实现组件的注册函数，所以这次看注册表这部分的时候就专门针对，组件注册来看了。<br />在<<
2011-04-26 17:35:00
476
原创 文件管理_1
<br />跟文件管理相关的就平时应用来说最重要几个函数如下：（如果你想通过这篇文章知道怎么使用这些函数，那么抱歉，我这里写的只会浪费你时间）<br />读写文件：<br />CreateFile//打开（或者创建）文件句柄<br />ReadFile//读文件<br />WriteFile//写文件<br />CloseHandle//关闭句柄<br />GetStdHandle//得到标准设备句柄<br />（在这里ReadFile和WriteFile的最后一个参数OVERLAPPED结构体都设为NUL
2011-04-26 17:16:00
639
原创 Groupsock的分析_2
<br />前面说了Groupsock的基类，现在来整体的分析下Groupsock：<br />首先是：<br /> removeAllDestination<br /> removeDestination<br /> addDestination<br /> changeDestinationParamters<br />这4个成员函数，这几个函数都是跟一个 destRecord链表关联的，成员变量 fDests指向这个链表的表头。<br />从字面意思基本可以得到
2011-04-12 18:36:00
2505
1
原创 Groupsock的分析_1
<br /> 在进行Groupsock分析之前先复习下 组播（多播）的知识.<br /> 首先组播 是基于 UDP的，所以在后面代码里面会出现：sock(AF_INET,SOCK_DGRAM,0); SOCK_DGARM就是代表是UDP进行通信。<br />然后组播是对应一个D网段的IP，我们需要加入组播才能向组播的成员发送数据或者接受数据，所以代码中会有setsockopt的调用（当然这个函数不光是针对加入组播的）。 最后需要注意的一点是，我们通讯 是在UDP(TCP）之上的某个端口上
2011-04-03 18:30:00
4119
原创 TaskScheduler的分析_4
前面分析了跟TaskScheduler相关的3个链表，那么现在就剩下最后一个doEventLoop函数了。在BasicTaskScheduler0中对doEventLoop进行了实现，它是通过循环调用 SingleStep 来完成功能的。在这里需要提一下为什么要通过 while(1) 这个循环来不停的调用SingleStep，因为在SingleStep中 有 select 函数，对于单线程 网络通讯 select 模型，必须要不停的循环调用select函数（同步阻塞模式），因为select是监控某些端口，
2011-04-03 00:13:00
3161
原创 TaskScheduler的分析_3
前面提到了跟 DelayTask相关的一个链表，现在来看跟BackgroundHandling相关的另一个链表：HandleSet.这个链表跟：setBackgroundHandlingdisableBackgroundHandlingmoveSocketHandling这3个函数相关。其中setBackgroundHandling根据第二个参数 int conditionSet 是否为零 对应于插入和删除节点的操作。disableBackgroundHanding 对应删除节点操作。moveSocketH
2011-04-02 14:53:00
1415
原创 选择排序
<br />前面提到了仿函数，那么这里就利用仿函数实现了选择排序：<br />首先定义一个仿函数模板：<br />template<typename T>struct my_larger:public std::binary_function<T,T,bool>{ bool operator()(T arg1,T arg2) { return arg1>arg2; }}; <br />然后是选择排序的实现：<br />template<typename Iterator,typ
2011-04-02 12:50:00
538
原创 TaskScheduler的分析_2
<br />前面说到了 在 TaskScheduler中可能包含3个链表。<br />然后我们继续看TaskScheduler的子类 BasicTaskScheduler就可以到里面有一个这个成员变量：<br />DelayQueue <br />fDelayQueue；<br /> <br />fDelayQueue就是我们前面说的其中一个链表，这个链表是跟DelayedTask相关的。<br />然后我们来继续看DelayQueue这个链表类，它的节点是DelayQueueEntry。这是一个双向
2011-04-01 16:42:00
1128
原创 仿函数
<br />仿函数的主要目的是让对象的操作与函数操作一致，然后就是为了能进一步扩展满足一些适配器的操作。<br />所以根据上面2个目的，仿函数有2点需要实现。<br />1. 让对象的操作与函数的操作一致。 那么对象只需要 重载 operator() 就可以了。<br />2.让仿函数能进一步扩展，那么仿函数就必须有共同的规范，比如我们需要 得到 参数类型 和返回类型怎么办，所以为了满足这点需要，我们必须 继承 unarg_function<T,E>（一元操作） 或者继承binary_function<
2011-04-01 10:02:00
579
原创 TaskScheduler的分析_1
virtual ~TaskScheduler ()virtual TaskToken scheduleDelayedTask (int64_t microseconds, TaskFunc *proc, void *clientData)=0virtual void unscheduleDelayedTask (TaskToken &prevTask)=0virtual void rescheduleDelayedTask (TaskToken &task, int64_t microseconds, Ta
2011-03-31 19:49:00
2937
1
原创 归并排序的实现
<br />定义：<br />归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 （从百度百科上摘抄下来的）<br /> <br />基本的实现可以如下表示：<br /> <br />void merger_sort(Iterator first,Iterator last)<br />{<br />if(last-first<=1)<br />return ;<br />Iterator m
2011-03-31 13:44:00
532
原创 UsageEnviroment的分析
<br />UsageEnvironment是live555中最基本的几个基类之一，不过它的功能很简单，就是对错误的处理和输出。<br />在这个类里面有几个虚函数：<br />operator << 用于输出信息<br />setResultMsg 用于设置一个内部字符串（一般用来表示错误信息的）<br />reportBackgroundError 用于报告错误信息。<br /> <br />在live555中是通过BasicUsageEnvrionment来继承UsageEnvironment来
2011-03-30 20:46:00
1344
原创 计数排序的实现
<br />定义：<br />计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。（来自维基百科）<br /> <br />实现：<br /> <br /> <br />#ifndef COUNT_SORT_H#define COUNT_SORT_H#include<iostream>using namespace std;template<typename
2011-03-25 15:49:00
471
原创 RB Tree的部分实现
<br />跟前面一样，主要是平衡度的问题，RB树是通过节点上的颜色来识别是否平衡的。那么关键是 怎么知道是否平衡，怎么恢复平衡。<br />首先 每个节点有一个成员用于记录节点的颜色：<br />enum Color_node {red=0,black};template<class T>struct node{ typedef node* PVOID ; PVOID parent,l_child,r_child; T key; Colo
2011-03-25 14:12:00
574
原创 桶排序的实现
<br />最近CSDN不知道搞什么，很慢，太无语了。<br />桶排序定义：<br />N个数，区间在[0,1)，把这段区间划分成N份，然后把这N个数依次放到这N份区间中去，注意这里每份空间都代表一个桶，然后对桶里面的元素进行排序，最后把桶结合起来就成了有序的数列。<br />在这里我把区间设为[min，max+1），原理是一样的，其实桶排序的实现是从哈希表来的，后面有时间按会实现hash表的。<br />源码：<br />#ifndef BUCKET_SORT_H#define BUCKET_SOE
2011-03-24 17:57:00
646
原创 AVL Tree 的实现
<br />首先 AVL 树是平衡二叉搜索树，所以首先 必须满足搜索树，即l_child值<parent值<=r_child值。这个在前面已经实现了。插入和删除不停的递归就可以。<br />其次 AVL 树是平衡二叉树，他的平衡条件是左右子树的深度之差小于2.而关键问题在怎么计算深度之差。<br />一般的方法都是通过平衡度来衡量的。而平衡度怎么得到呢，一般是通过左右子树的深度差得到。其实别人怎么得到平衡度我也没搞明白，不过在这里我是参考了一中思路，就是在每个节点中 包含它自己的高度，而没有直接包含平衡度。
2011-03-22 15:04:00
2908
原创 鸡尾酒排序的实现
<br />定义：<br />也就是定向冒泡排序, 鸡尾酒搅拌排序, 搅拌排序 (也可以视作选择排序的一种变形), 涟漪排序, 来回排序 or 快乐小时排序, 是冒泡排序的一种变形。此演算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。（摘抄自 百度百科）<br /> <br />实现：<br />template<typename Iter,typename T>void cocktail_sort(Iter first,Iter last,T){ bool flag=false;
2011-03-20 18:55:00
607
原创 冒泡算法的实现
<br />定义：<br />冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二
2011-03-20 18:06:00
467
原创 二叉查询树的实现
因为在关联容器里面主要的内部结构是RB-tree，而红黑树又是一种平衡二叉树，平衡二叉树又是属于二叉查询树，所以按照 侯捷介绍的顺序依次来实现，今天先把二叉查询树这种最简单的实现掉：首先，二叉查询树 不像heap中完全二叉树那样内存分配用线性存储的，二叉查询树一般内部存储是通过链表来实现的，首先来看每个节点的数据结构：templatestruct node{ T value; node* lChild; node* rChild;}; 每个节点都包含了它的孩子节点信息，这样可
2011-03-18 13:31:00
622
原创 heap的分析
<br />以前对堆都没什么了解，今天看了书之后才终于明白了，堆其实就是一个完全二叉树，对于查找和排序时间复杂度可以很好的降低：<br />heap分为两种：一种是max-heap一种是min-heap，按照书上的，我们假设为 max-heap，即根节点为最大值：<br />所以：<br />我们的内存分配方式为线性存储，用的是vector。<br />父节点如果位置是 i，那么子节点位置就是2*i+1 和2*i+2；<br />所以如果我们插入一个元素的话，通过跟它的父节点比较，然后依次互换位置。这样就能
2011-03-16 12:45:00
611
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人