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年代后期，我国高校陆续开设该课程。《数据结构课程》所处的地位为什么要学习数据结构
1、什么是程序、软件？
程序=算法+数据结构N.沃思（NiklausWirth)
算法是程序的骨架，而数据结构是程序的血脉；
数据结构是研究非数值数据的数学建模和数据表示的；
软件=程序+文档（软件工程的观点）2.电子计算机的主要用途
(1)数值计算早期
求解梁架结构中的应力问题线性方程
人口增长情况预报微分方程…
(2)非数值计算后来1.2基本概念和术语（重点）

数据（data)—所有能输入到计算机中去的描述客观事物的符号

整数的子集是数据
中文文字组成的任何形式的信息是数据
图像、声音和视频是数据
甲骨文不是数据
某些少数民族文字不是数据数据元素（dataelement）—数据的基本单位，也称节点（node）或记录（record）
数据项（dataitem）—有独立含义的数据最小单位，也称域(field)
数据对象（dataobject）—性质相同的数据元素的集合，是数据的一个子集。
客观世界中的数据都不是孤立存在的，换句话说数据之间是有联系的。人们应用计算机处理各种各样的数据，必然要涉及到数据之间的联系。
数据结构（datastructure)—指相互之间存在一种或多种特定关系的数据元素的集合。
教师手中的学生花名册是数据结构
列车时刻表是数据结构
某大学全体师生是数据结构
某城市公共交通地理图是数据结构数据结构的形式定义
数据结构是一个二元组：
Data-Structure=(D，S)
其中：
D是数据元素的有限集，S是D上关系的有限集。根据数据元素间关系的基本特性，有四种基本数据结构
（集合）——数据元素间除“同属于一个集合”外，无其它关系
线性结构——一个对一个，如线性表、栈、队列
树形结构——一个对多个，如树
图状结构——多个对多个，如图数据的逻辑结构与存储结构密切相关
算法设计 逻辑结构
算法实现 存储结构 元素n1536本课程授课内容的体系组织与主线数据类型—高级语言中指数据的取值范围及其上可进行的操作的总称抽象数据类型（abstractdatatype）
指数学模型以及定义在该模型上的一组操作.
抽象数据类型和数据类型实质上是一个概念。

抽象数据类型的三元组表示
ADT=(D