大学教程(零起点)数据结构--概论.ppt

数据结构 课程代码02331 3.课程重要性 1，学习计算机程序设计的基础科目 2，硕士研究生入学考试必考科目 4.教学内容 线性表：顺序表，链表，顺序栈，链栈 顺序队，链队，串 数组和广义表: 树：二叉树，线索二叉树，树和森林，哈夫曼树 图：存储，遍历，生成树，最短路径，拓扑排序 排序：插入排序，交换排序，选择排序，归并排序 查找：线性表查找，树形查找，散列技术 文件：顺序文件，索引文件，散列文件 5.考核方式 实践性考核（主考院校统考） 主考院校成绩50%，平时成绩50% 目录 第1章 概论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 多维数组和广义表 第6章 树 第7章 图 第8章 排序 第9章 查找 第10章 文件 第1章 概论 1.1基本概念和术语 1.2学习数据结构的意义 1.3算法的描述与分析 1.1基本概念和术语 数据结构主要研究： 1）计算机加工对象（数据）的逻辑结构 2）实现各种基本操作的算法。 数据表示、数据处理 基本术语 数据（Data)： 所有能被计算机处理的符号的集合。 信息的载体 能被计算机识别、存储、加工 基本术语 数据元素（Data Element）： 是数据这个集合中的一个个体。 数据结构的基本单位 又称为元素、结点、顶点、记录 由多个数据项组成 基本术语 数据项（Data Item）： 数据元素常常还可分为若干个数据项 数据项是数据具有意义的最小单位 又称为字段、域、属性 基本术语 数据结构（Data Structure）： 数据之间的相互关系 数据的组织形式 包含三个方面内容： 1 数据元素间的逻辑关系：逻辑结构 2 数据元素及其关系在存储器中的表示：存储结构 3 数据的运算、数据的加工 表1-1所示的学生信息。 数据特点： 每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格； 表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构； 对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。 基本术语 数据逻辑结构两大类： 线性结构： 仅有一个开始结点和一个终端结点 其余结点仅有一个直接前趋和一个直接后继 非线性结构 每个结点可有多个直接前趋和多个直接后继 基本术语 数据存储结构 四种基本存储方法： 顺序存储： 使用一段连续内存 借助数据元素的相对存储位置表示数据的逻辑结构 基本术语 数据存储结构 四种基本存储方法： 链式存储： 使用任意内存 借助数据元素地址的指针表示数据的逻辑结构 基本术语 数据存储结构 四种基本存储方法： 索引存储： 建立索引 借助索引表中的索引指示各存储节点的存储位置 基本术语 数据存储结构 四种基本存储方法： 散列存储： 利用散列函数 用散列函数指示各节点的存储位置 1.2 学习数据结构的意义 算法 + 数据结构 = 程序 应用举例1——学籍档案管理 学号姓名 李军 性别 男 出生年月 80.12 …… 学号姓名 单晓宏 性别 男 出生年月 81.3 应用举例2——制定教学计划 在制定教学计划时，需要考虑： 各门课程的开设顺序，即有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。 常用运算 加工型运算：其操作改变原逻辑结构的值 如：结点个数，结点内容等 引用型运算：其操作不改变原逻辑结构的值 查找 读取 插入 删除 更新 以上操作哪些是加工型操作，那些是引用型操作？ 1.3算法的描述与分析 算法 规定求解给定类型问题所需的所有“处理步骤”及执行顺序，使给定类型问题能在有限时间内被机械的求解 算法必须使用某种语言描述： 程序（计算机语言） 伪语言算法 非形式算法（自然语言） 本教材中使用了类C语言描述算法 算法五大特性： 1. 有穷性 2. 确定性 3. 有零个或多个输入 4. 有一个或多个输出 5. 有效性 一个算法首先应是正确的，此外考虑： 1. 执行算法所需时间 2. 执行算法所耗费存储空间（辅助空间） 3. 算法易于理解，易于编码，易于调试 算法所耗时间： 算法中每条语句执行时间之和 每条语句执行时间： 每条语句执行次数与该语句执行一次时间的乘积 语句执行的次数称为频度 例1-2 设变量a、b、c、d中各含一个整数。求a、b、c中的最大值与d的乘积 问题的规模： 算法求解问题的输入量，一般用n表示 时