《算法与数据结构》教学课件-第1章 绪论--C语言描述（第2版）张乃孝编著汇.ppt

张乃孝 算法与数据结构——C语言描述 张乃孝：算法与数据结构——C语言描述 数据结构 信息学院信息技术教研室 XXX 副教授 素质提高 认真的态度 全局的观念 合作的精神 教学计划 讲课：3学时/周 上机：2学时/周 （1-507） 学习方法 复习 c语言的相关内容: 子函数、指针、数组、结构体 实践 深入思考 编写算法 上机调试 成绩考核 平时 30% 考勤 书面作业、网络课堂测试（）、 实验（实验报告、源程序）、 期中考试 期末考试(笔试) 70% 分治法： 把一个规模较大的问题分成两个或多个较小的与原问题相似的子问题，首先对子问题进行求解，然后把各个子问题的解合并起来，得出整个问题的解，即对问题分而治之。 分治法： 二分法检索 对数据结构的要求：顺序有序表 查找方法： 先确定待查记录所在范围，然后逐步缩小范围，直到找到该记录，或查找区间缩小到0也没有查找到给定值的记录为止。 确定待查记录所在范围：用二分区间的方法。 A B C K J I H O N M L G F E D 0 0 0 0 0 0 0 1 1 1 1 1 1 1 45 50 25 25 0 对于n=3时的0-1背包问题，假设w=[16,15,15], p=[45,25,25],c=30用分支限界法解： A B C K J I H O N M L G F E D 0 0 0 0 0 0 0 1 1 1 1 1 1 1 45 50 25 25 0 对于n=3时的0-1背包问题，假设w=[16,15,15], p=[45,25,25],c=30用分支限界法解： 1.4.3 算法的精化 算法?程序 排序问题 把n个整数从大到小排序。 算法思想（直接选择排序） （1）从数组a中选出一个最大的整数放到一个空的数组a’中，作为a’的第一个元素。 （2）从数组a中剩下的元素中再选出最大的整数放到a’中，接在前一个已放入元素的后面。 （3）反复执行步骤（2），直到a中所有的整数都放到排好序的a’中。 对于数据结构的不同理解，实际上都离不开以下三个要素： 逻辑结构：它定义了数学模型中的基本元素和元素之间的相互关系。 存储结构：它给出了数学模型的具体表示方式，包括结点的表示和关系的表示。 操作：它给出抽象数据类型关心的各种行为在存储结构上的具体实现算法。 1.3.2 数据结构的分类 按逻辑结构分类 逻辑结构可以用一个二元组B=K , R来表示，其中K是结点的有穷集合，R是K上的一个关系。 所谓关系可以理解为“二元组的集合”。K上的二元组是K中元素的有序对，记为k , k’。K上的一个关系就是K 上的一些二元组组成的集合，K上不同的二元组集合构成不同的关系。 如果k , k’ ∈ K, k , k’∈R, 则称k为k’的前驱，k’为k的后继。没有前驱的结点成为开始结点，没有后继的结点称为终端结点。 根据R的特点可以将数据结构分为三类： （1）线性结构：K中每个结点最多只有一个前驱结点和一个后继结点。 （2）树形结构： K中每个结点最多只有一个前驱结点，但可以有多个后继结点。 （3）复杂结构：K中结点的前驱、后继结点个数不作限制的结构。 按存储结构分类（四类）： 顺序表示：有一个连续的空间，顺序存放数据结构中的各个结点。 链接表示：结点的存放位置是任意的，结点之间的关系通过与结点关联的指针方式显式表达出来。 散列方式：选择适当的散列函数，根据关键码的值将结点映射到给定的存储空间（散列表）中。 索引方式：通过辅助的索引结构给出一个从关键码到存储地址的映射方法。索引结构由索引项组成，每个索引项包含一个结点的关键码和该结点的存储位置。 1.3.3 结点与结构 在实际应用中，一个结点可以是一个字符、一个整数，也可以是一个struct。 在数据结构的讨论中，重点研究的是“结构”，至于每个结点的具体类型并非关心的重点，为了叙述的简便，通常假设为一个初等类型（例如，整数类型）。 1.3.4 外存数据的组织（略） 1.4 算法 1.4.1 什么是算法 算法的概念 算法(Algorithm)是由有穷规则构成的为解决某一类问题的运算序列。 算法可以有若干输入，这些输入是在算法开始时给出的初始值或条件；算法通常又有若干个输出，它们是同输入有某种关系的计算结果。除此之外，算法还有以下性质： 有穷性; 确定性; 可行性; 有穷性。一个算法必须在执行了有穷步之后结束。 确定性。算法的每一步，必须有确切的定义。 可行性。算法的每个动作，都是能够由机器或人准确完成的，是“力所能及”的。 算法的正确性 算法能够实现预想的目标。 如果一个算法以一组满足初始条件的输入开始，那么该算法的执行一定终止，并且在终止时得到满足要求的结果。 1.4.2 算法的设