C26.【C++ Cont】动态内存管理和面向对象的方式实现链表
🧨🧨🧨🧨🧨🧨🧨🧨🧨除夕篇🧨🧨🧨🧨🧨🧨🧨🧨🧨
目录
1.知识回顾
2.两个操作符
new操作符
示例代码1:申请一个变量
示例代码2:申请连续的内存空间
delete操作符
示例代码3
1.知识回顾
C语言中的动态内存管理知识回顾:
68.【C语言】动态内存管理(重点)(1)
69.【C语言】动态内存管理(重点)(2)
70.【C语言】动态内存管理(重点)(3)
71.【C语言】动态内存管理(重点)(4)
E37.【C语言】动态内存管理练习题
2.两个操作符
和C语言一样,在堆区上自行申请空间和释放空间,注意:new和delete应该配对使用
new操作符
new申请一个变量的空间,new[ ]申请一个数组的空间
new返回的是申请到的内存空间的起始地址,因此需要指针来接收
示例代码1:申请一个变量
格式:new 数据类型 或 new 数据类型(初始值)
//p1指向申请的int类型的空间,但未初始化
int* p1 = new int;
if (p1==nullptr)
{
perror("new");
return 1;
}
//p2指向申请的int类型的空间,已初始化为5
int* p2 = new int(5);
if (p2==nullptr)
{
perror("new");
return 1;
}注:为防止new开辟空间失败,建议判断p1和p2是否为空,或者assert断言
VS2022调试模式下在内存窗口输入&p1
再跳到0x0128a288查看,4字节的cd,显然未初始化
VS2022调试模式下在内存窗口输入&p2
再跳到0x0128a2b8查看,为05 00 00 00,已初始化为5
示例代码2:申请连续的内存空间
申请连续的内存空间即申请数组空间
格式:new 数据类型[元素个数]
int* p3 = new int[10];//申请10个int类型的空间注:new不是只能给内置类型开辟空间,也可以给自定义类型开辟空间,例如结构体
delete操作符
delete负责释放一个变量的空间,delete[ ]释放一个数组的空间
格式:delete 指针 或 delete[] 指针(数组的空间)
示例代码3
int* p1 = new int;
if (p1==nullptr)
{
perror("new");
return 1;
}
int* p2 = new int(5);
if (p2==nullptr)
{
perror("new");
return 1;
}
int* p3 = new int[10];
if (p1==nullptr)
{
perror("new");
return 1;
}
delete p1;
p1 = nullptr;
delete p2;
p2 = nullptr;
delete[] p3;
p3 = nullptr;要养成良好的习惯,delete后防止野指针要手动为指针置空
有关malloc和new,delete和free的区别这里不做讲解,竞赛中只需要知道怎么用就行
注意:在竞赛中数据结构的模拟实现不会采用malloc和free或者 new 和 delete 的方式,代码量大和运行速度慢而是采用静态的足够大的数组来模拟实现
3.面向对象的方式实现链表
1.知识回顾
63.【C语言】再议结构体(上)
86.【C语言】数据结构之链表的总体概述87.【C语言】数据结构之链表的头插和尾插
91.【C语言】数据结构之单向链表的头删和尾删
92.【C语言】数据结构之单向链表的查找,中间插入和删除,销毁
上面的这些文章实际上是面向过程的方式实现链表
2.面向对象的方式实现
竞赛中一般使用数组去模拟链表,这里简单了解就行
面向对象的方式:可以使用结构体去封装链表的各个操作(隐藏对象的内部实现细节,只暴露必要的接口供外部使用),之后借助点操作符去调用成员函数
(有关C++结构体的内容参见C24.【C++ Cont】结构体文章)
实现代码
struct List
{
Node* phead;//指向头节点的指针
Node* ptail;//指向尾节点的指针
List()//构造函数用于初始化指向头节点的指针
{
phead = nullptr;
ptail = nullptr;
}
~List()//析构函数用于销毁链表
{
while (phead)
{
SLTPopFront();
}
phead = nullptr;
ptail = nullptr;
}
Node* BuySLTNode(SLTDataType x)//新建节点
{
Node* newnode = new Node;
if (newnode == nullptr)
{
perror("new");
return nullptr;
}
newnode->val = x;
newnode->next = nullptr;
return newnode;
}
void SLTPushFront(SLTDataType x)//头插节点
{
Node* newnode = BuySLTNode(x);
if (phead == nullptr)
{
phead = ptail= newnode;
}
else
{
newnode->next = phead;
phead = newnode;//不用改动ptail
}
}
void SLTPushBack(SLTDataType x)//尾插节点
{
Node* newnode = BuySLTNode(x);
if (phead == nullptr)
{
ptail = phead = newnode;//如果是第一次插入需要同时更新首尾指针
}
else
{
ptail->next = newnode;
ptail = ptail->next;
}
}
void SLTPopFront()//头删节点
{
if (phead == nullptr)
{
cout << "链表为空,禁止头删" << endl;
return;
}
Node* tmp = phead;
phead = tmp->next;
delete tmp;
tmp = nullptr;
}
void SLTPopBack()//尾删节点
{
if (phead == nullptr)
{
cout << "链表为空,禁止尾删" << endl;
return;
}
Node* tmp = phead;
if (phead->next == nullptr)
{
delete phead;
ptail= phead = nullptr;//删除最后一个节点,注意将首尾指针都置为空
return;
}
while (tmp->next != ptail)//寻找尾节点前面的节点
{
tmp = tmp->next;
}
delete ptail;
ptail = tmp;
ptail->next = nullptr;
tmp = nullptr;
}
void SLTPrint()//打印链表的所有节点
{
Node* cur = phead;
while (cur)
{
cout << cur->val << "-->";
cur = cur->next;
}
cout << "NULL"<<endl;
}
};
如果用类写:
class List
{
private:
Node* phead;
Node* ptail;
public:
List()
{
//......
}
~List()
{
//......
}
Node* BuySLTNode(SLTDataType x)
{
//......
}
void SLTPushFront(SLTDataType x)
{
//......
}
void SLTPushBack(SLTDataType x)
{
//......
}
void SLTPopFront()
{
//......
}
void SLTPopBack()
{
//......
}
void SLTPrint()
{
//......
}
};
封装后的接口说明
只需要向开发者提供接口说明,供开发者调用,例如:
/
//文件名:list.cpp
//作者:zhancod
//版本:v1.0
//完成日期:2025.1.28
//修改记录:......
//
//描述:单链表API
//提醒:1.使用前先创建链表(List list;),之后调用接口函数(list.函数(?))
// 2.链表存储的数据类型定义在typedef int SLTDataType;
// 3.不需要手动new和delete链表
//
//1.函数:SLTPushFront
// 功能:头插节点
// 使用方式:list.SLTPushFront(data)
//
//2.函数:SLTPushBack
// 功能:尾插节点
// 使用方式:list.SLTPushBack(data)
//
//3.函数:SLTPopFront
// 功能:头删节点
// 使用方式:list.SLTPopFront()
//
//4.函数:SLTPopBack
// 功能:尾删节点
// 使用方式:list.SLTPopBack()
//
//5.函数:SLTPrint
// 功能:打印链表的所有节点
// 使用方式:list.SLTPrint()
//
调用接口的代码
int main()
{
{
List list;
list.SLTPushFront(1);
list.SLTPushBack(2);
list.SLTPushFront(3);
list.SLTPushBack(4);
list.SLTPushFront(5);
list.SLTPopFront();
list.SLTPrint();
list.SLTPopBack();
list.SLTPrint();
list.SLTPopBack();
list.SLTPopFront();
list.SLTPopBack();
list.SLTPopFront();
list.SLTPopBack();
list.SLTPrint();
}
return 0;
}执行结果
练习
稍微修改上方的代码可以提交本题:707. 设计链表 - 力扣（LeetCode）
之后会单独出一篇文章讲解
🎉❤️🎉❤️🎉❤️🎉❤️🎉❤️祝各位码农们蛇年大吉 巳巳如意!❤️🎉❤️🎉❤️🎉❤️🎉❤️🎉