绪论学习辅助资料

第一章绪论 数值问题与非数值问题 1 数值问题例1已知 游泳池的长len和宽wide 求面积area 设计求解问题的方法 编程main intlen wide area scanf d d n 1 1本课程研究的问题 建模型 问题涉及的对象 游泳池的长len宽wide 面积area 对象之间的关系 area len wide 建模型 问题涉及的对象 课程 课程之间的关系 同一研究生选修的课程之间有某种 冲突 关系 同一个研究生选修的不能按排在同一时间内考试 顶点 表示课程 同一研究生选修的课程用边连接 有边连接的课程不能按排在同一时间考试 2 非数值问题例2已知研究生选课情况 安排课程考试的日程 要求在尽可能短的时间内完成考试 1 1本课程研究的问题 设计求解问题的方法 每一种颜色代表一个考试时间 着上相同颜色的顶点是可以按排在同一时间考试的课程 用尽可能少的颜色为图的顶点着色 使相邻的顶点着上不同的颜色 如下是一种考试日程 第一天 算法分析 A 计算机图形学 C 第二天 形式语言 B 模式识别人工智能 D 第三天 计算机网络 E 第四天 人工智能 F 1 1本课程研究的问题 课程考试可用图的着色法求解问题 求解考试日程的流程设G表示课程关系图 V是图G中所有尚未着色的顶点集合 NEW表示可以用新颜色着色的顶点集合 1 I 1 V 图中所有顶点的集合 2 若V非空DO置NEW为空集合 在V中找出所有 不相邻 的顶点将这些顶点加入NEW 从V中去掉这些顶点 第I天考试课程为NEW中顶点所对应的课程 以某种形式输出NEW中顶点所对应的课程 I I 1 3 若V空 结束 编程 存储图 集合 实现图集合的操作 1 1本课程研究的问题 数值问题 对象 len wide area 用数值表示 对象之间的关系 area len wide 可用方程或函数表示 数据存储 可用程序设计语言中的实型变量存储数据 问题求解方法 用某种计算方法求解 非数值问题 对象 课程 用课程名表示 对象之间的关系 课程间有 冲突 关系 数据及数据之间的关系存储 问题求解方法 不能用数值表示 课程之间的这种关系不能用方程或函数表示 3数值问题与非数值问题的比较 1 1本课程研究的问题 1 1本课程研究的问题 数据结构的研究问题 非数值数据之间的结构关系 及如何表示 如何存储 如何处理 本课程讨论的问题 应用中常用的几种数据间的结构关系 及如何表示 如何存储 如何处理 1 2数据结构的有关概念 1 2数据结构的有关概念 一本书的书目信息 什么是数据结构 数据结构的地位 数学 硬件 软件之间核心专业基础课 数据结构 带有结构和操作的数据元素集合 结构 数据元素之间的关系 操作 对数据的加工处理 对每种数据结构 主要讨论如下两方面的问题 1 数据的逻辑结构 数据结构的基本操作 2 数据的存储结构 数据结构基本操作的实现 按照逻辑关系组织起来的一批数据 按一定的存储方法把它存储在计算机中 并在这些数据上定义了运算的集合 一数据的逻辑结构1常见逻辑关系有 线性结构 线性表 栈 队列 字符串 多维数组 广义 树结构图结构数据的逻辑结构的表示 1 二元组B D R D 结点 初等或组合类型 的集合 R D上的有穷关系的集合 一般R r r是K上的一个二元关系例如 r ki K 1 i n 2 图示表示 1 2数据结构的有关概念 线性结构除第一个元素和最后一个元素之外 其他元素都有且仅有一个直接前趋 有且仅有一个直接后继 L 其中D a1 a2 a3 an R r r 1 2数据结构的有关概念 树结构有且仅有一个称为根的结点没有前驱 其它结点有且仅有一个前驱 所有结点可以有零个或多个后继 除根外的其他结点 都存在唯一条从根到该结点的路径T D A B C D E F G H I J R r r A B 1 2数据结构的有关概念 图结构每个元素可以有零个或多个直接前趋 零个或多个直接后继 G1 V1 v0 v1 v2 v3 v4 E1 v0 v1 v0 v3 v1 v2 v1 v4 v2 v3 v2 v4 G2 V2 v0v1 v2 v3 E2 二数据的存储结构 顺序存储结构用一组连续的内存单元依次存放数据元素 通过元素的存储顺序反映数据元素之间的逻辑关系 链式存储结构 用内存中任意一组单元存放数据元素 通过保存元素的存储位置来表示数据元素之间的逻辑关系 三数据的运算逻辑结构和存储结构都相同但运算不同 则数据结构不同 例如 栈与队列 对于一种数据结构 常见的运算 建立数据结构 清除数据结构 插入一个新数据元素 删除某个数据元素 修改某个数据元素 排序 检索 四数据结构基本操作的实现 基本操作在计算机上的实现 算法 1 2抽象数据类型数据抽象与过程抽象实现信息隐蔽和局部化 以一个严格定义的过程接口的方式 在数据结构上提供一个抽象 数据的实现和处理细节被隐蔽了 抽象数据类型定义了一组运算的数学模型 与物理存储结构无关 使软件系统建立在数据之上 一算法的概念算法是求解问题的操作序列 算法的基本特征 1 输入 0个或多个输入 2 输出 1个或多个输出 3 有穷性 算法必须在有限步内结束 4 确定性 组成算法的操作必须清晰无二义性 5 有效性 组成算法的操作必须能够在计算机上实现 求两个正整数m n中的最大数MAX的算法 1 若m n则max m 2 若m n则max n 例 二算法的度量 算法设计的两个目标 易读 易编码和调试 软件工程 充分利用计算机资源 算法和数据结构 评估方法 实验 运行程序 渐进分析 关键资源 影响运行时间的因素往往与问题的输入规模n有关 1算法时间复杂度T n 本课程采用以求解问题的基本操作 原操作 的执行次数作为算法时间的度量 1 4算法与算法分析 O n3 称为矩阵相乘算法时间复杂度 O n3 表示矩阵相乘算法执行时间与n3成正比 即O n3 与n3同一数量级 n阶矩阵相乘的算法 For i 1 i n i For j 1 j n j c i j 0 For k 1 k n k c i j a i k b k j 例 矩阵相乘的基本运算 乘法加法 算法的时间复杂度一般来说 设算法中基本操作的执行次数是问题规模n的某个函数f n 算法的时间复杂度记作 T n O f n 它表示随问题规模n的增大 算法执行时间的增长率与f n 的增长率相同 算法的时间复杂度级别 O 1 O logn O nlogn O n O n2 O 2n 1 4算法与算法分析 有些算法 基本操作执行次数与问题的输入数据有关 这时可考虑 1 平均时间复杂度 2 最差情况下的时间复杂度 3 最佳情况下的时间复杂度