C++笔试必备：链表反转与String类实现解析

"这篇资料是关于C++笔试题目的汇总，包含了链表反转等常见问题。对于准备C++笔试或面试的人员具有参考价值。" 在C++编程中，链表反转是一个经典的问题，通常出现在面试和笔试中。这里提到了两种解决方法。 1. 非递归方法： 这个方法通过遍历链表，使用三个辅助指针pre、cur和ne来实现链表反转。首先，初始化pre为头节点，cur为头节点的下一个节点。在循环中，ne会存储cur的下一个节点，然后cur的next指针指向前一个节点pre，接着pre和cur都向前移动一位，直到遍历完链表。最后，将head指针更新为反转后的头节点，并确保其next指针为空。以下是非递归方法的源代码： ```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; head = pre; } ``` 2. 递归方法： 递归方法的基本思路是先反转链表的剩余部分，然后再处理当前节点。在递归调用中，将反转后的链表头部连接到当前节点的前面。然而，这种方法会使得反转后的最后一个节点的next指针仍然指向原链表的头节点，形成一个环。因此，需要在返回时将这个节点的next指针设为NULL。递归方法的源代码如下： ```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) { m_data = new char[strlen(str) + 1]; strcpy(m_data, str); } else { m_data = NULL; } } String(const String& another) { if (another.m_data) { m_data = new char[strlen(another.m_data) + 1]; strcpy(m_data, another.m_data); } else { m_data = NULL; } } ~String() { delete[] m_data; } String& operator=(const String& rhs) { if (this != &rhs) { delete[] m_data; if (rhs.m_data) { m_data = new char[strlen(rhs.m_data) + 1]; strcpy(m_data, rhs.m_data); } else { m_data = NULL; } } return *this; } private: char* m_data; // 用于保存字符串 }; ``` 以上是针对链表反转的两种方法和`String`类的成员函数实现的基本思路。理解并掌握这些内容对于理解和解答C++笔试题目至关重要。