东莞市公租房申请网站-建设网,华为公司邮箱是多少,pc网站转换手机网站代码,南京网站设计哪家好文章目录 一、基本概念和术语#xff1f;1.1、数据1.2、数据元素1.3、数据项#xff08;属性、字段#xff09;1.4、数据对象1.5、数据结构 二、逻辑结构和物理结构#xff08;存储结构#xff09;2.1、逻辑结构1、定义2、分类#xff08;线性结构和非线性结构#xff0… 文章目录 一、基本概念和术语1.1、数据1.2、数据元素1.3、数据项属性、字段1.4、数据对象1.5、数据结构 二、逻辑结构和物理结构存储结构2.1、逻辑结构1、定义2、分类线性结构和非线性结构 2、物理结构1定义2顺序存储和链式存储3其他存储方式 三、算法和抽象数据类型简介3.1 抽象数据类型定义3.2 算法定义1、算法的特性2、算法效率的度量2.1 事后统计法2.2 事前分析统计 3、算法的复杂度4、算法实例 一、基本概念和术语
1.1、数据
数据是描述客观事物的符号是计算机可以操作的对象是能被计算机识别并输入到计算机处理的符号集合。
数据不仅仅包括整型、实型等数值型还有字符、声音、图像、视频等非数值类型
1.2、数据元素
数据元素是组成数据的、有一定意义的基本单位在计算机中通常作为整体处理也称为记录元组、结点、顶点。
1.3、数据项属性、字段
一个数据元素可以由若干个数据项组成。数据项是数据不可分割的最小单位。
1.4、数据对象
数据对象是性质相同的数据元素的集合是数据的子集。
1.5、数据结构
在现实世界中不同数据元素之间不是独立的而是存在特定的关系这些关系称为结构。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括三方面的内容逻辑结构、存储结构和数据的运算。数据的逻辑结构和存储结构是密不可分的两个方面一个算法的设计取决于所选定的逻辑结构而算法的实现依赖于所采用的存储结构。
二、逻辑结构和物理结构存储结构
数据结构是相互间存在特定关系的数据的集合分为逻辑结构和物理结构。
2.1、逻辑结构
1、定义
逻辑结构是指数据对象中数据元素之间相互关系逻辑关系即从逻辑关系上描述数据。它与数据的存储无关是独立于计算机存储器的。
2、分类线性结构和非线性结构
根据数据元素之间关系的不同特征通常有下列4类基本结构复杂程度依次递进。 集合结构中的数据元素之间除了同属于一个集合外没有其他的关系。 线性结构线性结构中的数据元素之间是一对一的关系。 树形结构树形结构中的数据元素之间是一对多的关系。 图状结构或网状结构结构中的元素之间是多对多的关系。
2、物理结构 1定义
数据的物理结构是指数据的逻辑结构在计算机中的存储方式。又称存储结构。
它研究的是数据结构在计算机中的实现方法包括数据元素的表示和元素之间的关系。
数据元素的存储结构形式主要有两种顺序存储和链式存储
2顺序存储和链式存储
1. 顺序存储结构
是利用数据元素在存储器中的相对位置来表示数据元素之间的逻辑顺序。顺序存储结构是把数据元素放在地址连续的存储单元中程序设计中使用数组类型来实现。逻辑相邻物理相邻
2. 链式存储结构
利用结点中指针来表示数据元素之间的关系。把数据元素存储在任意的存储单元里这组存储单元可以是连续的也可以是连续的程序设计中使用指针类型来实现。逻辑相邻物理不一定相邻
3其他存储方式 索引存储类似于目录以后可以联系操作系统的文件系统章节来理解。 散列存储通过关键字直接计算出元素的物理地址。
三、算法和抽象数据类型简介
3.1 抽象数据类型定义
数据类型是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
例如C语言中数据类型分为基本类型和构造类型
基本类型整型、浮点型、字符型等
构造类型数组、结构、联合、指针、枚举型、自定义类型等
抽象数据类型abstract data typeADT是指一个数学模型及定义在该模型上的一组操作。
3.2 算法定义
算法是特定问题求解步骤的描述是独立存在的一种解决问题的方法和思想。
1、算法的特性
输入有0个或多个输入输出至少有1个或多个输出有穷性算法在有限的步骤后应该自动结束而不会无限循环。确定性算法中的每个步骤都有确定的含义不会出现二义性可行性算法的每一步都是可行的正确性算法对于合法数据能够得到满足要求的结果能够处理非法输入并得到合理的结果。可读性算法要便于阅读、理解和交流健壮性算法不应该得到莫名其妙的结果性价比利用最少的资源得到满足要求的结果
2、算法效率的度量
效率评估是工程中算法最重要的附加特性。
2.1 事后统计法
比较不同算法对同一组输入数据的运行处理时间。
缺点
A、为了获得不同算法的运行处理时间必须编写相应程序
B、运行处理时间严重依赖硬件以及运行时环境
C、算法的测试数据选取困难
2.2 事前分析统计
依据统计的方法对算法效率进行评估
影响算法效率的主要因素
A、算法采用的策略和方法
B、问题的输入规模
C、编译器产生的代码
D、计算机的执行速度
算法效率的简单估算 三种求和算法的关键部分的操作数量分别为2nn1。随着问题规模的增大操作数量的差异会越来越大效率差异也会越来越大。 不同算法操作数量的对比
算法操作数量对比的实例一 n3时算法B优于算法A。随着n的规模增大算法A优势比较明显。
算法操作数量对比的实例二 n1时算法C与算法D效率相同。随着n规模的增大算法C优势明显优于算法D。
判断算法的效率时操作数量中的常数项和其他次阶项常常可以忽略只需要关注最高阶项。
3、算法的复杂度
1算法的时间复杂度
算法时间复杂度是算法运行后对时间需求量的定性描述。
由于主要关注算法的效率问题因此主要讨论算法的时间复杂度。
O表示法
算法的效率严重依赖于操作Operations数量操作数量的估算可以作为时间复杂度的估算在判断时首先关注操作数量的最高阶项。
O2O1
O3n3 O3nOn
O3n2n4On2
常见的时间复杂度 2算法的空间复杂度
算法空间复杂度是算法运行后对空间需求量的定性描述。
通常使用Sn表示算法的空间复杂度。使用时间复杂度的推导方法推导空间复杂度。
当算法所需的内存空间大小为常数时算法的空间复杂度为S1。
通常情况下算法的时间复杂度更受关注。可以通过增加额外空间降低时间复杂度。
算法是解决具体问题的步骤数据结构是算法解决问题的载体。
4、算法实例
一个数组中存储着1——1000的数字每个数字可能出现多次或者不出现找出出现次数最多的数字。void search(int array[], int len)
{//总计可能出现1000种可能值int sp[1000] {0};int max 0;for(int i 0; i len; i){//遍历数组数组中某个数组出现一次增加统计1次sp[array[i] - 1];}for(int i 0; i 1000; i){if(max sp[i]){max sp[i];}}for(int i 0; i 1000; i){if(max sp[i]){cout Number: i 1 endl;cout Count: max endl;}}
}使用空间换时间算法的时间效率为On。
