数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。
数据:所有能被输入到计算机中,且能被计算机处理的符号的集合。是计算机操作的对象的总称。数据元素:数据(集合)中的一个“个体”,数据及结构中讨论的基本单位数据项:数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。数据类型:在一种程序设计语言中,变量所具有的数据种类。整型、浮点型、字符型等等逻辑结构:数据之间的相互关系。集合结构中的数据元素除了同属于一种类型外,别无其它关系。线性结构数据元素之间一对一的关系树形结构数据元素之间一对多的关系图状结构或网状结构结构中的数据元素之间存在多对多的关系物理结构/存储结构:数据在计算机中的表示。物理结构是描述数据具体在内存中的存储(如:顺序结构、链式结构、索引结构、哈希结构)等在数据结构中,从逻辑上可以将其分为线性结构和非线性结构数据结构的基本操作的设置的最重要的准则是,实现应用程序与存储结构的独立。实现应用程序是“逻辑结构”,存储的是“物理结构”。逻辑结构主要是对该结构操作的设定,物理结构是描述数据具体在内存中的存储(如:顺序结构、链式结构、索引结构、希哈结构)等。顺序存储结构中,线性表的逻辑顺序和物理顺序总是一致的。但在链式存储结构中,线性表的逻辑顺序和物理顺序一般是不同的。算法五个特性:有穷性、确定性、可行性、输入、输出算法设计要求:正确性、可读性、健壮性、高效率与低存储量需求。(好的算法)算法的描述有伪程序、流程图、N-S结构图等。E-R图是实体联系模型,不是程序的描述方式。设计算法在执行时间时需要考虑:算法选用的规模、问题的规模时间复杂度:算法的执行时间与原操作执行次数之和成正比。时间复杂度由小到大:O(1)、O(logn)、O(n)、O(nlogn)、O(n2)、O(n3)。幂次时间复杂度有小到大O(2n)、O(n!)、O(nn)空间复杂度:若输入数据所占空间只取决于问题本身,和算法无关,则只需要分析除输入和程序之外的辅助变量所占额外空间。
而对于算法的相关内容,我也把进行了整理,因为最近有粉丝在后台跟我说有没有什么算法的相关学习资料,这个东西,除了让他去刷题,我也想不到什么特别好的办法,尤其是像字节或者腾讯、谷歌这样对算法要求比较高的公司,还是让自己的算法能力强大一点吧
正好,这个时候有人跟我说,你可以整理一套知识体系,有一个复习方向啊,于是有了下面的这套思维导图
基础排序
基本涵盖常见的排序方式,每一个排序方式都会简单的标注排序方式、做法以及优化思路
数据结构
这个包含的比较多,包括递归、图、表、树、栈、队列
不过呢?这些再整理,那是我自己的,只有形成自己的知识体系才会是你自己的,不然以后再面试或者用到,你还是要翻江倒海的去翻找资料,而且因为是自己整理了自己看,只是作为一个目录的或者总结的形式来用
目录
冒泡排序
冒泡排序算法运行起来非常慢,但在概念上它是排序算法中最简单的,因此排序算法在刚开始研究排序技术时是一个非常好的算法。
递归
递归是一种方法(函数)调用自己的编程技术。这听起来似乎有点奇怪,或者甚至像是一个灾难性的错误。但是,递归在编程中却是最有趣,又有惊人高效的技术之一。就像拽着自己的鞋带拔高一样(你确实有鞋带,是吗?),在第一次遇到递归时,它似乎让人觉得难以置信。然而,递归不仅可以解决特定的问题,而且它也为解决很多问题提供了一个独特的概念上的框架。
树
为什么要用到树呢?因为它通常结合了另外两种数据结构的优点/p>
有序数组,链表。在树中查找数据项的速度和在有序数组中查找一样快,并且插入数据项和删除数据项的速度也和链表--样。下面,我们先来稍微思考一下这些话题,然后再深入地研究树的细节。
表
哈希表是一种数据结构,它可以提供快速的插入操作和查找操作。第一次接触哈希表时,它的优点多得让人难以置信。不论哈希表中有多少数据,插入和删除(有时包括删除)只需要接近常量的时间:即0(1)的时间级。实际上,这只需要几条机器指令。
对哈希表的使用者一人来说,这是一瞬间的事。哈希表运算得非常快,在计算机程序中,如果需要在一内查找上千条记录,通常使用哈希表(例如拼写检查器)。哈希表的速度明显比树快,正如前面几章看到的,树的操作通常需要O(N)的时间级。哈希表不仅速度快,编程实现也相对容易。
哈希表也有一些缺点:它是基于数组的,数组创建后难于扩展。某些哈希表被基本填满时,性能下降得非常严重,所以程序员必须要清楚表中将要存储多少数据(或者准备好定期地把数据转移到更大的哈希表中,这是个费时的过程)。
图
在计算机程序设计中,图是最常用的结构之一。一般来说,用图来帮助解决的问题类型与本书中已经讨论过的问题类型有很大差别。如果处理一般的数据存储问题,可能用不到图,但对某些问题(经常是一些有趣的问题),图是必不可少的
因为篇幅原因,我就整理展示这一些,需要这份资料的,