第1章绪论陈海涛.ppt

计算机软件技术基础数据结构（C语言版）扬州大学;教材和参考书;;目 录;1　引言;1.1 引言 ; 因此，再把电子数字计算机简单地看作是进行数值计算的工具，把数据仅理解为纯数值性的信息，就显得太狭隘了。现代计算机科学的观点，是把计算机程序处理的一切数值的、非数值的信息，乃至程序统称为数据（Data），而电子计算机则是加工处理数据（信息）的工具。 由于数据的表示方法和组织形式直接关系到程序对数据的处理效率，而系统程序和许多应用程序的规模很大，结构相当复杂，处理对象又多为非数值性数据。因此，单凭程序设计人员的经验和技巧已难以设计出效率高、可靠性强的程序。于是，就要求人们对计算机程序加工的对象进行系统的研究，即研究数据的特性以及数据之间存在的关系——数据结构（Date Structure）。;1.2 数据结构的发展简史及其在计算机科学中所处的地位; 1968年，高德纳（Donald E. Knuth，“高德纳”是他在1977年起的中文名）在对计算机软件中的编译程序、属性文法和运算法则等进行深入研究的基础上，写作出版了经典的《计算机程序设计技巧》的第一卷，提出了算法及数据结构的概念。高德纳的《计算机程序设计技巧》出版，立刻成为计算机软件开发的经典之作，该书被翻译成几十种文字，在全世界广为流传。高德纳是计算机软件设计的重要奠基人。; ; ; ;地位： “数据结构”在计算机科学中是一门综合性的专业基础课。 数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。 数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。;1.3 什么是数据结构;例1 考生录取信息系统;考生录取信息系统;例2 人机对奕问题;例3 田径赛的时间安排问题： 设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。 ;（1）设用如下六个不同的代号代表不同的项目： 跳高 跳远 标枪 铅球 100米 200米 A B C D E F （2）用顶点代表比赛项目 不能同时进行比赛的项目之间连上一条边。 （3）某选手比赛的项目必定有边相连（不能同时比赛）。 ;姓名;计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（Algorithm），最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。 计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。 运算是由计算机来完成，这就要设计相应的插入、删除和修改的算法 。也就是说，数据结构还需要给出每种结构类型所定义的各种运算的算法。 直观定义：数据结构是一门研究非数值计算的程序设计问题中计算机操作的对象以及它们之间的关系和操作(运算)等的学科。;1.4 基本概念和术语 ;  表 1-1 个人书库;2．数据元素 数据元素，它是组成数据的基本单位。在程序中通常把数据元素作为一个整体进行考虑和处理。例如，在表1-1所示的个人书库中，为了便于处理，把其中的每一行（代表一本书）作为一个基本单位来考虑，故该数据由10个数据元素构成。 一般情况下，一个数据元素中含有若干个数据项（也叫字段）。例如，在表1-1所示的表格数据中，每个数据元素都有登录号、书号、书名、作者、出版社和价格等六个数据项构成。数据项是构成数据的最小单位。 3．数据对象 类型相同的一组数据元素组成的集合，是数据的一个子集。;4．数据结构 数据结构是指相互之间存在某种关系的数据元素的集合。数据结构包括3方面主要内容：逻辑结构、存储结构和对数据的运算。;例，设有数据逻辑结构为： D＝（D，R） D＝｛d1,d2,…,d9｝ R=｛r｝ r=｛d1,d3,d1,d8,d2,d3,d2,d4,d2,d5,d3,d9,d5,d6,d8,d9,d9,d7,d4,d7,d4,d6 ｝ 画出这个数据逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点，哪些是中间结点。 ;5．逻辑结构 数据元素和数据元素之间的逻辑关系称为数据的逻辑结构，它与数据的存储结构无关，同一逻辑结构可以对应多种