C++链表反转与String类实现解析

"常见笔试题，包括C++链表反转的两种解法和String类的定义及成员函数实现。" 在计算机科学特别是编程面试中，常见的笔试题常常涉及到基础数据结构的操作，例如链表的反转。这里我们关注的是单向链表的反转问题，它是一个经典的算法题目，能够考察应聘者的逻辑思维和对指针操作的理解。 首先，我们可以采用迭代的方式来解决链表反转。这种方法通常使用三个指针：`pre`、`cur`和`ne`。`pre`指向当前节点的前一个节点，`cur`指向当前节点，`ne`则存储`cur`的下一个节点。初始化时，`pre`为`head`，`cur`为`head->next`。在循环中，每次将`cur`指向的节点的`next`指针指向`pre`，然后移动`pre`和`cur`指针。最后，需要将`head`指针更新为新的链表头，即`pre`。以下是对应的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; head = pre; } ``` 另一种方法是使用递归。递归反转的思路是从尾到头依次反转，直到只剩下一个或零个节点。递归函数接收两个参数，一个是当前处理的节点`p`，另一个是当前链表的头节点`head`。递归终止条件是`p`为空或者`p->next`为空，此时`head`更新为`p`并返回。否则，递归反转`p->next`，然后将其`next`指针指向`p`。由于递归过程中`head`会变成反转后的链表头，需要在返回后将最后一个节点的`next`设为`NULL`。以下是递归反转的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`类定义，包含了通用构造函数、拷贝构造函数、析构函数以及赋值运算符重载。为了实现这些成员函数，我们需要考虑如何正确地处理字符串内存的分配与释放，以及防止深浅拷贝等问题。 1. **通用构造函数**：默认构造函数可以接受一个`const char*`参数，表示空字符串或一个C风格字符串。如果传入了字符串，我们需要动态分配内存来保存字符串，并确保在对象生命周期结束时释放。 2. **拷贝构造函数**：拷贝构造函数需要创建一个新的`String`对象，其内部的`m_data`应指向与源对象相同的字符串副本。这里需要注意深拷贝，避免共享内存。 3. **析构函数**：析构函数负责释放`m_data`所指向的内存，确保不会造成内存泄漏。 4. **赋值函数**：赋值运算符重载（`operator=`）同样需要进行深拷贝，确保赋值后原对象和新对象的`m_data`分别指向不同的内存区域。 ```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 = new char[1]; m_data[0] = '\0'; } } 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; // 用于保存字符串 }; ``` 以上就是关于链表反转的两种方法以及`String`类的实现，这些基础知识对于准备IT行业面试的求职者来说至关重要，它们能帮助你更好地理解和解决问题，提升技术能力。