程序员面试精选.doc

程序员经典1双向链表的查找节点。考点：双向链表的操作 出现频率： 解析： 使用 right 指针遍历，直至找到数据为 data 的节点，如果找到节点，返回节点，否则返回 NULL。 1 /查找节点，成功则返回满足条件的节点指针，否则返回 NULL 2 DbNode *FindNode(DbNode *head, int data) /参数 1 是链表的表头节点 3 /参数 2 是要查找的节点,其数据为 data 4 DbNode *pnode = head; 56 if (head = NULL) /链表为空时返回 NULL 7 8 return NULL; 9 1011 /*找到数据或者到达链表末尾退出 while 循环*/ 12 while (pnode->right != NULL /使用 right 指针遍历 15 1617 /没有找到数据为 data 的节点，返回 NULL 18 if (pnode->right = NULL) 19 20 return NULL; 21 22 23 return pnode; 24 2考点：模板的特化的理解出现频率：解析：模板的特化（template specialization）分为两类：函数模板的特化和类模板的特化。（1）函数模板的特化：当函数模板需要对某些类型进行特别处理，称为函数模板的特化。例如：1 bool IsEqual(T t1, T t2)2 3 return 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 public: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 ;注意：进行类模板的特化时，需要特化所有的成员变量及成员函数。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(“ “);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 行实例化的模板类都是 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->right;12 while (pnode != NULL)13 14 pnode = pnode->right; /使用 right 指针遍历15 count+;16 1718 return count;19 更多精彩内容，请到“融智技术学苑 rzchina”使用模板有什么缺点？如何避免？6考点：理解模板编程的缺陷出现频率：解析：templates（模板）是节省时间和避免代码重复的极好方法，我们可以只输入一个类模板，就能让编译器实例化所需要的很多个特定类及函数。类模板的成员函数只有被使用时才会被实例化，所以只有在每一个函数都在实际中被使用时，我们才会得到这些函数。确实这是一个很重要的技术，但是如果不小心，使用模板可能会导致代码膨胀。什么是代码膨胀？请看下面的例子：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 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); /生成表头，表头数据为 023 for (int i = 1; i >2 class3 ，例如我们需要定义一个表示平面的点（Point）类，这个类有两个成员变量分别表示横坐标和纵坐标，并且这两个坐标的类型可以是 int、float、double 等等类型。因此可能写出类似Point_int_int、Point_float_int、Point_float_float 等这样的类。通过类模板，我们只需要写一个类。1 #include2 using namespace std;34 template5 class Point_T6 7 public:8 T1 a; /成员 a 为 T1 类型9 T2 b; /成员 b 为 T2 类型10 Point_T() : a(0), b(0) /默认构造函数11 Point_T(T1 ta, T2 tb) : a(ta), b(tb) /带参数的构造函数12 Point_T /赋值函数13 friend Point_T operator +(Point_T /重载+14 ;1516 template17 Point_T20 this->b = pt.b;21 return *this;22 2324 template25 Point_T operator +(Point_T 28 temp.a = pt1.a + pt2.a; /结果对象中的 a 和 b 分别为两个参数对象的各自 a 和 b 之和29 temp.b = pt1.b + pt2.b;30 return temp;31 3233 template34 ostream37 p_node->next = p_node + 1;38 p_node = p_node->next;39 n_idx+;40 41 p_node->data = n;42 p_node->next = pRet;43 4445 return pRet;46 4748 int main()49 50 node *pList = NULL;51 node *pIter = NULL;52 int n = 20;53 int m = 6;5455 /* 构造单向循环链表 */56 pList = node_create(n);5758 /* Josephus 循环取数 */59 pIter = pList;60 m %= n;61 while (pIter != pIter->next)62 63 int i = 1;6465 /* 取到第 m-1 个节点 */66 for (; i next;69 7071 /* 输出第 m 个节点的值 */72 printf(“%d “, pIter->next->data);7374 /* 从链表中删除第 m 个节点 */75 pIter->next = pIter->next->next;76 pIter = pIter->next;77 78 printf(“%d “, pIter->data);7980 /* 释放申请的空间 */81 delete pList;82 return 0;83 10举例说明什么是泛型编程考点：泛型编程的基本概念出现频率：解析：泛型编程指编写完全一般化并可重复使用的算法，其效率与针对某特定数据类型而设计的算法相同。所谓泛型，是指具有在多种数据类型上皆可操作的含意，在 C+中实际上就是使用模板实现。举一个简单的例子，比如我们要比较两个数的大小，这两个数的类型可能是 int，也可能是float，还有可能是 double。一般编程时我们可能这样写函数（不考虑使用宏的情况）：1 int max(int a, int b) /参数和返回值都是 int 类型2 3 return a > b? a: b;4 56 float max(float a, float b) /参数和返回值都是 float 类型7 8 return a > b? a: b;9 1011 double max(double a, double b) /参数和返回值都是 double 类型12 13 return a > b? a: b;14 可以看到，上面写了 3 个重载函数，他们的区别仅仅只是类型（参数及返回值）不同，而函数体完全一样。而如果使用模板，我们可以这样写：1 template /class 也可用 typename 替换2 T max(T a, T b) /参数和返回值都是 T 类型3 4 return a > b? a: b;5 这里的 class 不代表对象的类，而是类型（可用 typename 替换） 。这样 max 函数的各个参数以及返回值类型都为 T，对于任意类型的两个数，我们都可以调用 max 求大小，测试代码如下：1 int main()2 3 cout ”操作符（因为 max 函数体使用了这个操作符） 。显然，使用泛型编程（模板）可以极大地增加了代码的重用性。11考点：单链表的操作出现频率：已知两个链表 head1 和 head2 各自有序，请把它们合并成一个链表依然有序。使用非递归方法以及递归方法。解析：首先介绍非递归方法。因为两个链表 head1 和 head2 都是有序的，所以我们只需要找把较短链表的各个元素有序的插入到较长的链表之中就可以了。源代码如下：1 node* insert_node(node *head, node *item) /head != NULL2 3 node *p = head;4 node *q = NULL; /始终指向 p 之前的节点56 while(p->data data 9 p = p->next;10 11 if (p = head) /插入到原头节点之前12 13 item->next = p;14 return item;15 16 /插入到 q 与 p 之间之间17 q->next = item;18 item->next = p;19 return head;20 2122 /* 两个有序链表进行合并 */23 node* merge(node* head1, node* head2)24 25 node* head; /合并后的头指针26 node *p;27 node *nextP; /指向 p 之后2829 if ( head1 = NULL ) /有一个链表为空的情况，直接返回另一个链表30 31 return head2;32 33 else if ( head2 = NULL )34 35 return head1;36 3738 / 两个链表都不为空39 if(length(head1) >= length(head2) /选取较短的链表40 /这样进行的插入次数要少些41 head = head1;42 p = head2;43 44 else45 46 head = head2;47 p = head1;48 4950 while(p != NULL)51 52 nextP = p->next; /保存 p 的下一个节点53 head = insert_node(head, p); /把 p 插入到目标链表中54 p = nextP; /指向将要插入的下一个节点55 5657 return head;58 这里 insert_node()函数是有序的插入节点，注意与前面例题中的函数有区别，这里它传入的参数是 node*类型。然后在 merge()函数中（代码 5255 行）循环把短链表中的所有节点插入到长链表中。接下来介绍非递归方法。比如有下面两个链表：链表 1：1->3->5链表 2：2->4->6递归方法的步骤如下：（1）比较链表 1 和链表 2 的第一个节点数据，由于 15）和链表 2 再调用本过程，比较得到结果链表的第二个节点，即 2 与 3 比较得到 2。此时合并后的链表节点为 1->2。接下来的过程类似（2） ，如此递归知道两个链表的节点都被加到结果链表中。1 node * MergeRecursive(node *head1, node *head2)2 3 node *head = NULL;45 if (head1 = NULL)6 7 return head2;8 9 if (head2 = NUL)10 11 return head1;12 1314 if ( head1->data data )15 16 head = head1 ;17 head->next = MergeRecursive(head1->next,head2);18 19 else20 21 head = head2 ;22 head->next = MergeRecursive(head1,head2->next);23 2425 return head ;26 下面是测试程序：1 int main()2 3 node *head1 = create(); /创建单链表 14 node *head2 = create(); /创建单链表 25 /node *head = merge(head1, head2);6 node *head = MergeRecursive(head1, head2);7 print(head);89 return 0;10 这里使用 merge()函数和 MergeRecursive()函数测试，结果一致。