首页 > 代码库 > 数据结构—基础知识

数据结构—基础知识

首先了解一下数据结构中的概念(仅仅为了对其有了感性认识)

数据:描写叙述客观事物的符号,是计算机中可以操作的对象,可以被计算机识别,并输入给计算机处理的集合符号。

数据不只包含数值。还包含视频、音频、图片等等

数据元素:是组成数据的、具有一定意义的基本单位。在计算机中通常作为一个总体进行处理,也称为记录。

数据项:一个数据元素由若干个个数据项组成。

能够将数据元素理解我数据库中的一条记录,而数据项使其相应的属性。数据项是数据不可切割的最小单位。数据项是数据的最小单位。数据元素是数据结构中讨论的最小单位。

数据对象:是性质同样数据元素的集合,是数据的子集。

那么什么是数据结构呢?

是相互之间存在一种或多种特定关系的集合。


数据>数据对象>数据元素>数据项


依照视点不同,能够将数据结构能够分为逻辑结构和物理结构

逻辑结构:数据对象中数据元素之间的相互关系。

逻辑结构|

                |—集合结构:集合结构中,数据元素除了同属一个集合,没有其它关系

                |—线性结构:线性结构中数据元素之间是一对一的关系

                |—树结构:树结构之间的数据元素是一对多关系

                |—图结构:图结构之间的数据元素是多对多的关系

物理结构:数据的逻辑结构在计算机中的存储形式

物理结构|

                |—顺序存储结构:把数据元素存放到放到地址连续的存储单元中,其数据间的逻辑关系和物理关系一致。

                |—链接存储结构:把数据元素存放在随意的存储单元里,这组存储单元能够是连续的。也能够是不连续的。


抽象数据类型(Abstract Data Type)ADT

数据类型:一组性质同样的值的集合及其定义在该集合上的一些操作。

什么叫做抽象?

抽取事物具有的普遍性的本质。抽取出问题的特征忽略非本质的细节。是对事物的一个概括。

what is ADT?

是指一个数学模型。及其定义在该模型上的操作。

他包含数据及其对数据的操作。

ADT 抽象数据类型名

Data

        数据元素之间的逻辑关系的定义

Operation

        操作1

                 初始化条件

                 操作结果描写叙述

        操作2

                 ......

        操作n

                 .......

endADT

抽象数据类型体现了:问题分解、抽象和信息隐藏。


什么是算法?

解决特定问题求解步骤的描写叙述。在计算机中表示为指令的有序序列,而且每一个指令表示一个或多个操作。

算法的特性:输入输出、有穷性、确定性、可行性

算法的度量—时间复杂度

进行算法分析是,总的语句运行次数T(n)是关于n的函数。进而分析T(n)随n的变化情况并确定数量级。

算法时间复杂度用O(f(n))表示,表示随着问题规模n的增大。算法运行时间的增长率和f(n)的增长率同样,所以称为算法的渐进时间复杂度,简称时间复杂度。

求取算法时间复杂度:

推到大O阶:

1、用常数1代替执行时间中的全部加法常数

2、改动后的执行次数函数中,仅仅保留最高阶项

3、去除与这个最高项的相乘的常数

经常使用的时间复杂度排序:

O(1)<O(logn)<O(nlogn)<O(n2)【n的2次方】<O(n3)【n的三次方】<O(2n) 【2的n次方】<O(n!)<O(nn)【n的n次方】

一般我们指的是最坏时间复杂度

数据结构—基础知识