西安文理学院精品课 《数据结构》 教 案 计算机科学系 韩利凯 《数据结构》 第一章 绪论 [教学目标] 掌握数据结构的定义、内容、方法、描述、评价。 [重点、难点] 数据结构的研究范围，研究采用的方法，算法规则描述的工具，对算法作性能评价。 [教学方法] 用多媒体课件（ ppt ）以及与生活实例相结合等方法讲授，这样便于描述相关概念及学生记笔记，加深他们的印象，使基础知识掌握地比较牢固。 [学习要点] 1. 熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。 2. 了解抽象数据类型的定义、表示和实现方法。 3．理解算法五个要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入执行相同的路径）；③有输入；④有输出；⑤可行性（用以描述算法的操作都是足够基本的）。 4．掌握计算语句频度和估算算法时间复杂度的方法。 1 .1 什么是数据结构（定义） 首先介绍数据结构的相关名词。 1. 数据（Data） 数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。。 2. 数据元素（Data Element） 数据元素是组成数据的基本单位 ,是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。例如：学生登记表是数据，每一个学生的记录就是一个数据元素。 3. 数据对象（Data Object） 数据对象是性质相同的数据元素的集合，是数据的一个子集。 4. 数据结构（DATA Stru ctu re） 数据结构是指相互之间存在一种或多种特定关系的数据元素集合，是带有结构的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。 5. 数据类型(Data Type) 数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。 6. 数据抽象与抽象数据类型 １） 数据的抽象 高级语言中提供整型、实型、字符、记录、文件、指针等多种数据类型，可以利用这些类型构造出象栈、队列、树、图等复杂的抽象数据类型。 ２）抽象数据类型(Abstract Data Type) 抽象数据类型（简称 ADT）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。 抽象数据类型是近年来计算机科学中提出的最重要的概念之一，它集中体现了程序设计中一些最基本的原则：分解、抽象和信息隐藏。 一个抽象数据类型确定了一个模型，但将模型的实现细节隐藏起来；它定义了一组运算，但将...
