数据结构与算法.ppt

第一章绪论 1 3什么是数据结构 1 4基本概念和术语 1 5算法和算法的描述 1 1引言 1 2数据结构的地位 1 1引言 数值计算 非数值计算 研究数据的特性以及数据之间的关系 数据结构 1 2数据结构的地位 数据结构是介于数学 计算机硬件和计算机软件三者之间的一门核心课程 数学 硬件 软件 数据结构 1 3什么是数据结构 例1书目检索系统 程序 数据结构 算法 例2人机对奕问题 例3多叉路口交通灯管理问题 数据结构 是研究 程序设计中 计算机的操作对象以及它们之间关系和运算的一门学科 数据 计算机中描述客观事物的符号 节点 数据元素 数据的基本单位 1 4基本概念和术语 节点 数据项 图状结构 多个对多个 如 图 3 逻辑结构 数据元素之间的逻辑关系 线性结构 一个对一个 如 线性表 栈 队列 树形结构 一个对多个 如 树 根据数据元素之间的逻辑结构可将数据结构分为三类 4 存储结构 物理结构 数据在计算机中的存储表示 算法设计逻辑结构算法实现存储结构 链式存储结构 借助指示元素存储地址的指针表示数据元素间的逻辑关系 存储结构分为两种 顺序存储结构 借助元素在存储器中的相对位置来表示数据元素间的逻辑关系 数据的逻辑结构与存储结构密切相关 数据的逻辑结构 数据的存储结构 线性结构 顺序存储 链式存储 线性表 栈 队列 树形结构 图形结构 数据结构的两个方面 7 数据类型 数据的取值范围及其操作的总称 例 C语言中 提供int char float double等基本数据类型 数组 结构体 共用体 枚举等构造数据类型 还有指针 空 void 类型等 用户也可用typedef自定义数据类型 typedefstruct intnum charname 20 floatscore STUDENT STUDENTstu1 stu2 p 6 数据结构 数据元素和数据元素关系的集合 5 数据处理 插入 删除 查找 排序 修改等 8 算法 算法 解决特定问题的方法 1 5算法和算法的描述 1 5 1算法算法是执行特定计算的有穷过程 这个过程有5个特点 1 动态有穷 当执行一个算法时 不论是何种情况 在经过了有限步骤后 这个算法一定要终止 2 确定性 算法中的每条指令都必须是清楚的 指令无二义性 3 输入 具有0个或0个以上由外界提供的量 4 输出 产生1个或多个结果 5 可行性 每条指令都充分基本 能在有限的时间内完成 注意 算法和程序是有区别的 即程序未必能满足动态有穷 在本书中 只讨论满足动态有穷的程序 因此 算法 和 程序 是通用的 一个算法可以用自然语言 数字语言或约定的符号来描述 也可以用计算机高级程序语言来描述 如Pascal语言 C语言或伪代码等 1 5 2算法的描述 本书选用C语言作为描述算法的工具 defineTRUE1 defineFALSE 1 defineERRORNULL 1 预定义常量和类型 简单说明C语言的语法结构 数据类型 函数名 形式参数 形式参数说明 内部数据说明 执行语句组 函数名 2 函数的形式 函数的定义主要由函数名和函数体组成 函数体用花括号 和 括起来 函数中用方括号括起来的部分为可选项 函数名之间的圆括号不可省略 函数的结果可由指针或别的方式传递到函数之外 执行语句可由各种类型的语句所组成 两个语句之间用 号分隔 可将函数中的表达式的值通过return语句返回给调用它的函数 最后的花括号 之后的 函数名 为注释部分 可舍 简单赋值 变量名 表达式 它表示将表达式的值赋给左边的变量 变量 它表示变量加1后赋值给变量 变量 它表示变量减1后赋值给变量 3 赋值语句 成组赋值 1 变量1 变量2 变量3 变量k 表达式1 表达式2 表达式3 表达式k 2 数组名1 下标1 下标2 数组名2 下标1 下标2 串联赋值 变量1 变量2 变量3 变量k 表达式 条件赋值 变量名 条件表达式 表达式1 表达式2 交换赋值 变量1 变量2 表示变量1和变量2互换 情况语句 switch 表达式 case判断值1 语句组1 break case判断值2 语句组2 break case判断值n 语句组n break default 语句组 break 注意 switchcase语句是先计算表达式的值 然后用其值与判断值相比较 若它们相一致时 就执行相应的case下的语句组 若不一致 则执行default下的语句组 其中的方括号代表可选项 4 条件选择语句 if 表达式 语句 if 表达式 语句1 else语句2 for语句for 表达式1 表达式2 表达式3 循环体语句 5 循环语句 首先计算表达式1的值 然后求表达式2的值 若结果非零则执行循环体语句 最后对表达式3运算 如此循环 直到表达式2的值为零时止 while循环首先计算条件表达式的值 若条件表达式的值非零 则执行循环体语句 然后再次计算条件表达式 重复执行 直到条件表达式的值为假时退出循环 执行该循环之后的语句 while语句 while 条件表达式 循环体语句 该循环语句首先执行循环体语句 然后再计算条件表达式的值 若条件表达式成立 则再次执行循环体 再计算条件表达式的值 直到条件表达式的值为零 即条件不成立时结束循环 do while语句 do 循环体语句 while 条件表达式 输入语句 用函数scanf实现 当数据为字符时 用getchar函数实现 输出语句 用printf函数实现 当要输出字符数据时 用putchar函数实现 6 输入 输出语句 1 return表达式或return 用于函数结束 2 break语句 可用在循环语句或case语句中结束循环过程或跳出情况语句 3 exit语句 表示出现异常情况时 控制退出语句 8 注释形式可用 字符串 单行注释或 文字序列 7 其他一些语句 如 max函数 用于求一个或几个表达式中的最大值 min函数 用于求一个或几个表达式中的最小值 abs函数 用于求表达式的绝对值 eof函数 用于判定文件是否结束 eoln函数 用于判断文本行是否结束 9 一些基本的函数 设计一个好的算法应考虑以下几个方面 1 正确性 正确 的含义在通常的用法中有很大的差别 大体可分为以下四个层次 程序不含语法错误 程序对于几组输入数据能够得出满足规格说明要求的结果 程序对于精心选择的典型 苛刻而带有刁难性的几组数据能够得出满足规格说明要求的结果 程序对一切合法的输入数据都能产生满足规格说明要求的结果 1 5 3算法评价 运行时间是指一个算法在计算机上运算所花费的时间 它大致等于计算机执行一种简单操作 如赋值操作 转向操作 比较操作等等 所需要的时间与算法中进行简单操作次数的乘积 通常把算法中包含简单操作次数的多少叫做算法的时间复杂性 它是一个算法运行时间的相对量度 T n O f n 2 运行时间 时间复杂度的计算 例1 x s 0 1 O 1 T n O f n for i 1 i n i x s x n O n for j 1 j n j for k 1 k n k x s x n n O n2 例2 例3 频度 时间复杂度 程序 voidfactorsum n intn inti j intf w f 0 for i 1 i n i w 1 for j 1 j i j w w j f f w return 上述算法所用到的运算有乘法 加法 赋值和比较 其基本运算为乘法操作 在上述算法的执行过程中 对外循环变量i的每次取值 内循环变量j循环i次 因为内循环每执行一次 内循环体语句w w j只作一次乘法操作 即当内循环变量j循环i次时 内循环体的语句w w j作i次乘法 例4计算f 1 2 3 n 用C语言描述 整个算法所作的乘法操作总数是 f n 1 2 3 n n n 1 2 T n O n2 一个算法在计算机存储器上所占用的存储空间 包括存储算法本身所占用的存储空间 算法的输入 输出数据所占用的存储空间和算法运行过程中临时占用的存储空间 分析一个算法所占用的存储空间要从各方面综合考虑 算法在运行过程中所占用的存储空间的大小被定义为算法的空间复杂性 它包括局部变量所占用的存储空间和系统为了实现递归所使用的堆栈这两个部分 算法的空间复杂性一般以数量级的形式给出 空间复杂度 s n O f n 3 占用的存储空间 最简单和最直接的算法往往不是最有效的 但算法的简单性使得证明其正确性比较容易 同时便于编写 修改 阅读和调试 所以还是应当强调和不容忽视的 不过对于那些需要经常使用的算法来说 高效率 即尽量减少运行时间和压缩存储空间 比简单性更为重要 4 简单性 本章小结 本章主要介绍了如下一些基本概念 数据结构 数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储表示 即所谓数据的逻辑结构和物理结构 并对这种结构定义相适应的运算 设计出相应的算法 而且确保经过这些运算后所得到的新结构仍然是原来的结构类型 数据 数据是人们利用文字符号 数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述 在计算机科学中 数据的含义非常广泛 我们把一切能够输入到计算机中并被计算机程序处理的信息 包括文字 表格 图象等 都称为数据 结点 结点也叫数据元素 它是组成数据的基本单位 逻辑结构 结点和结点之间的逻辑关系称为数据的逻辑结构 存储结构 数据在计算机中的存储表示称为数据的存储结构 数据处理 数据处理是指对数据进行查找 插入 删除 合并 排序 统计以及简单计算等的操作过程 数据类型 数据类型是指程序设计语言中各变量可