C++面试题精华:链表反转与String类实现
需积分: 12 74 浏览量
更新于2024-07-26
收藏 210KB PDF 举报
在C++的编程面试中,链表反转和字符串类操作是常见的考察点。本文将分别讨论这两个主题。
1. 链表反转
单向链表的反转是面试中常被提问的基础问题。面试者可能会让你实现一个函数来翻转链表,例如将1->2->3->4->5变成5->4->3->2->1。最直观的方法是使用迭代法,如提供的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;
}
```
这段代码首先检查链表是否为空,然后通过三个指针(pre、cur和ne)交替更新节点的指针,使得当前节点的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;
}
}
```
在这个递归版本中,每次递归都处理掉一个节点,直到遍历完整个链表。
2. String类的实现
面试者可能还会要求你实现一个简单的`String`类,包括通用构造函数、拷贝构造函数、析构函数和赋值函数。以下是一个基本的实现:
```cpp
class String {
public:
// 通用构造函数
String(const char* str = NULL) : m_data(new char[strlen(str) + 1]) {
if (str)
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; // 用于保存字符串
};
```
这里定义了一个`String`类,包含了构造函数(包括默认构造函数和拷贝构造函数),析构函数负责在对象不再使用时释放动态分配的内存,并提供了一个赋值运算符重载,用于安全地更新字符串内容。
以上就是C++面试中常见的链表反转和简单`String`类实现的知识点,理解和掌握这些基础概念有助于你在实际编程中更自如地应对相关问题。
点击了解资源详情
点击了解资源详情
点击了解资源详情
2011-06-09 上传
2013-08-09 上传
124 浏览量
2010-06-28 上传
2010-10-27 上传