茶叶手机网站建设,网站建站网站哪家好,手机怎么编辑网页,深圳头条新闻在线看目录
前言
1 链表
1.1 链表的概念及结构
1.2 链表的分类
1.2.1 单向或者双向
1.2.2 带头或者不带头
1.2.3 循环或者非循环
1.2.4 无头单向非循环链表
1.2.5 带头双向循环链表
2 链表的实现
2.1 结构
2.2 结点的创建
2.3 尾插
2.4 头插
2.5 尾删
2.6 头删
2.7 …目录
前言
1 链表
1.1 链表的概念及结构
1.2 链表的分类
1.2.1 单向或者双向
1.2.2 带头或者不带头
1.2.3 循环或者非循环
1.2.4 无头单向非循环链表
1.2.5 带头双向循环链表
2 链表的实现
2.1 结构
2.2 结点的创建
2.3 尾插
2.4 头插
2.5 尾删
2.6 头删
2.7 查找
2.8 在pos位置之前插入数据
2.9 删除pos位置
2.10 在pos位置之后插入数据
2.11 删除pos位置之后的数据
2.12 打印数据
2.13 销毁数据 个人主页库库的里昂 C/C领域新星创作者 欢迎 点赞✍评论⭐收藏✨收录专栏数据结构与算法希望作者的文章能对你有所帮助有不足的地方请在评论区留言指正大家一起学习交流 前言 上一次我们分享了线性表中的一种结构顺序表它存在着一些其缺点比如在中间位置或者头部进行元素插入或者删除的时候时间复杂度是O(N)效率比较低并且顺序表在扩容的时候也存在时间和空间上的消耗由于我们每次都是按照二倍来扩的那就很有可能会出现扩大了用不完导致空间浪费的现象。这些问题该如何解决呢那就需要用到今天分享给大家的另一种线性结构链表。 1 链表
1.1 链表的概念及结构
概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 注意
从上图可看出链式结构在逻辑上是连续的但是在物理上不一定连续现实中的结点一般都是从堆上申请出来的从堆上申请的空间是按照一定的策略来分配的两次申请的空间可能连续也可能不连续
假设在32位系统上结点中值域为int类型则一个节点的大小为8个字节则也可能有下述链表 1.2 链表的分类
实际中链表的结构非常多样以下情况组合起来就有8种链表结构
1.2.1 单向或者双向 1.2.2 带头或者不带头 1.2.3 循环或者非循环 虽然有这么多的链表的结构但是我们实际中最常用还是两种结构
1.2.4 无头单向非循环链表 1.2.5 带头双向循环链表 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了后面我们代码实现了就知道了。
2 链表的实现
2.1 结构
typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;//数据域struct SListNode* next;//指针域
}SLTNode;2.2 结点的创建
我们想使用链表来实现各种功能得先有链表所以首先使用malloc创建节点。
SLNode* CreateNode(SLNDataType x)
{SLNode* newnode (SLNode*)malloc(sizeof(SLNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-val x;newnode-next NULL;return newnode;
} 2.3 尾插
我们在尾插时会有两种情况链表为空的插入和有其他节点的尾插。第一种情况会出现一些理解性的错误接下来就让我们学习学习这两种尾插的情况。 void SLTPushBack(SLNode** pphead, SLNDataType x)
{assert(pphead);SLNode* newnode CreateNode(x);if (*pphead NULL){*pphead newnode;}else{SLNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}
2.4 头插
要想让链表连起来就要让newnode-next存放下一个节点的地址也就是旧链表phead的值然后将newnode的地址存放在phead中形成新的链表。无论一开始有没有节点头插都是相同的。 void SLTPushFront(SLNode** pphead, SLNDataType x)
{assert(pphead);SLNode* newnode CreateNode(x);newnode-next *pphead;*pphead newnode;
}
2.5 尾删
在尾删时也有两种情况一种是有很多节点另一种是只剩一个节点当删最后一个节点时要改变plist的值所以我们要传递plist的指针。我们要使用两个指针当后面的指针释放后可以利用前面的指针将最后一个节点的next置为空。
void SLTPopBack(SLNode** pphead)
{assert(pphead);assert(*pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLNode* tail *pphead;while (tail-next-next ! NULL){tail tail-next;}free(tail-next);tail-next NULL;}
}
2.6 头删
头删时如果先释放空间就会找不到下一个节点的地址如果先把下一个节点的地址赋给*pphead就会导致无法释放空间所以我们要创建一个临时变量来存放下一个节点的地址。
void SLTPopFront(SLNode** pphead)
{assert(pphead);assert(*pphead);SLNode* tmp *pphead;*pphead (*pphead)-next;free(tmp);
}
2.7 查找
循环判断时不要使用cur-next这样写最后一个数据要单独处理不方便找到时就返回此时的地址。
SLNode* SLTFind(SLNode* phead, SLNDataType x)
{SLNode* cur phead;while (cur){if (cur-val x){return cur;}else{cur cur-next;}}return NULL;
}
2.8 在pos位置之前插入数据
在pos位置之前插入有一种特殊的情况就是头插要改变plist的值我们要传二级指针进去。同时我们要创建一个指针变量找到pos之前的位置才能使链表连接起来。
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{assert(pphead);assert(pos);assert(*pphead);if (*pphead pos){SLTPushFront(pphead, x);}else{SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLNode* newnode CreateNode(x);prev-next newnode;newnode-next pos;}
}
2.9 删除pos位置
有可能删除的是头节点所以要传递二级指针。
void SLTErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(*pphead);assert(pos);if (*pphead pos){SLTPopFront(pphead);}else{SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
}
2.10 在pos位置之后插入数据
这里我们要注意地址赋值的顺序顺序不对会造成内存泄漏。如果先把newnode的地址赋给pos的指针域就会丢失下一个节点的地址。
void SLTInsertAfter(SLNode* pos, SLNDataType x)
{assert(pos);SLNode* newnode CreateNode(x);newnode-next pos-next;pos-next newnode;
}
2.11 删除pos位置之后的数据
void SLTEraseAfter(SLNode* pos)
{assert(pos);assert(pos-next);SLNode* tmp pos-next;pos-next pos-next-next;free(tmp);tmp NULL;
}
2.12 打印数据
void SLTPrint(SLNode* phead)
{SLNode* cur phead;while (cur ! NULL){printf(%d-, cur-val);cur cur-next;}printf(NULL\n);
}
2.13 销毁数据
void SLTDestroy(SLNode** pphead)
{assert(pphead);SLNode* cur *pphead;while (cur){SLNode* next cur-next;free(cur);cur next;}*pphead NULL;
}