C++面试题精华:链表反转与String类实现
下载需积分: 12 | PDF格式 | 210KB |
更新于2024-07-26
| 146 浏览量 | 举报
在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`类实现的知识点,理解和掌握这些基础概念有助于你在实际编程中更自如地应对相关问题。
相关推荐









_上下求索_
- 粉丝: 12
最新资源
- 山东大学单片机实验教程之LCD 1602显示实验详解
- Dockerized Debian/Ubuntu deb包构建器:一站式解决方案
- 数字五笔:电脑上的手机笔划输入法
- 轻松实现自定义标签输入,Bootstrap-tagsinput组件教程
- Android页面跳转与数据传递的入门示例
- 又拍图片下载器:批量下载相册图片的利器
- 探索《Learning Python》第五版英文原版精髓
- Spring Cloud应用演示:掌握云计算开发
- 如何撰写奖学金申请书的完整指南
- 全面学成管理系统源码:涵盖多技术领域
- LiipContainerWrapperBundle废弃指南:细粒度控制DI注入
- CHM电子书反编译工具:一键还原内容
- 理解PopupWindows回调接口的实现案例
- Osprey网络可视化系统:开源软件平台介绍
- React组件:在谷歌地图上渲染自定义UI
- LiipUrlAutoConverterBundle不再维护:自动转换URL和邮件链接