数据结构第一章.ppt

主讲 金萍 皖西学院信息工程学院 Email jinping 算法与数据结构 主要参考书 数据结构题集 严蔚敏吴伟民编著清华大学出版社 数据结构习题与解析 李春葆编著清华大学出版社 课程目标数据结构是计算机专业的专业基础课 本课程主要研究信息的逻辑结构及其基本操作在计算机中的表示和实现 着重培养学生的数据抽象能力 考核方式笔试成绩60 实验成绩20 平时成绩20 学时安排理论64学时实验16学时 本课程的主要内容 数据结构的基本概念基本类型的数据结构 线性表 栈 队列 串 数组 广义表 树和图 及其应用查找和排序 本课程的学习方法 理解记忆 实践课堂教学 课外自学 本课程的学习方法 推荐学习网站唯C世界北京大学数据结构课程主页 目录 绪论线性表栈和队列串数组和广义表 树和二叉树图查找内部排序 第1章绪论 什么是数据结构基本概念和术语抽象数据类型的表示与实现算法和算法分析 什么是数据结构 背景知识数据结构的研究对象数据结构研究什么数据结构的学科性质 返回 背景知识 第一台计算机的诞生 计算机的用途 科学计算 控制 管理及数据处理 计算机的处理的对象 1 1 ABC 1946年美国ENIAC 返回 数据结构的研究对象 计算机解决问题的步骤 从实际问题抽象出适当的数学模型 设计解此数学模型的算法 编写程序 调试 测试得到解答 几个实例 1 图书馆的书目检索系统自动化问题 此时 计算机处理的对象是什么 几个实例 下列表格便是书目自动检索的数学模型 这是线性数据结构的实例 2 人机对弈问题 国际象棋大师卡斯帕罗夫与电脑 更年少者 的人机大战 人机对弈中电脑必须解决这样一个问题 如何像人类一样思考 这是中国版 人机大战 中的电脑棋手 紫光之星 为什么人机能够对弈 计算机将所有对弈的策略都存储起来 以应对可能出现的各种棋盘状态 几个实例 那么 此时计算机处理的对象是什么 井字棋对弈树 3 多叉路口交通灯的管理问题 图1 3五叉路口的模型 为一个多叉路口设计信号灯管理系统 不同行驶路线之间可能出现冲突 需要对所有的可能行驶路线作某种分组 使每个组内各方向行驶的车辆可以同时安全行驶 不会发生阻挡或碰撞 3 多叉路口交通灯的管理问题 图1 3五叉路口的模型 所有可能通行方向A BA CA DB AB CB DD AD BD CE AE BE CE D 3 多叉路口交通灯的管理问题 返回 数据结构研究什么 数据结构研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等 数据结构学科的发展1968年唐 欧 克努特 美国 背景 大型软件纷纷出现 结构程序设计方法成为主流 越来越重视 数据结构 返回 数据结构的学科性质 数据结构 是一门综合性的专业基础课 它的研究不仅涉及到计算机硬件 特别是编码理论 存储装置和存取方法等 的研究范围 而且和计算机软件的研究有着密切的关系 无论是编译程序还是操作系统 都涉及到数据元素在存储器中的分配问题 在研究信息检索时也必须考虑如何组织数据 以便查找和存取数据元素更为方便 因此 可以说 数据结构 是介于数学 计算机硬件和计算机软件三者之间的一门核心课程 返回 基本概念和术语 数据 所有能输入到计算机中并被计算机程序处理的符号的总称 数据元素 数据的基本单位 数据对象 是性质相同的数据元素的集合 数据结构 是相互之间存在一种或多种特定关系的数据元素的集合 数据元素间的基本结构 集合 线性 树 图 数据结构的形式定义 数据结构是一个二元组Data Structure D S 其中 D是数据元素的有限集 S是D上关系的有限集 数据结构的形式定义 例1 4在计算机科学中 复数可取如下定义 复数是一种数据结构Complex C R 其中 C是含两个实数的集合 c1 c2 R P 而P是定义在集合C上的一种关系 其中有序偶表示c1是复数的实部 c2是复数的虚部 数据结构的形式定义 数据的物理结构元素和结点数据域顺序映像非顺序映像数据类型抽象数据类型 这些名词术语的含义可自学 也可与后面章节对照学习 返回 抽象数据类型的表示和实现 注意 本教材采用介于伪码和C语言之间的类C语言作为描述工具 其优点是 使得数据结构与算法的描述和讨论简明清晰 不拘泥于C语言的细节 又能容易转换成C或C 程序 要求 自学P10 11的内容 返回 算法 algorithm 是对特定问题求解步骤的一种描述 它是指令的有限序列 算法与算法分析 什么是算法算法的特性算法设计的要求算法效率的度量算法的存储空间的需求 有穷性 确定性 可行性 输入 输出 正确性 可读性 健壮性 效率与低存储量需求 返回 算法效率的度量 为了便于比较同一问题的不同算法 通常的做法是 从算法中选取一种对所研究的问题来说是基本操作的原操作 以该基本操作重复执行的次数作为算法的时间度量 算法效率的度量 例如 两个N N矩阵相乘的算法中 乘法 运算是 矩阵相乘问题 的基本操作 整个算法的执行时间与该基本操作 乘法 重复执行的次数n3成正比 记作 T n O n3 算法效率的度量 一般情况下 算法中基本操作重复执行的次数是问题规模n的某个函数f n 算法的时间量度记作T n O f n 它表示随问题规模n的增大 算法执行时间的增长率和f n 的增长率相同 称作算法的渐进时间复杂度 简称时间复杂度 算法效率的度量 例如 在以下3个程序段中 x s 0 for i 1 i n i x s x for j 1 j n j for k 1 k n k x s x 这3个程序段的时间复杂度分别为O 1 O n O n2 分别称为常量阶 线性阶和平方阶 常见函数的增长率 返回 算法的存储空间需求 空间复杂度作为算法所需存储空间的量度 记作 S n O f n 其中 n为问题的规模 若额