《数据结构及算法》由会员分享，可在线阅读，更多相关《数据结构及算法（33页珍藏版）》请在金锄头文库上搜索。
1、数据结构及算法b课程名称：数据结构及算法b预修课程: C语言, 高等数学b教材：1.数据结构(C语言版)清华大学出版社 1997 2.数据结构题集(C语言版)清华大学出版社 1999b教师：徐镜春 关于习题与实验题教材中习题放在每章结束,但学生在每周都应该完成与上 课内容相应的部分小题有精力的同学应该思考数据结构题集中未列为必做 的练习,这会有助于理解课程内容习题包括理论习题和上机实验题实验题要求用C语言编写,并在计算机上调试通过实验报告至少应包括 题目 算法步骤 源程序(不太多时写在作业本上) 运算结果及分析 调试过程与体会第一章 绪论11什么是数据结构12基本概念和术语13抽象数据类型的表
2、示与实现14算法和算法分析 141 算法 142 算法设计的要求 143 算法效率的度量 144 算法的存储空间需求1.1 什么是数据结构计算机解决问题的步骤 实际问题 - 数学模型-算法-程序- 结果 工程师 数学家 程序员计算机的用途 科学计算(数值运算): 解方程(组), 函数求 值, 概率统计等 非数值运算: 字符, 表格, 图象, 声音等计算机的用途-数值运算水库大坝的应力计算预报人口增长天气预报计算机的用途-非数值运算书目检索系统多叉路口的交通灯管理问题有连线的节点用不 同的颜色标记, 表 示不能同时通行.要求使用的颜色数 尽可能少, 以使减 少等待时间.图论中的四色问题.多叉路口
3、的交通灯管理问题 不能同时通行的通路用连线把它们连起 来, 它们有: A-B 通路: CA, BD, BC A-D 通路: CB, BC B-C 通路: AB, AD B-D 通路: AB, CB C-A 通路: AB C-B 通路: BD, AD计算机的用途-非数值运算计算机与人对奕问题数据结构的定义描述非数值计算问题的模型是- 如表、树、图之类的数据结构数据结构是- 研究计算机的操作对象(数据)以及它们之间 的关系和操作等的学科.学科数据结构在计算机科 学中所处的地位综合性的专业基础课1.2 基本概念和术语数据：计算机程序处理的符号的总称。数据元素：数据的基本单位。 通常作为一个整体进行处
4、理。数据项：数据的不可分割的最小单位。 一个数据元素可以由若干个数据项构成。数据对象：性质相同的数据元素的集合 。数据结构：相互间存在一种或多种关系 的数据元素的集合。数据元素相互关系 - 称为“结构”四类基本结构 集合 线性结构 树型结构 图状结构（网状结构 ）数据结构的数学定义数据结构是一个二元组 Data_Structure = (D,S) D 数据元素的有限集合 S 定义在D上的关系的有限集合例如 Complex = (C,R) C = (c1,c2)| c1,c2是实数 R = P|P是定义在C上的关系，表示c1是 实部,c2是虚部逻辑结构和物理结构逻辑结构: 数据元素之间的逻辑关系
5、物理结构: 数据结构在计算机中的表示, 又称存储结构算法的设计取决于选定的逻辑结构算法的实现依赖于采用的存储结构数据类型与抽象的数据类型数据类型（Data Type）： 值的集合以及定义在这个集合上的一组操作。 例如: C语言中的整数类型抽象数据类型(ADT) 数学模型以及定义在该模型上的一组操作。 与其在计算机中的表示和实现无关。 ADT可用三元组表示：（D,S,P） D 数据对象; S D上的关系; P 对D 的基本操作集抽象数据类型的定义格式：ADT抽象数据类型名数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义 ADT抽象的数据类型名基本操作的定义格式为： 基本操
6、作名（参数表） 初始条件：初始条件描述 操作结果：操作结果描述抽象数据类型三元组的定义ADT Triplet 数据对象：D = e1,e2,e3 | e1,e2,e3属于 Elemset(定义了关系的某个集合) 数据关系：R1 = e1,e2|e2,e3 基本操作： InitTriplet(*e=Ti-1;return OK; 1.4 算法和算法分析, 1.4.1 算法算法（Algorithm）:对特定问题求解步骤 的一种描述算法的五个重要特性： （1）有穷性 （2）确定性 （3）可行性 （4）输入 （5）输出算法举例-气泡排序算法初始条件：n个待排序的数a0-an-1结果：排序后a0-an-
7、1从小到大排列 （1）置标记 change = TRUE; （2）i 从n-1直到i=2做（3）-（6）步 （3）change = FALSE; （4）j从0直到j=i-1做（5） （5）若ajaj+1则交换它们并置change=TRUE （6) 若change = FALSE则结束 （7）算法结束冒泡排序算法（1）1）i 从n-1直到i=2做（2）-（3）步 2）j从0直到j=i-1做（3） 3）若ajaj+1则交换它们 4）算法结束 void bb_sort(int a, int n)for (i=n-1; i1; -i) for (j= 0; j aj+1) aj aj+1; /bb_s
8、ort1.4.2 算法设计的要求算法应达到的目标 （1）正确性 （2）可读性 （3）健壮性 （4）效率与低存贮量1.4.3 算法效率的度量（1) 事后统计法（2）事前分析估算法 算法的时间复杂度：基本操作重复执行的次 数。 它是问题规模n的某个函数f(n)： T(n) = O(f(n)例如：两个nxn矩阵相乘两个nxn矩阵相乘的算法中乘法运算是基本操 作，其重复执行的次数为n3。该算法的时间复杂度为: T(n) = O(n3)。 for (i=1; i1 - i) change = false;for (j= 0; j aj+1) aj aj+1; change=TURE; /bubble_sort 渐近时间复杂度(阶)与语句频 度时间复杂度只考虑对于问题规模的增长率在难以精确计算基本操作执行次数时, 仅需 要求增长率(或阶)即可.阶： for(i=2; i1), 2n , 3nnc(c1), n2, n3nlog(n), nlog2(n)nr(0r1.0)log(n), log2(n)实验要求与习题理论习题 1.1, 1.2, 1.5, 1.6, 1.8, 1.10, 1.12实验题: 1.9并通过上机验证结果, 1.16,1.18
