第1章绪论第1节讲述.pptVIP

* * * * * * （2）线性结构 节点之间关系：一对一。 特点：开始节点和终端节点都是唯一的,除了开始节点和终端节点以外,其余节点都有且仅有一个前趋节点,有且仅有一个后继节点。线性表就是典型的线性结构。 … （3）树形结构 节点之间关系：一对多。 特点：开始节点唯一，终端节点不唯一。除终端节点以外，每个节点有一个或多个后续节点；除开始节点外，每个节点有且仅有一个前趋节点。 【例1.6：p4】有一种数据结构B4=（D,R），其中 　　D={48,25,64,57,82,36,75} 　　R={r1,r2} 　　r1={25,36,36,48,48,57,57,64,64,75,75,82} 　　r2={48,25,48,64,64,57,64,82,25,36,82,75} 画出其逻辑结构表示。 48 25 36 64 57 82 75 r2关系表示 r1关系表示 （4）图形结构 节点之间关系：多对多。 特点：没有开始节点和终端节点，所有节点都可能有多个前趋节点和多个后继节点。 1.1.3 存储结构类型 （2）链式存储方法 （3）索引存储方法 （4） 散列（哈希）存储方法 （1）顺序存储方法 前面通过示例已介绍 第9章介绍 （1）数据类型 高级程序语言中，一般须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。 1.1.4 数据结构和数据类型 数据类型是一个值的集合和定义在此集合上的一组操作的总称。 说明：数据类型就是已经实现了的数据结构。 如C/C++中的int就是整型数据类型。它是所有整数的集合（在16位计算机中为－32768~32767的全体整数）和相关的整数运算（如＋、－、＊、／等）。 int i=2,j=5,k; k=i+j; ... 因为i、j和k都属于int，而int提供了各种运算，所以可以进行相应运算。 int i=9999999999; i**; × （2）抽象数据类型 抽象数据类型（Abstract Data Type简写为ADT）指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算，而不考虑计算机的具体存储结构和运算的具体实现算法。 抽象数据类型=逻辑结构＋抽象运算 　 抽象数据类型实质上就是描述一个求解问题本身（与计算机无关），计算机人员就是在理解问题基础上实现用计算机求解问题的过程。 ADT Complex { 数据对象： D={e1,e2 | e1,e2均为实数} 数据关系： R={e1,e2 | e1是复数的实数部分，e2 是复数的 虚数部分 } 复数形式：e1+e2i或（e1，e2） 例如，复数抽象数据类型的定义： 基本操作： AssignComplex(z,v1,v2)：构造复数Z。 DestroyComplex(z)：复数z被销毁。 GetReal(z,real)：返回复数z的实部值。 GetImag(z,Imag)：返回复数z的虚部值。 Add(z1,z2,sum)：返回两个复数z1、z2的和。 } ADT Complex 运算功能描述 思考题： 　　数据类型和抽象数据类型有什么不同？ ━━本节完━━ * * * * * * * * * * * * * * * * * * * * 数 据 结 构 教材： [1] 数据结构教程（第4版），李春葆等，清华大学出版社 2013 [2] 数据结构教程（第4版）学习指导，李春葆等，清华大学出版社 2013 [3] 数据结构教程（第4版）上机实验指导，李春葆等，清华大学出版社 2013 十二五普通高等教育本科国家级规划教材 前期课程 数据结构 计算机基础 C语言 离散数学 后期课程 操作系统 编译原理 数据库原理 软件工程 … 承上启下 计算机科学课程体系（偏软） 1.1 什么是数据结构 关联的知识点 数据结构的概念 数据逻辑结构类型和存储结构类型 数据结构和数据类型的关系 抽象数据类型的作用和描述方法 第1章 绪论 数据：是所有能被输入到计算机中,且能被计算机处理的符号的集合。它是计算机操作的对象的总称,也是计算机处理的信息的某种特定的符号表示形式。 数据元素：是数据(集合)中的一个“个体”,是数据的基本单位。 数据对象：是具有相同性质的若干个数据元素的集合,如整数数据对象是所有整数的集合。 1.1.1 数据结构的定义 通过数据项进行描述数据元素。 默认情况下，数据结构中讨论的数据都是数据对象。 　例