数据结构第一章概论.ppt

数据结构第一章概论 重庆一中葛静 本章的主要内容 问题一 数据结构讨论的范畴问题二 基本概念问题三 算法及其度量 问题一 数据结构讨论的范畴 尼克劳斯 沃斯 NiklausWirth 生于瑞士 求学美洲 立业瑞士 苏黎世联邦理工学院教授 Pascal系列语言之父 世界闻名的计算机科学家 Algorithm DataStructures Programs算法 数据结构 程序程序 为计算机处理问题编制的一组指令集 算法 处理问题的策略 数据结构 问题的数学模型 数值计算的程序设计问题 全球天气预报 环流模式方程 数学模型 进行大量的数值运算 这是计算数学要讨论的问题 非数值计算的程序问题 例1 求n个数中的最大值算法 两两比较数据结构 n的范围 如果n达到10 12 如何表示这个整数 非数值计算的程序问题 例2 人机对弈算法 对弈的规则和策略数据结构 棋盘 棋子怎么表示 非数值计算的程序问题 例3 足协数据库管理算法 需要管理哪些项目 用户的界面 条例 规则等等 数据结构 各种各样的表格和数据库 综合各种程序设计的问题 抽出其具体的物理含义 就可得到几类数学模型 1 和数值计算相关的数学模型 如线性代数方程 非线性代数方程和常微分方程等 他们的数值解问题就是计算数学要解决的问题 2 非数值计算问题 其数学模型的表示和求解就是数据结构要研究的内容 概括的说 数据结构要研究的就是 非数值型计算的程序设计问题中描述现实世界实体的数学模型和在计算机中表示的方法以及这些数学模型进行的操作如何在计算机中实现 问题二 基本概念 数据 是计算机要处理的信息集合 是信息的某种特定的符号表示形式 其含义随着计算机的发展不断扩大 数据元素 是数据中的一个 个体 是数据结构中讨论的基本单位 但不是最小单位 如 学生 数据元素 姓名 性别 出生日期 年月日 入学日期 班级 数据项才是数据结构中要讨论的最小单位 数据结构 带结构的数据元素的集合 结构 就是数据元素之间存在的约束关系 例1 一个含有12位数的十进制整数可以用三个4位的十进制整数表示 1548 4913 7875 a1 1548 a2 4913 a3 7875 在a1 a2 a3之间存在次序关系 4973 7875 1548 1548 4913 7875a2a3a1 a1a2a3 数据结构 带结构的数据元素的集合 例2 2行3列的二维数组 a1 a2 a3 a4 a5 a6 行的次序关系 row 列的次序关系 col a1a3a4a1a2a3 a2a6a5a4a5a6 数据结构 带结构的数据元素的集合 例3 一位数组 a1 a2 a3 a4 a5 a6 这6个数据元素还可以存在单纯的次序关系 i 1 2 3 4 5 所以 相同的数据元素 不同的约束关系 构成了不同的数据结构 例3人机对奕问题 多叉路口交通灯管理问题 数据的逻辑结构 数据在逻辑上的联系 叫做数据的逻辑结构 数据的逻辑结构 只抽象反映数据元素的逻辑关系数据的存储 物理 结构 数据的逻辑结构在计算机存储器中的实现 数据逻辑结构的定义 定义为一个二元组 Data structures D S 其中 D是数据元素的有限集 S是D上关系的有限集 如 线性结构 数据对象 A ai 1 0 ai elemtype 其中n为线性表的表长 n 0时线性表为空表 数据关系 R r R 1 i n 1 数据的物理结构 存储结构 数据的在计算机上的存储表示称作数据的物理结构或存储结构 数据元素的映像方法 用二进制位 bit 的位串表示数据元素 321 10 101000001 2A 001000001 2 数据的物理结构 存储结构 关系集合的映像方法 所有关系都可用一个有序对的集合来表示 有序对看成是关系的一个基本单位 讨论关系的映像 只要讨论这个有序对的映像方法即可 映像方法 顺序映像 以存储位置的相邻表示后继关系 链式印象 存储位置无固定关系 用附加信息 指针 来表示后继关系 数据类型 数据类型是一个值的集合和定义在这个集合上的一组操作的总称 如pascal中的integer类型 数据范围 32768 32767 操作 divmod数据类型分为 简单型和结构类型 构造类型 结构类型 比如 数组 数组的值可以分割 它是某个结构的值 因此这个值集是一个数据结构 所以数据类型也可以看成是一个数据结构和定义在这个数据结构上的一组操作的总称 从这个概念出发 抽象数据类型 ADTAbstractDataType 是指一个数学模型以及定义在这个数学模型上的一组操作 例如 抽象数据类型复数的定义 ADTcomplex 数据对象 D e1 e2 e1 e2 real 数据关系 R e1是复数的实部 e2是复数的虚部 基本操作 Initcomplex z v1 v2 操作结果 构造复数z 其实部和虚部分别赋以参数v1 v2的值 Destroycomplex z 操作结果 复数z被销毁Getreal z x 初始条件 复数已存在操作结果 用x返回复数z的实部值Getimag z y 初始条件 复数已存在操作结果 用y返回z的虚部值Add z1 z2 sum 初始条件 z1 z2是复数操作结果 用sum返回两个复数的和值 抽象数据类型的描述方法 D S P 三元组表示 D是数据对象S是D上的关系集P是对D的基本操作 抽象数据类型的表示和实现 通过固有数据类型 即高级编程语言中已经实现的数据类型 来实现 问题三 算法及算法的衡量 算法 是为了解决某类问题而规定的一个有限长的操作序列 算法的五个重要特性 1 有穷性2 确定性3 可行性4 有输入5 有输出 算法的特性 1 有穷性 对任意一组合法输入值 在执行有穷步骤之后 一定能结束 即能在有限时间内完成 其含义有二 其一 描述算法的指令条数有限 其二 每一步的执行时间是有限的 非数学意义上的有限 而应理解为合理 算法的特性 确定性 每种情况下执行的操作 在算法中都有确切的规定 使算法的执行者或者阅读者能够明确其含义及如何执行 并且在任何条件下 算法都只有与之对应的一条路径 可行性 算法中的所有操作都必须足够基本 都可以通过已经实现的基本操作运算有限次来实现之 如 将a b的最大公约数赋值给c 增加x的值 交换a b两个变量的值 算法的特性 有输入 输入的形式多样 有的输入嵌在算法中 有的可通过终端输入 必须保证算法有可以加工的对象 如 求100以内的素数Fori 2to100do 有输出 信息加工的结果 算法设计 评价 的原则 1 正确性 程序不含语法错误程序对于几组输入数据能够得到满足要求的结果 对于精心选择的 典型的 苛刻且带有刁难性的几组输入数据都能得出满足要求的结果 程序对于一切合法的输入数据都能得出满足要求的结果 相当难 算法设计 评价 的原则 2 可读性算法主要是为了人的阅读与交流 其次才是为了计算机执行 因此算法应该易于人的理解 另一方面 晦涩难懂的程序易于隐藏较多的错误而难以调试 例如 多人合作设计大型软件系统设计程序设计编程 算法设计 评价 的原则 3 健壮性 对应着正确性 当输入数据非法时 算法应当恰当地作出反映或进行相应的处理 而不是产生莫名其妙的输出结果 并且 不应该中断程序的执行 而应是返回一个表示错误或错误性质的值 4 高效率与低存储量的需求 效率 算法执行的时间存储量 算法执行过程中最大的存储空间 二者均与问题的规模有关 算法效率的衡量方法和准则 1 事后统计法 算法 程序 运行时间缺点 1 必须执行程序 2 其他因素掩盖算法本质2 事前分析估算法 和算法执行时间相关的因素 算法选用的策略 问题的规模 编写程序的语言 编译程序产生的机器代码的质量 计算机执行指令的速度 第3 4 5条均与硬件及软件有关 一般不考虑 一个特定算法的 运行工作量 的大小 只依赖于问题的规模n 或者说 它是问题规模n的函数 我们要关系的是 随着n的增长 算法执行时间的增长与n的关系 T n O f n T n 就是算法的渐近时间复杂度 T n 增大的趋势与f n 相同 如何估算 算法 控制结构 原操作 固有数据类型的操作 算法的执行时间 原操作执行的次数 原操作执行的时间 从算法中选取起决定作用的基本操作叫原操作 以该基本操作在算法中重复执行的次数为算法运行时间的衡量准则 例1 fori 1tondoforj 1tondobeginc i j 0 fork 1tondoc i j c i j a i k b k j end 控制结构 3重循环基本操作 乘法时间复杂度 O n 3 例2 fori 1ton 1dobeginj i fork i 1tondoifa k ithenswap a j a i end 基本操作 比较 比较次数 n 1 n 2 1 n n 1 2 n 2 n 2与n 2成正比 故时间复杂度O n 2 例3 t true i n 1 while i 1 and t dobegint false forj 1toidoifa j a j 1 thenbeginswap a j a j 1 t true end dec i end 该算法与输入有关 最好情况O n 1 最坏O n 2 算法的存储空间需求 算法的空间复杂度S n O g n 表示随着n的增大 算法运行所需存储量的增长率与g n 的增长率相同 算法的存储量包括 程序本身所占空间 细微差别 可不考虑 输入数据所占得空间 辅助变量所占空间 一般情况下 所需存储量依赖于特定的输入 通常按最坏情况考虑 如何学习数据结构 了解常见的抽象数据类型对每种ADT 了解常见的逻辑结构设计逻辑结构是最难的 对给定的逻辑结构 自己设计物理结构物理结构一般只是数组和链结构数组可以随机访问 设计下标计算公式 经典例子 哈希表 二叉堆 并查集 线段树链结构应该根据元素间关系 链接 进行 移动 经典例子 伸展树 二项堆 跳跃表 特殊算法需要自己归纳出ADT并设计逻辑结构PQ树 后缀树 1 算法的计算量的大小称为计算的 B A 效率B 复杂性C 现实性D 难度2 算法的时间复杂度取决于 C A 问题的规模B 待处理数据的初态C A和B3 计算机算法指的是 C 它必须具备 B 这三个特性 1 A 计算方法B 排序方法C 解决问题的步骤序列D 调度方法 2 A 可执行性 可移植性 可扩充性B 可执行性 确定性 有穷性C 确定性 有穷性 稳定性D 易读性 稳定性 安全性 4 一个算法应该是 B A 程序B 问题求解步骤的描述C 要满足五个基本特性D A和C 5 下面关于算法说法正确的是 D A 算法最终必须由计算机程序实现B 为解决某问题的算法同为该问题编写的程序含义是相同的C 算法的可行性是指指令不能有二义性D 以上几个都是错误的 6 下面说法错误的是 C 1 算法原地工作的含义是指不需要任何额外的辅助空间 2 在相同的规模n下 复杂度O n 的算法在时间上总是优于复杂度O 2n 的算法 3 所谓时间复杂度是指最坏情况下 估算算法执行时间的一个上界 4 同一个算法 实现语言的级别越高 执行效率就越低A 1 B 1 2 C 1 4 D 3 7 从逻辑上可以把数据结构分为 C 两大类 A 动态结构 静态结构B 顺序结构 链式结构C 线性结构 非线性结构D 初等结构 构造型结构8 在下面的程序段中 对x的赋值语句的频度为 C FORi 1TOnDOFORj 1TOnDOx x 1 A O 2n B O n C O n2 D O log2n 1 数据元素是数据的最小单位 F 2 记录是数据处理的最小单位 F 3 数据的逻辑结构是指数据的各数据项之间的逻辑关系 F 4 算法的优劣与算法描述语言无关 但与所用计算机有关 F 5 健壮的算法不会因非法的输入数据而