C++口试相关.二（转）

C++面试相关.二（转）
双向链表的查找节点。

考点：双向链表的操作
出现频率：★★★★
解析：
使用right指针遍历，直至找到数据为data的节点，如果找到节点，返回节点，否则返回NULL。
1       //查找节点，成功则返回满足条件的节点指针，否则返回NULL
2         DbNode *FindNode(DbNode *head, int data)   //参数1是链表的表头节点
3         {                                          //参数2是要查找的节点,其数据为data
4                DbNode *pnode = head;
5     
6                if (head == NULL)                     //链表为空时返回NULL
7                {
8                         return NULL;
9                }
10   
11              /*找到数据或者到达链表末尾退出while循环*/
12              while (pnode->right != NULL && pnode->data != data)
13              {
14                       pnode = pnode->right;             //使用right指针遍历
15              }
16   
17              //没有找到数据为data的节点，返回NULL
18              if (pnode->right == NULL)
19              {
20                       return NULL;
21              }
22
23              return pnode;
24     }


解释什么是模板的特化（template specialization）?----------------

考点：模板的特化的理解
出现频率：★★★
解析：
模板的特化（template specialization）分为两类：函数模板的特化和类模板的特化。
（1）函数模板的特化：当函数模板需要对某些类型进行特别处理，称为函数模板的特化。例如：
1       bool IsEqual(T t1, T t2)
2       {
3                return t1 == t2;
4       }
5
6       int main()
7       {
8                char str1[] = "Hello";
9                char str2[] = "Hello";
10              cout << IsEqual(1, 1) << endl;
11              cout << IsEqual(str1, str2) << endl;   //输出0
12              return 0;
13     }
代码11行比较字符串是否相等。由于对于传入的参数是char *类型的，max函数模板只是简单的比较了传入参数的值，即两个指针是否相等，因此这里打印0。显然，这与我们的初衷不符。因此，max函数模板需要对char *类型进行特别处理，即特化：
1         template <>
2       bool IsEqual(char* t1, char* t2)           //函数模板特化
3       {
4                return strcmp(t1, t2) == 0;
5       }
这样，当IsEqual函数的参数类型为char* 时，就会调用IsEqual特化的版本，而不会再由函数模板实例化。
（2）类模板的特化：与函数模板类似，当类模板内需要对某些类型进行特别处理时，使用类模板的特化。例如：
1         template <class T>
2       class compare
3       {
4       public:
5                bool IsEqual(T t1, T t2)
6                {
7                         return t1 == t2;
8                }
9       };
10   
11     int main()
12     {
13              char str1[] = "Hello";
14              char str2[] = "Hello";
15              compare<int> c1;
16              compare<char *> c2;  
17              cout << c1.IsEqual(1, 1) << endl;        //比较两个int类型的参数
18              cout << c2.IsEqual(str1, str2) << endl;   //比较两个char *类型的参数
19              return 0;
20     }
这里代码18行也是调用模板类compare<char*>的IsEqual进行两个字符串比较，显然这里存在的问题和上面函数模板中的一样，我们需要比较两个字符串的内容，而不是仅仅比较两个字符指针。因此，需要使用类模板的特化：
1         template<>
2       class compare<char *> //特化(char*)
3       {
4       public:
5                bool IsEqual(char* t1, char* t2)
6                {
7                         return strcmp(t1, t2) == 0;         //使用strcmp比较字符串
8                }
9       };
注意：进行类模板的特化时，需要特化所有的成员变量及成员函数。


双向链表的打印。-----------------------------

考点：双向链表的操作
出现频率：★★★★
解析：
与测长的方法一样，使用right指针进行遍历。
1       //打印整个链表
2       void PrintList(DbNode *head)             //参数为链表的表头节点
3       {
4                DbNode *pnode = NULL;
5     
6                if (head == NULL)                  //head为NULL表示链表空
7                {
8                         return;
9                }
10              pnode= head;
11              while (pnode != NULL)
12              {
13                       printf("%d ", pnode->data);
14                       pnode = pnode->right;          //使用right指针遍历
15              }
16              printf("\n");
17     }