怎么仿一个复杂的网站,深圳网站建设厂家,wordpress在后台修改绑定域名,免费二维码制作网站目录
#x1f4a1;链表的概念和结构
#x1f4a1;链表的分类
#x1f4a1;无头单向非循环链表#xff08;单链表#xff09;的实现 定义节点结构
单链表的尾部插入
单链表的头部插入
单链表的尾部删除 单链表的头部删除
在指定位置插入前数据
在指定位置之后插入数…
目录
链表的概念和结构
链表的分类
无头单向非循环链表单链表的实现 定义节点结构
单链表的尾部插入
单链表的头部插入
单链表的尾部删除 单链表的头部删除
在指定位置插入前数据
在指定位置之后插入数据
删除结点
销毁链表
完整实现
带头双向循环链表的实现 定义节点结构
创建新节点
链表的初始化
双向链表的遍历打印
双向链表的尾插 双向链表的头插 完整实现 链表和顺序表数组的对比 链表的概念和结构
概念
链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 以单链表为例 可以看出 1.链式结构在逻辑上是连续的但是在物理上不一定连续 2.现实中的节点一般都是从堆上申请出来的 3.从堆上申请的空间是按照一定的策略来分配的两次申请的空间可能连续也可能不连续 链表的分类 虽然说有8种链表结构但是现实中主要使用的只有两种结构 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构如哈希桶、图的邻接表等等。带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都 是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带 来很多优势实现反而简单了。 无头单向非循环链表单链表的实现 定义节点结构
用 typedef 重定义要保存的数据类型方便修改灵活处理节点之间用指针相连每一个节点都会保存下一个节点的地址指向下一个节点
//定义链表节点的结构
typedef int SLDataType;
typedef struct SListNode
{SLDataType data;//要保存的数据struct SListNode* next;
}SLNode;
单链表的尾部插入 这里需要注意的是插入时可能头节点为空要改变指针所以要传二级指针 //尾插
void SLPushBack(SLNode** pphead, SLDataType x)
{assert(pphead);SLNode* node SLBuyNode(x);if (*pphead NULL){*pphead node;//改变结构体指针即指向结构体的指针return;}//说明链表不为空找尾SLNode* pcur *pphead;while (pcur-next){pcur pcur-next;}pcur-next node;//改变结构体成员pcur-next通过指针结构体的pcur指针访问结构体的next成员
}
单链表的头部插入
//头插
void SLPushFront(SLNode** pphead, SLDataType x)
{assert(pphead);SLNode* node SLBuyNode(x);//新节点跟头节点连起来node-next *pphead;//让新的节点称为头节点*pphead node;
}
单链表的尾部删除 删除时因为要释放空间所以要传递二级指针 注意 可能只有一个节点可能有多个节点不同情况不同处理 //尾删
void SLPopBack(SLNode** pphead)
{assert(pphead);//第一个节点不能为空assert(*pphead);//只有第一个节点的情况if ((*pphead)-next NULL){//直接把头节点删除free(*pphead);*pphead NULL;}else{//有多个节点的情况//找尾节点和尾节点的前一个节点SLNode* prev NULL;SLNode* ptail *pphead;while (ptail-next ! NULL){prev ptail;ptail ptail-next;}//prev的指针不再指向ptail,而是指向ptail的下一个节点prev-next ptail-next;free(ptail);//打印链表的函数里会判断是否为NULLptail NULL;}
} 单链表的头部删除 先保存头节点然后将原来头节点的下一个节点变成新的头节点最后释放掉原来的头节点 //头删
void SLPopFront(SLNode** pphead)
{assert(*pphead);assert(pphead);SLNode* del *pphead;*pphead (*pphead)-next;free(del);del NULL;
}
在指定位置插入前数据 插入位置 头部位置的插入需要改变头节点非链表头部位置的插入 //在指定位置之前插入数据
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{assert(pphead);//约定链表不能为空pos也不能为空assert(pos);assert(*pphead);SLNode* node SLBuyNode(x);//pos是头节点头插if (pos *pphead){node-next *pphead;*pphead node;return;}//找pos的前一个节点SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}// prev-node-posnode-next pos;prev-next node;
}
在指定位置之后插入数据 各种情况处理方法都一样不需要特殊处理 //在指定位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataType x)
{assert(pos);SLNode* node SLBuyNode(x);//pos node pos-nextnode-next pos-next;pos-next node;return;
}
删除结点 删除头节点需要将下一个节点设置为新的头节点删除其他位置的节点需要将该节点的前一个节点和后一个节点连接起来 //删除pos节点
void SLErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//如果pos是头节点if (pos *pphead){*pphead (*pphead)-next;free(pos);return;}SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}//prev pos pos-nextprev-next pos-next;free(pos);pos NULL;
}
销毁链表 注意先保存下一个节点的地址再释放节点 //销毁链表
void SLDesTroy(SLNode** pphead)
{assert(pphead);assert(*pphead);SLNode* pcur *pphead;while (pcur-next ! NULL){SLNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;
}
完整实现
#define _CRT_SECURE_NO_WARNINGS 1
#includeSList.h
void SLPrint(SLNode* phead)
{//循环打印SLNode* pcur phead;while (pcur ! NULL){printf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n);
}
//创建的新节点
SLNode* SLBuyNode(SLDataType x) {SLNode* node (SLNode*)malloc(sizeof(SLNode));node-data x;node-next NULL;return node;
}
//尾插
void SLPushBack(SLNode** pphead, SLDataType x)
{assert(pphead);SLNode* node SLBuyNode(x);if (*pphead NULL){*pphead node;//改变结构体指针即指向结构体的指针return;}//说明链表不为空找尾SLNode* pcur *pphead;while (pcur-next){pcur pcur-next;}pcur-next node;//改变结构体成员pcur-next通过指针结构体的pcur指针访问结构体的next成员
}
//头插
void SLPushFront(SLNode** pphead, SLDataType x)
{assert(pphead);SLNode* node SLBuyNode(x);//新节点跟头节点连起来node-next *pphead;//让新的节点称为头节点*pphead node;
}
//尾删
void SLPopBack(SLNode** pphead)
{assert(pphead);//第一个节点不能为空assert(*pphead);//只有第一个节点的情况if ((*pphead)-next NULL){//直接把头节点删除free(*pphead);*pphead NULL;}else{//有多个节点的情况//找尾节点和尾节点的前一个节点SLNode* prev NULL;SLNode* ptail *pphead;while (ptail-next ! NULL){prev ptail;ptail ptail-next;}//prev的指针不再指向ptail,而是指向ptail的下一个节点prev-next ptail-next;free(ptail);//打印链表的函数里会判断是否为NULLptail NULL;}
}
//头删
void SLPopFront(SLNode** pphead)
{assert(*pphead);assert(pphead);SLNode* del *pphead;*pphead (*pphead)-next;free(del);del NULL;
}
//查找第一个为x的节点
SLNode* SLFind(SLNode** pphead, SLDataType x)
{assert(pphead);SLNode* pcur *pphead;while (pcur){if (pcur-data x){return pcur;}pcur pcur-next;}return NULL;
}
//在指定位置之前插入数据
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{assert(pphead);//约定链表不能为空pos也不能为空assert(pos);assert(*pphead);SLNode* node SLBuyNode(x);//pos是头节点头插if (pos *pphead){node-next *pphead;*pphead node;return;}//找pos的前一个节点SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}// prev-node-posnode-next pos;prev-next node;
}
//在指定位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataType x)
{assert(pos);SLNode* node SLBuyNode(x);//pos node pos-nextnode-next pos-next;pos-next node;return;
}
//删除pos节点
void SLErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//如果pos是头节点if (pos *pphead){*pphead (*pphead)-next;free(pos);return;}SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}//prev pos pos-nextprev-next pos-next;free(pos);pos NULL;
}
//删除pos之后节点
void SLEraseAfter(SLNode* pos)
{assert(pospos-next);//pos pos-next pos-next-nextSLNode* del pos-next;pos-next pos-next-next;free(del);del NULL;
}
//销毁链表
void SLDesTroy(SLNode** pphead)
{assert(pphead);assert(*pphead);SLNode* pcur *pphead;while (pcur-next ! NULL){SLNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;
}
带头双向循环链表的实现 带头双向循环链表是双向链表的一种特殊形式它有以下特点 带头链表中有一个头节点它不存储实际数据只用于标识链表的起始位置。双向每个节点有两个指针分别指向前一个节点和后一个节点。循环链表的最后一个节点指向头节点形成一个循环。 定义节点结构
// 带头双向链表
typedef int LTDataType;
typedef struct ListNode
{LTDataType _data;struct ListNode* _next;struct ListNode* _prev;
}ListNode;
创建新节点 新节点的前驱指针和后驱指针都设置为NULL //创建新节点
ListNode* SLBuyNode(LTDataType x) {ListNode* node (ListNode*)malloc(sizeof(ListNode));node-_data x;node-_next NULL;node-_prev NULL;return node;
}
链表的初始化 初始化主要是对链表的头--哨兵节点进行操作它不保存具体的值可以随便设置它的存在可以确保链表一定不为空 //初始化
void InitList(ListNode** pHead)
{*pHead SLBuyNode(-1);(*pHead)-_next (*pHead);(*pHead)-_prev (*pHead);
}
双向链表的遍历打印 由于哨兵位不起到保存数据的作用所以在遍历打印时也会从头节点的下一个节点开始 // 双向链表打印
void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur pHead-_next;printf(哨兵位);while (cur!pHead){printf(%d, cur-_data);cur cur-_next;}printf(\n);
}
双向链表的尾插 由于这是一个循环链表所以尾插实际上就是在头节点的左边插入下面写了两种插入方法 // 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* node SLBuyNode(x);//方法一//ListNode* tail pHead-_prev;//tail-_next node;//node-_prev tail;//pHead-_prev node;//node-_next pHead;//方法二node-_prev pHead-_prev;pHead-_prev-_next node;node-_next pHead;pHead-_prev node;
} 双向链表的头插 头插是在哨兵位节点和它的下一个节点之间插入 // 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* node SLBuyNode(x);node-_next pHead-_next;pHead-_next-_prev node;pHead-_next node;node-_prev pHead;
} 完整实现
#define _CRT_SECURE_NO_WARNINGS 1
#includeList.h
//创建新节点
ListNode* SLBuyNode(LTDataType x) {ListNode* node (ListNode*)malloc(sizeof(ListNode));node-_data x;node-_next NULL;node-_prev NULL;return node;
}
//初始化
void InitList(ListNode** pHead)
{*pHead SLBuyNode(-1);(*pHead)-_next (*pHead);(*pHead)-_prev (*pHead);
}
// 双向链表打印
void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur pHead-_next;printf(哨兵位);while (cur!pHead){printf(%d, cur-_data);cur cur-_next;}printf(\n);
}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* node SLBuyNode(x);//方法一//ListNode* tail pHead-_prev;//tail-_next node;//node-_prev tail;//pHead-_prev node;//node-_next pHead;//方法二node-_prev pHead-_prev;pHead-_prev-_next node;node-_next pHead;pHead-_prev node;
}
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);assert(pHead-_next ! pHead);ListNode* del pHead-_prev;ListNode* next pHead-_prev-_prev;pHead-_prev next;next-_next pHead;free(del);del NULL;
}
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* node SLBuyNode(x);node-_next pHead-_next;pHead-_next-_prev node;pHead-_next node;node-_prev pHead;
}
// 双向链表头删
void ListPopFront(ListNode* pHead)
{assert(pHead);assert(pHead-_next ! pHead);ListNode* del pHead-_next;ListNode* next del-_next;pHead-_next next;next-_prev pHead;free(del);del NULL;
}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur pHead-_next;while (cur ! pHead){if (cur-_data x){return cur;}cur cur-_next;}return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* node SLBuyNode(x);ListNode* prev pos-_prev;prev-_next node;node-_prev prev;node-_next pos;pos-_prev node;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* del pos;ListNode* prev pos-_prev;prev-_next pos-_next;pos-_next-_prev prev;free(del);del NULL;
}
void ListDestory(ListNode* pHead)
{ListNode* cur pHead-next;while (cur ! pHead){ListNode* next cur-next;free(cur);cur next;}free(pHead);
}链表和顺序表数组的对比
不同点顺序表链表存储空间上物理上一定连续逻辑上连续但物理上不一定连续 随机访问支持O(1)不支持O(N)任意位置插入或者删除元素可能需要移动元素效率低O(N)只需修改指针指向插入动态顺序表空间不够时需要 扩容没有容量的概念应用场景元素高效存储频繁访问任意位置插入和删除频繁缓存利用率高低 _____________________________________________________________________________ ⭐感谢你的阅读希望本文能够对你有所帮助。如果你喜欢我的内容记得点赞关注收藏我的博客我会继续分享更多的内容。⭐
