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）

之后会单独出一篇文章讲解

🎉❤️🎉❤️🎉❤️🎉❤️🎉❤️祝各位码农们蛇年大吉 巳巳如意!❤️🎉❤️🎉❤️🎉❤️🎉❤️🎉