准备工作
创建一个头文件(SList.h),两个源文件(SList.c和test.c)
- SList.h:用于包含库函数的头文件,链表节点结构体声明,接口函数的声明等【另外两个源文件要包含SList.h这个头文件,才能使用其中的声明】
- SList.h:用于实现单链表的接口函数
- test.c:存放main函数,用于链表的测试
——————————————————————————————————————————————————
上图包含了以下3个操作
1.库函数的头文件的包含:
- stdio.h:输入/输出等函数
- stdlib.h:动态内存申请
- assert.h:报错函数assert
2.给链表节点的数据域的数据类型重命名
为什么要重命名呢?
这是为了以后如果改变了SL结构体中数据存储的类型时,不用到处改函数参数等地方的数据类型,只要改typedef后的int 为对应要改成的数据类型就可以。
3.链表节点结构体定义
——————————————————————————————————————————————————
打印链表
代码:
函数参数设计:
因为打印链表不会改变头指针,所以传输一级头指针
函数形象图解
【方框的上方框为数据域,下方框为指针域】
——————————————————————————————————————————————————
尾插
函数参数设计
- SLTNodephead:
因为当第一个节点为空的时候头指针指向的地址会改变,
所以传头指针的地址进去,用二级指针接收** - x:
要插入的数据
函数原理
先动态内存申请一个节点的空间
如果链表为空,就让新的节点成为第一个节点,让phead指向新节点。
否则就用cur遍历链表,用prev指向cur的前一个节点【实现方式:cur指向下一个节点之前,让prev=cur】,这样当cur遍历指向NULL结束循环时,prev就指向最后一个节点,此时再尾插,让prev的指针域指向新节点,再让新节点的指针域指向NULL。
(也可以省去prev,把while循环结束的条件换成cur->next,当cur->next为空时循环结束,此时cur正好指向链表的最后一个节点)
图解
【方框的上方框为数据域,下方框为指针域】
——————————————————————————————————————————————————
头插
函数参数设计
- SLTNodephead:
因为头指针指向的地址会改变,
所以传头指针的地址进去,用二级指针接收** - x:
要插入的数据
图解
【方框的上方框为数据域,下方框为指针域】
——————————————————————————————————————————————————
尾删
函数参数设计
- SLTNodephead:
因为当链表只有一个节点的时候头指针指向的地址会改变,
所以传头指针的地址进去,用二级指针接收**
图解
【方框的上方框为数据域,下方框为指针域】
——————————————————————————————————————————————————
头删
函数参数设计
- SLTNodephead:
因为头指针指向的地址会改变,
所以传头指针的地址进去,用二级指针接收**
图解
【方框的上方框为数据域,下方框为指针域】
——————————————————————————————————————————————————
随机查找
函数参数设计
- SLTNode*phead
因为打印链表不会改变头指针,所以传输一级头指针 - x:
查找的值
——————————————————————————————————————————————————
随机插入
函数参数设计
- SLTNodephead:
因为pos等于头指针的时候头指针指向的地址会改变,
所以传头指针的地址进去,用二级指针接收** - SLTNode*pos:
配合随机查找函数的返回值,pos一般等于随机查找函数返回的指针 - x
要插入的数据
图解
——————————————————————————————————————————————————
随机删除
函数参数设计
- SLTNodephead:
因为pos等于头指针的时候头指针指向的地址会改变,
所以传头指针的地址进去,用二级指针接收** - SLTNode*pos:
配合随机查找函数的返回值,pos一般等于随机查找函数返回的指针
图解
——————————————————————————————————————————————————
全部代码
SList.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType val;
struct SListNode* next;
}SLTNode;
//打印链表
void SListPrint(SLTNode*phead);
//尾插
void SListPushBack(SLTNode** phead, SLTDateType x);
//头插
void SListPushFront(SLTNode** phead, SLTDateType x);
//尾删
void SListPopBack(SLTNode** phead);
//头删
void SListPopFront(SLTNode** phead);
//查找x,找到了返回指向x的结构指针,找不到返回NULL
SLTNode* SListFind(SLTNode* phead, SLTDateType x);
//在pos之前插入数据
void SListInsert(SLTNode** phead, SLTNode*pos, SLTDateType x);
//删除pos指向的节点
void SListEase(SLTNode** phead, SLTNode* pos);
```c
```c
在这里插入代码片
SLst.c
#include"SList.h"
void SListPrint(SLTNode* phead)
{
SLTNode* cur = phead;//不要用直接用头节点去遍历链表,
//防止之后要使用头节点时找不到头节点
if (phead == NULL)//头结点为空
{
printf("NULL\n");
return;
}
while (cur)//cur为空时链表遍历结束
{
printf("%d->",cur->val);
cur = cur->next;//让cur指向下一个节点
}
printf("NULL");
}
void SListPushBack(SLTNode** phead, SLTDateType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//动态内存申请一个节点的空间
if (newnode == NULL)//malloc失败时返回NULL
{
printf("节点malloc失败");
exit(1);//结束程序
}
SLTNode* cur = *phead;
SLTNode* prev = *phead;//prev指向cur的前一个节点
if (*phead == NULL)
{
*phead = newnode;//头结点为空就让新节点成为头
newnode->next = NULL;//此时新节点为最后一个节点,所以其指针域指向NULL
newnode->val = x;//存放数据
}
else
{
while (cur)//遍历链表找到链表的最后一个节点
{
prev = cur;//让prev指向cur的前一个节点
cur = cur->next;
}
newnode->val = x;
prev->next = newnode;//此时prev为尾插前链表的最后一个节点,让它的指针域指新节点
newnode->next = NULL;
}
}
void SListPushFront(SLTNode** phead, SLTDateType x)
{
SLTNode* newnode= (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
printf("节点malloc失败");
exit(1);
}
if (*phead == NULL)
{
*phead = newnode;//让新节点成为头结点
newnode->next = NULL;
newnode->val = x;//存放数据
}
else
{
SLTNode* cur = *phead;//防止找不到 原头节点
*phead = newnode;//让新节点成为头结点
newnode->next = cur;//让新节点连接上 原头结点
newnode->val = x;
}
}
void SListPopBack(SLTNode** phead)
{
assert(*phead!=NULL);//不能一直删,当链表删空了的时候,再删就报错
SLTNode* prev = *phead;//prev指向cur的前一个节点
SLTNode* cur = *phead;
while (cur->next)//当cur指向最后一个节点时,结束循环
{
prev = cur;//循环结束时 prev指向链表的倒数第二个节点
cur = cur->next;
}
if (cur == *phead)//当链表只有头节点时
{
free(cur);
*phead = NULL;//为防止野指针,让phead中存放的地址置空
return;//结束函数
}
prev->next = NULL;//删除了最后一个节点时,让倒数第二个节点的指针域指向NULL
free(cur);
}
void SListPopFront(SLTNode** phead)
{
assert(*phead != NULL);//不能一直删,当链表删空了的时候,再删就报错
SLTNode* cur = (*phead)->next;//让cur指向链表的第二个节点,当链表只有一个节点时cur就等于NULL
free(*phead);//释放头节点指向的空间
*phead = cur;//让新的头节点指向删之前的链表的第二个节点
}
//查找数据域等于x的节点,找到了返回指向x的结构指针,找不到返回NULL
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
if (phead == NULL)//如果链表为空,就肯定找不到
return NULL;
else
{
SLTNode* cur = phead;
while (cur)//遍历链表
{
if (cur->val == x)//如果节点的数据域的值为要找的x
{
return cur;//找到了就返回
}
else
{
cur = cur->next;//不等于就让cur指向下一个节点
}
}
return NULL;//遍历完链表还找不到就是没有数据域为x的节点
}
}
//在pos之前插入数据
void SListInsert(SLTNode** phead, SLTNode* pos, SLTDateType x)
{
assert(pos != NULL);//pos不能为空
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
printf("节点malloc失败");
exit(1);
}
SLTNode* cur = *phead;
if (pos == *phead)//当pos指向头结点时,相当于头插
{
cur = *phead;//防止原头节点找不到了
*phead = newnode;
newnode->next = cur;
newnode->val = x;
}
else
{
SLTNode* prev = *phead;//prev指向cur的前一个节点
while (cur)
{
if (cur == pos)
{
prev->next = newnode;//当cur==pos时,prev指向pos的前一个节点
newnode->next = cur;//让新节点连接上pos
newnode->val = x;
return;//插入完成就返回
}
prev = cur;//cur不等于pos就让prev指向cur的当前指向的节点
cur = cur->next;//让cur指向后一个节点
}
}
}
//删除pos指向的节点
void SListEase(SLTNode** phead, SLTNode* pos)
{
assert(*phead != NULL);//不能一直删,当链表删空了的时候,再删就报错
assert(pos != NULL);//pos不能为空
SLTNode* tmp = pos->next;//存储pos的下一个节点,防止pos释放后找不到pos的下一个节点
SLTNode* cur = *phead;
if (pos == *phead)
{
free(*phead);
*phead = tmp;//让phead指向pos的下一个节点
return;
}
while (cur)
{
if (cur->next == pos)//此时cur指向pos的前一个节点
{
cur->next = tmp;
free(pos);
}
cur = cur->next;//不等于就让cur指向下一个节点
}
}
``文章来源:https://www.toymoban.com/news/detail-764521.html
以上就是全部内容了,如果对你有帮助的话,可以点个赞支持一下!文章来源地址https://www.toymoban.com/news/detail-764521.html
到了这里,关于详解C语言单链表接口函数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!