Algorithm-Linked List

链表:线性表的链式存储结构。

链表的创建:链表创建的时候要有一个节点永远指向链表的头节点或者首元节点,防止链表丢失。
头节点:一个不存储或者存储链表长度的节点。
首元节点:链表第一个存储数据的节点。

链表节点的添加:链表添加新节点需要
(1)创建新节点,把新节点的next指向插入位置的下一个节点
(2)把插入位置的上一个节点的next指向新节点。
注意:如果不保存插入位置后的节点,那么那些节点将会丢失。因为链表不是顺序存储,你将会把那些节点丢失在内存中。

链表节点的删除:链表删除节点需要
(1)创建一个临时节点用于保存需要删除的节点
(2)把删除节点的上一节点的next指向删除节点的下一个节点。
注意:如果不使用临时节点来保存删除节点,那么删除节点将会丢失。删除的节点需要通过free释放,否则将造成内存泄漏。

C代码:

Algorithm-BinaryHeap

二叉堆:二叉堆是一个完全二叉树或者近似二叉树的一种堆结构,一般分为大顶堆和小顶堆。所谓的大顶堆就是父节点的值大于左右子节点且堆顶是值最大的元素,而小顶堆相反,堆顶为最小元素。

二叉堆的删除:删除堆顶元素,并且把最末尾元素放到堆顶,再依据大/小顶堆的规则调整整个堆结构。
思路:遍历节点并进行判断。
<1>如果该节点的左子节点存在,右子节点不存在,那么删除左子节点,并将左子节点值赋予根节点;
<2>如果该节点的右子节点存在,而该节点的下一个(相邻)节点的左子节点不存在,那么删除该节点的右子节点,并将右子节点的值赋予根节点;
最后进行二叉堆重建,恢复到小/大顶堆的状态。

二叉堆的添加:把元素添加到最末尾,再根据大/小顶堆的结构调整整个堆。

二叉堆的重建:通过递归遍历节点,并比较父节点与子节点的值根据大/小顶堆的规则进行交换,直至遍历完所有节点并且符合该堆的规则。

Python3代码实现: