懂了数据结构结构思想，抚育算法不过是纸老虎-人工智能-知优网

数据结构的存储方式只有两种：数组(顺序存储)和链表(链式存储)。这句话怎么理解，不是还有散列表、栈、队列、堆、树、图等等各种数据结构吗?

一、数据结构的存储办法

数据结构的存储办法只需两种：数组(次序存储)和链表(链式存储)。

这句话怎样了解，不是还有散列表、栈、行列、堆、树、图等等各种数据结构吗?

咱们剖析问题，必定要有递归的思想，自顶向下，从笼统到详细。你上来就列出这么多，那些都归于「上层建筑」，而数组和链表才是「结构根底」。拜访那些多样化的数据结构，究其源头，都是在链表或许数组上的特别操作，API 不同罢了。

比方说「行列」、「栈」这两种数据结构既可以运用链表也可以运用数组完成。用数组完成，就要处理扩容缩容的问题;用链表完成，没有这个问题，但需求更多的内存空间存储节点指针。

「图」的两种表明办法，邻接表便是链表，邻接矩阵便是二维数组。邻接矩阵判别连通性敏捷，并可以进行矩阵运算处理一些问题，可是假如图比较稀少的话很耗费空间。邻接表比较节省空间，可是许多操作的功率上必定比不过邻接矩阵。

「散列表」便是经过散列函数把键映射到一个大数组里。并且关于处理散列抵触的办法，拉链法需求链表特性，操作简略，但需求额定的空间存储指针;线性探查法就需求数组特性，以便接连寻址，不需求指针的存储空间，但操作略微杂乱些。

「树」，用数组完成便是「堆」，拜访「堆」是一个彻底二叉树，用数组存储不需求节点指针，操作也比较简略;用链表完成便是很常见的那种「树」，拜访不必定是彻底二叉树，所以不适合用数组存储。为此，在这种链表「树」结构之上，又衍生出各种奇妙的规划，比方二叉查找树、AVL 树、红黑树、区间树、B 树等等，以应对不同的问题。

了解 Redis 数据库的朋友或许也知道，Redis 供给列表、字符串、调集等等几种常用数据结构，可是关于每种数据结构，底层的存储办法都至少有两种，以便于依据存储数据的实际情况运用适宜的存储办法。

综上，数据结构品种许多，乃至你也可以创造自己的数据结构，可是底层存储无非数组或许链表，二者的优缺点如下：

数组由所以紧凑接连存储,可以随机拜访，经过索引快速找到对应元素，并且相对节省存储空间。但正拜访接连存储，内存空间有必要一次性分配够，所以说数组假如要扩容，需求重新分配一块更大的空间，再把数据悉数仿制曩昔，时刻杂乱度 O(N);并且你假如想在数组中心进行刺进和删去，每次有必要搬移后边的一切数据以坚持接连，时刻杂乱度 O(N)。

链表拜访元素不接连，而是靠指针指向下一个元素的方位，所以不存在数组的扩容问题;假如知道某一元素的前驱和后驱，操作指针即可删去该元素或许刺进新元素，时刻杂乱度 O(1)。可是正拜访存储空间不接连，你无法依据一个索引算出对应元素的地址，所以不能随机拜访;并且拜访每个元素有必要存储指向前后元素方位的指针，会耗费相对更多的贮存空间。

二、数据结构的底子操作

关于任何数据结构，其底子操作无非遍历 + 拜访，再详细一点便是：增删查改。

数据结构品种许多，但它们存在的意图都是在不同的使用场景，尽或许高效地增删查改。话说这不便是数据结构的任务么?

怎样遍历 + 拜访?咱们仍然从最高层来看，各种数据结构的遍历 + 拜访无非两种办法：线性的和非线性的。

线性便是 for/while 迭代为代表，非线性便是递归为代表。再详细一步，无非以下几种结构：

数组遍历结构，典型的线性迭代结构：

voidtraverse(int[]arr){for(inti=0;i<arr.length;i++){//迭代拜访arr[i]}}

链表遍历结构，兼具迭代和递归结构：

/*底子的单链表节点*/classListNode{intval;ListNodenext;}
voidtraverse(ListNodehead){for(ListNodep=head;p!=null;p=p.next){//迭代拜访p.val}}
voidtraverse(ListNodehead){//递归拜访head.valtraverse(head.next);}

二叉树遍历结构，典型的非线性递归遍历结构：

/*底子的二叉树节点*/classTreeNode{intval;TreeNodeleft,right;}
voidtraverse(TreeNoderoot){traverse(root.left);traverse(root.right);}

你看二叉树的递归遍历办法和链表的递归遍历办法，类似不?再看看二叉树结构和单链表结构，类似不?假如再多几条叉，N 叉树你会不会遍历?

二叉树结构可以扩展为 N 叉树的遍历结构：

/*底子的N叉树节点*/classTreeNode{intval;TreeNode[]children;}
voidtraverse(TreeNoderoot){for(TreeNodechild:root.children)traverse(child);}

N 叉树的遍历又可以扩展为图的遍历，拜访图便是好几 N 叉棵树的结合体。你说图是或许呈现环的?这个很好办，用个布尔数组 visited 做符号就行了，这儿就不写代码了。

所谓结构，便是套路。不论增删查改，这些代码都是永久无法脱离的结构，你可以把这个结构作为纲要，依据详细问题在结构上增加代码就行了，下面会详细举例。

三、算法刷题攻略

首先要清晰的是，数据结构是东西，算法是经过适宜的东西处理特定问题的办法。也便是说，学习算法之前，最最少得了解那些常用的数据结构，了解它们的特性和缺点。

那么该怎样在 LeetCode 刷题呢?之前的文章算法学习之路写过一些，什么按标签刷，坚持下去如此。现在距那篇文章现已曩昔将近一年了，我不说那些不痛不痒的话，直接说详细的主张：

先刷二叉树，先刷二叉树，先刷二叉树!

这是我这刷题一年的亲自领会，下图是上一年十月份的提交截图：

大众号文章的阅览数据显现，大部分人对数据结构相关的算法文章不感兴趣，而是更关心动规回溯分治等等技巧。为什么要先刷二叉树呢，拜访二叉树是最简单培育结构思想的，并且大部分算法技巧，本质上都是树的遍历问题。

刷二叉树看到标题没思路?依据许多读者的问题，其实咱们不是没思路，仅仅没有了解咱们说的「结构」是什么。不要小看这几行破代码，简直一切二叉树的标题都是一套这个结构就出来了。

voidtraverse(TreeNoderoot){//前序遍历traverse(root.left)//中序遍历traverse(root.right)//后序遍历}

比方说我随意拿几道题的解法出来，不必管详细的代码逻辑，只需看看结构在其间是怎样发挥作用的就行。

LeetCode 124 题，难度 Hard，让你求二叉树中最大途径和，首要代码如下：

intans=INT_MIN;intoneSideMax(TreeNode*root){if(root==
nullptr)return0;intleft=max(0,oneSideMax(root->left));
intright=max(0,oneSideMax(root->right));ans=max(ans,left
+right+root->val);returnmax(left,right)+root->val;}

你看，这便是个后序遍历嘛。

LeetCode 105 题，难度 Medium，让你依据前序遍历和中序遍历的成果复原一棵二叉树，很经典的问题吧，首要代码如下：

TreeNodebuildTree(int[]preorder,intpreStart,intpreEnd,int[]inorder,intinStart,intinEnd,Map<Integer,Integer>inMap){
if(preStart>preEnd||inStart>inEnd)returnnull;
TreeNoderoot=newTreeNode(preorder[preStart]);intinRoot=inMap.get(root.val);intnumsLeft=inRoot-inStart;
root.left=buildTree(preorder,preStart+1,preStart+numsLeft,inorder,inStart,inRoot-1,inMap);root.right=buildTree(preorder,preStart+numsLeft+1,preEnd,inorder,inRoot+1,inEnd,inMap);returnroot;}

不要看这个函数的参数许多，仅仅为了操控数组索引罢了，本质上该算法也便是一个前序遍历。

LeetCode 99 题，难度 Hard，康复一棵 BST，首要代码如下：

voidtraverse(TreeNode*node){if(!node)return;
traverse(node->left);if(node->val<prev->val){s=(s
==NULL)?prev:s;t=node;}prev=node;
traverse(node->right);}

这不便是个中序遍历嘛，关于一棵 BST 中序遍历意味着什么，应该不需求说明了吧。

你看，Hard 难度的标题不过如此，并且还这么有规则可循，只需把结构写出来，然后往相应的方位加东西就行了，这不便是思路吗。

关于一个了解二叉树的人来说，刷一道二叉树的标题花不了多长时刻。那么假如你对刷题无从下手或许有害怕心思，无妨从二叉树下手，前 10 道或许有点难过;结合结构再做 20 道，或许你就有点自己的了解了;刷完整个专题，再去做什么回溯动规分治专题，你就会发现只需触及递归的问题，都是树的问题。

再举例吧，说几道咱们之前文章写过的问题。

动态规划详说明过凑零钱问题，暴力解法便是遍历一棵 N 叉树：

defcoinChange(coins:List[int],amount:int):
defdp(n):ifn==0:return0ifn<0:return-1
res=float('INF')forcoinincoins:subproblem=dp(n-coin)#子问题无解，越过ifsubproblem==-1:continueres=min(res,1+subproblem)returnresifres!=float('INF')else-1
returndp(amount)

这么多代码看不懂咋办?直接提取出结构，就能看出中心思路了：

#不过是一个N叉树的遍历问题罢了defdp(n):forcoinincoins:dp(n-coin)

其实许多动态规划问题便是在遍历一棵树，你假如对树的遍历操作纯熟于心，最少知道怎样把思路转化成代码，也知道怎样提取他人解法的中心思路。

再看看回溯算法，前文回溯算法详解爽性直接说了，回溯算法便是个 N 叉树的前后序遍历问题，没有破例。

比方 N 皇后问题吧，首要代码如下：

/*底子的单链表节点*/classListNode{intval;ListNodenext;}
voidtraverse(ListNodehead){for(ListNodep=head;p!=null;p=p.next){//迭代拜访p.val}}
voidtraverse(ListNodehead){//递归拜访head.valtraverse(head.next);}
0