导航：首页 > 开发技术 >

C语言怎么实现单链表

发表于：2024-11-23 作者：千家信息网编辑

千家信息网最后更新 2024年11月23日，这篇文章主要介绍"C语言怎么实现单链表"，在日常操作中，相信很多人在C语言怎么实现单链表问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答"C语言怎么实现单链表"的疑惑有所帮

千家信息网最后更新 2024年11月23日C语言怎么实现单链表

这篇文章主要介绍"C语言怎么实现单链表"，在日常操作中，相信很多人在C语言怎么实现单链表问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答"C语言怎么实现单链表"的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

一、单链表与顺序表的区别：

一、顺序表：

1、内存中地址连续

2、长度可以实时变化

3、不支持随机查找

4、适用于访问大量元素的，而少量需要增添/删除的元素的程序

5、中间插入或者删除比较方便，内存命中率较高

二、链表

1、内存中地址不连续（逻辑上连续，物理上不连续）

2、长度可以实时变化（避免浪费空间）

3、不支持随机查找，查找的时间复杂度为o(1),

4、适用于访问大量元素的，对访问元素无要求的程序

5、中间插入或者删除比较方便，效率高

二、关于链表中的一些函数接口的作用及实现

1、创建接口，开辟空间

2、尾插尾删

3、头插头删

4、查找并修改

5、中插中删

ps：我看了许多的单链表文章，在插删的接口实现上大多数是往前进行插删，这里写的则是往后进行插删

1、头文件里的结构体和函数声明等等

#pragma once#define _CRT_SECURE_NO_WARNINGS#include#include#include  typedef int SListDataType;//节点typedef struct SListNode{        SListDataType data;        struct SListNode* next;}SListNode; //struct SList//{//      SListNode* head;//      SListNode* tail;//}; //尾插尾删void SListPushBack(SListNode** pphead, SListDataType x);void SListPopBack(SListNode** pphead); //头插头删void SListPushFront(SListNode**  pphead, SListDataType x);void SListPopFront(SListNode** pphaed); void SListPrint(SListNode* phead);//查找并修改SListNode* SListFind(SListNode* phead, SListDataType x);//中插中删void SListInserAfter(SListNode**pphead,SListNode* pos, SListDataType x);void SListEraseAfter(SListNode* pos); //从头到尾打印链表void PrintTailToHead(SListNode* pList);

2、创建接口空间

//开辟的下一个空间SListNode* BuySListNode(SListDataType x){        SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));        if (newNode == NULL)        {                printf("申请结点失败\n");                exit(-1);        }        newNode->data = x;        newNode->next = NULL;        return newNode; }

3.尾插尾删

//尾插void SListPushBack(SListNode** pphead, SListDataType x){        SListNode* newNode = BuySListNode(x);//我们指向头指针的那个结点是**pphead，*pphead就是头指针的地址        //如果头指针的地址为空，我们就把新开辟的这个空间指针（已经传入值）再赋给头指针，也就是下面的这个if循环        if (*pphead == NULL)        {                *pphead = newNode;        }        else        {                //找尾巴，判断尾巴是不是空地址,这个函数实现的是尾插，我们找到尾巴后，如果尾巴是空地址，我们将插入的newNode赋给尾巴，此时                //实现了尾插，在下面的代码中，我们首先把头指针当成尾巴，从头指针开始依次往后找，如果下一个不是空指针，我们就令                //tail=tail->next,此时指向下一个结点，进入循环继续判断，当找到后，我们再令尾巴=newNode,在上面我们也判断了头指针为空的情况                SListNode* tail = *pphead;                while (tail->next!= NULL)                {                        tail = tail -> next;                }                tail->next = newNode;        }}void SListPopBack(SListNode** pphead){        //1、空        //2、一个结点        //3、一个以上        if (*pphead == NULL)        {                return;        }        else if ((*pphead)->next == NULL)        {                free(*pphead);                *pphead = NULL;        }        else        {                SListNode* prev = NULL;                SListNode* tail = *pphead;                while (tail->next != NULL)                {                        prev = tail;                        tail = tail->next;                 }                free(tail);                //tail = NULL;//这个无所谓，因为我们释放后，出了这个作用域，tail和prev都被销毁，没人能拿到，所以不会被再找到                prev->next = NULL;         }}

4、头插头删

//头插头删void SListPushFront(SListNode** pphead, SListDataType x){        SListNode* newnode = BuySListNode(x);        newnode->next = *pphead;        *pphead = newnode;}void SListPopFront(SListNode** pphead){        //1、空        //2、一个结点+3、一个以上                if (*pphead == NULL)        {                return;        }        //(*phead)->next:*和>都是解引用，同一优先级，我们需要给*pphead带括号，(*pphead)->next才是下一个结点                else{                //我们头删也会遇到情况，我们删除第一个的话，第一个里面还存有第二个结点的地址，我们必须在删除前，保存第二个结点的地址                SListNode* next = (*pphead)->next;                free(*pphead);//通过调试我们发现：free前后，*pphead的地址不变，但是*pphead里的值被置为随机值，free不仅仅把这块空间还给操作系统                  //而且还把这块空间存的值和地址都置为随机值                *pphead = next;        } }

5、单链表查找

//单链表查找SListNode* SListFind(SListNode* phead, SListDataType x){        SListNode* cur = phead;        while (cur)        {                if (cur->data == x)                {                        return cur;                }                cur = cur->next;        }        return NULL;}

6、中间插入（在pos后面进行插入）

void SListInserAfter(SListNode** pphead,SListNode* pos, SListDataType x){        assert(pos && pphead);        if (*pphead == pos)        {                SListPushFront(pphead, x);        }        else        {                SListNode* newnode = BuySListNode(x);                SListNode* tmp = *pphead;                while (tmp->next != pos)                {                        tmp = tmp->next;                }                tmp->next = pos;                pos->next = newnode;         }        }

7、中间删除（在pos后面进行删除）

void SListEraseAfter(SListNode* pos){        //删除pos后面的        assert(pos);        if (pos->next)        {                //pos->next=pos->next->next//不推荐                SListNode* next = pos->next;                SListNode* nextnext = next->next;                pos->next = nextnext;                free(next);        }}

8、单独打印链表和从头到尾打印链表

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

9、test.c

#include"SList.h" TestSList1(){         SListNode* pList = NULL;//这个结构体指针指向开辟的空间,头指针指向链表的开头        SListPushBack(&pList, 1);        SListPushBack(&pList, 2);        SListPushBack(&pList, 3);        SListPushBack(&pList, 4);        SListPrint(pList);         SListPopBack(&pList);        SListPopBack(&pList);        SListPopBack(&pList);        SListPopBack(&pList);        SListPopBack(&pList);        SListPrint(pList);         SListPushFront(&pList, 1);        SListPushFront(&pList, 2);        SListPushFront(&pList, 6);        SListPushFront(&pList, 4);        SListPushFront(&pList, 5);        SListPrint(pList);        SListPopFront(&pList);        SListPopFront(&pList);        SListPopFront(&pList);        SListPopFront(&pList);        SListPopFront(&pList);        SListPopFront(&pList);        SListPrint(pList);  } TestSList2(){        SListNode* pos1;        SListNode* pList = NULL;//这个结构体指针指向开辟的空间,头指针指向链表的开头        SListPushBack(&pList, 1);        SListPushBack(&pList, 2);        SListPushBack(&pList, 3);        SListPushBack(&pList, 4);        SListPrint(pList);        SListNode* pos = SListFind(pList, 3);        if (pos)        {                pos->data = 30;//这里将cur-data改为pos->data,然后再将pos-data原来的值改为30        }        SListPrint(pList);        pos1 = SListFind(pList, 30);//我们先去找到这个pos1的位置，然后再去插入        SListInserAfter(&pList,pos1,50);//函数传参要对应起来，我们用指针传用指针接收，不能在pos1位置直接写个数字        SListPrint(pList);        SListEraseAfter(pos1);//pList指向第一个结点，pList->next指向第二个结点，那么我们删除的是目标节点后面        SListPrint(pList);        //PrintTailToHead(&pList);}int main(){        TestSList1();        TestSList2();        return 0;         }

到此，关于"C语言怎么实现单链表"的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注网站，小编会继续努力为大家带来更多实用的文章！

很赞哦！