第02章基本数据结构及其运算-01资料.ppt

第02章 基本数据结构及其运算 研究的内容： 1、数据集合各数据间的逻辑结构 2、数据集合各数据间的物理结构 3、数据结构的运算 2.1 数据结构的基本概念 一、两个例子 1、有序表和无序表的查找 2、学生成绩表 学生成绩表格 选课单 二、什么是数据结构 在应用程序中涉及到各种各样的数据，如何在计算机中组织、存储、传递数据，需要讨论它们的归类及它们之间的关系，从而建立相应的数据结构，依此实现软件功能。 综上，描述这类非数值计算问题的数学模型不是数学方程,而是树、表和图之类的数据结构。 因此从广义上讲，数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现. 基本概念和术语 数据(Data) 是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。 数值性数据 非数值性数据 数据元素（Data Element） 数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。 有时一个数据元素可以由若干数据项(Data Item)组成。数据项是具有独立含义的最小标识单位。 数据元素又称为元素、结点、记录 数据项(Data Item) ? 数据对象 (data object) 具有相同性质的数据元素的集合。 整数数据对象 N = { 0, ?1, ?2, … } 字母字符数据对象 C={ ‘A’, ‘B’, ‘C’, … ‘F’ } 数据结构（Data Structure） 形式定义： 某一数据对象的所有数据成员之间的关系。记为： Data_Structure = {D, S} 其中，D 是某一数据对象， S 是该对象中所有数据成员之间的关系的有限集合。 四个基本结构 集合 线性结构 树形结构 网状结构 1、数据的逻辑结构 从逻辑关系上描述数据，与数据的存储无关； 从具体问题抽象出来的数据模型； 与数据元素本身的形式、内容无关； 与数据元素的相对位置无关。 数据的逻辑结构分类 线性结构 线性表 非线性结构 树 图（或网络） 堆结构 2、数据的存储结构（物理结构） 数据结构在计算机中的表示。 数据的存储结构依赖于计算机语言。 顺序存储表示 链接存储表示 索引存储表示 散列存储表示 * 78 87 2001,2 2000,9 DS2000 SX2000 20001 89 76 2000,9 2002,2 SX2000 ART2000 20004 87 78 2000,9 2001,2 SX2000 DS2000 20003 68 90 2002,2 2001,2 ART2000 DS2000 20002 成绩 时间 课程号 学号 职 位 业 绩 入队日期 出生日期 年 月 日 俱乐部名称 姓 名 bin dev etc lib user 2 1 14 13 12 11 2 3 4 6 7 8 9 10 3 1 5 8 7 10 11 9 9 8 7 4 5 6 6 2 3 13 1 5 5 线性结构 树形结构 树 二叉树 二叉排序树 12 3 5 4 8 7 11 10 2 9 1 6 1 2 5 6 4 3 1 2 5 4 3 6 11 33 18 14 6 6 5 19 21 图结构 网络结构 *