数据结构——C描述.ppt

数据结构DATA STRUCTURE —— C描述 为什么要学习数据结构? 从计算机软件技术的发展历史来看 数据库、操作系统、程序设计环境等 从人的思维方式来看 抽象思维 从计算机系的课程设置来看 基本概念和术语 学习数据结构的意义 算法描述和分析 “学生”表格 “课程”表格 选课单包含如下信息 学 号 课程编号 成 绩 时 间  学生选课系统中实体构成的网状关系 UNIX文件系统的系统结构图 数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别、存储和加工的符号的集合。 数值性数据 如整数、实数、双精度数等 非数值性数据 如字符串、多媒体信息等 数据元素：数据的基本单位（元素、结点、顶点、记录）。 可以有若干数据项组成（字段、域、属性，数据项是具有独立含义的最小标识单位） 什么是数据结构？ 数据结构包含以下三方面的内容 数据元素之间的逻辑关系（逻辑结构） 数据元素及其关系在计算机存储器内的表示（存储结构也称物理结构） 数据运算（对数据能施予的操作，全部合理的操作构成数据结构的运算集合） 逻辑结构面向问题，独立于计算机 物理结构面向计算机 数据运算定义在数据逻辑结构上 数据类型 数据类型 定义：一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称. C语言中的数据类型 char int float double void 字符型 整型 浮点型 双精度型 无值 抽象数据类型 (ADTs: Abstract Data Types) 由用户定义，用以表示应用问题的数据模型 由基本的数据类型组成, 并包括一组相关的服务（或称操作） 数据的逻辑结构及其在逻辑结构上定义的操作 独立于具体实现、将数据和操作封装和信息隐蔽。 自然数的抽象数据类型定义 ADT NaturalNumber is objects: 一个整数的有序子集合,它开始于0, 结束于机器能表示的最大整数(MaxInt)。 Function: 对于所有的 x, y ? NaturalNumber; False, True ? Boolean, +、-、、==、=等都是可用的服务。 Zero( ) : 返回自然数0 NaturalNumber IsZero(x) : if (x==0) 返回True Boolean else 返回False Add (x, y) : if (x+y=MaxInt)返回 x+y NaturalNumber else 返回MaxInt Subtract (x, y) : if (x y) 返回 0 NaturalNumber else 返回 x - y Equal (x, y) : if (x==y) 返回True Boolean else 返回 False Successor (x) : if (x==MaxInt) 返回 x NaturalNumber else 返回 x+1 end NaturalNumber 数据结构中数据元素之间的逻辑关系 直接前趋 任一结点A与它相邻且在它前面的结点B称B为A的直接前趋 直接后继 任一结点A与它相邻且在它后面的结点B称B为A的直接后继 数据的存储结构 主要是表达直接前趋和直接后继 1、顺序存储 结点的逻辑关系由结点存储的时的存储顺序的邻接关系来体现，即按存储位置的前后来体现。 2、链接存储 在结点内增加指针字段来体现。 3、索引存储 在存储结点信息的同时，还建立附加的索引表（稠密索引、稀疏索引） 4、散列存储 由结点的关键字直接计算出该结点的存储地址。 数据结构的抽象层次 线性聚类 直接存取类 数组、记录、文件 顺序存取类 栈、队列、表 广义索引类 散列表、词典 非线性聚类 层次聚集类 树，二叉树，堆 群聚集类 集合，图 数据结构的抽象层次 线性聚集类中各数据成员之间的线性关系 堆结