Ch_1简介.ppt

算法与数据结构;课时安排： 上课——52学时 上机——12学时;主要内容;数据结构 计算机类专业的核心课程之一 数据结构在计算机专业中是一门综合性的专业基础课。 计算机专业国家统考课程，45/150 ;c语言(或其他语言基础) 离散数学;编译原理 数据库系统 操作系统 软件工程 .net J2EE程序设计等 ……;1. 多读:读透课本,熟练掌握基本概念;教学资料;对学生的要求;第一章 绪论;主要内容;第一章 绪论;数据结构讨论的范畴;例1 书目检索系统自动化问题;例2 人机对弈问题;例3 制定教学计划 ; 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作(包括对数据进行查找,插入,删除,合并,排序,统计以及简单计算)等的学科.; 数据（data)—对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称.如整数，实数，字符串，图像，声音等。 数据元素（data element）—数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。是数据结构中讨论的基本单位 数据项（data item）—数据的不可分割的最小单位.一个数据元素可由若干个数据项组成。如一本书的书目信息为一个数据元素，书目信息中的每一项（如书名，作者名）为一个数据项。 数据对象是性质相同的数据元素的集合，是数据的一个子集。如整数数据对象是集合N ={ 0, ±1, ±2, … }，字母字符数据对象是集合C={‘A’,’B’,’C’,……，’Z’}。 数据结构（data structure)—是相互之间存在一种或多种特定关系的数据元素的集合。数据元素相互之间的关系称为结构。带结构的数据元素的集合。;数据结构概念的解释：;在2行3列的二维数组{a1, a2, a3, a4, a5, a6} 中六个元素之间 存在两个关系:;在一维数组 {a1, a2, a3, a4, a5, a6} 的数据元素之间存在如下的次序关系:;数据的逻辑结构可归结为以下四类:;数据结构的形式定义为:;例4 复数定义：复数是一种数据结构 Complex=(C, R) 其中：C是含两个实数的集合{c1,c2}；R={P}，而P是定义在集合C上的一种关系 { c1,c2},c1是复数的实部，c2是复数的虚部;例5 为课题小组设计一个数据结构。假设每个小组由1位教师、1-3名研究生及1-6名本科生组成，小组成员之间的关系是：教师指导研究生，而由每位研究生指导一至两名本科生。;数据的存储结构 ;数据元素的映象方法：; 数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像。得到两种不同的存储结构：顺序存储结构和链式存储结构。 顺序映像的特点:是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 非顺序映像的特点:是借助指示元素存储地址的指针来表示数据元素之间的逻辑关系。;元素n;复数存储结构示意图;1536;Z1=3.0-2.3i Z2= - 0.7+4.8i;数据的逻辑结构与存储结构密切相关 算法设计取决于 逻辑结构 算法实现依赖于 存储结构;在不同的编程环境中，存储结构可有不同的描述方法。;;数据类型;例如，C 语言中提供的基本数据类型有:; 数据类型 是一个 值的集合 和定义在此集合上的 一组操作 的总称。;1.3 抽象数据类型 (Abstract Data Type 简称ADT); 抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要数学特性不变，都不影响其外部的使用。 ;抽象数据类型的描述方法;ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名;赋值参数 只为操作提供输入值。 引用参数 以打头，除可提供输入值外， 还将返回操作结果。;例如，抽象数据类型复数的定义：;基本操作：; GetImag( Z, ImagPart ) 初始条件：复数已存在。 操作结果：用ImagPart返回复数Z的虚部值。;抽象数据类型的表示和实现;typedef struct { float realpart； float imagpart； }complex；;float GetReal( cpmplex Z )； // 返回复数 Z 的实部值;// -----基本操作的实现;1.4 算法和算法分析;1．有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即： 算法中的每个步骤都能在有限时间内完成。;3．可行性 算法中的所有