第1章绪论08.ppt

2020 2 2 软件基础教案 第一章绪论 计算机软件基础 TheFoundationsofComputerSoftware 制作 自动化学院电子系讲课 陈惠兵office 教五楼 623telephone 88960264E mail bluechb 2020 2 2 软件基础教案 第一章绪论 学时数 56小时授课 34小时实验 22小时 教材 数据结构 使用C语言 第3版 西安交通大学出版社作者 朱战立 2020 2 2 软件基础教案 第一章绪论 学生 表格 数据结构课程简介 2020 2 2 软件基础教案 第一章绪论 UNIX文件系统的系统结构图 root bin lib user etc math ds sw yin tao xie Stack cpp Queue cpp Tree cpp 2020 2 2 软件基础教案 第一章绪论 交通图 图 乌鲁木齐 兰州 西安 呼和浩特 北京 郑州 成都 1892 1145 668 676 695 511 842 2020 2 2 软件基础教案 第一章绪论 由以上例子可见 非数值计算问题的数学模型不再是数学方程 而是诸如表 树和图之类的 数据结构研究的是计算机所处理的数据元素间的结构关系及其操作实现的算法 数据结构 2020 2 2 软件基础教案 第一章绪论 1 研究数据结构的重要性 数据结构直接影响着程序的结构和算法 从而影响程序的运行效率 数据结构研究计算机所处理的数据元素间的关系及其操作实现的算法 数据结构是培养学生软件设计能力的重点专业课之一 2 数据结构的课程安排 2020 2 2 软件基础教案 第一章绪论 第0章C语言的数据类型第1章绪论2学时第2章线性表6学时第3章堆栈和队列4学时第5章数组2学时第7章树和二叉树8学时第8章图2学时第9章排序4学时第10章查找4学时 2020 2 2 软件基础教案 第一章绪论 第0章C语言的数据类型 1 基本数据类型 intshort long unsignedfloatfloat double longdouble 在C语言中数据类型 基本类型和构造类型基本类型 整型 浮点型 字符型构造类型 数组 结构 联合 指针 枚举型 自定义 2020 2 2 软件基础教案 第一章绪论 2 指针类型 计算机的内存的数据存取 内存区 地址内存单元例 旅馆 房间号房间 计算机访问内存的方式 直接方式 按变量的地址存取变量 间接方式 将变量的地址放在另一个变量中 例 A抽屉的钥匙放在B抽屉中 对存放变量的地址进行操作 函数间传递值 2020 2 2 软件基础教案 第一章绪论 指针 地址 表示 2000是变量i的指针 指针变量 变量的指针 指向变量的指针变量 例 int p 1 char p 2 表示指针型变量 基本型 指针变量名 定义 2020 2 2 软件基础教案 第一章绪论 指针运算符 例 p 1 相当于a 引用 2020 2 2 软件基础教案 第一章绪论 3 数组类型 数组名就是数组的起始地址数组作为函数参数时 为地址传递 inta 100 a a 0 a 1 a 1 aa 0 a 1 a 1 2020 2 2 软件基础教案 第一章绪论 4 字符串 字符串定义成字符数组 0 为字符串结束标志 chara 40 Iamastudent strlen a 为14不包括 0 2020 2 2 软件基础教案 第一章绪论 5 结构体类型 结构体由若干个结构体成员组成 定义结构体类型变量 1 定义结构体类型 2 定义结构体类型变量 structstudent charname 10 intage floatscore structstudentstudent1 structstudentstu2 100 structstudent p 2020 2 2 软件基础教案 第一章绪论 6 自定义类型 typedefcharelemtype typedefstructstudent charname 10 intage floatscore stu elemtypea stustudent1 动态开辟空间函数都包含在stdlib h头文件中 很多情况下存储空间是动态建立的 在增加结点之前要为结点分配存储空间 删除接点之后要释放存储空间 7 动态存储和释放空间的函数 例如 int pi float pf pi int malloc 2 pf float malloc 4 再如 pi int malloc sizeof int pf float malloc sizeof float 1 malloc函数 2 calloc函数 如 char ps ps char calloc 10 sizeof char 3 free函数 freep pi 2020 2 2 软件基础教案 第一章绪论 第1章绪论 1 2抽象数据类型和软件构造方法 自学 1 3算法设计目标和算法评价 1 1数据结构基本概念 2020 2 2 软件基础教案 第一章绪论 1 1数据结构基本概念 1 数据 Data 2 数据元素 3 数据项 DataFilde 4 数据对象 DataObject 5 数据结构 DataStructure 有关术语 6 数据类型 7 操作 2020 2 2 软件基础教案 第一章绪论 1 数据 数据是人们利用文字符号 数字符号以及其他规定的符号对现实世界的事物及其活动所作的抽象描述 数据 x x是计算机操作的对象 数值性数据非数值性数据 例如 整数 实数数据计算字符串文本编辑图形 图象 声音多媒体 2 数据元素 具有独立含义的最小标识单位数据元素是表示一个事物的一组数据 是数据的基本单位 有时一个数据元素由若干个数据项组成 2020 2 2 软件基础教案 第一章绪论 3 数据项 域 数据不可分割的最小单位 数据元素是有若干个数据域 项 组成 数据处理的最小单位 性质相同的数据元素的集合 4 数据对象 关系 见下图 一个班学生集合为数据对象 每一个数据元素均有六个数据域 项 数据元素1 数据元素2 数据元素33 例如 学生管理登记卡 特点 数据对象 数据元素3 数据项 2020 2 2 软件基础教案 第一章绪论 5 数据结构 计算机处理的数据元素的组织形式及其相互间的关系 由数据元素的有限集合及所有数据元素之间的关系组成 记为 Data Structure D R 其中 D是数据元素的有限集 R是所有数据元素之间的关系的有限集合 2020 2 2 软件基础教案 第一章绪论 例如 下述数据结构来描述2行3列的矩阵 它是一个含6个数据元素 a1 a2 a3 a4 a5 a6 的集合 且集合上存在 行关系 和 列关系 两个次序关系 其中行关系为 列关系为 再如 2020 2 2 软件基础教案 第一章绪论 逻辑结构 线性结构 非线性结构 顺序存储链式存储 所有元素呈线状关系的数据结构 存储结构 用一组地址连续的存储单元依次存储各个元素 用一组任意的存储单元存放数据元素 逻辑结构 逻辑数据结构 存储结构 物理数据结构 从不同的抽象层次看 2020 2 2 软件基础教案 第一章绪论 6 数据类型 具有相同性质的计算机数据集合及在这个集合上的一组操作 7 操作 数据结构上需要或能够进行的处理 2020 2 2 软件基础教案 第一章绪论 数据结构 逻辑结构 存储结构 操作实现算法 线性数据结构 非线性数据结构 线性表 栈 队列 树 图 顺序存储结构链式存储结构索引存储结构散列存储结构 2020 2 2 软件基础教案 第一章绪论 1 3算法设计目标和算法效率度量 1 算法定义 算法是描述求解问题方法的操作步骤的集合 2 算法特性 输入性有0个或若干个输入输出性至少产生一个输出或执行一个有意义的操作确定性每步定义都是确切 无歧义的有穷性算法应在执行有穷步后结束 整个指令序列在有限的时间内完成 可行性 有效性 算法中的每一个步骤都应当能被有效的执行 并得到确定的结果 例如 被零除的计算动作是不能被有效执行的 算法的描述 c c PASCAL 类c等语言 2020 2 2 软件基础教案 第一章绪论 3 算法设计目标 1 正确性 满足要求 2 可读性 易于理解 3 健壮性 可处理非法数据 4 高时间效率 执行时间短 5 高空间效率 省空间 2020 2 2 软件基础教案 第一章绪论 4 算法效率的度量 首先算法必须是正确的 此外还需考虑 1 算法易于理解 易于编程 在计算机上实现 易于调试 2 要求算法高效 节省时间与空间 时间和空间相互之间有一种制约关系 何者为重需视具体情况而定 重点考虑因素 时间 2020 2 2 软件基础教案 第一章绪论 一个算法所耗费的时间 应该是该算法中每条语句的执行时间之和 而每条语句的执行时间又是该语句的执行次数 频度 与该语句执行一次所需时间的乘积 我们假定 每条语句一次执行的时间都是相同的 为单位时间 这样我们对时间的分析就可以独立于软硬件系统 一般 时间复杂度是问题规模n的函数 T n 当问题的规模n趋于无穷大时 把时间复杂度T n 的数量级 阶 称为算法的渐进时间复杂度 有时简称为时间复杂度 2020 2 2 软件基础教案 第一章绪论 严格的数学定义为 若T n 和f n 是定义在正整数集合上的两个函数 当存在两个正的乘数C和n0时 使得对所有的 成立 则 都有 这时称T n 的时间复杂度为f n 数量级 1 假定每条语句的执行时间为单位时间 算法的时间复杂度是该算法中所有语句的执行频度之和 2020 2 2 软件基础教案 第一章绪论 x x 1 执行n次O n x x 1 只执行一次O 1 x x 1 For i 1 i n i x x 1 For i 1 i n i For j 1 j n j x x 1 x x 1 执行n2次O n2 例1 计算时间复杂度 2020 2 2 软件基础教案 第一章绪论 2 一般情况下 对步进循环语句只考虑循环体语句的执行次数 而忽略该语句中步长加一 终值判别 循环转移等成份 因此 当有若干个循环语句时 算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度所决定的 例2 x 0 y 0 for k 1 k n k x for i 1 i n i for j 1 j n j n ny T n O n2 2020 2 2 软件基础教案 第一章绪论 definen自然数matri floatA n n floatB n n floatC n n inti j k for i 0 i n i for j 0 j n j C i j 0 基本语句1for k 0 k n k C i j A i k B k j 基本语句2 例3 求两个方阵的乘积C A B 2020 2 2 软件基础教案 第一章绪论 分析 2020 2 2 软件基础教案 第一章绪论 3 选择执行的成分 如if语句的执行时间 决定于then子句 else子句耗时较多的部分 例 temp i i j j temp 4 如果算法的执行时间是一个与问题规模n无关的常数 则算法的时间复杂度为常数阶 记作T n O 1 T n O 1 2020 2 2 软件基础教案 第一章绪论 5 很多算法的时间复杂度不仅与问题的规模有关 而且还与它所处理的数据集的状态有关 通常是根据数据集中可能出现的最坏情况估计出算法的最坏时间复杂度 或者数据元素等概率取值情况下的平均时间复杂度 例4 冒泡排序对数组a n 的n个整数进行排序 求算法时间复杂度 分析 该算法时间复杂度随待排序的数据不同而不同 当某排序过程中没有两个数组元素交换 则排序结束 此时因flag 0而不满足循环条件而终止 但是在最坏情况下