您的位置:首页 > 教育 > 锐评 > 单链表<数据结构 C版>

单链表<数据结构 C版>

2024/10/14 11:08:44 来源:https://blog.csdn.net/2302_80803681/article/details/140506261  浏览:    关键词:单链表<数据结构 C版>

目录

概念

 链表的单个结点

 链表的打印操作

新结点的申请

尾部插入

头部插入

尾部删除

头部删除

查找

在指定位置之前插入数据

在任意位置之后插入数据

测试运行一下:

 删除pos结点

 删除pos之后结点

 销毁链表


概念

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

链表的每个结点有两个部分,分别是数据和指向下个结点的指针,每个链表的最后一个结点的下一个结点为NULL(不能对NULL解引用)。

放一张bit课件里的图,我觉得很形象:


 链表的单个结点

typedef int SLDataType;//重定义一下在链表内存放的数据类型,方便后期对类型进行统一修改//链表的单个结点
typedef struct SListNode {//Single List Node :链表结点SLDataType data;//存放的数据struct SListNode* next;//指向下一个结点的指针
}SLNode;//重定义名字方便后期使用

 链表的打印操作

//链表的打印操作
void SLPrint(SLNode* phead) {assert(phead);//不能传入空指针SLNode* pcur = phead;//pointer cursor:指针光标,不让头结点丢失(虽然不会改变头结点的指向)while (pcur) {//等同于pcur!=NULLprintf("%d->", pcur->data);//打印此结点的数据pcur = pcur->next;//使pcur指向下一个结点}printf("NULL\n");
}

新结点的申请

后面会涉及到新结点的插入,申请新结点可以封装成一个函数,避免代码冗余

//新结点的申请
SLNode* SLBuyNode(SLDataType x) {SLNode* node = (SLNode*)malloc(sizeof(SLNode));if (!node) {//返回值为空,申请失败(一般是空间不足了),直接退出perror("malloc fail");exit(1);}node->data = x;//将数据赋给datanode->next = NULL;//将下一个节点置为NULL;return node;
}

尾部插入

//尾部插入
void SLPushBack(SLNode** pphead, SLDataType x) {//注意在这里我们传参的是二级指针,因为我们需要在函数内部改变头结点的指向assert(pphead);//不能传NULL//新结点的申请SLNode* node=SLBuyNode(x);if (*pphead == NULL) {*pphead = node;}else {SLNode* pcur = *pphead;while (pcur->next) {//找到next元素为NULL的结点,也就是为链表尾部pcur = pcur->next;}pcur->next = node;}}

测试运行一下:


头部插入

//头部插入
void SLPushFront(SLNode** pphead, SLDataType x) {assert(pphead);SLNode* node = SLBuyNode(x);//这里需要处理头结点为空的情况吗?不需要,因为没有涉及到解引用其元素node->next = *pphead;*pphead = node;
}

测试运行一下:


尾部删除

//尾部删除
void SLPopBack(SLNode** pphead) {assert(*pphead && pphead);//if (!(*pphead)->next) {//处理只有一个元素的情况free(*pphead);*pphead = NULL;}else {SLNode* prev = NULL;SLNode* pcur = *pphead;while (pcur->next) {//找到尾结点前一个结点prev = pcur;pcur = pcur->next;}free(pcur);//将尾结点释放pcur = NULL;prev->next = NULL;//将尾结点的前一个结点的next元素置为NULL}
}

测试运行一下:


头部删除

//头部删除
void SLPopFront(SLNode** pphead) {assert(*pphead && pphead);SLNode* next = (*pphead)->next;//保存头结点的下一个结点地址free(*pphead);//释放头结点*pphead = next;//使头结点指向下一个结点
}

测试运行一下:


查找

在链表中想要对指定位置进行操作不能使用下标,所以我们必须找到指定位置的地址才能对其进行操作。

//查找
SLNode* SLFind(SLNode* phead, SLDataType x) {assert(phead);SLNode* pcur = phead;while (pcur) {if (pcur->data == x) {return pcur;}pcur = pcur->next;}return NULL;
}

在指定位置之前插入数据

//在指定位置之前插入数据
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x) {assert(pphead && pos && *pphead);//pos和pphead不能为空,以及pphead指向空间不能为空if (*pphead == pos) {//处理头插的情况SLPushFront(pphead,x);}else {SLNode* node = SLBuyNode(x);SLNode* pcur = *pphead;while (pcur->next != pos) {//找到pos前一个结点pcur = pcur->next;}node->next = pcur->next;pcur->next = node;}
}

测试运行一下:


在任意位置之后插入数据

//在任意位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataType x) {assert(pos);//pos不能为空SLNode* node = SLBuyNode(x);node->next = pos->next;pos->next = node;
}

测试运行一下:


 删除pos结点

//删除pos结点
void SLErase(SLNode** pphead, SLNode* pos) {assert(*pphead && pphead && pos);if (*pphead == pos) {//处理头删的情况SLPopFront(pphead);}else {SLNode* pcur = *pphead;while (pcur->next!= pos) {pcur = pcur->next;}pcur->next = pos->next;free(pos);pos = NULL;}
}

 测试运行一下:


 删除pos之后结点

//删除pos之后结点
void SLEraseAfter(SLNode* pos) {assert(pos && pos->next);//pos后面的结点也不能为空SLNode* next = pos->next;pos->next = next->next;free(next);next = NULL;
}

 测试运行一下:

 


 销毁链表

//销毁链表
void SLDestory(SLNode** pphead) {assert(pphead && *pphead);SLNode* pcur = *pphead;while (pcur) {SLNode* nextnode = pcur->next;//使用一个变量接受下一个结点地址free(pcur);pcur = nextnode;}*pphead = NULL;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com