小编给大家分享一下C++ 数据结构中单链表的示例分析,希望大家阅读完这篇文章之后都有所收获,下面让我们一起去探讨吧!
一、链表是什么
链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接依次实现的。
由图,链式结构在逻辑上是连续的,但是物理上不一定连续
显示中结点一般是从堆上申请出来的
从堆上申请的空间,是按照一定的策略划分的,两次申请的空间,可能连续,可能不连续,见顺序表
链表的分类
链表也可以分为很多种
单向或者双向
2. 带头或者不带头
3. 循环或非循环
我们最常用的还是无头单向非循环链表和带头双向循环链表 本篇我们实现无头单向非循环链表增删查改
二、链表的实现
基本结点结构
typedef int SLTDateType;typedef struct SListNode{SLTDateType data;struct SListNode* next;}SListNode;
头文件
//llist.h#pragma once#include <stdio.h>#include <assert.h>#include <stdlib.h>#include <string.h>typedef int SLTDateType;typedef struct SListNode{SLTDateType data;struct SListNode* next;}SListNode;// 动态申请一个节点SListNode* BuySListNode(SLTDateType x);// 单链表打印void SListPrint(SListNode* plist);// 单链表尾插void SListPushBack(SListNode** pplist, SLTDateType x);// 单链表的头插void SListPushFront(SListNode** pplist, SLTDateType x);// 单链表的尾删void SListPopBack(SListNode** pplist);// 单链表头删void SListPopFront(SListNode** pplist);// 单链表查找SListNode* SListFind(SListNode* plist, SLTDateType x);// 单链表在pos位置之后插入x// 分析思考为什么不在pos位置之前插入?void SListInsertAfter(SListNode* pos, SLTDateType x);// 单链表删除pos位置之后的值// 分析思考为什么不删除pos位置?void SListEraseAfter(SListNode* pos);// 单链表的销毁void SListDestory(SListNode* plist);
动态申请一个节点
// 动态申请一个节点SListNode* BuySListNode(SLTDateType x){SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL)//申请失败{printf("malloc fail\n");exit(-1);}else{newnode->data = x;newnode->next = NULL;}return newnode;}
单链表打印
链表单个结点中,data存储数据,next存储下一个结点的地址,可以通过next访问下一个结点
// 单链表打印void SListPrint(SListNode* plist){SListNode* cur = plist;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;//访问下一个结点}printf("NULL\n");}
单链表尾插
这里传入了头结点的地址的指针,是因为有可能要改变头结点的情况,传址调用幻术,如果只传入*plist,相当于只改变形参,实参不会有实际改变,通过pplist可以解决这个问题
// 单链表尾插void SListPushBack(SListNode** pplist, SLTDateType x){SListNode* newnode = BuySListNode(x);if (*pplist == NULL)//空链表{*pplist = newnode;}else{SListNode* tail = *pplist;//遍历至最后插入while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}}
单链表的尾删
一前一后遍历,找到空后直接free(tail),将prev->next置空即可
// 单链表的尾删void SListPopBack(SListNode** pplist){assert(pplist);if (*pplist == NULL)//空链表,无需删除{return;}else{SListNode* prev = NULL;SListNode* tail = *pplist;{while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}}}
单链表的头插
有点绕,要多想想
// 单链表的头插void SListPushFront(SListNode** pplist, SLTDateType x){assert(pplist);SListNode* newnode = BuySListNode(x);newnode->next = *pplist;*pplist = newnode;}
单链表头删
比较简单
// 单链表头删void SListPopFront(SListNode** pplist){assert(pplist);if (*pplist == NULL)//链表为空{return;}else{SListNode* next = (*pplist)->next;free(*pplist);*pplist = next;}}
// 单链表查找遍历即可SListNode* SListFind(SListNode* plist, SLTDateType x){SListNode* cur = plist;while (cur != NULL){if (cur->data = x){return cur;}cur = cur->next;}retuen NULL;}
*单链表在pos位置之后插入x
为什么不在pos之前插入,由于我们是单向链表,需要从头遍历查找pos,如果在pos之前插入,找到pos还需找到pos之前的地址,对所传参数不友好,所以我们一般在后插入
//单链表在pos位置之后插入xvoid SListInsertAfter(SListNode* pos, SLTDateType x){assert(pos);SListNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;}
单链表删除pos位置之后的值 为什么不删除pos位置,同上,在逻辑上和传参不友好.
// 单链表删除pos位置之后的值void SListEraseAfter(SListNode* pos){assert(pos);SListNode* next = pos->next;if (next){pos->next = next->next;free(next);next = NULL;}}
单链表的销毁 链表不像顺序表连续删头就可以,由于链表是一个一个分散的结点,需要逐一删除
// 单链表的销毁void SListDestory(SListNode** pplist){assert(*pplist);SListNode* cur = *pplist;while (cur){SListNode* next = cur->next;free(cur);cur = next;}*pplist = NULL;}
看完了这篇文章,相信你对“C++ 数据结构中单链表的示例分析”有了一定的了解,如果想了解更多相关知识,欢迎关注编程网行业资讯频道,感谢各位的阅读!