数据结构概论 PPT课件.ppt

数 据 结 构 * 数据结构课程的地位 ——针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。 ——是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。 关系 对象 关系 操作 数学 软件 硬件 对象 关系 操作 Data_Structure=（D, R） * 第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第9章 查找 第10章 排序 目 录 * 第1章　绪　论 讨论5个问题： 1.1 什么是数据结构 1.2 学习数据结构的意义 1.3 数据结构涵盖的主要内容 1.4 什么是抽象数据类型 1.5 算法效率的度量 * 1.1 什么是数据结构 是相互之间存在一种或多种特定关系的数据元素的集合，表示为： （数值或非数值） Data_Structure=（D, R） ——是指同一数据元素类型中各元素之间存在的关系 元素有限集 关系有限集 * 数据(data)——所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息 ）。 数据元素(data element)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。 数据项(Data item)——构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性 等）。 三者之间的关系：数据 数据元素 数据项 例：班级通讯录 个人记录 姓名、年龄…… 数据、数据元素和数据项 术语简介： * 数据结构这门学科主要完成以下工作： （1）数据集合中各数据元素之间的逻辑关系，即数据的逻辑结构； （2）在对数据集合进行访问和处理时，各数据元素在计算机物理介质中的实际存储，即数据的物理结构； （3）对数据集合中各数据元素的各种运算。 * 计算机解决问题的流程 （1）分析问题，建立数学模型。界定问题的输入、输出的边界，抽取问题的实质，忽略其细节，对问题进行抽象，形成相应的数学模型。 （2）确定数据结构。一旦对问题进行抽象后，就要设计合适的数据结构对解决问题所需的数据及数据之间的关系进行存储，描述出其相应的逻辑结构及存储结构。 （3）算法设计。解决问题的算法通常有很多种，一般要根据问题的要求和数据结构具有的特点来选择和设计算法，同时要考虑该算法在执行效率和占用内存空间上是否具优越性。 （4）编程实现。选用适当的计算机设计语言编写相应的程序，必要时设计相应的输入、输出界面，然后调试并运行这个程序，得出问题的解。 * 1.1 什么是数据结构 例1： 新生入学注册问题。 （1）学号的编码规则。新生入学时因管理的方便需填写姓名、出生年月、籍贯等信息，同时为了识别每位新生的身份需要为其分配一个学号，为此，不同的学校有不同的方案： ① 最简单的方法是按报名的顺序号来分配学号，其特点是方案简便，但不利于管理，每个学生的身份无法识别； ② 其次是采用入学年份+报名流水号的编码方式。这比上一种方案有所改善，但无法体现学生的专业等详细信息。 ③ 采用入学年份+学院编号+专业编号+流水号的编码方式。这种方案既可以体现学生的入学年份、专业等信息，也便于教务管理、学生管理等部门的管理。 * 1.1 什么是数据结构 学号 姓名 学院编号 专业编号 性别 出生年月 200805165001 赵飞霞 05 165 女 1988.5 200805165002 朱晨 05 165 男 1989.1 200805165003 孙磊 05 165 男 1988.2 … … … … … … 200805178023 华明 05 178 男 1989.5 … … … … … … 学院编号 学院名称 01 机械学院 02 自动化学院 … … 05 管理学院 专业编号 专业名称 165 信息管理 166 财务管理 … … 178 电子商务 * 1.1 什么是数据结构 例1： 新生入学注册问题。 （2）确定数据结构。接下来设计适当的数据格式来存储和表达这些信息，这里不仅存储结点信息，也要存储结点之间的连接信息，必要时可能要增加一些辅助性的数据结构。 学校 学院1 学院2 学院n 专业1 专业m … … … … … … 班级1 班级s …… 学生1 学生t …… … … … … … … … … 树形数据结构示例 * 1.1 什么是数据结构 例1： 新生入学注册问题。 （3）算法设计。对于上述问题，主要涉及学生信息的增加、删除、修改、查询等操作。这里涉及到树数据结构的初始化、创建、增加、删除等算法。关于树这种数据结构的相关算法，第6章将有详细介绍。