南京邮电大学计算机考研初试题《数据结构》DSB第1章-新.ppt

2 数据结构 * 课程的性质、目的和任务 《数据结构》课程从性质来讲是计算机软件专业的一门专业基础课。随着计算机技术在各领域应用的不断深入，必然改变非计算机专业(尤其是电子信息类专业)学生的知识结构，要求他们掌握软件技术知识，以结合本专业的需要从事软件的研究和开发。作为非计算机专业软件技术基础系列课程中的《数据结构》，其目的在于培养非计算机专业学生学会用面向对象方法描述各种数据结构，使用数据结构进行较为复杂的程序设计的能力。本课程介绍线性表、栈、队列、数组、树及二叉树、图、集合等等基本数据结构，包括它们的逻辑结构及其实现，介绍它们在实际中的应用；初步介绍算法的时间和空间分析方法。本课程将采用C++语言描述各种结构和算法。 引 言 数据结构的概念及其研究的问题，是本章中重要的概念，它们贯穿整本书。除了数据结构研究的三个方面，我们对每种数据结构都会给出应用的实例。 要学会描述数据结构和算法，分析算法的时、空复杂度。 第1章 基础知识 内容提要 1．给出数据结构的概念 2．介绍数据抽象和抽象数据类型 3．说明数据结构和算法描述的方法 4．介绍算法和算法分析的基本方法 1.1 算法和数据结构 课堂提要 第1章 基础知识 1.1 算法和数据结构 1.2 什么是数据结构 1.3 数据抽象和抽象 数据类型 1.4 描述数据结构和 算法 1.5 算法分析的基本 方法 数据结构和算法是计算机学科的基础之一，更是软件技术的基础。 数据的组织和表示方法直接影响使用计算机求解问题的效率。 算法设计通常建立在所处理数据的一定组织形式之上的，它们之间有着本质的联系。当讨论一种算法时，自然要涉及算法所处理的数据问题。 程序 =数据结构+算法 对大家来说，数据结构其实并不陌生。 比如：设计一个程序，能对全校的学生档案进行管理。 数据结构由数据元素组成，在数据结构上定义一组操作（运算）。 1. 数据：计算机加工处理的对象 2. 数值数据和非数值数据 (1)数值数据：包括整数、实数或复数。 主要用于工程与科学计算。 (2)非数值数据：包括字符、文字、图形、图象、 语音等。 用于情报检索、企业管理、图形图象、人工智能、远程教育、远程医疗、电子商务、电子图书馆和办公自动化等诸多领域。 回顾几个概念： 1.2 什么是数据结构 课堂提要 第1章 基础知识 1.1 算法和数据结构 1.2 什么是数据结构 1.3 数据抽象和抽象 数据类型 1.4 描述数据结构和 算法 1.5 算法分析的基本 方法 1.2.1 基本概念 数据是计算机加工处理的对象，一个数据可以是由成分数据组成的。 成分数据就是数据项，不可再分割。 数据元素：由成分数据组成的数据。 是组成数据的基本单位。 数据元素可以是简单类型的，也可以是结构类型的，如记录。 1. 数据结构举例 表1.1 学生情况表 … 男 女 女 女 性别 … 林悦 … 王小红 … … … … 张可可 … 陈菁 其他信息 姓名 学号 2. 什么是数据结构 数据结构是由数据元素依据某种逻辑联系组织 起来的。 它主要研究三个方面的内容： 逻辑结构：对数据元素间逻辑关系的描述称为 数据的逻辑结构。 存储结构：数据结构的实现形式，是数据结构 在计算机内的表示。 运算：在数据结构上执行的运算。 1.2.2 数据的逻辑结构 数据结构的逻辑结构可以用一个二元组表示。即 DS = （D， R） 其中， D是数据元素的有限集合，R是D中数据元素序偶的集合。 例如DS={D,R},D={a,b,c,d},R={a,b,b,c,c,d},其中，序偶a, b表示a和b之间的关系，我们称为a是b的直接前驱，b是a的直接后继。小圆圈代表数据元素，两个不同元素的序偶称为边。 a b c d 4种基本的逻辑结构 根据数据结构中数据元素之间关系的不同特征，可以划分为以下四种基本逻辑结构： (a)集合结构 (b)线性结构 (c)树形结构 (d)图结构 图1-2 四种基本的结构关系 线性结构：数据元素之间存在一对一的关系。一个前驱，一个后继。 树形结构：数据元素之间存在一对多的关系。 图结构：数据元素之间存在多对多的关系。每个结点的前驱和后继的数目都不同。 集合结构：结构中的数据元素之间除了“同属于一个