赞
踩
哈喽,大家好,今天我们学习的是数据结构里的链表,这里主要讲的是不带哨兵卫头节点的单向链表,下篇将会继续带大家学习双向链表。
目录
在上篇文章,我们已经学习了顺序表,不知大家有没有发现顺序表在一定程度上是存在缺陷的,比如说:
针对顺序表的缺陷,就有了链表来存储数据
概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
链表的定义:
这里的data就是要存放的数据
下面是要介绍的常用到的链表接口函数以及实现方法:
- //打印
- void SListPrint(SLTNode* phead);
- //创建新节点
- SLTNode* BuyListNode(SLTDateType x);
- //尾插
- void SListPushBack(SLTNode** pphead, SLTDateType x);
- //头插
- void SListPushFront(SLTNode** pphead, SLTDateType x);
- //头删
- void SListPopBack(SLTNode** pphead);
- //尾删
- void SListPopFront(SLTNode** pphead);
- //查找
- SLTNode* SListFind(SLTNode* phead, SLTDateType x);
- //插入
- void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
- void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x);
- //删除
- void SListErase(SLTNode** pphead, SLTNode* pos);
- //销毁
- void SListDestroy(SLTNode** pphead);
由于我们每次给链表插入数据时,都需要动态开辟空间来申请节点,所以我们把这个过程封装成一个函数,方便后续操作。
动态申请一个节点的步骤是先向计算机内存申请一块空间,这里我们将申请的空间用指针变量newnode来存储,然后将newnode中的data赋值,因为这是新开辟的节点,所以暂时将newnode中的next指向空。
注意:为了提高程序的可靠性,我们在动态内存申请后记得检查是否申请失败了,如果申请失败了输出提示信息,并退出程序。
- SLTNode* BuyListNode(SLTDateType x)
- {
- SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
- if (newnode == NULL)//如果动态内存申请失败就退出程序
- {
- printf("malloc fail\n");
- exit(-1);
- }
- newnode->data = x;
- newnode->next = NULL;
- return newnode;
- }
打印链表就是一个遍历链表的过程,我们首先定义一个指针(cur)指向链表的头节点,然后输出该节点的值,然后将指针指向下一个节点(cur=cur->next),依次进行,直到cur为空指针时停止
- void SListPrint(SLTNode* phead)
- {
- SLTNode* cur = phead;
- while (cur != NULL)
- {
- printf("%d->", cur->data);
- cur = cur->next;//将cur指向下一个节点
- }
- printf("NULL\n");
- }
尾插,就是先找到链表中最后一个节点,然后将数据插入到最后。
但是,我们要先判断链表是否为空,如果链表为空,我们直接直接将链表的头指针赋予要插入的数据。
由于尾插要改变链表,所以传参要用二级指针,包括下面的尾插,尾删,头删等都要用二级指针传参
- void SListPushBack(SLTNode** pphead, SLTDateType x)
- {
- SLTNode* newnode = BuyListNode(x);
- if (*pphead == NULL)
- {
- *pphead = newnode;
- }
- else
- {
- SLTNode* tail = *pphead;
- while (tail->next != NULL)
- {
- tail = tail->next;
- }
- tail->next = newnode;
- }
- }
头插是比较简单的一种操作,只需要申请新节点,将新节点的next指向链表的头,再让新节点成为链表的头即可。
- void SListPushFront(SLTNode** pphead, SLTDateType x)
- {
- SLTNode* newnode = BuyListNode(x);
- newnode->next = *pphead;
- *pphead = newnode;
- }
尾删:每次找到链表的最后一个节点和倒数第二个节点,然后释放最后一个节点所占的看空间并将最后一个节点置空,同时将倒数第二个节点的next指向NULL;如果链表只剩下一个节点,直接释放并置空该节点(这一步需要单独考虑)
注意:为了避免链表为空但有调用尾删的情况,我们需要断言一下,当传过来的链表是空链表的时候,程序就会报错
- void SListPopBack(SLTNode** pphead)
- {
- //保证链表不是空链表
- assert(*pphead != NULL);
- if ((*pphead)->next == NULL)
- {
- //当链表中只有一个节点
- free(*pphead);
- *pphead = NULL;
- }
- else
- {
- SLTNode* tail = *pphead;
- SLTNode* prev = NULL;
- while (tail->next != NULL)
- {
- prev = tail;
- tail = tail->next;
- }
- prev->next = NULL;
- free(tail);
- tail = NULL;
- }
- }
头删是将第一个节点释放然后指向第二个节点,在此之前需要定义一个指针next来保存第二个节点的地址。
- void SListPopFront(SLTNode** pphead)
- {
- //保证链表不是空链表
- assert(*pphead != NULL);
- SLTNode* next = (*pphead)->next;
- free(*pphead);
- *pphead = next;
- }
在pos位置插入x分为两种情况,一种是在pos前位置插入x ,另一种是在pos后位置插入x,下面将分别为大家介绍:
在pos位置前插入x,只需要找到pos的前一个位置,我们把pos的前一个位置命名为posPrev,然后创建一个新节点newnode,将posPrev的下一个节点指向newnode,newnode的下一个节点指向pos即可,如下图:
- void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
- {
- assert(pphead != NULL);
- assert(pos != NULL);
-
- SLTNode* newnode = BuyListNode(x);
- if (*pphead == pos)
- {
- newnode->next = *pphead;
- *pphead = newnode;
- }
- else
- {
- //找到pos的前一个位置
- SLTNode* posPrev = *pphead;
- while (posPrev->next != pos)
- {
- posPrev = posPrev->next;
- }
- posPrev->next = newnode;
- newnode->next = pos;
- }
- }
在pos位置后插入x比在pos位置前插入x要简单,不需要遍历链表即可完成
- void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x)
- {
- assert(pos != NULL);
- SLTNode* newnode = BuyListNode(x);
- newnode->next = pos->next;
- pos->next = newnode;
- }
删除pos位置值也需要先找到pos的前一个节点,因此也要考虑pos是链表的头节点的情况
- void SListErase(SLTNode** pphead, SLTNode* pos)
- {
- assert(*pphead != NULL);
- assert(pos != NULL);
- if (*pphead == pos)
- {
- *pphead = pos->next;
- free(pos);
- }
- else
- {
- SLTNode* posPrev = *pphead;
- while (posPrev->next != pos)
- {
- posPrev = posPrev->next;
- }
- posPrev->next = pos->next;
- free(pos);
- }
- }
查找x的地址,如果查找到了x,则返回该节点的地址,否则返回空指针。这个步骤也要遍历链表。
- SLTNode* SListFind(SLTNode* phead, SLTDateType x)
- {
- SLTNode* tail = phead;
- if (tail->data == x)
- {
- return tail;
- }
- while (tail ->data != x)
- {
- tail = tail->next;
- if (tail->data == x)
- {
- return tail;
- }
- }
- return NULL;
- }
销毁链表需要将所有节点所占的内存全部释放,再将链表的头置为空即可。
- void SListDestroy(SLTNode** pphead)
- {
- assert(*pphead != NULL);
- SLTNode* cur = *pphead;
- while (cur != NULL)
- {
- SLTNode* next = cur->next;
- free(cur);
- cur = next;
- }
- *pphead = NULL;
- }
SList.h文件:
- #pragma once
- #include<stdio.h>
- #include<stdlib.h>
- #include<assert.h>
-
- typedef int SLTDateType;
- typedef struct SListNode
- {
- SLTDateType data;
- struct SListNode* next;//存放下一个链表的地址
- }SLTNode;
-
- //打印
- void SListPrint(SLTNode* phead);
- //创建新节点
- SLTNode* BuyListNode(SLTDateType x);
- //尾插
- void SListPushBack(SLTNode** pphead, SLTDateType x);
- //头插
- void SListPushFront(SLTNode** pphead, SLTDateType x);
- //头删
- void SListPopBack(SLTNode** pphead);
- //尾删
- void SListPopFront(SLTNode** pphead);
- //查找
- SLTNode* SListFind(SLTNode* phead, SLTDateType x);
- //插入
- void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
- void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x);
- //删除
- void SListErase(SLTNode** pphead, SLTNode* pos);
- //销毁
- void SListDestroy(SLTNode** pphead);
SList.c文件:
- #include"SList.h"
-
- void SListPrint(SLTNode* phead)
- {
- SLTNode* cur = phead;
- while (cur != NULL)
- {
- printf("%d->", cur->data);
- cur = cur->next;//将cur指向下一个节点
- }
- printf("NULL\n");
- }
-
- SLTNode* BuyListNode(SLTDateType x)
- {
- SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
- if (newnode == NULL)//如果动态内存申请失败就退出程序
- {
- printf("malloc fail\n");
- exit(-1);
- }
- newnode->data = x;
- newnode->next = NULL;
- return newnode;
- }
-
- void SListPushBack(SLTNode** pphead, SLTDateType x)
- {
- SLTNode* newnode = BuyListNode(x);
- if (*pphead == NULL)
- {
- *pphead = newnode;
- }
- else
- {
- SLTNode* tail = *pphead;
- while (tail->next != NULL)
- {
- tail = tail->next;
- }
- tail->next = newnode;
- }
- }
-
- void SListPushFront(SLTNode** pphead, SLTDateType x)
- {
- SLTNode* newnode = BuyListNode(x);
- newnode->next = *pphead;
- *pphead = newnode;
- }
-
- void SListPopBack(SLTNode** pphead)
- {
- //保证链表不是空链表
- assert(*pphead != NULL);
- if ((*pphead)->next == NULL)
- {
- //当链表中只有一个节点
- free(*pphead);
- *pphead = NULL;
- }
- else
- {
- SLTNode* tail = *pphead;
- SLTNode* prev = NULL;
- while (tail->next != NULL)
- {
- prev = tail;
- tail = tail->next;
- }
- prev->next = NULL;
- free(tail);
- tail = NULL;
- }
- }
-
-
- void SListPopFront(SLTNode** pphead)
- {
- //保证链表不是空链表
- assert(*pphead != NULL);
- SLTNode* next = (*pphead)->next;
- free(*pphead);
- *pphead = next;
- }
-
- SLTNode* SListFind(SLTNode* phead, SLTDateType x)
- {
- SLTNode* tail = phead;
- if (tail->data == x)
- {
- return tail;
- }
- while (tail ->data != x)
- {
- tail = tail->next;
- if (tail->data == x)
- {
- return tail;
- }
- }
- return NULL;
- }
-
- void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
- {
- assert(pphead != NULL);
- assert(pos != NULL);
-
- SLTNode* newnode = BuyListNode(x);
- if (*pphead == pos)
- {
- newnode->next = *pphead;
- *pphead = newnode;
- }
- else
- {
- //找到pos的前一个位置
- SLTNode* posPrev = *pphead;
- while (posPrev->next != pos)
- {
- posPrev = posPrev->next;
- }
- posPrev->next = newnode;
- newnode->next = pos;
- }
- }
-
- void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x)
- {
- assert(pos != NULL);
- SLTNode* newnode = BuyListNode(x);
- newnode->next = pos->next;
- pos->next = newnode;
- }
-
- void SListErase(SLTNode** pphead, SLTNode* pos)
- {
- assert(*pphead != NULL);
- assert(pos != NULL);
- if (*pphead == pos)
- {
- *pphead = pos->next;
- free(pos);
- }
- else
- {
- SLTNode* posPrev = *pphead;
- while (posPrev->next != pos)
- {
- posPrev = posPrev->next;
- }
- posPrev->next = pos->next;
- free(pos);
- }
- }
-
- void SListDestroy(SLTNode** pphead)
- {
- assert(*pphead != NULL);
- SLTNode* cur = *pphead;
- while (cur != NULL)
- {
- SLTNode* next = cur->next;
- free(cur);
- cur = next;
- }
- *pphead = NULL;
- }
总结:这篇文章主要写的是单向链表,后续将继续带领大家学习双向链表。如果我写的有什么的不好之处,请在文章下方给出你宝贵的意见。如果觉得我写的好的话请点个赞赞和关注哦~
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/神奇cpp/article/detail/859789
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。