《数据结构A》第01章.ppt

南京邮电大学计算机学院陈慧南2006年9月 数据结构 DataStructuresinC 南京邮电大学计算机学院陈慧南2006年9月 数据结构A 课程性质 任务和目的 性质 是计算机学科的一门专业基础课 目的 在于学习如何组织和表示数据 并在相应的数据结构上实现对数据的操作 基本任务 是学习常见的基本数据结构 包括线性表 栈和队列 数组和字符串 树 搜索树 散列表 图和文件等 理解它们的逻辑结构 存储结构 领会在这些数据结构上定义的运算和实现运算的算法 学习和领会内 外排序算法 南京邮电大学计算机学院陈慧南2006年9月 第1章基础知识 南京邮电大学计算机学院陈慧南2006年9月 1 1算法与数据结构1 2什么是数据结构1 3数据抽象和抽象数据类型1 4描述数据结构和算法1 5算法分析的基本方法 南京邮电大学计算机学院陈慧南2006年9月 1 1算法与数据结构 南京邮电大学计算机学院陈慧南2006年9月 数据结构和算法是计算机学科的基础之一 更是软件技术的基础 数据的组织和表示方法直接影响使用计算机求解问题的效率 算法设计通常建立在所处理数据的一定组织形式之上的 它们之间有着本质的联系 当讨论一种算法时 自然要涉及算法所处理的数据问题 程序 数据结构 算法 南京邮电大学计算机学院陈慧南2006年9月 1 2什么是数据结构 南京邮电大学计算机学院陈慧南2006年9月 1 2 1基本概念 基本术语数据 data 计算机加工处理的对象 数据元素 组成数据的基本单位数值数据 numericaldata 非数值数据 non numericaldata 南京邮电大学计算机学院陈慧南2006年9月 数据结构的由来数据结构主要是为研究和解决如何使用计算机组织和处理这些非数值问题而产生的理论 技术和方法 它已成为计算机学科研究的基本课题之一 南京邮电大学计算机学院陈慧南2006年9月 数据结构包括三个方面逻辑结构 数据元素间的逻辑关系 存储结构 数据在计算机内的表示形式 运算 在数据上执行的操作 南京邮电大学计算机学院陈慧南2006年9月 南京邮电大学计算机学院陈慧南2006年9月 1 2 2数据的逻辑结构 数据的逻辑结构对数据元素间逻辑关系的描述被称为数据的逻辑结构 logicalstructure 它可以用一个二元组表示 DS D R 其中 D是数据元素的有限集合 R是D中元素序偶的集合 南京邮电大学计算机学院陈慧南2006年9月 四类基本逻辑结构 a 集合结构 b 线性结构 c 树形结构 d 图状结构 南京邮电大学计算机学院陈慧南2006年9月 1 2 3数据的存储表示 顺序存储需要一块连续的存储空间 并把逻辑上相关的数据元素依次存储在该连续的存储区中 Loc ak 102 2 k 南京邮电大学计算机学院陈慧南2006年9月 链接存储 几种存储结构顺序结构链接结构索引结构散列结构 DataLink 地址信息称为链 表示空链 南京邮电大学计算机学院陈慧南2006年9月 1 2 4数据结构的运算 数据结构最常见的运算创建运算 创建一个数据结构 清除运算 删除数据结构中的全部元素 插入运算 在数据结构的指定位置上插入一个新元素 删除运算 将数据结构中的某个元素删除 南京邮电大学计算机学院陈慧南2006年9月 静态数据结构和动态数据结构如果一个数据结构一旦创建 其结构不发生改变 则称为静态数据结构 否则成为动态数据结构 南京邮电大学计算机学院陈慧南2006年9月 例1 1栈数据结构堆栈是一种线性数据结构 可以向栈中加入元素 但只允许访问和删除最后入栈的元素 1 向栈中加入一个元素 Push运算 2 从栈中删除最后加入的元素 Pop运算 3 访问最后加入栈中的元素 Top运算 南京邮电大学计算机学院陈慧南2006年9月 什么是数据结构一个数据结构是由数据元素依据某种逻辑联系组织起来的 对数据元素间逻辑关系的描述称为数据的逻辑结构 数据必须在计算机内存储 数据的存储结构是数据结构的实现形式 是其在计算机内的表示 此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义 南京邮电大学计算机学院陈慧南2006年9月 1 3数据抽象和抽象数据类型 南京邮电大学计算机学院陈慧南2006年9月 1 3 1抽象 数据抽象和过程抽象 抽象 其实质是抽取共同的和本质的内容 忽略非本质的细节 数据抽象 使程序设计者可以将数据元素间的逻辑关系和数据在计算机内的具体表示分别考虑 过程抽象 使程序设计者将一个运算的定义与实现运算的具体方法分开考虑 抽象的好处主要在于降低了问题求解的难度 南京邮电大学计算机学院陈慧南2006年9月 整型int的规范变量a的取值范围是 32768 32767对变量a执行的操作有 算术运算 关系运算 赋值运算 整型int的实现变量a在计算机内存储表示方法 操作的具体实现方法 南京邮电大学计算机学院陈慧南2006年9月 1 3 2封装与信息隐蔽 封装 是指把数据和操纵数据的运算组合在一起的机制 使用者只能通过一组允许的运算访问其中的数据 信息隐蔽 对使用者隐藏了数据结构或程序的实现细节 通常将数据和操纵数据的运算组成模块 每个模块有一个明确定义的界面 模块内部信息只能经过这一界面被外部访问 南京邮电大学计算机学院陈慧南2006年9月 模块应采用封装和信息隐蔽原则来设计 这样的模块被称为黑盒子 封装和信息隐蔽的作用 错误局部化 降低问题求解的复杂性 提高程序的可靠性 C 语言的类可以封装数据和运算 其公有 保护和私有成员机制有利于实现信息隐蔽 南京邮电大学计算机学院陈慧南2006年9月 1 3 3数据类型和抽象数据类型 数据类型是程序设计语言中的概念 它是数据抽象的一种方式 一个数据类型定义了一个值的集合以及作用于该值集的运算集合 程序设计语言中 一个数据类型不仅规定了该类型的变量 或常量 的取值范围 还定义了该类型允许的运算 南京邮电大学计算机学院陈慧南2006年9月 抽象数据类型 abstractdatatypeADT 是一个数据类型 其主要特征是该类型的对象及其运算的规范 与该类型对象的表示和运算的实现分离 实行封装和信息隐蔽 即所谓使用和实现分离 南京邮电大学计算机学院陈慧南2006年9月 1 3 4数据结构与抽象数据类型 逻辑结构和运算的定义组成了数据结构的规范 specification 数据的存储表示和运算算法的描述构成数据结构的实现 implementation 从规范和实现两方面来讨论数据结构的方式是抽象数据类型的观点 一种数据结构被视为一个抽象数据类型 南京邮电大学计算机学院陈慧南2006年9月 数据结构的抽象层次抽象层 讨论数据的逻辑结构及其运算定义 实现层 讨论数据的存储表示以及运算的算法实现 南京邮电大学计算机学院陈慧南2006年9月 1 4描述数据结构和算法 南京邮电大学计算机学院陈慧南2006年9月 1 4 1数据结构的规范 数据结构被看成是一个类属抽象数据类型 ADT 用格式化的自然语言来描述 数据结构可以形式地用一个C 的抽象模板类描述 南京邮电大学计算机学院陈慧南2006年9月 ADT1 1栈ADTADTStack 数据 0个或多个元素的线性序列 a0 a1 an 1 其最大允许长度为MaxStackSize 运算 Create 建立一个空栈Destroy 撤消一个栈Push x 值为x的新元素进栈 成为栈顶元素Pop 从栈中删除栈顶元素Top x 在x中返回栈顶元素 南京邮电大学计算机学院陈慧南2006年9月 templateclassStack 栈类Stack是一个模板抽象类 其成员函数为纯虚函数 未定义数据成员 public virtualboolPush Tx 0 virtualboolPop 0 virtualboolTop T 南京邮电大学计算机学院陈慧南2006年9月 1 4 2实现数据结构 templateclassSeqStack publicStack public private inttop top记录最后入栈的元素在s的下标intmaxTop 最大栈顶指针T s s指向动态生成的一维数组 存放元素 南京邮电大学计算机学院陈慧南2006年9月 templateSeqStack SeqStack intmSize maxTop mSize 1 设置栈的容量值s newT mSize 生成存储栈的数组top 1 top 1表示空栈 南京邮电大学计算机学院陈慧南2006年9月 1 5算法分析的基本方法 南京邮电大学计算机学院陈慧南2006年9月 1 5 1算法及其性能标准 什么是算法笼统的说 算法是求解一类问题的任意一种特殊的方法 较严格的说法是一个算法是对特定问题的求解步骤的一种描述 它是指令的有限序列 此外 算法具有下列五个特征 南京邮电大学计算机学院陈慧南2006年9月 输入 算法有零个或多个输入输出 算法至少产生一个输出确定性 算法的每一条指令都有确切的定义 没有二义性 能行性 算法的每一条指令都足够基本 它们可以通过已经实现的基本运算执行有限次来实现 有穷性 算法必须总能在执行有限步之后终止 南京邮电大学计算机学院陈慧南2006年9月 算法的性能标准正确性 算法的执行结果应当满足预先规定的功能和性能要求 简明性 一个算法应当思路清晰 层次分明 简单明了 易读易懂 健壮性 当输入不合法数据时 应能做适当处理 不至于引起严重后果 效率 有效使用存储空间 并有高的时间效率 南京邮电大学计算机学院陈慧南2006年9月 1 5 2算法的时间复杂度 算法的时间复杂度是程序运行从开始到结束所需的时间 程序步一个程序步是指在语法上或语义上有意义的程序段 该程序段的执行时间与问题实例的特征无关 南京邮电大学计算机学院陈慧南2006年9月 floatSum floatlist constintn 此程序的程序步数为2n 3floattempsum 0 0 count 针对赋值语句for inti 0 i n i count 针对for循环语句tempsum list i count 针对赋值语句 count 针对for的最后一次执行count 针对return语句returntempsum 南京邮电大学计算机学院陈慧南2006年9月 1 5 3渐近时间复杂度 定义 大O记号 设f n 和g n 是定义在正整数上的正函数 如果存在两个正常数c和n0 使得当n n0时 有f n cg n 则记作f n O g n 南京邮电大学计算机学院陈慧南2006年9月 定理如果f n amnm am 1nm 1 a1n a0是m次多项式 则f n O nm 例 T n 3 6n3 2 5n2 2 8 O n3 南京邮电大学计算机学院陈慧南2006年9月 渐近时间复杂度使用大O记号表示的算法的时间复杂度 称为算法的渐近时间复杂度 渐近时间复杂度也常简称为时间复杂度 通常用O 1 表示常数计算时间 即算法只需执行有限个程序步 南京邮电大学计算机学院陈慧南2006年9月 关键操作很多情况下 可以通过考察一个程序中的关键操作 关键操作被认为是一个程序步 的执行次数来计算算法的渐近时间复杂度 有时也需要同时考虑几个关键操作 以反映算法的执行时间 南京邮电大学计算机学院陈慧南2006年9月 例voidMult inta n n b n n c n n intn n n矩阵a与b相乘得到c for inti 0 i n i n 1for intj 0 j n j n n 1 c i j 0 n2for intk 0 k n k n2 n 1 c i j a i k b k j n3 程序步为 2n3 3n2 2n 1c i j a i k b k j 可看成关键操作渐近时间复杂度为 T n O n3 南京邮电大学计算机学院陈慧南2006年9月 算法按时间复杂度分类多项式时间算法O 1 O log2n O n O nlog2n O n2 O n3 指数时间算法O 2n O n O nn 南京邮电大学计算机学院陈慧南2006年9月 1 5 4最好 最坏和平均时间复杂度 例子 在一个有n个元素的数组中查找一个指定元素 某个搜索算法从第一个元素开始 一次检查一个数组元素 南京邮电大学计算机学院陈慧南2006年9月 最好情况 如果待查元素恰好是第一个元素