网站内链404 not found,网站运营托管,做网站投入,旅游软件排行榜前十名简介 数据结构的本质#xff0c;只有两种结构#xff0c;数组与链表。其它的都是它的衍生与组合算法的本质就是穷举。 数组 数组可以分为两大类#xff0c;静态数组与动态数组。静态数组的本质是一段连续的内存#xff0c;因为是连续的#xff0c;所以我们可以采用偏移量的…简介 数据结构的本质只有两种结构数组与链表。其它的都是它的衍生与组合算法的本质就是穷举。 数组 数组可以分为两大类静态数组与动态数组。静态数组的本质是一段连续的内存因为是连续的所以我们可以采用偏移量的方式来对元素实现快速访问。而动态数组则是对静态数组的封装使得更加方便操作元素。有了动态数组后续的栈哈希队列都能更加优雅的实现。 静态数组 数组的超能力随机访问。只要任意一个索引都能推测出元素的内存地址而计算机的内存寻址能力为Log(1),所以数组的随机访问时间复杂度也同样为Log(1) 数组的局限性由于数组的大小是固定的所以当数组满了或者需要在中间插入/删除时。都需要移动元素这时候时间复杂度就上升为Log(N) 动态数组 动态数组无法解决静态数组Log(N)的问题它只是帮你隐藏了动态扩容与元素搬移的过程以及更加易用的API。 数组随机访问的超能力源于数组连续的内存空间而连续的内存空间就不可避免地面对元素搬移和扩缩容的问题 一个简单的动态数组 public class MyListT(){//真正存储数据的底层private T[] arr new T[5];//记录元素的数量public int Count { get; private set; }/// summary/// 增/// /summary/// param nameitem/parampublic void Add(T item){if (Count arr.Length){//扩容Resize(Count * 2);}arr[Count] item;Count;}/// summary/// 删/// /summary/// param nameidx/parampublic void RemoveAt(int idx){if (Count arr.Length / 4){//缩容Resize(arr.Length / 2);}Count--;for (int i idx; i Count; i){arr[i] arr[i 1];}arr[Count] default(T);}public void Remove(T item){var idx FindIndex(item);RemoveAt(idx);}/// summary/// 改/// /summary/// param nameidx/param/// param namenewItem/parampublic void Put(int idx,T newItem){arr[idx] newItem;}/// summary/// 查/// /summary/// param nameitem/param/// returns/returnspublic int FindIndex(T item){for(int i 0; i arr.Length; i){if (item.Equals(arr[i]))return i;}return -1;}/// summary/// 扩容/缩容操作/// /summary/// param nameinitCapacity/paramprivate void Resize(int initCapacity){var newArraynew T[initCapacity];for(var i 0; i Count; i){newArray[i] arr[i];}arr newArray;}} 数组的变种环形数组 有人可能会问了数组不是一段连续的内存吗怎么可能是环形的从物理角度出发这确实不可能。但从逻辑角度出发这是有可能的。其核心内容就是利用求模运算 public static void Run(){var arr new int[] { 1, 2, 3, 4, 5, 6 };var i 0;while (arr.Length 0){Console.WriteLine(arr[i]);//关键代码在此当i遍历到末尾时i1与arr.Length去余数变成0//从逻辑上完成了闭环i (i 1) % arr.Length;if ((i % arr.Length) 0){Console.WriteLine(完成了一次循环i归零);Thread.Sleep(1000);}}} 环形数组的关键在于它维护了两个指针 start 和 endstart 指向第一个有效元素的索引end 指向最后一个有效元素的下一个位置索引环形数组解决了什么问题数组在头部增删从O(N)优化为O(1) 链表 链表分为单链表与双链表单链表只有一个指针指向next元素。双链表有两个指针分别指向previous与next。除此之外并无其它区别。主要功能区别在于能否向前遍历。 为什么需要链表 前面说到数组的本质是一段连续的内存当元素移动/扩容时需要one by one 移动花销很大。那有没有一种能突破内存限制的数据结构呢链表就应运而生。链表不需要连续内存它们可以分配在天南海北它们之间的联系靠next/prev链接将零散的元素串成一个链式结构。 这么做有两个好处 提高内存利用率分配在哪都可以。所以可以降低内存碎片 方便扩容与移动只需要重新指向next/previous 即可实现增删改等操作无需移动元素与扩容。 但万物皆有代价因为链表的不连续性所以无法利用快速随机访问来定位元素只能一个一个的遍历来确定元素。因此链表的查询复杂度为Log(N) 一个简单的链表 public class MyLinkedListT
{public static void Run(){var linked new MyLinkedListstring();linked.AddLast(a);linked.AddLast(b);linked.AddLast(c);linked.AddLast(d);linked.Add(1, bc);linked.Put(1, aaaa);Console.WriteLine(linked.ToString()) ;}/// summary/// 虚拟头尾节点,有两个好处/// 1.无论链表是否为空 两个虚拟节点都存在避免很多边界值处理的情况。/// 2.如果要在尾部插入数据如果不知道尾节点那么需要复杂度退化成O(N),因为要从头开始遍历到尾部。/// /summaryprivate Node _head, _tail; public int Count { get; private set; }public MyLinkedList(){_tail new Node();_head new Node();_head.Next _tail;_tail.Prev _head;}public void AddLast(T item){var prev _tail.Prev;var next _tail;var node new Node(item);node.Next next;node.Prev prev;prev.Next node;next.Prev node;Count;}public void AddFirst(T item){var prev _head;var next _head.Next;var nodenew Node(item);node.Prev prev;node.Next next;prev.Next node;next.Prev node;Count;}public void Add(int idx,T item){var t Get(idx);var next t.Next;var prev t;var node new Node(item);node.Next next;node.Prev prev;prev.Next node;next.Prev node;}public void Remove(int idx){var t Get(idx);var prev t.Prev;var next t.Next;prev.Next next;next.Prev next;t null;Count--;}public void Put(int idx,T item){var t Get(idx);t.Value item;}private Node? Get(int idx){var node _head.Next;//这里有个优化空间可以通过idx在Count的哪个区间。从而决定从head还是从tail开始遍历for (int i 0; i idx; i){node node.Next;}return node;}public override string ToString(){var sb new StringBuilder();var node _head.Next;while (node ! null node.Value ! null){sb.Append(${node.Value}-);node node.Next;}sb.Append(null);return sb.ToString();}private class Node{public T? Value { get; set; }public Node Next { get; set; }public Node Prev { get; set; }public Node(){Valuedefault(T);}public Node(T value){Value value;}}
} 链表的变种跳表 在上面简单的例子中查询的复杂度为O(N),插入的复杂度为O(1).主要消耗在查询操作只能从头结点开始逐个遍历到目标节点。所以我们优化的重点就在于优化查询。 上面的例子中我们使用了虚拟头尾节点来空间换时间提高插入效率。同样的我们也可以采用这个思路来提高查询效率 跳表核心原理 index 0 1 2 3 4 5 6 7 8 9
node a-b-c-d-e-f-g-h-i-j 此时此刻你想拿到h的节点你需要从0开始遍历直到7。这时候你就想如果我能提前知道6的位置就好了这样我就只需要Next就能快速得到h 调表就是如此 indexLevel 0-----------------------8-----10
indexLevel 0-----------4-----------8-----10
indexLevel 0-----2-----4-----6-----8-----10
indexLevel 0--1--2--3--4--5--6--7--8--9--10
nodeLevel a-b-c-d-e-f-g-h-i-j-k 调表在原链表的基础上增加了多层索引每向上一层索引减少一半所以索引的高度是O(log N) 首先从最高层索引开始往下搜索引7在[0,8]区间 从节点0开始发现7在【4,8】拿到节点4的地址 从节点4开始发现7在【6,8】拿到节点6的地址 从节点6开始发现7在【6,7】最终找到节点7 在搜索的过程中会经过O(log N)层索引所以时间复杂度为O(log N) 调表实现比较复杂当新增与删除时还需考虑索引的动态调整需要保证尽可能的二分否则时间复杂度又会退化为O(N)有点类似自平衡的二叉搜索数不过相对来说比较简单。 文章转载自叫我安不理 原文链接重生之数据结构与算法----数组链表 - 叫我安不理 - 博客园 体验地址引迈 - JNPF快速开发平台_低代码开发平台_零代码开发平台_流程设计器_表单引擎_工作流引擎_软件架构
