数据结构基本概念.ppt

数据结构基本概念 数据结构的有关概念 本章要点 数据结构的分类及表示 算法及算法分析 2 1数据结构的有关概念 如 一个个人书库管理程序所要处理的数据是一张表格 数据 客观对象的符号表示 在计算机科学中 数据的含义非常广泛 我们把一切能够输入到计算机中并被计算机程序处理的信息 包括文字 表格 图象等 都称为数据 在如前所示的个人书库中 为了便于处理 把其中的每一行 代表一本书 作为一个基本单位来考虑 故该数据由10个数据元素构成 数据元素 数据的基本单位 在计算机程序中通常作为一个整体考虑和处理 例如 在如前所示的个人书库表格数据中 每个数据元素都有登录号 书号 书名 作者 出版社和价格等六个数据项构成 数据项 构成数据元素的成分 是数据不可分割的最小单位 每个数据元素可以由一个数据项 也可以由若干数据项组成 一般情况下 一个数据元素中含有若干个数据项 注 这里说的数据元素之间的关系是指元素之间本身固有的逻辑关系 与计算机无关 又称为数据的逻辑结构或抽象数据结构 结构 数据元素之间的关系 数据结构 相互之间存在一种或多种特定关系的数据元素的集合 即带结构的数据元素的集合 数据元素之间的逻辑关系分为 1 元素之间没有关系 集合 2 元素之间具有线性关系 线性数据结构 线性表结构 3 元素之间具有层次关系 层次数据结构 树结构 4 元素之间具有网状关系 网状数据结构 图结构 数据的逻辑结构 数据元素之间的逻辑关系 独立于计算机 是数据本身所固有的 例1 某班学生基本情况登记表 记录了每个学生的学号 姓名 专业 政治面貌 表中的记录是按学生的学号顺序排列的 学号姓名专业政治面藐001王洪计算机党员002孙文计算机团员003谢军计算机团员004李辉计算机团员005沈祥福计算机党员006余斌计算机团员007巩力计算机团员008孔令辉计算机团员 学生基本情况登记表的图示 学号关系是一种线性结构关系 例2家族的族谱家族的族谱反映的是家族成员之间的血缘关系 假设某家族有10个成员A B C D E F G H I J 他们之间的血缘关系可以用如下图表示 这种分支的结构关系被称为树结构 它很象一棵倒置的树 A是树的根 家族树的图示表示 11 图形表示法 西南科技大学 叶子 根 子树 数据的存储结构 逻辑结构在计算机存贮器中的映像 必须依赖于计算机 四种基本的存储方法 1 顺序存储方法 顺序存储结构 2 链接存储方法 链式存储结构 3 索引存储方法 4 散列存储方法 同一种逻辑结构可采用不同的存储方法 以上四种之一或组合 这主要考虑的是运算方便及算法的时空要求 2 2数据结构的表示 1图示表示 图示表示是由顶点和边构成的图 其中顶点表示数据 边表示数据之间的结构关系 学生基本情况表的图示表示 家族树的图示表示 用一个二元组 D S 表示数据结构 其中D是数据元素集合 S是D上关系的集合 2 二元组表示 家族树的二元组表示 D S D A B C D E F G H I J S A B 学生基本情况表的二元组表示 D S D 001 002 003 004 005 006 007 008 S 2 3算法与算法分析 一什么是算法 算法是对特定问题求解步骤的一种描述 例求10个正整数中最大数的算法 描述算法的方法有很多 流程图 自然语言 计算机语言 流程图描述 1 给10个元素a 0 a 9 输入数值 2 把第一个元素a 0 赋给用于保存最大值元素的变量max 3 把表示下标的变量i赋初值1 4 如果imax 则将a i 赋给max 否则不改变max的值 这使得max始终保存着当前比较过的所有元素的最大值 6 使下标i增1 以指示下一个元素 7 转向第 4 步继续执行 自然语言描述 main inti max a 10 printf 请输入10个整数 for i 0 imax max a i i printf 10个整数中的最大值为 max 计算机语言描述 1 输入 0个或多个输入 2 输出 1个或多个输出 3 有穷性 算法必须在有限步内结束 且每一步都是在有限时间内完成 4 确定性 在任何条件下 相同的输入只能得到相同的输出5 可行性 组成算法的操作必须能够在计算机上实现 二算法的基本特征 正确性可读性健壮性 当输入非法数据时 算法应做出适当反映或处理 执行算法所耗费的时间 时间复杂度 执行算法所耗费的存储空间 空间复杂度 三评价算法好坏的标准 同一个问题可以构造不同的算法 最终选择哪一个算法 这涉及如何评价一个算法好坏的问题 1 时间复杂度 一个算法执行所耗费的时间 从理论上是不能算出来的 必须上机运行测试才能知道 但我们不可能也没有必要对每个算法都上机测试 这是由于本身算法的实现也要耗费时间和精力的 因此 我们只需知道哪个算法花费的时间多 哪个算法花费的时间少就可以了 四算法效率 1 时间频度 一个算法花费的时间与算法中语句的执行次数成正比例 哪个算法中语句执行次数多 它花费时间就多 一个算法中的语句执行次数称为时间频度 记为T n n称为问题的规模 例 求下列算法的时间频度for i 1 i n i for j 1 j i j x x 1 分析 时间频度T n 1 2 3 n 例如 若T n n n 1 2 则有1 4 T n n2 1 故它的时间复杂度为 n2 即 n 与n2数量级相同 2 时间复杂度 设T n 的一个辅助函数为g n 定义为当n大于等于某一足够大的正整数n0时 存在两个正的常数A和B 其中A B 使得A T n g n B均成立 则称g n 是T n 的同数量级函数 把T n 表示成数量级的形式为 T n g n 其中 为Order 即数量级 的首字母 按数量级递增排列