从程序设计到算法设计

1、从程序设计到算法设计数据结构课程教学方法及在线教学平台应用的探讨武汉大学 李春葆2015年5月青岛清华大学出版社相关课程教学中的几点经验3ACM/IEEE-CS计算机科学课程体系20131从程序设计到算法设计的课程体系2数据结构课程教学方法及在线教学平台4内 容 提 要ACM/IEEE-CS计算机科学课程体系20131Curriculum 68CC 2001 CS 2008 CS 2013 中国计算机学会和全国高校计算机教育研究会也组成研究组：CCC2006AL Algorithms and Complexity AR Architecture and Organization CN Comp

2、utational Science DS Discrete Structures GV Graphics and Visual Computing HC Human-Computer Interaction IAS Information Assurance and SecurityIM Information Management IS Intelligent Systems NC Networking and CommunicationsOS Operating Systems PBD Platform-based DevelopmentPD Parallel and Distribute

3、d ComputingPL Programming Languages SDF Software Development Fundamentals SE Software Engineering SF System Fundamentals SP Social and Professional Issues18个知识领域1.1计算机科学分支学科的知识领域 It is naturally tempting to associate each Knowledge Area with a course. We explicitly discourage this practice in genera

4、l, even though many curricula will have some courses containing material from only one Knowledge Area or, conversely, all the material from one Knowledge Area in one course. We view the hierarchical structure of the Body of Knowledge as a useful way to group related information, not as a stricture f

5、or organizing material into courses. 很自然每一个知识领域都与一门课程相关联。一门课程可以包含一个知识领域的部分内容或全部内容。 但我们认为，将相关的信息组织成知识体层次结构是十分有用的，而不是狭窄地将内容组织进课程中。提示：计算机科学分支学科的知识单元PL Programming Languages PL/Object-Oriented Programming PL/Functional Programming PL/Event-Driven and Reactive Programming PL/Basic Type SystemsPL/Program

6、Representation PL/Language Translation and Execution PL/Syntax Analysis PL/Compiler Semantic Analysis PL/Code Generation PL/Runtime Systems PL/Static Analysis PL/Advanced Programming Constructs PL/Concurrency and Parallelism PL/Type Systems PL/Formal Semantics PL/Language Pragmatics PL/Logic Program

7、ming程序设计导论面向对象的程序设计高级语言程序设计1.2AL Algorithms and Complexity AL/Basic Analysis AL/Algorithmic Strategies AL/Fundamental Data Structures and Algorithms AL/Basic Automata, Computability and Complexity AL/Advanced Computational Complexity AL/Advanced Automata Theory and Computability AL/Advanced Data Str

8、uctures, Algorithms, and Analysis算法设计与分析数据结构知识领域的重要性1.3涵盖的学校类型社区大学学院教学型大学研究型大学1.4程序设计语言算法设计与分析数据结构从程序设计到算法设计的课程体系2进阶进阶程序设计数据结构算法设计与分析识字基本编程写作文以数据结构为中心的算法设计算法设计方法写文章通用算法设计算法设计方法学注重变量定义注重数据组织注重控制流程注重数据处理方法强调程序设计强调“好程序”的设计程序设计数据结构2.1数据结构和程序设计课程的侧重点掌握各种常用的数据结构掌握各种常用的求解策略数据结构算法设计与分析基于数据结构的算法设计，如栈、队列、二叉树和

9、图算法等。基于求解策略的算法设计，如贪心法、分治法、回溯法、动态规划和分枝限界法等。2.2数据结构和算法设计与分析课程的侧重点相关课程教学中的几点经验高级语言程序设计3数 据 结 构算法设计与分析3.13.23.3高级语言程序设计定义变量：使用内存（纸张）运算符：使用CPU（笔）程序（大脑）3.1.1 计算机语言工具化的理念3.112345678123456781234567812345678示例：机器人环境3.1.2 计算机语言提供的核心元素提供的指令Init(x,y)：初始位置Up：上移一个位置down：下移一个位置Left：左移一个位置Down：右移一个位置Over:是否超界End：结束

10、控制语句顺序语句：串行执行（冯诺依曼体系结构）条件语句：if/switch循环语句：while、do-while、for12345678123456781234567812345678为什么需要条件语句？Init(2,7);Right;Right;超界程序修改为：Init(2,7);if !Over Right;if !Over Right;End;条件语句12345678123456781234567812345678编程：从(2，2)移动到(7，6)Init(2,2);程序1Left;Left;Left;Left;Down;Down;Down;Down;Down;End;任务完成循环语句1

11、2345678123456781234567812345678Init(2,2);程序2for (i=1 To 4) Left;for (i=1 To 5 Down;End;任务完成为什么要使用循环语句？ 数学思路是人求解问题的过程，而程序设计思路是人指挥计算机求解问题的过程。前者是人求解问题的方式，后者是计算机求解问题的方式。 由于计算机的运行速度快，特别适合于求解简单重复的问题。所以将数学思路转换成设计程序思路时要充分利用这一特点，从问题求解中提炼出重复的步骤，用计算机语言中的循环语句加以实现。3.1.3 数学思路和程序设计思路的关系数学思维计算思维 示例：从5位同学中选派4位同学在星期五

12、、星期六、星期天参加公益活动，每人一天，要求星期五有2人参数，星期六、星期天各有1人参加，则不同的选派方法共有多少种？ 从5人中选派4位同学有 种，再从选出的4人中选2人星期五劳动有 种，其余2人在星期六、星期天劳动有 种，所以总共有 = 60种。数学思路求解：程序设计思路求解： 为了统计所有不同的选派的情况，用week数组统计每天安排参加公益活动的人数，week0表示星期五的人数、week1表示星期六的人数、week2表示星期天的人数，week3表示不参加公益活动的人数。week0week3的初始值均为0。 设5人分别安排公益活动的星期号为ae，显然，0ae3。当某人参加某星期号（编号i，0

13、i3，i=3时表示不参加任何公益活动）的公益活动时，weeki增1。void main() int week4=0; int a,b,c,d,e,count=0; for (a=0;a=3;a+) weeka+;for (b=0;b=3;b+) weekb+; for (c=0;c=3;c+) weekc+;for (d=0;d=3;d+) 满足条件 weekd+; for (e=0;enext)：小问题把“大问题”转化为若干个相似的“小问题”来求解。为什么在这里设计单链表的递归算法时不带头结点？L-next)求单链表中数据结点个数。f(L)f(L-next) a1a2.Lan设f(L)为单链

14、表中数据结点个数。 空单链表的数据结点个数为0f(L)=0 当L=NULL 对于非空单链表：=+ 1递归模型如下：f(L)=0当L=NULLf(L)=f(L-next)+1其他情况求单链表中数据结点个数递归算法如下：int count(Node *L) if (L=NULL) return 0; else return count(L-next)+1;递归模型如下：f(L)不做任何事件 当L=NULLf(L)输出L-data;f(L-next) 其他情况递归模型如下：f(L)不做任何事件 当L=NULLf(L)f(L-next);输出L-data 其他情况不带头结点单链表L正向显示所有结点值。

15、反向显示所有结点值。void traverse(Node *L) if (L=NULL) return; printf(%d ,L-data); traverse(L-next);递归算法void traverseR(Node *L) if (L=NULL) return; traverseR(L-next); printf(%d ,L-data);递归算法b-lchild根左子树右子树b-rchildbf(b) 大问题f(b-lchild)小问题1f(b-rchild)小问题2当f(b-lchild)和f(b-rchild)可解时，f(b)就很容易求解了。 二叉树算法设计示例： 假设二叉树采

16、用二叉链存储结构存储，试设计一个算法，计算一棵给定二叉树的所有叶子结点个数。设f(b)为二叉树b中叶子结点个数。 空二叉树中叶子结点个数为0f(b)=0 若b=NULLb 根为叶子结点时叶子个数为1f(b)=1 若*b为叶子结点f(b)=0若b=NULLf(b)=1若*b为叶子结点f(b)=f(b-lchild)+f(b-rchild)其他情况递归模型f(b)如下： 对于其他情况的二叉树bbb-lchildb-rchildf(b)=f(b-lchild)+ f(b-rchild)int LeafNodes(BTNode *b)int num1,num2; if (b=NULL) return

17、0; else if (b-lchild=NULL & b-rchild=NULL) return 1; else num1=LeafNodes(b-lchild);num2=LeafNodes(b-rchild);return (num1+num2); 递归算法如下：示例：假设二叉树采用二叉链存储结构存储，试设计一个算法，计算一棵给定二叉树的所有单分支结点个数。f(b)=0 若b=NULLf(b)=f(b-lchild)+f(b-rchild)+1 若*b为单分支结点f(b)=f(b-lchild)+f(b-rchild)其他情况设f(b)为二叉树b中单分支结点个数。递归模型f(b)如下：i

18、nt SSonNodes(BTNode *b)if (b=NULL)return 0; else if (b-lchild!=NULL & b-rchild=NULL |b-lchild=NULL & b-rchild!=NULL)/为单分支结点return SSonNodes(b-lchild)+ SSonNodes(b-rchild)+1; else /为双分支结点或叶子结点时 return SSonNodes(b-lchild)+ SSonNodes(b-rchild);递归算法如下： 图算法设计图算法深度优先遍历广度优先遍历示例：假设图G采用邻接表存储，设计一个算法，判断顶点u到v是否

19、有简单路径。 基于深度优先遍历算法的应用从顶点u开始进行深度优先搜索，当搜索到顶点v时表明从顶点u到顶点v有路径，即：用形参has（调用时其初值置为false）表示顶点uv是否有路径。uu1u2v深度优先搜索过程void ExistPath(AGraph *G,int u,int v,bool &has) /has表示u到v是否有路径,初值为false int w;ArcNode *p; visitedu=1;/置已访问标记 if (u=v)/找到了一条路径 has=true;/置has为true并结束算法 return; p=G-adjlistu.firstarc;/p指向顶点u的第一个相邻

20、点 while (p!=NULL) w=p-adjvex;/w为顶点u的相邻顶点 if (visitedw=0)/若w顶点未访问,递归访问它 ExistPath(G,w,v,has); p=p-nextarc; /p指向顶点u的下一个相邻点 深度优先搜索示例： 假设图G采用邻接表存储，设计一个算法输出图G中从顶点u到v的一条简单路径（假设图G中从顶点u到v至少有一条简单路径）。采用深度优先遍历的方法。为此在深度优先遍历算法的基础上增加path和d形参，其中path存放顶点u到v的路径，d表示path中的路径长度，其初值为-1。当从顶点u遍历到顶点v后，输出path并返回。DFS(G,u,v,p

21、ath,d)DFS(G,u1,v,path,d)DFS(G,um,v,path,d)um=v输出path并返回void FindaPath(AGraph *G,int u,int v,int path,int d)/d表示path中的路径长度，初始为-1 int w,i; ArcNode *p; visitedu=1; d+; pathd=u;/路径长度d增1，顶点u加入到路径中 if (u=v)/找到一条路径后输出并返回 printf(一条简单路径为:); for (i=0;iadjlistu.firstarc; /p指向顶点u的第一个相邻点 while (p!=NULL) w=p-adjv

22、ex;/相邻点的编号为w if (visitedw=0) FindaPath(G,w,v,path,d); p=p-nextarc; /p指向顶点u的下一个相邻点 深度优先搜索示例：假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到v的所有简单路径。 利用回溯的深度优先搜索方法。 从顶点u开始进行深度优先搜索，在搜索过程中，需要把当前的搜索线路记录下来。为此设立一个数组path保存走过的路径，用d记录走过的路径长度。若当前扫描到的顶点u等于v时，表示找到了一条路径，则输出路径path。DFS(G,u,v,path,d)回溯所有路径后结束um=v输出一条pathDFS(G,u1,v,pa

23、th,d)DFS(G,um,v,path,d)um=v输出一条pathDFS(G,um,v,path,d)置visitedum=0回溯置visitedum=0回溯visitedu1=0回溯void FindPath(AGraph *G,int u,int v,int path,int d)/d表示path中的路径长度，初始为-1int w,i;ArcNode *p;d+; pathd=u;/路径长度d增1，顶点u加入到路径中visitedu=1;/置已访问标记if (u=v & d=1)/找到一条路径则输出 for (i=0;iadjlistu.firstarc;/p指向顶点u的第一个相邻点

24、while (p!=NULL) w=p-adjvex;/w为顶点u的相邻顶点 if (visitedw=0)/若w顶点未访问,递归访问它 FindPath(G,w,v,path,d); p=p-nextarc;/p指向顶点u的下一个相邻点 visitedu=0;恢复环境,使该顶点可重新使用深度优先搜索从1到4的所有路径: 1 2 4 1 2 3 4 1 0 3 4 1 0 3 2 413240程序执行结果如下： 基于广度优先遍历算法的应用u一圈一圈向外走。BFS思路：u1v以u到v的最短路径构成分层示例：假设图G采用邻接表存储，设计一个算法，求不带权无向连通图G中从顶点u到顶点v的一条最短路径

25、（路径上经过的顶点数最少）。最好采用广度优先遍历来实现。typedef struct int data;/顶点编号 int parent;/前一个顶点的位置 QUERE;/非循环队列类型void ShortPath(ALGraph *G,int u,int v) /输出从顶点u到顶点v的最短逆路径 ArcNode *p; int w,i; QUERE quMAXV;/非循环队列 int front=-1,rear=-1;/队列的头、尾指针 int visitedMAXV; for (i=0;in;i+)/访问标记置初值0 visitedi=0; rear+;/顶点u进队 qurear.data

26、=u; qurear.parent=-1; visitedu=1; while (front!=rear)/队不空循环 front+;/出队顶点w w=qufront.data; if (w=v) /找到v时输出路径之逆并退出 i=front;/通过队列输出逆路径 while (qui.parent!=-1) printf(%2d ,qui.data); i=qui.parent; printf(%2dn,qui.data); break; p=G-adjlistw.firstarc; /找w的第一个邻接点while (p!=NULL) if (visitedp-adjvex=0) visit

27、edp-adjvex=1; rear+; /将w的未访问过的邻接点进队 qurear.data=p-adjvex; qurear.parent=front; p=p-nextarc;/找w的下一个邻接点 增加部分 两种遍历算法的差别1324001324以u到v的最短路径构成分层深度优先遍历可能找到的一条路径：1324001324路径：0 1 2 4路径上的顶点可能在同一层1234001324广度优先遍历找到的路径同一层只能有一个顶点。逆路径：4 3 0深度优先遍历能找所有路径，而广度优先遍历难以实现。广度优先遍历找到的路径是最短路径，而深度优先遍历不一定。结论：3.2.3 数据结构算法的多维性

28、同一问题的多种解法。迷宫问题用栈方法求解用队列方法求解用图搜索方法求解用递归方法求解示例:各种求解方法的特点和差别顺序查找算法二分查找算法利用了数据的有序性示例13.2.4 数据结构经典算法的启示串简单匹配算法串KMP匹配算法利用子串中部分匹配特性示例2简单选择排序算法堆选择排序算法利用了连续多次查找最大记录的特性示例3用Dijkstra求所有顶点之间的最短路径Floyd算法共享前面路径比较所得到的信息示例4找路径：AB膨胀所有物体。ABABAB机器人路径规划问题3.2.5 “小算法”解决“大问题”将路径搜索转换为图的顶点搜索。再可采用图遍历算法。 地图矢量化GIS求最短路径问题 图顶点搜索最

29、短路径算法设计设计存储结构问题描述ADT 逻辑结构抽象运算（功能描述）映射存储结构1存储结构n算法11算法1m算法n1算法nm运算实现最佳算法算法分析算法分析3.2.6 数据结构解决问题的思路基本算法策略穷举法（枚举法、暴力法或蛮力法）分治法贪心法动态规划回溯法分支限界法许多算法都可以采用递归实现算法设计与分析3.33.3.1 求解问题的算法策略 示例： TSP问题（Travelling Salesman Problem）又称为旅行推销员问题、货郎担问题。01235868585736798一个示意图01235657路径长度:23顶点0顶点0并通过所有顶点的路径：0123586858573679

30、8比较求出最短路径为： 02310路径1：01230：28路径2：01320：29路径3：02130：26路径4：02310：23路径5：03210：59路径6：03120：59时间复杂度为O(nn!) 穷举法求解TSP问题fk (i，V)假设从顶点s出发，最后回到出发点s的最短路径长度：出发顶点i经过的顶点集V顶点集V中顶点数fk (i，V)=g.edges(s，i)当V=，isMINfk-1(j,V-j)+g.edges(j,i)当V 动态规划求解TSP问题顶点0顶点0f0(3,)f0 (2,)f0 (3,)f0 (1,)f0 (2,)f0 (1,)36583685f1(2,3)f1 (3,2)f1 (1,3)f1 (3,1)f1 (1,2)f1 (2,1)441013431614f2(1,2,3)f2 2,1,3)f2 (3,1,2)172119f3(0,1,2,3)23求出最短路径为： 02310起点0时间复杂度为O(nn!) 设f(i,V)表示从顶点i出发经过V （它是一个顶点的集合）中各个顶点一次且仅一次，最后回到出发点s的最短路径长度。 回溯法求解TSP问题f(3,)2