北京信息科技大学数据机构课件第1章 绪论_200909课件.pptVIP

数据结构;主教材严蔚敏.《数据结构》.清华大学出版社.1997 辅导及实验教材严蔚敏.《数据结构题集（C语言版）》清华版，1999 参考教材1.王红梅.《数据结构（C＋＋版）》.清华大学出版社，20052.许卓群等.《数据结构与算法》高等教育出版社3.李春葆.数据结构习题与解析（A级）清华大学出版社，2006;课程性质;学习目标;学习要求;学习手段;成绩组成;;;1.1 数据结构的兴起和发展 ;用计算机解决实际问题的步骤：;1938年出生，25岁毕业于加州理工学院数学系，博士毕业后留校任教，28岁任副教授。30岁时，加盟斯坦福大学计算机系，任教授。从31岁起，开始出版他的历史性经典巨著： The Art of Computer Programming 他计划共写7卷，然而出版三卷之后，已震惊世界，使他获得计算机科学界的最高荣誉图灵奖，此时，他年仅36岁。;1.1 数据结构的兴起和发展 ; 数据结构随着程序设计的发展而发展;;1.2 数据结构的研究对象;例1 学籍管理问题——表结构;例2 人机对弈问题——树结构;例3 教学计划编排问题——图结构;1.2 数据结构的研究对象;1.2 数据结构的研究对象;1.3 数据结构基本概念;1.3 数据结构的基本概念; 数据项：;数据、数据元素、数据项之间的关系;数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。 逻辑结构：指数据元素之间逻辑关系的整体。;数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。 逻辑结构：指数据元素之间逻辑关系的整体。 存储结构：又称为物理结构，是数据及其逻辑结构在计算机中的表示。;假设用三个 4 位的十进制数表示一个含 12 位数的十进制数。例如: 3214,6587,9345 ─ a1(3214),a2(6587),a3(9345) 则在数据元素 a1、a2 和 a3 之间存在着“次序”关系 ?a1,a2?、?a2,a3? ;再例如，在2行3列的二维数组{a1, a2, a3, a4, a5, a6} 中六个元素之间 存在两个关系:;数据结构从逻辑上分为四类： ⑴ 集合：数据元素之间就是 “属于同一个集合” ；;数据结构从逻辑上分为四类： ⑴ 集合：数据元素之间就是 “属于同一个集合” ； ⑵ 线性结构：数据元素之间 存在着一对一的线性关系；;数据结构从逻辑上分为四类： ⑴ 集合：数据元素之间就是 “属于同一个集合” ； ⑵ 线性结构：数据元素之间 存在着一对一的线性关系； ⑶ 树结构：数据元素之间存在 着一对多的层次关系；;数据结构从逻辑上分为四类： ⑴ 集合：数据元素之间就是 “属于同一个集合” ； ⑵ 线性结构：数据元素之间 存在着一对一的线性关系； ⑶ 树结构：数据元素之间存在 着一对多的层次关系； ⑷ 图结构：数据元素之间存在 着多对多的任意关系。;数据结构的形式定义为:;通常有两种存储结构： 1. 顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。;通常有两种存储结构： 1. 顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。 2. 链接存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示 。;逻辑结构和存储结构之间的关系;二、数据类型;三、抽象数据类型 (Abstract Data Type 简称ADT);三、抽象数据类型 (Abstract Data Type 简称ADT);ADT 有两个重要特征:;抽象数据类型的描述方法;例如，抽象数据类型复数的定义：;抽象数据类型的表示和实现;1.3 数据结构的基本概念（小结）;;一、算法的相关概念;3.算法设计的原则 （1）正确性 （2）可读性 （3）健壮性 （4）高效率与低存储量需求 4.算法的描述方法 （1）自然语言 （2）流程图 （3）程序设计语言 （4）伪代码; 欧几里德算法 ;算法的描述方法——自然语言 ;① 输入m 和n； ② 求m除以n的余数r； ③ 若r等于0，则n为最大公约数，算法结束；否则执行第④步； ④ 将n的值放在m中，将r的值放在n中； ⑤ 重新执行第②步。;优点：流程直观 缺点：缺少严密性、灵活性 使用方法：描述简单算法 注意事项：注意抽象层次 ;N;优点：能由计算机执行 缺点：抽象性差，对语言要求高 使用方法：算法需要验证 注意事项：将算法写成子函数 ;#include iostream.h int CommonFact