当前位置：首页 > news >正文

【数据结构】单链表的增删查改

news 2025/5/4 8:23:03

本文是小编巩固自身而作，如有错误，欢迎指出！

1.链表的概念

概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

和之前的顺序表不同，顺序一般通过数组实现，每个储存的元素都是相邻的，而链表不一样，链表的每一个节点并不相连，而是通过链表内的指针进行相连，每一个节点可以分为两个部分，储存的数据和指向下一个节点的地址。

2.链表的性质

1、链式机构在逻辑上是连续的，在物理结构上不⼀定连续

2、结点⼀般是从堆上申请的

3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

我们在此用结构体创建链表的原型

//定义链表结构
typedef int sldatatype;
struct slistnode
{sldatatype data;//储存的数据struct slistnode* next;//指向下一个节点
};
typedef struct slistnode SLTNODE;

然后我们创建一个简单的链表

void test01()
{SLTNODE* node1 = (SLTNODE*)malloc(sizeof(SLTNODE));SLTNODE* node2 = (SLTNODE*)malloc(sizeof(SLTNODE));SLTNODE* node3 = (SLTNODE*)malloc(sizeof(SLTNODE));SLTNODE* node4 = (SLTNODE*)malloc(sizeof(SLTNODE));node1->data = 1;node2->data = 2;node3->data = 3;node4->data = 4;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;
}

3.链表的打印

我们现在看看链表的打印是怎么实现的

先前我们学习顺序表时我们打印时可以直接将指向元素的地址向后挪，而链表每一个节点之间是相互独立的，因此我们只能过通过指针之间的链接进行打印

void sltprint(SLTNODE* phead)
{SLTNODE* pcur = phead;while (pcur){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

在这个代码中，我们将每一个节点通过指针的方式进行链式访问。

4.链表的头插尾插

4.1链表的节点创建

要想要在链表中插入数值，就不能跟循序表一样进行数据的移动完成，而要通过创立新的节点

SLTNODE* sltbuynode(sldatatype x)
{//创建新的节点SLTNODE* newnode = (SLTNODE*)malloc(sizeof(SLTNODE));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}

4.2链表的尾插

其中的思路就是在链表尾部加入一个新的节点

oid sltpushback(SLTNODE** pphead, sldatatype x)
{SLTNODE* newnode= sltbuynode(x);if (*pphead == NULL)//链表为空{*pphead = newnode;}else{SLTNODE* ptail = *pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;}}

其中一个要注意的点当链表为空时，就直接将其作为头节点即可，还有一个值得思考的问题即为什么这里使用了二级指针？

其原因在于如果传过去的是节点，其中形参的改变并不会影响实参，即整个函数运行结束后，仍不会改变原来的节点

4.3链表的头插

void sltpushfrond(SLTNODE** pphead, sldatatype x)
{assert(*pphead);SLTNODE* newnode = sltbuynode(x);newnode->next = *pphead;*pphead = newnode;//让指向第一个节点的位置变化
}

不如尾插还需要遍历，头插只需要将创建的新节点指向的位置改为之前的头结点即可

5.链表的头删与尾删

5.1尾删

void sltpopback(SLTNODE** pphead)
{assert(pphead && *pphead);//只有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else {SLTNODE* prev = NULL;SLTNODE* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}
}

思路与尾插相同，把尾部的最后一个节点释放，并将其前一个节点的指向位置改为空指针即可

就是要考虑到一开始就只有一个节点的情况

5.2头删

void sltpopfront(SLTNODE** pphead)
{assert(pphead && *pphead);SLTNODE* next = (*pphead)->next;free(*pphead);*pphead=next;
}

直接将第一个节点释放，并将头节点的地址改为第二个节点的地址

6.单链表的查找

SLTNODE* sltfind(SLTNODE* phead, sldatatype x)
{SLTNODE* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

其主要思路就是将整个链表遍历找出值相同的节点，找到了就返回节点地址，没找到就返回NULL

7.链表的在任意节点的插值

7.1在位置前插值

void sltinsert(SLTNODE** pphead, SLTNODE* pos, sldatatype x)
{assert(pphead && pos);//指向第一个节点时if (pos == *pphead){sltpushfrond(*pphead,x);}SLTNODE* newnode = sltbuynode(x);SLTNODE* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;
}

先遍历链表找到插值位置的前一个节点，并将其指向的节点改变成插入的节点，并将插入的节点指向的位置设置为下一个节点

7.2在位置后插值

void sltinsertafter(SLTNODE* pos, sldatatype x)
{assert(pos);SLTNODE* newnode = sltbuynode(x);newnode->next = pos->next;pos->next = newnode;
}

直接改变两个指向地址即可

8.链表的删除

8.1指定位置的删除

void slterase(SLTNODE** pphead, SLTNODE* pos)
{assert(pphead && pos);//pos头结点if (pos == *pphead){sltpopfront(*pphead);}else {SLTNODE* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

其思路与插入相似，即将上一个节点的指向位置指向下一个节点即可，然后将原本的节点释放

8.2指定位置后一个数的删除

void slteraseafter(SLTNODE* pos)
{assert(pos&&pos->next);SLTNODE* del = pos->next;pos->next = del->next;free(del);del = NULL;
}

不需要遍历，直接改变本身的指向位置即可

9.链表的销毁

void slistdestory(SLTNODE** pphead)
{SLTNODE* pcur = *pphead;while (pcur){SLTNODE* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

利用循环将每一个节点依次释放，并将首节点置空即可。

10.完整代码实现

头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定义链表结构
typedef int sldatatype;
struct slistnode
{sldatatype data;//储存的数据struct slistnode* next;//指向下一个节点
};
typedef struct slistnode SLTNODE;
void sltprint(SLTNODE* phead);//打印链表
void sltpushback(SLTNODE** pphead, sldatatype x);//尾插
SLTNODE* sltbuynode(sldatatype x);//创建新的节点
void sltpushfrond(SLTNODE** pphead, sldatatype x);//头插
void sltpopback(SLTNODE** pphead);//尾删
void sltpopfront(SLTNODE** pphead);//头删
SLTNODE* sltfind(SLTNODE* phead, sldatatype x);//查找
void sltinsert(SLTNODE** pphead, SLTNODE* pos, sldatatype x);//在指定数据前插入数据
void sltinsertafter( SLTNODE* pos, sldatatype x);//在指定数据后插入数据
void slterase(SLTNODE** pphead, SLTNODE* pos);//删除pos节点
void slteraseafter(SLTNODE* pos);//删除pos的下一个节点
void slistdestory(SLTNODE** pphead);//销毁链表

源文件

#define _CRT_SECURE_NO_WARNINGS
#include"single_list.h"void sltprint(SLTNODE* phead)
{SLTNODE* pcur = phead;while (pcur){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("NULL\n");
}
SLTNODE* sltbuynode(sldatatype x)
{//创建新的节点SLTNODE* newnode = (SLTNODE*)malloc(sizeof(SLTNODE));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}
void sltpushback(SLTNODE** pphead, sldatatype x)
{SLTNODE* newnode= sltbuynode(x);if (*pphead == NULL)//链表为空{*pphead = newnode;}else{SLTNODE* ptail = *pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;}}
void sltpushfrond(SLTNODE** pphead, sldatatype x)
{assert(*pphead);SLTNODE* newnode = sltbuynode(x);newnode->next = *pphead;*pphead = newnode;//让指向第一个节点的位置变化
}
void sltpopback(SLTNODE** pphead)
{assert(pphead && *pphead);//只有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else {SLTNODE* prev = NULL;SLTNODE* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}
}
void sltpopfront(SLTNODE** pphead)
{assert(pphead && *pphead);SLTNODE* next = (*pphead)->next;free(*pphead);*pphead=next;
}
SLTNODE* sltfind(SLTNODE* phead, sldatatype x)
{SLTNODE* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
void sltinsert(SLTNODE** pphead, SLTNODE* pos, sldatatype x)
{assert(pphead && pos);//指向第一个节点时if (pos == *pphead){sltpushfrond(*pphead,x);}SLTNODE* newnode = sltbuynode(x);SLTNODE* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;
}
void sltinsertafter(SLTNODE* pos, sldatatype x)
{assert(pos);SLTNODE* newnode = sltbuynode(x);newnode->next = pos->next;pos->next = newnode;
}
void slterase(SLTNODE** pphead, SLTNODE* pos)
{assert(pphead && pos);//pos头结点if (pos == *pphead){sltpopfront(*pphead);}else {SLTNODE* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}
void slteraseafter(SLTNODE* pos)
{assert(pos&&pos->next);SLTNODE* del = pos->next;pos->next = del->next;free(del);del = NULL;
}
void slistdestory(SLTNODE** pphead)
{SLTNODE* pcur = *pphead;while (pcur){SLTNODE* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

测试文件

#define _CRT_SECURE_NO_WARNINGS
#include"single_list.h"
void test01()
{SLTNODE* node1 = (SLTNODE*)malloc(sizeof(SLTNODE));SLTNODE* node2 = (SLTNODE*)malloc(sizeof(SLTNODE));SLTNODE* node3 = (SLTNODE*)malloc(sizeof(SLTNODE));SLTNODE* node4 = (SLTNODE*)malloc(sizeof(SLTNODE));node1->data = 1;node2->data = 2;node3->data = 3;node4->data = 4;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;SLTNODE* plist = node1;sltprint(plist);}
void test02()
{SLTNODE* plist = NULL;//创建空链表sltpushback(&plist, 1);sltpushback(&plist, 1);sltpushback(&plist, 2);sltpushback(&plist, 4);sltpushback(&plist, 3);sltpushfrond(&plist, 5);sltpopfront(&plist);sltpopback(&plist);sltprint(plist);SLTNODE* find= sltfind(plist, 4);/*if (find){printf("找到了\n");}else{printf("未找到\n");}*//*sltinsert(&plist, find, 100);*/sltinsertafter(find, 50);//slterase(&plist, find);/*slteraseafter(find);*/slistdestory(&plist);sltprint(plist);
}
int main()
{test01();/*test02();*/return 0;
}

本次分享就到这里，后续会继续更新，感谢阅读！

查看全文

http://www.xdnf.cn/news/256411.html