辛运帏全套配套课件数据结构与算法 DSChapter01.ppt

《辛运帏全套配套课件数据结构与算法 DSChapter01.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章绪论1.1数据结构简介1.2有关的预备知识1.1.1数据结构的发展历史20世纪40年代只能直接对二进制数进行计算，这种数据根本谈不上什么结构，有结构也是非常简单的。20世纪50年代各种高级程序设计语言纷纷出现，所能描述的数据类型也逐渐增多。在FORTRAN、BASIC等语言中，都允许使用数组，其中最简单的是一维数组，这已经是一种典型的数据结构了。20世纪60年代美国计算机界出现了信息结构这一名称，后来改用数据结构。1968年，由美国计算机协会（ACM）颁发了建议性的计算机教学计划，计划中规定数据结构作为独立的一门课程。同年，世

2、界著名的计算机科学家、美国的D.E.Knuth教授的巨著《计算机程序设计艺术》第一卷《基本算法》出版。20世纪60年代末到70年代初结构程序设计成为程序设计方法学的主要内容，人们对数据结构越来越重视，著名的计算机科学家N.Wirth写了《算法+数据结构=程序》。20世纪80年代以后抽象数据类型概念的引入，将数据类型和与之相结合的操作合为一体，而将操作的具体实现和它的定义分离开来，将数据结构的理论和实践提高到一个新的水平。1.1.2数据结构的基本概念和术语数据能输入到计算机中并能被计算机处理的一切对象。这里必须强调指出，所谓数据绝不能

3、仅仅理解为整数或实数这种狭义的“数”，必须作广义的理解。例如，一个用某种程序设计语言编写的源程序、一篇文稿、一张地图、一幅照片、一首歌曲等等，都可以视为“数据”。今后随着计算机的发展，还将不断扩大数据的范围。数据元素数据的基本单位。由于数据的范围非常广泛，因此其基本单位也是可大可小的。大到可以是一个国家的地图、一本书、一部电影，小到可以是一个字符，甚至是计算机中的一位。对于较大的单位，还可以由称为“数据项”的较小单位组成。如图书馆中一本书的卡片就可以包含书名、作者名、出版社名、书号和出版日期等数据项。数据对象具有相同性质的数据元素的

4、集合，是数据的一个子集。因为在实际应用中不会同时处理一切类型的数据，总是对特定的问题处理一种或几种对象。例如用计算机求素数这个问题只涉及“整数”这种数据对象。数据结构彼此具有一定关系的数据元素的集合。事实上，这些关系反映了客观世界事物之间的联系。一般来说，数据有四类基本结构：集合线性结构树型结构图状结构或网状结构四类基本结构中数据元素之间的关系。集合线性结构树形结构图结构图1.1四类基本结构示意图抽象数据类型（AbstractDataType，简称ADT）抽象数据类型是指指一个数学模型和定义在该模型上的一组操作。栈的抽象数据类型描述

5、定义：元素类型为T的栈，由T的有限序列组成，对栈可以进行以下的操作：1)创建一个空栈；2)测试栈是否为空；3)压栈操作，即当栈不满时将一个新元素加入到栈顶部；4)出栈操作，即当栈不空时删除栈顶元素；5)取栈顶元素，即当栈不空时输出栈顶元素；1.2.1集合集合是数学中最基本的概念之一，所以对它无法下一个严格的数学定义，正如几何中无法定义点、直线一样。因此，我们只能对集合作描述性的说明。集合：一群无重复的对象的全体；元素：集合中的对象称为集合的元素；常用的表示方法列举法(穷举法)在描述元素个数较少的集合时，将集合中元素全部列出并括在一对

6、花括号之内的方法。例如S={a,b,c,d}，表示集合S由a、b、c、d四个元素组成。集合描述法对于元素个数较多的集合或由无穷多个元素组成的集合，可以用集合描述模式{x

7、P(x)}来指定，其中x表示该集合中的任一元素，P(x)是一个谓词，它对x进行限定。有关术语和记号属于如果x是集合S中的一个元素，则称x属于S，记作x∈S；否则，称x不属于S，记作xS。包含对于两个集合A、B，若集合A的元素都是集合B的元素，则称集合A包含于集合B中（或称集合B包含集合A），记作AB或BA，并且称A是B的子集。两个集合A和B相等，当且仅当AB且BA

8、。集合的并集合A和B的并是由A的所有元素和B的所有元素合并在一起组成的集合，记作A∪B，即A∪B={x

9、x∈A或x∈B}。集合的交集合A和B的交是由A和B的所有公共元素组成的集合，记作A∩B，即A∩B={x

10、x∈A且x∈B}。集合上的关系集合A上的关系R是A中元素的某些有序对偶的集合。如果(x,y)R，可记为xRy。例如，A是一切整数组成的集合，R={(x,y)

11、x,y∈A且x

12、都有aRa，则称R是自反的关系。（2）如果对A中的任何元素a，b，从aRb能推出bRa，则称R是对称的关系。（3）如果对A中的任何元素a，b，c，从aRb和bRc能推出aRc，则称R是传递的关系。若关系R同时是自反的、对称的和传递的，