个人主页 ： 水月梦镜花
个人专栏 ： 《C语言》 《数据结构》
前言
本博客将要实现的无头单向不循环链表。
一、单链表实现思路和图解
1.节点的定义(SListNode)
我们将节点定义为如下结构：
其成员变量有data，next。
将int重命名为STLDataType，方便我们以后修改数据域的内容。
//无头单向不循环链表
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SListNode;
2.申请一个节点(BuySListNode)
动态申明一个空间，来放置数据。如下：
将data的内容置成形参x，next置NULL。
//申请一个节点
SListNode* BuySListNode(SLTDataType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
retur
3.单链表打印(SListPrint)
循环遍历链表，直到尾节点。创建一个结构体指针变量cur，循环cur = cur->next，并打印cur->data的内容，直到cur == NULL。
//单链表打印
void SListPrint(SListNode* plist)
{
SListNode* cur = plist;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
4.单链表尾插(SListPushBack)
- 如果链表不为NULL(链表中有元素)，要先遍历链表找到尾节点，在让尾节点指向新节点，完成尾插。
- 如果链表为NULL(链表中没有元素)，此时应该直接让新节点等于头结点，完成尾插。(本链表是无哨兵位的)
- 如果传入的头结点无效，直接判错。
当链表为NULL，我们就要修改头结点本身的内容，所以我们需要头结点的指针，而本文中头结点本身就是结构体指针，所以尾插函数参数我们需要二级指针。
//单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x)
{
assert(pplist);
SListNode* newnode = BuySListNode(x);
if (*pplist != NULL)
{
SListNode* cur = *pplist;
while (cur->next != NULL)
{
cur = cur->next;
}
cur->next = newnode;
}
else
{
*pplist = newnode;
}
}
5.单链表的头插(SListPushFront)
对于头插而言，链表是否有元素并不重要，我们只需要让新节点的指向头结点，并将头结点等于新节点。
因为头插链表，一定会改变头结点的内容，所以我们头插函数的形参也是二级指针。
//单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x)
{
assert(pplist);
SListNode* newnode = BuySListNode(x);
newnode->next = *pplist;
*pplist = newnode;
}
6.单链表的尾删(SListPopBack)
- 如果链表元素有两个及两以上，我们需要两个指针变量prev，next来找尾节点，循环prev = cur，cur = cur->next，使next指向尾节点，prev指向尾节点的前一个，free尾节点，prev指向的节点指向NULL。
- 如果链表元素只有一个，直接free头结点，使头结点置NULL。
- 如果链表没有元素，直接判错。
当链表元素只有一个时，此时尾删链表，要修改头结点的内容，尾删函数的形参需要二级指针。
//单链表的尾删
void SListPopBack(SListNode** pplist)
{
assert(pplist);
//链表为NULL
assert(*pplist);
if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
SListNode* cur = *pplist;
SListNode* prev = NULL;
while (cur->next != NULL)
{
prev = cur;
cur = cur->next;
}
prev->next = NULL;
free(cur);
}
}
7.单链表头删(SListPopFront)
我们需要一个结构体指针变量next，来保存头结点的下一个节点，然后free头结点，使头结点 = 指针变量next。
- 如果链表没有元素，直接判错。
//单链表头删
void SListPopFront(SListNode** pplist)
{
assert(pplist);
assert(*pplist);
SListNode* next = (*pplist)->next;
free(*pplist);
*pplist = next;
}
8.单链表的查找(SListFind)
我们需要一个结构体指针变量cur，来遍历链表比较cur->data == x，如果相等，放回此时cur的内容(该节点的地址)。如果遍历完链表，并没有相等元素，放回NULL。
//单链表的查找
SListNode* SListFind(SListNode* plist, SLTDataType x)
{
SListNode* cur = plist;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
9.单链表在pos位置之后插入x(SListInsertAfter)
我们让newnode指向pos下一个的节点，pos指向newnode。
- 如果我们先让pos指向newnode，newnode在指向pos的下一个节点，就会造成newnode指向自己，导致链表成环。
- 该函数不会影响头结点的内容，所以函数的形参不用二级指针。
//单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
10.单链表删除在pos位置之后的值(SListEraseAfter)
我们需要一个结构体指针变量next，记录pos下一个节点的地址，然后是pos指向next的下一个节点，接着free(next)。
- 如果链表只有一个元素，我们不能调用该函数，否则会导致NULL指针的解引用。
- 该函数不会改变头结点的内容，所以形参我们不用二级指针。
//单链表删除在pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
assert(pos && pos->next);
SListNode* next = pos->next;
pos->next = next->next;
free(next);
}
11.单链表的销毁(SListDestroy)
我们需要两个结构体指针prev，cur。先让prev = cur ，cur再指向下一个节点，free(prev)，重复上述操作，直到cur指向NULL。
需要我们在函数调用完后，自己对头结点置NULL。
//单链表的销毁
void SListDestroy(SListNode* plist)
{
assert(plist);
SListNode* cur = plist;
while (cur != NULL)
{
SListNode* prev = cur;
cur = cur->next;
free(prev);
}
}
二、代码实现
//slist.h 文件
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//无头单向不循环链表
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SListNode;
//申请一个节点
SListNode* BuySListNode(SLTDataType x);
//单链表打印
void SListPrint(SListNode* plist);
//单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x);
//单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x);
//单链表的尾删
void SListPopBack(SListNode** pplist);
//单链表头删
void SListPopFront(SListNode** pplist);
//单链表的查找
SListNode* SListFind(SListNode* plist, SLTDataType x);
//单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x);
//单链表删除在pos位置之后的值
void SListEraseAfter(SListNode* pos);
//单链表的销毁
void SListDestroy(SListNode* plist);
//slist.c 文件
#include "slist.h"
//申请一个节点
SListNode* BuySListNode(SLTDataType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//单链表打印
void SListPrint(SListNode* plist)
{
SListNode* cur = plist;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
//单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x)
{
assert(pplist);
SListNode* newnode = BuySListNode(x);
if (*pplist != NULL)
{
SListNode* cur = *pplist;
while (cur->next != NULL)
{
cur = cur->next;
}
cur->next = newnode;
}
else
{
*pplist = newnode;
}
}
//单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x)
{
assert(pplist);
SListNode* newnode = BuySListNode(x);
newnode->next = *pplist;
*pplist = newnode;
}
//单链表的尾删
void SListPopBack(SListNode** pplist)
{
assert(pplist);
//链表为NULL
assert(*pplist);
if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
SListNode* cur = *pplist;
SListNode* prev = NULL;
while (cur->next != NULL)
{
prev = cur;
cur = cur->next;
}
prev->next = NULL;
free(cur);
}
}
//单链表头删
void SListPopFront(SListNode** pplist)
{
assert(pplist);
assert(*pplist);
SListNode* next = (*pplist)->next;
free(*pplist);
*pplist = next;
}
//单链表的查找
SListNode* SListFind(SListNode* plist, SLTDataType x)
{
SListNode* cur = plist;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
//单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//单链表删除在pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
assert(pos && pos->next);
SListNode* next = pos->next;
pos->next = next->next;
free(next);
}
//单链表的销毁
void SListDestroy(SListNode* plist)
{
assert(plist);
SListNode* cur = plist;
while (cur != NULL)
{
SListNode* prev = cur;
cur = cur->next;
free(prev);
}
}
总结
以上就是我对于无头单向不循环链表的实现！！！文章来源：https://www.toymoban.com/news/detail-624210.html
文章来源地址https://www.toymoban.com/news/detail-624210.html
到了这里，关于数据结构：单链表的实现(C语言)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
