C++面试题精华:链表反转与String类实现
需积分: 12 116 浏览量
更新于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`类实现的知识点,理解和掌握这些基础概念有助于你在实际编程中更自如地应对相关问题。
2010-06-28 上传
124 浏览量
2023-10-10 上传
2023-07-09 上传
2023-12-11 上传
2023-08-02 上传
2023-10-14 上传
2023-04-05 上传
2023-05-10 上传
_上下求索_
- 粉丝: 12
- 资源: 10
最新资源
- 新型智能电加热器:触摸感应与自动温控技术
- 社区物流信息管理系统的毕业设计实现
- VB门诊管理系统设计与实现(附论文与源代码)
- 剪叉式高空作业平台稳定性研究与创新设计
- DAMA CDGA考试必备:真题模拟及章节重点解析
- TaskExplorer:全新升级的系统监控与任务管理工具
- 新型碎纸机进纸间隙调整技术解析
- 有腿移动机器人动作教学与技术存储介质的研究
- 基于遗传算法优化的RBF神经网络分析工具
- Visual Basic入门教程完整版PDF下载
- 海洋岸滩保洁与垃圾清运服务招标文件公示
- 触摸屏测量仪器与粘度测定方法
- PSO多目标优化问题求解代码详解
- 有机硅组合物及差异剥离纸或膜技术分析
- Win10快速关机技巧:去除关机阻止功能
- 创新打印机设计:速释打印头与压纸辊安装拆卸便捷性