文章目录
- 一、单链表的定义及其结构
- 1.1.概念
- 1.2.单链表的结构
- 1.3.单链表的特点
- 二、单链表的实现
- 2.1.定义结点
- 2.2.创建单链表
- 2.3.打印单链表
- 2.4. 单链表尾插与尾删
- 2.4. 单链表头插与头删
- 2.4.查找某个结点
- 2.5.插入
- 2.6.删除\
- 总代码
一、单链表的定义及其结构
1.1.概念
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，但链表在逻辑上是连续的，顺序的，而数据元素的逻辑顺序是通过链表中的指针连接次序实现的。
1.2.单链表的结构
单链表（Singly Linked List）是一种常用的数据结构，它由若干个节点组成，每个节点包含两部分：数据域和指针域。数据域用于存储数据，而指针域则用于指向下一个节点的地址。单链表中每个节点只有一个指针域，指向下一个节点，最后一个节点的指针域指向 NULL，表示链表的结尾。
一看到这种结构有就会问，顺序表的存储方式和单链表哪里不同呢？
顺序表是一种基于数组实现的线性数据结构，其元素在内存中是连续存储的，其实就是数组的原理。而单链表是一种逻辑连续，物理不一定连续的线性表，实际上在内存中，每个结点可能会隔得很远，只是通过指针的方式将他们像绳子一样穿起来，也是每个结点都指向下一个结点地址空间。
1.3.单链表的特点
与顺序表不同，单链表的元素不是连续存储的，而是通过指针相连形成链式结构。因此，单链表具有以下优缺点。
优点：
- 支持动态内存分配。由于单链表不需要预先分配一段连续的空间，因此可以根据实际需求动态地申请、释放节点空间，避免浪费内存。
- 支持高效的插入、删除操作。由于单链表中的节点是通过指针相连的，因此在插入、删除一个节点时，只需要修改其前驱节点或后继节点的指针即可，时间复杂度为 O ( 1 ) O(1) O(1)。
缺点：
- 不支持随机访问。由于单链表中的节点不是连续存储的，因此不能像数组一样通过下标来直接访问一个元素，需要从头节点开始遍历整个链表才能访问任意位置的元素。
二、单链表的实现
2.1.定义结点
typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;//数据域struct SListNode* next;//指针域
}SLTNode;2.2.创建单链表
为一个新结点创建空间以及输入值
SLTNode* BuySLTNode(SLTDataType x) {SLTNode* newnode = new SLTNode;//申请空间，等同于malloc函数if (!newnode) {perror("fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}
根据上述函数，我们可以构造一个多个结点的单链表生成函数。
SLTNode* CreateSList(int n) {SLTNode* phead, * p; // 头节点phead = p = NULL; // 指向当前节点的指针for (int i = 0; i < n; i++) {SLTDataType x;cin >> x;SLTNode* newnode = BuySLTNode(x);// 创建新节点if (!phead)phead = p = newnode;// 插入到链表中else {p->next = newnode;p = p->next;}}return phead;
}
2.3.打印单链表
遍历链表，当链表中没有元素时，头指针所指向的就是NULL，也是停止循环的条件
void SLTPrint(SLTNode* phead)
{SLTNode* p=phead;//当前指针不为空就继续走while(!p){printf("%d->",p->data);p=p->next;}printf("NULL\n");}
2.4. 单链表尾插与尾删
尾插：
通过遍历链表找到尾节点，并将新节点链接到尾节点之后，实现了新元素的添加。
void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);//判断是否为空SLTNode* newnode = BuySLTNode(x);//创建一个新的结点//如果头为空的话就将新结点赋值给头结点if (*pphead == NULL) {*pphead = newnode;}//else{SLTNode* p = *pphead;//遍历到尾结点while (p->next) {p = p->next;}//尾结点指向新结点p->next = newnode;}
}
尾删：
在链表为空或只有一个节点时，直接释放相应内存空间即可；否则通过遍历找到尾节点，并释放其空间，然后将前一个节点的 next 指针指向 NULL
void SLTPopBack(SLTNode** pphead) {//链表为空就直接退出if (*pphead == NULL) {return;}//链表只有头结点的话,pphead->next=null等同于只有头结点if ((*pphead)->next == NULL) {//删除free(*pphead);*pphead = NULL;}else{SLTNode* p = *pphead;//找到尾结点的前一个结点while (p->next->next) {p = p->next;}//删除free(p->next);p->next = NULL;}
}
2.4. 单链表头插与头删
头插：
void SLTPushFront(SLTNode** pphead, SLTDataType x) {SLTNode* newnode = BuySLTNode(x);newnode->next = *pphead;//新结点后面连接旧的头结点*pphead = newnode;//头结点更新为新节点
}
头删：
void SLTPopFront(SLTNode** pphead) {assert(pphead);//if (*pphead == NULL)return;SLTNode* p = (*pphead)->next;//头结点的下一个结点free(*pphead);*pphead = p;//头结点更新为p}
2.4.查找某个结点
查找其实就和遍历单链表差不多，不过需要加一个数值是否相等的if判断语句
SLTNode* SListFind(SLTNode* plist, SLTDataType x) {SLTNode* p = plist;while (p) {if (p->data == x)return p;p = p->next;}return NULL;
}2.5.插入
该函数通过指针操作在单链表的指定位置插入一个值为x的新结点，同时也考虑了插入位置是头结点的情况。需要注意的是，此函数没有考虑插入位置为空的情况，即需要确保 pos 非空指针。同时，该函数只能在某个结点之前插入新的结点，如果需要在链表尾部插入，则需要先找到链表尾结点，并将其 next 指针指向新结点。
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pos);//一个值为x的新结点SLTNode* newnode = BuySLTNode(x);//头结点需要特殊处理if (*pphead == pos) {newnode->next = *pphead;*pphead = newnode;}else {SLTNode* p = *pphead;//p为前一个结点//遍历停止在pos结点之前while (p->next != pos) {p = p->next;}p->next = newnode;newnode->next = pos;}
}
2.6.删除\
若要删除的结点是头结点，则通过记录头指针的下一个结点来更新头结点，并释放原结点空间。
否则，需要寻找删除结点的前一个结点 pre，从而可以断开 pos 与 pre->next 之间的连接，同时释放 pos 的空间。因此，通过 while 循环遍历单链表找到前一个结点 pre。找到之后将 pre->next 指向待删除结点的下一个结点，并释放待删除结点空间。
void SListErase(SLTNode** pphead, SLTNode* pos) {assert(pos);assert(*pphead);//头结点需要特殊处理if (*pphead == pos){SLTNode* p = (*pphead)->next;//记录头结点下一个结点free(*pphead);//更新头结点*pphead = p;}else {SLTNode* pre = *pphead;//pre为前一个结点while (pre->next!=pos) {pre = pre->next;}pre->next = pos->next;free(pos);}
}
总代码
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include<bits/stdc++.h>
using namespace std;
//struct SListNode
//{
// SLTDataType data;
// struct SListNode* next;
//};
//typedef struct SListNode SLTNode;//void SLTPushBack(SLTDataType x)
//{
// SLTNode node;
//}typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;SLTNode* BuySLTNode(SLTDataType x);
SLTNode* CreateSList(int n);
void SLTPrint(SLTNode* phead);void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopFront(SLTNode** pphead);SLTNode* SListFind(SLTNode* plist, SLTDataType x);// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SLTNode* pos, SLTDataType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SLTNode* pos);// 在pos之前插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 删除pos位置
void SListErase(SLTNode** pphead, SLTNode* pos, SLTDataType x);SLTNode* BuySLTNode(SLTDataType x) {SLTNode* newnode = new SLTNode;if (!newnode) {perror("fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;}
SLTNode* CreateSList(int n) {SLTNode* phead, * p;phead = p = NULL;for (int i = 0; i < n; i++) {SLTDataType x;cin >> x;SLTNode* newnode = BuySLTNode(x);if (!phead)phead = p = newnode;else {p->next = newnode;p = p->next;}}return phead;}void SLTPrint(SLTNode* phead)
{SLTNode* p = phead;while (p) {cout << p->data << ">";p = p->next;}cout << "NULL" << endl;
}//
//void SLTPushBack(SLTNode** pphead, SLTDataType x) {
// assert(pphead);
// SLTNode* newnode = BuySLTNode(x);
// if (*pphead == NULL) {
// *pphead = newnode;
// }
// else {
// SLTNode* p = *pphead;
// while (p->next) {
// p = p->next;
// }
//
// p->next = newnode;
// }
//}
//
//
//void SLTPopBack(SLTNode** pphead) {
//
// //链表为空就直接退出
// if (*pphead == NULL) {
// return;
// }
//
// //
// if ((*pphead)->next == NULL) {
// free(*pphead);
// *pphead = NULL;
// }
// else
// {
// SLTNode* p = *pphead;
// while (p->next->next) {
// p = p->next;
// }
// free(p->next);
// p->next = NULL;
// }
//}
//
//
//
//void SLTPushFront(SLTNode** pphead, SLTDataType x) {
// SLTNode* newnode = BuySLTNode(x);
// newnode->next = *pphead;
// *pphead = newnode;
//}
//
//
//void SLTPopFront(SLTNode** pphead) {
// assert(pphead);
//
// if (*pphead == NULL)return;
//
// SLTNode* p = (*pphead)->next;
// free(*pphead);
// *pphead = p;
//
//}SLTNode* SListFind(SLTNode* plist, SLTDataType x) {SLTNode* p = plist;while (p) {if (p->data == x)return p;p = p->next;}return NULL;
}
//
//void SListInsertAfter(SLTNode* pos, SLTDataType x) {
// assert(pos);
//
//
// SLTNode* p = pos->next;
// SLTNode* newnode = BuySLTNode(x);
// pos->next = newnode;
// newnode->next = p;
//
// /*
// SLTNode* newnode = BuySLTNode(x);
// newnode->next=pos->next;
// pos->next=newnode;
// */
//}void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = BuySLTNode(x);if (*pphead == pos) {newnode->next = *pphead;*pphead = newnode;}else {SLTNode* p = *pphead;while (p->next != pos) {p = p->next;}p->next = newnode;newnode->next = pos;}
}//void SListEraseAfter(SLTNode* pos)
//{
// assert(pos);
// if (pos->next)return;
// else {
// SLTNode* q = pos->next;
// pos->next = q->next;
// free(q);
//
// }
//
//}void SListErase(SLTNode** pphead, SLTNode* pos) {assert(pos);assert(*pphead);if (*pphead == pos){SLTNode* p = (*pphead)->next;free(*pphead);*pphead = p;}else {SLTNode* pre = *pphead;while (pre->next!=pos) {pre = pre->next;}pre->next = pos->next;free(pos);}
}void SLTDestroy(SLTNode** pphead) {SLTNode* p = *pphead;while (p) {SLTNode* next = p->next;free(p);p = next;}*pphead = NULL;
}
![单链表的使用方法.数据结构(三)[上]](https://img-blog.csdnimg.cn/e1a54182c2934052ba201d0d103ec7d5.jpeg)
