数据结构第一章绪论.ppt

第一章：绪论 宁波大学教师教育学院 杨勇波 数据结构 计算机科学中的专业基础课。介于数学、计算机硬件、计算机软件三者之间的核心课程。 课程特点 模块性强，易于整体把握 主线清晰，易于逻辑记忆 逻辑结构→存储结构→基本操作实现→应用 逻辑结构：定义、基本术语、性质 存储结构：逻辑关系、存储思想、存储结构定义 基本操作：基于某种存储结构、插入、删除、查找、性能分析 学习提要 掌握本课程所涉及到的基本名词、术语和概念，特别是数据的逻辑结构和存储结构之间的关系及性质。 了解抽象数据类型的定义、表示和实现方法。 理解算法设计的五个要素和基本要求；掌握算法效率的度量方法，着重学习算法的时间复杂度分析。 1.1 什么是数据结构 一、为什么要学习数据结构？ 1、电子计算机的主要用途： ?早期： 主要用于数值计算。 ?后来： 处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。 数据结构课程的形成和发展 形成阶段 60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。 1968年，美唐?欧?克努特教授开创了数据结构的最初体系，《计算机程序设计技巧》第一卷《基本算法》 ，“数据结构”被列入美国一些大学计算机科学系的教学计划。 发展阶段： 数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。 70年代后期，80年代初，我国高校陆续开设该课程。 交通灯管理问题的数学模型 图状结构 图状结构 图状结构 图状结构 图状结构 图状结构 综上所述，许多非数值计算问题的数学模型不是数学方程或公式,而是上面所述的线性结构、树形结构和图形结构之类的数据结构。 求解非数值计算的问题： 主要考虑的是设计出合适的数据结构及相应的算法。 即：首先要考虑对相关的各种信息如何表示、组织和存储？ 因此，简单说来，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。 问题：学习数据结构有什么用？ 答：计算机内的数值运算依靠数学方程，而非数值运算（如表、树、图等）则要依靠数据结构。 同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。 程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。 《算法+数据结构=程序》 ①提高复杂程序设计的能力 ②培养算法设计能力 ③为后继课程（如操作系统、编译原理等）打基础。 学习困难 知识丰富，易于混淆 概念多 相近概念多 概念之间联系多 算法灵活，不易把握 相同操作，基于不同的逻辑结构，其实现不同 相同操作，基于不同的存储结构，其实现不同 相似操作，基于不同的逻辑结构，其实现不同 相似操作，基于不同的存储结构，其实现不同 抽象性强，不易理解 学习方法 宏观把握，思路清晰 课前预习，上课认真听讲，做好笔记，课后复习（1：1：2） 要学会采用不同的数据存储结构和不同的实现算法解决一个问题 多看、多做习题 参考书 严蔚敏等，数据结构（C语言版），清华大学出版社 1.2 基本概念和术语 数据（Data）： ——客观事物的符号表示 数据元素（Data element）： ——数据的基本单位，一个数据元素可以由若干个数据项（Data item ）组成 数据项（Data item ）： ——数据的最小单位 数据对象（Data object）： ——性质相同的数据元素的集合，数据的子集 1.2 基本概念和术语 数据（data）： 数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合, 是计算机程序加工的”原料”。 分类： 数值性数据 非数值性数据 2、数据元素（data element） 3、数据对象（data object） 4、数据结构(data structure) 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构(Structure)。 数据结构是一堆数据元素和这些数据元素之间的关系的总和。 1.2 基本概念和术语 数据结构(data structure) 包括三方面内容： (1)数据元素之间的逻辑关系，也称为数据的逻辑结构； (2)数据元素及其关系在计算机存储器内的表示，称为数据的存储结构； (3)数据的运算，即对数据施加的操作。 1.2 基本概念和术语 数据结构的形式定义： Data str