Java教程

数据结构基础1

本文主要是介绍数据结构基础1,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

数据结构
数据对象是具有相同性质(特征)的数据的集合
数据元素是数据的基本单位通常作为一个整体进行考虑和处理。(记录,数据元)
数据项由若干数据项组成,数据项是构成数据元素的不可分割的最小单位。(数据域、字段、列、属性)
数据类型是一个值的集合和定义在此集合上的一组操作的总称。
1)原子类型
其值不可再分的数据类型,如整数(int),字符char,浮点数float
2)结构类型
其值可以再分解为若干成分(分量)的数据类型
数据结构的三要素:逻辑结构,物理结构、存储结构,数据的运算
逻辑结构是组织数据的方法,物理结构是存储数据的方法,数据的运算是操作数据的方法。

逻辑结构研究的是数据之间的逻辑关系,是组织数据元素的方式,与物理存储(内存和磁盘)无关。
逻辑结构分为集合、线性结构、树形结构、图形结构(网状结构)也可以同意的分为线性结构和非线性结构。
集合:集合中任何数据元素之间都没有逻辑关系,组织形式松散。
线性结构,开始结点和终端结点都是唯一的,第一个结点认为是开始结点,最后一个结点认为是终端结点,除了开始结点和终端结点以外,其余结点都有且仅有一个前驱结点,有且仅有一个后继结点。
树形结构:开始结点和终端结点不唯一,开始结点就是指的根结点,终端结点就是指的最下面的结点。
图形结构:没有开始结点和终端结点。

物理结构指数据及其逻辑关系在计算机(内存和磁盘)中存储的方式,不同的计算语言实现的方式可能不同。
物理结构分为顺序存储、链式存储、索引存储、散列存储
把数据元素存放在任意的存储单元里,存储单元可以是连续的,也可以不连续。数据元素的存储关系并不能反映其逻辑关系,因此需要用一个指针存放后继结点的地址,通过地址就可以知道后继数据元素的位置。
索引存储的方法就像书的目录。
散列存储,根据元素的关键字直接计算出该元素的存储地址,又称哈希(Hash)存储。优点是检索、增加和删除结点的操作都很快;缺点是如果散列函数不好,可能出现元素存储单元的冲突,而解决冲突会增加时间和空间的开销。

数据的运算:

抽象数据类型(Abstract Data Type,ADT)
ADT是指一个数据模型一级定义在该模型上的一组操作。
抽象数据类型=逻辑结构+数据运算的定义
抽象数据类型可以用三元组表示:(D,S,T)
D是数据对象,S是D中数据元素关系的集合,P是对D的基本操作的集合
ADT 抽象数据类型名{
数据对象:<数据对象的定义>
数据关系:<数据关系的定义>
基本操作:<基本操作的定义>
}ADT抽象数据类型名
c语言技术网
有穷性、确定性、可行性、输入、输出

算法的复杂度
时间复杂度:计算机运行一个算法时,程序代码被执行的总次数。
程序代码的执行总次数一般与问题规模(需要处理的数据量)有关。
时间复杂度关心的是数量级,对f(n)函数表达式要简化,原则是:1)略去常数;2)只保留最高阶的项;3)变最高阶项的系数为1.
只关心程序代码中最内层循环的次数就可以了。
在这里插入图片描述
在这里插入图片描述
最好时间复杂度、最坏时间复杂度、平均时间复杂度
递归时间复杂度

空间复杂度:S(n) 算法消耗的内存空间,也是问题规模(需要处理的数据量)n的函数。
递归函数的空间复杂度
递归函数嵌套的调用自己,函数的参数和局部变量占用的内存空间在地区的过程中会持续增长,在归来的时候才逐层释放。当递归的深度达到一定量级,可能会造成栈内存空间不足的情况。
在这里插入图片描述
变量写在递归函数之前和之后是不一样的。
线性结构是最简单、最常用的一种数据结构。线性表是一种典型的线性结构。
在这里插入图片描述
在这里插入图片描述

这篇关于数据结构基础1的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!