C++ 单链表
雪芙花 人气:0单链表的实现(从入门到熟练)
概念和结构
概念:链表是一种物理存储结构上非连续、非顺序的存储结构
数据元素的逻辑顺序是通过链表中的指针链 接次序实现的
图示:
注意:
链表结构在逻辑上为连续的,但是物理上(内存中)不一定连续
链表节点都是在堆上申请出来的,申请空间按一定策略分配
结构种类
链表具有多种结构:单向\双向,带头\不带头,循环\非循环
实际上最常用的是:无头单向非循环链表,带头双向循环链表
链表的实现
注意:这里实现的是无头单向非循环链表
增删查改接口
// 动态申请一个节点 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 void SListInsertAfter(SListNode* pos, SLTDateType x); // 单链表删除pos位置之后的值 void SListEraseAfter(SListNode* pos);
节点结构体创建
typedef int SLTDateType; typedef struct SListNode { SLTDateType data; struct SListNode* next; }SListNode;
节点开辟
对于链表来说,每需要空间就需要进行开辟,这里我们将之封装成一个函数,便于后续调用直接使用(开辟的同时进行赋值)
参考代码:
//链表节点开辟 SLTNode* BuySListNode(SLTDateType x) { //动态分配一个节点 SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { //分配失败则打印错误信息并结束进程 perror("newnode fail:"); exit(-1); } //成功则进行赋值 newnode->data = x; newnode->next = NULL; //返回节点地址,以便后续操作 return newnode; }
数据打印
注意:
1.对于不带头的链表来说,打印数据不需要修改链表首节点地址(故只要传链表指针)
2.用循环遍历链表,每打印数据,需要指向下一个节点
3.依靠尾节点的址域为NULL来结束循环
代码:
//链表数据打印 void SListPrint(SLTNode* phead)//一级指针接收一级指针(打印不需改变指针本身内容) { //创建一个寻址指针 SLTNode* cur = phead; while (cur!=NULL)//后续还有节点 { //打印数据并指向下一个节点 printf("%d->", cur->data); cur = cur->next; } //最后打印空指针 printf("NULL\n"); return; }
链表尾插数据
- 要尾插数据则需要遍历找到链表的尾节点
- 对于不带头链表,尾插数据也可能是插在链表首元素的地址(当链表为空),需要修改链表指针的内容(故需要传入链表指针的地址)
- 插入数据要开辟节点
代码:
//链表尾插数据 void SListPushBack(SLTNode** pphead, SLTDateType x)//二级指针接收一级指针(尾插存在需改变链表指针本身内容) { //避免传入错误(直接报错便于找到错误位置) assert(pphead); //接收新节点的地址 SLTNode* newnode=BuySListNode(x); //头节点为空 if (*pphead == NULL) { *pphead = newnode; } else { //找尾节点 SLTNode* tail = *pphead;//创建寻址节点 //两个及以上节点的情况 while (tail->next != NULL) { //指向下一个节点 tail = tail->next; } //找到了 tail->next = newnode; } return; }
注意代码中的assert的作用:
- 正确传入链表指针的地址是不会为空的
- 但是对于非正常传入链表指针(不是链表指针的地址)且此时链表指针为空则会发生报错(assert报错会告诉错误位置),告诉程序员应该传入链表指针的地址
头删
注意:
- 删除前需要保存当前节点的址域(即保存下个节点的空间地址,以防丢失)
- 前删数据即删除当前链表首节点,即需修改链表指针的内容(故需传入链表指针的地址)
- 删除后修改链表指针内容,指向新的首节点
- 如果链表为空时无法删除(保存下个节点地址会造成非法访问)
代码:
//链表前删数据 void SListPopFront(SLTNode** pphead) { //避免传入错误(直接报错便于找到错误位置) assert(pphead); //链表为空的情况 if (*pphead == NULL) { return; } //创建指针保存第二个节点地址 SLTNode* next = (*pphead)->next; //释放当前头结点空间 free(*pphead); //更新头结点数据 *pphead = next; return; }
链表数据查找
注意:
- 查找时用循环遍历链表
- 对于查找数据不用修改链表指针的内容,故只需传入链表指针就行了
- 查找到时则返回节点地址,否则返回NULL
代码:
//链表数据查找 SLTNode* SListFind(SLTNode* phead, SLTDateType x) { //创建寻址指针 SLTNode* cur = phead; while (cur!=NULL) { if (cur->data == x)//找到数据符合节点 { return cur;//返回节点地址(好处:以便后续再寻找或修改) } else { //找下一个节点 cur = cur->next; } } //未找到数据符合节点 return NULL; }
链表pos位置前插数据
注意:
- 想要pos位置前插数据,不仅需要找到pos位置,还需要记录pos的前一个节点位置
- 传入的pos为NULL则报错
- 进行修改前节点的址域成新节点,并让新节点的址域修改成pos,这才是一个成功的pos位置前插数据
- 循环遍历链表查找pos位置,没有找到pos位置则什么也不干
代码:
//链表pos位置往前插入(较难)(还有在pos位置之后插入,简单点) void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x) { //避免传入错误(直接报错便于找到错误位置) assert(pphead); assert(pos); SLTNode* newnode = BuySListNode(x); //首结点符合的情况 if (*pphead == pos) { newnode->next = *pphead; *pphead = newnode; } else { //创建寻址指针 SLTNode* cur = *pphead; while (cur !=NULL) { if (cur->next!= pos) { cur = cur->next;//找到下一节点 } else // 找到对应空间 { cur->next = newnode; newnode->next = pos; return;//结束寻找(否则会一直插入,造成死循环) } } } //未找到则什么也不干 return; }
链表pos位置后插数据
注意:
- 后插则不用关注是否为首节点
- 也不用找到遍历找到前节点的位置
- 后插则先将新节点址域改成pos后节点地址再将pos的址域改成新节点地址
ps:一定要注意修改链接节点址域的先后,避免地址的丢失
代码:
//链表pos位置往后插入 void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x) { SLTNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode; return; }
链表pos位置数据删除
注意:
- 考虑删除首节点的情况,可能修改链表指针的内容,故需要传入链表指针的地址
- 对于删除节点,需要先保存pos位置下一个节点地址,将pos位置释放,再将pos位置前节点的址域改成pos位置后节点的地址,这才是成功的删除pos位置节点
- 循环找pos位置,没找到则什么也不干
参考代码:
//链表pos位置删除 void SListErase(SLTNode** pphead, SLTNode* pos) { //避免传入错误(直接报错便于找到错误位置) assert(pphead); assert(pos); //头结点符合的情况 if (*pphead == pos) { *pphead = (*pphead)->next; free(pos); } else { //创建寻址指针 SLTNode* cur = *pphead; while (cur != NULL) { if (cur->next != pos) { cur = cur->next;//找到下一节点 } else // 找到对应空间 { SLTNode* next = cur->next->next; free(cur->next); cur->next = next; return;//结束寻找 } } } //未找到则什么也不干 return; }
链表节点释放
注意:
- 对于动态开辟的内存空间,在使用后一定要记得的进行释放(避免造成内存泄漏)
- 因为链表节点是一个个开辟的,同样的释放也需要一个个进行释放
- 循环遍历释放当前节点前需保存后一个节点的地址,避免地址丢失无法释放
- 释放完后,还需将链表指针给置空(避免使用野指针)
参考代码:
//链表节点释放 void SListDestory(SLTNode** pphead) { //避免传入错误(直接报错便于找到错误位置) assert(pphead); //遍历释放 SLTNode* cur = *pphead; while (cur) { //保存下一个地址 SLTNode* next = cur->next; free(cur); cur = next; } //置空 *pphead = NULL; return; }
链表与顺序表区别
链表的优缺点
优点
- 按需申请空间(空间使用合理)
- 插入效率高(不用像顺序表样挪动数据)
缺点
- 不支持随机访问(无法用下标直接访问)
顺序表的优缺点
优点
- 支持随机访问 (有些算法需要结构支持随机访问:二分查找,快排等)
缺点
- 扩容空间有消耗(空间碎片化以及空间浪费)
- 插入数据需要挪动数据有消耗
加载全部内容