数据结构(C语言版)PPT第一章.ppt

数 据 结 构 主讲人： 翁伟 高级语言程序设计 主讲：翁伟 E-mail ：xmutwei@163.com Mobile phoneQQ : 503424558 纪律： 手机调整为振动 保持安静 授课方式：理论+实践（2+2） 授课时间：16周+1周课程设计 高级语言程序设计 为什么学这门课程？学了有什么用？ 计算机语言学的基础学科 研究生入学考试科目 前导课程 高级语言程序设计 后续课程 算法设计与分析 实现语言 C/C++ 一、教学内容：1、数据结构基本概念数据、数据元素、数据对象、数据结构和数据类型等概念2、算法及算法分析性能分析与度量：算法的性能标准；空间复杂度度量；时间复杂度度量二、教学要求：1、了解数据、数据对象、数据元素、数据类型、数据结构、数据的逻辑结构与物理结构概念及逻辑结构与物理结构间的关系2、了解算法的定义、算法的特性、算法的时间代价、算法的空间代价3、掌握计算语句频度和估算算法时间复杂度的方法 第一章 绪论 1.1 什么是数据结构 1.2 基本概念 1.3 抽象数据类型 1.4 算法及其分析 1.1什么是数据结构 一、为什么要学习数据结构？ 1、电子计算机的主要用途： ?早期： 主要用于数值计算。 ?后来： 处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。 数值计算解决问题的一般步骤： 数学模型→选择计算机语言→编出程序→测试→最终解答。 数值计算的关键是：如何得出数学模型（方程）？ 程序设计人员比较关注程序设计的技巧。 非数值计算问题： 数据元素之间的相互关系一般无法用数学方程加以描述 用计算机解决问题的过程 引 例 十字路口的交通灯管理问题的数学模型 求解非数值计算的问题： 主要考虑的是设计出合适的数据结构及相应的算法。 即：首先要考虑对相关的各种信息如何表示、组织和存储？ 因此，简单说来，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。 问题：学习数据结构有什么用？ 答：计算机内的数值运算依靠数学方程，而非数值运算（如表、树、图等）则要依靠数据结构。 同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。 程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。 《算法+数据结构=程序》 ①提高复杂程序设计的能力 ②培养算法设计能力 ③为后继课程（如操作系统、编译原理等）打基础。 数据结构课程的形成和发展 形成阶段 60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。 1968年，美唐?欧?克努特教授开创了数据结构的最初体系，《计算机程序设计技巧》第一卷《基本算法》 ，“数据结构”被列入美国一些大学计算机科学系的教学计划。 发展阶段： 数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。 70年代后期，80年代初，我国高校陆续开设该课程。 《数据结构课程》所处的地位： 1.2 基本概念和术语 1.2.1基本概念 数据（data）： 数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合, 是计算机程序加工的”原料”。 分类： 数值性数据 非数值性数据 2、数据元素（data element） 3、数据对象（data object） 4、数据结构(data structure) 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构(Structure)。 数据结构是一堆数据元素和这些数据元素之间的关系的总和。 按数据元素之间关系的不同特性，通常有4类基本结构 （1）集合 结构中的数据元素除了“同属于一个集合”外，别无其它关系。 （2）线性结构 结构中的数据元素之间存在一对一的关系。 （3）树型结构 结构中的数据元素之间存在一对多的关系。 （4）图状结构或网状结构 结构中的数据元素之间存在多对多的关系。 数据结构的形式定义 用一个二元组表示，记为： Data_Structure = （D, S） 其中，D 是数据元素的有限集（即一个数据 对象），S 是该对象中所有数据成员之间的关系的有限集合。 例、用数据结构如何描述2行3列矩阵： 它是一个含6个数据元素{a1,a2,a3,a4,a5,a6} 的集合，且集合上存在“行