通知
关于网站更多信息请加whimurmur模板/jpress插件QQ群(1061691290)            jpress从3.x升级到4.x,显示有些问题,慢慢修复中

数据结构 第1章 绪论

611人浏览 / 0人评论 / | 作者:因情语写  | 分类: 数据结构  | 标签: 数据结构  | 

作者:因情语写

链接:https://www.proprogrammar.com/article/762

声明:请尊重原作者的劳动,如需转载请注明出处


1.1 数据结构的研究内容
1.2 基本概念和术语
1.3 抽象数据类型的表示与实现

1.1 数据结构的研究内容

N.沃思(Niklaus Wirth) 教授提出:
程序=算法+数据结构
《数据结构》所处的地位:
介于数学、计算机硬件和计算机软件三者之间的 一门核心课程

1.2 基本概念和术语

(1)数据(data) —所有能输入到计算机中去的描述客观事物的符号
—数值性数据
—非数值性数据(多媒体信息处理)
(2)数据元素(data element) —数据的基本单位,也称结点(node)或记录(record)
(3)数据项(data item) —有独立含义的数据最小单位,也称域(field)
(4)数据对象(Data Object) :相同特性数据元素的集合,是数据的一个子集整数数据对象
N = { 0, ±1, ±2, … }
学生数据对象
⑩学生记录的集合
(5)数据结构(Data Structure)是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构是带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系。
数据结构 2+1(两个层次和一个操作)
逻辑结构
数据元素间抽象化的相互关系,与数据的存储无关,独立于计算机,它是从具体问题抽象出来的数学模型。
存储结构(物理结构)
数据元素及其关系在计算机存储器中的存储方式。
操作(运算、行为)
执行不同功能的算法

划分方法一

(1)线性结构----
有且仅有一个开始和一个终端结点,并且所有结点都最多只有一个直接前趋和一个后继。
例如:线性表、栈、队列、串
(2)非线性结构----
一个结点可能有多个直接前趋和直接后继。
例如:树、图

划分方法二

集合——数据元素间除“同属于一个集合”外,无其它关系
线性结构——一个对一个,如线性表、栈、队列
树形结构——一个对多个,如树
图形结构——多个对多个,如图
存储结构分为:
顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系
链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系
索引存储结构——字典中单词存储关系
散列存储结构——地址与散列函数之间建立的一种映射

数据类型

定义:在一种程序设计语言中,变量所具有的数据种类
C 语言:
基本数据类型: char int float double void
构造数据类型:数组、结构体、共用体、文件
数据类型是一组性质相同的值的集合, 以及定义于这个集合上的一组运算的总称

抽象数据类型

抽象数据类型 (ADTs: AbstractData Types)
—更高层次的数据抽象
—由用户定义,用以表示应用问题的数据模型
—由基本的数据类型组成, 并包括一组相关的操作

说明: 抽象数据类型的表示与实现

抽象数据类型可以通过固有的数据类型(如整型、实型、字符型等)来表示和实现。
如何学习抽象数据类型?

1.3 算法和算法分析

算法定义

一个有穷的指令集,这些指令为解决某一特定任务规定了一个运算序列

算法的特性

输入 有 0 个或多个输入
输出 有一个或多个输出(处理结果)
确定性 每步定义都是确切、无歧义的
有穷性 算法应在执行有穷步后结束
有效性 每一条运算应足够基本

算法设计的评价

正确性
可读性
健壮性
高效性(时间代价和空间代价)

算法效率的度量

算法效率:时间和空间来度量
时间复杂度
空间复杂度

算法效率的度量: 时间复杂度

算法效率:用依据该算法编制的程序在计算机上执行所消耗的时间来度量
事后统计
事前分析估计
方式 1.事后统计:利用计算机内的计时功能,不同算法的程序可以用一组或多组相同的统计数据区分
缺点:
①必须先运行依据算法编制的程序
②所得时间统计量依赖于硬件、软件等环境因素,掩盖算法本身的劣
方式 2.事前分析估计:
一个高级语言程序在计算机上运行所消耗的时间取决于:
①依据的算法选用何种策略
②问题的规模
③程序语言
④编译程序产生机器代码质量
⑤机器执行指令速度

时间复杂度的渐进表示法

一般情况下,算法中基本操作重复执行的时间是问题规模 n 的某个函数 f(n) ,算法执行的时间的增长率和 f(n) 的增长率相同,称渐近时间复杂度。
时间复杂度的表示方法有两种:
方法 1:大 O 法 T(n) = O(f(n))
它表示随问题规模 n 的增大,算法执行时间的增长率和 f(n) 的增长率相同,称作算法的渐进时间复杂度,简称时间复杂度。
方法 2:语句频度法
计算该语句重复执行的次数,又叫频度统计法。
说明:
数学符号“O”的定义为:若 T(n) 和 f(n) 是定义在正整数集合上的两个函数,则T(n) = O(f(n)) 表示存在正的常数 C 和 n0,使得当 n≥n0 时都满足0≤T(n) ≤Cf(n) 。

分析算法时间复杂度的基本方法

找出语句频度最大的那条语句作为基本语句
计算基本语句的频度得到问题规模 n 的某个函数 f(n)
取其数量级用符号“O”表示

引例与分析

时间复杂度是由嵌套最深层语句的频度决定的

算法效率的度量: 空间复杂度

(1)定义
(2)三个组成部分
存储算法本身所占用的空间
算法的输入/输出数据占用的空间
算法在运行过程中临时占用的辅助空间
(3)原地工作:若辅助空间相对于输入数据量是常数,则称此算法是原地工作。
说明:若所占空间量依赖于特定的输入,按最坏情况来分析

算法设计的要求

(1)正确性
(2)可读性
首先是给人读,然后才是机器执行
(3)健壮性, 容错性
(4)效率与低存储量需求
重点 1:基本术语:数据结构
重点 2:抽象数据类型
重点 3:算法优劣的评价标准
重点 4:数据结构的学习方法

重点 3: 算法优劣的评价标准: 时间复杂度

(1)当 f(n) 为对数函数、幂函数、或它们的乘积时,算法的运行时间是可以接受的,称这些算法是有效算法;当 f(n) 为指数函数或阶乘函数时,算法的运行时间是不可接受的,称这些算法是无效的算法。
(2)随着 n 值的增大,增长速度各不相同, n 足够大时,存在下列关系:
对数函数<幂函数<指数函数

增长率由慢到快
尽量少用指数阶的算法


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告