二叉树数据结构完全实现(非递归遍历)

最近为了准备考MSE研究生,也顺便复习了一下数据结构的理论知识,其中书中留了一个问题,算是习题吧,叫我们用非递归的方式遍历二叉树。我想既然算是复习,就自己再写一次吧。 二叉树ADT,是一个节点最多可有两个子节点的抽象数据类型,当结点数是N时,树的平均深度是O(根号N),平均查找时间在O(logN)。二叉树在计算机中有着非常广泛的应用,例如数据索引(二叉查找树),编译器设计(表达式树)等等。 遍历二叉树就是用不同的方式,把二叉树里面的数据逐一遍历出来,不同的遍历方式有不同的效果,例如中序遍历,遍历出来的数据一般都是已经排序的,后序遍历可以构建表达式树等。遍历的时候使用递归,当数据量很大时,可能因为应用程序自身的堆栈空间不够而导致程序的崩溃。如果自己建立堆栈的话,不仅可以保证堆栈够用,而且还减少函数调用时保存程序上下文的开销。

熟悉Nginx,为Nginx编写插件(四) 简单MVC

看了前面三篇文章是不是觉得Nginx的插件开发很简单?多看看Nginx的源代码对我们的开发插件很有帮助的。这篇文章是计划中的最后一篇,我准备在这篇文章里去实现一个可走通的Nginx MVC模块,现在WEB开发不是流行MVC架构嘛,所以我决定实现一个简单的MVC架构来完结我的连载…(连载上瘾了..) 本文地址:http://www.hoverlees.com/blog/?p=369 MVC就是所谓的Model-View-Controller结构,目的就是把程序和美工分开的方式,而且便于维护,好的Model一般都会提高Controller的开发效率,这个很多相信很多人比我要理解得透彻啦。我所设想的架构如下图形式: 麻雀虽小五脏俱全。Model是Nginx及MVC模块,View是一系列的HTML文件,Controller是一系列的动态链接库。 首先,View和Controller一般都是放在两个目录下的,这两个目录的信息肯定不写死在模块里,那我们就把它作为模块的参数,让它们可以在Nginx的配置文件里配置Controller和View所存放的目录。 OK,这儿我们就不需要更多的配置了,然后,我们决定这个MVC的调用指令为”mvc”,它接收两个参数,一个是Controller存放目录,另一个是View存放目录,下面是设置这个指令的代码,前两章说得比较多,这里就不多说了。

熟悉Nginx,为Nginx编写插件(三)

前两篇文章看了后相信可以写出五花八门的有用的Nginx插件了。我写的都是一些基本的流程,Nginx提供的函数可以很直观地从函数名上表现出来,所以也没过多的说明。这一章说说Nginx的配置,主要是配置模块命令的参数,顺便提一下HTTP的参数处理。 本文链接 这次实现一个提供命令 “pw” 的模块,这个命令需要一个参数: 模块命令调用的参数在这个command的set函数被内核调用的时候可以取得,即是内核传过来的ngx_conf_t变量里可以取得,cf->args->elts是一个参数字符串数组。 这时取到的参数我们可以存起来,也可以根据参数的不同指定不同的处理函数,本文的例子是用的第二种方式。

熟悉Nginx,为Nginx编写插件(二)

前面介绍了Nginx,现在准备为它写一个名叫“helloworld”的插件,它提供helloworld命令。 前面提到过,Nginx的插件可以提供命令,命令在插件里本身是关联到一个处理函数的,这个处理函数直接处理request,并把结果返回到链表里。可以在配置文件里配置什么时候执行插件的相关命令,这样就可以调度插件了。 本文地址:http://www.hoverlees.com/blog/?p=352 按上面和前一篇文章提的,我们可以加一个location叫/helloworld,如下: 这样用户访问/helloworld的时候,就可以执行我们的模块了。 但是还不能急,一般模块都会涉及到一些数据结构,像PHP的模块,需要模块结构,函数表结构等,类似的,Nginx的模块也需要模块结构,模块结构又相关到命令结构和上下文结构。思路都是差不多的。

熟悉Nginx,为Nginx编写插件(一)

最近打算写几篇关于Nginx插件开发的文章。 有人肯定要问我,怎么老是喜欢写插件,一会儿是php的,一会儿是apache的,现在又是Nginx的了。这怎么说呢,其实为linux写应用程序,可以理解成为linux写插件,就算你要写操作系统,同样也可以称之为“为CPU写插件”。为某个东西写插件,还不如说是要更加深入地了解这个东西呢。Nginx本身小巧,研究它其实都可以对整个代码扫通了,我们从中一定能学到人家的长处。 这次连载计划写成,第一篇,内核简介 第二篇,hello world 第三篇,模块配置 第四篇,一个实例。 当然,本文结尾处我也要推荐一篇国外高手写的文章,其实我很想把它翻译成中文,但这要等有时间的时候才能做,忙啊~~~ 本文原地址:http://www.hoverlees.com/blog/?p=322 Nginx是近两年才出来的高性能WebServer服务器,俄罗斯人开发,在我印象里,俄罗斯人搞的软件很牛X,他们在破解软件上也很牛X,唯一的缺点,就是语言的通用性不够牛X,不够大众… Nginx特性: Nginx非常快,非常省资源,网上有大量的Nginx性能测试数据,这儿就不多说了。还有一个开源的WebServer叫Cherokee,自称比Nginx更强劲的,不过这个没做太多研究。 Nginx直接集成反向代理功能,为大型的web应用提供负载均衡的保证。 Nginx本身非常小,整个Server其实就一个2M多的执行程序加上配置文件。 Nginx配置非常直观,配置就跟写脚本一样。 Nginx依赖的PCRE库,在文本处理上具有很强的功能,虽然Nginx本身主要是拿来做重定向的,但正则表达式在文本处理应用中的重要性和普遍性,相信所有做过Web的人都认同。 Nginx又依赖了OpenSSL库,数据安全方面又有保障,可以拿来做CS/BS架构应用项目的服务器(只需为Ngnix写插件而不用自己去实现网络协议),如OA系统,当下流行的网页游戏服务器,SNS游戏等。 Nginx的模块不像其它应用的扩展那样,是动态链接的,Nginx的模块是跟它的源代码一起直接编译到执行文件中,当然如果想让它可以动态链接外部库,只需要为Nginx写一个不是很难的模块即可实现。 Nginx主要的类型和常量定义在/src/core目录下的多个头文件中,对于这样小巧的工程,这些头文件定义的东西都值得去了解。

ictclas分词COM封装

中文分词,是程序对中文语义的分析的第一步,把一个句子按语法语义分成多个词语,便可方便进行下一步的处理。中文分词在中文搜索引擎方面广泛应用,还可以应用在聊天机器人、信息自动搜集等很多方面。 记得我的毕业设计就是中文搜索引擎,当时自己只用PHP实现了正向最大匹配分词法,效率不是很高,而且分出来的词也不是很精确(不过最简单,哈哈)。但对于一个毕业设计来说,这样已经足够了。但要对一个实际应用来说,分词肯定要越精准越好。中科院的ICTCLAS中文分词库,应该是最好的选择。 这个组件是因为PHP需要用到ictclas分词功能,但官方只提供dll版本,那就有两种方式,一种是封装成php模块,另一种就是封装成com组件了。既然是运行在windows上的,就决定装成com了。 组件提供3函数,init,split,exit.具体看例子一下子就知道了。

PHP模块by Nasm

用了这么多年的PHP,还真有幸地做过几次扩展,以前做的扩展,大都是在windows平台上,然后用的COM组件实现,也有一次写的应用程序,然后用TCP协议调用函数,却从来没有尝试过去写PHP模块,正好这次的PHP产品又有做扩展的需要,服务器也是多种操作系统的,这样的情况,何不尝试用PHP模块的方式来实现呢。我使用了NASM 汇编语言,这种开源的,跨平台的汇编语言。 为什么用汇编语言呢,其实PHP用C语言写模块的话,会有很多的宏调用,方便快捷,而我要用汇编语言去写第一个模块,主要就是想从PHP的文档和源代码共同地去研究PHP的内部,真正深入地了解它的执行。以后的开发肯定还是要用C语言的,因为它不仅仅是跨平台了,还可以跨CPU架构。 开始研究文档,PHP文档《PHP at the Core: A Hacker’s Guide to the Zend Engine》一章里很详细地讲述了PHP内核的运行机制及模块的加载方式,加上官方网站上下载的源代码,一切都不是秘密了。

MASM32编写的表单提交库

这个库是以前用MASM32的时候写的,它的功能其实就是实现multipart/form-data的标准的方式去与HTTP WebServer交互。只是这个库是纯socket实现的模拟浏览器表单提交,包含提交文件的功能。 首先要承认,做这个库的时候,我没有去看相关的规范文档,而是截获的IE提交表单的数据包来分析,然后再用socket直接封装的这个库。Multipart的form其它字段跟post的也差不多,而上传文件的时候是用一个界限字符串来区分文件。我一直在想,如果文件是一个文本文件,文本文件里恰好又包含这个boundary的结束标记,那会出现什么情况呢。呵呵,当然,我的boundary标记是随机生成的,所以基本上是不大可能与文本文件里有相同的字符串,有就不知道是什么结果了。总之我觉得我们不用太关注这种基本上不可能发生的小概率事件。 有了这个库,应用程序就可以实现跟浏览器一样的向webserver上传文件功能了。

32bit ASM to 64bit ASM–汇编语言64bit心得

最近有个项目,我使用NASM编写的,运行在32位windows和linux主机上,但后来需求增加了,需要在64位windows和linux上运行,windows自身有个wow(windows on windows)机制,32位程序根本不用移植就能在64位机器上跑,而linux虽然没有LOL机制(是Linux on linux,不是laugth out loud哈,呵呵 ~),但linux 可以安装ia-libs库(ia 应该是 Intel x86 Archive的简写)达到LOL效果,不过,编译ELF64和WIN64OBJ也是我比较感兴趣的,所以我要移植程序!