0


数据结构之单链表

前言:上一篇文章我们了解到顺序表,这一次来看另一种线性表-------单链表。

1. 单链表的概念

单链表,想必很多人会感到陌生吧。那么,到底什么是单链表呢?先了解清楚单链表的概念及特性,才能够更好的实现单链表。

所谓链表是一种物理存储结构上非连续,非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的

单链表就像火车车厢一样,每节车厢都通过链条进行链接。

在这里插入图片描述

那么,在链表里每节“车厢”是怎样的呢?

在这里插入图片描述

不过,在数据结构里“车厢”有一个专属名词-----节点(结点)。与顺序表不同的是,链表里的每节车厢都是独立申请下来的空间,我们称之为节点。

节点主要由两部分组成,当前节点要保存的数据和保存下一个节点的地址

链表的性质

1.链式结构在逻辑上是连续的,在物理结构上不一定是连续的

2.节点一般是从堆上申请的

3.从堆上申请出来的空间可能连续也可能不连续

现在我们已经了解到了链表的结构,接下来要该如何设计链表呢?**

在节点里需要保存数据及保存下一个节点的地址。这是两个不同的数据类型,因此使用结构体,也便于代码的可读性与可维护性

**。

2. 单链表的实现

2.1 单链表的定义

//链表存储数据类型typedefint SLDataType;//单链表的定义typedefstructSinglyLinkedList{
    SLDataType data;//保存的数据structSinglyLinkedList* next;//存储下一个节点的地址}SList;

2.2 单链表的接口

//打印单链表voidDisplaySList(SList* phead);//尾插voidSListPushBack(SList** pphead, SLDataType x);//尾删voidSListPopBack(SList** pphead);//头插voidSListPushFront(SList** pphead, SLDataType x);//头删voidSListPopFront(SList** pphead);//单链表查找
SList*SListFind(SList* phead, SLDataType x);//从指定位置之后开始插入数据voidSListInsertAfter(SList** pphead, SList* pos, SLDataType x);//从指定位置之前插入数据voidSListInsert(SList** pphead, SList* pos, SLDataType x);//从指定位置删除数据voidSListErase(SList** pphead, SList* pos);//销毁链表voidSListDestroy(SList** pphead);

2.2.1 单链表尾插

//尾插voidSListPushBack(SList** pphead, SLDataType x){assert(pphead);//开辟一个节点大小的空间,开辟失败就退出程序。/*SList* newnode = (SList*)malloc(sizeof(SList));
    if (NULL == newnode)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;*///SListBuyNewNode是一个创建新节点的函数,不仅仅在尾插//中需要创建节点,在头插中也需要。因此为了避免代码冗余以//及代码的可读性与可维护性,将创建新节点的功能封装成一个//函数来实现。
    SList* newnode =SListBuyNewNode(pphead, x);//单链表为空的情况if(NULL==*pphead){//plist为空,让plist指向newnode,指向链表的头结点*pphead = newnode;}else{
        SList* tail =*pphead;//找尾节点while(NULL!= tail->next){
            tail = tail->next;}//连接新的节点
        tail->next = newnode;}}

在这里插入图片描述

尾插数据需要一个节点大小的空间,用来存储数据及保存下一个节点的地址。因此首先申请一块节点大小的空间

接下来又分两种情况:

1.**

plist指向空,需要让plist指向链表头结点

**。

2.**

plist不指向空,新申请的结点直接连接在链表尾节点的后面

**。

在这里插入图片描述

assert(pphead);
pphead保存的是一级指针变量plist的地址,所以pphead一定不为
空。对pphead进行断言,是为了防止参数传输错误。

还有一个问题,不知道大家发现没有。这里为什么要用二级指针呢?答案很简单。**

plist是一个结构体指针,在尾插中有可能要改变plist,因此要用二级指针

**。这涉及到了实参与形参的关系。

2.2.2 创建新节点

//创建新节点
SList*SListBuyNewNode(SList** pphead,SLDataType x){
    SList* newnode =(SList*)malloc(sizeof(SList));if(NULL== newnode){printf("malloc fail\n");exit(-1);}
    newnode->data = x;
    newnode->next =NULL;return newnode;}

2.2.3 打印单链表

//打印单链表//这里也可以用二级指针来接收,保持代码风格的一致性voidDisplaySList(SList* phead){
    SList* cur = phead;while(NULL!= cur){printf("%d->", cur->data);
        cur = cur->next;}printf("NULL\n");}
SList* cur=phead,此时cur指向了链表的头结点,只要cur不等于
NULL,就打印链表节点里的数据。然后更新cur,指向下一个节点。

2.2.4 单链表尾删

//尾删voidSListPopBack(SList** pphead){assert(pphead);//单链表为空的情况assert(*pphead);//单链表至少有一个节点if(NULL==(*pphead)->next){free(*pphead);*pphead =NULL;}else{
        SList* tail =*pphead;
        SList* prev =NULL;//找尾节点while(NULL!= tail->next){
            prev = tail;
            tail = tail->next;}
        prev->next =NULL;//释放尾节点的空间free(tail);
        tail =NULL;}}

这里包含了3种情况:

1.**

plist指向空,代表没有链表(没有数据可以删除)

**

2.**

有多个节点

**

3.**

只有一个节点

**

画图分析:

在这里插入图片描述


在这里插入图片描述

1.尾删节点首先将尾节点的空间还给操作系统,然后再让尾节点的前
一个节点指向空(防止野指针的出现)
2.一直尾删,直到剩下一个节点。这个时候再尾删就要改变plist指针
了,因此尾删也需要二级指针
3.在尾删节点的时候,需要找到尾节点才能删除,由于单链表具有单
向性,因此还需要一个前驱指针,用来记录尾节点的前一个节点。

2.2.5 单链表头插

//头插voidSListPushFront(SList** pphead, SLDataType x){assert(pphead);//创建新节点
    SList* newnode =SListBuyNewNode(pphead, x);//新节点成为链表的头结点
    newnode->next =*pphead;//plist指向链表的头结点*pphead = newnode;}

在这里插入图片描述

注意:**

一定要先让新节点的next保存当前plist的值,再更新plist,指向新的头结点

**。

2.2.6 单链表头删

//头删voidSListPopFront(SList** pphead){assert(pphead);//单链表为空的情况assert(*pphead);//记录当前头结点
    SList* cur =*pphead;//更新plist*pphead =(*pphead)->next;//释放头结点的空间free(cur);
    cur =NULL;}

在这里插入图片描述

注意:
1.先让plist指向当前头结点的下一个节点,如果先删除当前头
结点,就找不到下一个节点了。
2.释放当前头结点的空间。
2.plist为空,说明链表为空,没有数据删除。

2.2.7 单链表查找

//单链表查找
SList*SListFind(SList* phead, SLDataType x){//单链表为空不查找assert(phead);

    SList* cur = phead;while(NULL!= cur){if(cur->data == x){return cur;}
        cur = cur->next;}returnNULL;}

从头结点开始遍历进行查找,找到了就返回该节点的地址,否则返回NULL

2.2.8 从指定位置之后开始插入数据

//从指定位置之后开始插入数据voidSListInsertAfter(SList** pphead, SList* pos, SLDataType x){assert(pphead);//创建新节点
    SList* newnode =SListBuyNewNode(pphead, x);//链表为空if(NULL==*pphead){*pphead = newnode;}else{
        SList* cur =*pphead;//找pos位置while(NULL!= cur){if(cur == pos){
                newnode->next = cur->next;
                cur->next = newnode;}
            cur = cur->next;}}}

在这里插入图片描述

从头结点开始遍历找pos位置,找到pos位置将新节点插入进去。

注意:**

让新节点的next保存pos位置下一个节点的地址,再让pos位置的节点的next保存新节点的地址

**。

2.2.9 从指定位置之前插入数据

//从指定位置之前插入数据voidSListInsert(SList** pphead, SList* pos, SLDataType x){assert(pphead);//创建新节点
    SList* newnode =SListBuyNewNode(pphead, x);if(NULL==*pphead){*pphead = newnode;}else{
        SList* cur =*pphead;//记录pos位置前一个节点
        SList* prev =NULL;while(NULL!= cur){if(cur == pos){
                newnode->next = prev->next;
                prev->next = newnode;}
            prev = cur;
            cur = cur->next;}}}

在这里插入图片描述

**

从头结点开始遍历找pos位置,找到pos位置,让pos位置的前一个节点的next保存新节点的地址,新节点的next保存pos位置节点的地址

**。

2.2.10 从指定位置删除数据

//从指定位置删除数据voidSListErase(SList** pphead, SList* pos){assert(pphead);//单链表为空assert(*pphead);

    SList* cur =*pphead;//找pos位置while(NULL!= cur->next){if(cur->next == pos){
            cur->next = pos->next;free(pos);
            pos =NULL;}
        cur = cur->next;}}

在这里插入图片描述

**

单链表不能为空,为空说明没有数据可以删除。找到pos位置,让pos位置的前一个节点的next指向pos位置节点的下一个节点,然后再释放掉pos位置的节点

**。

2.2.11 销毁链表

//销毁链表voidSListDestroy(SList** pphead){assert(pphead);
    SList* cur =*pphead;while(NULL!= cur){
        SList* prev = cur;
        cur = cur->next;free(prev);
        prev =NULL;}*pphead=NULL;}
从头结点开始遍历,先让cur指向头结点的下一个节点,再释放掉当前
的头结点。最后再让*pphead=NULL。在循环过程中,*pphead的指
向一直没有发生改变,销毁链表时,也要让plist指向空,防止出现野
指针。

3. 单链表完整代码的实现

SList.h的实现

#pragmaonce#include<stdio.h>#include<assert.h>#include<stdlib.h>typedefint SLDataType;typedefstructSinglyLinkedList{
    SLDataType data;structSinglyLinkedList* next;//存储下一个节点的地址}SList;//打印单链表voidDisplaySList(SList* phead);//尾插voidSListPushBack(SList** pphead, SLDataType x);//尾删voidSListPopBack(SList** pphead);//头插voidSListPushFront(SList** pphead, SLDataType x);//头删voidSListPopFront(SList** pphead);//单链表查找
SList*SListFind(SList* phead, SLDataType x);//从指定位置之后开始插入数据voidSListInsertAfter(SList** pphead, SList* pos, SLDataType x);//从指定位置之前插入数据voidSListInsert(SList** pphead, SList* pos, SLDataType x);//从指定位置删除数据voidSListErase(SList** pphead, SList* pos);//销毁链表voidSListDestroy(SList** pphead);

SList.c实现

#define_CRT_SECURE_NO_WARNINGS#include"SList.h"//打印单链表voidDisplaySList(SList* phead){
    SList* cur = phead;while(NULL!= cur){printf("%d->", cur->data);
        cur = cur->next;}printf("NULL\n");}//创建新节点
SList*SListBuyNewNode(SList** pphead,SLDataType x){
    SList* newnode =(SList*)malloc(sizeof(SList));if(NULL== newnode){printf("malloc fail\n");exit(-1);}
    newnode->data = x;
    newnode->next =NULL;return newnode;}//尾插voidSListPushBack(SList** pphead, SLDataType x){assert(pphead);/*SList* newnode = (SList*)malloc(sizeof(SList));
    if (NULL == newnode)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;*/
    SList* newnode =SListBuyNewNode(pphead, x);//单链表为空的情况if(NULL==*pphead){*pphead = newnode;}else{
        SList* tail =*pphead;while(NULL!= tail->next){
            tail = tail->next;}
        tail->next = newnode;}}//尾删voidSListPopBack(SList** pphead){assert(pphead);//单链表为空的情况assert(*pphead);//单链表至少有一个节点if(NULL==(*pphead)->next){free(*pphead);*pphead =NULL;}else{
        SList* tail =*pphead;
        SList* prev =NULL;while(NULL!= tail->next){
            prev = tail;
            tail = tail->next;}
        prev->next =NULL;free(tail);
        tail =NULL;}}//头插voidSListPushFront(SList** pphead, SLDataType x){assert(pphead);/*SList* newnode = (SList*)malloc(sizeof(SList));
    if (NULL == newnode)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;*/
    SList* newnode =SListBuyNewNode(pphead, x);//至少有一个节点/*if (NULL == *pphead)
    {
        *pphead = newnode;
    }
    else
    {
        newnode->next = *pphead;
        *pphead = newnode;
    }*/

    newnode->next =*pphead;*pphead = newnode;}//头删voidSListPopFront(SList** pphead){assert(pphead);//单链表为空的情况assert(*pphead);

    SList* cur =*pphead;*pphead =(*pphead)->next;free(cur);
    cur =NULL;}//单链表查找
SList*SListFind(SList* phead, SLDataType x){//单链表为空不查找assert(phead);

    SList* cur = phead;while(NULL!= cur){if(cur->data == x){return cur;}
        cur = cur->next;}returnNULL;}//从指定位置之后开始插入数据voidSListInsertAfter(SList** pphead, SList* pos, SLDataType x){assert(pphead);
    SList* newnode =SListBuyNewNode(pphead, x);if(NULL==*pphead){*pphead = newnode;}else{
        SList* cur =*pphead;while(NULL!= cur){if(cur == pos){
                newnode->next = cur->next;
                cur->next = newnode;}
            cur = cur->next;}}}//从指定位置之前插入数据voidSListInsert(SList** pphead, SList* pos, SLDataType x){assert(pphead);
    SList* newnode =SListBuyNewNode(pphead, x);if(NULL==*pphead){*pphead = newnode;}else{
        SList* cur =*pphead;
        SList* prev =NULL;while(NULL!= cur){if(cur == pos){
                newnode->next = prev->next;
                prev->next = newnode;}
            prev = cur;
            cur = cur->next;}}}//从指定位置删除数据voidSListErase(SList** pphead, SList* pos){assert(pphead);//单链表为空assert(*pphead);

    SList* cur =*pphead;while(NULL!= cur->next){if(cur->next == pos){
            cur->next = pos->next;free(pos);
            pos =NULL;}
        cur = cur->next;}}//销毁链表voidSListDestroy(SList** pphead){assert(pphead);
    SList* cur =*pphead;while(NULL!= cur){
        SList* prev = cur;
        cur = cur->next;free(prev);
        prev =NULL;}*pphead=NULL;}

test.c的实现

#define_CRT_SECURE_NO_WARNINGS#include"SList.h"voidTestSList1(){
    SList* plist =NULL;SListPushBack(&plist,1);SListPushBack(&plist,2);SListPushBack(&plist,3);SListPushBack(&plist,4);SListPushBack(&plist,5);DisplaySList(plist);SListPopBack(&plist);SListPopBack(&plist);SListPopBack(&plist);SListPopBack(&plist);SListPopBack(&plist);DisplaySList(plist);}voidTestSList2(){
    SList* plist =NULL;SListPushFront(&plist,10);SListPushFront(&plist,20);SListPushFront(&plist,30);SListPushFront(&plist,40);DisplaySList(plist);SListPopFront(&plist);DisplaySList(plist);

    SList* pos =SListFind(plist,50);if(NULL!= pos){printf("%d\n", pos->data);}else{printf("找不到\n");}}voidTestSList3(){
    SList* plist =NULL;SListInsertAfter(&plist,NULL,10);DisplaySList(plist);SListPushBack(&plist,1);SListPushBack(&plist,2);SListPushBack(&plist,3);SListPushBack(&plist,4);SListPushBack(&plist,5);

    SList* pos =SListFind(plist,4);SListInsertAfter(&plist, pos,20);DisplaySList(plist);

    pos =SListFind(plist,2);SListInsert(&plist, pos,30);DisplaySList(plist);

    pos =SListFind(plist,3);SListErase(&plist, pos);DisplaySList(plist);SListDestroy(&plist);}intmain(){//TestSList1();//TestSList2();TestSList3();return0;}

本文转载自: https://blog.csdn.net/2402_84532723/article/details/143448727
版权归原作者 CodePracticer 所有, 如有侵权,请联系我们删除。

“数据结构之单链表”的评论:

还没有评论