2022年数据结构学习线性链式结构总结 .pdf

《2022年数据结构学习线性链式结构总结 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构学习线性链式结构总结 .pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构学习（ C+ ）线性链式结构总结（代后记）【1】 happycock （原作）转自 CSDN 看到这个标题， 有些人一定松了一口气这小子可算白话完了，当然了，你要是略有惋惜之情，我真是受宠若惊。但不论你怎么想，写到这里只是告一段落，并没有完，后面还有很大一部分呢，比如树、图、查找、排序这么多年了，还是这点东西。 代后记的意思是， 我觉得对前面线性链式结构的总结，对后面的学习有指导意义： 从前面的学习中， 你能得出如何学习数据结构，以及如何正确看待这门课如果你能从重复建设中看到这样做的价值，你才能真正理解这门课的意义。在开始总结前，先整理一下以前的代码，假定你使用的是VC6，你的工程中现

2、在应该有这几个主要文件：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 ） ，不写怪怪的代码，通用性应该不是问题，但实际上不是这样。 所以，我不得不

3、花一些篇幅介绍如何修改以前的代码，所以，这篇文章就只能是 【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 循环内。

4、但是在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 m

5、ain() 一个道理）？但这合情合理的做法是违反标准的（让人想起了什么），到了 BCC32，人家不干了，非让给个返回值，可以添加return 0;了事，两边都不得罪；或者，定义void operator，一样两边都认可。 VC7 也要求 operator必须有返回值，还是标准的力量大啊。修正如上的问题之后，BCC32 就能编译了，但是还是一大堆waining ，这是我写作的风格导致的。 C+标准说，如果在类体内定义函数（而不是声明原型），那个函数被自动内联；也就是说， 我的那些类的成员函数，编译器都认为我想让他们成为内联函数，但是有些函数是不能内联的，于是编译器就说“你的要求太高了，我办不到”

6、我也没想让你受累啊，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - 自找麻烦的编译器。胡弄过去 BCC32 后，再拿Dev-cpp 试试，晕了，上百个error 和 warning。其实这是个连锁反应，首先，在GNU C+ 中， iostream.h 这个头文件被废弃了，强烈建议使用iostream（总觉得象大棒） ， 还好 VC6、 BCC32 也认这个。 改了这个， 又来了一个啼笑皆非的warning ，文件尾必须要有一个空

7、行？！我以前为了紧凑，有空行也删掉了，得，听你的，加上。这些都完事之后， Dev-cpp 就通过了，没有warning。这样修改完后，那些代码3 个编译器就都能编译了，看一下编译的exe 文件大小， VC6的最小（ Release版） ，BCC32 的大一点， Dev-cpp 的, 大得太可怕了，我不清楚是不是编译器的参数问题，但是GNU C+ 能在 Win32 下使用，都是经过转换的，不知道是不是这个原因。突然有个想法，哪个编译器编译的exe 文件运行的更快？哪个编译器效果更好？首先，要写个计时器， 这方面有人写过文章，我参考了一些人的，做了一个封装， 如下：#ifndef Timer_H

8、#define Timer_H #include 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; privat

9、e: LARGE_INTEGER timerB, timerE, Frequency; ; #endif 这个类使用很简单，就和秒表一样，先Start()，然后就可以用GetTime() 不断读出逝去的时间；再一次Start()，重新开始计时。计时单位是ms。现在， 让我们测试一下哪个编译器编译的程序运行的更快。后面部分， 请爱惜时间的人不要看，就当我在说梦话。测试程序#include simulationTest.h 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4

10、页 - - - - - - - - - #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

11、(int i = 1; i 11; i+) Simulation a(i,480,1,3,4,10); a.Run(); #endif 姑且不论我那Simulation写的怎么样，这个测试至少能反映不同情况下队列的平均性能。 顺便和标准库比较一下，看看自己写的代码效率怎么样。使用 STL 需要对 class Simulation改动一点代码，其实这是很简单的，如下的替换表：“ Queue.h ”QueueIsEmpty()EnQueue()DeQueue() using namespace std;dequeempty()push_back()pop_front()另外要把Simulation

12、:Run() 中的结果输出注释掉（PrintResult(); ）在我的机器上（C500、192RAM 、Win2000sp3，关掉其他前台程序）结果如下：IDE 或者编译器BCC32BCC32-STLVC6VC6-STL可执行文件大小（byte）142,848145,92061,44065,536第一次测试结果（ms）32.484842.32535.472444.448第二次测试结果（ms）32.619141.475235.66245.084递三次测试结果（ms）32.891941.985634.723843.9707结果表明 BCC32 编译的略比VC6 快一点，可是文件大小实在, （没有

13、比较Dev-cpp，是名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - 因为这么比较对它不公平，另外400 多 K 的生成文件，60 多 ms 的结果实在拿不出手）这有一部分原因是我的代码造成的，例如运行简单的数学运算测试#include #include Timer.h int main() Timer a; a.Start(); double s = 0, t; for (int i = 1; i = 10; i+) t =

14、1; for (int j = 1; j = i; j+) t *= j; s += t; cout options-Directories-Include files，将 C:SGISTL （你解压的目录）添加进去，然后，将这个路径移到最顶端，就OK 了。还要注意的是，用VC6 使用 SGISTL，文件中不能包含，要用 代替（该死的标准） 。如果你想用VC6 的 STL，只需要将C:SGISTL 移到底端就行了， 真是太简单了 （这就是IDE 的好处）。BCC32 就没这么容易了，BCB6 我没试，所以我不知道它的IDE 环境有没有解决方案。综上所述，如果你开始在Win32 上学习 C+，VC6 是最佳选择，强大的功能，简洁的界面，很高的性能（使用SGISTL 就更好了）。至于以后你是用VC 还是 BCB ，那就是看你的应用方向和个人喜好了。哎，又一篇垃圾文章问世了。另，STL 都是源码格式的，哪位高人研究过为什么SGISTL 的性能非常好吗？告诉我一下，那种源码看得让人眼晕。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -