数据结构学习(C++)——线性链式结构总结(代后记)【1】

类别:VC语言 点击:0 评论:0 推荐:

看到这个标题,有些人一定松了一口气——这小子可算白话完了,当然了,你要是略有惋惜之情,我真是受宠若惊。但不论你怎么想,写到这里只是告一段落,并没有完,后面还有很大一部分呢,比如树、图、查找、排序——这么多年了,还是这点东西。代后记的意思是,我觉得对前面线性链式结构的总结,对后面的学习有指导意义:从前面的学习中,你能得出如何学习数据结构,以及如何正确看待这门课——如果你能从重复建设中看到这样做的价值,你才能真正理解这门课的意义。

在开始总结前,先整理一下以前的代码,假定你使用的是VC6,你的工程中现在应该有这几个主要文件:Node.h、List.h、Stack.h、Queue.h、CircList.h、DblList.h、Polynomial.h、Expression.h、Matrix.h,一个含有main()的cpp文件。其他的是一些测试文件和一些应用,比如Simulation.h。如果你用的不是VC6,你一定背地里咒骂我多少次了,因为一大堆error和warning。我当初发布的时候,并没有考虑到不同编译器的差异,我觉得只要光使用标准库(仅仅用了iostream.h和stdlib.h),不写怪怪的代码,通用性应该不是问题,但实际上不是这样。所以,我不得不花一些篇幅介绍如何修改以前的代码,所以,这篇文章就只能是【1】了;不过,后面有一个计时器类的源码,就算是一点补偿吧。

VC6、BCB6、Dev-cpp的编译器的差异

这些应该是目前Win32下最常用的IDE环境了,各自的编译器分别是CL.exe、BCC32.exe、G++.exe(就是GNU C++)。我没装BCB6,所以只是拿BCC32来代替。VC6时间比较早(98年),对C++标准支持不是很完善,例如下面的代码:

for (int i = 1; i < 10; i++); for (int i = 1; i < 10; i++);

按照C++标准,i的作用域应该是for循环内。但是在VC6中,出了定义i的for循环,仍然有效,所以,这段代码在VC6中被认为是重复定义。我为了省事,在并列的第二个循环内,把int省略了。现在到了BCC32,它在这方面对于C++标准倒是很支持,于是,象我那样的做法,就是第二个i没定义。让这样的代码同时适应两个编译器的解决办法,要么第2个循环变量换个名字,要么退回到C的写法:

int i; for (i = 1; i < 10; i++); for (i = 1; i < 10; i++);

VC6中的=重载可以不需要函数类型(默认int),顺便不需要返回值。这很好理解,=只能是成员函数,并且操作对象是一定的,返回值是什么(和int main()一个道理)?但这合情合理的做法是违反标准的(让人想起了什么),到了BCC32,人家不干了,非让给个返回值,可以添加return 0;了事,两边都不得罪;或者,定义void operator=,一样两边都认可。VC7也要求operator=必须有返回值,还是标准的力量大啊。

修正如上的问题之后,BCC32就能编译了,但是还是一大堆waining,这是我写作的风格导致的。C++标准说,如果在类体内定义函数(而不是声明原型),那个函数被自动内联;也就是说,我的那些类的成员函数,编译器都认为我想让他们成为内联函数,但是有些函数是不能内联的,于是编译器就说“你的要求太高了,我办不到”——我也没想让你受累啊,自找麻烦的编译器。

胡弄过去BCC32后,再拿Dev-cpp试试,晕了,上百个error和warning。其实这是个连锁反应,首先,在GNU C++中,iostream.h这个头文件被废弃了,强烈建议使用iostream(总觉得象大棒),还好VC6、BCC32也认这个。改了这个,又来了一个啼笑皆非的warning,文件尾必须要有一个空行?!我以前为了紧凑,有空行也删掉了,得,听你的,加上。这些都完事之后,Dev-cpp就通过了,没有warning。

这样修改完后,那些代码3个编译器就都能编译了,看一下编译的exe文件大小,VC6的最小(Release版),BCC32的大一点,Dev-cpp的……大得太可怕了,我不清楚是不是编译器的参数问题,但是GNU C++能在Win32下使用,都是经过转换的,不知道是不是这个原因。突然有个想法,哪个编译器编译的exe文件运行的更快?

哪个编译器效果更好?

首先,要写个计时器,这方面有人写过文章,我参考了一些人的,做了一个封装,如下:

#ifndef Timer_H

#define Timer_H

 

#include <windows.h>

 

class Timer

{

public:

       Timer() { QueryPerformanceFrequency(&Frequency); }      

       inline void Start() { QueryPerformanceCounter(&timerB); } 

       inline double GetTime()

       {

              QueryPerformanceCounter(&timerE);

              return (double)(timerE.QuadPart - timerB.QuadPart) / (double)Frequency.QuadPart * 1000.0;

       }

private:

       LARGE_INTEGER timerB, timerE, Frequency;

};

 

#endif

这个类使用很简单,就和秒表一样,先Start(),然后就可以用GetTime()不断读出逝去的时间;再一次Start(),重新开始计时。计时单位是ms。

现在,让我们测试一下哪个编译器编译的程序运行的更快。后面部分,请爱惜时间的人不要看,就当我在说梦话。

测试程序

#include "simulationTest.h"

#include "Timer.h"

 

int main()

{

       Timer a;

       double t = 0;

      for (int j = 0; j < 10; j++)

       {

              a.Start();

              for (int i = 0; i < 10; i++) SimuBankTest();

              t += a.GetTime();

       }

       cout << t/10;

       system("Pause");

       return 0;

}

#ifndef SimulationTest_H

#define SimulationTest_H

 

#include "Simulation.H"

 

void SimuBankTest()

{

      for (int i = 1; i < 11; i++)

       {

              Simulation a(i,480,1,3,4,10);

              a.Run();

       }

}

 

#endif

姑且不论我那Simulation写的怎么样,这个测试至少能反映不同情况下队列的平均性能。顺便和标准库比较一下,看看自己写的代码效率怎么样。使用STL需要对class Simulation改动一点代码,其实这是很简单的,如下的替换表:

“Queue.h”

Queue

IsEmpty()

EnQueue()

DeQueue()

<deque> using namespace std;

deque

empty()

push_back()

pop_front()

另外要把Simulation::Run()中的结果输出注释掉(PrintResult();)在我的机器上(C500、192RAM、Win2000sp3,关掉其他前台程序)结果如下:

IDE或者编译器

BCC32

BCC32-STL

VC6

VC6-STL

可执行文件大小(byte)

142,848

145,920

61,440

65,536

第一次测试结果(ms)

32.4848

42.325

35.4724

44.448

第二次测试结果(ms)

32.6191

41.4752

35.662

45.084

递三次测试结果(ms)

32.8919

41.9856

34.7238

43.9707

结果表明BCC32编译的略比VC6快一点,可是文件大小实在……(没有比较Dev-cpp,是因为这么比较对它不公平,另外400多K的生成文件,60多ms的结果实在拿不出手)这有一部分原因是我的代码造成的,例如运行简单的数学运算测试

#include <iostream.h>

#include "Timer.h"

int main()

{

       Timer a;

       a.Start();

      double s = 0, t;

      for (int i = 1; i <= 10; i++)

       {

              t = 1;

              for (int j = 1; j <= i; j++) t *= j;

              s += t;

       }

       cout << a.GetTime();

       return 0;

}

BCC32居然还是将近140K,0.00530794ms;VC6不到60K,0.00335238ms;VC6在大小和速度上都领先BCC32。

结果还表明,我们自己写的队列,性能要比BCC32和VC6的STL好,这对VC6有点不公平,很多人都知道VC6的deque性能不好,怎么尽和人家短处比。看到这个结果,不禁欣欣然,毕竟个人胡捣鼓出的垃圾代码,性能比大厂商的STL还好。其实,这只是那些大厂商对STL的投入不够,我拿了SGI-STL(VC6编译)测试了一下,编译后大小70K,结果大致是15ms左右,比我的代码效率高一倍,汗……

附注:如何在VC6中使用SGI-STL

首先到SGI下载一份STL,216K的zip包,真是个了不起的杰作……网上都是溢美之词。将stl.zip解压到一个目录,比如C:\SGISTL,然后在VC6的IDE环境下,Tools->options->Directories->Include files,将C:\SGISTL(你解压的目录)添加进去,然后,将这个路径移到最顶端,就OK了。还要注意的是,用VC6使用SGI-STL,文件中不能包含<iostream>,要用<iostream.h>代替(该死的标准)。如果你想用VC6的STL,只需要将C:\SGISTL移到底端就行了,真是太简单了(这就是IDE的好处)。BCC32就没这么容易了,BCB6我没试,所以我不知道它的IDE环境有没有解决方案。

综上所述,如果你开始在Win32上学习C++,VC6是最佳选择,强大的功能,简洁的界面,很高的性能(使用SGI-STL就更好了)。至于以后你是用VC还是BCB,那就是看你的应用方向和个人喜好了。——哎,又一篇垃圾文章问世了。另,STL都是源码格式的,哪位高人研究过为什么SGI-STL的性能非常好吗?告诉我一下,那种源码看得让人眼晕。

本文地址:http://com.8s8s.com/it/it1673.htm