数据结构课件

《数据结构课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第一章　绪论第二章　线性表第三章　数组和广义表第四章　栈和队列第五章　串第六章　树第七章　图第八章　查找第九章　排序第一章　绪论本章学习要求：了解数据结构的研究内容。理解掌握数据结构的基本概念和术语。了解数据元素间的结构关系。理解掌握算法及算法的描述1.1数据结构的发展1.1.1数据结构的发展简史最早对这一发展作出杰出贡献的是D.E.Kunth教授和C.A.R.Hoare(霍尔)。D.E.Kunth的《计算机程序设计技巧》和霍尔的《数据结构札记》对数据结构这门学科的发展作出了重要贡献。随着计算机科学的飞速发展，到20世纪80年代初期，数据结构的基础研究日臻成熟，已经成为一门完整的学科

2、。1.1.2数据结构的研究内容用计算机解决一个具体的问题时，大致需要经过以下几个步聚：（1）分析问题，确定数据模型。（2）设计相应的算法。（3）编写程序，运行并调试程序直至得到正确的结果。[例1.1]学生成绩表学号姓名高数数据结构8201001李红89908201002杜刚9587…………82010040刘珊8786一个数据元素数据项[例1.2]组织示意图学院教务处学生处总务处图书馆电教中心团委财务科后勤中心[例1.3]七桥问题Euler在1736年访问俄罗斯的哥尼斯堡时，他发现当地的居民正从事一项非常有趣的消遣活动。哥尼斯堡城中有一条名叫勒格尔的河流横经其中，在河上建有七座桥如图所示：AD

3、BC这项有趣的消遣活动是在星期六作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点。设四块陆地分别为A、B、C、D，Euler把每一块陆地考虑成一个点，连接两块陆地的桥以线表示，便得到如下的图形：后来推论出此种走法是不可能的。他的论点是这样的，除了起点以外，每一次当一个人由一座桥进入一块陆地（或点）时，他（或她）同时也由另一座桥离开此点。即每个点如果有进去的边就必须有出来的边，因此每一个陆地与其他陆地连接的桥数必为偶数。七桥所成的图形中，没有一点含有偶数条数，因此上述的任务是不可能实现的。1.2数据结构的基本概念和术语数据（data）：是指在计算机科学中能够被计算机输

4、入、存储、处理和输出的一切信息，是计算机处理的信息的某种特定的符号表示形式。包括数字、英文、汉字、以及表示图形、声音、光和电的符号等。数据项(DataItem)：是数据的最小单位，有时也称为域（field），即数据表中的字段。数据项是具有独立含义的不可分割的最小标识单位。1.2数据结构的基本概念和术语数据元素(DataElement)：是数据的基本单位，在计算机信息处理中通常作为一个整体来考虑。一个数据元素可以由若干个数据项组成，数据元素也称为元素、结点、顶点、记录。数据对象(DataObject)：具有性质相同的数据元素的集合，是数据的一个子集。如整数数据对象是集合N={0,±1,±2,…

5、}。1.2数据结构的基本概念和术语数据类型：是一个值的集合和定义在这个值集合上的一组操作的总称。数据类型中定义了两个集合：值的集合和操作集合。其中值的集合定义了该类型数据元素的取值，操作集合定义了该类型数据允许参加的运算，例如C语言中的int类型，取值范围是[-32768～32767]，主要的运算为加、减、乘、除、取模、乘方等。数据结构(DataStructure)：带结构的数据元素的集合，描述了一组数据元素及元素间的相互关系。数据元素间的关系包括三个方面：数据的逻辑结构、存储结构和操作集合。1.2数据结构的基本概念和术语数据类型：是一个值的集合和定义在这个值集合上的一组操作的总称。数据类型

6、中定义了两个集合：值的集合和操作集合。其中值的集合定义了该类型数据元素的取值，操作集合定义了该类型数据允许参加的运算，例如C语言中的int类型，取值范围是[-32768～32767]，主要的运算为加、减、乘、除、取模、乘方等。数据结构(DataStructure)：带结构的数据元素的集合，描述了一组数据元素及元素间的相互关系。数据元素间的关系包括三个方面：数据的逻辑结构、存储结构和操作集合。1.3数据的逻辑结构逻辑结构（logicalstructure）：是指数据元素之间的逻辑关系，是用户使用需要建立起来的数据组织形式，是独立于计算机的。根据数据元素之间的不同关系，有以下四种基本逻辑结构：（

7、1）线性结构：结构中的数据元素之间是一对一的关系。在线性结构中，有且仅有一个开始结点和一个终端结点，除了开始结点和终端结点，其余结点都有且仅有一个直接前趋和一个直接后继。1.3数据的逻辑结构（2）树状结构或层次结构：数据元素之间存在着一对多的关系。比如部门之间的隶属关系、人类社会的父子关系、上下级关系等。在树形结构中，除根结点之外，每个结点都有唯一直接前趋，所有的结点都可以有0个或多个直接后继。1.3数据的逻