学步园

error C2143: 语法错误 : 缺少“;”(在“using”的前面)

#include "B.h"

class A
{
  void f(B*);
};

#include "A.h"

class B
{
  void f(A*);
};

class B;
class A
{
  void f(B*);
};

#include "A.h"
#include "B.h"

void A::f(B*)
{
  //TODO...
};

【Question 4】

Q:为什么模板的声明及定义最好都写在头文件中呢？

A:这是因为，编译器自身的编译顺序在作祟。

当编译器编译模板时，

它会先将模板类(函数)用具体的实参来临时生成一个单独的类，

因此如果将使用模版的方法定义写在另一个文件中，

编译器无法获知其定义，

从而无法生成临时类。

还有，

也要将模板的实参类先提前声明，

不然编译器将无法识别。

就像这样：

class OtherClass;
template<typename T>
T* ToDo()
{
  return new T;
}

不过，

除此之外

解决模板无法识别实参Bug的方法还有几个，

欲知详情，

且听下次分解。

【Question 5】

Q：其他解决模板实参无法识别的方法有哪些呢？

A：除了上述将定义写在头文件中的办法之外，还有以下两个方法：

1.将模板函数声明为inline。

这个原理其实与之前的那个是相同的，

因为将函数声明为inline之后，

编译器也会将其视作类所在头文件内定义的函数。

不过需要一提的是，

inline关键字只需要在声明时注明即可，

定义时无需再写(virtual等与此同理)。

2.在使用模板的文件中包含定义模板方法的cpp文件。

首先要说明的是，

这个办法不一定行得通。

具体情况取决于编译器的心情。

可能大家会感到惊讶，

但是确实如此，

在VC等编译器中，

的确可以#include "xxx.cpp"

不过笔者并不推荐这种方法，

因为这样做，

与将所有定义都写在头文件中的做法无异，

而所产生的问题，

就是【Question 3】所提及的内容了。

但令笔者奇怪的事，

大多数人解决模板问题都是使用最后一种方法，

莫非是因为省时省力？

【Question 6】

Q:关于学好C++，有一些实用的技巧么？

A:恩，在笔者到大二为止的五年学习编程的时间内，

确实发现了一些实用技巧，可以提升自己的编程能力。

这些技巧并非专职某一门语言，

而是适用于整个领域的学习。

现于大家分享如下：

1.在手机，平板等随身携带电子设备中放入一本语言类的电子书。

例如《C++ primer》,并且将其放在显著位置，

从而提醒自己记得随时阅读。

2.每天编写一段程序。

就算不是一个连贯的项目也可以。

但是要记住，

争取每天都尝试一些之前没有尝试过的语法，

例如今天使用容器，明天尝试模板。

3.塑造自己的面向对象思想。

这是一个极为关键的步骤，

但却被大部分人(甚至一些程序员)所忽视。

因为只有当你具备了这种思想时，

你才可能在生活中感受到程序的存在。

例如说当你看到并行水管时，

可能会联想到协同线程，

从而思考如何去实现这个功能。

4.将一些编程网站放在自己的浏览器首页。

初级者可以设置CSDN博客频道，

进阶者可以尝试CoolShell.cn等专业编程网站。

甚至每天上cnBeta看一些科技新闻都是好的。

5.使用微博等社交网站关注一些程序员。

新浪微博上有

@左耳朵耗子，@做游戏的老G，@玉伯也叫射雕 @程序员杂志 等知名程序员微博。

但是切记，

尽量不要关注"程序员的幽默"之类的微博，

因为要记住，你是想学一些东西，

而不是每天娱乐自己。

6.学会翻墙。

尽管这条跟编程关系不大，

但仍然占据相当重要的位置。

校园网(联通)的局限太大，

不要被限制在这样一个小圈子里。

国外才是高科技的诞生地，

真正顶尖的知识都在墙外。

国外网站跟国内网站相比强在哪里？

大家请看，

这是中文版Hao123与国际版Hao123对比：

中文版

国际版

7.使用谷歌进行英文搜索(专业内容)。

尽管这有可能让百度不高兴，

但是笔者还是想说，

请各位尽量使用谷歌进行搜索。

而且不要搜中文，

因为那样出来的还是百度的答案，

要使用英文，

只有使用英文，

你才可以知道还有StackOverflow这样比X度知道强100000000倍的知识问答网站存在。

只有使用英文，

你才可以知道C++竟然还有官方参考文档。

8.读一些侧面提高自己编程能力的书。

这里的侧面，

就是指并非直接讲如何使用好某个语言，

而是类似于”如何编写整洁代码“之类的通用书。

要知道，

养成一个良好的编程习惯，

对未来的帮助远远胜于精通某门语言。

在这里笔者推荐几本：

《程序员的自我修炼》

《整洁代码之道》

《某某之美》系列(例如架构之美，算法之美)

9.读一些行业顶尖人物的传记。

这里说的顶尖人物，

并不是乔布斯之流的，

那些是广为人知的，

他们的成功自然不言而喻。

值得学习的程序员，

应当像下面这几位：

Linus Torvalds ——
Linux作者。

Bjarne
Stroustrup —— C++发明者。

James
Gosling —— Java发明者。

10.时刻提醒自己：我是极客。

笔者认为，

这是最重要的一点。

不论自己目前如何，

都要时刻告诉自己，

你要成为什么样的人。

只有这样，

你才可能有足够的动力去如饥似渴地学习更强大的技术。

只有这样，

你才有可能成为真正的极客。

你可以不会编写整洁代码，

你可以连如何调试都不会，

你可以什么语言都不拿手，

你可以什么算法都写不出来，

但是，

如果你想在这个行业前进，

就告诉自己：我是极客，我会成功。

这不是装B，

这是自信。

世界都可以否定你，

但你自己不能。

Never forget it.

/********数据结构系列********/参考这里

【Question 7】

Q：请问什么是数据结构？

A：简单来说，

数据结构就是处理数据集合的玩意儿。

是组织并处理数据的一种途径。

使用数据结构，

能够更为高效地处理数据。

但数据结构并不处理单个数据(尽管可以)，

而是处理一大块数据的集合。

【Question 8】

Q：怎样区分文件结构(File Structure)与存储结构(Storage Structure)？

A：区分这两者的关键是，

看他们被访问的内存区域。

处理在计算机主内存内的结构时，

就是指存储结构。

而处理外部结构时，

就是文件结构。

注意这两者可以相互转化。

【Question 9】

Q：什么时候应当使用二分法(Binary Search)？

A：具体来说，

在一个处理已经排序之后的集合时，

最适合使用二分法。

首先搜索从集合的中间开始，

如果中间的值并不是要找的那个，

就比较大小，

然后再根据结果去搜索小的那一半或者大的那一半。

然后再进行迭代，

直至找到目标值。

具体请看这里：

http://en.wikipedia.org/wiki/Binary_search_algorithm

【Question 10】

Q：什么是链表？

A：链表是指，

结点与结点之间连接起来的一个序列。

是一个形似链条的数据结构。

【Question 11】

Q：数据结构主要应用在哪些领域？

A：简而言之，

只要涉及到数据，

就应当使用数据结构。

例如数值分析，

系统设计，AI，编译器设计，

数据库管理，图形图像等等。

好像没有我没提到的领域了吧？

【Question 12】

Q：什么是LIFO。

A：LIFO的全称是Last In First Out，

顾名思义，

是指数据的存储方式为后进先出。

这样子的话，

最后一个放入的数据，

却可以最先被取出来。

而最先放入的数据，

却需要最后一个被取出。

使用这种方式的典型的结构就是堆栈(Stack)。

如果不理解的话，

就请想想一摞盘子。

【Question 13】

Q：什么是FIFO？

A：同上，

全称为First In First Out。

也是一种数据存储方式，

最先放入的数据最先被取出。

使用这种方式的典型结构是队列(queue)。

想象是一条长长的队伍。

【Question 14】

Q：什么是二叉树？

A：这个离散课讲过了吧。

就是一整个拥有两个节点(左节点与右节点)的数据结构。

值得一提的是，

二叉树是链表的一种。

【Question 15】

Q：什么是二分树？

A：二分树是二叉树的一种。

其左右节点遵循以下规则：

A的左节点小于A，A的右节点大于等于A。

【Question 16】

Q：链表到底是不是一种线性数据结构呢？

A：这个取决于，

你应用链表的情况。

如果使用其进行存储，

很明显，

它并不是线性存储的(因为地址并不连续)。

而如果你使用它来获取数据，

那当然就是线性的咯(因为你只需要this->Next()就够了)。

【Question 17】

Q：动态内存分配是如何在管理数据方便起到辅助作用的？

A：除了能用来存储简单的数据结构类型外，

动态内存分配也能结合不同结构的内存块从而形成一个复杂的结构。

这个结构可以根据需要进行扩展及收缩。

【Question 18】

Q：什么是合并排序(Merge Sort)？

A：合并排序采用了一种

“逐个击破”的方法用来对数据进行排序。

先将一堆数据打碎(分成1个单位)，

再将相邻的两个合并且排序为一个更大的数据集，

然后循环此过程，

直至最后所有数据合并为一个数据集。

请看下图：

【Question 19】

Q：什么是Push与Pop？

A：这个问题，

我猜中国的初学者问的更多一些。

Push的意思为压入，将数据存入集合中。

Pop的意思为弹出，将数据从集合中取出。

一般来说的话呢，

只是使用Pop或是Push，

会根据数据结构的类型存放/取出相应位置的数据。

【Question 20】

Q：什么是线性搜索？

A：线性搜索是指，

在一个连续的数据结构中搜索一个目标值。

使用这种方法呢，

每一个位于此目标值之前的的数据都要被检索并与目标值进行对比，

直至找到目标值的位置。

迭代器就是这种行为哈。

【Question 21】

Q：heap与stack相比有哪些优劣？

A：首先是，

heap比stack更灵活。

在分配内存的时候，

heap支持动态分配并且可以回收内存。

所带来的副作用是，

使用heap的速度要比stack慢一些。

【Question 22】

Q：什么是堆排序(heap sort)？

A：堆排序是指，

利用堆结构对一个数据集进行排序。

首先将数据集制作成一个堆，

然后将堆的根结点(堆中最大的数字)与子结点交换之后取出，

之后对现根结点执行WalkDown方法(堆的一种排序行为)

将所得堆的根结点再次与子结点交换，并取出。

循环此过程，

直至堆中结点全被取出为止。

此过程如下图示：

【Question 23】

Q：堆排序有什么特点么？

A：最让人兴奋的是，

这个排序的最慢速度为O(n*log2n）要优于快速排序的最慢速度O(n*n)。

不过需要注意，它是不稳定的(稳定的是合并排序)。

除此之外，

它还是In-Place Algorithm。

至于什么是In-Place Algorithm，

请看下个问题。

【Question 24】

Q：什么是In-Place Algorithm？

A：中文名是原地算法。

故名思域，

就是将算法输出的数据存放在输入数据的位置上，

换言之，就是将原有数据进行替换。

这样做的效率要高于重新分配内存，

【Question 25】

Q：有哪些排序算法是原地算法？

A：很多。

冒泡排序，

选择排序，

插入排序，

希尔排序，

还有上述的堆排序等等。

不过值得注意的是，

快速排序并不是原地算法哦。

【Question 26】

Q：什么是dequeue？

A：dequeue就是，

双向的queue。

普通的queue只能从队列的一端(通常是末端)进行插入及删除操作。

而dequeue则可以选择任何一端。

【Question
27】

Q：什么是AVL Tree？

A：AVL Tree就是自平衡二叉查找树。

在这个树中，

任何一个结点的左右子结点的高度差最大为一。

例如下图：

【Question 28】

Q：AVL Tree的查找，删除等时间复杂度怎样呢？

A：AVL树的查找，插入，删除，

在平均和最坏的情况下都是O(log2 n)。

【Question
29】

Q：AVL Tree最大特点是什么？

A：是AVL旋转。

正因上述所说的那样，

AVL树需要随时保持自平衡(任何一个节点左右树高度最大为1)。

因此当插入或删除某个节点时，

破坏了平衡之后，

要进行AVL旋转恢复平衡。

此旋转分为四种：

(1)左左情况

如上图所示，

很明显看到5节点的左子树高度为3，而右子树高度为1，二者差为2，不平衡。

左边的多，那我们就向右旋转。

旋转规律需要大家自己去发现，

因为这个用语言非常难以形容，

但是要记住最后要让中间的那个节点为新的根节点。

(2)右右情况

同上正好相反。

右边多，我们就向左旋转。

(3)左右情况

当左子树的右节点多的时候，就要先进行左旋转，再进行右旋转操作。

首先左旋转的时候大家先忽略根结点5的话可能更容易理解，

然后形成左左情况，再重复(1)就OK了。

(4)右左情况

又是与上一个正好相反。

希望大家仔细观察图片，

好好理解AVL树的旋转过程。

笔者在刚刚学习这个的时候花了半个小时才完全弄懂此过程，

估计各位读者比笔者要聪明很多，

但也请用心去理解。

这样才有可能编写其代码。

(注：图片全部来自于维基百科,并经过笔者编辑)

【Question 30】

Q：什么是双向链表(Doubly linked list)？

A：双向链表是一种特殊的链表。

其最大特点是既可以正向遍历，也可以反向遍历。

顺便一提，

在c++中使用rbegin或rend来进行反向遍历。

【Question
31】

Q：什么是霍夫曼(Huffman)算法？

A：霍夫曼算法，

用来创建到给定权重具有最小权重路径长度的扩充二叉树。

例如创建一个包含出现几率较大的数据元素的表。

更多关于霍夫曼的事情请参考如下网址：

http://en.wikipedia.org/wiki/Huffman_coding

【Question 32】

Q：单链表的删除节点需要注意哪些事项？

A：注意要分情况。

当删除头节点时，

将Head指针指向第二个节点之后

再free头节点。

如果删除的是中间节点，

则需要将Next指针指向后一个节点，

再free此节点。

注意在单链表中插入节点与此过程相似。

【Question
33】

Q：如果不改变位置地删除或插入一个元素，什么结构最省时？

A：假设以下几种结构：

数组，链表，双向链表，单独存储head指针的双向链表。

在不改变原有结构的元素位置情况下，

使用数组最快。

其他的结构更适合动态插入删除元素。

【Question
34】

Q：是否可以使用栈(stack)来实现队列(queue)的功能？

A：可以。

需要使用两个栈A与B。

其中放入数据(Push)就压入A中。

取出(Pop)时先将A中的数据压入B中，

再从B中弹出数据即可(相当于对集合进行两次逆序排列，就成了正序)。

【Question
35】

Q：在涉及到内存管理的时候，C++中的堆(Stack)与栈(Heap)区别在哪里？

A：首先要注意的是，

这里的堆栈并非数据结构中的堆栈，

而是内存管理中的区域。

其中，

栈区的作用是存放函数的参数，局部变量的值等。

存储方式类似于Stack。

因为由编译器决定(连续的)内存大小，

因此内存受限(一般较小)。

所有会有大家常说的栈溢出(Stack Overflow)。

而堆区的作用是存放程序员自己开辟的变量空间的值，

例如使用 malloc,或new 创建的空间就在堆中。

存储方式类似于链表(而不是Heap！)。

因为使用链表结构，

内存空间并非连续的，

因此可以扩展较大的内存空间。

注意栈区由系统自动分配释放，堆区需要程序员自己开辟释放。

栈一般较快，堆较慢(因为需要使用指针先寻址并且是不连续内存块)。

【Question
36】

Q：除了上述两个内存区外，还有哪些内存区？

A：上述的两个内存区为动态数据区。

除了动态数据区，还有静态数据区与代码区。

静态数据区包括：

全局(静态)区，文字常量区。

全局区就是存放全局变量与静态变量的，

但是要注意初始化的与未初始化的全局变量并不在一块，

而是被分隔开了(但仍在全局区)。

文字常量区就是存放字符串常量的区域。

它与全局区都会在程序结束后被系统释放掉。

而程序代码区就是存放函数体的二进制代码的区域。

【Question
37】

Q：我该如何查看一个变量的地址？

A：这个很简单，

可以使用通配符"0x%08X"来输出地址：

int someVar = 0;
printf("0x%08X",&someVar);

【Question 38】

Q：可以多讲一点关于堆的事么？

A：好的。

首先大家要注意堆中包含两个指针:栈顶指针ESP与基(栈底)指针EBP。

基指针指向栈底(先压入)，栈顶指针指向栈顶(最后压入)。

这个过程中有一点很关键，

就是基指针的地址要大于等于栈顶指针的地址。

例如：

基指针地址：   0X0022ff50

栈顶指针地址：0X0022ff4C

过程是：EBP被压入->变量被压入(函数参数的话从右往左)

->ESP被压入->移动EBP开始新一轮压入。

【Question
39】

Q：ESP与EBP全称是什么？

A：这个很好记：

ESP——Extended Stack Pointer

EBP——Extended Base Pointer

【Question
40】

Q：可以简单概括一下什么是先序遍历，中序遍历以及后序遍历么？

A：三句话，

先序遍历：根结点->左节点->右节点。

伪代码：

void Traverse(Tree t)
{
	if(NULL != t)
	{
		visit(t);
		Traverse(t ->left);
		Traverse(t ->right);
	}
}

中序遍历：左节点->根结点->右节点。

伪代码：

void Traverse(Tree t)
{
	if(NULL != t)
	{
		Traverse(t ->left);
		visit(t);
		Traverse(t ->right);
	}
}

后序遍历：左节点->右节点->根结点。

伪代码：

void Traverse(Tree t)
{
	if(NULL != t)
	{
		Traverse(t ->left);
		Traverse(t ->right);
		visit(t);
	}
}

【Question 41】

Q：能简要地阐述一下完全二叉树与满二叉树的区别吗？

A：首先要记住，

我们一般常识性认为的满树，

左右结点都齐全，

深度为k，

且有2^k - 1个结点的二叉树就是满二叉树。

而完全二叉树在其拥有的n个结点中，

每一个结点都与满二叉树中的第1~n个结点一一对应。

简单来说，

因为二叉树的结点序号是按照 :父节点->左子树->右子树的顺序排列的，

因此如果一棵二叉树的最后两层中，

出现有左子树而没有右子树的情况下，

基本可以断定这是一个完全二叉树。

二者如下所示：

To be continue……