C语言数据结构实例讲解单链表的实现 C语言数据结构实例讲解单链表

1、单链表
2、单链表的实现

头文件
函数的实现

（1）打印链表
（2）动态申请结点
（3）尾插
（4）头插
（5）尾删
（6）头删
（7）查找
（8）在pos之前插入
（9）删除pos
（10）在pos之后插入
（11）在pos后删除
（12）最后用完记得销毁

3、各功能的测试

这里我们来简单实现单链表的增删查找。

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

文章图片

文章图片

（链表和我们生活中最接近的就是火车了。）

2、单链表的实现接下来我们来实现单链表的增删查改
【C语言数据结构实例讲解单链表的实现】
头文件

#pragma once #include #include #include typedef int SLDataType; //链表的创建typedef struct SListNode{ SLDataType data; //val struct SListNode* next; //存储下一个结点的地址}SListNode,SLN; //打印链表void SListPrint(SListNode* phead); //尾插void SListPushBack(SListNode** pphead, SLDataType x); //头插void SListPushFront(SListNode** pphead, SLDataType x); //尾删void SListPopBack(SListNode** pphead); //头删void SListPopFront(SListNode** pphead); //查找SListNode* SListFind(SListNode* phead, SLDataType x); //在pos位置之前插入void SListInsert(SListNode** pphead, SListNode* pos, SLDataType x); //删除pos位置void SListErase(SListNode** pphead, SListNode* pos); //在pos位置之后插入void SlistInserAfter(SListNode* pos, SLDataType x); //删除pos后的值void SlistEraseAfter(SListNode* pos); //用完销毁void SListDestroy(SListNode** pphead);

函数的实现

（1）打印链表

void SListPrint(SListNode* phead){ assert(phead); SListNode* cur = phead; if (cur == NULL) {printf("SList is NULL\n"); } while (cur != NULL) {printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }

（2）动态申请结点将一个data x动态申请结点。

文章图片

SListNode* BuySList(SLDataType x){ SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); if (newnode == NULL) {printf("malloc fail\n"); exit(-1); } else {newnode->data = https://www.it610.com/article/x; newnode->next = NULL; } return newnode; }

（3）尾插

文章图片

void SListPushBack(SListNode** pphead, SLDataType x){ assert(pphead); SListNode* newnode = BuySList(x); if (*pphead == NULL) {*pphead = newnode; } else {//找尾SListNode* tail = *pphead; while (tail->next != NULL){tail = tail->next; }//走完循环找到尾tail->next = newnode; } }

（4）头插

文章图片

void SListPushFront(SListNode** pphead, SLDataType x){ assert(pphead); SListNode* newnode = BuySList(x); newnode->next = *pphead; *pphead = newnode; }

（5）尾删

文章图片

void SListPopBack(SListNode** pphead){ assert(pphead); //当链表只有一个结点时 if (*pphead == NULL) {printf("SListNode is NULL\n"); return; } //当链表只有一个结点时 else if ((*pphead)->next == NULL) {free(*pphead); *pphead = NULL; } //当链表有多个结点时 else {SListNode* tail = *pphead; while (tail->next->next != NULL){tail = tail->next; }free(tail->next); tail->next = NULL; }}

（6）头删

文章图片

void SListPopFront(SListNode** pphead){ assert(pphead); if (*pphead == NULL) {printf("SList is NULL\n"); return; } else {SListNode* next = (*pphead)->next; free(*pphead); *pphead = next; }}

（7）查找

SListNode* SListFind(SListNode* phead, SLDataType x){ assert(phead); SListNode* cur = phead; while (cur != NULL) {if (cur->data =https://www.it610.com/article/= x){return cur; }//如果没找到就往下走cur = cur->next; } //循环完成后还没找到就说明链表中没有该值 return NULL; }

（8）在pos之前插入

文章图片

void SListInsert(SListNode** pphead, SListNode* pos, SLDataType x){ assert(pphead); assert(pos); //pos是第一个位置 if (pos == *pphead) {SListPushFront(pphead, x); } //pos不是第一个位置 else {SListNode* prev = *pphead; while (prev->next != pos){prev = prev->next; }SListNode* newnode = BuySList(x); prev->next = newnode; newnode->next = pos; }}

（9）删除pos

文章图片

void SListErase(SListNode** pphead, SListNode* pos){ assert(pphead); assert(pos); //1、头结点为空 if (*pphead == NULL) {printf("SList is NULL\n"); return; } //2、删除第一个结点 else if (pos == *pphead) {SListPopFront(pphead); } //3、其他结点 else {SListNode* prev = *pphead; while (prev->next != pos){prev = prev->next; }prev->next = pos->next; free(pos); pos = NULL; }}

（10）在pos之后插入相对于在pos之前插入，在pos后插入可以不用传头结点，无论pos在哪个位置都适用。

文章图片

void SListInsertAfter(SListNode* pos, SLDataType x){ assert(pos); SListNode* newnode = BuySList(x); SListNode* next = pos->next; pos->next = newnode; newnode->next = next; //下面这种方式也可以 /*SListNode* newnode = BuySList(x); newnode->next = pos->next; pos->next = newnode; */}

（11）在pos后删除

文章图片

void SListEraseAfter(SListNode* pos){ assert(pos); SListNode* next = pos->next; if (next) {pos->next = next->next; free(next); next = NULL; } }

（12）最后用完记得销毁

void SListDestroy(SListNode** pphead){ assert(pphead); SListNode* cur = *pphead; while (cur) {SListNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }

3、各功能的测试

#include "SList.h" void test1(){ SListNode* slist = NULL; //测试尾插 SListPushBack(&slist, 1); SListPushBack(&slist, 2); SListPushBack(&slist, 3); SListPushFront(&slist, 5); SListPushFront(&slist, 4); SListPrint(slist); //测试头插 SListPushFront(&slist, 5); SListPushFront(&slist, 4); SListPrint(slist); //测试尾删 SListPopBack(&slist); SListPopBack(&slist); SListPrint(slist); //测试头删 SListPopFront(&slist); SListPopFront(&slist); SListPopFront(&slist); SListPrint(slist); //测试查找 SListNode* ret1 = SListFind(slist, 5); printf("%d\n", ret1->data); /*SListNode* ret2 = SListFind(slist, 2); printf("%d\n", ret2->data); */ //pos前插测试 SListNode* pos = SListFind(slist, 1); if (pos) {SListInsert(&slist,pos,3); } SListPrint(slist); pos = SListFind(slist, 1); if (pos) {SListInsert(&slist, pos, 10); } SListPrint(slist); //删除pos测试 pos = SListFind(slist, 10); if (pos) {SListErase(&slist, pos); } SListPrint(slist); //测试在pos后插入 pos = SListFind(slist, 3); if (pos) {SListInsertAfter(pos, 6); } SListPrint(slist); pos = SListFind(slist, 1); if (pos) {SListInsertAfter(pos, 8); } SListPrint(slist); //测试删除pos后的值 pos = SListFind(slist, 1); if (pos) {SListEraseAfter(pos); } SListPrint(slist); } int main(){ test1(); return 0; }

运行结果：