ch1 绪论【荐】.ppt

第一章 绪论 1.1 什么是数据结构 1.2 基本概念和术语 （重点） 1.3 抽象数据类型的表示与实现（难点） 1.4 算法和算法分析 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 （重点、难点） 1.4.4 算法的存储空间需求 数据结构的非形式定义 数值计算问题的求解 特征：基于代数运算的计算问题，例如，矩阵运算、方程组的求解和数字信号处理，等等。 举例 百鸡百钱问题。公元前五世纪末，我国数学家张丘建在《算经》中提出了该问题。问题是这样的:“鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。凡百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？” 分析并建立数学模型：设鸡翁的个数为：cock只，鸡母的个数为：hen只, 鸡雏的个数为：chick只。依题意得到下列方程组： cock+hen+chick=100 5cock+3hen+chick/3=100 这就是描述该问题的数学模型。它是一个不定方程组，其解即为问题的解。 算法设计 基本思想：用穷举方法求解不定方程，即先穷举满足百鸡条件的鸡翁、鸡母、鸡雏的数目，然后再从这些数目中挑选出满足百钱条件的鸡翁、鸡母、鸡雏的数目。 算法如下： 循环：cock从0到19，步长为1，做 循环：hen从0到33，步长为1，做 [ chick←100-cock-hen; 若5×cock+3×hen+chick/3=100，则 输出 cock,hen,chick的值（得到一个解）; ] 编码：略。 上机调试程序 利用计算机解题的过程 首先经过分析问题，从中抽象出一个适当的数学模型，然后设计或选择一个解此数学模型的算法，最后编出程序进行调试、测试，直至得到最终的解答。解决问题的关键在于数学模型的建立和算法的设计。 非数值计算问题 例1 书目自动检索系统 非数值计算问题 例2 人机对奕问题 例3 多叉路口交通灯管理问题 求解非数值计算的问题： 主要考虑的是设计出合适的数据结构及相应的算法。 首先要考虑对相关的各种信息如何表示、组织和存储？ 因此，可以认为： 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。 数据结构是指带运算的具有一定逻辑关系的数据构成的集合。 数据结构课程的形成和发展： 形成阶段： 60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。 发展阶段： 数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。 70年代后期，我国高校陆续开设该课程。 《数据结构课程》所处的地位 Niklaus Wirth（尼克劳斯·沃思，1934－）男，瑞士人，1963年获得加州大学伯克利分校哲学博士，苏黎士联邦高等工业学校教授。他是Pascal语言之父及结构化程序设计的首创者，提出了著名的“数据结构+算法=程序”公式。因开发了EULER、ALGOL-W、 MODULA和PASCAL一系列崭新的程序设计语言而获得1984年图灵奖。 1.2 基本概念和术语（重点） 数据（data)—所有能输入到计算机中去的描述客观事物的符号 整数的子集是数据 中文文字组成的任何形式的信息是数据 图像、声音和视频是数据 甲骨文不是数据 某些少数民族文字不是数据 数据元素（data element）—数据的基本单位，也称节点（node）或记录（record） 数据项（data item）—有独立含义的数据最小单位，也称域(field) 数据对象（data object）—性质相同的数据元素的集合，是数据的一个子集。 本课程授课内容的体系组织与主线 授课内容的体系组织 利用抽象数据类型组织数据结构的内容，与现代程序理论与技术的发展形成了一致。 主线 以每一种“ADT的定义→ADT的实现→ADT的应用”为主线展开。 数据类型—高级语言中指数据的取值范围及其上可进行的操作的总称 抽象数据类型（abstract data type） 指数学模型以及定义在该模型上的一组操作. 抽象数据类型和数据类型实质上是一个概念。 抽象数据类型的三元组表示 ADT=(D,S,P) 其中: D：数据对象 S：D上的