[工学]数据结构导论2142第一章.ppt

数据结构导论 主讲： 1，国考（高职试本） 国考成绩80%，平时成绩20% 2，过程考（试本） 主考院校成绩50%，平时成绩50% 第1章 概论 1.1引言 1.2数据、逻辑结构和运算 1.3存储实现和运算实现 1.4算法分析 1.5数据结构及其评价和选择 1.1引言 数据结构主要研究： 1）计算机加工对象（数据）的逻辑结构 2）实现各种基本操作的算法。 数据表示、数据处理 应用举例1——学籍档案管理 学号姓名 李军 性别 男 出生年月 80.12 …… 学号姓名 单晓宏 性别 男 出生年月 81.3 假设一个学籍档案管理系统应包含如下表1-1所示的学生信息。 数据特点： 每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格； 表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构； 对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。 应用举例2——制定教学计划 在制定教学计划时，需要考虑： 各门课程的开设顺序，即有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。 1.2 数据、逻辑结构和运算 基本术语 数据（Data)：所有能被计算机处理的符号的集合。 数据元素（Data Element）：是数据这个集合中的一个个体。 数据项（Data Item）：数据元素常常还可分为若干个数据项，数据项是数据具有意义的最小单位。 逻辑结构（Logical Structure）： 指数据元素之间的结构关系。 物理结构（Physical Structure）： 指数据结构在机内的表示，也称为存储结构。 逻辑结构的种类： 特别注意： 运算的分类 加工型运算：其操作改变原逻辑结构的值 如：结点个数，结点内容等 引用型运算：其操作不改变原逻辑结构的值 查找 读取 插入 删除 更新 以上操作哪些是加工型操作，那些是引用型操作？ 1.3存储实现和运算实现 数据在计算机内的表示形式称为数据的存储结构 存储结构的主要部分 存储结点（每个存储结点存放一个数据元素） 数据元素之间关联方式的表示 附件设施 4种存储结构 顺序存储结构：借助数据元素的相对存储位置来表示数据的逻辑结构； 链式存储结构：借助数据元素地址的指针表示数据的逻辑结构 索引存储结构：借助索引表中的索引指示各存储节点的存储位置 散列存储结构：用散列函数指示各节点的存储位置 逻辑结构与存储结构的关系 运算的实现 算法规定了求解给定类型问题所需的所有“处理步骤”及执行顺序，使给定类型问题能在有限时间内被机械的求解 算法必须使用某种语言描述： 程序 伪语言算法 非形式算法（自然语言） 本教材中使用了类C语言描述算法 Printf表示输出，scanf表示输入 1.4算法分析 评价算法的好坏标准 正确性 易读性 健壮性 高效性 一个算法的时空性是指算法的 时间复杂度和空间复杂度 算法分析主要分析算法的 时间复杂度和空间复杂度，目的是提高算法的效率 例1-2 设变量a、b、c、d中各含一个整数。求a、b、c中的最大值与d的乘积 如何确定算法的计算量 合理地选择一种或几种操作作为“标准操作”，无特殊说明，默认以赋值语句作为标准操作 确定每个算法共执行多少次标准操作，并将此次数规定为该算法的计算量 如何确定算法的计算量 以算法在所有输入下的计算量的最大值作为算法的计算量，称为算法的最坏情况时间复杂度 以算法在所有输入下的计算量的加权平均值作为算法的计算量，称为算法的平均情况时间复杂度 最坏情况时间复杂度和平均情况时间复杂度通称为时间复杂度 例矩阵运算—矩阵乘法 Void matrixmlt ( ……) { for(i=0;in;i++) for(j=0;jn;j++) { C[i][j]=0; for(k=0;kn;k++) C[i][j]+=A[i][k]*B[k][j] ; } } 本课程讲述的主要内容 本课程将分别讲述数据结构的基本概念、线性表、栈和队列、串和数组、树形结构、图结构、查找、排序和文件等内容。 * * 表1-1 应用举例2——制定教学计划 数据结构主要研究： 数据的逻辑结构可归结为以下四类: 线性结构 树形结构 图状结构 集合结构 逻辑结构与数据元素本身