??xml version="1.0" encoding="utf-8" standalone="yes"?>嫩草影院久久99,色偷偷88欧美精品久久久,久久国产精品99国产精http://www.shnenglu.com/yuqilin1228/There is a way...zh-cnThu, 08 May 2025 21:50:52 GMTThu, 08 May 2025 21:50:52 GMT60Windows Live Writer 发布博客(cppBlog,cnblogs)http://www.shnenglu.com/yuqilin1228/archive/2011/08/23/154095.htmlLynnRaymondLynnRaymondMon, 22 Aug 2011 18:06:00 GMThttp://www.shnenglu.com/yuqilin1228/archive/2011/08/23/154095.htmlhttp://www.shnenglu.com/yuqilin1228/comments/154095.htmlhttp://www.shnenglu.com/yuqilin1228/archive/2011/08/23/154095.html#Feedback0http://www.shnenglu.com/yuqilin1228/comments/commentRss/154095.htmlhttp://www.shnenglu.com/yuqilin1228/services/trackbacks/154095.html阅读全文

LynnRaymond 2011-08-23 02:06 发表评论
]]>
【设计实cThe Practice of Programming 01http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110628.htmlLynnRaymondLynnRaymondFri, 26 Mar 2010 15:39:00 GMThttp://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110628.htmlhttp://www.shnenglu.com/yuqilin1228/comments/110628.htmlhttp://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110628.html#Feedback0http://www.shnenglu.com/yuqilin1228/comments/commentRss/110628.htmlhttp://www.shnenglu.com/yuqilin1228/services/trackbacks/110628.htmlThe Practice of Programming - Chapter 1 Style

1.1  Names

       A name should be informative, concise, memorable, and pronounceable if possible.

   

* Use descriptive names for globals, short names for locals.

Global variables need names long enough and descriptive enough to remind the reader of their meaning.

It's also helpful to include a brief comment with the declaration of each global.

The longer the program, the more important is the choice of good, descriptive, systematic names.

* Be consistent.

Give related things related names that show their relationship and high-light their difference.

* Use active names for functions.

* Be accurate.

   

1.2 Expressions and Statements

   

* Indent to show structure.

A consistent indentation style is the lowest-energy way to make a program's structure self-evident.

* Use the natural form of expressions.

Write expressions as you might speak them aloud.

* Parenthesize to resolve ambiguity.

* Break up complex expressions.

* Be clear.

the goal is to write clear code, not clever code.

* Be careful with side effects.

   

1.3 Consistency and Idioms

* Use a consistent indentation and brace style.

* Use idioms for consistency.

A central part of learning any language is developing a familiarity with its idioms.

* Use else-ifs for multi-way decisions.

   

1.4 Function Macros

* Avoid function macros.

* Parenthesize the macro body and arguments.

In C++, inline functions avoid the syntactic trouble while offering whatever performance advantage macros might provide.

They are appropriate for short functions that set or retrieve a single value.

   

1.5 Magic Numbers

Magic numbers are the constants, array sizes, character positions, conversion factors, and other literal numric values that appear in programs.

   

* Given names to magic numbers.

* Define numbers as constants, not macros.

The C preprocessor is a powerful but blunt tool, however, and macros are a dangerous way to program because they change the lexical structure of the program underfoot. Let the language proper do the work.

* Use character constants, not integers.

* Use the language to calculate the size of an object.

   

1.6 Comments

* Don't belabor the obvious.

* Comment functions and global data.

* Don't comment bad code, rewrite it.

* Don't contradict the code.

* Clarify,don't confuse.

   

1.7 Why bother?

The main concerns of programming style: descriptive names, clearity in expressions, straightforward control flow, readability of code and comments, and the importance of consistence use of conventions and idioms in achieving all of these.

Well-written code is easier to read and to understand, almost surely has fewer errors, and is likely to be smaller than code that has been carelessly tossed together and never polished.

The key observation is that good style should be a matter of habit.

Once they become automatic, your subconscious will take care of many of the details for you, and even the code you produce under pressure will be better.

   

   

E序设计实践 - W??/span>

1. 风格

1.1 名字

一个名字应该是非Ş式的、简l的、容易记忆的Q如果可能的话,最好是能够D的?/span>

* 全局变量使用h说明性的名字Q局部变量用短名字?/span>

全局变量的名字应该够长Q具有够的说明性。给每个全局变量声明附一个简短注释也非常有帮助?/span>

对于长的E序Q选择那些好的、具有说明性的、系l化的名字就更加重要?/span>

* 保持一致性?/span>

* 函数采用动作性名字?/span>

* 要准。名字与其实C持准的对应?/span>

   

1.2 表达式和语句

* 用羃行显C程序的l构?/span>

采用一U一致的~行风格Q是使程序呈现出l构清晰的最省力的方法?/span>

* 使用表达式的自然形式?/span>

表达式应该写得你能大声念出来?/span>

* 用加括号的方式排除二义性?/span>

* 分解复杂的表辑ּ?/span>

* 要清晰?/span>

目标应该是写出最清晰的代码,而不是最巧妙的代码?/span>

* 心副作用?/span>

?/span>++q一c运符h副作用,它们除了q回一个值外Q还隐含地改变变量的倹{?/span>

   

1.3 一致性和习惯用法

* 使用一致的~排和加括号风格?/span>

如果你工作在一个不是自己写的程序上Q请注意保留E序原有的风根{?/span>

* Z一致性,使用习惯用法?/span>

在学习一个语a的过E中Q一个中心问题就是逐渐熟悉它的习惯用法?/span>

   

-----------------------------------------------

常见习惯用法之一是@环的形式?/span>

例如Q?/span>

for(i = 0; i < n; i++)

array[i] = 1.0;

C++?/span>Java里常见的另一UŞ式是把@环变量的声明也包括在内:

for(int i = 0; i < n; i++)

array[i] = 1.0;

-----------------------------------------------

下面?/span>C语言扫描一个链表的标准循环Q?/span>

for(p = list; p != NULL; p = p->next)

...

-----------------------------------------------

无穷循环Q?/span>

for( ;; )

...

?/span>

while(1)

...

-----------------------------------------------

常见的另一个惯用法是把一个赋值放q@环条仉Q?/span>

while( (c = getchar()) != EOF)

putchar(c);

-----------------------------------------------

一个不好的例子Q?/span>

char *p, buf[256];

gets(buf);

p = malloc(strlen(buf));

strcpy(p, buf);

问题1.

l不要用函?/span>getsQ因Z没办法限制它p入那儿读入内容的数量。这常常会导致一个安全性问题?/span>

问题2.

q有另一个问题:strlen求出的值没有计入串l尾?/span>'\0'字符Q?/span>strcpy却将复制它?/span>

习惯写法是:

p = malloc(strlen(buf)+1);

strcpy(p, buf);

或在C++里:

p = new char[strlen(buf)+1];

strcpy(p , buf);

如果q里没有+1Q就要当心?/span>

strdup可以佉K免上q错误变得更单。可?/span>strdup不是ANSI C标准中的内容?/span>

问题3.

上面两个版本都没有检?/span>malloc的返回倹{?/span>

在实际程序中Q对?/span>malloc?/span>realloc?/span>strdup及Q何牵涉到存储分配的函敎ͼ它们的返回值都必须做检查?/span>

-----------------------------------------------

   

* ?/span>else-if表达多\选择?/span>

多\选择的习惯表C法形式如下Q?/span>

if (condition1)

statement1

else if (condition2)

statement2

...

else if (conditionn)

statementn

else

default-statement

   

1.4 函数?/span>

* 避免使用函数宏?/span>

函数宏最常见的一个严重问题是Q如果一个参数在定义中出现多ơ,它就可能被多ơ求倹{?/span>

如果调用时的实际参数带有副作用,l果可能生一个难以捉摸的错误?/span>

例子Q?/span>

?/span><ctype.h>中:

#define isupper(c) ((c) >= 'A' && (c) <= 'Z')

如果q样调用

while (isupper(c = getchar())),

两次输入的字W?/span>c被分别与'A'?/span>'Z'比较了?/span>

   

C语言标准允许?/span>isupper及类似函数定义ؓ宏,但要求保证它们的参数只求gơ?/span>

如果希望更安全些Q那么就一定不要嵌套地使用?/span>getcharq种带有副作用的函数?/span>

改写如下Q?/span>

while ((c = getchar()) != EOF && isupper(c))

有时多次求值带来的是执行效率问题,而不是真正的错误?/span>

   

* l宏的体和参数都加上括号?/span>

如果一个操作比较复杂,或者它很具一般性,值得包装hQ那么还是应该用函数?/span>

C++提供?/span>inline函数既避免了语法斚w的麻烦,而且又可得到宏能够提供的执行效率Q很适合来定义那些设|或者提取一个值的短信函数?/span>

   

1.5 秘的数 Q翻译的有点...Q?/span>

秘的数包括各种常数、数l的大小、字W位|、变换因子以及程序中出现的其他以文字形式写出的数倹{?/span>

   

* l神U的数v个名字?/span>

* 把数定义为常敎ͼ不要定义为宏?/span>

C语言预处理程序是一个强有力的工P但是它又有些鲁莽?/span>

使用宏进行编E是一U很危险的方式,因ؓ宏会在背地里改变E序的词法结构。我们应该让语法d正确的工作?/span>

Q译者注Q预处理命o不是C语言本n的组成部分,而是一l辅助成分。这里说"让语a..."Q也是说不要用预处理命令做。)

* 使用字符形式的常量,不要用整数?/span>

例子Q?/span>

if (c >= 65 && c <= 90)

...

q种写法完全依赖于特D的字符表示方式?/span>

q样写更好些Q?/span>

if (c >= 'A' && c <= 'Z')

...

但是Q如果在某个~码字符集里的字母编码不是连l的Q或Ҏ其他字母Q那么这U描q就是错的?/span>

最好是直接使用库函数?/span>

if(isupper(c))

...

-----------------------------------------------

E序里许多上下文中经常出现的0。如果我们把每个0的类型写得更明确更清楚,对读E序的h理解其作用是很有帮助的?/span>

例如Q用 (void*)0 ?/span> NULL 表示C里的I指针|?/span>'\0'而不?/span>0表示字符串结I字节?/span>

然而在C++里h们都已经接受了用0Q而不?/span>NULLQ表C空指针?/span>Java里则定义了关键字null?/span>

   

* 利用语言去计对象的大小?/span>

不要对Q何数据类型用显式写出来的大?/span>

例:

 char buf[1024];

 fgets(buf, sizeof(buf), stdin);

对于那些可以看清楚的数组Q不是指针)Q下面的宏定义能计算出数l的元素个数Q?/span>

#define NELEMS(array) (sizeof(array) / sizeof(array[0]))

   

1.6 注释

* 不要大谈明显的东ѝ?/span>

注释应该提供那些不能一下子从代码中看到的东西,或者把那些散布在许多代码里的信息收集到一赗?/span>

* l函数和全局数据加注释?/span>

* 不要注释差的代码Q重写它?/span>

* 不要与代码矛盾?/span>

当你改变代码Ӟ一定要注意保证其中的注释是准确的?/span>

* 澄清情况Q不要添乱?/span>

注释应该在困隄地方量帮助读者,而不是给他们讄障碍?/span>

   

注释很重要,但是也不必盲目注释?/span>

注释是一U工P它的作用是帮助读者理解程序中的某些部分,而这些部分的意义不容易通过代码本n直接看到?/span>

   

1.7 ZҎ费心

注重E序设计的风|h说明性的名字、清晰的表达式、直截了当的控制、可ȝ代码和注释,以及在追求这些内Ҏ一致地使用某些规则和惯用法的重要性?/span>

   

书写良好的代码更Ҏ阅读和理解,几乎可以保证其中的错误更?/span>

好风格应该成ZU习惯?/span>

一旦这U习惯变成自动的东西Q你的潜意识׃帮助你照料许多细节问题,甚至你在工作压力下写出的代码也会更好?/span>



LynnRaymond 2010-03-26 23:39 发表评论
]]>
【C++常识】C++的iostream标准库介l?/title><link>http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110620.html</link><dc:creator>LynnRaymond</dc:creator><author>LynnRaymond</author><pubDate>Fri, 26 Mar 2010 14:03:00 GMT</pubDate><guid>http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110620.html</guid><wfw:comment>http://www.shnenglu.com/yuqilin1228/comments/110620.html</wfw:comment><comments>http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110620.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.shnenglu.com/yuqilin1228/comments/commentRss/110620.html</wfw:commentRss><trackback:ping>http://www.shnenglu.com/yuqilin1228/services/trackbacks/110620.html</trackback:ping><description><![CDATA[<strong> Z么需要iostream 我们从一开始就一直在利用C++的输入输出在做着各种l习Q输入输出是由iostream库提供的Q所以讨论此标准库是有必要的Q它与C语言? stdio库不同,它从一开始就是用多重l承与虚拟承实现的面向对象的层ơ结构,作ؓ一个c++的标准库lg提供l程序员使用?</strong> <p><strong>   iostream为内|类型类型对象提供了输入输出支持Q同时也支持文g的输入输出,cȝ设计者可以通过对iostream? 的扩展,来支持自定义cd的输入输出操作?</strong> </p> <p><strong>   Z么说要扩展才能提供支持呢Q我们来一个示例?%CODE{"cpp"}% #include <stdio.h> #include <iostream></iostream>using namespace std; </strong> </p> <p><strong> class Test { public: Test(int a=0,int b=0) { Test::a=a; Test::b=b; } int a; int b; }; int main() { Test t(100,50); printf("%???",t);//不明的输出格式 scanf("%???",t);//不明的输入格式 cout<<t<<endl;//同样不够明确 cin>>t;//同样不够明确 system("pause"); } %ENDCODE% ׃自定义类的特D性,在上面的代码中,无论你用c风格的输入输出,或者是c++的输入输出都不是不明的一个表C,׃c语言没有q算W重载机 ӞDstdio库的不可扩充性,让我们无法让printf()和scanf()支持对自定义cd象的扩充识别Q而c++是可以通过q算W重载机制扩? iostream库的Qɾpȝ能能够识别自定义cdQ从而让输入输出明确的知道他们该q什么,格式是什么?</strong> </p> <p><strong>   在上例中我们之所以用printf与coutq行Ҏ目的是ؓ了告诉大ӞC与C++处理输入输出的根本不同,我们从cq的? 入输出可以很明显看出是函数调用方式,而c++的则是对象模式,cout和cin是ostreamcdistreamcȝ对象?</strong> </p> <h3><a name="2 fstream: ifstream ?ofstream"></a>1 iostream: istream ?ostream </h3> <strong>   C++中的iostream库主要包含下图所C的几个头文? </strong> <table class="twikiTable" border="0" cellpadding="1" cellspacing="1"> <tbody> <tr class="twikiTableEven"> <th class="twikiFirstCol" colspan="2" maxcols="0" bgcolor="#dadada">IOSstream ?</th> </tr> <tr class="twikiTableOdd"> <td class="twikiFirstCol" bgcolor="#eaeaea"><strong> fstream </strong> </td> <td bgcolor="#eaeaea"><strong> iomainip </strong> </td> </tr> <tr class="twikiTableEven"> <td class="twikiFirstCol" bgcolor="#ffffff"><strong> ios </strong> </td> <td bgcolor="#ffffff"><strong> iosfwd </strong> </td> </tr> <tr class="twikiTableOdd"> <td class="twikiFirstCol" bgcolor="#eaeaea"><strong> iostream </strong> </td> <td bgcolor="#eaeaea"><strong> istream </strong> </td> </tr> <tr class="twikiTableEven"> <td class="twikiFirstCol" bgcolor="#ffffff"><strong> ostream </strong> </td> <td bgcolor="#ffffff"><strong> sstream </strong> </td> </tr> <tr class="twikiTableOdd"> <td class="twikiFirstCol twikilast" bgcolor="#eaeaea"><strong> streambuf </strong> </td> <td class="twikiLast" bgcolor="#eaeaea"><strong> strstream </strong> </td> </tr> </tbody> </table> <p><strong>   我们所熟悉的输入输出操作分别是由istream(输入?和ostream(输出?q两个类提供的,Z允许双向的输入/ 输出Q由istream和ostreamzZiostreamcR?</strong> </p> <p><strong>   cȝl承关系见下图:<br><img alt="" src="http://www.pconline.com.cn/pcedu/empolder/gj/c/0504/pic/05cppios02.gif"> </strong> </p> <p><strong> iostream库定义了以下三个标准对象: </strong> </p> <ol> <li><strong> cinQ表C标准输?standard input)的istreamcd象。cin使我们可以从讑֤d数据?</strong> </li> <li><strong> coutQ表C标准输?standard output)的ostreamcd象。cout使我们可以向讑֤输出或者写数据?</strong> </li> <li><strong> cerrQ表C标准错?standard error)的osttreamcd象。cerr是导出程序错误消息的地方Q它只能允许向屏q设备写数据?</strong> </li> </ol> <p><strong>   输出主要由重载的左移操作W(<<Q来完成Q输入主要由重蝲的右UL作符(>>)完成: </strong> </p> <ol> <li><strong> >>a表示数据放入a对象中?</strong> </li> <li><strong> <<a表示a对象中存储的数据拿出?</strong> </li> </ol> <p><strong>   q些标准的流对象都有默认的所对应的设备,见下表:<br></strong> <table class="twikiTable" border="0" cellpadding="1" cellspacing="1"> <tbody> <tr class="twikiTableEven"> <th class="twikiFirstCol" maxcols="0" bgcolor="#dadada"><a title="Sort by this column" style="color: #000000;" rel="nofollow"><u>C++对象?/u></a> </th> <th maxcols="0" bgcolor="#dadada"><a title="Sort by this column" style="color: #000000;" rel="nofollow"><u>讑֤名称</u></a> </th> <th maxcols="0" bgcolor="#dadada"><a title="Sort by this column" style="color: #000000;" rel="nofollow"><u>C中标准设备名</u></a> </th> <th maxcols="0" bgcolor="#dadada"><a title="Sort by this column" style="color: #000000;" rel="nofollow"><u>默认含义</u></a> </th> </tr> <tr class="twikiTableOdd"> <td class="twikiFirstCol" align="middle" bgcolor="#eaeaea"><strong> cin </strong> </td> <td align="middle" bgcolor="#eaeaea"><strong> 键盘 </strong> </td> <td align="middle" bgcolor="#eaeaea"><strong> stdin </strong> </td> <td align="middle" bgcolor="#eaeaea"><strong> 标准输入 </strong> </td> </tr> <tr class="twikiTableEven"> <td class="twikiFirstCol" align="middle" bgcolor="#ffffff"><strong> cout </strong> </td> <td align="middle" bgcolor="#ffffff"><strong> 昄器屏q?</strong> </td> <td align="middle" bgcolor="#ffffff"><strong> stdout </strong> </td> <td align="middle" bgcolor="#ffffff"><strong> 标准输出 </strong> </td> </tr> <tr class="twikiTableOdd"> <td class="twikiFirstCol twikilast" align="middle" bgcolor="#eaeaea"><strong> cerr </strong> </td> <td class="twikiLast" align="middle" bgcolor="#eaeaea"><strong> 昄器屏q?</strong> </td> <td class="twikiLast" align="middle" bgcolor="#eaeaea"><strong> stderr </strong> </td> <td class="twikiLast" align="middle" bgcolor="#eaeaea"><strong> 标准错误输出 </strong> </td> </tr> </tbody> </table> <strong>   上表中的意思表明cin对象的默认输入设备是键盘Qcout对象的默认输备是昄器屏q?</strong> </p> <p><strong>   那么原理上E++有是如何利用cinQcout对象与左Ud右移q算W重载来实现输入输出的呢Q?</strong> </p> <p><strong>   下面我们以输Zؓ例,说明其实现原理: </strong> </p> <ol> <li><strong> cout是ostreamcȝ对象Q因为它所指向的是标准讑֤Q显C器屏幕Q,所以它在iostream头文件中作ؓ? 局对象q行定义?</strong> </li> <li><strong> ostream cout(stdout);//光认指向的C中的标准讑֤名,作ؓ其构造函数的参数使用? </strong> </li> <li><strong> 在iostream.h头文件中Qostreamcd应每个基本数据类型都有其友元函数对左UL作符q行了友 元函数的重蝲?</strong> <ul> <li><strong> ostream& operator<<(ostream &temp,int source); </strong> </li> <li><strong> ostream& operator<<(ostream &temp,char *ps); </strong> </li> <li><strong> ... {等 </strong> </li> </ul> </li> </ol> <p><strong>   一句输句:cout<<"www.cndev-lab.com"Q,事实上调用的是 ostream& operator<<(ostream &temp,char *ps);q个q算W重载函敎ͼ׃q回的是对象的引用Q引用可以作为左g用,所以当E序中有cMcout<<"www.cndev- lab.com"<<"中国软g开发实验室";q样的语句出现的时候,p够构成连l输出?</strong> </p> <p><strong>   ׃iostream库不光支持对象的输入输出Q同时也支持文g的输入输出Q所以在详细讲解左移与右U运符重蝲只前Q我? 有必要先Ҏ件的输入输出以及输入输出的控制符有所了解?</strong> </p> <h3><a name="2 fstream: ifstream ?ofstream"></a>2 fstream: ifstream ? ofstream </h3> <strong>   和文件有关系的输入输出类主要在fstream.hq个头文件中被定义,在这个头文g中主要被定义了三个类Q由q三个类控制Ҏ件的 各种输入输出操作Q他们分别是ifstream、ofstream、fstreamQ其中fstreamcL由iostreamcL生而来Q他们之间的l? 承关p见下图所C?br><img alt="" src="http://www.pconline.com.cn/pcedu/empolder/gj/c/0504/pic/05cppios04.gif"> </strong> <p><strong> ׃文g讑֤q不像显C器屏幕与键盘那h标准默认讑֤Q所以它在fstream.h头文件中是没有像cout那样预先定义的全局 对象Q所以我们必自己定义一个该cȝ对象Q我们要以文件作备向文g输出信息(也就是向文g写数?Q那么就应该使用ofstreamcR?</strong> </p> <p><strong>   ofstreamcȝ默认构造函数原形ؓQ?%CODE{"cpp"}% ofstream::ofstream(const char *filename,int mode = ios::out,int openprot = filebuf::openprot); %ENDCODE% </strong> </p> <ul> <li><strong> filenameQ  要打开的文件名 </strong> </li> <li><strong> modeQ    要打开文g的方?</strong> </li> <li><strong> protQ    打开文g的属?</strong> </li> </ul> <p><strong>   其中mode和openprotq两个参数的可选项表见下表Q?</strong> <table class="twikiTable" border="0" cellpadding="1" cellspacing="1"> <tbody> <tr class="twikiTableEven"> <td class="twikiFirstCol" colspan="2" align="middle" bgcolor="#eaeaea"><strong> mode 属性表 </strong> </td> </tr> <tr class="twikiTableOdd"> <td class="twikiFirstCol" bgcolor="#ffffff"><strong> ios::app </strong> </td> <td bgcolor="#ffffff"><strong> 以追加的方式打开文g </strong> </td> </tr> <tr class="twikiTableEven"> <td class="twikiFirstCol" bgcolor="#eaeaea"><strong> ios::ate </strong> </td> <td bgcolor="#eaeaea"><strong> 文g打开后定位到文g,ios:app包含有此属?</strong> </td> </tr> <tr class="twikiTableOdd"> <td class="twikiFirstCol" bgcolor="#ffffff"><strong> ios::binary </strong> </td> <td bgcolor="#ffffff"><strong> 以二q制方式打开文gQ缺省的方式是文本方式。两U方式的区别见前?</strong> </td> </tr> <tr class="twikiTableEven"> <td class="twikiFirstCol" bgcolor="#eaeaea"><strong> ios::in </strong> </td> <td bgcolor="#eaeaea"><strong> 文g以输入方式打开 </strong> </td> </tr> <tr class="twikiTableOdd"> <td class="twikiFirstCol" bgcolor="#ffffff"><strong> ios::out </strong> </td> <td bgcolor="#ffffff"><strong> 文g以输出方式打开 </strong> </td> </tr> <tr class="twikiTableEven"> <td class="twikiFirstCol twikilast" bgcolor="#eaeaea"><strong> ios::trunc </strong> </td> <td class="twikiLast" bgcolor="#eaeaea"><strong> 如果文g存在Q把文g长度设ؓ0 </strong> </td> </tr> </tbody> </table> <strong>   可以?#8220;?#8221;把以上属性连接v来,如ios::out|ios::binary?</strong> <table class="twikiTable" border="0" cellpadding="1" cellspacing="1"> <tbody> <tr class="twikiTableEven"> <td class="twikiFirstCol" colspan="2" align="middle" bgcolor="#eaeaea"><strong> openprot 属性表 </strong> </td> </tr> <tr class="twikiTableOdd"> <td class="twikiFirstCol" bgcolor="#ffffff"><strong> 属?</strong> </td> <td align="middle" bgcolor="#ffffff"><strong> 含义 </strong> </td> </tr> <tr class="twikiTableEven"> <td class="twikiFirstCol" bgcolor="#eaeaea"><strong> 0 </strong> </td> <td bgcolor="#eaeaea"><strong> 普通文Ӟ打开讉K </strong> </td> </tr> <tr class="twikiTableOdd"> <td class="twikiFirstCol" bgcolor="#ffffff"><strong> 1 </strong> </td> <td bgcolor="#ffffff"><strong> 只读文g </strong> </td> </tr> <tr class="twikiTableEven"> <td class="twikiFirstCol" bgcolor="#eaeaea"><strong> 2 </strong> </td> <td bgcolor="#eaeaea"><strong> 隐含文g </strong> </td> </tr> <tr class="twikiTableOdd"> <td class="twikiFirstCol twikilast" bgcolor="#ffffff"><strong> 4 </strong> </td> <td class="twikiLast" bgcolor="#ffffff"><strong> pȝ文g </strong> </td> </tr> </tbody> </table> <strong>   可以?#8220;?#8221;或?#8220;+”把以上属性连接v?Q如3?|2是以只d隐含属性打开文g?</strong> </p> <p><strong> 实例代码如下Q?%CODE{"cpp"}% #include <fstream></fstream>using namespace std; </strong> </p> <p><strong> int main() { ofstream myfile("c:\\1.txt",ios::out|ios::trunc,0); myfile<<"中国软g开发实验室"<<endl<<"|址Q?<<"www.cndev- lab.com"; myfile.close() system("pause"); } %ENDCODE% 文g使用完后可以使用close成员函数关闭文g?</strong> </p> <p><strong>   ios::app加模式,在用追加模式的时候同时进行文件状态的判断是一个比较好的习惯?</strong> </p> <p><strong>   CZ如下Q?</strong> </p> <p><strong> %CODE{"cpp"}% #include <iostream></iostream>#include <fstream></fstream>using namespace std; int main() { ofstream myfile("c:\\1.txt",ios::app,0); if(myfile)//或者写成myfile.fail() { cout<<"文g打开p|Q目标文件状态可能ؓ只读Q?; system("pause"); exit(1); } myfile<<"中国软g开发实验室"<<endl<<"|址Q?<<"www.cndev- lab.com"<<endl; myfile.close(); } %ENDCODE% </strong> </p> <p><strong>   在定义ifstream和ofstreamcd象的时候,我们也可以不指定文g。以后可以通过成员函数open()昑ּ的把一 个文件连接到一个类对象上?</strong> </p> <p><strong>   例如Q?</strong> </p> <p><strong> %CODE{"cpp"}% #include <iostream></iostream>#include <fstream></fstream>using namespace std; int main() { ofstream myfile; myfile.open("c:\\1.txt",ios::out|ios::app,0); if(myfile)//或者写成myfile.fail() { cout<<"文g创徏p|,盘不可写或者文件ؓ只读!"; system("pause"); exit(1); } myfile<<"中国软g开发实验室"<<endl<<"|址Q?<<"www.cndev- lab.com"<<endl; myfile.close(); } %ENDCODE% 下面我们来看一下是如何利用ifstreamcd象,文件中的数据读取出来,然后再输出到标准讑֤中的例子?</strong> </p> <p><strong>   代码如下Q?%CODE{"cpp"}% #include <iostream></iostream>#include <fstream></fstream>#include <string></string>using namespace std; int main() { ifstream myfile; myfile.open("c:\\1.txt",ios::in,0); if(myfile) { cout<<"文g读错?; system("pause"); exit(1); } char ch; string content; while(myfile.get(ch)) { content+=ch; cout.put(ch);//cout<<ch;q么写也是可以的 } myfile.close(); cout<<content; system("pause"); } %ENDCODE% 上例中,我们利用成员函数get()Q逐一的读取文件中的有效字W,再利用put()成员函数Q将文g中的数据通过循环逐一输出到标准设?屏幕) 上, get()成员函数会在文gd默尾的时候返回假|所以我们可以利用它的这个特性作为while循环的终止条Ӟ我们同时也在上例中引入了C++风格? 字符串类型stringQ在循环d的时候逐一保存到content中,要用stringcdQ必d含string.h的头文g?</strong> </p> <p><strong>  </strong> </p> <p><strong> 我们在简单介l过ofstreamcdifstreamcdQ我们再来看一下fstreamc,fstreamcL? iostreamz而来Qfstreamcd象可以同Ҏ件进行读写操作?</strong> </p> <p><strong>   CZ代码如下Q?%CODE{"cpp"}% #include <iostream></iostream>#include <fstream></fstream>using namespace std; int main() { fstream myfile; myfile.open("c:\\1.txt",ios::out|ios::app,0); if(myfile) { cout<<"文g写错?文g属性可能ؓ只读!"<<endl; system("pause"); exit(1); } myfile<<"中国软g开发实验室"<<endl<<"|址Q?<<"www.cndev- lab.com"<<endl; myfile.close(); </strong> </p> <p><strong> myfile.open("c:\\1.txt",ios::in,0); if(myfile) { cout<<"文g读错?文g可能丢失!"<<endl; system("pause"); exit(1); } char ch; while(myfile.get(ch)) { cout.put(ch); } myfile.close(); system("pause"); } %ENDCODE% ׃fstreamcd以对文g同时q行d操作Q所以对它的对象q行初始话的时候一定要昑ּ的指定mode和openprot参数?</strong> </p> <p><strong>   接下来我们来学习一下串类的基知识Q什么叫串流c? </strong> </p> <h3><a name="3 strstream: ostrstream ?istrs"></a>3 strstream: ostrstream ?istrstream </h3> <strong>   单的理解是能够控制字符串类型对象进行输入输出的c,C++不光可以支持C++风格的字W串控Ӟq可以支持C风格的字W串? 控制?</strong> <p><strong>   我们先看看看C++是如何对C风格的字W串进行控制的QC中的字符串其实也是字符数组Q字W数l内的数据在内存中的位置? 排列是连l的Q我们通常?char str[size]或者char *str的方式声明创建C风格字符数组Qؓ了能让字W数l作备ƈ提供输入输出操作QC++引入了ostrstream、istrstream? strstreamq三个类Q要使用他们创徏对象必d含strstream.h头文件?</strong> </p> <ul> <li><strong> istrstreamcȝ于执行C风格的串的输入操作Q也是以字W串数组作ؓ输入讑֤?</strong> </li> <li><strong> ostrstreamcȝ于执行C风格的串的输出操作Q也是一字符串数l作备?</strong> </li> <li><strong> strstreamcd时可以支持C风格的串的输入输出操作?</strong> </li> </ul> <p><strong>   istrstreamcL从istreamQ输入流c)和strstreambaseQ字W串基c)z? 来,ostrstream是从 ostreamQ输出流c)和strstreambaseQ字W串基c)z而来Qstrstream则是从iostream(输入输出类)和和 strstreambaseQ字W串基c)z而来?</strong> </p> <p><strong>   他们的承关pd下图所C?<br><img alt="" src="http://www.pconline.com.cn/pcedu/empolder/gj/c/0504/pic/05cppios05.gif"> </strong> </p> <p><strong>   串流同样不是标准讑֤Q不会有预先定义好的全局对象Q所以不能直接操作,需要通过构造函数创建对象?</strong> </p> <p><strong> cistrstream的构造函数原形如下: %CODE{"cpp"}% istrstream::istrstream(const char *str,int size); %ENDCODE% 参数1表示字符串数l?而参?表示数组大小Q当size?Ӟ表示istrstreamcd象直接连接到由str所指向的内存空间ƈ以\0l尾? 字符丌Ӏ?</strong> </p> <p><strong>   下面的示例代码就是利用istrstreamcd建类对象Q制定流输入讑֤为字W串数组Q通过它向一个字W型对象输入数据。代 码如下: %CODE{"cpp"}% #include <iostream></iostream>#include <strstream></strstream>using namespace std; int main() { char *name = "www.cndev-lab.com"; int arraysize = strlen(name)+1; istrstream is(name,arraysize); char temp; is>>temp; cout<<temp; system("pause"); } %ENDCODE% costrstream用于执行串流的输出,它的构造函数如下所C: %CODE{"cpp"}% ostrstream::ostrstream(char *_Ptr,int streamsize,int Mode = ios::out); %ENDCODE%   W一个参数是字符数组Q第二个是说明数l的大小Q第三个参数是指打开方式?</strong> </p> <p><strong>   我们来一个示例代码: %CODE{"cpp"}% #include <iostream></iostream>#include <strstream></strstream>using namespace std; int main() { int arraysize=1; char *pbuffer=new char[arraysize]; ostrstream ostr(pbuffer,arraysize,ios::out); ostr<<arraysize<<ends;//使用ostrstream输出到流对象的时?要用endsl束字符? cout<<pbuffer; delete[] pbuffer; system("pause"); } %ENDCODE% 上面的代码中Q我们创Z个c风格的串输出对象ostrQ我们将arraysize内的数据成功的以字符串的形式输出Costr对象所指向? pbuffer指针的堆I间中,pbuffer也正是我们要输出的字W串数组Q在l尾要用endsl束字符Ԍ如果不这么做有溢出的危险?</strong> </p> <h3><a name="4 stringstream"></a>4 stringstream </h3> <strong> 对于stringstream了来_不用我多_大家也已l知道它是用于C++风格的字W串的输入输出的? stringstream的构造函数原形如下: %CODE{"cpp"}%   stringstream::stringstream(string str); %ENDCODE%   CZ代码如下: %CODE{"cpp"}% #include <iostream></iostream>#include <sstream></sstream>#include <string></string>using namespace std; </strong> <p><strong> int main() { stringstream ostr("ccc"); ostr.put('d'); ostr.put('e'); ostr<<"fg"; string gstr = ostr.str(); cout<<gstr<<endl; </strong> </p> <p><strong> char a; ostr>>a; cout<<a </strong> </p> <p><strong> system("pause"); } %ENDCODE% 除此而外Qstringstreamcȝ对象我们q常用它q行string与各U内|类型数据之间的转换。示例代码如下: %CODE{"cpp"}% #include <iostream></iostream>#include <sstream></sstream>#include <string></string>using namespace std; </strong> </p> <p><strong> int main() { stringstream sstr; //--------int转string----------- int a=100; string str; sstr<<a; sstr>>str; cout<<str<<endl; //--------string转char[]-------- sstr.clear();//如果你想通过使用同一stringstream对象实现多种cd的{换,h意在每一ơ{换之后都必须调用clear() 成员函数?string name = "colinguan"; char cname[200]; sstr<<name; sstr>>cname; cout<<cname; system("pause"); } %ENDCODE% 接下来我们来学习一下输?输出的状态标志的相关知识. </strong> </p> <h3><a name="5 io_state 输入/输出的状态标?></a>5 io_state 输入/输出的状态标?</h3> <strong> C++中负责的输入/输出的系l包括了关于每一个输?输出操作的结果的记录信息。这些当前的状态信息被包含在io_statecd的对 象中。io_state是一个枚丄型(像open_mode一PQ以下便是它包含的倹{?</strong> <ul> <li><strong> goodbit 无错?</strong> </li> <li><strong> Eofbit 已到达文件尾 </strong> </li> <li><strong> failbit 非致命的输入/输出错误Q可挽回 </strong> </li> <li><strong> badbit 致命的输?输出错误,无法挽回 </strong> </li> </ul> <p><strong> 有两U方法可以获得输?输出的状态信息。一U方法是通过调用rdstate()函数Q它返回当前状态的错误标记。例如,假如? 有Q何错误,则rdstate()会返回goodbit.下例CZQ表C出了rdstate()的用法: %CODE{"cpp"}% #include <iostream></iostream>using namespace std; </strong> </p> <p><strong> int main() { int a; cin>>a; cout<<cin.rdstate()<<endl; if(cin.rdstate() == ios::goodbit) { cout<<"输入数据的类型正,无错误!"<<endl; } if(cin.rdstate() == ios_base::failbit) { cout<<"输入数据cd错误Q非致命错误Q可清除输入~冲区挽回!"<<endl; } system("pause"); } %ENDCODE%   另一U方法则是用下面Q何一个函数来相应的输入/输出状态: %CODE{"cpp"}% bool bad(); bool eof(); bool fail(); bool good(); %ENDCODE% </strong> </p> <p><strong>   下例CZQ表C出了上面各成员函数的用法: %CODE{"cpp"}% #include <iostream></iostream>using namespace std; </strong> </p> <p><strong> int main() { int a; cin>>a; cout<<cin.rdstate()<<endl; if(cin.good()) { cout<<"输入数据的类型正,无错误!"<<endl; } if(cin.fail()) { cout<<"输入数据cd错误Q非致命错误Q可清除输入~冲区挽回!"<<endl; } system("pause"); } %ENDCODE% 如果错误发生Q那么流状态既被标Cؓ错误Q你必须清除q些错误状态,以你的E序能正适当地l运行。要清除错误状态,需使用clear()函数? 此函数带一个参敎ͼ它是你将要设为当前状态的标志倹{,只要ios::goodbit作ؓ实参?</strong> </p> <p><strong>   CZ代码如下Q?%CODE{"cpp"}% #include <iostream></iostream>using namespace std; </strong> </p> <p><strong> int main() { int a; cin>>a; cout<<cin.rdstate()<<endl; cin.clear(ios::goodbit); cout<<cin.rdstate()<<endl; system("pause"); } %ENDCODE% 通常当我们发现输入有错又需要改正的时候,使用clear()更改标记为正后Q同时也需要用get()成员函数清除输入~冲区,以达到重复输入的? 的?</strong> </p> <p><strong>   CZ代码如下Q?%CODE{"cpp"}% #include <iostream></iostream>using namespace std; </strong> </p> <p><strong> int main() { int a; while(1) { cin>>a; if(cin)//条g可改写ؓcin.fail() { cout<<"输入有错!请重新输?<<endl; cin.clear(); cin.get(); } else { cout<<a; break; } } system("pause"); } %ENDCODE%   最后再l出一个对文g错误标记处理的例子Qm固学习,代码如下Q? %CODE{"cpp"}% #include <iostream></iostream>#include <fstream></fstream>using namespace std; </strong> </p> <p><strong> int main() { ifstream myfile("c:\\1.txt",ios_base::in,0); if(myfile.fail()) { cout<<"文gdp|或指定文件不存在!"<<endl; } else { char ch; while(myfile.get(ch)) { cout<<ch; } if(myfile.eof()) { cout<<"文g内容已经全部d"<<endl; } while(myfile.get(ch)) { cout<<ch; } } system("pause"); } %ENDCODE%  </strong> </p> <br> <img src ="http://www.shnenglu.com/yuqilin1228/aggbug/110620.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.shnenglu.com/yuqilin1228/" target="_blank">LynnRaymond</a> 2010-03-26 22:03 <a href="http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110620.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>【C++常识】C++输入输出?/title><link>http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110619.html</link><dc:creator>LynnRaymond</dc:creator><author>LynnRaymond</author><pubDate>Fri, 26 Mar 2010 14:01:00 GMT</pubDate><guid>http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110619.html</guid><wfw:comment>http://www.shnenglu.com/yuqilin1228/comments/110619.html</wfw:comment><comments>http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110619.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.shnenglu.com/yuqilin1228/comments/commentRss/110619.html</wfw:commentRss><trackback:ping>http://www.shnenglu.com/yuqilin1228/services/trackbacks/110619.html</trackback:ping><description><![CDATA[<p>C++ 通过以下几个cL持文件的输入输出Q?/p> <ul> <li>ofstream: 写操作(输出Q的文gc?(由ostream引申而来) </li> <li>ifstream: L作(输入Q的文gc?由istream引申而来) </li> <li>fstream: 可同时读写操作的文gc?(由iostream引申而来) </li> </ul> <p> </p> <h3>打开文g(Open a file)</h3> <p>对这些类的一个对象所做的W一个操作通常是它和一个真正的文g联系hQ也是说打开一个文件。被打开的文件在E序中由一个流对象 (stream object)来表C?(q些cȝ一个实? Q而对q个对象所做的M输入输出操作实际是对该文g所做的操作?/p> <p>要通过一个流对象打开一个文Ӟ我们使用它的成员函数open()Q?/p> <p><code><font face="NSimsun">void open (const char * filename, openmode mode);</font></code>q里filename 是一个字W串Q代表要打开的文件名Qmode 是以下标志符的一个组合:</p> <table border="1" cellpadding="3" cellspacing="0"> <tbody> <tr> <td>ios::in</td> <td>??而打开 文g</td> </tr> <tr> <td>ios::out</td> <td>??而打开 文g</td> </tr> <tr> <td>ios::ate</td> <td>初始位置Q文件尾</td> </tr> <tr> <td>ios::app</td> <td>所有输出附加在文g 末尾</td> </tr> <tr> <td>ios::trunc</td> <td>如果文g已存在则? 删除该文?/td> </tr> <tr> <td>ios::binary</td> <td>二进制方?/td> </tr> </tbody> </table> <p>q些标识W可以被l合使用Q中间以”?#8221;操作W?|)间隔。例如,如果我们惌以二q制方式打开文g”example.bin” 来写入一些数据,我们可以通过以下方式调用成员函数openQ)来实玎ͼ</p> <p><code><font face="NSimsun">ofstream file;<br>file.open ("example.bin", ios::out | ios::app | ios::binary); </font></code>ofstream, ifstream ?fstream所有这些类的成员函数open 都包含了一个默认打开文g的方式,q三个类的默认方式各不相同:</p> <table border="1" cellpadding="3" cellspacing="0"> <tbody> <tr> <th>c?/th> <th>参数的默认方?/th> </tr> <tr> <td>ofstream</td> <td>ios::out | ios::trunc</td> </tr> <tr> <td>ifstream</td> <td>ios::in</td> </tr> <tr> <td>fstream</td> <td>ios::in | ios::out</td> </tr> </tbody> </table> <p>只有当函数被调用时没有声明方式参数的情况下,默认值才会被采用。如果函数被调用时声明了M参数Q默认值将被完全改写,而不会与调用参数l合?/p> <p>׃对类ofstream, ifstream ?fstream 的对象所q行的第一个操作通常都是打开文gQ这些类都有一个构造函数可以直接调用open 函数Qƈ拥有同样的参数。这P我们可以通过以下方式q行与上面同L定义对象和打开文g的操作:</p> <p><code><font face="NSimsun">ofstream file ("example.bin", ios::out | ios::app | ios::binary);</font></code>两种打开文g的方式都是正的?/p> <p>你可以通过调用成员函数is_open()来检查一个文件是否已l被利的打开了:</p> <p><code><font face="NSimsun">bool is_open();</font></code>它返回一个布?bool) |为真QtrueQ代表文件已l被利打开Q假( false )则相反?/p> <h3>关闭文g(Closing a file)</h3> <p>当文件读写操作完成之后,我们必须文件关闭以使文仉新变为可讉K的。关闭文仉要调用成员函数close()Q它负责缓存中的数据排攑և来ƈ 关闭文g。它的格式很单:</p> <p><code><font face="NSimsun">void close ();</font></code>q个函数一旦被调用Q原先的? 对象(stream object)可以被用来打开其它的文件了Q这个文件也可以重新被其它的进E?process)所有访问了?/p> <p>为防止流对象被销毁时q联pȝ打开的文Ӟ析构函数(destructor)会自动调用关闭函数close?/p> <h3>文本文g(Text mode files)</h3> <p>cofstream, ifstream 和fstream 是分别从ostream, istream 和iostream 中引甌来的。这是Z?fstream 的对象可以用其父类的成员来讉K数据?/p> <p>一般来_我们用这些类与同控制?console)交互同样的成员函?cin ? cout)来进行输入输出。如下面的例题所C,我们使用重蝲的插入操作符<<Q?/p> <table border="2" cellpadding="1" cellspacing="1" width="400"> <tbody> <tr> <td><font color="#008000">// writing on a text file</font><br>#include <fiostream.h>int main () {<br>ofstream examplefile (”example.txt”);<br>if (examplefile.is_open()) {<br>examplefile << “This is a line.\n”;<br>examplefile << “This is another line.\n”;<br>examplefile.close();<br>}<br>return 0;<br>}</td> <td><font color="#008000">file example.txt<br></font>This is a line.<br>This is another line.</td> </tr> </tbody> </table> <p>从文件中d数据也可以用?cin的用同LҎQ?/p> <table border="2" cellpadding="1" cellspacing="1" width="400"> <tbody> <tr> <td><font color="#008000">// reading a text file</font><br>#include <iostream.h><br>#include <fstream.h><br>#include <stdlib.h>int main () {<br>char buffer[256];<br>ifstream examplefile (”example.txt”);<br>if (! examplefile.is_open())<br>{ cout << “Error opening file”; exit (1); }<br>while (! examplefile.eof() ) {<br>examplefile.getline (buffer,100);<br>cout << buffer << endl;<br>}<br>return 0;<br>}</td> <td>This is a line.<br>This is another line.</td> </tr> </tbody> </table> <p>上面的例子读入一个文本文件的内容Q然后将它打印到屏幕上。注意我们用了一个新的成员函数叫做eof Q它是ifstream 从类 ios 中承过来的Q当到达文g末尾时返回true ?/p> <h3>状态标志符的验?Verification of state flags)</h3> <p>除了eof()以外Q还有一些验证流的状态的成员函数Q所有都q回bool型返回|Q?/p> <ul> <li><strong> bad()</strong> 如果在读写过E中出错Q返?true 。例如:当我们要对一个不是打开为写状态的文gq行写入Ӟ或者我们要写入的设备没有剩余空间的时候? </li> <li><strong> fail()</strong> 除了与bad() 同样的情况下会返?true 以外Q加上格式错误时也返回true Q例如当惌d一个整敎ͼ而获得了一个字母的时候? </li> <li><strong> eof()</strong> 如果L件到达文件末,q回true? </li> <li><strong> good()</strong> q是最通用的:如果调用以上M一个函数返回true 的话Q此函数q回 false ?</li> </ul> <p>要想重置以上成员函数所查的状态标志,你可以用成员函数clear()Q没有参数?/p> <h3>获得和设|流指针(get and put stream pointers)</h3> <p>所有输?输出对?i/o streams objects)都有臛_一个流指针Q?/p> <ul> <li>ifstreamQ?cMistream, 有一个被UCؓget pointer的指针,指向下一个将被读取的元素? </li> <li>ofstream, cM ostream, 有一个指?put pointer Q指向写入下一个元素的位置? </li> <li>fstream, cM iostream, 同时l承了get ?put </li> </ul> <p>我们可以通过使用以下成员函数来读出或配置q些指向中d位置的流指针Q?/p> <ul> <li><strong> tellg() ?tellp()</strong> q两个成员函C用传入参敎ͼq回pos_type cd的?ҎANSI-C++ 标准) Q就是一个整敎ͼ代表当前get 指针的位置 (用tellg) ?put 指针的位置(用tellp). </li> <li><strong> seekg() 和seekp()</strong> q对函数分别用来改变指针get 和put的位|。两个函数都被重载ؓ两种不同的原型: <p>seekg ( pos_type position );<br>seekp ( pos_type position );</p> <p>使用q个原型Q流指针被改变ؓ指向从文件开始计的一个绝对位|。要求传入的参数cd与函?tellg 和tellp 的返回值类型相同?/p> <p>seekg ( off_type offset, seekdir direction );<br>seekp ( off_type offset, seekdir direction );</p> <p>使用q个原型可以指定由参数direction军_的一个具体的指针开始计的一个位U?offset)。它可以是:</p> <table border="1" cellpadding="3" cellspacing="0"> <tbody> <tr> <td>ios::beg</td> <td>从流开始位 |计的位移</td> </tr> <tr> <td>ios::cur</td> <td>从流指针? 前位|开始计的位移</td> </tr> <tr> <td>ios::end</td> <td>从流末尾? 开始计的位移</td> </tr> </tbody> </table> </li> </ul> <p>?指针 get ?put 的值对文本文g(text file)和二q制文g(binary file)的计方法都是不同的Q因为文本模式的文g中某些特D字W可能被修改。由于这个原因,对以文本文g模式打开的文件L使用seekg ? seekp的第一U原型,而且不要对tellg ?tellp 的返回D行修攏V对二进制文Ӟ你可以Q意用这些函敎ͼ应该不会有Q何意外的行ؓ产生?/p> <p>以下例子使用q些函数来获得一个二q制文g的大:</p> <table border="2" cellpadding="1" cellspacing="1" width="400"> <tbody> <tr> <td><font color="#008000">// obtaining file size<br><font color="#000000">#include <iostream.h><br>#include <fstream.h></font></font><font color="#008000"><font color="#000000">const char * filename = “example.txt”;</font></font><font color="#008000"><font color="#000000">int main () {<br>long l,m;<br>ifstream file (filename, ios::in|ios::binary);<br>l = file.tellg();<br>file.seekg (0, ios::end);<br>m = file.tellg();<br>file.close();<br>cout << “size of ” << filename;<br>cout << ” is ” << (m-l) << ” bytes.\n”;<br>return 0;<br>}</font></font></td> <td>size of example.txt<br>is 40 bytes.</td> </tr> </tbody> </table> <h3>二进制文?Binary files)</h3> <p>在二q制文g中,使用<< ?gt;>Q以及函敎ͼ如getlineQ来操作W输入和输出数据Q没有什么实际意义,虽然它们是符合语法的?/p> <p>?件流包括两个为顺序读写数据特D设计的成员函数Qwrite ?read。第一个函?(write) 是ostream 的一个成员函敎ͼ都是被ofstream所l承。而read 是istream 的一个成员函敎ͼ被ifstream 所l承。类 fstream 的对象同时拥有这两个函数。它们的原型是:</p> <p>write ( char * buffer, streamsize size );<br>read ( char * buffer, streamsize size );</p> <p>q里 buffer 是一块内存的地址Q用来存储或d数据。参数size 是一个整数|表示要从~存QbufferQ中d或写入的字符数?/p> <table border="2" cellpadding="1" cellspacing="1" width="400"> <tbody> <tr> <td><font color="#008000"><font color="#008000">// reading binary file</font><br><font color="#000000">#include <iostream><br>#include <fstream.h></font></font><font color="#008000"><font color="#000000">const char * filename = “example.txt”;</font></font><font color="#008000"><font color="#000000">int main () {<br>char * buffer;<br>long size;<br>ifstream file (filename, ios::in|ios::binary|ios::ate);<br>size = file.tellg();<br>file.seekg (0, ios::beg);<br>buffer = new char [size];<br>file.read (buffer, size);<br>file.close();</font></font><font color="#008000"><font color="#000000">cout << “the complete file is in a buffer”;</font></font><font color="#008000"><font color="#000000">delete[] buffer;<br>return 0;<br>}</font></font></td> <td>The complete file<br>is in a buffer</td> </tr> </tbody> </table> <h3>~存和同?Buffers and Synchronization)</h3> <p>?我们Ҏ件流q行操作的时候,它们与一个streambuf cd的缓?buffer)联系在一赗这个缓存(bufferQ实际是一块内存空_作ؓ?stream)和物理文件的媒介。例如,对于一个输出流Q? 每次成员函数put (写一个单个字W?被调用,q个字符不是直接被写入该输出所对应的物理文件中的,而是首先被插入到该流的缓存(bufferQ中?/p> <p>当缓存被排放出来(flush)Ӟ它里面的所有数据或者被写入物理媒质中(如果是一个输出流的话Q,或者简单的被抹?如果是一个输入流的话)? q个q程UCؓ同步(synchronization)Q它会在以下M情况下发生:</p> <ul> <li><strong> 当文件被关闭?</strong> 在文件被关闭之前Q所有还没有被完全写出或d的缓存都被同步? </li> <li><strong> 当缓存buffer 满时:</strong> ~存Buffers 有一定的I间限制。当~存满时Q它会被自动同步? </li> <li><strong> 控制W明指?</strong> 当遇到流中某些特定的控制W时Q同步会发生。这些控制符包括Qflush 和endl? </li> <li><strong> 明确调用函数sync():</strong> 调用成员函数sync() (无参?可以引发立即同步。这个函数返回一个int |{于-1 表示没有联pȝ~存或操作失败?</li> </ul> <br><img src ="http://www.shnenglu.com/yuqilin1228/aggbug/110619.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.shnenglu.com/yuqilin1228/" target="_blank">LynnRaymond</a> 2010-03-26 22:01 <a href="http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110619.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>【{载】ƈ查集 (Union-Find Sets)http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110618.htmlLynnRaymondLynnRaymondFri, 26 Mar 2010 13:59:00 GMThttp://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110618.htmlhttp://www.shnenglu.com/yuqilin1228/comments/110618.htmlhttp://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110618.html#Feedback0http://www.shnenglu.com/yuqilin1228/comments/commentRss/110618.htmlhttp://www.shnenglu.com/yuqilin1228/services/trackbacks/110618.html阅读全文

LynnRaymond 2010-03-26 21:59 发表评论
]]>
【{载】从零开始学法Q十U排序算法介l?/title><link>http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110617.html</link><dc:creator>LynnRaymond</dc:creator><author>LynnRaymond</author><pubDate>Fri, 26 Mar 2010 13:54:00 GMT</pubDate><guid>http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110617.html</guid><wfw:comment>http://www.shnenglu.com/yuqilin1228/comments/110617.html</wfw:comment><comments>http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110617.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.shnenglu.com/yuqilin1228/comments/commentRss/110617.html</wfw:commentRss><trackback:ping>http://www.shnenglu.com/yuqilin1228/services/trackbacks/110617.html</trackback:ping><description><![CDATA[<a title="Permanent link to 从零开始学法Q十U排序算法介l(上)" rel="bookmark"><u><font color="#800080">从零开始学法Q十U排序算法介l(上)</font></u></a>   From:Martix67【牛啊!?br>今天我正式开始按?a target="_blank"><u><font color="#0000ff">我的目录</font></u></a>写我的OI心得了。我要把 我所有学到的OI知识传给以后千千万万的OIer。以前写q的一些东西不重复写了Q但我最后将会重新整理,使之成ؓ一个完整的教程?br>    按照 我的目录Q讲M东西之前我都会先介绍旉复杂度的相关知识Q以后动不动׃扯到q个东西。这个已l写q了Q你可以?a target="_blank"><u><font color="#0000ff">q里</font></u></a>看到那篇又臭又长的文章。在? 排序法的过E中Q我们将始终围绕旉复杂度的内容q行说明?br>    我把q篇文章UC?#8220;从零开始学法”Q因为排序算法是最基础的算法,介绍 法时从各种排序法入手是最好不q的了?br><br>    l出n个数Q怎样它们从到大排序?下面一口气讲三U常用的法Q它们是最单的? 最昄的、最Ҏ惛_的。选择排序(Selection Sort)是说Q每ơ从数列中找Z个最的数放到最前面来,再从剩下的n-1个数中选择一个最的Q不断做下去。插入排?Insertion Sort)是,每次从数列中取一个还没有取出q的敎ͼq按照大关pL入到已经取出的数中得已l取出的C然有序。冒泡排?Bubble Sort)分ؓ若干进行,每一排序从前往后比较每两个盔R的元素的大小Q因此一排序要比较n-1对位|相ȝ敎ͼq在每次发现前面的那个数比紧接它 后的数大时交换位|;q行_多趟直到某一跑完后发现q一没有进行Q何交换操作(最坏情况下要跑n-1,q种情况在最的C于给定数列的最后面? 发生Q。事实上Q在W一冒泡结束后Q最后面那个数肯定是最大的了,于是W二ơ只需要对前面n-1个数排序Q这又将把这n-1个数中最的数放到整个数? 的倒数W二个位|。这样下去,冒排序Wi结束后后面i个数都已l到位了Q第i+1实际上只考虑前n-i个数Q需要的比较ơ数比前面所说的n-1? )。这相当于用数学归纳法证明了冒排序的正性:实质与选择排序相同。上面的三个法描述可能有点模糊了,没明白的话网上找资料Q代码和动画演示遍地 都是?br><img alt="" src="http://www.matrix67.com/blogimage/200703311.gif" border="0"><br>    q? 三种法非常Ҏ理解Q因为我们生zd中经常在用。比如,班上的MM搞选美zdQ有人叫我给所有MM排个名。我们通常会用选择排序Q即先找p为最? 亮的Q然后找W二漂亮的,然后扄三漂亮的Q不断找剩下的h中最满意的。打扑克牌时我们希望抓完牌后手上的牌是有序的Q三?挨在一P后面紧接着两个 9。这Ӟ我们会用插入排序,每次拿到一张牌后把它插入到手上的牌中适当的位|。什么时候我们会用冒泡排序呢Q比如,体育课上从矮到高排队Ӟ站队完毕 后M有h出来Q比较挨着的两个h的n高,指挥刎ͼ你们俩调换一下,你们俩换一下?br>    q是很有启发性的。这告诉我们Q什么时候用什么排序最 好。当Z渴望先知道排在前面的是谁Ӟ我们用选择排序Q?strong style="color: #0000ff;">当我们不断拿 到新的数q想保持已有的数始终有序Ӟ我们用插入排序;当给出的数列已经比较有序Q只需要小q度的调整一下时Q我们用冒排序?<br><br>    ? 们来一下最坏情况下三种法各需要多次比较和赋值操作?br>    选择排序在第iơ选择时赋值和比较都需要n-iơ(在n-i+1个数中选一? 出来作ؓ当前最|其余n-i个数与当前最值比较ƈ不断更新当前最|Q然后需要一ơ赋值操作。d需要n(n-1)/2ơ比较与n(n-1) /2+nơ赋倹{?br>    插入排序在第iơ寻找插入位|时需要最多i-1ơ比较(从后往前找到第一个比待插入的数小的数Q最坏情况发生在q个数是 所有已l取出的C最的一个的时候)Q在已有数列中给新的数腾Z|需要i-1ơ赋值操作来实现Q还需要两ơ赋值借助临时变量把新取出的数搬进搬出。也 是_最坏情况下比较需要n(n-1)/2ơ,赋值需要n(n-1)/2+2nơ。我q么写有点误ghQ大家不要以为程序的实现用了两个数组哦,其实一 个数l就够了Q看看上面的演示q道了。我只说法Q一般不写如何实现。学法的都是强人,知道法了都能写Z个漂亮的代码来?br>    冒? 序第i排序需要比较n-iơ,n-1排序dn(n-1)/2ơ。给出的序列逆序排列是最坏的情况Q这时每一ơ比较都要进行交换操作。一ơ交换操作需 ?ơ赋值实玎ͼ因此冒排序最坏情况下需要赋?n(n-1)/2ơ?br>    按照渐进复杂度理论,忽略所有的常数Q三U排序的最坏情况下复杂 度都是一LQO(n^2)。但实际应用中三U排序的效率q不相同。实践证明(政治考试时每道大题都要用q四个字Q,插入排序是最快的Q虽然最坏情况下? 选择排序相当甚至更糟Q,因ؓ每一ơ插入时L插入的位|多数情况只需要与已有数的一部分q行比较Q你可能知道q还能二分)。你或许会说冒排序也可以在 半\上完成,q没有跑到第n-1就已经有序。但冒排序的交换操作更ҎQ而插入排序中扑ֈ了插入的位置后移动操作只需要用赋值就能完成(你可能知道这 q能用moveQ。本文后面将介绍的一U算法就利用插入排序的这些优ѝ?br><br>    我们证明了,三种排序Ҏ在最坏情况下旉复杂度都? O(n^2)。但大家惌吗,q只是最坏情况下的。在很多时候,复杂度没有这么大Q因为插入和冒在数列已l比较有序的情况下需要的操作q远低于n^2? Q最好情况下甚至是线性的Q。抛开选择排序不说Q因为它的复杂度?#8220;?#8221;的,对于选择排序没有什?#8220;?#8221;的情况)Q我们下面探讨插入排序和冒排序在特? 数据和^均情况下的复杂度?br>    你会发现Q如果把插入排序中的Ud赋值操作看作是把当前取出的元素与前面取出的且比它大的数逐一交换Q那插入 排序和冒泡排序对数据的变动其实都是相d素的交换操作。下面我们说明,若只能对数列中相ȝ数进行交换操作,如何计算使得n个数变得有序最需要的交换 ơ数?br>    我们定义逆序对的概念。假设我们要把数列从到大排序,一个逆序Ҏ指的在原数列中,左边的某个数比右边的大。也是_如果扑ֈ 了某个i和j使得i<j且Ai>AjQ我们就说我们找C一个逆序寏V比如说Q数?,1,4,2中有三个逆序对,而一个已l有序的数列逆序 对个Cؓ0。我们发玎ͼ交换两个盔R的数最多消除一个逆序对,且冒泡排序(或插入排序)中的一ơ交换恰好能消除一个逆序寏V那么显Ӟ原数列中有多个? 序对冒排序Q或插入排序Q就需要多次交换操作Q这个操作次C可能再少?br>    若给出的n个数中有m个逆序对,插入排序的时间复杂度可以? 是O(m+n)的,而冒泡排序不能这么说Q因为冒泡排序有很多“无用”的比较(比较后没有交换)Q这些无用的比较过了O(m+n)个。从q个意义上说Q? 插入排序仍然更ؓ优秀Q因为冒泡排序的复杂度要受到它跑的趟数的制约。一个典型的例子是这L数列Q?, 2, 3, 4, 5, 6, 7, 1。在q样的输入数据下插入排序的优劉K常明显,冒排序只能哭着喊上天不公?br>    然而,我们q不惌排序算法对于某个特定数据的效率。我 们真正关心的是,对于所有可能出现的数据Q算法的q_复杂度是多少。不用激动了Q^均复杂度q不会低于^斏V下面证明,两种法的^均复杂度仍然? O(n^2)的?br>    我们仅仅证明法需要的交换ơ数q_为O(n^2)p够了。前面已l说q,它们需要的交换ơ数与逆序对的个数相同。我 们将证明Qn个数的数列中逆序对个数^均O(n^2)个?br>    计算的方法是十分巧妙的。如果把l出的数列反q来Q从后往前倒过来写Q,你会? 现原来的逆序对现在变成顺序的了,而原来所有的非逆序对现在都成逆序了。正反两个数列的逆序对个数加h正好是数列所有数对的个数Q它{于n(n- 1)/2。于是,q_每个数列有n(n-1)/4个逆序寏V忽略常敎ͼ逆序对^均个数O(n^2)?br>    上面的讨论启C我们,要想搞出一个复 杂度低于qxU别的排序算法,我们需要想办法能把d老远的两个数q行操作?br><br>    Z惛_惛_惛_Q怎么都想不出怎样才能搞出复杂? 低于qx的算法。后来,英雄出现了,Donald Shell发明了一U新的算法,我们证明它的复杂度最坏情况下也没有O(n^2) Q似乎有Z喜欢研究正确性和复杂度的证明Q我会用实例告诉大家Q这些证明是非常有意思的Q。他把这U算法叫做Shell增量排序法Q大家常说的希尔? 序)?br>    Shell排序法依赖一U称之ؓ“排序增量”的数列,不同的增量将D不同的效率。假如我们对20个数q行排序Q用的增量? 1,3,7。那么,我们首先对这20个数q行“7-排序”(7-sortedness)。所?-排序Q就是按照位|除?的余数分l进行排序。具体地 _我们把???5三个位置上的数进行排序,第2??6个数q行排序Q依此类推。这P对于L一个数字kQ单看A(k), A(k+7), A(k+14), …q些数是有序的?-排序后,我们接着又进行一?-排序Q别忘了我们使用的排序增量ؓ1,3,7Q。最后进?-排序Q即普通的排序Q后整个 Shell法完成。看看我们的例子Q?br><br>  3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2  <-- 原数?br>  3 3 2 0 5 1 5 7 4 4 0 6 1 6 8 7 9 9 8 2  <-- 7-排序?br>  0 0 1 1 2 2 3 3 4 4 5 6 5 6 8 7 7 9 8 9  <-- 3-排序?br>  0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9  <-- 1-排序后(完成Q?br><br>    在每一、每一l的排序中我们L使用插入排序。仔l观察上面的例子你会发现是什么导致了 Shell排序的高效。对Q每一排序将使得数列部分有序Q从而得以后的插入排序很快扑ֈ插入位置。我们下面将紧紧围绕q一Ҏ证明Shell排序法 的时间复杂度上界?br>    只要排序增量的第一个数?QShell排序法是正确的。但是不同的增量导致不同的旉复杂度。我们上面例子中 的增?1, 3, 7, 15, 31, …, 2^k-1)是用最q泛的增量序列之一Q可以证明用这个增量的旉复杂度ؓO(n√n)。这个证明很单,大家可以参看一些其它的资料Q我们今天不? 明它。今天我们证明,使用增量1, 2, 3, 4, 6, 8, 9, 12, 16, …, 2^p*3^qQ时间复杂度为O(n*(log n)^2)?br>    很显ӞM一个大?的正整数都可以表CZؓ2x+3yQ其中x和y是非负整数。于是,如果一个数列已l是2-排序的且? 3-排序的,那么对于此时数列中的每一个数A(i)Q它的左Ҏ它大的只有可能是A(i-1)。A2l对不可能比A12大,因ؓ10可以表示Z?和两 ?的和Q则A2<A4<A6<A9<A12。那么,在这个增量中?-排序时每个数找插入位|只需要比较一ơ。一共有n个数Q? 所?-排序是O(n)的。事实上Q这个增量中?-排序也是O(n)Q因为在2-排序之前Q这个数列已l是4-排序?-排序q的Q只看数列的奇数Ҏ 者偶数项Q即单看每一l)的话又成了刚才的样子。这个增量序列y妙就巧妙在,如果我们要进行h-排序Q那么它一定是2h-排序q且3h-排序q,于是? 理每个数A(i)的插入时只需要和A(i-h)q行比较。这个结论对于最开始几ơ(hD大时Q的h-排序同样成立Q当2h?h大于nӞ按照定义Q? 我们也可以认为数列是2h-排序?h-排序的,qƈ不媄响上q结论的正确性(你也可以认ؓh太大以致于排序时每一l里的数字不过3个,属于常数U)? 现在Q这个增量中的每一排序都是O(n)的,我们只需要数一下一p了多趟。也是_我们现在只需要知道小于n的数中有多少个数h2^p*3^q 的Ş式。要?^p*3^q不超qnQp的取值最多O(log n)个,q的取值最多也是O(log n)个,两两l合的话共有O(logn*logn)U情c于是,q样的增量排序需要跑O((log n)^2),每一的复杂度O(n)Qȝ复杂度ؓO(n*(log n)^2)。早pq了Q证明时间复杂度其实很有意思?br>    我们自然 会想Q有没有能复杂度降到O(nlogn)甚至更低的增量序列。很遗憾Q现在没有Q何迹象表明存在O(nlogn)的增量排序。但事实上,很多时? Shell排序的实际效率超q了O(nlogn)的排序算法?br><br>    后面我们介l三UO(nlogn)的排序算法和三种U性时间的? 序算法。最后我们将以外部排序和排序|络l束q一章节?br><br>    很多人问到我关于转脓的问题。我Ƣ迎除商业目的外M形式的{_论坛? Blog、Wiki、个人网站、PodCastQ甚臛_成ppt、pdfQ,但一定要注明出处Q最好保留原始链接。我的网站需要点反向链接才能在网l中? 存下去,大家也都可以xq且推广q个Blog。我一直支持cc版权协议Q因此发C文章中的问题或者想要补充什么东西尽提出来Q好让更多的人学习到? 东西。我昨天看Blog上原来写的一些东西,居然q着发现了几个错误式子和错别字,好奇大家居然没有提出来。发C问题真的要告诉我Q即使格式有炚w题也 要说一下,决不能让它那么错着。另外有什么徏议或x也请说一下,我希望听C同的声音不同的见解,好让我决定这cL章以后的发展方向?br><br>Matrix67 原创<br>转脓h明出?br><br><a title="Permanent link to 从零开始学法Q十U排序算法介l(上)" rel="bookmark"><u><font color="#800080">从零开始学法Q十U排序算法介l(中)</font></u></a><br> 本文被华丽的分割U分Z四段。对 于O(nlogn)的排序算法,我们详细介绍归ƈ排序q证明归q排序的旉复杂度,然后单介l堆排序Q之后给出快速排序的基本思想和复杂度证明。最后我 们将证明QO(nlogn)在理Z已经辑ֈ了最优。学qOI的h一般都学过q些很基的东西,大多数OIer们不必看了。ؓ了保持系列文章的完整性,? q是花时间写了一下?br><br>    首先考虑一个简单的问题Q如何在U性的旉内将两个有序队列合ƈZ个有序队列(q输出)Q?br><br>A 队列Q? 3 5 7 9<br>B队列Q? 2 7 8 9<br><br>    看上面的例子QAB两个序列都是已经有序的了。在l出数据已经有序的情况下Q我 们会发现很多奇的事Q比如,我们要输出的第一个数一定来自于q两个序列各自最前面的那个数。两个数都是1Q那么我们随便取Z个(比如A队列的那? 1Qƈ输出Q?br><br>A队列Q?s>1</s> 3 5 7 9<br>B队列Q? 2 7 8 9<br>输出Q?<br><br>    注意Q我们取Z一个数Q在原数列中删除q个数。删除操作是通过Ud队首指针? 现的Q否则复杂度高了?br>    现在QA队列打头的数变成3了,B队列的队首仍然是1。此Ӟ我们再比??哪个大ƈ输出的那个敎ͼ<br><br>A队列Q?s>1</s> 3 5 7 9<br>B队列Q?s>1</s> 2 7 8 9<br>输出Q? 1<br><br>    ? 下来的几步如下:<br><br>A队列Q?s>1</s> 3 5 7 9         A队列Q?s>1 3</s> 5 7 9         A队列Q?s>1 3 5</s> 7 9          A队列Q?s>1 3 5 7</s> 9<br>B队列Q?s>1 2</s> 7 8 9   ==>   B队列Q?s>1 2</s> 7 8 9   ==>   B队列Q?s>1 2</s> 7 8 9    ==>   B队列Q?s>1 2</s> 7 8 9     ……<br>输出Q? 1 2              输出Q? 1 2 3            输出Q? 1 2 3 5           输出Q? 1 2 3 5 7<br><br>    我希望你明白了这是怎么做的。这个做法显然是正确的,复杂 度显然是U性?br><br>    归ƈ排序(Merge Sort)会用到上面所说的合ƈ操作。给Z个数列,归ƈ排序利用合ƈ操作在O(nlogn)的时间内数列从到大排序。归q排序用的是分治 (Divide and Conquer)的思想。首先我们把l出的数列^分ؓ左右两段Q然后对两段数列分别q行排序Q最后用刚才的合q算法把q两D(已经排过序的Q数列合qؓ一 个数列。有Z?#8220;对左右两D|列分别排序时用的什么排?#8221;么?{案是:用归q排序。也是_我们递归地把每一D|列又分成两段q行上述操作。你不需? 兛_实际上是怎么操作的,我们的程序代码将递归调用该过E直到数列不能再分(只有一个数Qؓ止?br>    初看q个法时有Z误以为时间复杂度? 当高。我们下面给出的一个图用非递归的眼光来看归q排序的实际操作q程Q供大家参考。我们可以借助q个图证明,归ƈ排序法的时间复杂度? O(nlogn)?br><br>[3] [1] [4] [1] [5] [9] [2] [7]<br>  \ /     \ /     \ /     \ /<br>[1 3]   [1 4]   [5 9]   [2 7]<br>     \   /           \   /<br>   [1 1 3 4]       [2 5 7 9]<br>           \       /<br>       [1 1 2 3 4 5 7 9]<br><br>    上图中的每一?#8220; \ / ”表示的是上文所q的U性时间合q操作。上囄?行来图解归ƈ排序。如果有n个数Q表C成上图昄需要O(logn)行。每一行的合ƈ操作复杂度d? 是O(n)Q那么logn行的d杂度为O(nlogn)。这相当于用递归树的Ҏ对归q排序的复杂度进行了分析。假设,归ƈ排序的复杂度? T(n)QT(n)׃个T(n/2)和一个关于n的线性时间组成,那么T(n)=2*T(n/2)+O(n)。不断展开q个式子我们可以同样可以得到 T(n)=O(nlogn)的结论,你可以自p试。如果你能在U性的旉里把分别计算出的两组不同数据的结果合q在一PҎ T(n)=2*T(n/2)+O(n)=O(nlogn)Q那么我们就可以构造O(nlogn)的分ȝ法。这个结论后面经常用。我们将在计几何部分D 一大堆cM的例子?br>    如果你第一ơ见到这么诡异的法Q你可能会对<a target="_blank"><strong> <font color="#618898">q个</font></strong> </a>感兴? 分治是递归的一U应用。这是我们第一ơ接触递归q算。下面说的快速排序也是用的递归的思想。递归E序的复杂度分析通常和上面一Pd?Master Theory)可以化这个分析过E。主定理和本文内容离得太q,我们以后也不会用它,因此我们不介l它Q大家可以自己去查。有个名词在q里的话扑֭习资 料将变得非常ҎQ我最怕的是一个东西不知道叫什么名字,半天找不到资料?br><br>    归ƈ排序有一个有的副品。利用归q排序能够在 O(nlogn)的时间里计算出给定序列里逆序对的个数。你可以用Q何一U^衡二叉树来完成这个操作,但用归ƈ排序l计逆序Ҏ方便。我们讨论逆序对一? 是说的一个排列中的逆序对,因此q里我们假设所有数不相同。假如我们想要数1, 6, 3, 2, 5, 4中有多少个逆序对,我们首先把这个数列分为左右两Dc那么一个逆序对只可能有三U情况:两个数都在左边,两个数都在右边,一个在左一个在叟뀂在左右两段 分别处理完后Q线性合q的q程中我们可以顺便算出所有第三种情况的逆序Ҏ多少个。换句话_我们能在U性的旉里统计出A队列的某个数比B队列的某个数 大有多少U情c?br><br>A队列Q? 3 6         A队列Q?s>1</s> 3 6         A队列Q?s>1</s> 3 6         A队列Q?s>1 3</s> 6         A队列Q?s>1 3</s> 6<br>B队列Q? 4 5   ==>   B队列Q? 4 5   ==>   B队列Q?s>2</s> 4 5   ==>   B队列Q?s>2</s> 4 5   ==>   B队列Q?s>2 4</s> 5   ……<br>? 出:               输出Q?              输出Q? 2            输出Q? 2 3          输出Q? 2 3 4<br><br>    每一ơ从B队列取出一个数Ӟ我们q道了在A队列中有多少个数比B 队列的这个数大,它等于A队列现在q剩的数的个数。比如,当我们从B队列中取?Ӟ我们同时知道了A队列??两个数比2大。在合ƈ操作中我们不断更 新A队列中还剩几个数Q在每次从B队列中取Z个数时把当前A队列剩的数目加进最l答案里。这h们算Z所?#8220;大的数在前一半,的数在后一?#8221;的情 况,其余情况下的逆序对在q之前已l被递归地算q了?br><br>============================华丽的分? U?===========================<br><br>    堆排?Heap Sort)利用了堆(Heap)q种数据l构Q?a target="_blank"><strong> <font color="#618898">什么是堆?</font></strong> </a>Q? 堆的插入操作是^均常数的Q而删除一个根节点需要花费O(log n)的时间。因此,完成堆排序需要线性时间徏立堆Q把所有元素依ơ插入一个堆Q,然后用dO(nlogn)的时间不断取出最的那个数。只要堆会搞Q堆 排序׃搞。堆在那日志里有详l的说明Q因此这里不重复说了?br><br>============================华丽的分? U?===========================<br><br>    快速排?Quick Sort)也应用了递归的思想。我们想要把l定序列分成两段Qƈ对这两段分别q行排序。一U不错的x是,选取一个数作ؓ“关键?#8221;Qƈ把其它数分割Z 部分Q把所有小于关键字的数都放在关键字的左边,大于关键字的都放在右边,然后递归地对左边和右边进行排序。把该区间内的所有数依次与关键字比较Q我们就 可以在线性的旉里完成分割的操作。完成分割操作有很多有技巧性的实现ҎQ比如最常用的一U是定义两个指针Q一个从前往后找扑ֈ比关键字大的Q一个从? 往前找到比关键字小的,然后两个指针对应的元素交换位|ƈl箋Ud指针重复刚才的过E。这只是大致的方法,具体的实现还有很多细节问题。快速排序是我们最 常用的代码之一Q网上的快速排序代码五花八门,各种语言Q各U风格的都有。大家可以随便找一个来看看Q我说过了我们讲法但不讲如何实现。NOIp很简 单,很多人NOIp前就背了一个快速排序代码就上战Z。当时我把快速排序背完了Q抓紧时间还Z背了一下历Ԍ免得晚上听写又不及格?br>    ? 像归q排序,快速排序的旉复杂度很难计。我们可以看刎ͼ归ƈ排序的复杂度最坏情况下也是O(nlogn)的,而快速排序的最坏情冉|O(n^2)的? 如果每一ơ选的关键字都是当前区间里最大(或最)的数Q那么这样将使得每一ơ的规模只减一个数Q这和插入排序、选择排序{^方排序没有区别。这U情 况不是不可能发生。如果你每次选择关键字都是选择的该区间的第一个数Q而给你的数据恰好又是已经有序的,那你的快速排序就完蛋了。显Ӟ最好情冉|每一? 选的数正好就是中位数Q这把该区间^分ؓ两段Q复杂度和前面讨论的归ƈ排序一模一栗根据这一点,快速排序有一些常用的优化。比如,我们l常从数列中? 机取一个数当作是关键字Q而不是每ơL取固定位|上的数Q,从而尽可能避免某些Ҏ的数据所D的低效。更好的做法是随机取三个数ƈ选择q三个数的中? C为关键字。而对三个数的随机取值反而将p更多的时_因此我们的这三个数可以分别取数列的头一个数、末一个数和正中间那个数。另外,当递归C一? 深度发现当前区间里的数只有几个或十几个时Ql递归下去反而费Ӟ不如q回插入排序后的l果。这U方法同旉免了当数字太时递归操作出错的可能?br><br>    ? 面我们证明,快速排序算法的q_复杂度ؓO(nlogn)。不同的书上有不同的解释ҎQ这里我选用法D上的讲法。它更有技巧性一些,更有一些,需 要{几个弯才能想明白?br>    看一看快速排序的代码。正如我们提到过的那U分割方法,E序在经q若q次与关键字的比较后才进行一ơ交换,因此? 较的ơ数比交换次数更多。我们通过证明一ơ快速排序中元素之间的比较次数^均ؓO(nlogn)来说明快速排序算法的q_复杂度。证明的关键在于Q我们需 要算出某两个元素在整个算法过E中q行q比较的概率?br>    我们举一个例子。假如给Z1?0q?0个数Q第一ơ选择关键?它们分成了 {1,2,3,4,5,6}和{8,9,10}两部分,递归左边时我们选择?作ؓ关键字,使得左部分又被分割ؓ{1,2}和{4,5,6}。我们看刎ͼ 数字7与其它所有数都比较过一ơ,q样才能实现分割操作。同样地Q??q?个数都需要与3q行一ơ比较(除了它本w之外)。然而,3?决不可能怺? 较过Q??也不可能q行q比较,因ؓW一ơ出现在3?Q??之间的关键字把它们分割开了。也是_两个数A(i)和A(j)比较q,当且仅当W一 个满A(i)<=x<=A(j)的关键字x恰好是A(i)或A(j) Q假设A(i)比A(j))。我们称排序后第i的CؓZ(i)Q假设i<jQ那么第一ơ出现在Z(i)和Z(j)之间的关键字恰好是Z(i) 或Z(j)的概率ؓ2/(j-i+1)Q这是因为当Z(i)和Z(j)之间q不曾有q关键字ӞZ(i)和Z(j)处于同一个待分割的区_不管q个区间 有多大,不管递归到哪里了Q关键字的选择L随机的。我们得刎ͼZ(i)和Z(j)在一ơ快速排序中曄比较q的概率?/(j-i+1)?br>    ? 在有四个敎ͼ2,3,5,7。排序时Q相ȝ两个数肯定都被比较过Q????都有2/3的概率被比较q,2?之间被比较过?/4的可能。也是 _如果对这四个数做12ơ快速排序,那么2?????之间一共比较了12*3=36ơ,2???之间d比较?*2=16ơ,2? 之间q_比较?ơ。那么,12ơ排序中ȝ比较ơ数期望gؓ36+16+6=58。我们可以计出单次的快速排序^均比较了多少ơ:58/12=29 /6。其实,它就{于6Ҏ率之和,1+1+1+2/3+2/3+2/4=29/6。这其实是与期望值相关的一个公式?br>    同样圎ͼ如果有n 个数Q那么快速排序^均需要的比较ơ数可以写成下面的式子。ok=j-iQ我们能够最l得到比较次数的期望gؓO(nlogn)?br>   <img alt="" src="http://www.matrix67.com/blogimage/200704061.gif" border="0"><br>    q? 里用C一个知识:1+1/2+1/3+…+1/n与log n增长速度相同Q即Σ(1/n)=Θ(log n)。它的证明放在本文的最后?br><br>    ? 三种O(nlogn)的排序算法中Q快速排序的理论复杂度最不理惻I除了它以外今天说的另外两U算法都是以最坏情况O(nlogn)的复杂度q行排序。但 实践上看快速排序效率最高(不然为啥叫快速排序呢Q,原因在于快速排序的代码比其它同复杂度的法更简z,常数旉更小?br><br>    快速排 序也有一个有的副品:快速选择l出的一些数中第k的数。一U简单的Ҏ是用上qCQ一UO(nlogn)的算法对q些数进行排序ƈq回排序后数l的 Wk个元素。快速选择(Quick Select)法可以在^均O(n)的时间完成这一操作。它的最坏情况同快速排序一P也是O(n^2)。在每一ơ分割后Q我们都可以知道比关键字的 数有多少个,从而确定了关键字在所有数中是W几的。我们假讑օ键字是第m。如果k=mQ那么我们就扑ֈ了答案——第k元素即该关键字。否则,我们? 归地计算左边或者右边:当k<mӞ我们递归地寻扑ַ边的元素中第k的Q当k>mӞ我们递归地寻扑֏边的元素中第k-m的数。由于我? 不考虑所有的数的序Q只需要递归其中的一边,因此复杂度大大降低。复杂度q_U性,我们不再具体证了?br>    q有一U算法可以在最坏O(n) 的时间里扑ևWk元素。那是我见过的所有算法中最没有实用价值的法。那个O(n)只有理论价倹{?br><br>============================ 华丽的分割线============================<br><br>    我们前面证明q,仅仅依靠交换盔R元素的操作,复杂度只 能达到O(n^2)。于是,Z试交换距离更远的元素。当Z发现O(nlogn)的排序算法似乎已l是极限的时候,又是什么制U了复杂度的下界呢?? 们将要讨论的是更底层的东ѝ我们仍然假设所有的数都不相{?br>    我们L不断在数与数之间q行比较。你可以试试Q只?ơ比较绝对不可能l? 4个数排出序。每多进行一ơ比较我们就又多知道了一个大关p,?ơ比较中一共可以获?个大关pR?个大关pd?^4=16U组合方式,? 个数的顺序一共有4!=24U。也是_4ơ比较可能出现的l果数目不以区?4U可能的序。更一般地Q给你n个数叫你排序Q可能的{案共有n! 个,kơ比较只能区?^kU可能,于是只有2^k>=n!时才有可能排出顺序。等号两边取ҎQ于是,ln个数排序臛_需要log2(n!)ơ? 注意Q我们ƈ没有说明一定能通过log2(n!)ơ比较排出顺序。虽?^5=32过?!Q但q不以说明5ơ比较一定够。如何用5ơ比较确?? 数的大小关系q需要进一步研I。第一ơ例外发生在n=12的时候,虽然2^29>12!Q但现已证明l?2个数排序最需?0ơ比较。我们可以证 明log(n!)的增镉K度与nlogn相同Q即log(n!)=Θ(nlogn)。这是排序所需要的最的比较ơ数Q它l出了排序复杂度的一个下界? log(n!)=Θ(nlogn)的证明也附在本文最后?br>    <a target="_blank"><strong> <font color="#618898">q篇日志</font></strong> </a>的第 三题中证明log2(N)是最优时用到了几乎相同的Ҏ。那U?#8220;用天q称出重量不同的那个球至要U几?#8221;一c题目也可以用这U方法来解决。事实上Q这? 有一整套的理论,它叫做信息论。信息论是由香农(Shannon)提出的。他用对数来表示信息量,用熵来表C可能的情况的随机性,通过q算可以知道你目? 得到的信息能够怎样影响最l结果的定。如果我们的信息量是?为底的,那信息论变成信息学了。从Ҏ上说Q计机的一切信息就是以2为底的信息量 (bits=<u>bi</u>nary digi<u>ts</u>)Q因此我们常说香农是数字通信之父。信息论和热力学关系密切Q比如熵的概忉|直接 从热力学的熵定义引申q来的。和q个有关的东西已l严重偏题了Q这里不说了Q有兴趣可以ȝ《信息论与编码理论》。我对这个也很有兴趣Q半懂不懂的Q很? 了解更多的东西,有兴的同志不妨加入讨论。物理学真的很神奇,利用物理学可以解军_多纯数学问题Q我有时间的话可以D一些例子。我他妈的ؓ啥要选文U? 呢?br>    后面介l的三种排序是线性时间复杂度Q因为,它们排序时根本不是通过互相比较来确定大关pȝ?br><br><br>? 1Q?#931;(1/n)=Θ(log n)的证?br>    首先我们证明Q?#931;(1/n)=O(log n)。在式子1+1/2+1/3+1/4+1/5+…中,我们?/3变成1/2Q得两?/2加v来凑成一?Q再?/5,1/6?/7全部变成 1/4Q这样四?/4加v来又是一?。我们把所?/2^k的后?^k-1全部扩大ؓ1/2^kQ得这2^k个分式加h是一?。现 在,1+1/2+…+1/n里面产生了几?呢?我们只需要看于n的数有多个2的幂卛_。显Ӟl过数的扩大后原式各Ҏd为log n。O(logn)?#931;(1/n)的复杂度上界?br>    然后我们证明Q?#931;(1/n)=Ω(log n)。在式子1+1/2+1/3+1/4+1/5+…中,我们?/3变成1/4Q得两?/4加v来凑成一?/2Q再?/5,1/6?/7全部 变成1/8Q这样四?/8加v来又是一?/2。我们把所?/2^k的前?^k-1全部羃ؓ1/2^kQ得这2^k个分式加h是一? /2。现在,1+1/2+…+1/n里面产生了几?/2呢?我们只需要看于n的数有多个2的幂卛_。显Ӟl过数的~小后原式各Ҏd? /2*logn?#937;(logn)?#931;(1/n)的复杂度下界?br><br><br>?Qlog(n!)=Θ(nlogn)的证?br>    ? 先我们证明,log(n!)=O(nlogn)。显然n!<n^nQ两边取Ҏ我们得到log(n!)<log(n^n)Q? log(n^n)q于nlogn。因此,O(nlogn)是log(n!)的复杂度上界?br>    然后我们? 明,log(n!)=Ω(nlogn)。n!=n(n-1)(n-2)(n-3)….1Q把前面一半的因子全部~小到n/2Q后面一半因子全部舍去,昄 有n!>(n/2)^(n/2)。两边取ҎQlog(n!)>(n/2)log(n/2)Q后者即Ω(nlogn)。因 此,Ω(nlogn)是log(n!)的复杂度下界?br><br>今天写到q里了,大家帮忙校对?br>Matrix67原创<br>转脓h明出 ?br><a title="Permanent link to 从零开始学法Q十U排序算法介l(上)" rel="bookmark"><u><font color="#800080">从零开始学法Q十U排序算法介l(下)</font></u></a><br>那么Q有什么方法可以不用比较就能排 出顺序呢Q借助Hash表的思想Q多Ch都能惛_q样一U排序算法来?br>    我们假设l出的数字都在一定范围中Q那么我们就可以开一个范围相? 的数l,记录q个数字是否出现q。由于数字有可能有重复,因此Hash表的概念需要扩展,我们需要把数组cdҎ整型Q用来表C每个数出现的次数?br>    ? q样一个例子,假如我们要对数列3 1 4 1 5 9 2 6 5 3 5 9q行排序。由于给定数字每一个都于10Q因此我们开一??的整型数lT[i]Q记录每一个数出现了几ơ。读C个数字xQ就把对应的T[x]? 一?br><br>  A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9<br>               +---+---+---+---+---+---+---+---+---+---+<br>      ? ?iQ?| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |<br>               +---+---+---+---+---+---+---+---+---+---+<br>出现ơ数T[i]Q?| 0 | 2 | 1 | 2 | 1 | 3 | 1 | 0 | 0 | 2 |<br>               +---+---+---+---+---+---+---+---+---+---+<br><br>    最后,我们用一个指针从? 往后扫描一遍,按照ơ序输出0?Q每个数出现了几ơ就输出几个。假如给定的数是n个大不过m的自然数Q显然这个算法的复杂度是O(m+n)的?br><br>    ? 曄以ؓQ这是U性时间排序了。后来我发现我错了。再后来Q我发现我曾犯的错误是一个普遍的错误。很多h都以Z面的q个法是传说中的计数排序。问 题出在哪里了Qؓ什么它不是U性时间的排序法Q原因是Q这个算法根本不是排序算法,它根本没有对原数据进行排序?br><br><br><strong> ? 题一Qؓ什么说上述法没有Ҏ据进行排序?</strong> <br>STOP! You should think for a while.<br><br>    我们班有很多MM。和w高相差太远的MM在一赯定很别扭Q? 接个吻都要弯腰才行(<a target="_blank"><strong> <font color="#618898">猫</font></strong> </a>矮死了)。ؓ此,我希望给我们班的MM的n高排序。我们班MM的n高, 再离׃没有过2c的Q这很适合用我们刚才的法。我们在黑板上画一?00?00的数l,MM依次自曝w高Q我负责?#8220;?#8221;字统计h数。统计出? 了,从小到大依次?41, 143, 143, 147, 152, 153, …。这哪门子排序Q就一排数字对我有什么用Q我要知道的是哪个MM有多高。我们仅仅把元素的属性g到大列了出来,但我们没有对元素本nq行排序。也 是_我们需要知道输出结果的每个数值对应原数据的哪一个元素。下文提到的“排序法的稳定?#8221;也和属性g实际元素的区别有兟?br><br><br><strong> ? 题二Q怎样线性时间排序后的输出结果还原ؓ原数据中的元素?</strong> <br>STOP! You should think for a while.<br><br>    同样借助Hash表的思想Q我们立xCcM? 开散列的方法。我们用链表把属性值相同的元素串v来,挂在对应的T[i]上。每ơ读C个数Q在增加T[i]的同时我们把q个元素放进T[i]延出去? 链表里。这P输出l果时我们可以方便地获得原数据中的所有属性gؓi的元素?br><br>  A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9<br>               +---+---+---+---+---+---+---+---+---+---+<br>      数字 iQ?| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |<br>               +---+---+---+---+---+---+---+---+---+---+<br>出现ơ数T[i]Q?| 0 | 2 | 1 | 2 | 1 | 3 | 1 | 0 | 0 | 2 |<br>               +---+o--+-o-+-o-+-o-+-o-+--o+---+---+-o-+<br>                    |    |   |   |   |    |          |<br>                 +--+  +-+   |   |   +-+  +---+      |<br>                 |     |   A[1]  |     |      |     A[6]<br>               A[2]  A[7]    |  A[3]  A[5]   A[8]    |<br>                 |           |         |            A[12]<br>               A[4]        A[10]      A[9]<br>                                       |<br>                                      A[11]<br><br>    ? 象地_我们在地上摆10个桶Q每个桶~一个号Q然后把数据分门别类攑֜自己所属的桉。这U排序算法叫做桶式排?Bucket Sort)。本文最后你看到桶式排序的另一个用途?br>    链表写v来比较麻烦,一般我们不使用它。我们有更简单的Ҏ?br><br><br><strong> ? 题三Q同h输出元素本nQ你能想Z用链表的其它法么?</strong> <br>STOP! You should think for a while.<br><br>  A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9<br>               +---+---+---+---+---+---+---+---+---+---+<br>      数字 iQ?| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |<br>               +---+---+---+---+---+---+---+---+---+---+<br>出现ơ数T[i]Q?| 0 | 2 | 1 | 2 | 1 | 3 | 1 | 0 | 0 | 2 |<br>               +---+---+---+---+---+---+---+---+---+---+<br>修改后的T[i]Q?| 0 | 2 | 3 | 5 | 6 | 9 | 10| 10| 10| 12|<br>               +---+---+---+---+---+---+---+---+---+---+<br><br>    所有数都读入后Q我们修? T[i]数组的|使得T[i]表示数字i可能的排名的最大倹{比如,1最差排名第二,3最q可以排到第五。T数组的最后一个数应该{于输入数据的数字个 数。修改T数组的操作可以用一ơ线性的扫描累加完成?br>    我们q需要准备一个输出数l。然后,我们从后往前扫描A数组Q依照T数组的指CZ? 把原数据的元素直接放到输出数l中Q同时T[i]的值减一。之所以从后往前扫描A数组Q是因ؓq样输出l果才是E_的。我们说一个排序算法是E_? (Stable)Q当法满q样的性质Q属性值相同的元素Q排序后前后位置不变Q本来在前面的现在仍然在前面。不要觉得排序算法是否具有稳定性似乎关p? 不大Q排序的E_性在下文的某个问题中变得非帔R要。你可以倒回ȝ看前面说的七U排序算法哪些是E_的?br>    例子中,A数组最后一个数9 所对应的T[9]=12Q我们直接把9攑֜待输出序列中的第12个位|,然后T[9]变成11Q这样下一ơ再出现9时就应该攑֜W?1位)?br><br>A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9 <--<br>T[i]= 0, 2, 3, 5, 6, 9, 10, 10, 10, 11<br>Ans = _ _ _ _ _ _ _ _ _ _ _ 9<br><br>    接下来的几步如下Q?br><br>A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 <--<br>T[i]= 0, 2, 3, 5, 6, 8, 10, 10, 10, 11<br>Ans = _ _ _ _ _ _ _ _ 5 _ _ 9<br><br>A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5, 3 <--<br>T[i]= 0, 2, 3, 4, 6, 8, 10, 10, 10, 11<br>Ans = _ _ _ _ 3 _ _ _ 5 _ _ 9<br><br>A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5 <--<br>T[i]= 0, 2, 3, 4, 6, 7, 10, 10, 10, 11<br>Ans = _ _ _ _ 3 _ _ 5 5 _ _ 9<br><br>    q种法? 做计数排?Counting Sort)。正性和复杂度都是显然的?br><br><br><strong> 问题四:l定数的数据范围大了该怎么 办?</strong> <br>STOP! You should think for a while.<br><br>    前面的算法只有在数据的范围不大时才可行,如果l定的数在长整范围内的话Q这个算法是不可行的Q因? 你开不下q么大的数组。Radix排序(Radix Sort)解决了这个难题?br>    昨天我没事翻了一下初中(9班)时的同学录,回忆了一? q去。我把比较感兴趣的MM的生日列在下面(l对真实Q。如果列表中的哪个MM有幸看到了这日志(几乎不可能)Q左边的Support栏有我的电子联系 方式Q我想知道你们怎么样了。排名不分先后?br> </strong> <ul> <li><strong style="color: #0000ff;">19880818<br> </strong></li> <li><strong style="color: #0000ff;">19880816<br> </strong></li> <li><strong style="color: #0000ff;">19890426<br> </strong></li> <li><strong style="color: #0000ff;">19880405<br> </strong></li> <li><strong style="color: #0000ff;">19890125<br> </strong></li> <li><strong style="color: #0000ff;">19881004<br> </strong></li> <li><strong style="color: #0000ff;">19881209<br> </strong></li> <li><strong style="color: #0000ff;">19890126<br> </strong></li> <li><strong style="color: #0000ff;">19890228 </strong></li> </ul> <p><strong style="color: #0000ff;"><br>    q就是我的数据了。现在,我要l这些数排序。假如我的电脑只能开?..99的数l,那计数排序算法最多对两位数进行排序。我把 每个八位C位两位地分成四段Q图1Q,分别q行四次计数排序。地球h都知道月份相同时应该看哪一日,因此我们看月份的大小时应该事先保证日已经有序。换 句话_我们先对“最不重?#8221;的部分进行排序。我们先Ҏ有数的最后两位进行一ơ计数排序(?Q。注意观??6LMM??6LMMQ本ơ排 序中它们的属性值相同,׃计数排序是稳定的Q因?月䆾那个排完后依然在1月䆾那个的前头。接下来我们对百位和千位q行排序Q图3Q。你可以看到两个 26日的MM在这一ơ排序中分出了大,而月份相同的MM依然保持日数有序Q因数排序是E_的)。最后我们对q䆾排序Q图4Q,完成整个法。大安 是跨世纪的好儿童Q因此没有图5了?br><br>       <img alt="" src="http://www.matrix67.com/blogimage/200704131.gif" border="0"><br><br>    q? U算法显然是正确的。它的复杂度一般写成O(d*(n+m))Q其中n表示n个数Qm是我开的数l大(本例中m=100Q,d是一个常数因子(本例? d=4Q。我们认为它也是U性的?br><br><br><strong> 问题五:q样的排序方法还有什么致命的~陷Q?/strong> <br>STOP! You should think for a while.<br><br>    ? 使数据有30位,我们也可以用d=5?的Radix法q行排序。但Q要是给定的数据有无I多位怎么办?有h_q可能么。这是可能的Q比如给定的数据 是小敎ͼ更准地_实数Q。基于比较的排序可以区分355/113?#960;? 个大Q但你不知道Radix排序需要精到哪一位。这下惨了,实数的出现把貌似高科技的线性时间排序打回了农业时代。这Ӟ桶排序再度出山,挽救了线性时 间排序悲惨的命运?br><br><br><strong> 问题六:如何对实数进行线性时间排序?</strong> <br>STOP! You should think for a while.<br><br>    ? 们把问题化一下,l出的所有数都是0?之间的小数。如果不是,也可以把所有数同时除以一个大整数从而{化ؓq种形式。我们依然设立若q个Ӟ比如Q以 数点后面一位数Z据对所有数q行划分。我们仍然用链表把同一cȝC在一P不同的是Q每一个链表都是有序的。也是_每一ơ读C个新的数都要q? 行一ơ插入排序。看我们的例子:<br><br>      A[]= 0.12345, 0.111, 0.618, 0.9, 0.99999<br>               +---+---+---+---+---+---+---+---+---+---+<br>      十分位: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |<br>               +---+-o-+---+---+---+---+-o-+---+---+-o-+<br>                     |                   |           |<br>                   A[2]=0.111          A[3]=0.618   A[4]=0.9<br>                     |                               |<br>                   A[1]=0.12345                     A[5]=0.99999<br><br>    假如再下一个读入的数是 0.122222Q这个数需要插入到十分位ؓ1的那个链表里适当的位|。我们需要遍历该链表直到扑ֈW一个比0.122222大的敎ͼ在例子中则应该插? 到链表中A[2]和A[1]之间。最后,我们按顺序遍历所有链表,依次输出每个链表中的每个数?br>    q个法昄是正的Q但复杂度显然不? U性。事实上Q这U算法最坏情况下是O(n^2)的,因ؓ当所有数的十分位都相同时法是一个插入排序。和原来一P我们下面要计算法的q_旉复杂 度,我们希望q种法的^均复杂度是线性的?br>    q次^均复杂度我们用最W的办法。我们将出所有可能出现的情况的L间复杂度Q除以ȝ 情况敎ͼ得到q_的复杂度是多?br>    每个数都可能属于10个桶中的一个,n个数ȝ情况?0^nU。这个值是我们庞大的算式的分母部分? 如果一个桶里有K个元素,那么只与q个桶有关的操作有O(K^2)ơ,它就是一ơ插入排序的操作ơ数。下面计,?0^nU情况中QK0=1有多种? cK0=1表示Qn个数中只有一个数?hQ其余n-1个数的十分位只能在1?中选择。那么K0=1的情冉|C(n,1)*9^(n-1)Q而每 个K0=1的情况在0h中将产生1^2的复杂度。类似地QKi=p的情冉|为C(n,p)*9^(n-p)Q复杂度总计为C(n,p)*9^(n- p)*p^2。枚举所有K的下标和p|累加hQ这个算式大家应该能写出来了Q但是这?#8230;…怎么啊。别怕,我们是搞计算机的Q拿出点和MO不一L? 西来。于是,Mathematica 5.0隆重dQ我做数学作业全靠它。它帮我们化简q个复杂的式子?br><img alt="" src="http://www.matrix67.com/blogimage/200704132.gif" border="0"><br><br>    ? 们遗憑֜发现Q虽然常数因子很(只有0.1Q,但算法的q_复杂度仍然是qx的。等一下,1/10的那?0是我们桶的个数吗Q那么我们ؓ什么不把桶? 个数弄大点?我们q脆用m来表C桶的个敎ͼ重新计算一ơ:<br><img alt="" src="http://www.matrix67.com/blogimage/200704133.gif" border="0"><br><br>    ? 出来Q操作次CؓO(n+n^2/m)。发C么,如果m=Θ(n)的话Q^均复杂度变成了O(n)。也是_当桶的个数等于输入数据的个数Ӟ? 法是q_U性的?br>    我们在Hash表开散列的介l中重新提到q个l论?br><br>    且慢Q还有一个问题?0个桶以十分位? 数字归类Q那么n个桶用什么方法来分类呢?注意Q分cȝҎ需要满I一Q一个数分到每个桉的概率相同(q样才有我们上面的结论)Q二Q所有桶里容U_ 素的范围必须是连l的。根据这两个条gQ我们有办法把所有数恰好分ؓncR我们的输入数据不是都在0?之间么?只需要看q些C以n的整数部分是多少? 行了Q读C个数后乘以n取整得几插入到几号桉。这本质上相当于把区间[0,1)q_分成n份?br><br><br><strong> 问题七:? 没有复杂度低于线性的排序法</strong> <br>STOP! You should think for a while.<br><br>    我们从O(n^2)走向O(nlogn)Q又从O(nlogn)走向U性, 每一ơ我们都讨论了复杂度下限的问题,Ҏ讨论的结果提Z更优的算法。这ơȝ不行了,不可能有比线性还快的法了,因ؓ——你d、输出数据至就需 要线性的旉。排序算法之旅在U性时间复杂度q一站终止了Q所有十U排序算法到q里介绍完毕了?br><br><br><br>    文章有越写越? 的趋势了Q我查v来也来篏了。我又看了三遍,应该没问题了。群众的眼睛是雪亮的Q恳请大家帮我找错?br></strong></p> <strong style="color: #0000ff;"> </strong><br> <img src ="http://www.shnenglu.com/yuqilin1228/aggbug/110617.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.shnenglu.com/yuqilin1228/" target="_blank">LynnRaymond</a> 2010-03-26 21:54 <a href="http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110617.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>【{载】位q算介及实用技?/title><link>http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110616.html</link><dc:creator>LynnRaymond</dc:creator><author>LynnRaymond</author><pubDate>Fri, 26 Mar 2010 13:48:00 GMT</pubDate><guid>http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110616.html</guid><wfw:comment>http://www.shnenglu.com/yuqilin1228/comments/110616.html</wfw:comment><comments>http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110616.html#Feedback</comments><slash:comments>1</slash:comments><wfw:commentRss>http://www.shnenglu.com/yuqilin1228/comments/commentRss/110616.html</wfw:commentRss><trackback:ping>http://www.shnenglu.com/yuqilin1228/services/trackbacks/110616.html</trackback:ping><description><![CDATA[<a title="Permanent link to 位运简介及实用技巧(一Q:基础? rel="bookmark">? q算介及实用技巧(一Q:基础?/a>   FROM:Matrix67大牛 <br>dq底写的关于<a target="_blank">位运?/a>的日志是q个Blog里少数大受欢q的文章之一Q很多h都希望我能不断完善那文章。后来我看到了不其 它的资料Q学习到了更多关于位q算的知识,有了重新整理位运技巧的x。从今天h开始写q一pd位运讲解文章,与其说是原来那篇文章? follow-upQ不如说是一个remake。当焉先我q是从最基础的东西说赗?br><br>什么是位运?<br>    E序中的所有数在计 机内存中都是以二进制的形式储存的。位q算说穿了,是直接Ҏ数在内存中的二进制位q行操作。比如,andq算本来是一个逻辑q算W,但整C整数? 间也可以q行andq算。D个例子,6的二q制?10Q?1的二q制?011Q那? and 11的结果就?Q它是二q制对应位进行逻辑q算的结果(0表示FalseQ?表示TrueQ空位都?处理Q:<br>     110<br>AND 1011<br>----------<br>    0010  -->  2<br>    ׃位运直接对内存数据q行操作Q不需要{? 十进Ӟ因此处理速度非常快。当然有Z_q个快了有什么用Q计? and 11没有什么实际意义啊。这一pd的文章就告诉你Q位q算到底可以q什么,有些什么经典应用,以及如何用位q算优化你的E序?br><br><br>Pascal 和C中的位运符?br>    下面的a和b都是整数cdQ则Q?br>C语言  |  Pascal语言<br>-------+-------------<br>a & b  |  a and b<br>a | b  |  a or b<br>a ^ b  |  a xor b<br>  ~a   |   not a<br>a << b |  a shl b<br>a >> b |  a shr b<br>    ? 意C中的逻辑q算和位q算W号是不同的?20|1314=1834Q但520||1314=1Q因为逻辑q算?20?314都相当于True。同? 的,!a和~a也是有区别的?br><br><br>各种位运的使用<br>    === 1. andq算 ===<br>    andq算? 常用于二q制取位操作Q例如一个数 and 1的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶Q二q制的最末位?表示该数为偶敎ͼ最末位?表示该数为奇?<br><br>    === 2. orq算 ===<br>    orq算通常用于二进制特定位上的无条件赋|例如一个数or 1的结果就是把二进制最末位变成1。如果需要把二进制最末位变成0Q对q个数or 1之后再减一可以了Q其实际意义是把这个数变成最接近的偶数?br><br>    === 3. xorq算 ===<br>    xor q算通常用于对二q制的特定一位进行取反操作,因ؓ异或可以q样定义Q??异或0都不变,异或1则取反?br>    xorq算的逆运是它本w, 也就是说两次异或同一个数最后结果不变,?a xor b) xor b = a。xorq算可以用于单的加密Q比如我惛_我MM?314520Q但怕别人知道,于是双方U定拿我的生?9880516作ؓ密钥?314520 xor 19880516 = 20665500Q我把20665500告诉MM。MM再次计算20665500 xor 19880516的|得到1314520Q于是她明白了我的企图?br>    下面我们看另外一个东ѝ定义两个符?和@Q我怎么找不到那个圈 里有个叉的字W)Q这两个W号互ؓ逆运,也就是说(x # y) @ y = x。现在依ơ执行下面三条命令,l果是什么?<br><code>x <- x # y<br>y <- x @ y<br>x <- x @ y</code><br>    执行了第一句后x变成了x # y。那么第二句实质是y <- x # y @ yQ由?和@互ؓ逆运,那么此时的y变成了原来的x。第三句中x实际上被赋gؓ(x # y) @ xQ如?q算h交换律,那么赋值后x变成最初的y了。这三句话的l果是,x和y的位|互换了?br>    加法和减法互为逆运, q且加法满交换律。把#换成+Q把@换成-Q我们可以写Z个不需要时变量的swapq程(Pascal)?br><code>procedure swap(var a,b:longint);<br>begin<br>   a:=a + b;<br>   b:=a - b;<br>   a:=a - b;<br>end;</code><br>    好了Q刚才不是说xor的逆运是它本w吗Q于是我们就有了一个看h非常诡异? swapq程Q?br><code>procedure swap(var a,b:longint);<br>begin<br>   a:=a xor b;<br>   b:=a xor b;<br>   a:=a xor b;<br>end;</code><br><br>    === 4. notq算 ===<br>    notq算的定义是把内存中??全部取反。用notq算时要格外心Q你需要注意整数类型有没有W号? 如果not的对象是无符h敎ͼ不能表示负数Q,那么得到的值就是它与该cd上界的差Q因为无W号cd的数是用$0000?FFFF依次表示的。下面的 两个E序Q仅语言不同Q均q回65435?br><code>var<br>   a:word;<br>begin<br>   a:=100;<br>   a:=not a;<br>   writeln(a);<br>end.</code><br><code>#include <stdio.h><br>int main()<br>{<br>    unsigned short a=100;<br>    a = ~a;<br>    printf( "%d\n", a );    <br>    return 0;<br>}</code><br>    ? 果not的对象是有符L整数Q情况就不一样了Q稍后我们会?#8220;整数cd的储?#8221;节中提到?br><br>    === 5. shlq算 ===<br>    a shl bpC把a转ؓ二进制后左移b位(在后面添b?Q。例?00的二q制?100100Q?10010000转成十进制是400Q那?00 shl 2 = 400。可以看出,a shl b的值实际上是a乘以2的bơ方Q因为在二进制数后添一?q当于该数乘以2?br>    通常 认ؓa shl 1比a * 2更快Q因为前者是更底层一些的操作。因此程序中乘以2的操作请量用左UM位来代替?br>    定义一些常量可能会 用到shlq算。你可以方便地用1 shl 16 - 1来表C?5535。很多算法和数据l构要求数据规模必须?的幂Q此时可以用shl来定义Max_N{常量?br><br>    === 6. shrq算 ===<br>    和shl怼Qa shr b表示二进制右Ub位(L末b位)Q相当于a除以2的bơ方Q取_。我们也l常用shr 1来代替div 2Q比如二分查找、堆的插入操作等{。想办法用shr代替除法q算可以使程序效率大大提高。最大公U数的二q制法用除?操作来代替慢得出奇的modq? ,效率可以提高60%?br><br><br>位运的单应?br>    有时我们的程序需要一个规模不大的Hash表来记录状态。比如,做数 独时我们需?7个Hash表来l计每一行、每一列和每一个小九宫格里已经有哪些数了。此Ӟ我们可以?7个小?^9的整数进行记录。例如,一个只? ??的小九宫格就用数?8表示Q二q制?00010010Q,而某一行的状态ؓ511则表C一行已l填满。需要改变状态时我们不需要把q个数{ 成二q制修改后再转回去,而是直接q行位操作。在搜烦Ӟ把状态表C成整数可以更好地进行判重等操作?a target="_blank">q道?/a>是在搜烦中用位q算加速的l典例子。以后我们会看到更多的例子?br>    下面列D了一些常见的 二进制位的变换操作?br><br>    功能              |           CZ            |    位运?br>----------------------+---------------------------+--------------------<br>? 掉最后一?nbsp;         | (101101->10110)           | x shr 1<br>在最后加一? 0         | (101101->1011010)         | x shl 1<br>在最后加一?         | (101101->1011011)         | x shl 1+1<br>把最后一位变?       | (101100->101101)          | x or 1<br>把最后一位变?       | (101101->101100)          | x or 1-1<br>最后一位取?nbsp;         | (101101->101100)          | x xor 1<br>把右数第k位变?      | (101001->101101,k=3)      | x or (1 shl (k-1))<br>把右数第k位变?      | (101101->101001,k=3)      | x and not (1 shl (k-1))<br>xWk位取 ?nbsp;        | (101001->101101,k=3)      | x xor (1 shl (k-1))<br>取末? ?nbsp;             | (1101101->101)            | x and 7<br>取末k ?nbsp;              | (1101101->1101,k=5)       | x and (1 shl k-1)<br>取右 数第k?nbsp;          | (1101101->1,k=4)          | x shr (k-1) and 1<br>把末k 位变?          | (101001->101111,k=4)      | x or (1 shl k-1)<br>末k位取 ?nbsp;            | (101001->100110,k=4)      | x xor (1 shl k-1)<br>把右边连 l的1变成0    | (100101111->100100000)    | x and (x+1)<br>把右L一?变成 1    | (100101111->100111111)    | x or (x+1)<br>把右边连l的0变成1    | (11011000->11011111)      | x or (x-1)<br>取右边连l的1         | (100101111->1111)         | (x xor (x+1)) shr 1<br>L双vW一?的左?| (100101000->1000)         | x and (x xor (x-1))<br><br>    最后这一个在树状数组 中会用到?br><br><br>Pascal和C中的16q制表示<br>    Pascal中需要在16q制数前?W号表示QC中需要在前面? 0x来表C。这个以后我们会l常用到?br><br>整数cd的储?br>    我们前面所说的位运都没有涉及负数Q都假设q些q算是在 unsigned/wordcdQ只能表C正数的整型Q上q行操作。但计算机如何处理有正负W号的整数类型呢Q下面两个程序都是考察16位整数的储存方式 Q只是语a不同Q?br><code>var<br>   a,b:integer;<br>begin<br>   a:=$0000;<br>   b:=$0001;<br>   write(a,' ',b,' ');<br>   a:=$FFFE;<br>   b:=$FFFF;<br>   write(a,' ',b,' ');<br>   a:=$7FFF;<br>   b:=$8000;<br>   writeln(a,' ',b);<br>end.</code><br><code>#include <stdio.h><br>int main()<br>{<br>    short int a, b;<br>    a = 0×0000;<br>    b = 0×0001;<br>    printf( "%d %d ", a, b );<br>    a = 0xFFFE;<br>    b = 0xFFFF;<br>    printf( "%d %d ", a, b );<br>    a = 0×7FFF;<br>    b = 0×8000;<br>    printf( "%d %d\n", a, b );<br>    return 0;<br>}</code><br>    两个E序的输出均? 1 -2 -1 32767 -32768。其中前两个数是内存值最的时候,中间两个数则是内存值最大的时候,最后输出的两个数是正数与负数的分界处。由此你可以清楚地看到计机? 如何储存一个整数的Q计机?0000?7FFF依次表示0?2767的数Q剩下的$8000?FFFF依次表示-32768?1的数?2? 有符h数的储存方式也是cM的。稍加注意你会发玎ͼ二进制的W一位是用来表示正负LQ?表示正,1表示负。这里有一个问题:0本来既不是正敎ͼ也不? 负数Q但它占用了$0000的位|,因此有符L整数cd范围中正C数比负数一个。对一个有W号的数q行notq算后,最高位的变化将D正负颠倒, q且数的l对g?。也是_not a实际上等?a-1。这U整数储存方式叫?#8220;补码”?br><br>最后还有两句话<br>    Matrix67 原创<br>    转脓h明出?br><br><a title="Permanent link to 位运简介及实用技巧(二)Q进阶篇(1)" rel="bookmark">? q算介及实用技巧(二)Q进阶篇(1)</a> <br> <p>=====   真正强的东西来了Q?nbsp;  =====<br><br>二进制中?有奇Cq是偶数?br>    我们可以用下面的代码来计? 一?2位整数的二进制中1的个数的奇偶性,当输入数据的二进制表C里有偶C数字1时程序输?Q有奇数个则输出1。例如,1314520的二q制 101000000111011011000中有9?Q则x=1314520时程序输??br><code>var<br>   i,x,c:longint;<br>begin<br>   readln(x);<br>   c:=0;<br>   for i:=1 to 32 do<br>   begin<br>      c:=c + x and 1;<br>      x:=x shr 1;<br>   end;<br>   writeln( c and 1 );<br>end.</code><br>    但这L效率q不高,位运的奇之处q? 没有体现出来?br>    同样是判断二q制?的个数的奇偶性,下面q段代码强了。你能看个代码的原理吗?<br><code>var<br>   x:longint;<br>begin<br>   readln(x);<br>   x:=x xor (x shr 1);<br>   x:=x xor (x shr 2);<br>   x:=x xor (x shr 4);<br>   x:=x xor (x shr 8);<br>   x:=x xor (x shr 16);<br>   writeln(x and 1);<br>end.</code><br>    Z说明 上面q段代码的原理,我们q是?314520出来说事?314520的二q制?01000000111011011000Q第一ơ异或操作的l果? 下:<br><br>    00000000000101000000111011011000<br>XOR  0000000000010100000011101101100<br>---------------------------------------<br>    00000000000111100000100110110100<br><br>    ? 到的l果是一个新的二q制敎ͼ其中双vWi位上的数表示原数中第i和i+1位上有奇C1q是偶数?。比如,最双那个0表示原数末两位有偶数?Q右 L3位上?pC原数的q个位置和前一个位|中有奇C1。对q个数进行第二次异或的结果如下:<br><br>    00000000000111100000100110110100<br>XOR   000000000001111000001001101101<br>---------------------------------------<br>    00000000000110011000101111011001<br><br>    l? 果里的每?表示原数的该位置及其前面三个位置中共有奇C1Q每?pC原数对应的四个位置上共偶数?。一直做到第五次异或l束后,得到的二q制? 的最末位pC整?2位数里有多少?Q这是我们最l想要的{案?br><br><br>计算二进制中?的个?br>    同样假设x是一? 32位整数。经q下面五ơ赋值后Qx的值就是原数的二进制表CZ数字1的个数。比如,初始时x?314520Q网友抓狂:能不能换一个数啊)Q那么最? x变成了9Q它表示1314520的二q制中有9??br><code>x := (x and $55555555) + ((x shr 1) and $55555555); <br>x := (x and $33333333) + ((x shr 2) and $33333333); <br>x := (x and $0F0F0F0F) + ((x shr 4) and $0F0F0F0F); <br>x := (x and $00FF00FF) + ((x shr 8) and $00FF00FF); <br>x := (x and $0000FFFF) + ((x shr 16) and $0000FFFF); </code><br>    Z便于解说Q我们下面仅说明q个E序是如何对一?位整数进 行处理的。我们拿数字211Q我们班某MM的生日)来开刀?11的二q制?1010011?br><br>+---+---+---+---+---+---+---+---+<br>| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |   <---原数<br>+---+---+---+---+---+---+---+---+<br>|  1 0  |  0 1  |  0 0  |  1 0  |   <---W一ơ运后<br>+-------+-------+-------+-------+<br>|    0 0 1 1    |    0 0 1 0    |   <---W二ơ运后<br>+---------------+---------------+<br>|        0 0 0 0 0 1 0 1        |   <---W三ơ运后Q得Cؓ5<br>+-------------------------------+<br><br>    ? 个程序是一个分ȝ思想。第一ơ我们把每相ȝ两位加v来,得到每两位里1的个敎ͼ比如前两?0pC原数的前两位有2?。第二次我们l箋两两? 加,10+01=11Q?0+10=10Q得到的l果?0110010Q它表示原数?位有3?Q末4位有2?。最后一ơ我们把0011?010 加v来,得到的就是整个二q制?的个数。程序中巧妙C用取位和右移Q比如第二行?33333333的二q制?0110011001100….Q用 它和x做andq算q当于?为单位间隔取数。shr的作用就是让加法q算的相同数位对齐?br><br><br>二分查找32位整数的前导0个数<br>    q? 里用的C语言Q我直接Copy的Hacker's Delight上的代码。这D代码写成C要好看些Q写成Pascal的话会出现很多begin和endQ搞得代码很隄。程序思想是二分查找,应该很简 单,我就不细说了?br><code>int nlz(unsigned x)<br>{<br>   int n;<br><br>   if (x == 0) return(32);<br>   n = 1;<br>   if ((x >> 16) == 0) {n = n +16; x = x <<16;}<br>   if ((x >> 24) == 0) {n = n + 8; x = x << 8;}<br>   if ((x >> 28) == 0) {n = n + 4; x = x << 4;}<br>   if ((x >> 30) == 0) {n = n + 2; x = x << 2;}<br>   n = n - (x >> 31);<br>   return n;<br>}</code><br><br><br>只用位运来? l对?br>    q是一个非常有的问题。大家先自己x吧,Ctrl+A昄{案?br>    {案Q假设x?2位整敎ͼ则x xor (not (x shr 31) + 1) + x shr 31的结果是x的绝对?br>    x shr 31是二q制的最高位Q它用来表示x的符受如果它?Qx为正Q,则not (x shr 31) + 1{于$00000000Q异或Q何数l果都不变;如果最高位?QxQ,则not (x shr 31) + 1{于$FFFFFFFFQx异或它相当于所有数位取反,异或完后再加一?br><br><br>高低位交?br>    <a target="_blank">q个?/a>实际上是我出的,做ؓ学校内部NOIp模拟赛的W一题。题目是q样Q?br><br> </p> <blockquote>    l出一个小?^32的正整数。这个数可以用一?2位的二进制数表示Q不?2位用0补Q。我们称q个二进 制数的前16位ؓ“高位”Q后16位ؓ“低位”。将它的高低位交换,我们可以得到一个新的数。试问这个新的数是多(用十q制表示Q?br>  例如Q? ?314520用二q制表示?000 0000 0001 0100 0000 1110 1101 1000Q添加了11个前?补?2位)Q其中前16位ؓ高位Q即0000 0000 0001 0100Q后16位ؓ低位Q即0000 1110 1101 1000。将它的高低位进行交换,我们得到了一个新的二q制?000 1110 1101 1000 0000 0000 0001 0100。它x十进制的249036820? <p> </p> </blockquote> <p><br>    当时几乎没有人想到用一句位操作来代替冗长的E序。用位q算的话两句话就完了?br><code>var<br>   n:dword;<br>begin<br>   readln( n );<br>   writeln( (n shr 16) or (n  shl 16) );<br>end.</code><br>    而事实上QPascal有一个系l函数swap直接可以用?br><br><br>? q制逆序<br>    下面的程序读入一?2位整数ƈ输出它的二进制倒序后所表示的数?br>    输入Q? 1314520    Q二q制?0000000000101000000111011011000Q?br>    输出Q? 460335104  Q二q制?0011011011100000010100000000000Q?br><code>var<br>   x:dword;<br>begin<br>   readln(x);<br>   x := (x and $55555555) shl  1 or (x and $AAAAAAAA) shr  1;<br>   x := (x and $33333333) shl  2 or (x and $CCCCCCCC) shr  2;<br>   x := (x and $0F0F0F0F) shl  4 or (x and $F0F0F0F0) shr  4;<br>   x := (x and $00FF00FF) shl  8 or (x and $FF00FF00) shr  8;<br>   x := (x and $0000FFFF) shl 16 or (x and $FFFF0000) shr 16;<br>   writeln(x);<br>end.</code><br>    它的原理和刚才求二进制中1 的个数那个例题是大致相同的。程序首先交换每盔R两位上的敎ͼ以后把互怺换过的数看成一个整体,l箋q行?位ؓ单位、以4位ؓ单位的左叛_换操作。我 们再ơ用8位整?11来演C程序执行过E:<br>+---+---+---+---+---+---+---+---+<br>| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |   <---原数<br>+---+---+---+---+---+---+---+---+<br>|  1 1  |  1 0  |  0 0  |  1 1  |   <---W一ơ运后<br>+-------+-------+-------+-------+<br>|    1 0 1 1    |    1 1 0 0    |   <---W二ơ运后<br>+---------------+---------------+<br>|        1 1 0 0 1 0 1 1        |   <---W三ơ运后<br>+-------------------------------+<br><br><br>Copyright 也很?br><code>writeln('Matrix' , 42 XOR 105 , '原创Q{贴请注明出处');</code></p> <a title="Permanent link to 位运简介及实用技巧(三)Q进阶篇(2)" rel="bookmark">? q算介及实用技巧(三)Q进阶篇(2)</a> <br> <p>今天我们来看两个E微复杂一点的例子?br><br>n皇后问题位运版<br>    n皇后问题是啥我就不说了吧Q学~程的肯定都见过。下? 的十多行代码是n皇后问题的一个高效位q算E序Q看到过的h都夸它牛。初始时Qupperlim:=(1 shl n)-1。主E序调用test(0,0,0)后sum的值就是n皇后ȝ解数。拿q个MUSACOQ?.3sQ暴爽?br><code>procedure test(row,ld,rd:longint);<br>var<br>      pos,p:longint;<br>begin<br><br>{ 1}  if row<>upperlim then<br>{ 2}  begin<br>{ 3}     pos:=upperlim and not (row or ld or rd);<br>{ 4}     while pos<>0 do<br>{ 5}     begin<br>{ 6}        p:=pos and -pos;<br>{ 7}        pos:=pos-p;<br>{ 8}        test(row+p,(ld+p)shl 1,(rd+p)shr 1);<br>{ 9}     end;<br>{10}  end<br>{11}  else inc(sum);<br><br>end;</code><br>    ? 一看似乎完全摸不着头脑Q实际上整个E序是非常容易理解的。这里还是徏议大家自己单步运行一探究竟,实在没研I出来再看下面的解说?br><br><img alt="" src="http://www.matrix67.com/blogimage/200707261.gif" border="0">  <img alt="" src="http://www.matrix67.com/blogimage/200707262.gif" border="0"><br>    ? 普通算法一Pq是一个递归q程Q程序一行一行地L可以攄后的地方。过E带三个参数Qrow、ld和rdQ分别表C在U列和两个对角线方向的限制条? 下这一行的哪些地方不能放。我们以6×6的棋盘ؓ例,看看E序是怎么工作的。假讄在已l递归到第四层Q前三层攄子已l标在左图上了。红艌Ӏ蓝色和l色 的线分别表示三个方向上有冲突的位|,位于该行上的冲突位置qrow、ld和rd中的1来表C。把它们三个qv来,得到该行所有的位Q取反后得到所 有可以放的位|(用pos来表C)。前面说q?a相当于not a + 1Q这里的代码W?行就相当于pos and (not pos + 1)Q其l果是取出最双的那?。这PppC行的某个可以攑֭的位|,把它从pos中移除ƈ递归调用testq程。注意递归调用时三个参数的? 化,每个参数都加上了一个禁位,但两个对角线方向的禁位对下一行的影响需要^UM位。最后,如果递归到某个时候发现row=111111了,说明六个皇后 全放q去了,此时E序从第1行蟩到第11行,扑ֈ的解的个数加一?br><br>    ~~~~====~~~~=====   华丽的分割线   =====~~~~====~~~~<br><br>Gray?br>    假如我有4个潜在的GFQ我需要决定最l到底和谁在一赗一个简单的办法 是Q依ơ和每个MM交往一D|_最后选择l我带来?#8220;满意?#8221;最大的MM。但看了<a target="_blank">dd牛的理论</a>后, 事情开始变得复杂了Q我可以选择和多个MM在一赗这P需要考核的状态变成了2^4=16U(当然包括0000q一状态,因ؓ我有可能是玻璃)。现在的 问题是Q我应该用什么顺序来遍历q?6U状态呢Q?br>    传统的做法是Q用二进制数的顺序来遍历所有可能的l合。也是_我需要以 0000->0001->0010->0011->0100->…->1111q样的顺序对每种状态进行测试。这? 序很不U学Q很多时候状态的转移都很耗时。比如从0111?000时我需要暂时甩掉当前所有的3个MMQ然后去把第4个MM。同时改变所有MM与我? 关系是一件何{巨大的工程啊。因此,我希望知道,是否有一U方法可以得,从没有MMq一状态出发,每次只改变我和一个MM的关p(q或者甩Q,15ơ操 作后恰好遍历完所有可能的l合Q最l状态不一定是1111Q。大家自己先试一试看行不行?br>    解决q个问题的方法很巧妙。我们来说明Q假如我 们已l知道了n=2时的合法遍历序Q我们如何得到n=3的遍历顺序。显Ӟn=2的遍历顺序如下:<br><br>00<br>01<br>11<br>10<br><br>    ? 可能已经惛_了如何把上面的遍历顺序扩展到n=3的情cn=3时一共有8U状态,其中前面4个把n=2的遍历顺序照搬下来,然后把它们对U翻折下dƈ? 最前面加上1作ؓ后面4个状态:<br><br>000<br>001<br>011<br>010  ↑<br>--------<br>110  ↓<br>111<br>101<br>100<br><br>    ? q种Ҏ得到的遍历顺序显然符合要求。首先,上面8个状态恰好是n=3时的所?U组合,因ؓ它们是在n=2的全部四U组合的基础上考虑选不选第3个元? 所得到的。然后我们看刎ͼ后面一半的状态应该和前面一半一h?#8220;盔R状态间仅一位不?#8221;的限Ӟ?#8220;镜面”处则是最前面那一位数不同。再ơ翻折三阉? 序Q我们就得到了刚才的问题的答案:<br><br>0000<br>0001<br>0011<br>0010<br>0110<br>0111<br>0101<br>0100<br>1100<br>1101<br>1111<br>1110<br>1010<br>1011<br>1001<br>1000<br><br>    q? U遍历顺序作ZU编码方式存在,叫做Gray码(写个中文让蜘蛛来抓:格雷码)。它的应用范围很qѝ比如,n阶的Gray码相当于在nl立方体上的 Hamilton回\Q因为沿着立方体上的边C步,nl坐标中只会有一个值改变。再比如QGray码和Hanoi塔问题等仗Gray码改变的是第几个 敎ͼHanoi塔就该移动哪个盘子。比如,3阶的Gray码每ơ改变的元素所在位|依ơؓ1-2-1-3-1-2-1Q这正好?阶Hanoi塔每ơ移? 盘子~号。如果我们可以快速求出Gray码的Wn个数是多,我们可以输ZQ意步数后Hanoi塔的Ud步骤。现在我告诉你,Gray码的Wn个数Q从 0vQ是n xor (n shr 1)Q你能想出来q是Z么吗Q先自己x吧?br><br>    下面我们把二q制数和Gray码都写在? 面,可以看到左边的数异或自n右移的结果就{于双的数?br><br>二进制数   Gray?br>   000       000<br>   001       001<br>   010       011<br>   011       010<br>   100       110<br>   101       111<br>   110       101<br>   111       100<br><br>    ? 二进制数的角度看Q?#8220;镜像”位置上的数即是对原数q行notq算后的l果。比如,W?个数010和倒数W?个数101的每一位都正好相反。假设这两个数分 别ؓx和yQ那么x xor (x shr 1)和y xor (y shr 1)的结果只有一点不同:后者的首位?Q前者的首位?。而这正好是Gray码的生成Ҏ。这p明了QGray码的Wn个数实是n xor (n shr 1)?br><br>    今年四月?a target="_blank">mashuo</a>l? 我看?a target="_blank">q道?/a>Q是二维意义上的Gray码。题目大意是_??^(n+m)-1的数写成2^n * 2^m的矩阵,使得位置盔R两数的二q制表示只有一位之差。答案其实很单,所有数都是由m位的Gray码和n位Gray码拼接而成Q需要用左移操作? orq算完成。完整的代码如下Q?br><code>var<br>   x,y,m,n,u:longint;<br>begin<br>   readln(m,n);<br>   for x:=0 to 1 shl m-1 do begin<br>      u:=(x xor (x shr 1)) shl n; //输出数的左边是一个m位的Gray?br>      for y:=0 to 1 shl n-1 do<br>         write(u or (y xor (y shr 1)),' '); //q上一个n位Gray?br>      writeln;<br>   end;<br>end.</code><br><br>Matrix67原创<br>转脓h明出?/p> <a title="Permanent link to 位运简介及实用技巧(四)Q实战篇" rel="bookmark"><strong> 位运简介及实用技巧(四)Q实战篇</strong> </a><br>下面 分n的是我自己写的三个代码,里面有些题目也是我自己出的。这些代码都是在我的Pascal时代写的Q恕不提供C语言了。代码写得ƈ不好Q我只是惛_诉大 家位q算在实战中的应用,包括了搜索和状态压~DP斚w的题目。其实大家可以在|上扑ֈ更多用位q算优化的题目,q里整理Z些自己写的代码,只是Z? 创系列文章的完整性。这一pd文章到这里就l束了,希望大家能有所收获?br>    Matrix67原创Q{贴请注明出处?br><br><br> <blockquote>Problem : 费解的开?br><br><a target="_blank"><strong> <font color="#618898">题目来源</font></strong> </a><br>    06 qNOIp模拟赛(一Q?by Matrix67 W四?br><br>问题描述<br>    你玩q?#8220;拉灯”游戏吗?25盏灯排成一?×5的方 形。每一个灯都有一个开养I游戏者可以改变它的状态。每一步,游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生q锁反应Q和q个灯上下左右相 ȝ灯也要相应地改变其状态?br>    我们用数?#8220;1”表示一盏开着的灯Q用数字“0”表示关着的灯。下面这U状?br><br>10111<br>01101<br>10111<br>10000<br>11011<br><br>    ? 改变了最左上角的灯的状态后变成:<br><br>01111<br>11101<br>10111<br>10000<br>11011<br><br>    ? 改变它正中间的灯后状态将变成Q?br><br>01111<br>11001<br>11001<br>10100<br>11011<br><br>    l? 定一些游戏的初始状态,~写E序判断游戏者是否可能在6步以内所有的灯都变亮?br><br>输入格式<br>    W一行有一个正整数nQ代表数 据中共有n个待解决的游戏初始状态?br>    以下若干行数据分为nl,每组数据?行,每行5个字W。每l数据描qC一个游戏的初始状态。各l数 据间用一个空行分隔?br>    对于30%的数据,n<=5Q?br>    对于100%的数据,n<=500?br><br>? 出格?br>    输出数据一共有n行,每行有一个小于等?的整敎ͼ它表C对于输入数据中对应的游戏状态最需要几步才能所有灯变亮?br>    ? 于某一个游戏初始状态,?步以内无法所有灯变亮Q请输出“-1”?br><br>样例输入<br>3<br>00111<br>01011<br>10001<br>11010<br>11100<br><br>11101<br>11101<br>11110<br>11111<br>11111<br><br>01111<br>11111<br>11111<br>11111<br>11111<br><br>? 例输?br>3<br>2<br>-1 <p> </p> </blockquote> <p><br><br>E序代码<br><code>const<br>   BigPrime=3214567;<br>   MaxStep=6;<br>type<br>   pointer=^rec;<br>   rec=record<br>         v:longint;<br>         step:integer;<br>         next:pointer;<br>       end;<br><br>var<br>   total:longint;<br>   hash:array[0..BigPrime-1]of pointer;<br>   q:array[1..400000]of rec;<br><br>function update(a:longint;p:integer):longint;<br>begin<br>   a:=a xor (1 shl p);<br>   if p mod 5<>0 then a:=a xor (1 shl (p-1));<br>   if (p+1) mod 5<>0 then a:=a xor (1 shl (p+1));<br>   if p<20 then a:=a xor (1 shl (p+5));<br>   if p>4 then a:=a xor (1 shl (p-5));<br>   exit(a);<br>end;<br><br>function find(a:longint;step:integer):boolean;<br>var<br>   now:pointer;<br>begin<br>   now:=hash[a mod BigPrime];<br>   while now<>nil do<br>   begin<br>      if now^.v=a then exit(true);<br>      now:=now^.next;<br>   end;<br><br>   new(now);<br>   now^.v:=a;<br>   now^.step:=step;<br>   now^.next:=hash[a mod BigPrime];<br>   hash[a mod BigPrime]:=now;<br>   total:=total+1;<br>   exit(false);<br>end;<br><br>procedure solve;<br>var<br>   p:integer;<br>   close:longint=0;<br>   open:longint=1;<br>begin<br>   find(1 shl 25-1,0);<br>   q[1].v:=1 shl 25-1;<br>   q[1].step:=0;<br>   repeat<br>      inc(close);<br>      for p:=0 to 24 do<br>         if not find(update(q[close].v,p),q[close].step+1) and (q[close].step+1<MaxStep) then<br>         begin<br>            open:=open+1;<br>            q[open].v:=update(q[close].v,p);<br>            q[open].step:=q[close].step+1;<br>         end;<br>   until close>=open;<br>end;<br><br>procedure print(a:longint);<br>var<br>   now:pointer;<br>begin<br>   now:=hash[a mod BigPrime];<br>   while now<>nil do<br>   begin<br>      if now^.v=a then<br>      begin<br>         writeln(now^.step);<br>         exit;<br>      end;<br>      now:=now^.next;<br>   end;<br>   writeln(-1);<br>end;<br><br>procedure main;<br>var<br>   ch:char;<br>   i,j,n:integer;<br>   t:longint;<br>begin<br>   readln(n);<br>   for i:=1 to n do<br>   begin<br>      t:=0;<br>      for j:=1 to 25 do<br>      begin<br>         read(ch);<br>         t:=t*2+ord(ch)-48;<br>         if j mod 5=0 then readln;<br>      end;<br>      print(t);<br>      if i<n then readln;<br>   end;<br>end;<br><br>begin<br>   solve;<br>   main;<br>end.</code><br><br><strong> =======================  ? 感的分割U?nbsp; =======================</strong> <br><br><br> </p> <blockquote>Problem : garden / 和MM逛花?br><br>题目来源<br>    <a target="_blank"><strong> <font color="#618898">07qMatrix67生日邀误</font></strong> </a>W? 四题<br><br>问题描述<br>    花园设计Q简单就是美。Matrix67常去的花园有着非常单的布局Q花园的所有景点的位置都是“? ?#8221;了的Q这些景点可以看作是q面坐标上的格点。相ȝ景点之间有小路相q,q些\全部q于坐标u。景点和\l成了一?#8220;不完整的|格”?br>    一 个典型的花园布局如左图所C。花园布局??列的|格上,花园?6个景点的位置用红色标注在了图中。黑色线条表C景炚w的小路,其余灰色部分实际q不 存在?br>        <img alt="" src="http://www.matrix67.com/data/prob4.gif" border="0"><br><br>    Matrix67 的生日那天,他要带着他的MM在花园里游玩。Matrix67不会带MM两次l过同一个景点,因此每个景点最多被游览一ơ。他和他的MM边走边聊Q他们是 如此的投入以致于他们从不?#8220;d地拐?#8221;。也是_除非前方已没有景Ҏ是前方的景点已经讉Kq,否则他们会一直往前走下去。当前方景点不存在或已游 览过ӞMatrix67会带MM另选一个方向l前q。由于景点个数有限,讉Kq的景点越来越多,q早会出C能再走的情况Q即四个方向上的盔R景点 都访问过了)Q此时他们将l束花园的游览。Matrix67希望知道以这U方式游览花园是否有可能遍历所有的景点。Matrix67可以选择从Q意一个景 点开始游览,以Q意一个景点结束?br>    在上图所C的花园布局中,一U可能的游览方式如右图所C。这U浏览方式从(1,2)出发Q以(2,4) l束Q经q每个景Ҏ好一ơ?br><br>输入格式<br>    W一行输入两个用I格隔开的正整数m和nQ表C园被布局在m行n列的|格上?br>    ? 下m行每行n个字W,字符“0”表示该位|没有景点,字符“1”表示对应位置有景炏V这些数字之间没有空根{?br><br>输出格式<br>    ? 的程序需要寻找满?#8220;不主动拐?#8221;性质且遍历所有景点的游览路线?br>    如果没有q样的游览\U,误Z?#8220;Impossible”Q不带引 P注意大小写)?br>    如果存在游览路线Q请依次输出你的Ҏ中访问的景点的坐标,每行输出一个。坐标的表示格式?#8220;(x,y)”Q代表第x 行第y列?br>    如果有多U方案,你只需要输出其中一U即可。评系l可以判断你的方案的正确性?br><br>样例输入<br>6 4<br>1100<br>1001<br>1111<br>1100<br>1110<br>1110<br><br>? 例输?br>(1,2)<br>(1,1)<br>(2,1)<br>(3,1)<br>(4,1)<br>(5,1)<br>(6,1)<br>(6,2)<br>(6,3)<br>(5,3)<br>(5,2)<br>(4,2)<br>(3,2)<br>(3,3)<br>(3,4)<br>(2,4)<br><br>? 据规?br>    对于30%的数据,n,m<=5Q?br>    对于100%的数据,n,m<=10? <p> </p> </blockquote> <p><br><br>E序代码Q?br><code>program garden;<br><br>const<br>   dir:array[1..4,1..2]of integer=<br>     ((1,0),(0,1),(-1,0),(0,-1));<br><br>type<br>   arr=array[1..10]of integer;<br>   rec=record x,y:integer;end;<br><br>var<br>   map:array[0..11,0..11]of boolean;<br>   ans:array[1..100]of rec;<br>   n,m,max:integer;<br>   step:integer=1;<br>   state:arr;<br><br>procedure readp;<br>var<br>   i,j:integer;<br>   ch:char;<br>begin<br>   readln(m,n);<br>   for i:=1 to n do<br>   begin<br>      for j:=1 to m do<br>      begin<br>         read(ch);<br>         map[i,j]:=(ch='1');<br>         inc(max,ord( map[i,j] ))<br>      end;<br>   readln;<br>   end;<br>end;<br><br>procedure writep;<br>var<br>   i:integer;<br>begin<br>   for i:=1 to step do<br>      writeln( '(' , ans[i].x , ',' , ans[i].y , ')' );<br>end;<br><br>procedure solve(x,y:integer);<br>var<br>   tx,ty,d:integer;<br>   step_cache:integer;<br>   state_cache:arr;<br>begin<br>   step_cache:=step;<br>   state_cache:=state;<br>   if step=max then<br>   begin<br>      writep;<br>      exit;<br>   end;<br><br>   for d:=1 to 4 do<br>   begin<br>      tx:=x+dir[d,1];<br>      ty:=y+dir[d,2];<br>      while map[tx,ty] and ( not state[tx] and(1 shl (ty-1) )>0) do<br>      begin<br>         inc(step);<br>         ans[step].x:=tx;<br>         ans[step].y:=ty;<br>         state[tx]:=state[tx] or ( 1 shl (ty-1) );<br>         tx:=tx+dir[d,1];<br>         ty:=ty+dir[d,2];<br>      end;<br><br>      tx:=tx-dir[d,1];<br>      ty:=ty-dir[d,2];<br>      if (tx<>x) or (ty<>y) then solve(tx,ty);<br>      state:=state_cache;<br>      step:=step_cache;<br>   end;<br>end;<br><br>{====main====}<br>var<br>   i,j:integer;<br>begin<br>   assign(input,'garden.in');<br>   reset(input);<br>   assign(output,'garden.out');<br>   rewrite(output);<br><br>   readp;<br>   for i:=1 to n do<br>   for j:=1 to m do<br>     if map[i,j] then<br>     begin<br>        ans[1].x:=i;<br>        ans[1].y:=j;<br>        state[i]:=1 shl (j-1);<br>        solve(i,j);<br>        state[i]:=0;<br>     end;<br><br>   close(input);<br>   close(output);<br>end.</code><br><br><strong> =======================  ? 感的分割U?nbsp; =======================</strong> <br><br><br> </p> <blockquote>Problem : cowfood / 玉米?br><br>题目来源<br>    USACO月赛<br><br>? 题描q?br>    农夫U翰购买了一处肥沃的矩Ş牧场Q分成M*N(1<=M<=12; 1<=N<=12)个格子。他惛_那里的一些格子中U植味的玉c뀂遗憄是,有些格子区域的土地是贫瘠的,不能耕种?br>    _明 的约知道奶牛们q食时不喜欢和别的牛盔RQ所以一旦在一个格子中U植玉米Q那么他׃会在盔R的格子中U植Q即没有两个被选中的格子拥有公p。他q没 有最l确定哪些格子要选择U植玉米?br>    作ؓ一个思想开明的人,农夫U翰希望考虑所有可行的选择格子U植Ҏ。由于太开明,他还考虑一个格? 都不选择的种植方案!请帮助农夫约确定种植方案L?br><br>输入格式:<br>    W一行:两个用空格分隔的整数M和N<br>    W? 二行到第M+1行:Wi+1行描q牧场第i行每个格子的情况QN个用I格分隔的整敎ͼ表示q个格子是否可以U植Q?表示肥沃的、适合U植Q?表示贫瘠的? 不可U植Q?br><br>输出格式<br>    一个整敎ͼ农夫U翰可选择的方案L除以 100,000,000 的余?br><br>样例输入<br>2 3<br>1 1 1<br>0 1 0<br><br>样例输出<br>9<br><br>样例说明<br><br>    l可以种植玉c的格子~? P<br>      1 2 3<br>        4<br><br>    ? U一个格子的Ҏ有四U?1,2,3?)Q种植两个格子的Ҏ有三U?13,14?4)Q种植三个格子的Ҏ有一U?134)Q还有一U什么格子都? U?br>    4+3+1+1=9?br><br>数据规模<br>    对于30%的数据,N,M<=4Q?br>    对于 100%的数据,N,M<=12? <p> </p> </blockquote> <p><br><br>E序代码Q?br><code>program cowfood;<br><br>const<br>   d=100000000;<br>   MaxN=12;<br><br>var<br>   f:array[0..MaxN,1..2000]of longint;<br>   w:array[1..2000,1..2000]of boolean;<br>   st:array[0..2000]of integer;<br>   map:array[0..MaxN]of integer;<br>   m,n:integer;<br><br>function Impossible(a:integer):boolean;<br>var<br>   i:integer;<br>   flag:boolean=false;<br>begin<br>   for i:=1 to MaxN do<br>   begin<br>      if flag and (a and 1=1) then exit(true);<br>      flag:=(a and 1=1);<br>      a:=a shr 1;<br>   end;<br>   exit(false);<br>end;<br><br>function Conflict(a,b:integer):boolean;<br>var<br>   i:integer;<br>begin<br>   for i:=1 to MaxN do<br>   begin<br>      if (a and 1=1) and (b and 1=1) then exit(true);<br>      a:=a shr 1;<br>      b:=b shr 1;<br>   end;<br>   exit(false);<br>end;<br><br>function CanPlace(a,b:integer):boolean;<br>begin<br>   exit(a or b=b);<br>end;<br><br>procedure FindSt;<br>var<br>   i:integer;<br>begin<br>   for i:=0 to 1 shl MaxN-1 do<br>      if not Impossible(i) then<br>      begin<br>         inc(st[0]);<br>         st[st[0]]:=i;<br>      end;<br>end;<br><br>procedure Init;<br>var<br>   i,j:integer; <br>begin<br>   for i:=1 to st[0] do<br>   for j:=i to st[0] do<br>      if not Conflict(st[i],st[j]) then<br>      begin<br>         w[i,j]:=true;<br>         w[j,i]:=true;<br>      end;<br>end;<br><br>procedure Readp;<br>var<br>   i,j,t,v:integer;<br>begin<br>   readln(m,n);<br>   for i:=1 to m do<br>   begin<br>      v:=0;<br>      for j:=1 to n do<br>      begin<br>         read(t);<br>         v:=v*2+t;<br>      end;<br>      map[i]:=v;<br>      readln;<br>   end;<br>end;<br><br>procedure Solve;<br>var<br>   i,j,k:integer;<br>begin<br>   f[0,1]:=1;<br>   map[0]:=1 shl n-1;<br>   for i:=1 to m do<br>   for j:=1 to st[0] do<br>      if not CanPlace(st[j],map[i]) then f[i,j]:=-1 else<br>        for k:=1 to st[0] do if (f[i-1,k]<>-1) and w[j,k] then<br>           f[i,j]:=(f[i,j]+f[i-1,k]) mod d;<br>end;<br><br>procedure Writep;<br>var<br>   j:integer;<br>   ans:longint=0;<br>begin<br>   for j:=1 to st[0] do<br>      if f[m,j]<>-1 then ans:=(ans+f[m,j]) mod d;<br>   writeln(ans);<br>end;<br><br>begin<br>   assign(input,'cowfood.in');<br>   reset(input);<br>   assign(output,'cowfood.out');<br>   rewrite(output);<br><br>   FindSt;<br>   Init;<br>   Readp;<br>   Solve;<br>   Writep;<br><br>   close(input);<br>   close(output);<br>end.</code></p> <br> <img src ="http://www.shnenglu.com/yuqilin1228/aggbug/110616.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.shnenglu.com/yuqilin1228/" target="_blank">LynnRaymond</a> 2010-03-26 21:48 <a href="http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110616.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title><b>【{载之VC++】利用Visual C++制作应用E序启动画面</b>http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110615.htmlLynnRaymondLynnRaymondFri, 26 Mar 2010 13:44:00 GMThttp://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110615.htmlhttp://www.shnenglu.com/yuqilin1228/comments/110615.htmlhttp://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110615.html#Feedback0http://www.shnenglu.com/yuqilin1228/comments/commentRss/110615.htmlhttp://www.shnenglu.com/yuqilin1228/services/trackbacks/110615.html http://edu.itbulo.com

摘要 Q? 本文提供了四U启动画面制作方法?br>
  使用启动画面一是可以减等待程序加载过E中的枯燥感Q尤其是一些大型程序)Q二是可以用来显CY 件名U和版权{提CZ息。怎样使用VC++制作应用E序的启动画面呢Q本文提供四U方法,前三U适用于基于文档的应用E序Q第四种适用于基于对话框的应? E序?br>
   1.利用lg库中的Splash Screenlg实现

  (1)? Photoshop{制作启动画面图像,保存为bmp格式?br>
  (2)用AppwizardZ个基于单文档的工ESplash?br>
(3)在资源中插入位图资源

  打开VC++的资源编辑器Q用鼠标右键单击Resources文g夹,选择Import命oQ插入所? 作的位图。如果位图超q?56ԌVC会弹Z个对话框Q提CZ囑ַl插入但不能在位囄辑器中显C,定卛_。将位图ID改ؓIDB_SPLASH?

(4)dSplash Screen控g

  ①选择菜单“project”/“Add To Project”/“Conponents and Controls”打开对话框,在列表框中双?#8220;Visual C++ Conponents”选项Q选择“Splash Screen”控gQ然后单?#8220;Insert”?br>
  ②确认或修改cd和位图资? IDQ单击OK认?br>
  ③编译、连接,漂亮的启动画面就昄出来了?br>
  (5)如果需要改变启动画面的停留旉Q就? 改SetTimer()函数的第二个参数Q默认是750 毫秒。该函数所在位|:
int CSplashWnd::OnCreate(LPCREATESTRUCT lpCreateStruct)
{
 
 // Set a timer to destroy the splash screen.
 SetTimer(1, 750, NULL); //修改W二个参C调整画面停留旉
 return 0;
}
2.利用无模式对话框昄启动画面

  (1)用AppwizardZ个基于单文档的工E? Splash?br>
  (2)导入用作启动画面的图片,更改ID为IDB_SPLASH?br>
  (3)新徏一个对话框Q在其中 d启动画面?br>
  在资源中新徏一个对话框Q创建对话框cCSplashDlg。在对话框中d一个Picture控gQ打开? “Properties”对话框,? GeneralQ在Type下拉列表中选择BitmapQ在Image下拉列表中选前面导入的位图资源ID|IDB_SPLASH?br>
(4)修改对话框的昄效果

  ①调整对话框大小Q去掉两个自动生成的按钮Qƈ?#8220;Properties”?#8220;Styles”中L 对Title bar的选取Q?br>
  ②选中囑փQ调整大之适应对话框的可编辑区Q修改其“Properties”?#8220;Styles”? 之居中?br>
  (5)在CMainFramecȝOnCreate()函数中添加创建、显Cƈ销毁无模式对话框的代码?br>
#include “SplashDlg.h” //加到MainFrm.cpp文g的头文g调用部位
int CMainFrame::OnCreate(LPCREATESTRUCT lpCreateStruct)
{
 CSplashDlg *dlg = new CSplashDlg(this);
 dlg->Create(CSplashDlg::IDD,this); //创徏对话?br> dlg->ShowWindow(SW_SHOW); //昄对话?br> dlg->UpdateWindow();
 Sleep(2000); //画面昄停留旉Q单位ؓ毫秒
 …
 dlg->DestroyWindow(); //销毁对话框
 return 0;

3.通过发送消息显C和销毁启动画?br>
  ①重复方法二的步?x??br>
  ②? Class Wizard为CMainFramecL加消息响应函数WM_TIMER?br>
  ?修改代码Q通过发送WM_TIMER消息 启动和销毁启动画?br>
  1Q定义对话框cȝ变量

  在MainFrm.h文g头部d#include "SplashDlg.h"Qƈ在CMainFramcȝ定义中加上公用变量CSplashDlg *Splash?br>
  2Q添加计时器 消息相应函数代码
void CMainFrame::OnTimer(UINT nIDEvent) 
{
 if(Splash->IsWindowVisible()){
  Splash->SetActiveWindow(); //把启动画面设|ؓ当前zdH口
  Splash->UpdateWindow();
  Sleep(2000); //修改此处可更改画面显C时?br>  Splash->SendMessage(WM_CLOSE); //关闭对话?br> }
 else{
  SetActiveWindow();
  KillTimer(1) ; //清除WM_TIMER事g
 }
}

 3Q修Ҏ架生成函数OnCreate()
int CMainFrame::OnCreate(LPCREATESTRUCT lpCreateStruct)
{
 SetTimer(1,0,NULL); //dID?的WM_TIMER? ?br> Splash=new CSplashDlg();
 Splash->Create(IDD_DIALOG1);
 Splash->ShowWindow(SW_SHOW);
 …

4.制作Z对话框的应用E序启动画面

  以上几种Ҏ都不能给Z对话框的应用E序做启动画面,? 面介l一U方法给Z对话框的应用E序做启动画面。基于对话框的应用程序没有主框架Q因此不能采用前面几U方法制作启动画面。不q我们可以把Ҏ一建立? 的启动画面文件移植过来,然后Q对E序q行一些修攏V?

  (1)参照Ҏ一建立Z单文档的工程Splash?br>
(2)建立Z对话框的工程Cover?br>
  (3)文gUL

  ①将Splash1.cpp 和Splash1.h 两个文g从方法一建立的Splash工程拯到Cover工程中,q且分别加入到Source Files和Header Files中;

②导入位图文件到工程的资源中Q改ID为IDB_SPLASH?br>
  (4)修改代码Q实现启动画面的调用

  ①添? CCoverApp 的InitInstance() 函数代码
#include "Splash1.h" //加在Cover.cpp文g的头文g调用部位
BOOL CCoverApp::InitInstance()
{
 CCommandLineInfo cmdInfo;
 ParseCommandLine(cmdInfo);
 CSplashWnd::EnableSplashScreen(cmdInfo.m_bShowSplash);
 


②用ClassWizard dOnCreate() 函数到对话框cCCoverDlg中,q修改代?br>
#include "Splash1.h" //加在CoverDlg.cpp文g的头文g调用部位
int CCoverDlg::OnCreate(LPCREATESTRUCT lpCreateStruct)
{
 
 CSplashWnd::ShowSplashScreen(this); //昄启动画面
 
}

说明Q启动画面停留时间的修改同方法一?br>
   5.l束?/strong>

  正如前面提过 的,q用好启动画面可以给使用者留下一个强烈的印象Qv到很好的宣传作用Q以上程序均在Visual C++ 6.0、Windows2000调试通过?


LynnRaymond 2010-03-26 21:44 发表评论
]]>
<b>【{载之VC++】Visual C++ 入门_解</b>http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110614.htmlLynnRaymondLynnRaymondFri, 26 Mar 2010 13:41:00 GMThttp://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110614.htmlhttp://www.shnenglu.com/yuqilin1228/comments/110614.htmlhttp://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110614.html#Feedback0http://www.shnenglu.com/yuqilin1228/comments/commentRss/110614.htmlhttp://www.shnenglu.com/yuqilin1228/services/trackbacks/110614.html阅读全文

LynnRaymond 2010-03-26 21:41 发表评论
]]>
【C++常识】C/C++头文件一?/title><link>http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110613.html</link><dc:creator>LynnRaymond</dc:creator><author>LynnRaymond</author><pubDate>Fri, 26 Mar 2010 13:39:00 GMT</pubDate><guid>http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110613.html</guid><wfw:comment>http://www.shnenglu.com/yuqilin1228/comments/110613.html</wfw:comment><comments>http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110613.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.shnenglu.com/yuqilin1228/comments/commentRss/110613.html</wfw:commentRss><trackback:ping>http://www.shnenglu.com/yuqilin1228/services/trackbacks/110613.html</trackback:ping><description><![CDATA[<strong> <font size="2">C、传l?C++<br><br>#include <assert.h>    //讑֮插入?br>#include <ctype.h>     //字符处理<br>#include <errno.h>     //定义错误?br>#include <float.h>     //点数处?br>#include <fstream.h>    //文g输入Q输?br>#include <iomanip.h> //参数化输入/输出<br>#include <iostream.h>   //数据输入/输出<br>#include <limits.h>    //定义各种数据cd最值常?br>#include <locale.h>    //定义本地化函?br>#include <math.h>     //定义数学函数<br>#include <stdio.h>     //定义输入Q输出函?br>#include <stdlib.h>    //定义杂项函数及内存分配函?br>#include <string.h>    //字符串处?br>#include <strstrea.h>   //Z数组的输入/输出<br>#include <time.h>     //定义关于旉的函?br>#include <wchar.h> //宽字W处理及输入Q输?br>#include <wctype.h>    //宽字W分c?br><br>//////////////////////////////////////////////////////////////////////////<br><br>? ?C++ Q同上的不再注释Q?br><br>#include <algorithm>    //STL 通用法<br>#include <bitset>     //STL 位集容器<br>#include <cctype><br>#include <cerrno><br>#include <clocale><br>#include <cmath><br>#include <complex>     //复数c?br>#include <cstdio><br>#include <cstdlib><br>#include <cstring><br>#include <ctime><br>#include <deque>      //STL 双端队列容器<br>#include <exception> //异常处理c?br>#include <fstream><br>#include <functional>   //STL 定义q算函数Q代替运符Q?br>#include <limits><br>#include <list>      //STL U性列表容?br>#include <map>       //STL 映射容器<br>#include <iomanip><br>#include <ios>       //基本输入Q输出支?br>#include <iosfwd>     //输入Q输出系l用的前置声明<br>#include <iostream><br>#include <istream>     //基本输入?br>#include <ostream>     //基本输出?br>#include <queue>      //STL 队列容器<br>#include <set>       //STL 集合容器<br>#include <sstream>     //Z字符串的?br>#include <stack>      //STL 堆栈容器    <br>#include <stdexcept>    //标准异常c?br>#include <streambuf>    //底层输入Q输出支?br>#include <string>     //字符串类<br>#include <utility>     //STL 通用模板c?br>#include <vector>     //STL 动态数l容?br>#include <cwchar><br>#include <cwctype><br><br>using namespace std;<br><br>//////////////////////////////////////////////////////////////////////////<br><br>C99 增加<br><br>#include <complex.h>   //复数处理<br>#include <fenv.h>    //点环境<br>#include <inttypes.h>  //整数格式转换<br>#include <stdbool.h>   //布尔环境<br>#include <stdint.h>   //整型环境<br>#include <tgmath.h>   //通用cd数学?/font>C/C++ 头文件一?br><!----><br></strong> <font size="2"><strong> C、传l?C++<br><br>#include <assert.h>    //讑֮插入?br>#include <ctype.h>     //字符处理<br>#include <errno.h>     //定义错误?br>#include <float.h>     //点数处?br>#include <fstream.h>    //文g输入Q输?br>#include <iomanip.h>    //参数化输入/输出<br>#include <iostream.h>   //数据输入/输出<br>#include <limits.h>    //定义各种数据cd最值常?br>#include <locale.h>    //定义本地化函?br>#include <math.h>     //定义数学函数<br>#include <stdio.h>     //定义输入Q输出函?br>#include <stdlib.h>    //定义杂项函数及内存分配函?br>#include <string.h>    //字符串处?br>#include <strstrea.h>   //Z数组的输入/输出<br>#include <time.h>     //定义关于旉的函?br>#include <wchar.h> //宽字W处理及输入Q输?br>#include <wctype.h>    //宽字W分c?br><br>//////////////////////////////////////////////////////////////////////////<br><br>? ?C++ Q同上的不再注释Q?br><br>#include <algorithm>    //STL 通用法<br>#include <bitset>     //STL 位集容器<br>#include <cctype><br>#include <cerrno><br>#include <clocale><br>#include <cmath><br>#include <complex>     //复数c?br>#include <cstdio><br>#include <cstdlib><br>#include <cstring><br>#include <ctime><br>#include <deque>      //STL 双端队列容器<br>#include <exception> //异常处理c?br>#include <fstream><br>#include <functional>   //STL 定义q算函数Q代替运符Q?br>#include <limits><br>#include <list>      //STL U性列表容?br>#include <map>       //STL 映射容器<br>#include <iomanip><br>#include <ios>       //基本输入Q输出支?br>#include <iosfwd>     //输入Q输出系l用的前置声明<br>#include <iostream><br>#include <istream>     //基本输入?br>#include <ostream>     //基本输出?br>#include <queue>      //STL 队列容器<br>#include <set>       //STL 集合容器<br>#include <sstream>     //Z字符串的?br>#include <stack>      //STL 堆栈容器    <br>#include <stdexcept>    //标准异常c?br>#include <streambuf>    //底层输入Q输出支?br>#include <string>     //字符串类<br>#include <utility>     //STL 通用模板c?br>#include <vector>     //STL 动态数l容?br>#include <cwchar><br>#include <cwctype><br><br>using namespace std;<br><br>//////////////////////////////////////////////////////////////////////////<br><br>C99 增加<br><br>#include <complex.h>   //复数处理<br>#include <fenv.h>    //点环境<br>#include <inttypes.h>  //整数格式转换<br>#include <stdbool.h>   //布尔环境<br>#include <stdint.h>   //整型环境<br>#include <tgmath.h>   //通用cd数学?/strong> </font><br> <br> <img src ="http://www.shnenglu.com/yuqilin1228/aggbug/110613.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.shnenglu.com/yuqilin1228/" target="_blank">LynnRaymond</a> 2010-03-26 21:39 <a href="http://www.shnenglu.com/yuqilin1228/archive/2010/03/26/110613.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item></channel></rss> <footer> <div class="friendship-link"> <p>лǵվܻԴȤ</p> <a href="http://www.shnenglu.com/" title="精品视频久久久久">精品视频久久久久</a> <div class="friend-links"> </div> </div> </footer> <a href="http://www.zajiaosd.cn" target="_blank">88þþƷһëƬ</a>| <a href="http://www.jejf.cn" target="_blank">þþþþþþƷŮ99</a>| <a href="http://www.vaez.cn" target="_blank">պŷþ</a>| <a href="http://www.skgv0713.cn" target="_blank">޾Ʒþþþþο</a>| <a href="http://www.yhshoes.cn" target="_blank">ɫۺϾþĻۺ</a>| <a href="http://www.zzdls.cn" target="_blank">wwwþ</a>| <a href="http://www.qzshinetex.cn" target="_blank">ھƷ˾þþӰԺ</a>| <a href="http://www.xkeir8vz.cn" target="_blank">һɫۺϾþ</a>| <a href="http://www.yk999.cn" target="_blank">þóСƵ</a>| <a href="http://www.pnpxnc.cn" target="_blank">þþƷ</a>| <a href="http://www.shangxin.net.cn" target="_blank">Ʒ999þþþþĻ</a>| <a href="http://www.265z.cn" target="_blank">޾þþþþ</a>| <a href="http://www.airesou.cn" target="_blank">ľþþþר</a>| <a href="http://www.56zhuanjia.com.cn" target="_blank">Ļþи</a>| <a href="http://www.uniontruck.cn" target="_blank">˾þں2019 </a>| <a href="http://www.lkwg.com.cn" target="_blank">þùŷպƷ</a>| <a href="http://www.ksxhsd.cn" target="_blank">һƷþð͹</a>| <a href="http://www.wuhujob.com.cn" target="_blank">պƷھþ</a>| <a href="http://www.99605.com.cn" target="_blank">Ժձһձþ </a>| <a href="http://www.qhylhsk.cn" target="_blank">þþþӰԺŮ</a>| <a href="http://www.fylmbd.cn" target="_blank">þƵ6</a>| <a href="http://www.shaikr.cn" target="_blank">2021þþƷѹۿ</a>| <a href="http://www.3q168.net.cn" target="_blank">޹Ʒþþþ</a>| <a href="http://www.ckpic.com.cn" target="_blank">99þþƷѿһ</a>| <a href="http://www.xxxls.cn" target="_blank">av˾þۺɫ</a>| <a href="http://www.sangaotang.cn" target="_blank">þùӰԺ</a>| <a href="http://www.tobeok.cn" target="_blank">69Ʒþþþ9999APGF </a>| <a href="http://www.baaag.cn" target="_blank">ƷþþþþĻһ</a>| <a href="http://www.gsm1.com.cn" target="_blank">AVһþ</a>| <a href="http://www.ykezn.cn" target="_blank">97þþþ</a>| <a href="http://www.j19785.cn" target="_blank">99þ99ֻѵľƷ</a>| <a href="http://www.nxol.net.cn" target="_blank">Ƶþ</a>| <a href="http://www.gxsc.net.cn" target="_blank">99þۺϹƷ</a>| <a href="http://www.dmbetter.cn" target="_blank">þþþĻ</a>| <a href="http://www.ljvs.cn" target="_blank">þۺϾɫۺϾƷ</a>| <a href="http://www.panroad.cn" target="_blank">þþžȫ</a>| <a href="http://www.18xh.cn" target="_blank">һۺϾþ</a>| <a href="http://www.jingxi.jx.cn" target="_blank">һƷþþ޹</a>| <a href="http://www.2blood.cn" target="_blank">99þùۺϾƷӰԺ</a>| <a href="http://www.dztsc.cn" target="_blank">avþþþþòվ</a>| <a href="http://www.santoncc.cn" target="_blank">þô㽶</a>| <script> (function(){ var bp = document.createElement('script'); var curProtocol = window.location.protocol.split(':')[0]; if (curProtocol === 'https') { bp.src = 'https://zz.bdstatic.com/linksubmit/push.js'; } else { bp.src = 'http://push.zhanzhang.baidu.com/push.js'; } var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(bp, s); })(); </script> </body>