保定网站建设seo优化营销,淄博网站文章优化,优化的含义是什么,wordpress中文瀑布流一、双向链表的结构 注意#xff1a;双向链表又称带头双向循环链表 这⾥的“带头”跟前⾯我们说的“头节点”是两个概念#xff0c;实际前⾯的在单链表阶段称呼不严 谨#xff0c;但是为了同学们更好的理解就直接称为单链表的头节点。 带头链表⾥的头节点#xff0c;实际…
一、双向链表的结构 注意双向链表又称带头双向循环链表 这⾥的“带头”跟前⾯我们说的“头节点”是两个概念实际前⾯的在单链表阶段称呼不严 谨但是为了同学们更好的理解就直接称为单链表的头节点。 带头链表⾥的头节点实际为“哨兵位”哨兵位节点不存储任何有效元素只是站在这⾥“放哨 的” “哨兵位”存在的意义 遍历循环链表避免死循环。 双向链表每个节点储存一个有效数据前驱指针后继指针 二、. 双向链表的实现
2.1 创建初始化
2.2.1 List.h
#pragma once
typedef struct ListNode
{int val;struct ListNode* next;struct ListNode* prev;}LTNode; //初始化
LTNode* LTInit();
2.2.2 List.c #define _CRT_SECURE_NO_WARNINGS
#includeList.h
#includestdlib.h
#includeassert.h
#includestdio.h
LTNode* LTInit()//哨兵位初始化
{LTNode* head (LTNode*)malloc(sizeof(LTNode));head-val -1;head-next head-prev head;return head;
} 2.2.3 text.c #define _CRT_SECURE_NO_WARNINGS
#includeList.h
#includestdio.h
int main()
{LTNode* head;headLTInit();return 0;
} 代码运行测试 2.2尾插头插
分析 尾插1.往d3节点的后面插入数据叫做尾插 2.往哨兵位head之前插入数据也叫尾插 头插
在哨兵位和头节点之间插入
2.2.1 List.h
//尾插
//1.往d3节点的后面插入数据叫做尾插 2.往哨兵位head之前插入数据也叫尾插
void LTPushBack(LTNode* head, int x);//打印
void LTPrint(LTNode* head);
//头插
void LTPushFront(LTNode* head, int x);
2.2.2 List.c
//创建新节点
LTNode* Listbuynode(int x)
{LTNode* node (LTNode*)malloc(sizeof(LTNode));node-val x;node-next node-prev NULL;return node;
}
void LTPushBack(LTNode* head, int x)
{LTNode* node Listbuynode(x);//对新节点进行操作node-next head;node-prev head-prev;//对原来的尾节点和哨兵位进行操作head-prev-next node;head-prev node;
}
void LTPrint(LTNode* head)
{assert(head);LTNode* pcur head-next;while (pcur ! head){printf(%d-, pcur-val);pcur pcur-next;}printf(\n);
}void LTPushFront(LTNode* head, int x)
{LTNode* node Listbuynode(x);//对新节点进行操作node-next head-next;node-prev head;//对哨兵位和头节点进行操作head-next-prev node;head-next node;
}
2.2.3 text.c
#define _CRT_SECURE_NO_WARNINGS
#includeList.h
#includestdio.h
int main()
{LTNode* head;headLTInit();LTPushBack(head, 1);LTPushBack(head, 2);LTPushBack(head, 3);LTPushFront(head,4);//4-1-2-3LTPrint(head);return 0;
}
2.3 头删尾删
2.3.1 List.h
//尾删
void LTPopBack(LTNode* head);//头删
void LTPopFront(LTNode* head);
2.3.2 List.c
void LTPopBack(LTNode* head)
{//链表为空不能删除assert(head);assert(head-next ! head);//将尾节点进行保存LTNode* del head-prev;//连接次尾节点和哨兵位del-prev-next head;head-prev del-prev;free(del);del NULL;}
void LTPopFront(LTNode* head)
{//链表为空不能删除assert(head);assert(head-next ! head);//将头节点进行保存LTNode* del head-next;//连接哨兵位和次头节点head-next del-next;del-next-prev head;free(del);del NULL;
}2.3.3 text.c
#define _CRT_SECURE_NO_WARNINGS
#includeList.h
#includestdio.h
int main()
{LTNode* head;headLTInit();LTPushBack(head, 1);LTPushBack(head, 2);LTPushBack(head, 3);LTPushFront(head, 4);LTPrint(head);//4-1-2-3LTPopFront(head);LTPrint(head);//1-2-3LTPopBack(head);LTPrint(head);1-2return 0;
}
2.4 查找数据在pos节点后插入数据删除pos节点
2.4.1 List.h //在pos位置之后插入数据
void LTInsert(LTNode* pos, int x);
//删除pos节点
void LTErase(LTNode* pos);//查找数据
LTNode* LTFind(LTNode* head, int x);
2.4.2 List.c
void LTInsert(LTNode* pos, int x)
{assert(pos);LTNode* node Listbuynode(x);//先处理新节点node-prev pos;node-next pos-next;//在处理前后节点pos-next node;node-next-prev node;
}LTNode* LTFind(LTNode* head, int x)
{assert(head);assert(head-next!head);LTNode* pcur head-next;while (pcur ! head){if (pcur-val x){return pcur;}pcur pcur-next;}return NULL;
}
void LTErase(LTNode* pos)
{assert(pos);pos-prev-next pos-next;pos-next-prev pos-prev;free(pos);pos NULL;
}
2.4.3 text.c
#define _CRT_SECURE_NO_WARNINGS
#includeList.h
#includestdio.h
int main()
{LTNode* head;headLTInit();LTPushBack(head, 1);LTPushBack(head, 2);LTPushBack(head, 3);LTPushBack(head, 4);//LTPopBack(head);//LTPrint(head);//LTPopBack(head);LTNode* find LTFind(head, 4);LTInsert(find, 11);LTPrint(head);//1-2-3-4-11LTErase(find);//1-2-3-11LTPrint(head);return 0;
}
2.5 销毁 若销毁接口用二级指针接受传哨兵位指针的地址那么可以改变哨兵位指针指向,使哨兵位指向NULL; 若销毁接口用一级指针接受传一级指针哨兵位指针传过去的形参是指针存储的地址不能够改变指针的指向在对形参操作可以释放哨兵位指向的地址空间形参的值为空间地址但是不能改变实参指针的指向实参依然指向原来被释放的地址空间需要手动将实参置为NULL. 简而言之若需要改变一级指针指向需要传二级指针。 前面都是用一级指针传参为了保持接口的一致性我们用一级指针传参
2.5.1 List.h
//销毁
void LTDestroy(LTNode* phead);
2.5.2 List.c
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur phead-next;LTNode* next pcur-next;while (pcur ! phead){free(pcur);pcur next;next next-next;}free(phead);phead NULL;
}2.5.3 text.c
#define _CRT_SECURE_NO_WARNINGS
#includeList.h
#includestdio.h
int main()
{LTNode* head;headLTInit();LTPushBack(head, 1);LTPushBack(head, 2);LTPushBack(head, 3);LTPushFront(head, 4);/*LTPrint(head);LTPopFront(head);*/LTPrint(head);//LTPopBack(head);//LTPrint(head);//LTPopBack(head);LTNode* find LTFind(head, 4);/*LTInsert(find, 11);*/LTErase(find);LTPrint(head);LTDestroy(head);head NULL;return 0;
}
2.6 完整代码
2.6.1 List.h
#pragma once
typedef struct ListNode
{int val;struct ListNode* next;struct ListNode* prev;}LTNode; //初始化
LTNode* LTInit();
//销毁
void LTDestroy(LTNode* phead);
//尾插
//1.往d3节点的后面插入数据叫做尾插 2.往哨兵位head之前插入数据也叫尾插
void LTPushBack(LTNode* head, int x);//打印
void LTPrint(LTNode* head);
//头插
void LTPushFront(LTNode* head, int x);//尾删
void LTPopBack(LTNode* head);//头删
void LTPopFront(LTNode* head);//在pos位置之后插入数据
void LTInsert(LTNode* pos, int x);
//删除pos节点
void LTErase(LTNode* pos);//查找数据
LTNode* LTFind(LTNode* head, int x);
2.6.2 List.c
#define _CRT_SECURE_NO_WARNINGS
#includeList.h
#includestdlib.h
#includeassert.h
#includestdio.h
LTNode* LTInit()//哨兵位初始化
{LTNode* head (LTNode*)malloc(sizeof(LTNode));head-val -1;head-next head-prev head;return head;
}
//创建新节点
LTNode* Listbuynode(int x)
{LTNode* node (LTNode*)malloc(sizeof(LTNode));node-val x;node-next node-prev NULL;return node;
}
void LTPushBack(LTNode* head, int x)
{LTNode* node Listbuynode(x);//对新节点进行操作node-next head;node-prev head-prev;//对原来的尾节点和哨兵位进行操作head-prev-next node;head-prev node;
}
void LTPrint(LTNode* head)
{assert(head);LTNode* pcur head-next;while (pcur ! head){printf(%d-, pcur-val);pcur pcur-next;}printf(\n);
}void LTPushFront(LTNode* head, int x)
{LTNode* node Listbuynode(x);//对新节点进行操作node-next head-next;node-prev head;//对哨兵位和头节点进行操作head-next-prev node;head-next node;
}
void LTPopBack(LTNode* head)
{//链表为空不能删除assert(head);assert(head-next ! head);//将尾节点进行保存LTNode* del head-prev;//连接次尾节点和哨兵位del-prev-next head;head-prev del-prev;free(del);del NULL;}
void LTPopFront(LTNode* head)
{//链表为空不能删除assert(head);assert(head-next ! head);//将头节点进行保存LTNode* del head-next;//连接哨兵位和次头节点head-next del-next;del-next-prev head;free(del);del NULL;
}void LTInsert(LTNode* pos, int x)
{assert(pos);LTNode* node Listbuynode(x);//先处理新节点node-prev pos;node-next pos-next;//在处理前后节点pos-next node;node-next-prev node;
}LTNode* LTFind(LTNode* head, int x)
{assert(head);assert(head-next!head);LTNode* pcur head-next;while (pcur ! head){if (pcur-val x){return pcur;}pcur pcur-next;}return NULL;
}
void LTErase(LTNode* pos)
{assert(pos);pos-prev-next pos-next;pos-next-prev pos-prev;free(pos);pos NULL;
}void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur phead-next;LTNode* next pcur-next;while (pcur ! phead){free(pcur);pcur next;next next-next;}free(phead);phead NULL;
}2.6.3 text.c
#define _CRT_SECURE_NO_WARNINGS
#includeList.h
#includestdio.h
int main()
{LTNode* head;headLTInit();LTPushBack(head, 1);LTPushBack(head, 2);LTPushBack(head, 3);LTPushFront(head, 4);/*LTPrint(head);LTPopFront(head);*/LTPrint(head);//LTPopBack(head);//LTPrint(head);//LTPopBack(head);LTNode* find LTFind(head, 4);/*LTInsert(find, 11);*/LTErase(find);LTPrint(head);LTDestroy(head);head NULL;return 0;
}
三、顺序表和双向链表的优缺点分析 不同点 顺序表 链表单链表 存储空间上 物理上一定连续 逻辑上连续但物理上不⼀定连续 随机访问 ⽀持O(1 不支持O(n) 任意位置插⼊或者删除元素 可能需要搬移元素效率低O(N) 只需修改指针指向 插入 动态顺序表空间不够时需要扩容 没有容量的概念 应⽤场景 元素⾼效存储频繁访问 任意位置插⼊和删除频繁
