数据结构-使用C语言朱战立.ppt

教材：教材： 朱战立编著，数据结构朱战立编著，数据结构使用使用 C C语言（第语言（第3 3版），西安交通大版），西安交通大 学出版社，学出版社，20032003年年 数数 据据 结结 构构 2 学时数：70（50学时授课20学时上机） 教材：朱战立编著，数据结构（使用C语言）第 3版，西 安交通大学出版社 ，2003年 参考书： 1严蔚敏等，数据结构（C语言版），清华大学 出版社 2 数据结构学习指导与典型题解，朱战立等编 著，西安交通大学出版社 ，2002年 3 内内 容容 安安 排排 章内 容 学时 章 内 容 学时 1绪 论47树和二叉树 10 2线性表48图10 3栈和队列89排序4 4串210查找4 5数组411 上机（共10次 ） 20 合计70 4 1、上课认真听讲，适当做好笔记。 2、考试成绩分两部分：平时成绩（包括出勤和上机实验）占 20%，期末成绩占80%。 3、课后需要多读课文和参考书，上网查看相关内容，在理解 基本内容的基础上，多看、多做习题。 4、上机实验十分重要，一定要在上机前做好充分准备，多采 用不同的数据存储结构和不同的实现算法解决一个问题。 对学生的几点要求对学生的几点要求 5 第第1 1章 绪 论章 绪 论 讨论5个问题： 1.1 1.1 数据结构数据结构的基本概念的基本概念 1.2 1.2 抽象数据类型和软件构造方法抽象数据类型和软件构造方法 1.4 1.4 算法和算法的时间复杂度算法和算法的时间复杂度 1.5 1.5 算法书写规范算法书写规范 6 1.1 1.1 数据结构的基本概念数据结构的基本概念 1 1、举例、举例 建立一个学生档案系统。学生表包括学号、姓名、 性别、籍贯。要求：查找“王红”是否存在。 解决的方法步骤： 1) 如何记录所有学生记录（及选择何种逻辑数据结 构）？ 2) 选择何种存储结构？ v 若把所有记录依次存储在一个数组中采用 顺序存储结构 v 若采用指针链表采用链式存储结构 7 R=r； r=, ,.试分析该数据结 构属于哪种逻辑结构. 树型 30 作业 什么是逻辑结构与存储结构，他们之间 的关系如何？ 31 设有数据逻辑结构为：line=(D,R);其中 D=a，b，c，d，e，f,g；R=r；r=，,. 试画出对应的图形并说明属于哪种逻辑 结构. 32 将上述关系改为r=，,.试画出对应 的图形并说明属于哪种逻辑结构. 33 34 1.4 1.4 什么是抽象数据类型什么是抽象数据类型 1 数据类型与抽象数据类型的区别？ 2 抽象数据类型如何定义？ 3 抽象数据类型如何表示和实现？ 讨论 ： 35 1 数据类型与抽象数据类型的区别 数据类型：是一个值的集合和定义在该值上的 一组操作的总称。 抽象数据类型：由用户定义，用以表示应用问题的数 据模型。它由基本的数据类型构成，并包括一组相关 的服务（或称操作） 它与数据类型实质上是一个概念，但其特征是使用使用与 实现分离实现分离，实行封装封装和信息隐蔽信息隐蔽（独立于计算机） 36 2 抽象数据类型如何定义 抽象数据类型可以用以下的三元组来表示： ADT = （D，R，P） ADT抽象数据类型名 数据对象： 数据关系： 基本操作 ： ADT抽象数据类型名 ADT 常用 定义 格式 数据对象D上的关系集D上的操作集 37 1.4.3 抽象数据类型如何表示和实现 抽象数据类型可以通过固有的数据类型（如整型 、实型、字符型等）来表示和实现。 （参看课本P28，线性表的抽象数据类型，思考用 具体C语言如何实现） 注意：注意：上机时要必须用具体语言实现，如 C或C+等 队列的抽象数据类型定义 ADT Queue 数据对象：D=ai|aiElemSet, i=1,2, ,n, n0 数据关系：R1=|ai-1,aiD, i=1,2, ,n 约定a1为队列头，an为队列尾。 基本操作： InitQueue( (2) 执行算法所消耗的存储空间,其中主要考虑 辅助存储空间. (3) 算法应该易于理解,易于编码,易于调试等. 43 时间复杂度 (time complexity) 语句频度语句频度( (Frequency Count)Frequency Count) 语句重复执行的语句重复执行的 次数次数 语句的执行时间语句的执行时间 语句频度语句频度执行一次所需时执行一次所需时 间间 算法的执行时间算法的执行时间 所有语句执行时间的总和所有语句执行时间的总和 算法的渐近时间复杂度算法的渐近时间复杂度(asymptotic time (asymptotic time complexity)complexity)，简称时间复杂度，简称时间复杂度 因为语句的执因为语句的执 行时间取决于机器的硬件速度、指令类型、以行时间取决于机器的硬件速度、指令类型、以 及编译所产生的代码质量，所以将算法中基本及编译所产生的代码质量，所以将算法中基本 操作的最大语句频度作为算法执行时间的量度操作的最大语句频度作为算法执行时间的量度 ，它是问题规模，它是问题规模n n 的某个函数的某个函数 f (n)f (n) 44 时间复杂度时间复杂度表示法 记作记作T(n)=O(f T(n)=O(f (n)(n) （称为（称为 大大OO表示法表示法)，表示随问题规模表示随问题规模n n 的增大，算法执的增大，算法执 行时间的增长率和行时间的增长率和f(n) f(n) 的增长率相同。的增长率相同。 时间复杂度往往不是精确的执行次数，而是估时间复杂度往往不是精确的执行次数，而是估 算的数量级，它着重体现的是随着问题规模算的数量级，它着重体现的是随着问题规模n n的的 增大，算法执行时间的变化趋势增大，算法执行时间的变化趋势 时间复杂度的数量级时间复杂度的数量级 O O (1) aj+1) flag=1; aj aj+1; 分析算法复杂度： 最好情况：0次 最坏情况：1+2+3+n-1=n(n-1)/2 平均时间复杂度为:O(n2) 50 空间复杂度度量（Space ComplexitySpace Complexity） 空间是指执行算法所需用的存储空间空间是指执行算法所需用的存储空间 存储空间的固定部分存储空间的固定部分 程序指令代码的空间，常数、简单变量、定程序指令代码的空间，常数、简单变量、定 长成分长成分( (如数组元素、结构成员等如数组元素、结构成员等) )变量所占变量所占 的空间的空间 可变部分可变部分 递归栈所用的空间、通过递归栈所用的空间、通过malloc( )malloc( )和和free( )free( ) 等等 函数动态使用的空间函数动态使用的空间 与问题规模与问题规模 n n 的函数关系表示为：的函数关系表示为： S S（ n n ）= O= O（ f(n)f(n)） 52 本章小结本章小结 数据结构课程 数据结构算法程序，涉及数 学、计算机硬件和软件。 数据结构定义指互相有关联的数据元素的集合， 可用data_Structure=(D,R)表