《数据结构 第一章概论PPT课件》由会员分享，可在线阅读，更多相关《数据结构 第一章概论PPT课件（27页珍藏版）》请在金锄头文库上搜索。
1、数据结构 第一章绪论 1 1数据结构研究什么 将现实世界中的数据描述及关系表示出来 并存储到计算机内 供用户程序操作 现实世界中的数据描述及关系 4种 离散型 线性结构 层次结构 网状结构 离散数学 研究离散型 数据结构 研究线性结构 层次结构和网状结构 线性结构 线性表表示 层次结构 树形结构表示 网状结构 图结构表示 数据结构研究 数据逻辑结构 存储结构及施加其上的运算 例1L 20 5 66 15 44 是一个线性表例2一张登记表DL序号姓名性别年龄1李刚男25记录12王霞女29记录23刘大海男40记录34李爱林男44记录4其中 姓名 性别 年龄是数据项 item 数据域 field 姓
2、名 性别 年龄 是记录 record C语言将 记录 record 定义为 结构 struct 登记表也是一个线性表 例3家族中父子关系是一种层次结构 树T 张一 张三 张二一 张三一 张三小 张三大 张二 张四 层次结构 部门之间的隶属关系 学校 系 科 班领导和被领导之间领导关系 主席 部长 司长 处长 科长 例4无向图G A B D C E F G 其中 A B C等是顶点 vertex 图中任意两个顶点之间都可能有关系 网络结构 电网 电信网 计算机通信网等 1 基本数据结构的定义 特性 运算与算法1 1线性结构 线性表 栈 队列 双队列 数组 串 1 2非线性结构 树 二叉树 图 网
3、络 2 数据结构的存储结构与实现选择存储结构 设计算法3 查找算法 顺序 折半 分块 哈希 二叉排序树等4 排序算法 内部排序 外部排序5 文件6 基本应用与综合应用要求具备的知识 c语言及程序设计 具有一定的程序设计能力 本课程的内容和任务 1 2基本概念和术语 1 数据 data 所有能输入到计算机中并被计算机程序加工 处理的符号的总称 如 整数 实数 字符 声音 图象 图形等 2 数据元素 dataelement 数据的基本单位 元素 记录 结点 顶点 在计算机程序中通常作为一个整体进行考虑和处理 3 数据项 dataitem 是数据的不可分割的最小单位 如 姓名 年龄等一个数据元素可由
4、一个或多个数据项组成 如 姓名 年龄 4 数据对象 dataobject 由性质相同 类型相同 的数据元素组成的集合 数据对象是数据的一个子集 例1由4个整数组成的数据对象D1 20 30 88 45 例2由正整数组成的数据对象D2 1 2 3 例3由26个字母组成的数据对象D3 A B C Z 其中 D1 D3是有穷集 D2是无穷集 5 抽象数据对象ElemSet 某种同类型的数据元素 6 数据结构 datastructure 数据之间的相互关系 即数据的组织形式 内容包括 数据逻辑结构 数据存储结构和数据运算 数据逻辑结构 数据元素之间的逻辑关系 数据存储结构 数据元素及其关系在存储器中的
5、存储表示 数据运算 定义在数据逻辑结构上的操作 如 查询 插入 删除和修改 排序等 数据逻辑结构有两大类 线性结构 特征 若结构是非空集 则仅有一个开始结点和一个终止结点 其他结点都只有一个前趋结点和一个后继结点 非线性结构 特征 一个结点有多个前趋结点和后继结点 数据存储结构有4种 顺序存储结构 链接存储结构 索引存储结构和散列存储结构 数据逻辑结构和存储结构与运算三者之间有紧密的关系 如 给定一种数据的逻辑结构 可采取顺序存储结构或链接存储结构进行存储 按定义的运算和运算性质的不同 施加于同一数据结构上 则会导致有不同的种类的数据结构产生 如 限制在线性表的一端做插入和删除操作 称该线性表
6、为栈 若限制在线性表的一端插入 另一端删除操作 称该线性表为队 其栈和队都有顺序存储结构或链接存储结构 则它们存储结构称为 顺序栈 链式栈 顺序队 链式队 1 线性表2 栈线性结构3 队列 双队列4 数组数据结构5 字符串非线性1 树 二叉树结构2 图 数据逻辑结构分类 数据顺序存储结构和链式存储结构 物理结构 存储表示 物理表示 数据结构在计算机存储器中的映象 mapping 1 顺序存储结构 向量 一维数组 例 chara 5 A B C D ABCDE01234a是一维数组 2 非顺序存储结构 链接表 指针类型和结构类型定义 例 单链表datanext Head A B C D 4个结点
7、的单链表 7 数据类型 datatype 是一个值的集合和定义在这个值上的一组操作的总称 用数据类型定义数据结构 1 原子类型 如 int char float等 2 结构类型 如 数组 结构 联合体等 8 抽象数据类型 AbstractDataType 与计算机的实现无关的数据类型 形式定义 ADT抽象数据类型名 1 数据对象 2 数据关系 一个或多个关系 3 一组基本操作 运算 ADT抽象数据类型名注意 常用DataType表示抽象元素类型 1 3算法和算法分析数据的运算是通过算法描述的 1 算法 求解一个特定任务的指令的有限序列 例 求a 0 n 1 中n个数的平均值 假定n 0 flo
8、ataverage floata intn inti floats 0 0 累加器赋初值for i 0 i n i s s a i a i 累加到s中s s n 计算平均值printf ave f s 输出return s 返回 其中 a n为输入量 s为输出量 2 算法的5个特征 1 有穷性 在有限步 或有限时间 之后算法终止 例 i 0 s 0 while i 10 s i 2 确定性 无二义性 例 x 5 y 10 z x y printf d d d x y z x y解释为 x y x y 3 可行性 可以在计算机上实现 for i 1 s 0 i 1000000000000 i s
9、 4 输入 有0或多个输入量 5 输出 至少有一个输出量 3 算法设计要求 1 正确性a 无语法错误 b 对n组输入产生正确结果 c 对特殊输入产生正确结果 d 对所有输入产生正确结果 2 可读性 算法主要是为了人的阅读与交流 3 健壮性 有出错处理的提示 4 高效与低存储量 下列描述不符合算法的什么特征和要求 例1voidsuanfa1 inti s 0 for i 0 i 0 i 死循环s 不能终止 例2floatsuanfa2 intx y scanf d x y sqrt x 当x 0时 出错return y 4 算法的时间复杂度 衡量算法性能 a 算法正确性 b 执行算法所消耗的时间
10、 c 执行算法所消耗的空间 主要考虑辅存空间 d 算法易读易理解 易于编码 易于调试等 主要讨论算法执行时间 算法所消耗的时间 算法中每条语句执行时间之和 每条语句执行时间 语句的执行次数 一次执行该语句的时间 语句的频度 设n为求解的问题的规模 基本操作 或语句 执行次数总和称为语句频度 记作f n 问题的规模n 指线性表的长度 多项式的项数 矩阵的阶数 树的结点数 图中的顶点或边数等 注 一次执行语句的时间是很难精确算出的 它与机器的执行速度 编译程序编译质量及运行环境等因素有关 算法所消耗的时间粗略地用算法中语句执行的最大次数来度量 求两个n阶方阵的乘积 C A B definen100
11、intMultiply inta n n intb n n intc n n intj i k 语句的频度f n 1 for i 0 i n i n 1 2 for j 0 j n j n n 1 3 c i j 0 n2 4 for k 0 k n k n2 n 1 5 c i j c i j a i k b k j n3 算法所消耗的时间就是所有语句频度之和T n T n 2n3 3n2 2n 1T n 是矩阵的阶数n的函数 当n 2n3 3n2 2n 1与n3同阶 即同一数量级 记为 T n O f n O n3 即与f n 中最高的阶相同 例1 ints 语句的频度f n scanf
12、d s 1s 1printf d s 1 其中 语句频度为 f n f 1 3与问题规模n无关的常数 时间复杂度为 T n O f n O 3 O 1 O 1 称成为常量阶 常量数量级只要算法的执行时间不随问题规模n增大而增长 即使算法中有上千条语句 其执行的时间只不过是一个较大的常数 算法的时间复杂度仍然是常数阶O 1 例2分析下面的算法 voidsum inta intn f n ints 0 i 1次for i 0 i n i n次s s a i n次printf d s 1次 其中 语句频度为 f n 1 n n 1时间复杂度为 T n O f n O 2n 2 O n O n 称成为
13、线性阶 线性数量级一般情况下 对步进循环 只考虑循环体中的语句执行的次数 可忽略步长加1 终值判断 控制转移等成分 例3分析下面的算法 1 voidsum intm intn 2 inti j s 0 1次3 for i 1 i m i m次4 for j 1 j n j m n次5 s m n次6 printf d s m次7 8 其中 f m n 1 m 2 m n m 2mn 2m 1当m n时 f n 2n2 2n 1T n O f n O 2n2 2n 1 O n2 平方阶 对嵌套层次的循环结构 时间的复杂度T n 由最内层循环体语句的频度f n 决定 例4分析下面的算法 1 voi
14、dsum intn 2 inti j s 0 1次3 for i 1 i n i n次4 for j 1 j i j 次5 s 次6 printf d s n次7 8 其中 第4行的次数为1 2 n n 1 n 2第5行的次数为1 2 n n 1 n 2f n 1 n n n 1 n n2 3n 1T n O f n O n2 平方阶例5有算法 在数组a 0 n 1 中查找k值 1 i n 1 2 while i 0若a中最前一个元素是要找的k 则 3 语句的频度为常数0 在这种情况下 采用最坏的时间复杂度作为算法的时间复杂度 T n 0 n 常用时间复杂度递增依次为 常数阶O 1 对数阶O
15、log2n 线性阶O n 线性对数阶O nlog2n 平方阶O n2 立方阶O n3 K方阶O nk 指数阶O 2n O 1 算法效率最高 O 2n 算法效率最低 5 算法的空间复杂度执行算法所需存储空间的大小 也是问题规模n的函数 6 算法的复杂度包括 算法时间复杂度和算法空间复杂度 低 高 例6冒泡排序的C语言算法 对数组a中n个数按递增次序作冒泡排序1 Voidbubble1 inta intn 2 inti j temp 3 for i 0 ia j 1 次6 temp a j 次7 a j a j 1 次8 a j 1 temp 次9 10 for i 0 i n i n次11 printf d a i n次12 思考 在最好情况下 f n T n O f n 在最坏情况下 f n T n O f n 例7冒泡排序的 类C语言 算法 对数组a中n个数按递增次序作冒泡排序1 voidbubble2 inta intn 2 for i n 1 change TRUE i 1 change i 3 change FALSE change为交换标志4 for j 0 ja j 1 6 a j a j 1 交换元素7 change TRUE 修改交换标志8 9 10 思考 在最好情况下 f n T n O f n 在最坏情况下 f n T n O f n
