富士通C++面试：链表反转与String类实现

"本文主要介绍了两道常见的C++面试题，分别是链表反转和String类的成员函数实现，这些问题在富士通等公司的面试中可能会出现。" 在C++编程中，链表反转是一个基础但重要的问题，尤其在面试中常常被用来考察候选人的逻辑思维和对数据结构的理解。对于单向链表的反转，有两种常见的解决方案： 1. 迭代法：此方法使用两个指针，`pre` 和 `cur`。`pre` 指针用于记录当前节点的前一个节点，`cur` 指针则用于遍历链表。在遍历过程中，每次将 `cur` 指针指向的节点的 `next` 指针反转为 `pre`，然后更新 `pre` 和 `cur` 的值。当 `cur` 指针为空时，反转完成。以下是对应的C++代码实现： ```cpp struct linka { int data; linka* next; }; void reverse(linka*& head) { if (head == NULL) return; linka* pre = head; linka* cur = head->next; while (cur) { linka* ne = cur->next; cur->next = pre; pre = cur; cur = ne; } head->next = NULL; // 反转完成后，链表头的next应设为NULL head = pre; // 更新头结点 } ``` 2. 递归法：这种方法利用递归的思想，先反转链表的剩余部分，然后将当前节点设置为其前一个节点，从而完成反转。递归法需要注意处理基本情况（空链表或只有一个元素的链表），以及处理反转后形成的循环。以下是对应的C++代码实现： ```cpp linka* reverse(linka* p, linka*& head) { if (p == NULL || p->next == NULL) { head = p; return p; } else { linka* tmp = reverse(p->next, head); tmp->next = p; return p; } } ``` 接下来是第二个面试题目，涉及`String`类的成员函数实现。这个类是基本的字符串类，包含了常见的构造函数、拷贝构造函数、析构函数以及赋值操作符重载。以下是对这些成员函数的可能实现： ```cpp class String { public: String(const char* str = NULL) { if (str == NULL) // strlen在参数为NULL时会出错，因此需进行判断 m_data = new char[1]; // 创建一个空字符串 else m_data = new char[strlen(str) + 1]; strcpy(m_data, str); } String(const String& another) { // 拷贝构造函数 m_data = new char[strlen(another.m_data) + 1]; strcpy(m_data, another.m_data); } ~String() { // 析构函数 delete[] m_data; } String& operator=(const String& rhs) { // 赋值函数 if (this != &rhs) { // 避免自我赋值 delete[] m_data; m_data = new char[strlen(rhs.m_data) + 1]; strcpy(m_data, rhs.m_data); } return *this; } private: char* m_data; // 用于保存字符串 }; ``` 在这个实现中，我们确保了内存管理的正确性，避免了悬空指针和内存泄漏。构造函数和拷贝构造函数都根据传入的字符串动态分配内存，并复制字符串内容。析构函数负责释放分配的内存。赋值操作符重载遵循了深拷贝的原则，确保了对象间的独立性。同时，为了防止自我赋值导致的问题，我们在赋值函数内部进行了检查。