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

数据结构,信息学院信息技术教研室 xxx 副教授 ,c语言,数据结构,操作系统,数据库,编译原理,人工智能,算法的设计与分析,知识关联,数据结构,熟悉c语言,复杂程序的设计,能力培养,素质提高,认真的态度 全局的观念 合作的精神,教学计划,讲课：3学时/周 上机：2学时/周 （1-507）,学习方法,复习 c语言的相关内容: 子函数、指针、数组、结构体 实践 深入思考 编写算法 上机调试,成绩考核,平时 30% 考勤 书面作业、网络课堂测试（）、 实验（实验报告、源程序）、 期中考试 期末考试(笔试) 70%,上机实验报告参考大纲（p.26） 上机题目 1. 问题的需求分析 2. 抽象数据类型的设计 3. 算法与数据结构的设计 4. 算法的精化与程序的实现 5. 程序的调试与计算结果分析 6. 时间与空间代价分析 7. 有待改进的问题，收获与体会。,算法与数据结构 c语言描述（第2版） 张乃孝 编著 高等教育出版社,1 绪 论 学习数据结构的必要性 : 程序 数据结构 算法,1.1 从问题到程序 建立计算机求解问题的模型。 模型的形式有：容易被人理解但不太严格的需求模型；比较抽象但很精确的数学模型；容易被计算机理解或执行的实现模型。,为一个实际问题开发一个程序 系统通常可以分成以下四个阶段,编码阶段,设计阶段,分析阶段,测试和维护,（与本课程关系最密切）,问题分析示例,对于一个多叉路口， 设计一个交通信号灯 的管理系统。首先需 要分析一下所有车辆 的行驶路线的冲突问 题。这个问题可以归 结为对车辆的可能行 驶方向作某种分组， 对分组的要求是使任 一个组中各个方向行 驶的车辆可以同时安 全行驶而不发生碰撞。,1.1.1 问题分析与抽象,可通行方向 ab ac a d b a bc bd da db d c e a eb ec ed,有些通行方向显然不能同时进行，相应的结点间画一条连线。,ab,ac,ad,ba,bc,bd,da,d b,dc,ea,eb,ec,ed,图1.2 交叉路口行驶冲突的模型,把图1.2中的结点进行分组，使得有线段相连的结点不在同一个组里。 通过上面的分析，我们就获得了该交通管系统的数学模型。下面就可以着手进行算法的设计。,1.1.2 程序的设计与实现 选择算法,2. “贪心法” while 有结点未着色； 选择一种新颜色； 在未着色的结点中,给尽可能多的彼此结 点之间没有边的点着色； ,1. “穷举法”：对n个结点，逐个测试其所有组合；,用一种颜色给尽可能多的结点上色，只要这些结点之间没有边相连。,ab,ac,ad,ba,bc,bd,da,d b,dc,ea,eb,ec,ed,图1.2 交叉路口的图示模型,把上面方法应用于图1.2，得到下面的分组： 绿色：ab, ac, ad, ba, dc, ed 蓝色：bc, bd, ea 红色：da, db 白色：eb, ec 选择抽象数据类型： 图,算法的描述 假设需要着色的图是g，集合v1包括图中所有未被着色的结点，着色开始时v1是g所有结点集合。new表示已确定可以用新颜色着色的结点集合。 从v1中找出可用新颜色着色的结点集的程序框架描述为： new= ; for 每个v v1 do if v与new中所有结点间都没有边 从v1中去掉v ; new=newv ; ,对集合和图的操作: 判断一个集合是否为空:isempty(v1); 从集合中去掉一个元素:remove(v1,v); 向集合里增加一个元素:add(new,v); 检查结点v与结点集合new中各结点之间在图g中是否有边连接: notadjacentwith(new,v,g); 有了图、集合这样的结构和基于其上的操作，程序的实现非常简单。,算法1.1 贪心法着色 int colorup( graph g) int color=0; set v1=g.v,new; while(!isempty(v1) new=; while(vv1 ,教材错误,数据结构的设计 程序员需要自己用语言所提供的类型机制实现集合、图这些抽象数据类型。 算法的精化与代码生成 根据设计的数据结构，对算法的描述进行进一步的精化。例如， notadjacentwith(new,v,g)如何具体来实现?如果这个问题比较复杂，就还需要选择算法，也可能存在需要新的数据类型和数据结构。经过这种反复的精化过程，直到算法中所有部分都细化为能用程序设计语言描述的成分，得到的就是我们希望的程序。,1.2 抽象数据类型 1.2.1 什么是抽象数据类型 类型(type)是一组值的集合。如，true和false 数据类型（data type）通常是指在计算机语言中可以使用的一个类型，它不仅包括这个类型的值的集合，还包括定义在这个类型上的一组操作。如，整数。 抽象数据类型(abstract data type简称adt)是具有一定操作的抽象类型。它不关心类型中值的表示形式和各种操作的具体实现方法，是所有可能的值的具体表示和各种操作的具体实现的抽象。,1.2.2 意义和作用 抽象数据类型的实质是抽象出了数据类型的使用要求，而把它的具体表示方法和运算的实现细节都隐藏起来了。 从问题求解的观点来看，抽象数据类型仅仅规定了数据类型应该具有的操作。问题求解的过程中，直接使用抽象数据类型提供的各种操作，也就是说，问题求解的工作是在一个更加抽象的层次上进行的。一旦抽象数据类型被实现（数据表示和各种操作的实现），问题也就迎刃而解了。 抽象数据类型的概念是面向对象方法的理论基础。,1.2.3 举例 adt 1.1 圆的抽象数据类型 adt circle is operations area 计算圆的面积 circumference 计算圆的周长 getradius 获取圆的半径 setradius 设置圆的半径 end adt circle,adt 1.2 集合的抽象数据类型 adt set is operations isempty 判断集合是否为是空集合 add 给集合增加一个元素 remove 删除集合中的一个元素 isin 判断一个元素是否在当前集合中 end adt set,adt,user1,user2,usern,.,实现1,实现2,实现3,1.3 数据结构 “结构”：把某些成分按一定的规律或方式组织在一起的实体。 1.3.1 什么是数据结构 数据结构（data structures): 通常是指计算机中表示的、具有一定逻辑关系和行为特征的一组数据。其中的每个数据元素称为这个结构的一个结点。,根据面向对象的观点，可以把数据结构理解为抽象数据类型的物理实现。这就需要解决两个问题： 一个是如何具体表示抽象数据类型中的数学模型；另一个是如何给出抽象数据类型中需要操作的具体实现。,对于数据结构的不同理解，实际上都离不开以下三个要素： 逻辑结构：它定义了数学模型中的基本元素和元素之间的相互关系。 存储结构：它给出了数学模型的具体表示方式，包括结点的表示和关系的表示。 操作：它给出抽象数据类型关心的各种行为在存储结构上的具体实现算法。,1.3.2 数据结构的分类 按逻辑结构分类 逻辑结构可以用一个二元组b=来表示，其中k是结点的有穷集合，r是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 算法的设计 算法是千变万化的。 设计一个好的算法需要设计者根据要解决的问题，充分发挥自己的分析和综合能力，经过认真构思、仔细设计和耐心调整。 在算法设计的过程中，最重要的是需要创新精神。（难点）,在实际应用中，许多算法的设计思想具有相似之处，我们可以对它们分类进行学习和研究。 常用的算法设计的方法有：,贪心法： 当追求的目标是一个问题的最优解时，设法把对整个问题的求解工作分成若干步骤来完成。在其中的每一个阶段选择从局部看是最优的方案，以期望通过各阶段的局部最优选择达到整体的最优。 算法1.1 采用的就是贪心法,数钱问题：一个出纳员要支付一定数量的现金款。假设他手中有各种面值的纸币和硬币，要求他用最少的货币数支付规定的现金款。 出纳员一般是按照货币单位从大到小的次序，数出需要支付的现金。 例如，现在他有5个1分，2个5分，2个1角，1个2角，要支付27分。 首先支付1个2角，然后是1个5分，最后是2个1分。这就是贪心算法。,贪心算法不一定总是能得到正确的答案。 例如，现在出纳员有5个1分，2个10分，1个15分硬币，要支付20分。 按贪心策略：得到1个15分，5个1分,分治法：,把一个规模较大的问题分成两个或多个较小的与原问题相似的子问题，首先对子问题进行求解，然后把各个子问题的解合并起来，得出整个问题的解，即对问题分而治之。,分治法： 二分法检索,对数据结构的要求：顺序有序表 查找方法： 先确定待查记录所在范围，然后逐步缩小范围，直到找到该记录，或查找区间缩小到0也没有查找到给定值的记录为止。 确定待查记录所在范围：用二分区间的方法。,用二分法查找 kval=19 的过程,确定查找范围：mid=(low+high)/2=6 kvalst.elemmid 查找范围在15 重新设置 high=mid-1,mid,mid,mid=(low+high)/2=3 kval=st.elemmid 查找成功,首先和记录所在区间111的中间位置记录的关键字56相比较，因为1956，表明关键字等于19的记录只能存在于15区域，所以，查找区间的上限可下移。,再次把待查找关键字与记录所在区间15的中间位置记录的关键字19相比较，因为1919，所以查找成功,回溯法 采用一步一步向前试探的方法，当某一步有多种选择时，可以先任意选择一种，只要这种选择暂时可行就继续向前试探，一旦发现到达某一步后无法再前进，说明前面的选择是错误的，这是就可以后退，回到上一步重新选择（称为回溯）。,四皇后问题。 设有一个4*4的棋盘，把4个棋子放到格子上，要求满足下列条件： （1）任意两个棋子不在同一行和同一列上； （2）任意两个棋子不在同一行对角线上。,得到一个解,动态规划法 与分治法相似，都是把一个大问题分解为若干较小的问题。不同的是，动态规划法分解的子问题比较多，而且子问题相互包含，为了重用已经计算的结果，要把计算的中间结果保存起来，动态规划法通常是自底向上进行。,动态规划：最短路径问题,a0,b1,a1,d2,c2,b2,a2,c3,b3,a3,c4,b4,a4,b5,a5,a6,5,5,5,5,3,3,3,3,3,3,3,1,1,6,6,6,6,6,3,8,8,7,8,4,2,2,2,2,3,4,要求选一条从a0到a6的最短线路。,4,3,7,5,9,7,6,8,13,10,9,12,13,16,18,分枝界限法 采用广度优先策略，在全部问题解的空间中进行系统搜索，与此同时，利用最优解属性的上下界来控制搜索的分枝，剪去不必再花时间搜索的部分，从而提高搜索的效率。,对于n=3时的0-1背包问题，假设w=16,15,15, p=45,25,25,c=30用分支限界法解：,对于n=3时的0-1背包问题，假设w=16,15,15, p=45,25,25,c=30用分支限界法解：,对于n=3时的0-1背包问题，假设w=16,15,15, p=45,25,25,c=30用分支限界法解：,对于n=3时的0-1背包问题，假设w=16,15,15, p=45,25,25,c=30用分支限界法解：,对于n=3时的0-1背包问题，假设w=16,15,15, p=45,25,25,c=30用分支限界法解：,45,对于n=3时的0-1背包问题，假设w=16,15,15, p=45,25,25,c=30用分支限界法解：,对于n=3时的0-1背包问题，假设w=16,15,15, p=45,25,25,c=30用分支限界法解：,45,对于n=3时的0-1背包问题，假设w=16,15,15, p=45,25,25,c=30用分支限界法解：,45,对于n=3时的0-1背包问题，假设w=16,15,15, p=45,25,25,c=30用分支限界法解：,45,45,50,25,对于n=3时的0-1背包问题，假设w=16,15,15, p=45,25,25,c=30用分支限界法解：,45,50,25,25,0,对于n=3时的0-1背包问题，假设w=16,15,15, p=45,25,25,c=30用分支限界法解：,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中。,为了节省空间，可以把排好序的数据仍然放到数组a中。只要把第一次选出的最大整数与a0交换，把第二次选出的最大整数与a1交换 第一步精化： （1）从a0到an-1中选出最大整数，设为aj，把a0与aj交换。 （2）从a1到an-1中选出最大整数，设为aj，把a1与aj交换。 （n）从an-1到an-1中选出最大整数，设为aj，把an-1与aj交换。,以上有规律的n次重复操作可以用一个循环来控制； 当第n-1次重复执行后，只剩下一个未排序的元素了，因此不必再执行第n次重复操作了。 第二次精化 i以1为步长，从0到n-2，循环执行： （1）从ai到an-1中选出最大的整数，设为aj。 （2）把ai与aj进行交换。 下面对（1）、（2）进行精化。,第三次精化 i以1为步长，从0到n-2，循环执行： （1）jaj，则j-k （3）t-ai; ai-aj; aj-t; 剩下的工作就是写程序了。,算法1.2 选择排序算法 void sortintarray(int a,int n)/教材错 int i,j,k; for(i=0;iaj) j=k; t=ai;ai=aj;aj=t; ,1.4.4 算法的分析 时间代价和空间代价,算法的空间代价(或称空间复杂性)：当被解决问题的规模(以某种单位计算)由1增至n时，解该问题的算法所需占用的空间也以某种单位由f(1) 增至f(n)，这时我们称该算法的空间代价是f(n)。,算法的时间代价(或称时间复杂性)：当问题规模以某种单位由1增至n时，对应算法所耗费的时间也以某种单位由g(1)增至g(n)，这时我们称算法的时间代价是g(n)。,三个值得注意的概念： 问题规模 空间单位：一般规定为一个简单变量(如整型、实型等)所占存储空间的大小； 时间单位：一般规定为执行一个简单语句(如赋值语句、判断语句等)所用时间。 例如，直接选择排序 主要运算： 比较运算 空间单位： 一个元素占存储空间s 时间单位： 一次比较所用时间t (n-1)+(n-2)+2+1=n*(n-1)/2,代价的表示和计算 在描述算法分析的结果时，人们通常采用“大o”表示法：说某个算法的时间代价(或者空间代价)为o(f(n)，则表示如果存在正的常数c和n0，当问题的规模nn0后，该算法的时间(或空间)代价t(n)cf(n)。这时也称该算法的时间(或空间)代价的增长率为f(n)。这种说法意味着：当n充分大时，该算法的复杂性不大于f(n)的一个常数倍。,常用的计算规则：,1. 加法规则 t(n) = t1(n)+ t2(n) = o(f1(n) + o(f2(n) = o(max(f1(n), f2(n),2. 乘法规则 t(n) = t1(n)t2(n) = o(f1(n) o(f2(n)= o(f1(n)f2(n),采用 “大o表示法”简化了时间和空间代价的度量，其基本思想是主要关注复杂性的量级：最坏情况下的代价(对同样规模的问题所花费的最大代价)、最好情况下的代价和平均情况下的代价等。,关心当n充分大时，函数t(n)=？ c log2n n n*log2n n2 n3 10n,cnn =ann bnn for(i=0; in; i+) for(j=0; jn; j+) cij=0; for(k=0;