python大型网站开发,如何进行电子商务网站推广,wordpress文章内容编辑器,WordPress编辑器高亮系列文章目录 文章目录系列文章目录前言一、哨兵位的头节点二、双向链表的结点三、接口函数的实现1、创建结点2、初始化3、尾插与尾删4、头插与头删5、打印6、查找7、随机插入与随机删除8、判空、长度与销毁四、顺序表和链表的对比1. 不同点2. 优缺点五、缓存命中1、缓存2、缓存…系列文章目录 文章目录系列文章目录前言一、哨兵位的头节点二、双向链表的结点三、接口函数的实现1、创建结点2、初始化3、尾插与尾删4、头插与头删5、打印6、查找7、随机插入与随机删除8、判空、长度与销毁四、顺序表和链表的对比1. 不同点2. 优缺点五、缓存命中1、缓存2、缓存命中总结前言
一般题目给的单链表是无头单向非循环链表但是我们可以升级成双向带头循环链表这个链表比起单链表更有优势。 一、哨兵位的头节点 上面带有head头结点的链表就是带头的链表题目中的链表一般没有头节点phead指针直接指向第一个结点而带头的链表phead指针指向头结点头节点指向第一个结点一般称为 哨兵位的头节点。
二、双向链表的结点
typedef int LTDataType;typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;比起单链表的结点多了指向前一个结点的指针——prev。
三、接口函数的实现
1、创建结点
LTNode* BuyListNode(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));assert(newnode);newnode-next NULL;newnode-prev NULL;newnode-data x;return newnode;}2、初始化
LTNode* InitList()
{LTNode* phead BuyListNode(-1);phead-next phead;phead-prev phead;return phead;
}初始化即开辟一个头节点然后让这个头节点的前后指针域都指向自己。
3、尾插与尾删 void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode BuyListNode(x); newnode-prev phead-prev;phead-prev-next newnode;newnode-next phead;phead-prev newnode;
}void LTPopBack(LTNode* phead)
{assert(phead);assert(phead-next ! phead);//空phead-prev phead-prev-prev;free(phead-prev-next);phead-prev-next phead;}双向带头循环链表并没有单独讨论空链表的情况这就是头节点的好处之所以不用讨论就是因为节点的个数不可能为0最少也包括一个头节点。
4、头插与头删 void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode BuyListNode(x);LTNode* tail phead-next;newnode-next phead-next;newnode-prev phead;tail-prev newnode;phead-next newnode;}void LTPopFront(LTNode* phead)
{assert(phead);assert(phead-next ! phead);LTNode* tail phead-next-next;LTNode* tailPrev phead-next;phead-next tail;tail-prev phead;free(tailPrev);} 5、打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){printf([%p | %d | %p], cur-prev, cur-data, cur-next);if(cur-next ! phead)printf(-);cur cur-next;}printf(\n);
}就是从头遍历一遍即可但是需要注意的是这是一个循环链表如果我们不加限制条件的话他会一直循环下去。所以我们这里需要加上判断条件。
6、查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);assert(phead-next ! phead);LTNode* cur phead-next;while (cur-data ! x cur ! phead)cur cur-next;if (cur phead)return NULL;else return cur;
}也要加限制条件。
7、随机插入与随机删除
void* LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode BuyListNode(x);LTNode* tail pos-prev;tail-next newnode;newnode-next pos;newnode-prev tail;pos-prev newnode;
}void* LTErase(LTNode* pos)
{assert(pos);LTNode* tail pos-prev;tail-next pos-next;tail-next-prev tail;free(pos);
}实现方式之前的头尾操作一样也可以复用到头尾操作中。
8、判空、长度与销毁
bool LTEmpty(LTNode* phead)
{assert(phead);return phead-next ! phead;
}size_t LTSize(LTNode* phead)
{assert(phead);LTNode* cur phead-next;size_t size 0;while (cur ! phead){size;cur cur-next;}return size;
}void LTDestory(LTNode* phead)
{LTNode* cur phead-next;while (cur ! phead)LTErase(cur);free(phead);
}逐个释放就行。
四、顺序表和链表的对比
1. 不同点
不同点顺序表链表存储空间上物理上一定连续逻辑上连续但物理上不一定连续随机访问支持O(1)不支持O(N)任意位置插入或者删除元素可能需要搬移元素效率低O(N)只需修改指针指向插入动态顺序表空间不够时需要扩容没有容量的概念应用场景元素高效存储频繁访问任意位置插入和删除频繁缓存利用率高低
2. 优缺点
顺序表: 优点尾插尾删效率高下标的随机访问。 缺点空间不够需要扩容扩容的代价大头部或者中间插入删除效率低需要挪动数据。
链表: 优点需要扩容按需申请释放小块结点内存任意位置插入效率很高–O(1)。 缺点不支持下标随机访问
五、缓存命中
1、缓存
CPU与内存经常有数据的访问与存储但两者运行速度不同就导致了CPU会“等待”内存传输数据的情况我们在二者之间搭建一片缓冲区域即缓存来解决这个问题。 从下到上各种存储器的内存逐渐降低数据传输速度逐级增高。
2、缓存命中
那么每次CPU会从寄存器中读取数据这二者的速度差距已经大大缩小了。我们以一个数组为例我们想对第一个元素进行计算我们不仅会把第一个元素所对的内存传输到寄存器还会把其相邻的内存空间传输到寄存器中作为备用每次传输到寄存器中的数据的大小取决于电脑的相应配置。 这样我们在CPU访问完第一元素后假设我们还需要计算第二个元素我们又恰好在寄存器中存储了第二个元素的内存信息。CPU便可直接调用而无需寄存器再去读取。这就叫缓存命中。 总结
链表和顺序表各有优势带头双向链表比起单链表更加方便操作。
深窥自己的心而后发觉一切的奇迹在你自己。——培根
