【数据结构|C语言版】单链表

阅读本书更多章节>>>>

前言1. 单链表的概念和结构1.1 单链表的概念1.2 单链表的结构 2. 单链表的分类3.单链表的实现3.1 新节点创建3.2 单链表头插3.3 单链表头删3.4 单链表尾插3.5 单链表尾删3.6 链表销毁 4. 代码总结4.1 SLT.h4.2 SLT.c4.3 test.c 后言

---

前言

各位小伙伴大家好！时隔不久，小编来给大家讲解一下单链表的相关知识。

1. 单链表的概念和结构

1.1 单链表的概念

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

逻辑上连续物理上非连续

1.2 单链表的结构

链表是由一个个结点组成的

【节点】

【单链表雏形】

2. 单链表的分类

链表的结构⾮常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构。

【常见分类】

比较常见的是无头单向非循环链表和带头双向循环链表。

3.单链表的实现

3.1 新节点创建

//创建一个新节点SListNode* BuySLTNode(SLDateType x){SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));if(newNode == NULL){perror("malloc:");return;}newNode->data = x;newNode=>next = NULL;return newNode;}

3.2 单链表头插

//头插void SListPushFront(SListNode** pphead,SLDateType x){assert(pphead);SListNode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;}

3.3 单链表头删

//头删void SListPopFront(SListNode** pphead){assert(pphead);assert(*pphead);SListNode* cur = *pphead;*pphead = (*pphead)->next;free(cur);cur = NULL;}

3.4 单链表尾插

//尾插void SLTPushBack(SListNode**pphead, SLDateType x){assert(pphead);SListNode* newnode = BuySLTNode(x);//1.链表为空//2.链表不为空if (*pphead == NULL){*pphead = newnode;        //不需要让newnode->next=NULL,在BuySLTNode中我们就已经进行过这个操作了}else{//找到链表的尾巴tailSListNode* tail = *pphead;while (tail->next){tail = tail->next;}tail->next = newnode;}}

3.5 单链表尾删

//尾删void SListPopBack(SListNode**pphead){assert(pphead);assert(*pphead);//1.链表只有一个元素//2.链表有两个及两个以上的元素if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SListNode* tail = *pphead;SListNode* prev = NULL;//找尾while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);prev->next = NULL;tail = NULL;·       另一种方法//SListNode* tail = *pphead;//while (tail->next->next)//{//tail = tail->next;//}//free(tail->next);//tail->next = NULL;}}

3.6 链表销毁

//销毁void SLTDestory(SListNode** pphead){assert(pphead);SListNode* cur = *pphead;while (cur){SListNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;}

4. 代码总结

4.1 SLT.h

#pragma once#include<stdio.h>#include<assert.h>#include<stdlib.h>typedef int SLTDateType;typedef struct SLTNode{SLTDateType data;struct SLTNode* next;}SLTNode;//创建一个结点SLTNode* BuyListNode(SLTDateType x);//销毁单链表void SLTDestory(SLTNode** pphead);//单链表头插void SLTPushFront(SLTNode** pphead, SLTDateType x);//单链表尾插void SLTPushBack(SLTNode** pphead, SLTDateType x);//单链表头删void SLTPopFront(SLTNode** pphead);//单链表尾删void SLTPopBack(SLTNode** pphead);//单链表结点查找SLTNode* SLTNodeFind(SLTNode* phead, SLTDateType x);//单链表结点删除(删除pos位置的结点)void SLTErase(SLTNode** pphead, SLTNode* pos);//单链表结点插入(在pos之前插入)void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);// 单链表结点插入(在pos之后插入)void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x);// 单链表结点修改void SLTModify(SLTNode* phead, SLTNode* pos, SLTDateType x);//打印单链表void PrintSLT(SLTNode * phead);

4.2 SLT.c

#include"SLT.h" //建立一个新的结点//这是链表的缺点：经常需要使用malloc为newnode开辟空间SLTNode* BuyListNode(SLTDateType x){//为什么要用malloc，是因为，如果在BuyListNode函数中SLTNode newnode，出了这个函数，newnode就被销毁了，//用malloc开辟空间，只要我们不主动释放这个空间，这个空间的数据一直存在，SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//static SLTNode newnode；if (newnode == NULL){perror("malloc:");exit(0);}newnode->data = x;newnode->next = NULL;return newnode;} //头插void SLTPushFront(SLTNode** pphead, SLTDateType x){assert(pphead);//phead可能为NULL，但是pphead指向phead，不可能为空SLTNode* newnode = BuyListNode(x);//这里可不是newnode->next = (*pphead)->next;newnode->next = *pphead;*pphead = newnode;}  //尾插//尾插特别容易出错，当链表中没有数据，即phead=NULL时，尾插就相当于头插了，此时需要改变phead的值void SLTPushBack(SLTNode** pphead, SLTDateType x){assert(pphead);SLTNode* newnode = BuyListNode(x);//1、空//2、非空if (*pphead == NULL){*pphead = newnode;//newnode->next = NULL;这一步是不需要的，newnode在建立的时候就默认newnode->next=NULL；}else{SLTNode* cur = *pphead;//这是单向链表的缺点，需要去找尾while (cur->next != NULL){cur = cur->next;}cur->next = newnode;}} //头删void SLTPopFront(SLTNode** pphead){assert(pphead);//温柔的检查if (*pphead == NULL)return;//暴力的检查assert(*pphead);SLTNode* head = *pphead;*pphead = (*pphead)->next;free(head);head = NULL;} //尾删void SLTPopBack(SLTNode** pphead){assert(pphead);assert(*pphead);//1、一个结点//2、两个结点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* cur = *pphead;while (cur->next->next){cur = cur->next;}free(cur->next);cur->next = NULL;}}//打印单向链表void PrintSLT(SLTNode* phead){SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL");printf("\n");} //单链表查找某个结点SLTNode* SLTNodeFind(SLTNode* phead, SLTDateType x){SLTNode* find = phead;//别忘记分析找不到结点的情况while (find){if (find->data == x){return find;}find = find->next;}return NULL;} //删除pos位置的结点void SLTErase(SLTNode** pphead, SLTNode* pos){assert(pphead);assert(pos);if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;//如果prev->next已经为空了，说明链表已经查完了，还没有查到pos//证明pos传入有误assert(prev->next);}prev->next = pos->next;free(pos);//pos = NULL;这个没必要，改变不了pos}}//单链表结点前插//一般插入结点都是在pos之前插入，但单链表在实现前插是比较困难的void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x){assert(pphead);//头插if (pos == *pphead){SLTPushFront(pphead, x);}//非头插else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;assert(prev->next);}SLTNode* newnode = BuyListNode(x);prev->next = newnode;newnode->next = pos;}}//单链表结点后插void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x){SLTNode* cur = *pphead;while (cur != pos){cur = cur->next;//防止pos传错了assert(cur);}SLTNode* newnode = BuyListNode(x);newnode->next = pos->next;pos->next = newnode;} // 单链表结点修改void SLTModify(SLTNode* phead, SLTNode* pos, SLTDateType x){SLTNode* cur = phead;while (cur != pos){cur = cur->next;assert(cur);}pos->data = x;}//销毁链表void SLTDestory(SLTNode** pphead){assert(pphead);SLTNode* cur = *pphead;//比cur->next!=NULL更好一些while (cur){SLTNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;}

4.3 test.c

#include"SLT.h"void test1(){SLTNode* plist = NULL;SLTPushFront(&plist, 0);SLTPushFront(&plist, -1);SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);PrintSLT(plist);SLTPopFront(&plist);SLTPopBack(&plist);PrintSLT(plist);SLTNode* pos = SLTNodeFind(plist, 0);SLTInsert(&plist, pos, -2);PrintSLT(plist);SLTInsert(&plist, pos, -1);PrintSLT(plist);SLTInsertBack(&plist, pos, 3);PrintSLT(plist);SLTModify(plist, pos, 4);PrintSLT(plist);}int main(){test1();}

后言

以上就是小编对单链表的一些初步认识。
如果觉得小编讲的还可以，还请一键三连。互三必回！
持续更新中~，下周见！

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/zhengce/2024-04-29/163595.html，文章来源：网络cs，作者：峨乐，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！