数据结构和数据库教案.ppt

《数据结构和数据库教案.ppt》由会员分享，可在线阅读，更多相关《数据结构和数据库教案.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构和数据库数据结构和数据库-2-课程简介课程简介n内容简介内容简介n数据结构数据结构n目的目的：掌握各种常用数据结构，提高学生：掌握各种常用数据结构，提高学生程序设计程序设计的能力的能力 n从逻辑结构、存储结构和数据的运算三个方面掌握数据从逻辑结构、存储结构和数据的运算三个方面掌握数据结构结构n针对问题，选择合适的数据结构，设计高效的算法针对问题，选择合适的数据结构，设计高效的算法n教材教材：严蔚敏等编著，：严蔚敏等编著，数据结构数据结构( (C C语言版语言版) )，清华大学出版社，清华大学出版社 n数据库数据库n目的目的：掌握：掌握数据库设计数据库设计思想，熟悉小型思想，熟悉小型DB

2、MS的基本数据操作的基本数据操作n关系数据理论、数据库设计、关系数据理论、数据库设计、SQL语言语言 n教材教材：王珊、陈红编著，：王珊、陈红编著，数据库系统原理教程数据库系统原理教程，清华大学出，清华大学出版社，版社，1998 n学时：学时：54/28 学分：学分：3.5-3-教学、实验与考核教学、实验与考核n资源资源nhttp:/ n考核要求考核要求n作业作业+平时：平时：15%n上机：上机：15% 上机报告上机报告n期末考试：期末考试：70%-4-教学参考书教学参考书nRobert L.Kruse, Clovis L. Tondo, Bruce P. Leung, Data Struct

3、ures & Program Design in C(2nd ed.), 1997, Prentice Hall.数据结构与程序设计数据结构与程序设计(C语言描述语言描述)-影印版影印版(gravure).北京：清华北京：清华大学出版社，大学出版社，1998.7.http:/www.china- n唐策善、黄刘生唐策善、黄刘生 编著，编著，数据结构数据结构( (第二版第二版) )，中国科学技术大学出，中国科学技术大学出版社，版社，2001. n岳丽华、丁卫群编著，岳丽华、丁卫群编著，数据库系统概论数据库系统概论，科学出版社，科学出版社，2000 n萨师煊、王珊，萨师煊、王珊，数据库系统概论数据

4、库系统概论( (第三版第三版) )，高等教育出版社，高等教育出版社，2000 数据结构部分数据结构部分线性表、栈和队列、数组线性表、栈和队列、数组树和二叉树、图树和二叉树、图查找、内部排序查找、内部排序第一章第一章 绪论绪论重点重点：数据结构的基本概念：数据结构的基本概念难点难点：ADT、算法复杂度算法复杂度-7-第一章第一章 绪论绪论1.1 什么是数据结构什么是数据结构1.2 基本概念和术语基本概念和术语1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现1.4 算法和算法分析算法和算法分析 1.4.1 算法算法 1.4.2 算法设计的要求算法设计的要求 1.4.3 算法效率的度量算法效

5、率的度量 1.4.4 算法的存储空间的需求算法的存储空间的需求-8-1.1 什么是数据结构什么是数据结构nNiklaus WirthAlgorithm + Data Structures = Programs Algorithm: 求解问题的策略求解问题的策略DS: 问题的数学模型问题的数学模型Programs: 为计算机处理问题编制的一组指令为计算机处理问题编制的一组指令n例例1：学生成绩单学生成绩单学号学号姓名姓名数据结构数据结构PB01001张平张平80PB01002王晴王晴85-9-1.1 什么是数据结构什么是数据结构n例例1：学生成绩单学生成绩单要求要求：给定学生的学号或姓名，要求打

6、印出其成绩；：给定学生的学号或姓名，要求打印出其成绩；若学生不存在，则报告没有该学生的信息。若学生不存在，则报告没有该学生的信息。计算机处理该问题时，应考虑计算机处理该问题时，应考虑：1) 数据及其存储数据及其存储：学生学生(学号学号,姓名姓名,成绩成绩) struct student char sNo8;char sName9;int nScore; astStudent200;2) 基本运算的实现基本运算的实现-10-1.1 什么是数据结构什么是数据结构n例例2：图书馆的书目检索系统自动化问题图书馆的书目检索系统自动化问题n例例3：计算机和人对弈问题计算机和人对弈问题n例例4：多叉路口交通

7、灯的管理问题多叉路口交通灯的管理问题n结论结论n描述这类描述这类非数值计算问题非数值计算问题的数学模型不是数的数学模型不是数学方程学方程,而是树、表和图之类的而是树、表和图之类的数据结构数据结构n数据结构描述现实世界实体的数据结构描述现实世界实体的数学模型数学模型及其及其上的上的操作操作在计算机中的在计算机中的表示和实现表示和实现-11-1.2 基本概念和术语基本概念和术语n数据数据(Data)n信息的信息的载体载体n能输入到计算机中被计算机程序处理的能输入到计算机中被计算机程序处理的符号符号集集n数据元素数据元素(Data Element)n数据的数据的基本单位基本单位n在计算机程序中作为一

8、个在计算机程序中作为一个整体整体进行考虑和处理进行考虑和处理n一个数据元素可以由若干一个数据元素可以由若干数据项数据项( (Data Item)Data Item)组成组成n数据项数据项是具有独立含义的最小标识单位是具有独立含义的最小标识单位n数据对象数据对象(Data Object)n性质相同的数据元素的集合性质相同的数据元素的集合 e.g. C= A, B, , Z -12-1.2 基本概念和术语基本概念和术语-数据结构数据结构n数据结构数据结构(Data Structure)n形式定义形式定义nData_Structure = ( D, S )nD-数据对象数据对象 nS该对象中各数据元

9、素之间的关系的有限集该对象中各数据元素之间的关系的有限集n四个基本的数据结构四个基本的数据结构n集合结构集合结构：关系集合是空集关系集合是空集顶点元素间无任何关系，顶点元素间无任何关系，R= 空集空集-13-1.2 基本概念和术语基本概念和术语-线性结构线性结构/树树n线性结构线性结构：元素间的关系是元素间的关系是1 : 1一个结点（除尾结点外）有且仅有一个直接前驱一个结点（除尾结点外）有且仅有一个直接前驱一个结点（除头结点外）有且仅有一个直接后继一个结点（除头结点外）有且仅有一个直接后继n树型结构树型结构：一般树、二叉树、森林一般树、二叉树、森林一个结点可以有多个直接后继（除叶子结点外），一

10、个结点可以有多个直接后继（除叶子结点外），但只有一个直接前驱（除根结点外）但只有一个直接前驱（除根结点外）-14-1.2 基本概念和术语基本概念和术语-图状结构图状结构图状结构图状结构：元素间的关系是元素间的关系是m : n一个结点可以有多个直接后继，也可以有多个直接前驱一个结点可以有多个直接后继，也可以有多个直接前驱-15-1.2 基本概念和术语基本概念和术语-逻辑结构逻辑结构n数据的逻辑结构数据的逻辑结构n特征特征n从从逻辑关系逻辑关系上描述数据，与数据的存储无关上描述数据，与数据的存储无关n从具体问题从具体问题抽象抽象出来的数据模型出来的数据模型n与与数据元素数据元素本身的本身的形式形式

11、、内容内容无关无关n与与数据元素数据元素的相对的相对位置无关位置无关n分类分类n线性结构线性结构：线性表：线性表n非线性结构非线性结构：树、图：树、图-16-1.2 基本概念和术语基本概念和术语-存储结构存储结构n数据的存储结构数据的存储结构n数据结构在计算机中的表示数据结构在计算机中的表示n依赖于计算机程序设计语言依赖于计算机程序设计语言n数据元素之间的关系的表示数据元素之间的关系的表示n顺序映像顺序映像（顺序存储结构）（顺序存储结构）向量（表格存储结构）向量（表格存储结构）n非顺序映像非顺序映像（链式存储结构）（链式存储结构）单链表、双链表、多重链表、循环链表单链表、双链表、多重链表、循环

12、链表n索引存储结构索引存储结构n散列存储结构散列存储结构-17-1.2 基本概念和术语基本概念和术语-抽象数据类型抽象数据类型n抽象数据类型抽象数据类型n数据类型数据类型n一个值的集合一个值的集合n定义在该值集上的一组操作定义在该值集上的一组操作nC语言中的基本数据类型语言中的基本数据类型nint short char float double n抽象数据类型抽象数据类型n一个一个数学模型数学模型及定义在该模型上的一组及定义在该模型上的一组操作操作n如：如：矩阵矩阵 + + （求转置、加、乘、逆、特征值）（求转置、加、乘、逆、特征值） -18-1.2 基本概念和术语基本概念和术语-抽象数据类型

13、抽象数据类型n抽象数据类型定义抽象数据类型定义n（D, S, P）nD数据对象数据对象SD上的关系集上的关系集P对对D的基本操作集的基本操作集ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象的定义数据对象：数据对象的定义 数据关系：数据关系的定义数据关系：数据关系的定义 基本操作：基本操作的定义基本操作：基本操作的定义 ADT 抽象数据类型名抽象数据类型名基本操作名（参数表）基本操作名（参数表）初始条件：初始条件描述初始条件：初始条件描述操作结果：操作结果描述操作结果：操作结果描述-19-1.2 基本概念和术语基本概念和术语-抽象数据类型抽象数据类型n抽象数据类型的特征抽象数据类型的特

14、征n数据抽象数据抽象对程序处理的实体的描述对程序处理的实体的描述,强调的是其本质的特强调的是其本质的特征、其所能完成的功能以及它和外部养护的接口征、其所能完成的功能以及它和外部养护的接口(即外界使用它的方法即外界使用它的方法) n数据封装数据封装将实体的外部特性和其内部实现细节分离，并且将实体的外部特性和其内部实现细节分离，并且对外部养护隐藏其内部实现细节对外部养护隐藏其内部实现细节-20-1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现n通过程序设计语言中的类型来实现通过程序设计语言中的类型来实现nCn抽象数据类型抽象数据类型n数据对象数据对象 结构体结构体n基本操作基本操作 函数函

15、数nC+，Javan抽象数据类型抽象数据类型 类类 class n数据对象数据对象 数据成员数据成员n基本操作基本操作 成员函数成员函数(方法方法) n一个例子一个例子-21-1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现n表示：伪语言表示：伪语言n借用程序设计语言的结构描述借用程序设计语言的结构描述-简洁、严谨简洁、严谨n忽略程序设计语言的细节忽略程序设计语言的细节-简洁简洁n伪伪C语言与语言与C语言的区别语言的区别n抽象数据类型抽象数据类型：typedefn赋值赋值：成组赋值、交换赋值成组赋值、交换赋值n选择语句选择语句： switch的扩展的扩展n输入输入/输出输出：可以忽略格

16、式串可以忽略格式串n头文件、辅助变量定义头文件、辅助变量定义：忽略忽略nC的扩展的扩展：引入引入C+的引用参数表示变参的引用参数表示变参-22-1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现n伪伪C中的引用参数中的引用参数C的扩展的扩展C的虚实结合的虚实结合：单向的值传递：单向的值传递问题问题：如何简单地表示返回多个值？：如何简单地表示返回多个值？C支持的策略支持的策略：全局变量、将形参定义为指针类型、全局变量、将形参定义为指针类型、将返回值定义为指针类型将返回值定义为指针类型C+的另一种处理的另一种处理：引用参数：引用参数 类型说明符类型说明符 &引用参数名引用参数名引用参数与实在

17、参数共享存储单元引用参数与实在参数共享存储单元利用引用参数表示利用引用参数表示变参变参(可以将在被调用函数体中改变了可以将在被调用函数体中改变了的值代回主调处）的值代回主调处）-23-1.4 算法和算法分析算法和算法分析-定义和特性定义和特性n定义定义对特定问题的求解步骤的一种描述，指令的有对特定问题的求解步骤的一种描述，指令的有限序列限序列n特性特性n有穷性有穷性：算法在执行有穷步后能结束：算法在执行有穷步后能结束n确定性确定性：每一指令有确切的含义，无二义：每一指令有确切的含义，无二义n可行性可行性：每一操作都可以通过已经实现的基本运算：每一操作都可以通过已经实现的基本运算执行有限次来实现

18、执行有限次来实现n输入输入：零个或多个输入：零个或多个输入n输出输出：一个或多个输出：一个或多个输出-24-1.4 算法和算法分析算法和算法分析-算法评价标准算法评价标准n算法评价标准算法评价标准n正确性正确性n程序不含语法错误程序不含语法错误n对于几组输入数据能够得出满足要求的结果对于几组输入数据能够得出满足要求的结果n对于精心挑选的典型、苛刻的几组输入数据对于精心挑选的典型、苛刻的几组输入数据 n对于一切合法的输入数据对于一切合法的输入数据 n可读性可读性n健壮性健壮性：异常处理机制：异常处理机制n高效率高效率与与低存储量低存储量需求需求-25-1.4 算法和算法分析算法和算法分析-事后统

19、计事后统计n算法效率的度量算法效率的度量n事后统计事后统计n利用计算机内部的计时功能利用计算机内部的计时功能n缺陷缺陷n运行依据算法编制的程序运行依据算法编制的程序n时间统计量依赖于计算机的软硬件环境时间统计量依赖于计算机的软硬件环境 double start, stop; time (&start); mainprocess(n, ); time (&stop); double runTime = stop - - start; printf ( ”%d%dn , n, runTime );-26-1.4 算法和算法分析算法和算法分析-时间分析时间分析n事前分析估算事前分析估算(时间时间)n

20、算法的策略算法的策略n问题规模问题规模n编程语言编程语言n编译器产生的机器代码质量编译器产生的机器代码质量n机器执行指令的速度机器执行指令的速度n时间复杂度度量时间复杂度度量n运行时间运行时间 = = 算法中每条语句执行时间之和算法中每条语句执行时间之和n每条语句执行时间每条语句执行时间 = = 频度频度 * * 语句执行一次所需时间语句执行一次所需时间n设每条语句执行一次所需时间为设每条语句执行一次所需时间为单位时间单位时间n(渐进渐进)时间复杂度时间复杂度： T(n) = O(f(n) 例子例子n常见函数的增长率常见函数的增长率：P16-27-1.4 算法和算法分析算法和算法分析-空间分析

21、空间分析n空间复杂度度量空间复杂度度量n算法的存储量算法的存储量n存储空间的固定部分存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等如数组元素、结构成分、对象的数据成员等)变量变量所占空间所占空间n可变部分可变部分尺寸与实例特性有关的成分变量所占空间、引用变尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间、通过量所占空间、递归栈所用空间、通过malloc/new和和free/delete命令动态使用空间命令动态使用空间n空间复杂度空间复杂度: 由于算法引入的额外空间由于算法引入的额外空间n(渐进渐进)空间复杂度空间复杂度： S(n) = O(f(n)