前言
介绍
🍃数据结构专区:数据结构
参考
该部分知识参考于《数据结构(C语言版 第2版)》29~36页
补充
后序代码中会遇见这个结构体
typedef struct LNode
{
...
}LNode,*LinkList;
对于这个代码,目的是定义线性表的单链表储存结构。
关键在于LNode与*LinkList
抽象出两个句子:
typedef struct Node LNode;
typedef struct Node* LinkList;LNode,参照typede的用法,可以得知LNode就是struct LNode的别名,即LNode==struct LNode;
LinkList,是一个指向该结构体的的指针的别名。其实这个*应该不是跟着LinkList,而是跟在LNode后面的,即LNode* == LinkList。
可以通过这样一个例子可以这样来理解
typedef struct int ElemType
typedef struct int* ElemTypePtr
第一个是 定义整型变量的别名 ElemType
第二个是 定义指向整型变量的指针的别名 ElemTypePtr
LNode Node;//定义结构体变量Node;
LinkList Ptr;//定义指向结构体的指针变量Ptr;
🌈每一个清晨,都是世界对你说的最温柔的早安:ૢ(≧▽≦)و✨
目录
1、单链表的基本概念
单链表(Singly Linked List)是一种常见的数据结构,用于存储一系列的元素,其中每个元素称为节点(Node)。在单链表中,每个节点包含两部分:一部分存储数据(data),另一部分存储指向下一个节点的指针(pointer 或 next)。以下是单链表的一些基本概念:
- 节点(Node):
- 节点是单链表的基本单元。
- 每个节点包含两个部分:
- 数据域(data):存储实际的数据。
- 指针域(next):存储指向下一个节点的指针(如果当前节点是最后一个节点,则指针为 null 或 NULL)。
- 头节点(Head Node):
- 单链表通常有一个头节点,它指向链表的第一个实际数据节点(如果链表不为空)。
- 头节点本身不存储数据,也可以存储一个哨兵值(dummy value)或者作为链表操作的辅助。
- 尾节点(Tail Node):
- 链表的最后一个节点,其 next 指针为 null 或 NULL。
- 链表长度(Length):
- 链表中节点的数量。
- 通常通过一个额外的变量来维护链表的长度,以加快获取链表长度的操作。
- 操作:
- 插入(Insert):在链表的特定位置插入一个新节点。
- 删除(Delete):删除链表中的某个节点。
- 查找(Search):在链表中查找特定值的节点。
- 遍历(Traversal):从头节点开始,依次访问链表中的每个节点。
- 时间复杂度:
- 插入、删除和查找操作的时间复杂度通常为 O(n),其中 n 是链表的长度。这是因为这些操作在最坏情况下需要遍历链表的一部分或全部节点。
- 遍历链表的时间复杂度为 O(n)。
- 内存管理:
- 单链表使用动态内存分配来创建节点,因此在使用完毕后需要手动释放每个节点的内存,以避免内存泄漏。
单链表相比于数组,其优势在于插入和删除操作的时间复杂度较低(在已知位置的情况下),但劣势在于访问特定位置的节点需要从头节点开始遍历,不如数组那样高效。
2、单链表的基本操作
2.1 宏定义和结构体
#include<iostream>
using namespace std;
//控制最大值
#define MAXSIZE 1000
//声明Status用于记录返回结果
typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode* next;
}LNode, *LinkList;
2.2 初始化 O(1)
//初始化 O(1)
Status InitList(LinkList& L)
{
L = new LNode;
//等价于
//L = (LNode*)malloc(sizeof(LNode));
L->next = NULL;
return OK;
}
2.3 销毁 O(n)
//链表销毁 O(n),n为链表中数据节点的个数
Status DestroyLink(LinkList& L)
{
LNode* pre = L;
LNode* p = L->next; //pre指向节点p的前驱节点
while (p)
{
free(pre); //释放pre节点
pre = p; //pre , p 同步向后移动一位
p = pre->next;
}
//循环结束后,p为NULL,pre指向尾节点,释放它
free(pre);
return OK;
}
2.4 判空 O(1)
//判空 O(1)
Status ListEmpty(LinkList L)
{
return(L->next == NULL);
}
2.5 求表长 O(n)
//求表长 O(n),n为链表中数据节点的个数
int ListLength(LinkList L)
{
int n = 0;
LNode* p = L->next;
while (p)
{
n++;
p = p->next;
}
return n;
}
2.6 取值(按序号查找) O(n)
//取值 O(n),n为链表中数据节点的个数
//按照序号进行查找
Status GetElemLink(LinkList L, int i, ElemType& e)
{
LNode* p = L->next;
int j = 1;
while (p && j < i) //顺链表域向后查找,直到p为空或p指向第i个元素
{
p = p->next;
++j;
}
if (!p || j > i) //i值不合法
{
return ERROR;
}
else
{
e = p->data; //用引用返回得到的参数数据
return OK;
}
}
2.7 按值查找 O(n)
//按照元素进行查找 O(n),n为链表中数据节点的个数
LNode* LocateElem(LinkList L, ElemType e)
{
LNode* p;
p = L->next;
while (p && p->data != e) //顺链表域向后查找,直到p为空或者p所指节点的数据域为e
{
p = p->next;
}
return p; //查找到后返回e元素的结点地址p,查找失败后返回为NULL
}
2.8 指定插入 O(n)
//链表插入 O(n),n为链表中数据节点的个数
//将e节点元素插入到i节点的前面,则需要移动到i-1的位置
Status InsertLink(LinkList& L, int i, ElemType e)
{
LNode* p = L;
int j = 0;
while (p && j < i - 1) //查找到第i-1个节点
{
++j;
p = p->next;
}
if (!p || j > i - 1)
{
return ERROR;
}//该情况出现,即插入位置非法
//循环结束后,已经移动到了i节点的前一个位置,进行尾插即可
LNode* s = new LNode; //为即将要插入位置开辟一个结点
s->data = e;
s->next = p->next;//首先进行尾部连接
p->next = s;//随后进行头部连接
return OK;
}
2.9 删除 O(n)
//链表删除某个结点 O(n),n为链表中数据节点的个数
Status DeleteLink(LinkList& L, int i, ElemType e)
{
LNode* p = L;
int j = 0;
while (p && j < i - 1)
{
p = p->next;
j++;
}//循环结束后,p会指向要删除节点的前驱节点
if (!(p->next) || j > i - 1)
{
return ERROR;
}//要判断位置是否非法
//进行删除
LNode* q;
q = p->next; //临时保存被删除节点的地址以备后续释放
p->next = q->next; //改变被删除节点的前驱节点的指针域
e = q->data; //删除时拿出来被删除节点的数据
delete q;
return OK;
}
2.10 输出链表
//遍历打印链表 O(n),n为链表中数据节点的个数
void TraverseList(LinkList L)
{
if (L == nullptr || L->next == nullptr) {
cout << "链表为空" << endl;
return;
}
LNode* p;
p = L->next;
while (p)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
2.11 头插法 O(n)
//头插法 O(n),n为链表中数据节点的个数
void CreatLink_F(LinkList& L, int n)
{
L = new LNode;
L->next = NULL;
for (int i = 0; i < n; i++)
{
LinkList p = new LNode;
cin >> p->data;
p->next = L->next;
L->next = p;
}
}
2.12 尾插法 O(n)
//尾插法 O(n),n为链表中数据节点的个数
void CreatLink_L(LinkList& L, int n)
{
L = new LNode;
L->next = NULL;
LNode* r = L;
for (int i = 0; i < n; i++)
{
LNode* p = new LNode;
cin >> p->data;
p->next = NULL;
r->next = p;
}
}
2.13 整体代码(含测试)
#include<iostream>
using namespace std;
//控制最大值
#define MAXSIZE 1000
//声明Status用于记录返回结果
typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode* next;
}LNode, *LinkList;
//初始化 O(1)
Status InitList(LinkList& L)
{
L = new LNode;
//等价于
//L = (LNode*)malloc(sizeof(LNode));
L->next = NULL;
return OK;
}
//链表销毁 O(n),n为链表中数据节点的个数
Status DestroyLink(LinkList& L)
{
LNode* pre = L;
LNode* p = L->next; //pre指向节点p的前驱节点
while (p)
{
free(pre); //释放pre节点
pre = p; //pre , p 同步向后移动一位
p = pre->next;
}
//循环结束后,p为NULL,pre指向尾节点,释放它
free(pre);
return OK;
}
//判空 O(1)
Status ListEmpty(LinkList L)
{
return(L->next == NULL);
}
//求表长 O(n),n为链表中数据节点的个数
int ListLength(LinkList L)
{
int n = 0;
LNode* p = L->next;
while (p)
{
n++;
p = p->next;
}
return n;
}
//取值 O(n),n为链表中数据节点的个数
//按照序号进行查找
Status GetElemLink(LinkList L, int i, ElemType& e)
{
LNode* p = L->next;
int j = 1;
while (p && j < i) //顺链表域向后查找,直到p为空或p指向第i个元素
{
p = p->next;
++j;
}
if (!p || j > i) //i值不合法
{
return ERROR;
}
else
{
e = p->data; //用引用返回得到的参数数据
return OK;
}
}
//按照元素进行查找 O(n),n为链表中数据节点的个数
LNode* LocateElem(LinkList L, ElemType e)
{
LinkList p;
p = L->next;
while (p && p->data != e) //顺链表域向后查找,直到p为空或者p所指节点的数据域为e
{
p = p->next;
}
return p; //查找到后返回e元素的结点地址p,查找失败后返回为NULL
}
//链表插入 O(n),n为链表中数据节点的个数
//将e节点元素插入到i节点的前面,则需要移动到i-1的位置
Status InsertLink(LinkList& L, int i, ElemType e)
{
LNode* p = L;
int j = 0;
while (p && j < i - 1) //查找到第i-1个节点
{
++j;
p = p->next;
}
if (!p && j > i - 1)
{
return ERROR;
}//该情况出现,即插入位置非法
//循环结束后,已经移动到了i节点的前一个位置,进行尾插即可
LNode* s = new LNode; //为即将要插入位置开辟一个结点
s->data = e;
s->next = p->next;//首先进行尾部连接
p->next = s;//随后进行头部连接
return OK;
}
//链表删除某个结点 O(n),n为链表中数据节点的个数
Status DeleteLink(LinkList& L, int i, ElemType e)
{
LNode* p = L;
int j = 0;
while (p && j < i - 1)
{
p = p->next;
j++;
}//循环结束后,p会指向要删除节点的前驱节点
if (!(p->next) || j > i - 1)
{
return ERROR;
}//要判断位置是否非法
//进行删除
LNode* q;
q = p->next; //临时保存被删除节点的地址以备后续释放
p->next = q->next; //改变被删除节点的前驱节点的指针域
e = q->data; //删除时拿出来被删除节点的数据
delete q;
return OK;
}
//遍历打印链表 O(n),n为链表中数据节点的个数
void TraverseList(LinkList L)
{
if (L == nullptr || L->next == nullptr) {
cout << "链表为空" << endl;
return;
}
LNode* p;
p = L->next;
while (p)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
//头插法 O(n),n为链表中数据节点的个数
void CreatLink_F(LinkList& L, int n)
{
L = new LNode;
L->next = NULL;
for (int i = 0; i < n; i++)
{
LinkList p = new LNode;
cin >> p->data;
p->next = L->next;
L->next = p;
}
}
//尾插法 O(n),n为链表中数据节点的个数
void CreatLink_L(LinkList& L, int n)
{
L = new LNode;
L->next = NULL;
LNode* r = L;
for (int i = 0; i < n; i++)
{
LNode* p = new LNode;
cin >> p->data;
p->next = NULL;
r->next = p;
}
}
int main() {
LinkList L;
ElemType e;
cout << "开始测试单链表操作函数:" << endl;
// 测试初始化函数
cout << "\n1. 测试初始化函数 InitList" << endl;
if (InitList(L) == OK) {
cout << "链表初始化成功" << endl;
}
else {
cout << "链表初始化失败" << endl;
return 1;
}
// 测试插入函数
cout << "\n2. 测试插入函数 InsertLink" << endl;
for (int i = 1; i <= 5; i++) {
if (InsertLink(L, i, i * 10) == OK) {
cout << "成功在位置 " << i << " 插入元素 " << i * 10 << endl;
}
else {
cout << "在位置 " << i << " 插入元素失败" << endl;
}
}
// 测试遍历打印函数
cout << "\n3. 测试遍历打印函数 TraverseList" << endl;
cout << "当前链表内容:";
TraverseList(L);
// 测试取值函数
cout << "\n4. 测试取值函数 GetElemLink" << endl;
if (GetElemLink(L, 3, e) == OK) {
cout << "第3个元素的值为:" << e << endl;
}
else {
cout << "获取第3个元素失败" << endl;
}
// 测试查找函数
cout << "\n5. 测试查找函数 LocateElem" << endl;
e = 30;
LNode* found = LocateElem(L, e);
if (found) {
cout << "元素 " << e << " 在链表中" << endl;
}
else {
cout << "元素 " << e << " 不在链表中" << endl;
}
// 测试删除函数
cout << "\n6. 测试删除函数 DeleteLink" << endl;
if (DeleteLink(L, 2, e) == OK) {
cout << "成功删除第2个元素,删除的元素值为:" << e << endl;
cout << "删除后的链表内容:";
TraverseList(L);
}
else {
cout << "删除第2个元素失败" << endl;
}
// 测试求长度函数
cout << "\n7. 测试求长度函数 ListLength" << endl;
cout << "当前链表的长度为:" << ListLength(L) << endl;
// 测试判空函数
cout << "\n8. 测试判空函数 ListEmpty" << endl;
if (ListEmpty(L) == OK) {
cout << "链表为空" << endl;
}
else {
cout << "链表不为空" << endl;
}
// 测试头插法创建链表
cout << "\n9. 测试头插法创建链表 CreatLink_F" << endl;
LinkList L1;
cout << "请输入3个元素用于头插法创建链表:";
CreatLink_F(L1, 3);
cout << "头插法创建的链表内容:";
TraverseList(L1);
// 测试尾插法创建链表
cout << "\n10. 测试尾插法创建链表 CreatLink_L" << endl;
LinkList L2;
cout << "请输入3个元素用于尾插法创建链表:";
CreatLink_L(L2, 3);
cout << "尾插法创建的链表内容:";
TraverseList(L2);
// 测试销毁函数
cout << "\n11. 测试销毁函数 DestroyLink" << endl;
if (DestroyLink(L) == OK && DestroyLink(L1) == OK && DestroyLink(L2) == OK) {
cout << "链表销毁成功" << endl;
}
else {
cout << "链表销毁失败" << endl;
}
cout << "\n所有测试完成" << endl;
return 0;
}
结语
该部分内容需要大家实操才可以有所收获,同时这部分又是后续学习中的基础,希望大家可以认真对待!