【数据结构课件】绪论.pptVIP

2006-2-2 涪陵师范学院计算机科学系 李长志 数据结构 计算机科学系专业技术基础课程 主讲：李长志 联系方式： Email:lichangzhi024@ MSN: lichangzhi024@ 关于数据结构 学习数据结构的目的 我们采用的教材 课程教学内容整体安排 学习数据结构的目的 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科 与《离散数学》不同的是，《数据结构》不仅仅考虑数据本身的数学性质，而且还必须考虑数据的存储结构。 教学要求： 学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析技术； 学会复杂程序设计，要求学生能够初步掌握符合软件工程规范的较为复杂的程序设计的方法。 我们采用的教材 《数据结构》（C语言版） 严蔚敏等编著，清华大学出版社出版 “虽然C语言不是抽象数据类型的理想描述工具”，但“鉴于‘面向对象程序设计’并非数据结构的先修课程”，“全书采用类C语言作为数据结构和算法的描述语言” 本书假设读者掌握C语言程序设计基本技术且未学习过《离散数学》课程。 课程教学内容整体安排 对书中目录页中带**的章节和第5，8，11和12章不做要求 进度安排： 绪论：数据结构中的基本概念、算法的描述方式和分析方法 线性表：数组与指针的使用，随机存储设备，内存与文件 栈与队列：操作受限的线性表，递归分析 字符串与数组 树与二叉树： 图 查找与排序 主要算法设计策略： 1.2 基本概念和术语 数据（Data） 数据元素（Data Element） 数据结构（Data Structure） 数据对象（Data Object） 数据类型（Data Type） 抽象数据类型（Abstract Data Type） 数据与数据元素 数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。 数值性数据 非数值性数据 数据元素：是数据的最小单位，有时一个数据元素由数据项组成（具有独立含义的最小标识单位） 数据结构的内容 数据结构指数据元素间的关系。它包括逻辑结构和物理结构。 逻辑结构：从解决问题的需要出发，为实现必要的功能所建立的数据结构，它属于用户的视图，是面向对象的。 物理结构（存储结构）：指数据该如何在计算机中存放，是数据逻辑结构的物理存储方式，是属于具体实现的视图，是面向计算机的。 数据对象与数据类型 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。 抽象数据类型（ADT） 数据的抽象 抽象数据类型 抽象数据类型定义了一个数据对象，数据对象中各个元素间的结构关系以及一组处理数据的操作。 ADT包括定义和实现两个方面，其中，定义是独立于实现的。定义仅给出ADT的逻辑特性，不必考虑如何在计算机中实现。 1.3 用C语言描述ADT C语言的基本数据类型 结构体定义 函数声明与函数定义 指针与数组 1.4 算法和算法分析 算法设计的要求 算法效率的度量 时间复杂度 运行时间：问题规模的函数f (n) 时间复杂度T(n)的渐进性分析Ο、Ω、Θ 操作计数和执行步数：最好、最坏和平均操作数 空间复杂度 代码空间 数据空间 环境栈 时间复杂度的表示工具 Ο(big oh)若lim T(n) / f(n) →0 ， 则T(n)= Ο( f(n) ) ; Ω(big omega)若lim f(n) / T(n) →0 ， 则T(n)= Ω( f(n) ) ; Θ(big theta)若lim f(n) / T(n) →c ， 则T(n)= Θ( f(n) ) ; 算法时间复杂度的后期测试 在算法中的某些部位插装时间函数 time ( ) 测定算法完成某一功能所花费的时间 空间复杂度 指令空间 数据空间 存储常量和简单变量的存储空间 存储复合变量的存储空间和动态分配的空间 执行栈（环境栈） 其它 *计算机科学系 李长志 * 一个算法所耗费的时间，应该是该算法中每条语句的执行时间之和，而每条语句的执行时间又是该语句的执行次数（频度）与该语句执行一次所需时间的乘积。 我们假定，每条语句一次执行的时间都是相同的，为单位时间。这样我们对时间的分析就可以独立于软硬件系统。 时间复杂度 我们将算法求解问题的输入量称为问题的规模，用一个整数来表示，一个算法的时间复杂度是该算法的时间耗费，一般地说，时间复杂度是问题规模的函数 － T( n )。 当问题的规模n 趋于无穷大时，把时间复杂度T( n )的数量级（阶）