C语言中数据结构——单链表

文章列表

C语言中数据结构——单链表

🐶博主主页：@ᰔᩚ. 一怀明月ꦿ

❤️‍🔥专栏系列：线性代数，C初学者入门训练，题解C，C的使用文章，「初学」C++

🔥座右铭：“不要等到什么都没有了，才下定决心去做”

🚀🚀🚀大家觉不错的话，就恳求大家点点关注，点点小爱心，指点指点🚀🚀🚀

🐰单链表

🏡单链表的定义

🏡单链表的打印

🏡单链表的创建节点

🏡单链表的头插

🏡单链表的尾插

🏡单链表的尾删

🏡单链表的头删

🏡单链表的查找

🏡单链表的改动

🏡单链表的元素个数

🏡单链表的任意位置插入元素

单链表的任意位置删除元素

🏡单链表的销毁

🏡单链表中的源码

🌸main文件

🌸头文件test.h

🌸test.c文件

🐰单链表

🏡单链表的定义

typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;//next存放的下一个节点的地址
}SLT;

🏡单链表的打印

依次打印链表中的数据

void SLTprintf(SLT* phead)
{SLT* cur=phead;while(cur!=NULL){printf("%d ",cur->data);cur=cur->next;}printf("\\n");
}

🏡单链表的创建节点

动态开辟一个空间，然后返回这个空间的地址，即动态开辟的节点

SLT* Buylistnode(int x)
{SLT* newnode=(SLT*)malloc(sizeof(SLT));if(newnode==NULL){perror("malloc fail");return 0;}newnode->data=x;newnode->next=NULL;return newnode;
}

🏡单链表的头插

复用了动态创建节点

void SLTPushFront(SLT** pphead,SLTDataType x)
{SLT* newnode= Buylistnode(x);newnode->next=*pphead;*pphead=newnode;
}

🏡单链表的尾插

注意一个节点和多个节点时

void SLTPushBack(SLT** pphead,SLTDataType x)
{SLT* newnode=Buylistnode(x);if(*pphead==NULL)//当为空链表时{*pphead=newnode;}else{SLT* tail=*pphead;while(tail->next){tail=tail->next;}tail->next=newnode;}
}

🏡单链表的尾删

这两种方法的本质都是找到倒数第二个节点

第一种尾删的方法

注意一个节点和多个节点时


void SLTPopBack(SLT** pphead)
{assert(*pphead);SLT* prev=NULL;SLT* tail=*pphead;if(tail->next==NULL){free(tail);*pphead=NULL;}else{while(tail->next){prev=tail;tail=tail->next;}free(tail);prev->next=NULL;}
}

第二种尾删的方法

注意一个节点和多个节点时

void SLTPopBack(SLT** pphead)
{assert(*pphead);SLT* tail=*pphead;if(tail->next==NULL)//只有一个节点{free(tail);*pphead=NULL;}else//有多个节点{while(tail->next->next)//这也是找到倒数第二个节点{tail=tail->next;}free(tail->next);tail->next=NULL;}
}

🏡单链表的头删

注意一个节点和多个节点时

void SLTPopFront(SLT** pphead)
{assert(*pphead);SLT* tail=*pphead;if(tail->next==NULL)//一个节点{free(tail);*pphead=NULL;}else//多个节点{tail=tail->next;free(*pphead);*pphead=tail;}
}

🏡单链表的查找

（找到了，就返回所在的位置，没找到返回-1）

int SLTFind(SLT** pphead,SLTDataType x)
{assert(*pphead);SLT* try_b=*pphead;int Count=1;while(try_b->next){if(try_b->data==x){return Count;}Count++;try_b=try_b->next;}return  -1;
}

🏡单链表的改动

需要给出改动的位置以及要改动的值

void SLTChange(SLT** pphead,int pos,SLTDataType x)
{assert(*pphead);int Count=Totalsize(pphead);assert(pos<=Count);SLT* tail=*pphead;while(pos--){tail=tail->next;}tail->data=x;
}

🏡单链表的元素个数

计算链表的元素个数，然后返回个数

int Totalsize(SLT** pphead)
{SLT* tail=*pphead;int Count=0;while(tail){tail=tail->next;Count++;}return Count;
}

🏡单链表的任意位置插入元素

需要给出插入的位置以及要插入的值（说明一下，这里是插入元素的位置的后面），插入的位置一定要合法

void SLTInsertAfter(SLT** pphead,int pos, SLTDataType x)
{assert(pos<=Count);if((*pphead)==NULL){SLTPushFront(pphead, x);}else{SLT* prev=NULL;SLT* tail=*pphead;while(pos--){prev=tail;tail=tail->next;}SLT* newnode=Buylistnode(x);prev->next=newnode;newnode->next=tail;}
}

单链表的任意位置删除元素

删除的位置一定要合法

void SLTEraseAfter(SLT** pphead,int pos)
{assert(*pphead);assert(pos<=Count-1);if((*pphead)->next==NULL){SLTPopFront(pphead);}else{SLT* prev=NULL;SLT* taillater=NULL;SLT* tail=*pphead;while(pos--){prev=tail;tail=tail->next;}taillater=tail->next;free(tail);tail=NULL;prev->next=taillater;}
}

🏡单链表的销毁

void SLTDestroy(SLT** pphead)
{free(*pphead);*pphead=NULL;
}

🏡单链表中的源码

为方便调试单链表，这里没有使用了菜单

🌸main文件

#include"test.h"
void test1(void)
{SLT* plist=NULL;SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTprintf(plist);printf("\\n");SLTPushBack(&plist, 4);SLTPushBack(&plist, 3);SLTPushBack(&plist, 2);SLTPushBack(&plist, 1);SLTprintf(plist);
}
void test2(void)
{SLT* plist=NULL;SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPushBack(&plist, 4);SLTPushBack(&plist, 3);SLTPushBack(&plist, 2);SLTPushBack(&plist, 1);SLTprintf(plist);
//    SLTPopBack(&plist);
//    SLTPopBack(&plist);
//    SLTPopBack(&plist);
//    SLTPopBack(&plist);
//    SLTPopBack(&plist);
//    SLTPopBack(&plist);
//    SLTPopBack(&plist);
//    SLTprintf(plist);SLTPopFront(&plist);SLTPopFront(&plist);SLTPopFront(&plist);SLTPopFront(&plist);SLTPopFront(&plist);SLTPopFront(&plist);SLTPopFront(&plist);SLTPopFront(&plist);SLTprintf(plist);
}
void test3(void)
{SLT* plist=NULL;SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPushBack(&plist, 4);SLTPushBack(&plist, 3);SLTPushBack(&plist, 2);SLTPushBack(&plist, 1);SLTprintf(plist);int ret=SLTFind(&plist,4);printf("position is('-1'is not find)：%d\\n",ret);
}
void test4(void)
{SLT* plist=NULL;SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPushBack(&plist, 4);SLTPushBack(&plist, 3);SLTPushBack(&plist, 2);SLTPushBack(&plist, 1);SLTprintf(plist);SLTChange(&plist, 23, 100);SLTprintf(plist);
}
void test5(void)
{SLT* plist=NULL;SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPushBack(&plist, 4);SLTPushBack(&plist, 3);SLTPushBack(&plist, 2);SLTPushBack(&plist, 1);SLTprintf(plist);int ret=Totalsize(&plist);SLTPopFront(&plist);SLTPopFront(&plist);SLTPopFront(&plist);SLTPopFront(&plist);SLTPopFront(&plist);SLTPopFront(&plist);SLTPopFront(&plist);SLTPopFront(&plist);SLTprintf(plist);ret=Totalsize(&plist);printf("total is :%d\\n",ret);
}
void test6(void)
{SLT* plist=NULL;//   SLTPushFront(&plist, 1);
//    SLTPushFront(&plist, 2);
//    SLTPushFront(&plist, 3);
//    SLTPushFront(&plist, 4);
//    SLTPushBack(&plist, 4);
//    SLTPushBack(&plist, 3);
//    SLTPushBack(&plist, 2);
//    SLTPushBack(&plist, 1);SLTprintf(plist);SLTInsertAfter(&plist, 1, 100);SLTprintf(plist);
}
void test7(void)
{SLT* plist=NULL;SLTPushFront(&plist, 1);
//    SLTPushFront(&plist, 2);
//    SLTPushFront(&plist, 3);
//    SLTPushFront(&plist, 4);
//    SLTPushBack(&plist, 4);
//    SLTPushBack(&plist, 3);
//    SLTPushBack(&plist, 2);
//    SLTPushBack(&plist, 1);SLTprintf(plist);SLTEraseAfter(&plist, 1);SLTprintf(plist);
}
void test8(void)
{SLT* plist=NULL;SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPushBack(&plist, 4);SLTPushBack(&plist, 3);SLTPushBack(&plist, 2);SLTPushBack(&plist, 1);SLTprintf(plist);SLTDestroy(&plist);SLTprintf(plist);
}
int main()
{//test1();//完成头插尾插//test2();//完成尾删//test3();//查找//test4();//改动//test5();//判断链表有多少个元素// test6();//任意插入元素//test7();//任意删除元素test8();//销毁链表
}

🌸头文件test.h

#ifndef test_h
#define test_h
#include <stdio.h>
#endif /* test_h */
#include<stdlib.h>
#include<assert.h>typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;//next存放的下一个节点的地址
}SLT;//单链表的打印
void SLTprintf(SLT* phead);
//单链表的头插
void SLTPushFront(SLT** pphead,SLTDataType x);
//单链表的尾插
void SLTPushBack(SLT** pphead,SLTDataType x);
//单链表的尾删
void SLTPopBack(SLT** pphead);
//单链表的头删
void SLTPopFront(SLT** pphead);
//单链表的查找（找到了，就返回所在的位置，没找到返回-1）
int SLTFind(SLT** pphead,SLTDataType x);
//单链表的改动（改变给出位置的值）
void SLTChange(SLT** pphead,int pos,SLTDataType x);
//单链表的元素个数
int Totalsize(SLT** pphead);
//单链表的任意位置插入元素
void SLTInsertAfter(SLT** pphead,int pos, SLTDataType x);
//单链表的任意位置删除元素
void SLTEraseAfter(SLT** pphead,int pos);
//单链表的销毁
void SLTDestroy(SLT** pphead);

🌸test.c文件

#include "test.h"void SLTprintf(SLT* phead)
{SLT* cur=phead;while(cur!=NULL){printf("%d ",cur->data);cur=cur->next;}printf("\\n");
}
SLT* Buylistnode(int x)
{SLT* newnode=(SLT*)malloc(sizeof(SLT));if(newnode==NULL){perror("malloc fail");return 0;}newnode->data=x;newnode->next=NULL;return newnode;
}
void SLTPushFront(SLT** pphead,SLTDataType x)
{SLT* newnode= Buylistnode(x);newnode->next=*pphead;*pphead=newnode;
}
void SLTPushBack(SLT** pphead,SLTDataType x)
{SLT* newnode=Buylistnode(x);if(*pphead==NULL){*pphead=newnode;}else{SLT* tail=*pphead;while(tail->next){tail=tail->next;}tail->next=newnode;}
}
//这两种方法的本质都是找到倒数第二个节点
//第一种尾删的方法
void SLTPopBack(SLT** pphead)
{assert(*pphead);SLT* prev=NULL;SLT* tail=*pphead;if(tail->next==NULL){free(tail);*pphead=NULL;}else{while(tail->next){prev=tail;tail=tail->next;}free(tail);prev->next=NULL;}
}
//第二种尾删的方法
//void SLTPopBack(SLT** pphead)
//{
//    assert(*pphead);
//    SLT* tail=*pphead;
//    if(tail->next==NULL)//只有一个节点
//    {
//        free(tail);
//        *pphead=NULL;
//    }
//    else//有多个节点
//    {
//        while(tail->next->next)//这也是找到倒数第二个节点
//        {
//            tail=tail->next;
//        }
//        free(tail->next);
//        tail->next=NULL;
//    }
//}void SLTPopFront(SLT** pphead)
{assert(*pphead);SLT* tail=*pphead;if(tail->next==NULL)//一个节点{free(tail);*pphead=NULL;}else//多个节点{tail=tail->next;free(*pphead);*pphead=tail;}
}int SLTFind(SLT** pphead,SLTDataType x)
{assert(*pphead);SLT* try_b=*pphead;int Count=1;while(try_b->next){if(try_b->data==x){return Count;}Count++;try_b=try_b->next;}return  -1;
}
int Totalsize(SLT** pphead)
{SLT* tail=*pphead;int Count=0;while(tail){tail=tail->next;Count++;}return Count;
}
void SLTChange(SLT** pphead,int pos,SLTDataType x)
{assert(*pphead);int Count=Totalsize(pphead);assert(pos<=Count);SLT* tail=*pphead;while(pos--){tail=tail->next;}tail->data=x;
}void SLTInsertAfter(SLT** pphead,int pos, SLTDataType x)
{if((*pphead)==NULL){SLTPushFront(pphead, x);}else{SLT* prev=NULL;SLT* tail=*pphead;while(pos--){prev=tail;tail=tail->next;}SLT* newnode=Buylistnode(x);prev->next=newnode;newnode->next=tail;}
}void SLTEraseAfter(SLT** pphead,int pos)
{assert(*pphead);if((*pphead)->next==NULL){SLTPopFront(pphead);}else{SLT* prev=NULL;SLT* taillater=NULL;SLT* tail=*pphead;while(pos--){prev=tail;tail=tail->next;}taillater=tail->next;free(tail);tail=NULL;prev->next=taillater;}
}void SLTDestroy(SLT** pphead)
{free(*pphead);*pphead=NULL;
}

🌸🌸🌸如果大家还有不懂或者建议都可以发在评论区，我们共同探讨，共同学习，共同进步。谢谢大家！ 🌸🌸🌸

C语言中数据结构——单链表

🐰单链表

🏡单链表的定义

🏡单链表的打印

🏡单链表的创建节点

🏡单链表的头插

🏡单链表的尾插

🏡单链表的尾删

🏡单链表的头删

🏡单链表的查找

🏡单链表的改动

🏡单链表的元素个数

🏡单链表的任意位置插入元素

单链表的任意位置删除元素

🏡单链表的销毁

🏡单链表中的源码

🌸main文件

🌸头文件test.h

🌸test.c文件

相关问题

公告