绪论 本讲内容 计算机如何计算世界(兼什么是数据结构)？ 基本概念 相关概念与术语 基本结构类型 逻辑结构与存储结构 抽象数据类型 定义（数据被抽象成抽象数据类型） 表示与实现 算法及算法分析初步 基本概念 算法评价 如何学数据结构 写在后面 计算机如何计算世界？ 一切都是数据(世界也是) 一些都可以计算(世界也是) 数据：客观事物的符号表示 所有能输入到计算机中并被计算机程序处理的符号的总称/集合 数值型/非数值型（一般指有结构的数据） 数值型可以直接进行四则等基本运算 非数值型并非是不可以用数字来表示，而是对其做数学运算没有实在意义 主要面向非数值型数据 graph LR 客观世界--> 逻辑抽象 逻辑抽象-->计算机世界 物-->数 数据元素(Data Element) 数据的基本单位，在程序中通常作为一个整体来进行考虑和处理 数据元素又称为元素、结点、记录 数据项(Data Item) 数据的不可分割的最小单位(原子) 对客观事物(数据元素)某一方面特性的数据描述 数据元素可由1或多个数据项构成 数据对象(Data Object)：性质相同的数据元素的集合 结构：数据(事物)组成部分的搭配和排列 关系：数据(事物)之间相互作用、相互联系的状态 数据结构定义 数据对象+关系 Data_Structure = ( D, S ) D — 数据对象,数据元素的有限集 S — 是D上关系的有限集 四种基本数据结构类型 集合结构 线性结构(一对一，相邻关系) 树(一对多，层次关系) 图(多对多，‘任意’关系) 请同学们举例抽象 逻辑结构 逻辑关系：实体/数据元素之间存在的自然（直观）关系，经过一定的抽象，得到的符合逻辑的关系。这种关系一般可由人为定义或者描述。 逻辑结构： 数据元素间存在的由上述逻辑关系定义的结构 前面四种基本结构类型均指逻辑结构 从逻辑关系上描述数据，与数据存在哪里无关 线性结构---线性表 非线性结构---树/图 存储结构/存储表示 数据(及逻辑结构)在计算机中的表示/实现 数据对象存储+关系存储 将存储空间想象成一个二维表格，则数据对象+关系有几种存储方式呢？ /*----> 思考 思考 思考 思考 《----/* 顺序存储：数据元素连续存储在物理位置相邻的存储单元 非顺序存储(链式)：数据元素分散(连续不是必要条件)存储在存储单元 前者逻辑关系用数据元素在存储器中的（相对）位置来表示 后者逻辑关系用指向另一个单元（如地址）的量（如c语言的指针）来表示 数据的存储结构是逻辑结构用计算机程序语言的实现 数据结构实现中，数据元素间的逻辑结构和物理结构密不可分 还须实现可对数据元素施加的各种操作。这些操作也被称为运算 抽象数据类型 数据类型(Data Type)：在高级程序语言，是性质相同的数据元素的集合及定义在该集合上的一组操作。 如C语言中的基本数据类型 数据结构更强调数据元素之间的关系 抽象数据类型(ADT,Abstract Data Type) 一个数学模型以及定义在该模型上的一组操作 数据结构+操作=（数据+关系）+操作 由实现者来定义 并尽量实现信息隐蔽和数据封装，使用与实现相分离 不同的数据结构，相同的操作--->不同ADT 相同的数据结构，不同的操作--->不同ADT 形式化：ADT=(D，S，P) ADT定义是逻辑上的定义，与具体实现无关 具体定义，参考教材P9 例1-6 ADT的表示与实现 教材利用类C语言伪码P10 用#define预定义常量与类型 数据结构表示用typedef，将数据元素统一命名为ElemType 注意其借用了C++的引用&，c语言中，基本上可以改为* P12例1-7 总结 后续部分用pdf/PPT