淘宝客怎么样做网站,网络公司经营范围互联网金融,东莞交易中心,办公室装修效果图片大全在上一篇文章中#xff0c;我们探索了顺序表这一基础的数据结构#xff0c;它提供了一种有序存储数据的方法#xff0c;使得数据的访 问和操作变得更加高效。想要进一步了解#xff0c;大家可以移步于上一篇文章#xff1a;探索顺序表#xff1a;数据结构中的秩序之美
今…在上一篇文章中我们探索了顺序表这一基础的数据结构它提供了一种有序存储数据的方法使得数据的访 问和操作变得更加高效。想要进一步了解大家可以移步于上一篇文章探索顺序表数据结构中的秩序之美
今天我们将进一步深入探讨另一个重要的数据结构——链表
链表和顺序表一样都属于线性表也用于存储数据但其内部结构和操作方式有着明显的不同。通过C语言的具体实现我们将会更加直观地理解它
源码可以打我的gitee里面查找唔姆/比特学习过程2 (gitee.com) 文章目录 [toc] 一.链表的概念及结构二.链表的分类三.无头单向非循环链表的实现1.项目文件规划2.基本结构及功能一览3.各功能接口具体实现3.1打印单链表3.2尾插3.3头插3.4尾删3.5头删3.6查找3.7插入pos前一个3.8删除pos前一个3.9插入pos后一个3.10删除pos后一个3.11销毁避免内存泄露
一.链表的概念及结构 链表是一种物理存储(实际上)结构上非连续、非顺序杂乱随意排序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 实际情况中 从上图可发现 链表在逻辑上连续在物理上是不连续的各个节点Node一般都是从堆上面申请空间的从堆上面申请的空间是有一定策略的可能连续可也能不连续 二.链表的分类 单向或者双向 带头或者不带头 循环或者非循环 三种情况随意组合起来就有8种链表结构 其中最为常用的是
无头单向非循环和带头双向循环 无头单向非循环链表结构简单但是一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等 带头双向循环链表结构最复杂一般用在单独存储数。实际中使用的链表数据结构都是带头双向循环链表。这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现它反而简单了 这两种结果都会给大家实现的今天先来无头单向非循环链表 三.无头单向非循环链表的实现
1.项目文件规划 头文件SList.h:用来基础准备常量定义typedef链表表的基本框架函数的声明源文件SList.h:用来各种功能函数的具体实现源文件test.c:用来测试功能是否有问题进行基本功能的使用
2.基本结构及功能一览
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.htypedef int SLDataType;typedef struct SingleListNode
{int data;SingleListNode* next;
}SLNode;void SLPrint(SLNode* phead);// 单链表打印void SLPushBack(SLNode** pphead, int n);// 单链表尾插
void SLPushFront(SLNode** pphead, int n);// 单链表头插
void SLPopBack(SLNode** pphead);// 单链表尾删
void SLPopFront(SLNode** pphead);// 单链表尾删SLNode* SLFind(SLNode* phead, int n);
SLNode* SLInsert(SLNode** pphead, SLNode* pos, int n);//在pos前面插入
SLNode* SLErase(SLNode** pphead, SLNode* pos);//删除pos前面那个void SLInsertAfter(SLNode* pos, int n);//在pos后面插入
void SLEraseAfter(SLNode* pos);//在pos后面删除void SLDestory(SLNode** pphead);3.各功能接口具体实现
3.1打印单链表
void SLPrint(SLNode* phead)
{assert(phead);SLNode* cur phead;while (cur ! NULL)//与while(cur)同样的效果{printf(%d , cur-data);cur cur-next;}printf(\n);
}3.2尾插
SLNode* CreateNode(int n)
{SLNode* newNode (SLNode*)malloc(sizeof(SLNode));if (newNode NULL){perror(malloc error);return -1;}newNode-data n;newNode-next NULL;return newNode;
}void SLPushBack(SLNode** pphead, int n)
{assert(pphead);SLNode* newNode CreateNode(n);//先把节点搞好//先考虑一下没有节点的情况if (*pphead NULL){*pphead newNode; //这就是传二级指针的原因//我们要改变 SLNode* phead本身的指向就把他地址传过来//当我们只是要改变指向的结构体里的内容时只要传SLNode* phead就行了}else{SLNode* tail *pphead;while (tail-next ! NULL)//找到最后一个节点{tail tail-next;}tail-next newNode;}
}通过 CreateNode 函数创建了一个含有数值 n 的新节点 newNode然后根据链表是否为空进行不同的操作 如果链表为空即头指针指向空则将新节点 newNode 赋值给头指针 *pphead如果链表不为空则需要找到链表末尾的节点通过遍历找到最后一个节点(tail)并将其 next 指针指向新节点 newNode以将新节点插入到链表的末尾 为什么传入二级指针 这种设计方式的原因在于需要修改指针本身的值而不是只修改指针所指向的内容 考虑到单链表在插入节点时可能会涉及链表头指针的修改如果直接传递单级指针指向头指针在函数内部对头指针进行修改是不会反映到函数外部的(形参是实参的临时拷贝)。但如果使用二级指针可以在函数内部修改指针的指向这样修改后的指向会在函数外部保持 3.3头插
void SLPushFront(SLNode** pphead, int n)
{assert(pphead);SLNode* newNode CreateNode(n);//先把节点搞好if (*pphead NULL){*pphead newNode;}else{newNode-next (*pphead)-next;(*pphead)-next newNode;}//或者//newNode-next (*pphead);//*pphead newNode;
}通过 CreateNode 函数创建了一个含有数值 n 的新节点 newNode接着根据链表是否为空进行不同的操作 如果链表为空即头指针指向空则将新节点 newNode 赋值给头指针 *pphead如果链表不为空则将新节点 newNode 的 next 指针指向当前头节点的下一个节点原链表的第二个节点然后将当前头节点的 next 指针指向新节点 newNode以完成插入 注释部分显示了另一种写法通过先设置新节点的 next 指针指向当前头节点然后再将链表的头指针指向新节点实现了同样的插入操作 3.4尾删
void SLPopBack(SLNode** pphead)
{assert(pphead);assert(*pphead);//防止一个都没有还删if ((*pphead)-next NULL)//只有一个{free(*pphead);*pphead NULL;}else{//找到倒数第二个SLNode* pre_tail *pphead;while (pre_tail-next-next ! NULL){pre_tail pre_tail-next;}free(pre_tail-next);pre_tail-next NULL;}
}检查链表头指针 *pphead 是否存在不为 NULL以及链表是否为空只有一个节点 如果链表中只有一个节点则直接释放该节点并将链表头指针设置为 NULL表示链表为空如果链表中有多个节点则会找到倒数第二个节点即指向最后一个节点的前一个节点。它通过遍历链表直到找到倒数第二个节点 pre_tail然后释放最后一个节点并将倒数第二个节点的 next 指针设置为 NULL表示该节点成为新的末尾节点 3.5头删
void SLPopFront(SLNode** pphead)
{assert(pphead);assert(*pphead);//防止一个都没有还删SLNode* first (*pphead)-next;//一个和多个都适用free(*pphead);*pphead first;
}创建了一个临时指针 first 来指向原链表的第二个节点如果存在。这是因为要删除的是链表的头节点为了不断开链表需要先保存第二个节点的地址通过 free(*pphead) 释放掉原来的头节点然后将链表的头指针 *pphead 更新为原头节点的下一个节点 first 3.6查找
SLNode* SLFind(SLNode* phead, int n)
{assert(phead);SLNode* cur phead;while (cur ! NULL)//与while(cur)同样的效果{if (cur-data n){return cur;}cur cur-next;}return NULL;
}3.7插入pos前一个
void SLInsert(SLNode** pphead, SLNode* pos, int n)//在pos前面插入
{assert(pphead);assert(pos);SLNode* cur *pphead;if (*pphead pos)//在第一个节点前面插入{// 头插SLTPushFront(pphead, n);}else{while (cur-next ! pos){cur cur-next;}SLNode* newNode CreateNode(n);newNode-next cur-next;cur-next newNode;}
}如果要插入的位置 pos 就是链表的头节点 *pphead即在第一个节点前面插入则调用 SLTPushFront 函数直接在链表头部插入新节点 newNode如果要插入的位置不是头节点则通过循环遍历链表直到找到 pos 的前一个节点 cur然后创建新节点 newNode 并将其插入到 pos 前面完成节点的插入操作 3.8删除pos前一个
void SLErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(pos);assert(*pphead ! pos);//防止前面没有SLNode* cur *pphead;SLNode* pre_cur *pphead;while (cur-next ! pos){pre_cur cur;cur cur-next;}pre_cur-next pos;free(cur);cur NULL;
}3.9插入pos后一个
void SLInsertAfter(SLNode* pos, int n)
{assert(pos);SLNode* newNode CreateNode(n);newNode-next pos-next;pos-next newNode;
}创建一个新节点 newNode并将新节点的 next 指针指向 pos 节点原本的下一个节点以保证链表的连续性将 pos 节点的 next 指针指向新节点 newNode完成了在指定节点之后插入新节点的操作 3.10删除pos后一个
void SLEraseAfter(SLNode* pos)
{assert(pos);SLNode* next pos-next-next;free(pos-next);pos-next NULL;pos-next next;
}3.11销毁避免内存泄露
void SLDestory(SLNode** pphead)
{assert(pphead);SLNode* cur *pphead;SLNode* next *pphead;while (cur!NULL){next cur-next;free(cur);cur next;}*pphead NULL;
}循环删除每一个Node最后把原本的结构体指针指向NULL 好啦这次知识就先到这里啦下一次大概率是双向带头循环的代码实现了。
