数据结构第一章.ppt

数据结构 教材 数据结构 C语言版 题集严蔚敏吴伟民清华大学出版社 课程安排 全书共分12章 教学内容为前1 7 9 10章总计64学时 授课52学时 上机12学时 预备知识 熟练掌握C语言 尤其是指针和结构工具 VC 参考书目 1 数据结构 杨秀金张红梅 西安电子科技大学出版社2 数据结构习题解析与上机实验指导 中国水利水电出版社3 数据结构C 语言描述 刘卫东沈官林译严蔚敏审 清华大学出版社4网络资源Internet 第一章绪论 本章主要介绍下列内容1 1问题的引入 什么是数据结构1 2基本概念和术语1 3抽象数据类型及其表示实现1 4算法和算法分析 1 1什么是数据结构 程序设计 为计算机处理问题编制一组指令集的过程算法 处理问题的策略数据结构 是指数据的逻辑结构和存储结构计算机解决的问题分为 NiklausWirth Algorithm DataStructures Programs 数值计算问题非数值计算问题 算法 数据结构 程序 例 学籍档案 图书目录卡类问题 一个记录 一个表 记录之间是一种顺序关系 线性表 数据之间的逻辑结构称为线性结构 主要操作 查找 插入 删除 例 院系结构 家谱问题 人机对弈问题 河南工业大学 信息学院 计算机 电子 通信 土建学院 经贸学院 数据之间是一种层次关系 树结构 主要操作 遍历 查找 插入 删除 一个教学计划包含许多课程 在教学计划包含的许多课程之间 有些必须按规定的先后次序进行 有些则没有次序要求 即有些课程之间有先修和后续的关系 有些课程可以任意安排次序 这种各个课程之间的次序关系可用一个称作图的数据结构来表示 有向图中的每个顶点表示一门课程 如果从顶点vi到vj之间存在有向边 则表示课程i必须先于课程j进行 例 教学计划编排 交通问题 通信网问题 图结构 对每个节点怎样遍历一遍 且仅一遍 效率最高 主要操作 存储 插入 删除 检索等 概括地说 数据结构是一门讨论 描述现实世界实体的数学模型 非数值计算 及其上的操作在计算机中如何表示和实现 的学科 数据结构课程研究的内容 逻辑结构 线性表 树 图 机内存储 运算与操作 顺序存储结构 链式存储结构 复合存储结构 建立 输入 插入 删除 查找 排序 数据间的逻辑关系 机内存储方式 相关运算处理及算法分析 数据结构是一门主要研究怎样合理的组织数据 建立合适的数据结构 提高计算机执行程序所用的时间效率和空间效率的学科 数据 计算机程序所处理的符号的总称 数据元素 数据的基本单位 它可由若干数据项组成 数据对象 是性质相同的数据元素的集合 是数据的子集 数据结构 是相互之间存在一种或多种特定关系的数据元素的集合 1 2基本概念和术语 在程序中常作为整体考虑和处理 数字 字母 声音 图像等 整数N 0 1 2 08级学生的学籍表 共有300个结构相同的记录 数据元素 数据结构 一个数据结构有两个要素 一个是数据元素的集合 另一个是关系的集合 在形式上 数据结构通常可以采用一个二元组来表示 Data Structure D S 其中 D是数据元素的有限集 S是D上关系的有限集 例1 4复数是一种数据结构 Complex C R 其中 C是包含两个实数的集合 c1 c2 R P P是定义在集合C上的一种关系 其中有序偶表示c1是复数的实部 c2虚部 例 计算机系学生的学号 选课 业余爱好 担当职务情况统计如下 计算机控制 图形学 软件工程 计算机安全学 汉字处理工具软件等六门课 用A B C D E F表示 数据元素 数据项 数据元素之间的逻辑关系 分 集合 数据元素间除 同属于一个集合 外 无其它关系线性结构 一个对一个 如线性表 栈 队列树形结构 一个对多个 如树和二叉树图状结构 多个对多个 如图或网 数据的逻辑结构 数据的逻辑结构在计算机存储设备中的映射 分 顺序存储结构 链式存储结构 顺序存储链式存储 数据的存储结构 1 顺序存储结构 以相对的存储位置表示逻辑关系 物理地址连续 采用顺序存储方法所得到的存储表示称为顺序存储结构 2 链式存储结构 不要求逻辑上相邻的结点在物理位置上亦相邻 结点间的逻辑关系由存储结点时附加的指针字段表示 地址不连续 有指针指示 采用链接存储方法所得到的存储表示称为链式存储结构 利用C语言的一维数组表示顺序存储结构 definedMAXSIZE100ElemTypeelem MAXSIZE 利用C语言的动态链表表示链式存储结构 TypedefstructNode ElemTypedata 数据域 structNode next 指针域 Node data next 数据类型 DataType 一个值的集合和定义在此集合上操作的总称 分为原子类型 int float char等 和结构类型 数组 结构体 文件等 1 3抽象数据类型 C中的int值集 32768 32767 操作 等 抽象数据类型 AbstractDataType 抽象数据类型 ADT 是指一个数学模型以及定义在此数学模型上的一组操作 与机内表示和实现无关 指的是数学抽象性 抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成 例如 整数 实现加 减 乘 除等操作 原子类型 变量的值是不可分解的固定聚合类型 由确定数目的成分按某种结构组成 可变聚合类型 构成可变聚合类型 值 的成分的数目不确定 抽象数据类型的定义可以由一种数据结构和定义在其上的一组操作组成 而数据结构又包括数据元素及元素间的关系 因此抽象数据类型一般可以由元素 关系及操作三种要素来定义 抽象数据类型用三元组表示 D S P 其中 D是数据对象 S是D上的关系 P是对D的基本操作集 ADT有两个重要特征 数据抽象用ADT描述程序处理的实体时 强调的是其本质的特征 其所能完成的功能以及它和外部用户的接口 即外界使用它的方法 数据封装将实体的外部特性和其内部实现细节分离 并且对外部用户隐藏其内部实现细节 抽象数据类型的描述方法 ADT抽象数据类型名 数据对象 数据关系 基本操作 其中基本操作的定义格式为 基本操作名 参数表 初始条件 初始条件描述 操作结果 操作结果描述 例 抽象数据类型 复数 ADTComplex 数据对象 D c1 c2 FloatSet 数据关系 R1 基本操作 Creatc 已知a 输出a c1 c2i的形式 ADTComplex 例 抽象数据类型 三元组 ADTTriplet 数据对象 D e1 e2 e3 e1 e2 e3 ElemSet 数据关系 R1 基本操作 InitTriplet T v1 v2 v3 操作结果 构造三元组T 元素ei分别赋值vi Min T e 初始条件 三元组T已经存在操作结果 用e返回T的3个元素中最小值 ADTTriplet 面向过程的方法面向对象的方法 抽象数据类型的实现 1 4 1算法的概念 对特定问题求解步骤的一种描述 是指令的有限序列 每条指令表示一个或多个操作 算法应具备的特性 2 确定性 指令具有确切的含义 相同的输入有相同的输出 1 有穷性 对合法的输入值在执行有穷步之后结束 3 可行性 所有操作可经已实现的基本运算执行有限次来实现 4 输入 0个或多个 5 输出 一个或多个 1 4算法和算法分析 2 可读性 便于阅读和交流 3 健壮性 能够对输入的非法数据作出反应和处理 4 效率与低存储量需求 效率指算法的执行时间 存储量需求指算法执行过程中所需要的最大存储空间 1 4 2算法设计的要求 1 正确性 算法应满足具体问题的需求 a 程序不含语法错误b 对于几组输入可得满足要求的结果c 对于精心选择的几组典型 苛刻 带有刁难性的输入数据可得满足要求的结果d 对一切合法的输入数据都能得出产生要求的结果 算法的时间效率主要由两个因素决定 l所需处理问题的数据量大小 数据量大 所花费的时间就多 l在解决问题的过程中 基本操作的执行次数时间复杂度 算法中基本操作重复执行的次数是问题规模n的某个函数 T n O f n 好的算法应该能够在数据量n增长的同时 函数T n 的增长速度比较缓慢 1 4 3算法效率的度量 问题的规模 是数据元素的个数 通常用n来表示例如 对一个学院 n可为数百人 对整个学校 n可为上千至上万人 算法分析要脱离开具体机型 语言因素来分析 主要是时间因素 还有内存空间的占用 例如程序段 1 printf d 123 2 for i 1 i n i printf d i 3 for i 1 i n i for j 1 j n j printf d i j 4 for i 1 i n i for j 1 j n j for k 1 j n k printf d i j k 时间效率分析 语句频度 语句重复执行的次数 频度 1 n n2 n3 算法复杂度 O 1 O n O n2 O n3 时间效率分析 算法的时间复杂度 根据算法中最大语句频度来估算 记作T n O f n f n 的估计法 取近似的 粗略的 变化率 n的阶 例如 for i 1 i n i for j 1 j i j printf d i j 语句频度 算法复杂度 按数量级递增排列 常见的时间复杂度有常数阶O 1 对数阶O log2n 线性阶O n 线性对数阶O nlog2n 平方阶O n2 立方阶O n3 k次方阶O nk 指数阶O 2n 常见函数的增长率 空间复杂度 S n O f n 辅助空间的度量 辅助空间就是除算法代码本身和输入输出数据所占据的空间外 算法临时开辟的存储空间单元 在有些算法中 占据辅助空间的数量与所处理的数据量有关 而有些却无关 后一种是较理想的情况 在设计算法时 应该注意空间效率 1 4 4空间效率的分析 1 预定义常量及类型函数结果状态代码 defineTRUE1 defineFALSE0 defineOK1 defineERROR0 defineOVERFLOW 1Status是函数的类型 其值是函数结果状态代码typedefintStatus 1 4 5算法描述工具 类CP10 2 数据结构的