﻿<?xml version="1.0" encoding="utf-8" standalone="yes"?><rss version="2.0" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:trackback="http://madskills.com/public/xml/rss/module/trackback/" xmlns:wfw="http://wellformedweb.org/CommentAPI/" xmlns:slash="http://purl.org/rss/1.0/modules/slash/"><channel><title>IT博客-菜鸟天堂</title><link>http://www.cnitblog.com/tonywearme/</link><description>海纳百川有容乃大，壁立千仞无欲则刚</description><language>zh-cn</language><lastBuildDate>Wed, 29 Apr 2026 06:04:35 GMT</lastBuildDate><pubDate>Wed, 29 Apr 2026 06:04:35 GMT</pubDate><ttl>60</ttl><item><title>Why you should learn the API before MFC[转载]</title><link>http://www.cnitblog.com/tonywearme/archive/2006/09/17/16952.html</link><dc:creator>樱木</dc:creator><author>樱木</author><pubDate>Sun, 17 Sep 2006 02:10:00 GMT</pubDate><guid>http://www.cnitblog.com/tonywearme/archive/2006/09/17/16952.html</guid><wfw:comment>http://www.cnitblog.com/tonywearme/comments/16952.html</wfw:comment><comments>http://www.cnitblog.com/tonywearme/archive/2006/09/17/16952.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cnitblog.com/tonywearme/comments/commentRss/16952.html</wfw:commentRss><trackback:ping>http://www.cnitblog.com/tonywearme/services/trackbacks/16952.html</trackback:ping><description><![CDATA[
		<!--StartFragment --> 
<h1>Why you should learn the API before MFC</h1><h2>The Controversy</h2>Too many people come on to IRC and ask "What is better, MFC or API?" and too many people are willing to say "MFC sucks" or "API sucks" either because of traumatic events involving one or the other in early childhood, or because everyone else is saying it. 
<p>The standard arguments are: </p><ul><li>API is too hard </li><li>MFC is too confusing </li><li>API is too much code </li><li>MFC is bloated </li><li>API doesn't have wizards </li><li>MFC is badly designed </li><li>API isn't Object Oriented </li><li>MFC kicked my dog </li><li>API stole my girlfriend </li></ul>And so on... 
<h2>My Answer</h2>My opinion, although by no means the only one, is that you should use the right framework for the right job. 
<p>First of all a clarification on what the API and MFC are. API is a generic term meaning Application Programming Interface, however in the context of Windows programming, it means specifically the Windows API, which is the lowest level of interaction between applications and the windows operating system. Drivers of course have even lower levels, and different sets of function calls to work with, but for the vast majority of windows development this is not an issue. MFC is a <i>Class Library</i>, it's a bunch of C++ classes that have been written to reduce the amount of work it takes to do certain things with the API. It also introduces an (arguably) Object Oriented framework into the application that you can either take advantage of or ignore, which is what most beginners do since the framework isn't really aimed at writing MP3 players, IRC clients or games. </p><p>Every program, whether it is written with MFC, Delphi, Visual Basic, perl, or any other wacked out language or framework you can think of, is eventually built upon the API. In many cases this interaction is hidden, so you don't deal directly with the API, the runtime and support libraries do it for you. Some people ask, "MFC can do Blah Blah Blah, can the API?" The answer is that MFC can only do what the API can do, because it's built on top of it. However doing things yourself with the API may take considerably more code than using the pre-written MFC classes. </p><p>So what is the right framework? For starters, for people that are just learning to program, I strongly believe that you should work with the API untill you are comfortable with the way windows applications work and you understand all of the basic mechanics behind things like the message loop, GDI, controls, and maybe even multithreading and sockets. This way you will understand the fundamental building blocks of all windows applications, and can apply this common knowledge to MFC, Visual Basic, or whatever other framework you choose to work with later. It's also important because these other frameworks don't support everything that the API does, simply because it does a whole lot and they can't necessarily support all of the arcane little things that most people won't use. So when you finally do need to use them you need to add it yourself, you can't rely on the framework to do it for you and if you don't understand the API this could be quite the chore. </p><p>But isn't MFC easier? In a certain sense it's easier in that many common tasks are done for you, thus reducing the amount of code that you need to actually type. However, less code does not mean "easier" when you don't understand the code you DO need to write, or how all of the code that is there to support you actually works. Generally beginners who use the wizards to start there applications have no idea what most of the generated code does, and spend a great deal of time trying to figure out where to add things, or what changes to make to acheive a certain result. If you start your programs from scratch, either in the API or with MFC, then you know where everything is because you put it there, and you will only use features that you understand. </p><p>Another important factor is that most people that are learing the Win32 API for the first time don't already have a strong base in C++. To try and comprehend windows programming with MFC and learn C++ at the same time can be a monumental task. Although it's not impossible, it will take you considerably longer to become productive than if you already knew either C++ or the API. </p><h2>So basically...</h2>What it comes down to is that I think you should learn the API untill you feel comfortable with it, and then try out MFC. If it seems like it's making sense to you and saving you time, then by all means use it. 
<p><b>However, and this is important</b>... if you work with MFC without understanding the API and then ask for help with something, and the answer you get is stated using the api (such as "Use the HDC provided in the WM_CTLCOLORSTATIC message") and you say "huh?" because you don't know how to translate an API subject into MFC on your own, then you are in trouble and people will get frustrated with you for not learning what you need to know before you try and use MFC. </p><p>I personally prefer to work with the API, it just suits me better, but if I were to write a database frontend, or a host for a set of ActiveX controls I would seriously consider using MFC, as it would eliminate a lot of code that I would need to reinvent otherwise. </p><img src ="http://www.cnitblog.com/tonywearme/aggbug/16952.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cnitblog.com/tonywearme/" target="_blank">樱木</a> 2006-09-17 10:10 <a href="http://www.cnitblog.com/tonywearme/archive/2006/09/17/16952.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>计算机无法访问,您可能没有权限使用网络资源.请与这台服务器的管理员联系以查明您</title><link>http://www.cnitblog.com/tonywearme/archive/2006/09/16/16917.html</link><dc:creator>樱木</dc:creator><author>樱木</author><pubDate>Sat, 16 Sep 2006 02:21:00 GMT</pubDate><guid>http://www.cnitblog.com/tonywearme/archive/2006/09/16/16917.html</guid><wfw:comment>http://www.cnitblog.com/tonywearme/comments/16917.html</wfw:comment><comments>http://www.cnitblog.com/tonywearme/archive/2006/09/16/16917.html#Feedback</comments><slash:comments>1</slash:comments><wfw:commentRss>http://www.cnitblog.com/tonywearme/comments/commentRss/16917.html</wfw:commentRss><trackback:ping>http://www.cnitblog.com/tonywearme/services/trackbacks/16917.html</trackback:ping><description><![CDATA[
		<p>最近机器重装， 发现局域网上另一台机器上的打印机访问不了， 而其他人可以使用。 打开网上邻居， 点击“工组组计算机”， 弹出来错误框： <!--StartFragment --><b><font class="bt_16" color="#990000">计算机无法访问,您可能没有权限使用网络资源.请与这台服务器的管理员联系以查明您</font></b> 。 问题原因：瑞星防火墙关闭就可以正常添加网络打印机了。<br /><br />那么， 如何在不关闭瑞星防火墙（18.42）的情况下允许windows文件与打印机共享服务呢？ 到瑞星－》系统设置－》端口开关， 允许TCP 139， TCP445， UDP 137， UDP138四个端口即可。<br /><br /><!--StartFragment --> <b>基本原理</b><br />SMB(Server Message Block) Windows协议族，用于文件和打印共享服务。NBT(NetBIOS over TCP/IP) 使用137(UDP), 138(UDP) and 139 (TCP）来实现基于TCP/IP的NETBIOS网际互联。<br /><br />在Windows NT中SMB基于NBT实现。而在Windows2000中，SMB除了基于NBT的实现，还有直接通过445端口实现。当Win2000（允许NBT)作为client来连接SMB服务器时，它会同时尝试连接139和445端口，如果445端口有响应，那么就发送RST包给139端口断开连接，以455端口通讯来继续.当445端口无响应时，才使用139端口。当Win2000（禁止NBT)作为client来连接SMB 服务器时，那么它只会尝试连接445端口，如果无响应，那么连接失败。（注意可能对方是NT4.0服务器。） 如果win2000服务器允许NBT, 那么UDP端口137, 138, TCP 端口 139, 445将开放。 如果 NBT 被禁止, 那么只有445端口开放。 </p>
<img src ="http://www.cnitblog.com/tonywearme/aggbug/16917.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cnitblog.com/tonywearme/" target="_blank">樱木</a> 2006-09-16 10:21 <a href="http://www.cnitblog.com/tonywearme/archive/2006/09/16/16917.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>目标决定了你成功的高度！</title><link>http://www.cnitblog.com/tonywearme/archive/2006/09/10/16629.html</link><dc:creator>樱木</dc:creator><author>樱木</author><pubDate>Sun, 10 Sep 2006 12:36:00 GMT</pubDate><guid>http://www.cnitblog.com/tonywearme/archive/2006/09/10/16629.html</guid><wfw:comment>http://www.cnitblog.com/tonywearme/comments/16629.html</wfw:comment><comments>http://www.cnitblog.com/tonywearme/archive/2006/09/10/16629.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cnitblog.com/tonywearme/comments/commentRss/16629.html</wfw:commentRss><trackback:ping>http://www.cnitblog.com/tonywearme/services/trackbacks/16629.html</trackback:ping><description><![CDATA[
		<p>
				<font face="宋体">你今天站在哪个位置并不重要，但你下一步迈向哪却很关键。</font>
		</p>
		<p>
				<font face="宋体">　　不能延长生命的长度，但你可以增加生命的宽度。</font>
		</p>
		<p>
				<font face="宋体">　　重要的并不在于你现在的地位是多么卑微，或者从事的工作是多么地微不足道，只要你强烈地渴望攀登成功的巅峰并愿意为此付出艰辛的努力，那么总有一天你会喜笑颜开如愿以偿。</font>
		</p>
		<p>
				<font face="宋体">　　<strong><span style="COLOR: #333399; FONT-FAMILY: 宋体; mso-bidi-font-family: 宋体">有什么样的目标，就有什么样的人生。</span></strong></font>
		</p>
		<p>
				<font face="宋体">　　社会结构是一种金字塔状结构。大量的人处在金字塔的底部，只有一小部分人处在金字塔的顶部。处在底层的人们每天只能收支相抵，量入为出，只能现 挣现吃，仅够糊口。而处在顶尖的人则是蒸蒸日上，繁荣兴旺。每一个城市每一个公司，都是大多数人在底层，少数人在顶部，而处在顶部的人都是从底层逐渐上升的。</font>
		</p>
		<p>
				<font face="宋体">　　<strong><span style="COLOR: #333399; FONT-FAMILY: 宋体; mso-bidi-font-family: 宋体">为什么偏偏是他们达到了众人瞩目的高度呢？</span></strong></font>
		</p>
		<p>
				<font face="宋体">　　上帝对每个人都是公平的，希尔顿、洛克菲勒并不比你拥有的时间多一秒钟，但为什么只有他们取得了令人瞩目的成就？问题的关键就在于你没有人生的高度。</font>
		</p>
		<p>
				<font face="宋体">　　绝大多数人之所以平庸一生，之所以只能在历史的舞台上扮演无足轻重的次要角色<span lang="EN-US">——</span>包括那些懒惰闲散的人、好逸恶劳的人、平庸无奇的人<span lang="EN-US">——</span>原因就是他们缺乏内在的动力。</font>
		</p>
		<p>
				<font face="宋体">　　哈佛大学曾做过一个著名的实验。</font>
		</p>
		<p>
				<font face="宋体">　　在一群智力与年龄都相近的青年中进行了一次关于人生目标的调查，结果发现：</font>
		</p>
		<p>
				<font face="宋体">　　<span lang="EN-US">3%</span>的人有十分清晰的长远目标；</font>
		</p>
		<p>
				<font face="宋体">　　<span lang="EN-US">10%</span>的人有清晰但比较短期的目标；</font>
		</p>
		<p>
				<font face="宋体">　　<span lang="EN-US">60%</span>的人只有一些模糊的目标；</font>
		</p>
		<p>
				<font face="宋体">　　<span lang="EN-US">27%</span>的人根本没有目标。</font>
		</p>
		<p>
				<font face="宋体">　　<span lang="EN-US">25</span>年后，哈佛大学再次对他们做了跟踪调查，结果令人十分吃惊！</font>
		</p>
		<p>
				<font face="宋体">　　那<span lang="EN-US">3%</span>的人全部成了社会各界的精英，行业领袖；</font>
		</p>
		<p>
				<font face="宋体">　　那<span lang="EN-US">10%</span>的人都是各专业各领域的成功人士，生活在社会的中上层，事业有成；</font>
		</p>
		<p>
				<font face="宋体">　　那<span lang="EN-US">60%</span>的人大部分生活在社会中下层，胸无大志，事业平平；</font>
		</p>
		<p>
				<font face="宋体">　　那<span lang="EN-US">27%</span>的人过得很不如意，工作不稳定，入不敷出，常常抱怨社会，抱怨政府，怨天尤人。</font>
		</p>
		<p>
				<font face="宋体">　　在我们的周围这样的人比比皆是，这些人私下里认为自己很聪明，他们满足于混日子，敷衍了事，混水摸鱼，过一天算一天，日复一日年复一年浪费自己 宝贵的青春、生命、大好前程；他不知道自己所做的蹩脚的工作，对老板的损害不及对自身损害的一半。对于老板而言，这可能会是几个美元的损失，但对他自身来说，这却是人格和自尊的丧失，是做人的丧失。</font>
		</p>
		<p>
				<font face="宋体">　　回溯历史，我们不难发现，每一个伟大的建树每一项杰出的成就都是由那些志向高远的人所创造的，不论是像爱迪生、福特、贝尔、莱特兄弟这样的发明 家，还是像马丁<span lang="EN-US">·</span>路德<span lang="EN-US">·</span>金以及从囚徒成为南非总统的纳尔逊<span lang="EN-US">·</span>曼德拉这样的社会改革家。他们拒绝接受中庸之道，他们追求卓越，所以他们功成名就，这就是精华法则：最优秀的将会上升到金字塔的顶部。</font>
		</p>
		<p>
				<font face="宋体">　　对于年轻人来说，不管现在他多么贫穷或者多么笨拙，只要他有着积极进取的心态和更上一层楼的决心，我们就不应该对他失去信心。对于一个渴望着在 这个世界上立身扬名、成就一番事业的人来说，任何东西都不是他前进的障碍。不管他所处的环境是多么地恶劣，也不管他面临艰难险阻，他总是能通过内心的力量驱动自己，脱颖而出，勇往直前。我们不可能阻挡一个林肯一样、威尔逊一样、或者希尔顿一样的人物的崛起。对于这样的一些人来说，即便是贫穷到买不起书本的 地步，他们依旧可以通过借阅而获得梦寐以求的知识，即使处于卑微的境地，他们也从不放弃梦想。他们即使一次次失败，也从不放弃努力。他们就是拥有<span lang="EN-US">“</span>自驱 力<span lang="EN-US">”</span>的人。</font>
		</p>
		<p>
				<font face="宋体">　　你或许会认为自己太差劲，能成就一番事业的机会和概率微乎其微，但是，问题的关键并不在于你现在的地位是多么地卑微或者从事的工作是多么地微不 足道，只要你有强烈的进取心，只要你不局限于狭小的圈子，只要你渴望着有朝一日成为万众瞩目的人物，只要你希冀着攀登上成功的颠峰并愿意为此付出切实有效的努力，那么任何障碍都阻挡不了你成功的步伐。正如胚芽通过力量的积蓄最终钻出地面一样，竹子需要在地下长四年长到地上然后每年快于一年，你也将通过持之 以恒的努力逐渐地远离平庸，拥有辉煌而壮丽的人生。</font>
		</p>
		<p>
				<font face="宋体">　　我们不应该根据人们现在从事的工作来对他进行评判，在确切地了解一个人的理想和抱负之前，无法对一个人轻易地下结论。判断一个人的标准应该是看 他所拥有的抱负和确立的目标。一个年轻人，只要他具备毅力、恒心和信念，他完全有可能成为一个杰出人物。在一个人的日常活动中，我们可以发现某些预示着他的未来的东西。他做事的风格，他对工作的投入程度，他的言行举止<span lang="EN-US">——</span>所有的一切都预示着他会拥有什么样的未来。当我们看到一个工作兢兢业业，想方设法地使每一件事都做得尽善尽美，以自己的努力和成就为荣，并在此基础上积极寻求进一步的发展和提高的人时，我相信他总有一天会崭露头角。</font>
		</p>
		<p>
				<font face="宋体">　　洛杉矶郊区有个年仅<span lang="EN-US">15</span>岁的孩子，拟了一个题为《一生的志愿》的表格，其中包括：</font>
		</p>
		<p>
				<font face="宋体">　　<span lang="EN-US">“</span>到尼罗河、亚马逊河和刚果河探险；登上珠穆朗玛峰、乞力马扎罗山和麦特荷恩山；驾驭大象、骆驼、鸵鸟和野马；探访马可<span lang="EN-US">·</span>波罗和亚历山大一世走 过的路；主演一部像<span lang="EN-US">‘</span>人猿泰山<span lang="EN-US">’</span>那样的电影；驾驶飞行器起飞降落；读完莎士比亚、柏拉图和亚里士多德的著作；谱一部乐谱；写一本书；游览全世界的每一个国 家；结婚生孩子；参观月球<span lang="EN-US">……”</span></font>
		</p>
		<p>
				<font face="宋体">　　他把每一项编了号，共有<span lang="EN-US">127</span>个目标。</font>
		</p>
		<p>
				<font face="宋体">　　当把梦想庄严地写在纸上之后，他开始循序渐进地实行。</font>
		</p>
		<p>
				<font face="宋体">　　<span lang="EN-US">16</span>岁那年，他和父亲到佐治亚洲的奥克费诺基大沼泽和佛罗里达州的埃弗洛莱兹探险。</font>
				<span lang="EN-US">
						<br />
				</span>
				<font face="宋体">　</font>
				<span lang="EN-US">
						<br />
				</span>
				<font face="宋体">　　他按计划逐个地实现了自己的目标，<span lang="EN-US"> 49</span>岁时，他完成了<span lang="EN-US">127</span>个目标中的<span lang="EN-US">106</span>个。这个美国人叫约翰<span lang="EN-US">·</span>戈达德，获得了一个探险家所能享有的一切荣誉。他集腋成裘、不辞艰苦地努力实现包括游览长城<span lang="EN-US">(</span>第<span lang="EN-US">40</span>号<span lang="EN-US">)</span>及参观月球<span lang="EN-US">(</span>第<span lang="EN-US">125</span>号<span lang="EN-US">)</span>等目标。如果你也能像他一样，从小拥有远大的抱负，有一天，你也会发现自己是那个走得最远的人<span lang="EN-US">!</span></font>
		</p>
		<p>
				<font face="宋体">　　当年轻的希尔顿在希尔顿酒店当服务员时，酒店的高层领导已经预测到了，即便希尔顿现在仅仅是一个普通的清洁工，但这个年轻人必定前程无限，因为 他是如此全身心地投入工作，如此地乐观自信，如此强烈地渴望大展宏图。他经手的每一件事都能做到尽善尽美，这些都预示和象征着他未来作为的不可限量。</font>
		</p>
		<p>
				<font face="宋体">　　事实证明他的确是做到了这一点。<span lang="EN-US"></span></font>
		</p>
		<p class="MsoNormal" style="MARGIN: 0cm 0cm 0pt">
				<span lang="EN-US">
						<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" /?>
						<o:p> </o:p>
				</span>
		</p>
<img src ="http://www.cnitblog.com/tonywearme/aggbug/16629.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cnitblog.com/tonywearme/" target="_blank">樱木</a> 2006-09-10 20:36 <a href="http://www.cnitblog.com/tonywearme/archive/2006/09/10/16629.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>证明: C++中的友元运算符函数operator@不能属于任何类</title><link>http://www.cnitblog.com/tonywearme/archive/2006/09/08/16551.html</link><dc:creator>樱木</dc:creator><author>樱木</author><pubDate>Fri, 08 Sep 2006 13:37:00 GMT</pubDate><guid>http://www.cnitblog.com/tonywearme/archive/2006/09/08/16551.html</guid><wfw:comment>http://www.cnitblog.com/tonywearme/comments/16551.html</wfw:comment><comments>http://www.cnitblog.com/tonywearme/archive/2006/09/08/16551.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cnitblog.com/tonywearme/comments/commentRss/16551.html</wfw:commentRss><trackback:ping>http://www.cnitblog.com/tonywearme/services/trackbacks/16551.html</trackback:ping><description><![CDATA[证明: C++中的友元运算符函数operator@不能属于任何类, 也就是说该友元不能是友元成员.<br /><br />proof:<br /><br /><p class="MsoNormal" style="MARGIN: 0cm 0cm 0pt"><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">友元运算符函数只能是一般的类外部友元函数</span><span lang="EN-US">, </span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">而不能是属于某个类的友元成员函数</span><span lang="EN-US">. </span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">如果</span><span lang="EN-US">operator@</span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">是</span><span lang="EN-US">A</span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">类的成员函数</span><span lang="EN-US">, </span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">同时又是</span><span lang="EN-US">B</span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">类的友元</span><span lang="EN-US">, </span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">假设</span><span lang="EN-US">@</span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">是</span><span lang="EN-US">m</span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">目运算符</span><span lang="EN-US">, </span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">则</span><span lang="EN-US">A</span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">类要求</span><span lang="EN-US">operator@</span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">只带有</span><span lang="EN-US">n-1</span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">个参数</span><span lang="EN-US">. </span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">但同时作为</span><span lang="EN-US">B</span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">类的友元</span><span lang="EN-US">, B</span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">类要求</span><span lang="EN-US">operator@</span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">带有</span><span lang="EN-US">n</span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">个参数</span><span lang="EN-US">(</span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">因为没有</span><span lang="EN-US">B</span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">类的</span><span lang="EN-US">this</span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">指针</span><span lang="EN-US">), </span><span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">由此矛盾</span><span lang="EN-US">.<br /><br /><br />哇哈哈, 竟然证明C++的语言特性, 这倒是第一次, 值得留念!</span></p><img src ="http://www.cnitblog.com/tonywearme/aggbug/16551.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cnitblog.com/tonywearme/" target="_blank">樱木</a> 2006-09-08 21:37 <a href="http://www.cnitblog.com/tonywearme/archive/2006/09/08/16551.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>VC里面模板类定义的位置</title><link>http://www.cnitblog.com/tonywearme/archive/2006/09/04/16364.html</link><dc:creator>樱木</dc:creator><author>樱木</author><pubDate>Mon, 04 Sep 2006 14:43:00 GMT</pubDate><guid>http://www.cnitblog.com/tonywearme/archive/2006/09/04/16364.html</guid><wfw:comment>http://www.cnitblog.com/tonywearme/comments/16364.html</wfw:comment><comments>http://www.cnitblog.com/tonywearme/archive/2006/09/04/16364.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cnitblog.com/tonywearme/comments/commentRss/16364.html</wfw:commentRss><trackback:ping>http://www.cnitblog.com/tonywearme/services/trackbacks/16364.html</trackback:ping><description><![CDATA[今天用类模板写了一个可扩展空间的栈. compile没问题, 一run就发现报链接错误, 说几个类的成员函数都找不到:<br />error LNK2001: unresolved external symbol ****. 检查了一下, 发现和以前写的没什么两样啊, 后来才发现原来所有的函数定义及实现都是放在一个.h中, 现在遵循良好的设计规范, 把类定义放在.h中, 类的实现放在.cpp中反而出错了?? 晕!<br /><br />网上查了一点资料, 发现VC6好像是不支持分开写的, (不是模板当然可以!), 无论是类模板还是函数模板, 都必须写在一个.h文件中. 有人可能会说那么这个包含方法实现的头文件如果多个其他文件include它, 那不是就有问题了么? 要不要#pragma once呀, 这里明确告诉你, 不用的. &lt;&lt;Thinking in C++&gt;&gt;里面说, 因为类模板的.h文件和普通类的.h文件在编译器处理的时候好像是有区别的. 原因自己去看书吧, 不过书里说得不多,我也忘记啦.<img src ="http://www.cnitblog.com/tonywearme/aggbug/16364.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cnitblog.com/tonywearme/" target="_blank">樱木</a> 2006-09-04 22:43 <a href="http://www.cnitblog.com/tonywearme/archive/2006/09/04/16364.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>随便加入MainFrm.h可以么?</title><link>http://www.cnitblog.com/tonywearme/archive/2006/09/04/16363.html</link><dc:creator>樱木</dc:creator><author>樱木</author><pubDate>Mon, 04 Sep 2006 14:27:00 GMT</pubDate><guid>http://www.cnitblog.com/tonywearme/archive/2006/09/04/16363.html</guid><wfw:comment>http://www.cnitblog.com/tonywearme/comments/16363.html</wfw:comment><comments>http://www.cnitblog.com/tonywearme/archive/2006/09/04/16363.html#Feedback</comments><slash:comments>1</slash:comments><wfw:commentRss>http://www.cnitblog.com/tonywearme/comments/commentRss/16363.html</wfw:commentRss><trackback:ping>http://www.cnitblog.com/tonywearme/services/trackbacks/16363.html</trackback:ping><description><![CDATA[今天实验室的一位师弟向我请教一个问题, 说加了一个类(一个.h和.cpp)后出来了莫名奇妙的n多编译错误, 由于要访问主窗口中的某些对象, 他在新加的头文件中包含了MFC的MainFrm.h文件. 还好MFC没有忘记很多, 在#include&lt;MainFrm.h&gt;前加了include&lt;stdafx.h&gt;就行了.  轻松搞定,呵呵~<img src ="http://www.cnitblog.com/tonywearme/aggbug/16363.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cnitblog.com/tonywearme/" target="_blank">樱木</a> 2006-09-04 22:27 <a href="http://www.cnitblog.com/tonywearme/archive/2006/09/04/16363.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>关于Web页面的一些小知识</title><link>http://www.cnitblog.com/tonywearme/archive/2006/09/02/16299.html</link><dc:creator>樱木</dc:creator><author>樱木</author><pubDate>Sat, 02 Sep 2006 08:00:00 GMT</pubDate><guid>http://www.cnitblog.com/tonywearme/archive/2006/09/02/16299.html</guid><wfw:comment>http://www.cnitblog.com/tonywearme/comments/16299.html</wfw:comment><comments>http://www.cnitblog.com/tonywearme/archive/2006/09/02/16299.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cnitblog.com/tonywearme/comments/commentRss/16299.html</wfw:commentRss><trackback:ping>http://www.cnitblog.com/tonywearme/services/trackbacks/16299.html</trackback:ping><description><![CDATA[静态Web页面的工作原理<br />
1) Web页面的创建者编写由纯HTML组成的Web页面, 并将其保存到服务器上.<br />
2) 用户在其浏览器中输入了Web页面请求, 该请求就从浏览器传递到Web服务器.<br />
3) Web服务器定位.htm文件并将它转换为HTML流.<br />
4) 浏览器处理HTML并显示该页面.<br /><br />
优点: 静态页面的处理速度非常之快<br />
缺点: 页面的内容在用户请求页面之前就已经完全确定了. 因此不同的用户在不同的时间通过不同的方式访问得到的页面都是相同的. 而且没有安全性, 任何人都可以查看源代码.<br /><br />
Web服务器是一种软件, 用于管理Web页面, 处理用户的访问页面请求.<br />
Apache, IIS, Enterprise<br /><br />
提供动态Web页面的两种方法:<br />
1) 客户端生成技术: 由浏览器上的插件完成创建动态页面的全部工作. Web服务器将HTML和生成HTML的指令通过网络发送到客户端浏览器, 浏览器利用这些指令为页面生成纯HTML<br />
缺点: 包含指令的文件(html或单独的指令文件)下载时间很长; 各浏览器对指令的解释可能不同; 由于代码是在客户端解释的, 使用服务器端资源(如database)的客户端代码不安全.<br /><br />
客户端脚本语言:<br />
JavaScript: Netscape开发, 基于Java, 但与Java不同<br />
JScript: Microsoft自己版本的JavaScript<br />
VBScript: Microsoft开发, 基于VB, 通用性很差, 只有IE支持. 当页面只在内部网访问且客户机器都是Windows上的IE时才考虑使用.<br />
考虑到安全性, 脚本语言的功能有所限制<br /><br />
Java Applet: 浏览器从服务器下载Java文件, 并利用内置于浏览器的JVM执行它.<br />
比较安全(Sandbox:沙箱)<br /><br />
Flash: Macromedia开发<br /><br />
2) 服务器端生成技术: 所有的指令处理过程都是在服务器上完成,只有HTML代码和客户端脚本传回给浏览器. ASP.NET当然属于此类.<br /><br />
CGI: 公共网关接口. 工作方式与ASP/ASP.NET不同. CGI允许用户调用Web服务器上的另一个程序来创建动态Web页面, 且CGI的作用是将用户提供的数据传递给该程序以进行处理. CGI可以运行与许多不同的平台.<br />
缺点: 学要许多服务器资源, 增加了额外开销.<br /><br />
ASP: 仅局限于使用脚本语言(主要是JavaScript或VBScript), 它在Web服务器上处理JavaScript或VBScript, 然后在将它们发送到浏览器之前将其转换成HTML, 而不是在浏览器上. 只有IIS支持. <br /><br />
JSP: 代码在不同服务器间的兼容性. 运行速度比ASP快.<br />
CodeFusion: 非免费<br />
PHP: 超文本预处理程序(HyperText Preprocessor)<img src ="http://www.cnitblog.com/tonywearme/aggbug/16299.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cnitblog.com/tonywearme/" target="_blank">樱木</a> 2006-09-02 16:00 <a href="http://www.cnitblog.com/tonywearme/archive/2006/09/02/16299.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>折半插入排序的实现</title><link>http://www.cnitblog.com/tonywearme/archive/2006/09/01/16259.html</link><dc:creator>樱木</dc:creator><author>樱木</author><pubDate>Fri, 01 Sep 2006 08:22:00 GMT</pubDate><guid>http://www.cnitblog.com/tonywearme/archive/2006/09/01/16259.html</guid><wfw:comment>http://www.cnitblog.com/tonywearme/comments/16259.html</wfw:comment><comments>http://www.cnitblog.com/tonywearme/archive/2006/09/01/16259.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cnitblog.com/tonywearme/comments/commentRss/16259.html</wfw:commentRss><trackback:ping>http://www.cnitblog.com/tonywearme/services/trackbacks/16259.html</trackback:ping><description><![CDATA[
		<p>template&lt;typename T&gt;<br />void insertion_sort( T * t, const int &amp; size )<br />{<br /> int key,<br />  i, j,<br />  low, high, mid;<br />  <br /> for( i=1; i&lt;size; i++ )<br /> {<br />  if( t[i] &lt; t[i-1] )<br />  {<br />   low = 0;<br />   high = i-1;<br />   key = t[i];<br />   while( low &lt;= high )<br />   {<br />    mid = (low+high)/2;<br />    <br />    if( key &lt; t[mid] )<br />     high = mid - 1;<br />    else<br />     low = mid + 1;    <br />   }   <br />   for( j=i; j&gt;high+1; j-- )<br />    t[j] = t[j-1];<br />   t[high+1] = key;<br />  }<br /> }<br />}</p>
		<p>// 保持稳定性要求折半查找返回最后相等的关键字的位置或其右边<br />// high+1: 插入的位置<br /><br />分析:<br />由于折半插入排序和直接插入排序相比, 仅减少了关键字比较的次数, 而记录移动次数不变. 其时间复杂度仍为O(n^2).  而且它查找和移动不是在同一个迭代中完成的. 所以只有当n较大时其性能才略优于直接插入排序.</p>
<img src ="http://www.cnitblog.com/tonywearme/aggbug/16259.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cnitblog.com/tonywearme/" target="_blank">樱木</a> 2006-09-01 16:22 <a href="http://www.cnitblog.com/tonywearme/archive/2006/09/01/16259.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>直接插入排序的链表实现</title><link>http://www.cnitblog.com/tonywearme/archive/2006/09/01/16258.html</link><dc:creator>樱木</dc:creator><author>樱木</author><pubDate>Fri, 01 Sep 2006 07:00:00 GMT</pubDate><guid>http://www.cnitblog.com/tonywearme/archive/2006/09/01/16258.html</guid><wfw:comment>http://www.cnitblog.com/tonywearme/comments/16258.html</wfw:comment><comments>http://www.cnitblog.com/tonywearme/archive/2006/09/01/16258.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cnitblog.com/tonywearme/comments/commentRss/16258.html</wfw:commentRss><trackback:ping>http://www.cnitblog.com/tonywearme/services/trackbacks/16258.html</trackback:ping><description><![CDATA[template&lt;class T&gt;<br />void insertion_sort( node&lt;T&gt; * &amp; head )//<br />{<br /> node&lt;T&gt; * first_unsorted,<br />      * last_sorted,<br />   * insert,<br />   * insertPre;<br /> if( head )<br /> {<br />  last_sorted = head;  <br />  while( last_sorted-&gt;next )<br />  {<br />   first_unsorted = last_sorted-&gt;next;<br />   if( first_unsorted-&gt;key &lt; last_sorted-&gt;key )<br />   {<br />    insert = head;   <br />    while( first_unsorted-&gt;key&gt;=insert-&gt;key ) //从前到后, 保持稳定<br />    {<br />     insertPre = insert;<br />     insert = insert-&gt;next;<br />    }    <br />    if( insert == head )<br />    {<br />     last_sorted-&gt;next = first_unsorted-&gt;next;//<br />     first_unsorted-&gt;next = head;<br />     head = first_unsorted;       <br />    }<br />    else<br />    {     <br />     last_sorted-&gt;next = first_unsorted-&gt;next;<br />     first_unsorted-&gt;next = insert;<br />     insertPre-&gt;next = first_unsorted;<br />    }    <br />   }<br />      else<br />    last_sorted = first_unsorted;//   <br />  } <br /> }<br />}<br />说明:<br />1) 插入之前不需要移动元素, 所以不需要从后往前查找. <br />2) 保持算法的稳定性.<br />3) 函数参数必须是指针的引用!<br /><img src ="http://www.cnitblog.com/tonywearme/aggbug/16258.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cnitblog.com/tonywearme/" target="_blank">樱木</a> 2006-09-01 15:00 <a href="http://www.cnitblog.com/tonywearme/archive/2006/09/01/16258.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>请编写一个正确的二分搜索算法？！</title><link>http://www.cnitblog.com/tonywearme/archive/2006/08/30/16180.html</link><dc:creator>樱木</dc:creator><author>樱木</author><pubDate>Wed, 30 Aug 2006 15:24:00 GMT</pubDate><guid>http://www.cnitblog.com/tonywearme/archive/2006/08/30/16180.html</guid><wfw:comment>http://www.cnitblog.com/tonywearme/comments/16180.html</wfw:comment><comments>http://www.cnitblog.com/tonywearme/archive/2006/08/30/16180.html#Feedback</comments><slash:comments>1</slash:comments><wfw:commentRss>http://www.cnitblog.com/tonywearme/comments/commentRss/16180.html</wfw:commentRss><trackback:ping>http://www.cnitblog.com/tonywearme/services/trackbacks/16180.html</trackback:ping><description><![CDATA[
		<p>本文是《数据结构与程序设计（c++语言描述）》中关于二分搜索的学习笔记，二分搜索的思想很简单，但是要实现一个正确最优的算法确不是那么容易。第一个二分搜索算法于1946年就出现，然而第一个完全正确的二分搜索算法直到1962年才出现，所以，认真点＋留神点～ ^_^<br /><br />首先，介绍一下二分搜索的思想：对于一个有序表而言，要查找某个关键字，首先比较表中央的那个节点，如果该节点的关键字与目标关键字相同，则找到。若比目标小，则目标关键字肯定出现在该点的右半段内。反之则出现在左半段。这样，每次比较后就能丢去一半的节点，对于一般的有序线性表而言，其搜索效率大大高于顺序查找。<br /><br /><font color="#ff0000">第一个版本的二分搜索：</font><br />根据算法，我们设置三个位置指示器：low, high, mid，分别指向当前搜索范围的最低位置、最高位置和中间位置，中间位置由mid = (low+high)/2决定。首先将mid处的关键字与key比较，相同则返回mid；若key较大，令low＝mid＋1继续搜索右半段；若key较小，令high＝mid－1继续搜索左半段。这样，搜索范围不断减小，high－low也越来越小。当high-low&lt;0时算法由于没有找到key而终止。<br /><br />///////////////////////////////////程序实现///////////////////////////////////////////<br />//第一个版本的递归实现（binary_search_v1_recursion）<br />template&lt;class Record, class Key&gt;<br />int binary_search( Record * r, const int &amp; low, const int &amp; high, const Key &amp; k )<br />{<br /> int mid = ( low + high ) / 2;<br /> if( low &lt;= high )<br /> {<br />  if( r[mid] == k )<br />   return mid;<br />  else if( r[mid] &lt; k )<br />   return binary_search( r, mid+1, high, k );<br />  else<br />   return binary_search( r, low, mid-1, k );<br /> }<br /> else<br />  return -1;<br />}<br /><br />//第一个版本的迭代实现（binary_search_v1_iteration）<br />template&lt;class Record, class Key&gt;<br />int binary_search( Record * r, const int &amp; size, const Key &amp; k )<br />{<br /> int low=0, high=size-1, mid;<br /> while( low &lt;= high )<br /> {<br />  mid = (low + high)/2;<br />  if( r[mid] == k )<br />   return mid;<br />  else if( r[mid] &lt; k )<br />   low = mid + 1;<br />  else<br />   high = mid -1;<br /> }<br /> return -1;<br />}<br /><br />在这个版本中，由于&gt;，&lt;符号的使用，搜索的范围始终控制在[low, high]之间，在0～low－1之间的一定小于关键字，在high＋1～size－1之间的一定大于关键字。当找到一个关键字时退出循环算法结束（成功）。考虑一下如果一张有序表中有多个重复关键字怎么办呢？一般的习惯是返回第一个的序号，然而此版本的算法只是返回随机的一个位置。这是一个问题。<br /><br />///////////////////////////////////复杂度分析///////////////////////////////////////////<br />接下来分析一下和目标关键字k的比较次数。在分析用关键字比较次数来作为算法时间复杂性度量的这一类查找算法时，比较树（comparison tree）是很有用的一种方法。在此介绍两种类型的比较树（当然是和算法有关），它们都符合2－树的定义。所谓2－树就是树中的节点要么是叶子节点要么有两个儿子节点（注意：2－树不是二叉树，前者的条件更强些）。二叉树相信大家已经非常熟悉了，所以这里直接拿出它的两个引理而不加证明：<br />1）第i层上最多有2^i个节点（0&lt;=i&lt;&lt;h=树深度）。<br />2）高度为h的一棵二叉树最多有（2^h）-1个节点，节点最多时为满二叉树。<br /><br />易验证这里的比较树都是2－树，而2－树是条件更强的二叉树，自然满足1）、2）。<br />此算法的的比较树如下（size＝10）：<br /><img src="D:\Documents and Settings\zj\桌面\searchTree1.jpg" /><br />在这棵查找树中，内部节点（i）表示一次查找成功，外部（叶子F）节点表示一次查找失败，形象一点的话可以说查找成功的情况分布在树冠（树的上部）查找失败的情况树的底层或次底层（可用数学归纳法证明，从略啦）。在证明过程中需要特别注意的是若是查找成功，成功节点的祖先（在比较路径上从root（第0层）到成功节点的父亲）各比较了两次！而成功节点自身则比较了一次。失败的话自然路径上的每个内部节点都比较了两次。另外注意内部节点有n个，外部节点有n＋1个（n表示有序表大小）。<br /><br />查找失败：<br />查找失败时的比较次数与树的深度密切相关。假设深度h，则F节点分布在h层或h和h－1层。由于h－1层上非F节点都会在h层产生两个F节点，因此：2^(h-1) &lt; n+1 &lt;= 2^h 。所以树深度h= <span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">┌</span></span>lg(n+1)<span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">┐（以2为底）。所以平均情况和最坏情况下查找失败的比较次数是2×<span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">┌</span></span><font size="3">lg(n+1)</font><span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">┐。<br /></span></span><br />查找成功：<br />首先引入2－树的引理：对于任何一个2－树而言（二叉树就没有这个定理！），外部路径总长度E＝内部路径总长度I＋内部节点个数q×2。可以用数学归纳法证明，不是很难，从略。E<span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">≈(n+1)<span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">┌</span></span><font size="3">lg(n+1)</font><span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">┐ <span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">∴I＝<span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">(n+1)<span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">┌</span></span><font size="3">lg(n+1)</font><span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">┐－2n 。平均内部路径长度＋1表示平均比较的节点数，故:<br /></span></span></span></span></span>（I/n＋1）×2－1＝2（n＋1）<span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">┌</span></span><font face="宋体"><font size="3">lg(n+1)</font><span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">┐/n－3就是成功查找的平均查找长度。其中×2表示每个节点都比较2次（除了最后一个节点），最后的减1也就是减去那个多算的1次比较。<br /></span></font>另外一种求法是从上到下计算每一层的比较次数然后相加，这是国内很多教材选用的方法，比较直接且麻烦，偶不喜欢～。<br />查找成功时的最坏情况当然是树的深度减1：<span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">┌</span></span><font face="宋体"><font size="3">lg(n+1)</font><span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">┐－1 。<br /></span></font><br /><font color="#ff0000">第一个版本的二分搜索：<br /></font>前面一个版本二分搜索特点是当找到一个成功情况时就退出，这样对于具有多个相同关键字的有序表来说就不太适合了，最好返回这些相同关键字的第一个的位置而不是随便一个。由此引出了下面的改进算法：当mid处的关键字等于k时，算法并不马上结束，因为mid之前可能还有相同的关键字，也就是说第一个关键字的位置&lt;=mid，所以令high=mid。那么这个算法结束的条件是什么呢？这个是关键。当low或high中的任何一个先指向第一个k关键字时，在接下来的迭代过程中该指针将保持不变，另一个指针会不断向它靠近直到high＝low。也就是说high＝low是查找成功的必要条件，可见：（high＝low）&amp;&amp;（mid处关键字＝k）就是查找成功的充分条件。查找失败有两种可能：<br />1）（high＝low））&amp;&amp;（mid处关键字<span style="FONT-FAMILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">≠</span>k）<br />2）low &gt; high<br /><br />///////////////////////////////////程序实现///////////////////////////////////////////<br />//第二个版本的递归实现（binary_search_v2_recursion）<br />template&lt;class Record, class Key&gt;<br />int binary_search( Record * r, const int &amp; low, const int &amp; high, const Key &amp; k )<br />{<br /> int mid = (low + high)/2;<br /> if( low &lt; high )<br /> {<br />  if( k &lt;= r[mid] )<br />   binary_search( r, low, mid, k );  <br />  else<br />   binary_search( r, mid+1, high, k );<br /> }<br /> else if( low == high )<br /> {<br />  if( k == r[mid] )<br />   return low;<br />  else<br />   return -1;<br /> }<br /> else<br />  return -1;<br />}<br /><br />//第二个版本的迭代实现（binary_search_v2_iteration）<br />template&lt;typename Record, typename Key&gt;<br />int binary_search( Record * r, const int &amp; size, const Key &amp; k )<br />{<br /> int low=0, high=size-1, mid;<br /> while( low &lt; high )<br /> {<br />  mid = (low + high) / 2;<br />  if( k &gt; r[mid] )<br />   low = mid + 1;<br />  else<br />   high = mid;<br /> }<br /> if( low &gt; high )<br />  return -1;<br /> else<br /> {<br />  if( k == r[low] )<br />   return low;<br />  else<br />   return -1;<br /> }<br />}<br /><br />///////////////////////////////////复杂度分析///////////////////////////////////////////<br />由于成功和失败的判断一定要走到最后一步才能确定，所以成功和失败的情况都是在2－树的叶子（外部）节点反之亦然。而这些外部节点总数为2n（n为有序表大小），所以比较树的深度h＝<span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">┌</span></span><font face="宋体"><font size="3">lg(2n）</font><span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">┐＝<span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">┌</span></span><font size="3">lgn</font><span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">┐＋1 。由于2－树叶子节点层数最多相差1，所以查找成功/查找失败时的平均比较次数和最坏比较次数均<span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">≈<span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">┌</span></span><font size="3">lgn</font><span style="FONT-SIZE: 10.5pt; FONT-FAMILY: 宋体; mso-bidi-font-size: 12.0pt; mso-bidi-font-family: 'Times New Roman'; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">┐＋1 。算法2的比较树如下（n＝10）：<br /></span></span></span></span></font><img src="D:\Documents and Settings\zj\桌面\searchTree2.JPG" /><br />由此得出结论，虽然算法1和算法2的时间复杂度是一个级别，但是当n较大时，算法2要比算法1快1倍！虽然从表面看算法1在某些情况下（树顶的那些成功节点）的确比算法2先结束，但是它只是对处于搜索树上部的一些为数不多的节点来说是早结束，而付出的代价却是每个节点比较2次。n较小的时候可能算法1稍微快点，但是此时的n非常小（比较对数曲线）以至于采用顺序查找会比二分算法1更好。由此我们得出结论如下：<br />对于较大的有序表，采用二分搜索算法2最快。<br />对于较小的有序表，采用顺序搜索就可以啦。<br /><br />当然了，实际上由于算法1的两次比较都是相同两个数之间的比较，所以对于某些优化的编译器来说，可能实际的比较时间比两次独立的比较所需的时间要少（比如重复访问的数据直接从cache而不是从ram中读。。。etc）。<br /><br />呵呵，写到这里终于结束啦。各位各位，如果将来面试的时候考官叫你写个二分搜索算法，你会写哪个呀？要想起我哦，呵呵～ <br /><br /></p>
<img src ="http://www.cnitblog.com/tonywearme/aggbug/16180.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cnitblog.com/tonywearme/" target="_blank">樱木</a> 2006-08-30 23:24 <a href="http://www.cnitblog.com/tonywearme/archive/2006/08/30/16180.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item></channel></rss>