数据结构c语言CH.ppt

2020 2 3 数据结构 阜阳师范学院数学与计算科学学院信息教研室王先超 数据结构是计算机及相关专业中一门重要的专业基础课程 当用计算机来解决实际问题时 就要涉及到数据的表示及数据的处理 而数据表示及数据处理正是数据结构课程的主要研究对象 通过这两方面内容的学习 为后续课程 特别是软件方面的课程打下了厚实的知识基础 同时也提供了必要的技能训练 因此 数据结构课程在计算机应用专业中具有举足轻重的作用 本课程的任务是 在基础方面 要求学生掌握常用数据结构的基本概念及其不同的实现方法 在技能方面 通过系统学习能够在不同存储结构上实现不同的运算 并对算法设计的方式和技巧有所体会 学业基础 本课程的先修课程为离散数学和高级语言程序设计 学习本课程必须具备高级语言程序设计 比如Pascal语言或C语言 的基础知识与基本技能 它的后续课程有操作系统和数据库原理等 进度安排 总学时68 其中课堂讲授60学时 实验教学8学时 第一章绪言 1 1什么是数据结构程序 数据结构 算法例1书目自动检索系统 书目文件 例2人机对奕问题 例3教学计划编排问题 一个教学计划包含许多课程 在教学计划包含的许多课程之间 有些必须按规定的先后次序进行 有些则没有次序要求 即有些课程之间有先修和后续的关系 有些课程可以任意安排次序 这种各个课程之间的次序关系可用一个称作图的数据结构来表示 如图1 3所示 有向图中的每个顶点表示一门课程 如果从顶点vi到vj之间存在有向边 则表示课程i必须先于课程j进行 数据结构定义 是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科 由以上三个例子可见 描述这类非数值计算问题的数学模型不再是数学方程 而是诸如表 树 图之类的数据结构 因此 可以说数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科 学习数据结构的目的是为了了解计算机处理对象的特性 将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理 与此同时 通过算法训练来提高学生的思维能力 通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高 1 2基本概念和术语数据 data 所有能输入到计算机中去的描述客观事物的符号数据元素 dataelement 数据的基本单位 也称节点 node 或记录 record 数据项 dataitem 有独立含义的数据最小单位 也称域 field 数据结构 datastructure 数据元素和数据元素关系的集合 数据的逻辑结构 只抽象反映数据元素的逻辑关系数据的存储 物理 结构 数据的逻辑结构在计算机存储器中的实现 1536 元素2 1400 元素1 1346 元素3 元素4 1345 h 链式存储 h 数据类型 高级语言中指数据的取值范围及其上可进行的操作的总称 例C语言中 提供int char float double等基本数据类型 数组 结构体 共用体 枚举等构造数据类型 还有指针 空 void 类型等 用户也可用typedef自己定义数据类型 typedefstruct intnum charname 20 floatscore STUDENT STUDENTstu1 stu2 p 1 3算法的描述和算法分析简介算法 algorithm 解决某一特定问题的具体步骤的描述 是指令的有限序列算法特性 算法的描述 采用C语言算法的评价 衡量算法优劣的标准正确性 correctness 可读性 readability 健壮性 robustness 效率与低存储量 算法效率 用依据该算法编制的程序在计算机上执行所消耗的时间来度量1 事后统计 利用计算机内记时功能 不同算法的程序可以用一组或多组相同的统计数据区分缺点 必须先运行依据算法编制的程序 所得时间统计量依赖于硬件 软件等环境因素 掩盖算法本身的优劣2 事前分析估计 一个高级语言程序在计算机上运行所消耗的时间取决于 依据的算法选用何种策略 问题的规模 程序语言 编译程序产生机器代码质量 机器执行指令速度同一个算法用不同的语言 不同的编译程序 在不同的计算机上运行 效率均不同 所以使用绝对时间单位衡量算法效率不合适 算法的时间复杂性 timecomplexity 算法的时间相当于程序时间中的运行时间部分 同样 关键操作的次数对时间复杂性的影响最大 假设 算法中关键操作执行的次数是问题特征 规模 n的某个函数f n 那么 算法的时间量度 复杂性 记作 T n O f n 在多数情况下 算法中关键操作执行的次数和包含它的语句的频度相同 语句的频度 frequencycount 指的是该语句重复执行的次数 所以 在实际应用时 用算法中语句的最大频度作为算法的时间复杂性 例1 x s 0 将x自增看成是基本操作 则语句频度为 即时间复杂度为 1 如果将s 0也看成是基本操作 则语句频度为 其时间复杂度仍为 1 即常量阶 例2 for I 1 I n 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 证略 例 for i 2 i n I for j 2 j i 1 j x a i j x 语句频度为 1 2 3 n 2 1 n 2 n 2 2 n 1 n 2 2 n2 3n 2 时间复杂度为O n2 即此算法的时间复杂度为平方阶 一个算法时间为O 1 的算法 它的基本运算执行的次数是固定的 因此 总的时间由一个常数 即零次多项式 来限界 而一个时间为O n2 的算法则由一个二次多项式来限界 以下六种计算算法时间的多项式是最常用的 其关系为 O 1 O logn O n O nlogn O n2 O n3 指数时间的关系为 O 2n O n O nn 当n取得很大时 指数时间算法和多项式时间算法在所需时间上非常悬殊 因此 只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法 那就取得了一个伟大的成就 1 4例题解析 选择题1 下列四种基本的逻辑结构中 数据元素之间关系最弱的是 A集合B线性结构C树形结构D图状结构2 在数据结构中 从逻辑上可以把数据结构分为 A动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构D内部结构和外部结构3 一个存储结点存放一个 A数据项B数据元素C数据结构D数据类型4 下列时间复杂度最差的是AO log2n BO 1 CO 2n D n2 5 线性表中各元素是 关系 A网状B集合C有序D层次 判断题1 算法的时间复杂度和空间复杂度合称为算法的复杂度 2 每个数据结构都具备三个基本运算 插入 删除和查找 3 算法必须具有输入 输出和正确性