Data Structure1.ppt

DataStructure 数据结构主讲 周颖颖办公室 宏博楼311 数据结构和计算机系统的关系 你知道吗 操作系统内核中怎样管理内存操作系统中的进程如何管理一个程序是如何运行的 课程性质 计算机应用专业一门专业基础课在计算机各处领域中均会使用到数据结构的有关知识全面地掌握各种常用的数据结构内容多 难度大较强的程序设计能力 C语言和数学基础 考核目标 P240闭卷 笔试 150分钟共6学分 考前修完实验1学分P237P239考题覆盖到章节并分能力层次和考题难易 课程内容及掌握程度要求 绪论线形结构 包括线形表 栈 队列和数组等内容非线形结构 包括树 图等内容排序查找文件掌握程度 各章不同 实践考核说明 1 书后实践环节实验须在课程考试前完成2 学期结束前实践考核 上机考试120分钟 包括修改程序 或填写语句 和上机调试程序Windows环境下的TurboC系统考题一般为三道题左右 涵盖实验内容的三分之二以上 由主考学校批改 上机环境说明 VC6 0Turbocforwindows Cfree其他 基本要求 从数据结构的逻辑结构 存储结构和数据运算三个方面去掌握线性表 栈 队列 串 数组 广义表 树 图和文件等常用的数据结构 掌握在各种常用的数据结构上实现的排序和查找的运算对算法的时间和空间复杂性有一定的分析能力针对简单应用问题 应能选择合适的数据结构及设计有效的算法之一 学习方法 熟知课程要求 有的放矢掌握每章考核知识点和要求 掌握重点掌握各种数据结构的定义和实现熟记教材重点算法 自行强化程序设计经验 多动手 第一章绪论 学习目标和要求P228考核知识点1 数据结构的基本概念和术语 要求达到 识记 层次 2 数据结构在软件系统中的作用 要求达到 识记 层次 3 算法的描述和分析 要求达到 领会 层次 主要内容 1 2数据结构及计算机系统中作用 记 1 1基本概念和术语 记 1 3算法描述和分析 领会 重点 数据结构的逻辑结构 存储结构及数据运算的概念和关系难点 算法复杂度分析 1 2数据结构 计算机是一门研究用计算机进行信息表示和处理的科学 这里面涉及到两个问题 信息的表示信息的处理信息的表示和处理又直接关系到处理信息的程序的效率 必须分析待处理的对象的特征及各对象之间存在的关系 这就是数据结构这门课所要研究的问题 什么是数据结构计算机的程序是对信息进行加工处理 在大多数情况下 这些信息并不是没有组织 信息 数据 之间往往具有重要的结构关系 这就是数据结构的内容 数据结构在各种软件系统中所起的作用程序 算法 数据结构 选择合适的数据结构是解决应用问题的关键步骤 例1 电话号码查询系统 设有一个电话号码薄 它记录了N个人的名字和其相应的电话号码 假定按如下形式安排 a1 b1 a2 b2 an bn 其中ai bi i 1 2 n 分别表示某人的名字和对应的电话号码要求设计一个算法 当给定任何一个人的名字时 该算法能够打印出此人的电话号码 如果该电话簿中根本就没有这个人 则该算法也能够报告没有这个人的标志 算法的设计 依赖于计算机如何存储人的名字和对应的电话号码 或者说依赖于名字和其电话号码的结构 数据的结构 直接影响算法的选择和效率 上述的问题是一种数据结构问题 可将名字和对应的电话号码设计成 二维数组 表结构 向量 假定名字和其电话号码逻辑上已安排成N元向量的形式 它的每个元素是一个数对 ai bi 1 i n数据结构还要提供每种结构类型所定义的各种运算的算法 例2田径赛时间安排 六个项目比赛 每人最多参加3个有5名选手报名抽象为对无向图进行 着色 操作 即用尽可能少的颜色去给图中每个顶点着色 使得任意两个有边连接的相邻顶点着上不同的颜色 每一种颜色表示一个比赛时间 着上同一种颜色的顶点是可以安排在同一时间内竞赛的项目 1 2基本概念和术语数据 Data 是对信息的一种符号表示 在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称 数据元素 DataElement 是数据的基本单位 在计算机程序中通常作为一个整体进行考虑和处理 一个数据元素可由若干个数据项组成 数据项是数据的不可分割的最小单位 数据对象 DataObject 是性质相同的数据元素的集合 是数据的一个子集 数据结构 DataStructure 是相互之间存在一种或多种特定关系的数据元素的集合 数据类型 在一种程序设计语言中 变量所具有的数据种类 例 在C语言中数据类型 基本类型和构造类型基本类型 整型 浮点型 字符型构造类型 数组 结构 联合 指针 枚举型 自定义数据对象 某种数据类型元素的集合 例 英文字符类型的数据对象是 A B C D E F 数据结构的逻辑结构 存储结构及数据运算的含义及其相互关系 逻辑结构 独立与计算机的硬件结构的一种抽象的数学模型存储结构 也就是逻辑结构在计算机中的具体实现 它是一个依赖与计算机硬件的结构 基本运算 即定义在某种逻辑结构上的具体操作 关心它 做什么 运算实现 就是如何去实现某种具体的运算 即让我们知道该 怎么做 算法评价 每一种运算实现的不同方法 所对应的时间性能 空间性能都是不同 数据结构的逻辑结构 简称数据结构数据之间的相互关系称为逻辑结构 通常分为2类基本结构 一 线性结构结构中的数据元素之间存在一对一的关系 1 4章 二 非线性结构结构中的数据元素之间存在一对多的关系 5 7章 学生成绩表数据结构 直接前趋直接后趋开始结点终端结点结点间的关系构成了逻辑结构计算机如何表示各结点间的关系 如何进行查找 删除 插入等数学运算 数据存储结构的四种方法 顺序存储 数组逻辑相邻的结点存储在物理相邻的存储单元链式存储 指针不要求物理相邻索引存储存储结点并附加索引表 稠密索引 稀疏索引 散列存储根据结点关键字计算存储地址 算法 是对特定问题求解步骤的一种描述算法是指令的有限序列 其中每一条指令表示一个或多个操作 算法是一系列将输入装换为输出的计算步骤基本运算和实现 2 7中针对不同数据结构 8 9章 用语言描述计算过程 1 3算法的描述与分析 算法的特点 理解 1 有穷性一个算法必须总是在执行有穷步之后结束 且每一步都在有穷时间内完成 2 确定性算法中每一条指令必须有确切的含义 且算法只有一个入口和一个出口 3 可行性算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的 4 输入一个算法有零个或多个输入 这些输入取自于某个特定的对象集合 5 输出一个算法有一个或多个输出 这些输出是同输入有着某些特定关系的量 算法设计的要求评价一个好的算法有以下几个标准 1 正确性 Correctness 算法应满足具体问题的需求 2 效率与存储量需求效率指的是算法执行的时间 存储量需求指算法执行过程中所需要的最大存储空间 3 可读性 Readability 算法应该好读 以有利于阅读者对程序的理解 4 健壮性 Robustness 算法应具有容错处理 当输入非法数据时 算法应对其作出反应 而不是产年莫名其妙的输出结果 算法耗费的时间 语句执行时间之和每条语句执行时间 频度 语句执行一次时间假设每条语句执行一次均为单位时间频度 是指该语句重复执行的次数 算法的时间特性 例 for i 0 i n i n 1for j 0 j n j n n 1 c i j 0 n2for k 1 k n k n2 n 1 c i j a i k b k j n3 由于是一个三重循环 每个循环从1到n 则总次数为 n n n n3渐进时间复杂度为T n O n3 时间复杂度 问题的规模 输入量 整数表示 时间复杂度 TimeComplexity 一般情况下 算法中基本操作重复执行的次数是问题规模n的某个函数 算法的时间量度 称作算法的时间复杂度 n T n 的数量级称为渐进时间复杂度 记作T n O f n 渐进时间复杂度是算法的时间性能主要评价标准 例 temp i j j j temp 语句频度为 即时间复杂度为 1 例 for i 1 i n 1 i x s x 语句频度为 2n其时间复杂度为 O n 即时间复杂度为线性阶 例 for i 1 i n i for j 1 j n j x s x 语句频度为 2n2其时间复杂度为 O n2 即时间复杂度为平方阶 定理 若A n amnm am 1nm 1 a1n a0是一个m次多项式 则A n O nm 语句频度为 1 2 3 n 2 1 n 2 n 2 2 n 1 n 2 2 n2 3n 2 时间复杂度为O n2 即此算法的时间复杂度为平方阶 例 for i 2 i n I for j 2 j i 1 j x a i j x 渐进时间复杂度从宏观上评价 T1 n 100n2和T2 n 5n3 1 n20习题1 5 算法时间复杂度还依赖于输入示例的初始状态 在数值A 0 n 1 中查找给定值K的算法 i n 1 while i 0考虑 1 A中没有与K相等的元素 2 A中最后一个元素A n 1 K最坏时间复杂度 平均时间复杂度 以下六种计算算法时间的多项式是最常用的 其关系为 O 1 O lgn O n O nlgn O n2 O n3 指数时间的关系为 O 2n O n O nn 当n取得很大时 指数时间算法和多项式时间算法在所需时间上非常悬殊 算法的存储空间需求空间复杂度 算法所需存储空间的度量 记作 S n O f n 其中n为问题的规模 或大小 C语言知识点 数组结构体指针例 输入5个学生的姓名 学号 性别和3门课成绩 并计算平均分 1 若一个算法的时间复杂度用T n 表示 其中n的含义是 A 问题规模B 语句条数C 循环层数D