2010Chap1正式上课.ppt

例1 书目自动检索系统 当你想找某一方面的参考书时，需要到图书馆查阅图书目卡片。 利用计算机实现自动检索时，计算机处理的对象便是这些目录卡片上的书目信息。在书目检索系统中可以建立一张按登录号顺序排列的书目文件和三张分别按书名、作者名和分类号顺序排列的索引表。这四张表便是书目自动检索的数学模型。 例2 计算机和人对弈问题 在对奕问题中，计算机操作的对象是对奕过程中可能出现的棋盘状态——称为格局。每个格局可以派生出五个格局，每一个新的格局又可派生出四个可能出现的格局，格局之间的关系不是线性的。 例3 多叉路口交通灯的管理问题 设计一个多叉路口交通信号灯的管理系统，使车辆相互不碰撞，又能达到车辆的最大流通。 首先需要分析一下所有车辆的行驶路线的冲突问题。这个问题可以归结为对车辆的可能行驶方向作某种分组，对分组的要求是使任一个组中各个方向行驶的车辆可以同时安全行驶而不发生碰撞。 多叉路口交通灯管理问题 从数学模型上分： 数值问题（数学方程） 非数值问题 非数值计算中数据元素之间的相互关系一般无法用数学方程加以描述 数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。 1.2 数据结构的发展简史及其在计算机科学中所处的地位 发展史： 1、 “数据结构”作为一门独立的课程在国外是从1968年才开始设立的。 2、 1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。 地位： “数据结构”在计算机科学中是一门综合性的专业基础课。 数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。 数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。 如何描述存储结构呢？ 以内存地址来描述存储结构，实现很困难，借用高级程序语言中提供的“数据类型”来描述，“一维数组”类型描述顺序存储结构，“指针”来描述链式存储结构。 可把C语言看成是一个执行C指令和C数据类型的虚拟处理器，存储结构是数据结构在C虚拟处理器中的表示，称之为虚拟存储结构。 举例说明：抽象数据类型的定义、表示、实现 例1-6抽象数据类型三元组Triplet的定义 书P9 例1-7抽象数据类型Triplet的表示和实现 书P12 1.2 算法的描述和算法分析简介 一、算法的定义及特性： 算法（algorithm）—解决某一特定问题的具体步骤的描述，是指令的有限序列 算法特性— 元素n …….. 元素i …….. 元素2 元素1 Lo Lo+m Lo+(i-1)*m Lo+（n-1)*m 存储地址 存储内容 Loc(元素i)=Lo+（i-1)*m 顺序存储结构: 借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。 1536 元素2 1400 元素1 1346 元素3 ∧ 元素4 1345 1346 元素3 1536 ……. …….. ……. 1536 元素2 1400 ……. …….. ……. ∧ 元素4 1346 1400 元素1 1345 指针 存储内容 存储地址 链式存储结构: 借助指示元素存储地址的指针表示数据元素间的逻辑关系。 h 二、数据类型 数据类型 是一个 值的集合和定义在此集合上的 一组操作的总称。 例如：C语言中的整形变量，其值集为某个区间上的整数（区间大小依赖于不同的机器），定义在其上的操作为加、减、乘、除和取模等算术运算。 数据类型是和数据结构密切相关的一个概念。 计算机中数据类型概念广泛存在于处理器（广义处理器：包括计算机的硬件系统和软件系统）中： （1）计算机硬件系统数据类型：通常含有“位”、“字节”、“字”等原子类型，它们的操作通过计算机设计的一套指令系统直接由电路系统完成。 （2）高级程序语言中的数据类型：非结构的原子类型 如C语言中，提供int, char, float, double等基本数据类型，还有指针、空(void)类型。结构类型如C语言中数组、结构体、共用体、枚举等构造数据类型等。 高级程序语言提供的数据类型，其操作需通过编译器或解释器转化成低