数据结构]单链表
单链表
文章目录
- 单链表
- 定义
- 单链表的优缺点
- 用代码定义单链表
- 初始化单链表
- 不带头结点的单链表
- 带头结点的单链表
- 单链表的插入
- 按位序插入(带头结点)
- 指定结点的后插操作
- 指定结点的前插操作
- 单链表的删除
- 按位序删除(带头节点)
- 删除指定结点
- 单链表的查找
- 按位查找
- 按值查找
- 求单链表的长度
- 单链表的建立
- 尾插法
- 头插法
定义
单链表:用链式存储的方式实现线性表
链式存储:用一组任意的存储单元存储线性表的数据元素,不要求逻辑上相邻的元素在物理位置上也相邻
单链表的优缺点
- 优点:不要求大片连续的空间,该容量方便
- 缺点:不可随机存取,要耗费一定的空间存放指针(每个结点除了存放数据元素外,还要存储指向下一个结点的指针)
用代码定义单链表
struct LNode{ //定义单链表结点类型
ElemType data; //每个结点存放一个数据元素
struct LNode *next; //指针指向下一个结点
};
typedef struct LNode LNode;
typedef struct LNode *LinkList;
用typedef
对上面的代码进行简化
typedef <数据类型> <别名>
typedef struct LNode { // 定义单链表结点类型
ElemType data; // 每个结点存放一个数据元素
struct LNode *next; // 指针指向下一个结点
} LNode, *LinkList;
要表示一个单链表时,只需声明一个头指针 L ,指向单链表的第一个结点
LNode * L; //声明一个指向单链表第一个结点的指针,强调这是一个结点
LinkList L; //声明一个指向单链表第一个结点的指针,强调这是一个单链表
初始化单链表
InitList(&L):初始化表,构造一个空的线性表L,分配内存空间
不带头结点的单链表
typedef struct LNode { // 定义单链表结点类型
ElemType data; // 每个结点存放一个数据元素
struct LNode *next; // 指针指向下一个结点
} LNode, *LinkList;
bool InitList(LinkList &L) {
L = NULL; //空表,暂时还没有任何结点,防止出现脏数据
return true;
}
void test(){
LinkList L; // 声明一个指向单链表的指针,这里的L是结构体指针
// 注意此处并没有创建一个结点
InitList(L); //初始化一个空表
//......后续代码....
}
带头结点的单链表
typedef struct LNode { // 定义单链表结点类型
ElemType data; // 每个结点存放一个数据元素
struct LNode *next; // 指针指向下一个结点
} LNode, *LinkList;
// 初始化一个单链表(带头结点)
bool InitList(LinkList &L){
L = (LNode*) malloc(sizeof(LNode)); //分配头结点
if (L == NULL) { //内存不足,分配失败
return false;
}
L->next = NULL; //头结点后暂时没有存放数据
return true;
}
void test(){
LinkList L; //声明一个指向单链表的指针,这里的L是结构体指针
//注意此处并没有创建一个结点
InitList(L); // 初始化一个空表
//......后续代码....
}
不带头结点,写代码更麻烦,需要对第一个数据结点和后续数据结点的处理,需要用不同的代码逻辑,对空表和非空表的处理需要用不同的代码逻辑
带头结点,一套代码完成,实现更方便
单链表的插入
ListInsert(&L,i,e):插入操作,在表L中的第 i 个位置上插入指定元素 e
按位序插入(带头结点)
思路
- 在表 L 中的第 i 个位置上插入指定元素 e,那么首先要找到第 i-1 个结点,将新节点插入其后,如果是插入到第 1 个位置,那么头节点可以视为第 0 个结点
- 新结点后继为所寻结点的后继,新结点成为所寻结点的后继
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
bool ListInsert(LinkList &L, int i, ElemType e)
{
if (i < 1) {
return false;
}
LNode *p; // 结构体指针p, 指向当前扫描到的结点
int j = 0; // 当前p指向的是第j个结点
p = L; // L 指向头结点,头结点是第0个结点(不存数据)
// 循环找到第 i - 1 个结点
// 非空表示不能到链表尽头了,j < i - 1,表示要找到第 i - 1 个节点就停下来了
while (p != NULL && j < i - 1) {
p = p->next;
j++;
}
// 到这里 p 指向了第 i - 1 个节点
// 校验发现第 i - 1个节点是空的,这就表示原链表只有 i - 2 个节点,第 i - 2 个节点的后继是空指针。
if (p == NULL) {
return false;
}
LNode *s = (LNode *)malloc(sizeof(LNode));
// malloc 返回值必须校验
if (s == NULL) {
return false;
}
s->data = e;
s->next = p->next;
p->next = s; // 将结点s连到p之后
//注意上面两句代码的执行顺序不能颠倒
return true; // 插入成功
}
时间复杂度分析
- 最好情况:新元素插入到表头;最好时间复杂度 = O ( 1 ) O(1) O(1)
- 最坏情况:新元素插入到表尾;最坏时间复杂度 = O ( n ) O(n) O(n)
- 平均情况:新元素插入到任何一个位置的概率相同; 平均时间复杂度 = O ( n ) O(n) O(n)
指定结点的后插操作
// 在 p 结点后插入元素 e
bool InsertNextNode(LNode* p, ElemType e)
{
if (p == NULL) {
return false;
}
LNode *s = (LNode*)malloc(sizeof(LNode));
// 判定内存是否申请成功
if (s == NULL) {
return false;
}
// 链表插入数据分三步,填数,建后继链,断前驱链
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
时间复杂度: O ( 1 ) O(1) O(1)
指定结点的前插操作
方法1:常规算法
bool InsertPriorNode(Linklist L, LNode *p, ElemType e)
{
if (p == NULL) {
return false;
}
LNode * pre = L; // 前驱结点
// 遍历循环查找
while (pre != NULL) {
if (pre->next == p) {
break;
}
pre = pre->next;
}
// 如果找不到,那就是空值
if (pre == NULL) {
return false;
}
// 直接调用指定结点后插元素,在p的前一个结点插入,即是在p的前驱结点的后一个插入
return InsertNextNode(pre, e);
}
时间复杂度: O ( n ) O(n) O(n)
方法2:交换节点算法
思路:直接对指定节点进行后插操作,交换新节点与指定节点的数据域
bool InsertPriorNode(LNode *p, ElemType e)
{
if (p == NULL) {
return false;
}
LNode *s = (LNode*)malloc(sizeof(LNode));
// 判定内存是否申请成功
if (s == NULL) {
return false;
}
// 解链,重新成链
s->next = p->next;
p->next = s;
// 数据交换swap
s->data = p->data;
p->data = e;
return true;
}
时间复杂度: O ( 1 ) O(1) O(1)
单链表的删除
ListDelete(&L,i,&e):删除操作,删除表L中第 i 个位置的元素,并用 e 返回删除元素的值
按位序删除(带头节点)
思路:头结点可以看作“第0个”结点,遍历找到第 i-1 个结点,将其指针指向第 i+1 个结点,并释放第 i 个结点
bool ListDelete(Linklist &L, int i, ElemType &e)
{
if (i < 1) {
return false;
}
LNode *p; // 结构体指针p, 指向当前扫描到的结点
int j = 0; // 当前 p 指向的是第 j 个结点
p = L; // L 指向头结点,头结点是第0个结点(不存数据)
// 循环找到第 i-1 个结点
while (p != NULL && j < i - 1) {
p = p->next;
j++;
}
if (p == NULL) {
return false; // i值不合法
}
// 第i-1个结点后没有其他结点,不存在第i个结点
if (p -> next == NULL) {
return false;
}
// 到这里的代码都和指定位序插入结点相同
LNode *q = p->next; // 令q指向被删除结点,即临时变量
e = q->data; // 用e把返回值带回来
p->next = q->next; // 将*q结点从链中断开
free(q); // 释放结点的存储空间
return true; // 删除成功
}
时间复杂度: O ( n ) O(n) O(n)
删除指定结点
类似指定结点的插入操作的方法
单链表的查找
按位查找
GetElem(L,i):按位查找操作,获取表L中第 i 个位置的元素的值
//按位查找,返回第 i 个元素(带头结点)
LNode * GetElem(LinkList L, int i){
if(i < 0){
return NULL;
}
LNode *p; // 结构体指针p, 指向当前扫描到的结点
int j = 0; // 当前 p 指向的是第 j 个结点
p = L; // L 指向头结点,头结点是第0个结点(不存数据)
while(p != NULL && j < i){
p = p->next;
j++;
}
return p;
}
平均时间复杂度: O ( n ) O(n) O(n)
按值查找
LocateElem(L,e):按值查找操作,在表L中查找具有给定关键字值的元素
LNode * LocateElem(LinkList L,ElemType e){
LNode *p = L->next; //从第 1 个结点开始查找数据域为 e 的结点
while(p != NULL && p->data != e){
p = p->next;
}
return p;
}
平均时间复杂度: O ( n ) O(n) O(n)
求单链表的长度
Length(L):求表长,返回线性表L的长度,即L中数据元素的个数
int Length(LinkList L){
int len = 0; //统计表长
LNode *p = L;
while(p->next != NULL){
p = p->next;
len++;
}
return len;
}
平均时间复杂度: O ( n ) O(n) O(n)
单链表的建立
基于带头结点的单链表讨论
-
Step 1:初始化一个单链表
typedef struct LNode { // 定义单链表结点类型 ElemType data; // 每个结点存放一个数据元素 struct LNode *next; // 指针指向下一个结点 } LNode, *LinkList; // 初始化一个单链表(带头结点) bool InitList(LinkList &L){ L = (LNode*) malloc(sizeof(LNode)); //分配头结点 if (L == NULL) { //内存不足,分配失败 return false; } L->next = NULL; //头结点后暂时没有存放数据 return true; } void test(){ LinkList L; //声明一个指向单链表的指针,这里的L是结构体指针 //注意此处并没有创建一个结点 InitList(L); // 初始化一个空表 //......后续代码.... }
-
Step 2:每次取一个数据元素,插入到表尾/表头
尾插法
思路
初始化单链表
设置变量 length 记录链表长度
while 循环 {
每次取一个元素 e;
ListInsert(L, length + 1, e) 插到尾部;
length++;
}
常规做法
每次取新结点,都从头结点开始遍历到尾部,然后将结点插入到尾部
bool ListInsert(LinkList &L, int i, ElemType e)
{
if (i < 1) {
return false;
}
LNode *p;
int j = 0;
p = L;
// 循环找到第 i-1 个结点
while (p != NULL && j < i - 1) {
p = p->next;
j++;
}
if (p== NULL) {
return false;
}
LNode *s = (LNode *)malloc(sizeof(LNode));
if (s == NULL) {
return false;
}
// 开始插入
s->data = e;
s->next = p->next;
p->next = s; // 把结点s连到p之后
return true;
}
时间复杂度: O ( n 2 ) O(n^2) O(n2)
优化算法
将链表值依次输入,并使用一个临时指针变量记录尾部结点
LinkList List_TailInsert(LinkList &L)
{
// 正向建立单链表
int x; // ElemType -> 整型
L = (LinkList)malloc(sizeof(LNode)); // 头结点
if (L == NULL) {
return NULL;
}
LNode *s, *r = L; // r为表尾指针
while(scanf("%d", &x) != EOF){
s = (LNode*)malloc(sizeof(LNode));
if (s == NULL) {
// ... 清理内存代码...
return NULL;
}
s->data = x;
r->next = s;
r = s;
}
r->next = NULL;
return L;
}
时间复杂度: O ( n ) O(n) O(n)
头插法
思路
初始化单链表
while (没有取完) {
每次取一个数据元素e;
ListInsertNode(L,e);
}
LinkList List_HeadInsert(LinkList &L)
{
LNode *s;
int x;
L = (Linklist)malloc(sizeof(LNode)); // 创建头结点
if (L == NULL) {
return NULL;
}
L->next = NULL; //初始为空链表,清除脏数据
while (scanf("%d",&x) != EOF) {
s = (LNode*)malloc(sizeof(LNode));
if (s == NULL) {
// ... 清理内存代码...
return NULL;
}
s->data = x;
s->next = L->next;
L->next = s;
}
return L;
}
参考文章
【DS 数据结构】003 | 单链表
上一篇: 简单的 DHCP 分配,以及子网划分实验
下一篇: Vue.js(过渡)