1、程序员经典1 双向链表的查找节点。考点：双向链表的操作出现频率：解析：使用 right 指针遍历，直至找到数据为 data 的节点，如果找到节点，返回节点，否则返回NULL。1 /查找节点，成功则返回满足条件的节点指针，否则返回 NULL2 DbNode *FindNode(DbNode *head, int data) /参数 1 是链表的表头节点3 /参数 2 是要查找的节点,其数据为 data4 DbNode *pnode = head;56 if (head = NULL) /链表为空时返回 NULL7 8 return NULL;9 1011 /*找到数据或者到达链表末尾退出 whi
2、le 循环*/12 while (pnode-right != NULL /使用 right 指针遍历15 1617 /没有找到数据为 data 的节点，返回 NULL18 if (pnode-right = NULL)19 20 return NULL;21 2223 return pnode;24 2 考点：模板的特化的理解出现频率：解析：模板的特化（template specialization）分为两类：函数模板的特化和类模板的特化。（1）函数模板的特化：当函数模板需要对某些类型进行特别处理，称为函数模板的特化。例如：1 bool IsEqual(T t1, T t2)2 3 retu
3、rn t1 = t2;4 56 int main()7 8 char str1 = “Hello“;9 char str2 = “Hello“;10 cout 2 bool IsEqual(char* t1, char* t2) /函数模板特化3 4 return strcmp(t1, t2) = 0;5 这样，当 IsEqual 函数的参数类型为 char* 时，就会调用 IsEqual 特化的版本，而不会再由函数模板实例化。（2）类模板的特化：与函数模板类似，当类模板内需要对某些类型进行特别处理时，使用类模板的特化。例如：1 template2 class compare3 4 publi
4、c:5 bool IsEqual(T t1, T t2)6 7 return t1 = t2;8 9 ;1011 int main()12 13 char str1 = “Hello“;14 char str2 = “Hello“;15 compare c1;16 compare c2;17 cout 2 class compare /特化(char*)3 4 public:5 bool IsEqual(char* t1, char* t2)6 7 return strcmp(t1, t2) = 0; /使用 strcmp 比较字符串8 9 ;注意：进行类模板的特化时，需要特化所有的成员变量及
5、成员函数。3 考点：双向链表的操作出现频率：解析：与测长的方法一样，使用 right 指针进行遍历。1 /打印整个链表2 void PrintList(DbNode *head) /参数为链表的表头节点3 4 DbNode *pnode = NULL;56 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(“
6、 “);17 4 考点：类模板的实例化的理解出现频率：1 template2 class Array 3 4 ;5 void foo( )6 7 Array arr1;8 Array arr4, arr5;9 Array arr2, arr3;10 Array arr6;11 12 How many instances of the template class Array will get instantiated inside thefunction foo()A 3 B 6 C 4 D 1解析：模板类（template class）的实例个数是由类型参数的种类决定的。代码 7 行和 9
7、行实例化的模板类都是 Array，代码 8 行实例化的模板类是 Array，代码 10 行实例化的模板类是Array。一共是三个实例。答案：A5 考点：双向链表的操作出现频率：解析：为了得到双向链表的长度，需要使用 right 指针进行遍历，直到得到 NULL 为止。1 /获取链表的长度2 int GetLength(DbNode *head) /参数为链表的表头节点3 4 int count = 1;5 DbNode *pnode = NULL;67 if (head = NULL) /head 为 NULL 表示链表空8 9 return 0;10 11 pnode = head-righ
8、t;12 while (pnode != NULL)13 14 pnode = pnode-right; /使用 right 指针遍历15 count+;16 1718 return count;19 更多精彩内容，请到“融智技术学苑 rzchina”使用模板有什么缺点？如何避免？6 考点：理解模板编程的缺陷出现频率：解析：templates（模板）是节省时间和避免代码重复的极好方法，我们可以只输入一个类模板，就能让编译器实例化所需要的很多个特定类及函数。类模板的成员函数只有被使用时才会被实例化，所以只有在每一个函数都在实际中被使用时，我们才会得到这些函数。确实这是一个很重要的技术，但是如果不
9、小心，使用模板可能会导致代码膨胀。什么是代码膨胀？请看下面的例子：1 template2 class A3 4 public:5 void work()6 7 cout data = data;6 pnode-left = pnode-right = pnode; /创建新节点时7 /让其前驱和后继指针都指向自身8 return pnode;91011 /创建链表12 DbNode *CreateList(int head) /参数给出表头节点数据13 /表头节点不作为存放有意义数据的节点14 DbNode *pnode = (DbNode *)malloc(sizeof(DbNode);15
10、 pnode-data = head;16 pnode-left = pnode-right = pnode;1718 return pnode;19 2021 /插入新节点,总是在表尾插入; 返回表头节点22 DbNode *AppendNode(DbNode *head, int data) /参数 1 是链表的表头节点，23 /参数 2 是要插入的节点,其数据为 data24 DbNode *node = CreateNode(data); /创建数据为 data 的新节点25 DbNode *p = head, *q;2627 while(p != NULL)28 29 q = p;30 p = p-right;31 32 q-right = node;33 node-left = q;3435 return head;36 我们可以使用其中的 CreateList()和 AppendNode()来生成一个链表，下面是一个数据生成从0 到 9 含有 10 个节点的循环链表。1 DbNode *head = CreateList(0); /生成表头，表头数据为 0
