seo建设网站,品牌建设网站,网站分类目录源码,郑州网站建设douyanet一、链表的概念
链表是一种物理存储结构上非连续、非顺序的存储结构#xff0c;也就是内存存储不是像顺序表那么连续存储#xff0c;而是以结点的形式一块一块存储在堆上的#xff08;用动态内存开辟#xff09;。
既然在内存上不是连续存储#xff0c;那我们如何将这一…一、链表的概念
链表是一种物理存储结构上非连续、非顺序的存储结构也就是内存存储不是像顺序表那么连续存储而是以结点的形式一块一块存储在堆上的用动态内存开辟。
既然在内存上不是连续存储那我们如何将这一块一块单独的空间链接起来呢
我们可以创建一个结构体充当我们的结点里面分别存放数据数据域和下一个结点的地址指针域这样我们就可以将一块一块单独的空间链接起来了。
而单链表顾名思义就是单向链接的链表效果如同下图 前言
在讲解单链表的各个接口前很有必要讲解以下单链表的物理内存到底是如何存储的先掌握这个接下来的讲解就会更容易理解
头结点指向的地址就是第一个结点的总地址
第一个结点的指针域指向的是第二个结点的总地址所以分为两个地址
一个是结点的总地址另一个是结点总地址里面的next指针存放的指针域的地址这个指针域的地址又指向了下一个结点的总地址。
看下面的图解内存存储的数据实际中是没有箭头的把箭头去掉才是内存中真正的存储模式 二、接口实现
对数据结构我们一般采用增删查改去实现。
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.htypedef int SLTDataType;typedef struct SListNode
{SLTDataType data;//数据域struct SListNode* next;//指针域
}SLTNode;void SLTPrint(SLTNode* phead);SLTNode* BuySListNode(SLTDataType x);void SLTPushBack(SLTNode** phead, SLTDataType x);void SLTPushFront(SLTNode** phead, SLTDataType x);void SLTPopFront(SLTNode** phead);void SLTPopBack(SLTNode** phead); 1、遍历单链表打印函数
一般需要创建一个临时变量去接收头结点
//遍历链表肯定需要头结点
void SLTPrint(SLTNode* phead)
{SLTNode* cur phead;//一般需要临时创建变量while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL);
}
2、创建单链表函数
SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc);exit(-1);}newnode-data x;newnode-next NULL;
}3、尾插
需要分情况讨论
如果链表本身是空直接改变头结点的指针直接指向新建的结点若不为空需要找到尾结点
TIP:何时用指针变量何时用二级指针
改变结构体本身需要结构体指针
改变结构体指针需要结构体指针指针二级指针并且要有解引用的操作
刚才第一种情况直接将头结点的指针改变成新指针的地址这种直接改变指针的模式就需要二级指针进行解引用才能达到目的。
void SLTPushBack(SLTNode** phead, SLTDataType x)
{//需要分情况讨论如果链表本身是空if (*phead NULL){SLTNode* newnode BuySListNode(x);//改变结构体本身需要结构体的指针//改变结构体指针需要结构体指针指针二级指针并且要有解引用的操作*phead newnode;}else{//先找尾结点SLTNode* newnode BuySListNode(x);SLTNode* tail *phead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}}
4、头插
头插肯定需要二级指针因为每次头插都要改变头指针指向的位置
//头插肯定需要二级指针因为每次头插都要改变头指针指向的位置
void SLTPushFront(SLTNode** phead, SLTDataType x)
{SLTNode* newnode BuySListNode(x);newnode-next *phead;*phead newnode;
}5、尾删
分三种情况
第一种是链表为空需要assert断言检查第二种链表中只有一个结点需要改变结构体指针因此函数传参也是需要二级指针第三种链表有多于一个的结点需要先找到尾结点。
void SLTPopBack(SLTNode** pphead)
{//分三种情况// 第一种就是链表为空assert(*pphead);// 第二种链表只有一个结点需要改变结构体指针if ((*pphead)-next NULL){free(*pphead);pphead NULL;}//第三种链表多于一个结点else{SLTNode* tail *pphead;SLTNode* tailprev NULL;while (tail-next ! NULL){tailprev tail;tail tail-next;}free(tail);tailprev-next NULL;//严格要求尾指针前一个的next指向null}
}6、头删
不需要分类讨论直接改变头节点的指针指向但是需要一个临时变量存储结点便于后面的操作
void SLTPopFront(SLTNode** phead)
{assert(*phead);SLTNode* newnode (*phead)-next;free(*phead);*phead newnode;
}
