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

"这篇资料包含了C++中常见的笔试题，主要涉及数据结构，特别是链表操作，如链表反转。同时给出了String类的定义，并要求实现相关成员函数。" 在C++编程中，数据结构是面试和笔试中的热门话题，其中链表作为基础的数据结构之一，其反转操作常常被用来考察程序员对指针操作的理解和问题解决能力。题目提供了两种链表反转的方法： 1. 非递归法： 这种方法通过迭代完成，首先定义三个指针，pre、cur和ne，分别代表当前节点的前一个节点、当前节点和当前节点的下一个节点。遍历链表，每次迭代时，将当前节点的next指针指向前一个节点（即pre），然后移动pre和cur到下一个位置。最后更新head为新的链表头。这种方法不涉及额外的栈空间，但需要更多的代码来处理边界条件。 ```cpp struct linka { int data; linka* next; }; void reverse(linka*& head) { if (head == NULL) return; linka* pre, * cur, * ne; pre = head; cur = head->next; while (cur) { ne = cur->next; cur->next = pre; pre = cur; cur = ne; } head->next = NULL; head = pre; } ``` 2. 递归法： 递归法通过反转链表的剩余部分，然后将当前节点插入到反转后的链表的末尾。这种方法更简洁，但需要额外的系统栈空间，且反转后需要手动断开循环。递归函数接收两个参数，一个是当前节点，另一个是当前链表的头。 ```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. 通用构造函数：创建一个空字符串或拷贝传入的字符串。 2. 拷贝构造函数：创建String对象的副本。 3. 析构函数：释放动态分配的内存。 4. 赋值运算符：实现深拷贝，将右侧对象的值赋给左侧对象。 对于String类的实现，一般如下： ```cpp class String { public: String(const char* str = NULL) { if (str == NULL) { // strlen在参数为NULL时会抛异常才会有这步判断 m_data = new char[1]; m_data[0] = '\0'; } else { size_t len = strlen(str); m_data = new char[len + 1]; strcpy(m_data, str); } } String(const String& another) { size_t len = strlen(another.m_data); m_data = new char[len + 1]; strcpy(m_data, another.m_data); } ~String() { delete[] m_data; } String& operator=(const String& rhs) { if (this != &rhs) { size_t len = strlen(rhs.m_data); delete[] m_data; m_data = new char[len + 1]; strcpy(m_data, rhs.m_data); } return *this; } private: char* m_data; // 用于保存字符串 }; ``` 这些基础知识对于C++程序员来说非常重要，不仅能够考察他们对基本数据结构的操作，还能评估他们在内存管理和对象拷贝方面的理解。