数据结构主要研究数据元素之间的关系。
既然数据结构是研究数据元素之间的基本关系,那基本关系如何表示呢?逻辑结构就是根据数据元素之间关系的不同特性,分为了4类基本结构
定义好了逻辑结构,我们能进行什么操作呢?数据的运算就是结合逻辑结构以及实际需求来定义的基本运算,举个栗子🌰,我们定义一个线性表的结构,可以进行的数据运算有查找,增加,删除等等
我们定义好了逻辑结构,又想好了该需要有哪些运算,那如何在计算机中实现呢?那这里给出四种基本方法
其中后三者都是非顺序存储的。以上:逻辑结构,数据的运算以及物理结构就是数据结构的三要素
先挑熟悉的说:数据类型。相信在学习C语法的时候我们对数据类型已经很熟悉了,常用的int型,float型,char型都是数据类型。这里我们给出一个通俗的定义,我们只关注其中两个东西,即这个数据类型的值的范围以及可进行的操作。还是举个栗子🌰,就拿bool型来说,值的范围是0,1,可进行的操作是:与、或、非等基本逻辑运算。
看完数据类型,抽象数据类型也很容易理解了,还是先给出一个不太通俗的定义:抽象数据类型是 抽象数据组织 以及 与之相关的操作。通俗点讲就是站在使用者的角度,我只需要知道这个数据元素之间是什么结构关系,以及可以执行什么操作。
我们知道,程序 = 数据结构 + 算法。在上面提到,数据结构是如何用数据描述现实世界,然后存进计算机,那么算法通俗点讲就是:如何处理这些数据来解决问题。
算法的5个特性(缺一不可)
有了上面5个特性,我们才可以说它是一个算法。那么从一个算法进化到一个好的算法又需要什么呢?
空间复杂度,顾名思义,就是这个程序运行时需要的内存需求,想知道它需要多少内存,我们应该先知道,一个程序在运行时,哪些东西需要占用内存。那么无非就是两个东西,即:
所以对于非递归程序,找到和所占空间大小相关的变量分析即可
对于递归程序,因为每次调用一遍递归函数都要占用新的空间,所以在分析递归程序的空间复杂度时,要找到递归调用的深度和问题规模n的关系。调用深度x的数量级就是空间复杂度
事后统计的问题
一言概之,受太多外界因素的影响
一般只考虑算法的最坏时间复杂度和平均时间复杂度。