二手房公司网站源码,wordpress 分类 权限,wordpress上传文件路径,江阴建设银行网站文章目录 前言一、链表的概念二、链表的分类三、链表的结构四、前置知识准备五、单链表的模拟实现定义头节点初始化单链表销毁单链表打印单链表申请节点头插数据尾插数据头删数据尾删数据查询数据在pos位置之后插入数据删除pos位置之后的数据 总结 前言 本篇的单链表完全来说是… 文章目录 前言一、链表的概念二、链表的分类三、链表的结构四、前置知识准备五、单链表的模拟实现定义头节点初始化单链表销毁单链表打印单链表申请节点头插数据尾插数据头删数据尾删数据查询数据在pos位置之后插入数据删除pos位置之后的数据 总结 前言 本篇的单链表完全来说是单向不带头单链表这种和另外一种链表(双向带头循环链表)使用最广泛我们只要对它们两个有所了解即可 正文开始 一、链表的概念 链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的
二、链表的分类 三、链表的结构 就如同下图一样一节一节前面连着后面就是链表的一种表现 同时我们也发现以下几点
从上图可看出链式结构在逻辑上是连续的但是在物理上不一定连续节点一般都是在堆上申请出来的从堆上申请空间两次申请得到的内存可能连续也可能不连续 物理结构数据实际存储在内存中的结构 逻辑结构想象出来的结构 四、前置知识准备
在正式开始实现之前我希望你有以下认识
实现部分接口需要通过二级指针接受实参原因在于我们需要可以修改实参而形参只是实参的一份拷贝要想修改实参必须得传指针同样若实参本来就是指针那么就要传指针的指针即二级指针而是实参为一级指针时(同样是传递地址)需要使用二级指针进行接受否则获得临时拷贝不会影响到实参。修改实参的情况比如一开始为空在插入时需将头指针存储在有效结点的的地址上需要改变实参的值单链表的初始化这里实现链表没有必要进行初始化初始化对于一开始就要开辟的空间有初始化的需求表示多个节点通过地址链接在一起那么只需要开辟新节点的时候初始化下就行了(有哨兵位需要初始化)二级指针断言二级指针存放的是头节点的地址头节点的地址为空那么还有什么意义呢
五、单链表的模拟实现
定义头节点
//单链表节点
//根据定义需要存储一个数据和一个指向下一个结点的指针
typedef int SLDataType;//定义数据类型可以根据需要更改typedef一下就很方便
typedef struct SList
{SLDataType data; //数据域 存储数据struct SList* next; //指针域 存储指向下一个结点的指针
}SList;请注意这里不能在节点内就单独用SList来定义next指针因为这时候还没有typedef成功呢还在节点内部
初始化单链表
因为创建一个变量实质是给变量开辟一块内存空间但是这块内存空间可能有遗留的数据所以在创建变量之后需要进行初始化而数据域我们也不清楚到底该传那个随便传个0就行但是指针域就必须置空了否则就是野指针
void SListInit(SList* phead)
{assert(phead); //防止传入空指针传入则报错phead-data 0; //将数据初始化为0phead-next NULL;//将结点指针初始化为NULL
}销毁单链表
有开辟内存自然而然的就有还回内存即销毁单链表 void SListDestroy(SList* phead)
{assert(phead);SList* cur phead; //为了能在后序找到头结点所以新创建一个变量指向头结点while (cur ! NULL){SList* next cur-next;free(cur);cur next;}
}我们不妨来想想为什么是传一级指针即可首先我们这里是为了销毁内存虽然说形参的这个节点指针和实参的节点指针地址不一样但是所存的节点都是同一个节点所以可以直接传指针有因为我们说链表在物理上是不连续的所以得通过指针跳着跳着一个个销毁
打印单链表 同样的我们只要传一级指针就可以了且通过指针来跳转
void SListPrint(SList* phead)
{assert(phead);SList* cur phead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}申请节点
在插入中使用相当频繁所以我们再对此单独实现一个函数使得代码更加的结构化 请注意指针并不单独开空间它起到的更多是一个中间人的作用通过指针来控制
SList* BuySeqList(SLDataType x)
{SList* pnewNode (SList*)malloc(sizeof(SList));//动态开辟一个单链表类型大小if (pnewNode NULL)//动态开辟的内存不一定成功所以需要判断{printf(malloc fail\n);exit(-1);}//内存开辟成功则把数据赋值到指定位置pnewNode-data x;pnewNode-next NULL;return newnode;
}头插数据 void SListPushFront(SList** pphead, SLDataType x)
{SList* newnode BuySeqList(x);newnode-next *pphead;*pphead newnode;
}尾插数据 void SListPushBack(SList** pphead, SLDataType x)
{SList* newnode BuySeqList(x);if (*pphead NULL) // 没有节点的时候{*pphead newnode;}else // 有节点的时候{SList* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}头删数据
void SListPopFront(SList** pphead)
{assert(*pphead);//头结点不为空则有数据SList* head (*pphead)-next;free(*pphead);*pphead head;
}尾删数据
void SListPopBack(SList** pphead)
{assert(*pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SList* tail *pphead;SList* prev NULL;while (tail-next ! NULL){prev tail;tail tail-next;}free(tail);tail NULL;prev-next NULL;}
}查询数据
找到则返回当前当前数据结点地址没找到则返回空地址
SList* SListFind(SList* phead, SLDataType x)
{assert(phead);SList* cur phead;while (cur ! NULL){if (cur-data x){return cur;}cur cur-next;}return NULL;
}在pos位置之后插入数据 void SListInsertAfter(SList* pos, SLDataType x)
{assert(pos);SList* newnode BuySeqList(x);SList* next pos-next;pos-next newnode;newnode-next next;
}删除pos位置之后的数据 void SListEraseAfter(SList* pos)
{assert(pos);assert(pos-next);//判断pos之后是否有数据没数据则报错SList* next pos-next-next;free(pos-next);pos-next next;
}总结 链表可以说是CS学生遇到的第二个劝退点了第一个是指针它是我们所学知识的一个集成展现需要我们对前面知识的充分掌握所以对计算机来说知识比较连贯这也是学习它比较难受的地方
