目录链表分类单链表的介绍单链表的基本操作创建打印尾插头插尾删头删查找任意位置插入任意位置删除销毁完整代码总结链表分类 链表主要有下面三种分类方法: 单向或者双向带头或者不带头循环或者
链表主要有下面三种分类方法:
typedef struct SListnode
{
DataType data;//数据域
struct SListNode *next;//结构体指针,指向下一个节点
}SListNode;//类型别名
如图
链表的每一个节点由数据域和指针域构成,数据域存放数据,指针域中的指针指向下一个节点。
plist表示链表的指针,指向链表的第一个节点,最后一个节点的指针为空。
创建单链表有几点需注意:
SListNode* BuySListNode(DataType x)
{
SListNode* plist = (SListNode*)malloc(sizeof(SListNode));
if (plist == NULL)
{
return NULL;//判断是否申请成功
}
plist->data = x;
plist->next = NULL;
return plist;
}
遍历链表,进行打印
void SListPrint(SListNode* plist)
{
assert(plist);
SListNode* cur = plist;
while (cur)
{
printf("%d-->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
尾插的操作步骤:
注意事项:
void SListPushBack(SListNode** pplist, DataType x)
{
//改变指针指向,参数传二级指针
assert(pplist);//判断链表是否存在,与链表是否为空不同
//1.若链表为空,*pplist指向插入的节点
if (*pplist == NULL)
{
*pplist = BuySListNode(x);
}
else {
//2.链表不为空,指针移动到链表最后一个节点,其next指向插入的节点
SListNode* cur = *pplist;
while (cur->next)
{
cur = cur->next;//cur的next为空时,cur指向最后一个节点
}
cur->next = BuySListNode(x);
}
}
头插操作顺序:
进行头插时,要注意各个步骤的顺序,如果直接令*pplist指向了新增的的节点,会导致原有的第一个节点无法找;另外,链表为空时的操作方法与链表非空时代码可以合并,不用再分开写各种情况。
void SListPushFront(SListNode** pplist, DataType x)
{
assert(pplist);
//if (NULL == *pplist)
//{
// //链表为空
// *pplist = BuySListNode(x);
//}
//else
//{
// SListNode* temp = *pplist;//temp指向链表原来的第一个节点
// *pplist = BuySListNode(x);//plist指向新增的节点
// (*pplist)->next = temp;//新增的节点指向原来的第一个节点
//}
//上面两种情况代码可以合并
SListNode* node = BuySListNode(x);//申请一个新节点
node->next = *pplist;//新增的节点的next指向原来的第一个节点
*pplist = node;//*pplist指向新增的节点
}
尾删步骤:
注意事项:
void SListPopBack(SListNode** pplist)
{
assert(pplist);
//1.链表为空
if (NULL== *pplist)
{
return;
}
//2.链表只有一个元素
else if (NULL == (*pplist)->next)
{
free(*pplist);
*pplist = NULL;
}
//3.链表有多个元素
else
{
SListNode* prev = NULL;
SListNode* cur = *pplist;
while (cur->next)
{
prev = cur;
cur = cur->next;//循环结束时cur指向最后一个节点
}
//cur= NULL;//这里不能写cur=NULL,需要找到cur的前一个节点,将其next置空\
否则前一个结点的next依然指向原来的最后一个节点
prev->next = NULL;//prev成为最后一个节点
free(cur);//释放原来最后一个节点的空间
}
头删的操作步骤:
同样的,头删也要注意保存原来第一个节点的位置,否则*pplist指向改变后,原来的第一个节点就找不到了,会无法释放空间造成内存泄漏。
void SListPopFront(SListNode** pplist)
{
assert(pplist);
//1.单链表为空
if (NULL == *pplist)
{
return;
}
2.单链表有一个节点
//else if (NULL == (*pplist)->next)
//{
// *pplist = NULL;//删除后链表为空
//}
3.单链表有多个节点
//else
//{
//*pplist= (*pplist)->next;
//}
//两种情况可以合并,只有一个节点时,*pplist的next为空
else
{
SListNode* delNode = *pplist;
*pplist = delNode->next;
free(delNode);//释放删除节点的空间
}
}
用于查找某一元素是否存在于链表中,若存在则返回其第一次出现在链表中的位置,不存在则返回NULL。
遍历时注意循环条件。
SListNode* SListFind(SListNode* plist, DataType x)
{
SListNode* cur = plist;
while (cur)
{
if (cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;
}
pos节点后插入的步骤:
注意事项
void SListInsertAfter(SListNode* pos, DataType x)
{
assert(pos);//指针合法性校验
SListNode* newNode = BuySListNode(x);
newNode->next = pos->next;
pos->next = newNode;
}
与任意位置的插入相同,只能删除给定节点pos后面的节点
void SListDeleteAfter(SListNode* pos)
{
assert(pos);
//1.链表有一个节点
if (NULL == pos->next)
{
return;
}
//2.链表有多个节点
else
{
SListNode* temp = pos->next;
pos->next = temp->next;
free(temp);
}
}
链表的销毁,遍历一遍,逐个释放空间
void SListDestroy(SListNode** pplist)
{
assert(pplist);//链表是否存在
//1.链表为空
if (NULL == *pplist)
{
return;
}
else
{
SListNode* cur = NULL;
while (*pplist)
{
cur = *pplist;
*pplist = (*pplist)->next;
free(cur);
}
}
}
work.h
头文件包含,函数声明,定义结构体
#pragma once
#include<stdio.h>
#include<windows.h>
#include<assert.h>
#include<assert.h>
typedef int DataType;
typedef struct SListNode
{
DataType data;//数据域
struct SListNode *next;//结构体指针,指向下一个节点
}SListNode;//类型别名
//函数声明
SListNode* BuySListNode(DataType x);//节点申请
void SListPrint(SListNode* pst);//单链表遍历打印
void SListPushBack(SListNode** pplist, DataType x);//单链表尾插
void SListPushFront(SListNode** pplist, DataType x);//单链表头插
void SListPopBack(SListNode** pplist);//单链表尾删
void SListPopFront(SListNode** pplist);//单链表头删
SListNode* SListFind(SListNode* plist, DataType x);//单链表查找
void SListInsertAfter(SListNode* pos, DataType x);//pos后位置的插入
void SListDeleteAfter(SListNode* pos);//pos后位置的删除
void SListDestroy(SListNode** pplist);//释放链表空间
work.c
各操作函数的具体实现
#include"work.h"
//链表与顺序表的区别是,顺序表是物理空间上连续的
//而链表只在逻辑上连续,所以链表申请空间时是使用一个申请一个
//顺序表则是一次申请一段空间
SListNode* BuySListNode(DataType x)
{
//若在栈申请内存函数调用结束后会释放,所以使用动态申请
SListNode* plist = (SListNode*)malloc(sizeof(SListNode));
if (plist == NULL)
{
return NULL;//判断是否申请成功
}
plist->data = x;
plist->next = NULL;
return plist;
}
void SListPrint(SListNode* plist)
{
assert(plist);
SListNode* cur = plist;
while (cur)
{
printf("%d-->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
//尾插法
void SListPushBack(SListNode** pplist, DataType x)
{
//改变指针指向,参数传二级指针
assert(pplist);//判断链表是否存在,与链表是否为空不同
//1.若链表为空,*pplist指向插入的节点
if (*pplist == NULL)
{
*pplist = BuySListNode(x);
}
else {
//2.链表不为空,指针移动到链表最后一个节点,其next指向插入的节点
SListNode* cur = *pplist;
while (cur->next)
{
cur = cur->next;//cur的next为空时,cur指向最后一个节点
}
cur->next = BuySListNode(x);
}
}
//头插法
void SListPushFront(SListNode** pplist, DataType x)
{
assert(pplist);
//if (NULL == *pplist)
//{
// //链表为空
// *pplist = BuySListNode(x);
//}
//else
//{
// SListNode* temp = *pplist;//temp指向链表原来的第一个节点
// *pplist = BuySListNode(x);//plist指向新增的节点
// (*pplist)->next = temp;//新增的节点指向原来的第一个节点
//}
//链表为空的情况可以和不为空合并
SListNode* node = BuySListNode(x);//申请一个新节点
node->next = *pplist;//新增的节点的next指向原来的第一个节点
*pplist = node;//*pplist指向新增的节点
}
//尾删法?
void SListPopBack(SListNode** pplist)
{
assert(pplist);
//1.链表为空
if (NULL== *pplist)
{
return;
}
//2.链表只有一个元素
else if (NULL == (*pplist)->next)
{
free(*pplist);
*pplist = NULL;
}
//3.链表有多个元素
else
{
SListNode* prev = NULL;
SListNode* cur = *pplist;
while (cur->next)
{
prev = cur;
cur = cur->next;//循环结束时cur指向最后一个节点
}
//cur= NULL;//这里不能写cur=NULL,需要找到cur的前一个节点,将其next置空\
否则前一个结点的next依然指向原来的最后一个节点
prev->next = NULL;//prev最后一个节点
free(cur);//释放原来最后一个节点的空间
}
}
//头删
void SListPopFront(SListNode** pplist)
{
assert(pplist);
//1.单链表为空
if (NULL == *pplist)
{
return;
}
2.单链表有一个节点
//else if (NULL == (*pplist)->next)
//{
// *pplist = NULL;//删除后链表为空
//}
3.单链表有多个节点
//else
//{
//*pplist= (*pplist)->next;
//}
//两种情况可以合并,只有一个节点时,*pplist的next为空
else
{
SListNode* delNode = *pplist;
*pplist = delNode->next;
free(delNode);//释放删除节点的空间
}
}
//单链表查找
SListNode* SListFind(SListNode* plist, DataType x)
{
SListNode* cur = plist;
while (cur)
{
if (cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;
}
//任意位置的插入
//只能在pos的后面插入
void SListInsertAfter(SListNode* pos, DataType x)
{
assert(pos);//指针合法性校验
SListNode* newNode = BuySListNode(x);
newNode->next = pos->next;
pos->next = newNode;
}
//任意位置的删除
//只能删除给定的pos后面的节点
void SListDeleteAfter(SListNode* pos)
{
assert(pos);
//1.链表有一个节点
if (NULL == pos->next)
{
return;
}
//2.链表有多个节点
else
{
SListNode* temp = pos->next;
pos->next = temp->next;
free(temp);
}
}
// 链表空间释放
void SListDestroy(SListNode** pplist)
{
assert(pplist);//链表是否存在
//1.链表为空
if (NULL == *pplist)
{
return;
}
else
{
SListNode* cur = NULL;
while (*pplist)
{
cur = *pplist;
*pplist = (*pplist)->next;
free(cur);
}
}
}
main.c
程序入口,测试用例
#include"work.h"
void Test()
{
SListNode* node = NULL;//定义一个结构体指针
//尾插法插入五个节点
SListPushBack(&node, 1);
SListPushBack(&node, 2);
SListPushBack(&node, 3);
SListPushBack(&node, 4);
SListPushBack(&node, 5);
SListPrint(node);//遍历打印
SListPushFront(&node, 0);//头插一个节点
SListPrint(node);//遍历打印
SListPopBack(&node);//尾删最后一个节点
SListPrint(node);//遍历打印
SListPopFront(&node);//头删第一个节点
SListPrint(node);//遍历打印
printf("%p\n", SListFind(node, 4));//查找3在链表中的位置
printf("%p\n", SListFind(node, 99));//查找99在链表中的位置
SListInsertAfter(SListFind(node, 4), 99);//4后面插入一个节点99
SListPrint(node);//遍历打印
SListDeleteAfter(SListFind(node, 4));//删除4的下一个节点
SListPrint(node);//遍历打印
}
int main()
{
Test();
system("pause");
return 0;
}
以上为个人经验,希望能给大家一个参考,也希望大家多多支持编程网。
--结束END--
本文标题: C语言中单链表的基本操作(创建、销毁、增删查改等)
本文链接: http://www.lsjlt.com/news/194231.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0