网站服务提供商,商务网站建设的流程,手机网站建设费用,美丽说网站优化大家好#xff0c;今天为大家分享一下第二个数据结构——单链表 先打个广告#xff1a;这里是博主写道顺序表#xff0c;大家也可以查看#xff1a;顺序表详解 首先#xff1a; 我们学完顺序表的时候#xff0c;我们发现有以下问题#xff1a; 中间/头部的插入删除…大家好今天为大家分享一下第二个数据结构——单链表 先打个广告这里是博主写道顺序表大家也可以查看顺序表详解 首先 我们学完顺序表的时候我们发现有以下问题 中间/头部的插入删除时间复杂度为O(N) 增容需要申请新空间拷贝数据释放旧空间、消耗大量资源。 增容一般是2倍的增长势必会有一定的空间浪费。例如当前容量为300满了以后增容到600我们再继续插入了5个数据后面没有数据插入了那么就浪费了295个数据空间。 链表就能够很好的解决这些问题
链表是一种物理存储单元上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点链表中每一个元素称为结点组成结点可以在运行时动态生成。每个结点包括两个部分一个是存储数据元素的数据域另一个是存储下一个结点地址的指针域。由于不必须按顺序存储链表在插入的时候可以达到O(1)的复杂度比另一种线性表顺序表快得多但是查找一个节点或者访问特定编号的节点则需要O(n)的时间而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。 单链表模样如下 博主分享的链表接口如下
typedef int SLTDataType;//存储的数据类型
typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;//打印链表
void SListPrint(SLTNode* phead);
//创建节点
SLTNode* BuySListNode(SLTDataType x);
//尾插
void SListPushBack(SLTNode** phead, SLTDataType x);
//头插
void SListPushFront(SLTNode** phead, SLTDataType x);
//尾删
void SListPopBack(SLTNode** phead);
//头删
void SListPopFront(SLTNode** phead);
//查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
//在pos位置之前插入
void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x);
//删除pos位置
void SListErase(SLTNode** phead, SLTNode* pos);
//在pos位置之后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的位置
void SListEraseAfter(SLTNode* pos);下面对每个接口的实现进行说明 1、创建新节点的接口函数 SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));//出这个函数newnode被销毁但是它保存的地址空间是malloc出来的不会销毁assert(newnode);newnode-data x;newnode-next NULL;return newnode;
}assert断言检查一下如果申请失败就报错提示申请成功就返回创建的节点的地址 2、打印数据函数的实现 void SListPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}定义一个指针cur指向头结点使用这个指针循环遍历这个指针指向的不为空的话就继续循环在循环中打印cur-data对应的操作是printf(“%d-”, cur-data);打印%d后面加-是为了方便观察;然后将cur指针移动到下一个结点的位置对应操作是cur cur-next;继续打印直到cur为空打印完毕 3、尾插函数的实现 void SListPushBack(SLTNode** phead, SLTDataType x)
{//需要传入头节点以供寻找尾结点从而进行尾插SLTNode* newnode BuySListNode(x);//创造新结点assert(phead);//就算链表为空但是他的地址不能为空呀if (*phead NULL){*phead newnode;}else {SLTNode* tail *phead;//循环找尾节点while (tail-next ! NULL){tail tail-next;}//找到当下最后一个节点后让它指向插入的这个节点tail-next newnode;}
}4、头插函数的实现 void SListPushFront(SLTNode** phead, SLTDataType x)
{assert(phead);//就算链表为空但是他的地址不能为空呀SLTNode* newnode BuySListNode(x);//创造新结点newnode-next *phead;*phead newnode;
}将创建的新结点的地址存放在newnode指针变量中pphead为原先头结点的地址头插一个新结点后应该将新结点的next存放原先头结点的地址对应操作为newnode-next pphead;然后保存在pphead应该为新的头结点的地址也就是newnode所指向的地址对应操作为pphead newnode; 5、尾删函数的实现 void SListPopBack(SLTNode** phead)
{//if (*phead NULL)//温柔的检查//{// return;//}assert(phead);//就算链表为空但是他的地址不能为空呀assert(*phead!NULL);//暴力检查if ((*phead)-next NULL)//如果只有一个节点{free(*phead);*phead NULL;// 要改变phead,就需要二级指针}else//如果有多个结点{SLTNode* tailPrev *phead;SLTNode* tail *phead;//循环找尾节点while (tail-next ! NULL){tailPrev tail;tail tail-next;}free(tail);tailPrev-next NULL;}}先创建两个指针一个tail,一个tailprev,便利一遍链表tail保存最后一个节点tailprev保存最后一个节点的前一个节点free掉tail,将tailprev的next指向NULL就完成了尾删 如果只有一个节点则释放后要通过对二级指针解引用将其置为空 6、头删函数的实现 void SListPopFront(SLTNode** phead)// 要改变phead,就需要二级指针
{assert(*phead!NULL);//链表为空就不能删除呀assert(phead);//就算链表为空但是他的地址不能为空呀//if (*phead NULL)//温柔的检查//{// return;//}SLTNode* Next (*phead)-next;free(*phead);*phead Next;
}提前保存好头节点的next值删除后将头节点变为保存的next 7、查找函数的实现 SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur phead;while (cur){if (cur-data x){return cur;}cur cur-next;}return NULL;
}遍历一遍链表哪个节点的数据和要求的数据相同则返回该节点 8、任意位置插入节点函数的实现 void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x)
{assert(pos);//插入位置 传 错为空就报错assert(*phead);assert(phead);//就算链表为空但是他的地址不能为空呀if (pos *phead){SListPushFront(phead, x);//头插}else{SLTNode* prev *phead;while (prev-next !pos){prev prev-next;}SLTNode* newnode BuySListNode(x);prev-next newnode;newnode-next pos;}
}这个函数写出来之后就可以利用他对前面所写的头插和尾插进行改写了大佬们可以尝试一下呀 9、删除节点函数的实现 void SListErase(SLTNode** phead, SLTNode* pos)
{assert(pos);//插入位置 传 错为空就报错assert(*phead);assert(phead);//就算链表为空但是他的地址不能为空呀if (pos *phead){SListPopFront(phead);}else{SLTNode* prev *phead;while (prev-next! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;//可有可无}
}
这个函数写出来之后就可以利用他对前面所写的头删和尾删进行改写了大佬们可以尝试一下呀 下面是完整的代码
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.htypedef int SLTDataType;
typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;//打印链表
void SListPrint(SLTNode* phead);
//创建节点
SLTNode* BuySListNode(SLTDataType x);
//尾插
void SListPushBack(SLTNode** phead, SLTDataType x);
//头插
void SListPushFront(SLTNode** phead, SLTDataType x);
//尾删
void SListPopBack(SLTNode** phead);
//头删
void SListPopFront(SLTNode** phead);
//查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
//在pos位置之前插入
void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x);
//删除pos位置
void SListErase(SLTNode** phead, SLTNode* pos);
//在pos位置之后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的位置
void SListEraseAfter(SLTNode* pos);#define _CRT_SECURE_NO_WARNINGS 1
#includeSList.hvoid SListPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));//出这个函数newnode被销毁但是它保存的地址空间是malloc出来的不会销毁assert(newnode);newnode-data x;newnode-next NULL;return newnode;
}void SListPushBack(SLTNode** phead, SLTDataType x)
{//需要传入头节点以供寻找尾结点从而进行尾插SLTNode* newnode BuySListNode(x);//创造新结点assert(phead);//就算链表为空但是他的地址不能为空呀if (*phead NULL){*phead newnode;}else {SLTNode* tail *phead;//循环找尾节点while (tail-next ! NULL){tail tail-next;}//找到当下最后一个节点后让它指向插入的这个节点tail-next newnode;}
}void SListPushFront(SLTNode** phead, SLTDataType x)
{assert(phead);//就算链表为空但是他的地址不能为空呀SLTNode* newnode BuySListNode(x);//创造新结点newnode-next *phead;*phead newnode;}void SListPopBack(SLTNode** phead)
{//if (*phead NULL)//温柔的检查//{// return;//}assert(phead);//就算链表为空但是他的地址不能为空呀assert(*phead!NULL);//暴力检查if ((*phead)-next NULL)//如果只有一个节点{free(*phead);*phead NULL;// 要改变phead,就需要二级指针}else//如果有多个结点{SLTNode* tailPrev *phead;SLTNode* tail *phead;//循环找尾节点while (tail-next ! NULL){tailPrev tail;tail tail-next;}free(tail);tailPrev-next NULL;}}void SListPopFront(SLTNode** phead)// 要改变phead,就需要二级指针
{assert(*phead!NULL);//链表为空就不能删除呀assert(phead);//就算链表为空但是他的地址不能为空呀//if (*phead NULL)//温柔的检查//{// return;//}SLTNode* Next (*phead)-next;free(*phead);*phead Next;
}SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur phead;while (cur){if (cur-data x){return cur;}cur cur-next;}return NULL;
}void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x)
{assert(pos);//插入位置 传 错为空就报错assert(*phead);assert(phead);//就算链表为空但是他的地址不能为空呀if (pos *phead){SListPushFront(phead, x);//头插}else{SLTNode* prev *phead;while (prev-next !pos){prev prev-next;}SLTNode* newnode BuySListNode(x);prev-next newnode;newnode-next pos;}
}void SListErase(SLTNode** phead, SLTNode* pos)
{assert(pos);//插入位置 传 错为空就报错assert(*phead);assert(phead);//就算链表为空但是他的地址不能为空呀if (pos *phead){SListPopFront(phead);}else{SLTNode* prev *phead;while (prev-next! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;//可有可无}
}void SListInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode BuySListNode(x);newnode-next pos-next;//这两句的顺序一定要区分好pos-next newnode;}void SListEraseAfter(SLTNode* pos)
{assert(pos);if (pos-next NULL){return;}else{SLTNode* del pos-next;pos-next del-next;free(del);del NULL;//可有可无}
}单链表分享到这里就完了大家可以参考有不正确的地方还请指教谢谢
