【Draco徐C++学习心得】模板和基础数据结构【初阶】.docx

应大家的强烈要求，今天专写模板和基础数据结构的设计。模板模板应该是C+里面篇幅最少的东西了。模板，顾名思义，就是模板0 0费尽心机的重载，不如一个模板来的痛快。模板的使用：模板带来的便利不仅仅是函数上的。学C+多少会对STL有所了解。STL的全称是Standard Template Library，标准模板库。做COM的ATL全称是Active Template Library，活动模板库。由此可见模板的应用是多么广泛。但是小徐先跟大家说一个前提：不论是模板类还是模板函数，它们的实现最好放在一起。也就是说，在.h文件中声明的模板，最好不要在.cpp中实现，而是将实现代码一并放入.h文件中，最后在.h文件的开头加上#pragma once编译指令。你们可能说了，这样.h不会变的臃肿了么。小徐也没办法，对于模板的支持每款编译器都不一样，而且越老的编译器对模板的支持就越差，小徐也是因为这个原因舍弃了VC6的编译器，换成VS2008。见过很多解决这种方法的案例，一般是在.h文件中写入声明，将实现写在.inl文件中，然后在.h文件的末尾加入#include XXX.inl模板类的使用大家可以参照STL的实现代码，因为STL本身就是个非常好的例子。小徐也没法说的太详细，因为模板这东西本来就很浅，但是用的好会非常犀利。模板的特例还是拿上面的add函数举例子。如果我传入的参数是char *，即两个字符串，让两个字符串相加，即首尾相连的话，我们就不能单纯的用数值相加来操作了，因为传进来的是两个地址，而且字符串连接需要一些特殊的代码，于是我们：可以看到上图在使用特例化后的模板类和模板函数的时候，模板的参数表不能少，是几个还是要传入几个。额，恩，还有，在模板列表中class和typename是一样的。模板特例化有一个非常有意思的应用是编译时类型特征的提取：这段代码来自lua_tinker.h，是目前很流行的对Lua进行C API封装的代码。对lua感兴趣的同学可以到网上下载，只有两个文件，lua_tinker.h和lua_tinker.cpp。讲解的不要，自己琢磨琢磨。-我-是-分-割-线-数据结构当你认为本次日志的重头戏来了的时候，你就错啦。不瞒你们说，小徐去年考数据结构是靠抄的。所以本着考试心情的童鞋可以就此打住了。小徐只能讲讲数据结构的一些常用的结构和使用方法，如何设计等等。复杂度神马的不会，查找效率神马的没有，要看公式的也可以就此打住了。数据结构最最最最最简单的结构是线性表。何为线性表？就是数组啦。忽视忽视。用得最多扩展最多的是链表结构：数据结构是一种动态的结构，可以动态的插入或删除数据，没有数组这种结构的容量上限。所以结点之间手拉手是最好的选择啦。前一个结点的pnext指针成员指向了下一个结点的地址，这句话应该很好理解吧。好比同学们站好队，我从队伍最后面看只能看到一个人：我只能看到D。但是我想找A，显然D也看不到A，于是D问C能看到么，C也看不到；于是C再问B，然后B说A就在我前面啊。D被称为首结点，一般情况下我们只需要记住首结点就可以了。每个数据结构中都充斥了这种指向型的结构。比如树也是，哈希表也是，图也是。所以理解不了这种指向的概念，就没有办法继续向下学习。数据结构的效率效率分为两个方面：插入效率和查找效率。插入效率最高的莫过于链表，因为我只要让新的结点指向首结点，然后让这个新的结点变成首结点就可以了。但是查找效率就很低了。就像上面说的，我想找到A，必须要从D一路问过去。而树这种结构就相对便捷一些：这样我从D开始，通过某种约定在C和B之中选择了B，然后再找到了A。这样不就更快捷了么？这是查找效率的提升。但是因为这种提升，插入效率就变了慢了一些。如果我们要插入一个E：从D开始，通过某种约定选择B，然后再通过某种约定确定E应该作为B的左子结点被插入。这显然就比链表的插入要慢一些了。所谓某种约定，是我们自己定义的，最常见的约定是二叉树的左子节点比右子节点小：对于数据结构来说，最快的插入和查找效率应该是即时插入和查找，就像数组一样，只需要对指针进行偏移就可以了，比如：int a10000=.;我们要找第9999个数据，只需要：a9999;就可以了。那么在数据结构中我们可不可以实现这种查找非常快捷的方式呢？答案是可以的，就是哈希表。哈希表可以被认为是一个定长的线性空间，就像一个数组一样。它存储的数据包括两个部分，即：键和值，就像我要找到小明的户籍资料，只需要向户籍库提供“小明”这个名字key，然后库就能返回资料这个value一样。“小明”这个名字作为一个key，需要以此为根据，以某种约定插入到表中去。怎么插？“小明”是一个字符串呢。所以我们就需要一个函数，即哈希函数，通过某种算法，把字符串算成数字：int f(char *) /do r = f(小明);r就作为哈希表的偏移量，被称为哈希值。用r将信息插入进去，再查找的时候，只需要再进行一下函数的运算，即可即时的找到我们存储的资料。所以哈希表的效率看起来只和哈希函数有关。现在有两个问题：1.前面提到的哈希表是“定长的线性空间”，所以它容量有限2.两个不同的key会有可能通过哈希函数的运算得到的哈希值是一样的，怎么解决。问题2提到的就叫做冲突。即两个key不一样，但是算出来的哈希值是一样。通常解决的方法是移位：假设小明和小李的哈希值一样，由于小明在之前已经插入到3位置，于是小李向后窜一位，插入到4位置。这么做问题2算是解决了。问题一怎么解决呢？我们可以把哈希表和链表结合成一体：我们可以把小李这个结点像链表一样挂接在小明后面，让小明来指向小李。这样做我们就可以解决容量不足的问题了，只不过牺牲了一点查找效率。因为我们如果要找到小李，首先要找到小明。链表的结点查找叫做迭代。拉链式哈希表的查找分为哈希值偏移和迭代。这样我们需要认清楚一点：设我们要存储的数据总量为R，那么理想中的拉链式哈希表线性空间和每个拉链的长度（即最多结点数）为根号R。最差的查找效率为进行根号R次的迭代。使用哈希表确实效率很不错，但是它的缺点在于需要对数据总量有一个大概的把握，这样才能合理的分配线性空间。基于此，目前运用的最广泛的还是树结构。树也有很多分支，比如二叉树，B树等等。数据结构的编写非常能锻炼一个人的代码功底。数据结构学的这么差的小徐都不好意思说自己做了很长时间的数据结构编程。而且最糟糕的是数据结构编程是不可视的，而且在刚开始学习编写的时候很容易造成程序崩溃，比如内存的二次