【最新】星火杯讲座ppt模版课件

星火小组组系列讲讲座 程序设计设计入门门 褚华华 西安电电子科技大学软软件所 n让我们先感受一段程序做为开始吧 n我怎样才能达到这种境界？ 我应该具有 n扎实的基础 数据结构、离散数学、编译原理 n丰富的想象力 不要拘泥于固定的思维方式 丰富的想象力是建立在丰富的知识的基础之上 n最简单的是最好的 相同的代码永远不要写两遍 学习程序设计的一般步骤 读抄改写读抄改写 认真认真读读仔细仔细抄抄随意随意改改经常经常写写 写好代码的十个秘诀 n1.集百家之长，归我所用 （Follow Basic Coding Style） n2.取个好名字 （Using Naming Conventions） n3.凌波微步，未必摔跤（ Evil goto？ Maybe Not） n4.先发制人，后发制于人 （Practice Defensive Coding） n5. 见招拆招，滴水不漏（ Handle The Error Cases: They Will Occur!） n6. 熟悉剑法刀术，所向无敌 （Learn WIN32 API Seriously） n7. 双手互搏，无坚不摧（ Test, but dont stop there） n8. 活用断言 （Use, dont abuse, assertions） n9. 草木皆兵，不可大意（ Avoid Assumptions） n10. 最高境界，无招胜有招 （Stop writing so much code） 写好代码的十个秘诀 n集百家之长，归我所用（Follow Basic Coding Style） 代码能够清晰地表达你的思路 代码应该具备自解释能力 代码的缩进和排版规范 所有的函数和变量应用他人容易理解的名字 减少单个函数的长度，控制在50-100行以内 多使用枚举和常量定义（不要从天上掉下一个 数字来） 写好代码的十个秘诀 n凌波微步，未必摔跤（Evil goto？ Maybe Not） goto的使用应该遵循原则，而不是全盘否定 不用写高深晦涩的语句，不要一味追求性能忽 视代码的可读性 模式并不总是正确的 写好代码的十个秘诀 n先发制人，后发制于人（Practice Defensive Coding） 尽量保持代码的简洁和简单 调用其他接口和函数时现对返回值进行检查 避免有符号/无符号、32位/16位、被零除等误 算情况 写好代码的十个秘诀 n见招拆招，滴水不漏（Handle The Error Cases: They Will Occur!） 通过异常处理机制来保证程序代码的健壮性 异常处理中一定要注意资源的释放 异常处理要关注日志的详细记录，便于后续 BUG分析 不要把后台编码或系统异常直接抛给用户 n熟悉剑法刀术，所向无敌（Learn WIN32 API Seriously） Win32 API是Windows平台编程的根本 对系统强大的类库的熟悉和整理将事半功倍 写好代码的十个秘诀 n双手互搏，无坚不摧（Test, but dont stop there） 如果你没有进行测试，你完成的代码将仅仅是 个半成品 尽可能多地对自己的代码进行测试 编码人员应该更专注于白盒测试和单元测试 要善于使用Junit、Nunit、PureCoverage、 Compuware、Ncover等测试工具 相互间的Review和走查是对代码可维护性的重 要测试手段 有特殊性能要求时需要对相关功能或模块单独 进行性能测试 写好代码的十个秘诀 n活用断言（Use, dont abuse, assertions） 断言可以很好的描述假设和不可能情况 断言对程序Debug很有用，可以尽早地发现程 序问题 n草木皆兵，不可大意（Avoid Assumptions） 考虑到用户使用的各种场景 不用假设用户会正确地输入数据，要做好各种 完整性和便捷的检验 程序中70%左右的代码是为了保证这种完整性 服务的，正常条件下的功能可能30%代码就实 现了 写好代码的十个秘诀 n最高境界，无招胜有招（Stop writing so much code） 不要一味地拷贝粘贴代码 编码过程注意重用，函数级组件级系统级 通过重构持续改进代码质量，改进自我逻辑思 维 程序设计的一般步骤 n第一步：透彻地分析和理解所要解决的问 题 n第二步：解决这个问题的主要步骤（解题 方法） n第三步：关键操作，以及操作之间的关系 （程序的逻辑结构） n第四步：把这些操作翻译成某种程序设计 语言的源代码（程序的实现） 程序设计的一般步骤 n第一步：透彻地分析和理解所要解决的问 题 n第二步：解决这个问题的主要步骤（解题 方法） n第三步：关键操作，以及操作之间的关系 （程序的逻辑结构） n第四步：把这些操作翻译成某种程序设计 语言的源代码（程序的实现） 在没有透彻地理解问题之前，一 定要抑制住写代码的冲动！ 从理论论走向实实践 练习练习一： 年级级学生成绩绩管理系统统 基本要求 n按照教师，学生，管理员三种角色设计系统功能； n班级管理功能（管理员）：班级的添加，修改，删除 班级功能； n学生管理功能（管理员）：登记，修改，删除某班某 个学生的基本信息，可以一次导入某班全部学生信息 ； n成绩管理功能（老师）：登记，修改某个学生某门课 成绩，可以一次导入某班全部学生成绩。 n成绩查询功能（全部用户）：每个学生可以查询自己 所有课程的成绩。教师可以查询所带班级的成绩，可 以对成绩进行排序和统计。管理员可以查询全年级所 有学生所有课程的成绩并进行排序和统计，所有人都 可以浏览各个班级的公共信息。 基本需求 主要功能 n登记各班的学生基本情况 n插入某班某个学生的基本情况 n修改各班学生基本情况 n删除学生基本情况 n登记各班所有学生各门课的成绩 n修改某个学生某门功课的成绩 n浏览各班信息 n查找，浏览每个学生的基本信息 n查找，浏览每个学生的成绩信息 n成绩的排序和统计 n 学生/班级管理 权限：管理员 成绩管理 权限：教师 成绩查询 权限：所有用户 关键数据 n年级 年级编号、班级数 n班级 班级编号、教室、人数 n学生 学号、班级、姓名、性别、年龄、电话 n课程 课程编号、名称、学分、学时、开课学期、开课类型（ 必、限、任） n课程成绩 学号、课程编号、平时成绩、考试成绩、最终成绩 n用户权限（三种角色：教师、学生、管理员） 用户名、密码、权限 关键数据 n设计的重点：数据之间的关系 实现提示 n从简单到复杂，从部分到全面 可以逐个功能实现 先给出一个简单的实现，然后再逐渐补充完整 l尽量将数据（学生信息、课程信息、课程 成绩等）放在文件中 l考虑异常情况下的处理 n扩展 把数据放在数据库（例如Access）中 从理论论走向实实践 练习练习二： 航空客运订订票系统统 基本需求 n航班信息修改 n航班信息查询 多种查询方式：航班号、起点、终点、起飞时 间、到达时间等 起点与终点间存在多条航线时，要求输出费用 最小的航线（直航以及需要中转的航线） lDijkstra算法（单源点最短路径） n订票 n退票 图论基础知识 n图的定义 n图的存储结构 n图的应用 遍历：广度优先遍历、深度优先遍历 图的连通性：最小生成树（Prim算法、克鲁 斯卡尔算法） 拓扑排序 关键路径（AOV网） 最短路径 图的定义 n图G = (V, E)，其中 V是顶点集合； E是V中顶点偶对的有穷集，这些顶点偶对被 称为边或弧； V(G)：顶点集合 E(G)：边集合 图的存储结构 n邻接矩阵（数组表示） n邻接表（链表表示） n十字链表 n邻接多重表 n边表 邻接矩阵 n基本思想 对于有n个顶点的图，用一维数组vexsn存储 顶点信息，用二维数组Ann存储顶点之间 关系的信息。该二维数组称为邻接矩阵。 在邻接矩阵中，以顶点在vexs数组中的下标代 表顶点，邻接矩阵中的元素Aij存放的是顶 点i到顶点j之间关系的信息。 邻接矩阵 vexs a b c d e a a 0 1 1 0 0 b 1 0 1 1 1 c 1 1 0 1 0 d 0 1 1 0 1 e 0 1 0 1 0 b cde 无向图顶点表 邻接矩阵 vexs a b c d e a a 6 2 b 3 c 3 1 d 4 5 e bcde 有向带权图顶点表 邻接矩阵 ab cd e 3 5 4 1 2 6 3 ab cd e 邻接矩阵 n存储结构 #define MAX 100 struct vertex int num; / 顶点编号 char data; / 顶点信息 ; struct Graph vertex vexMAXMAX; / 顶点集合 int edgesMAXMAX; / 边 ; 邻接链表 n基本思想： 对图的每个顶点建立一个单链表，存储该顶点 所有邻接顶点及其相关信息。 第i个单链表表示依附于顶点Vi的边（对有向 图是以顶点Vi为头或尾的弧）。 邻接链表 n链表中的结点称为表结点，每个结点由三 个域组成， 邻接点域adjvex：指示与顶点Vi邻接的顶点在 图中的位置（顶点编号） 链域nextarc：指向下一个与顶点Vi邻接的表 结点 数据域info：存储和边或弧相关的信息，如权 值等。 adjvex info nextarc 表结点： 邻接链表 n每个链表设一个表头结点（称为顶点结点 ）： 链域firstarc：指向链表中的第一个结点 数据域data：存储顶点名或其他信息。 data firstarc顶点结点： 邻接链表 v1 v2v3 v4 v5 0 MAX_VEX-1 v1 v2 v3 v4 v5 2 1 3 0 2 0 3 1 4 2 0 4 2 3 1 2 3 4 邻接链表 n存储结构 #define MAX_VEX 30 /* 最大顶点数 */ typedef int InfoType; typedef struct LinkNode int adjvex ; / 邻接点在头结点数组中的位置(下标) InfoType info ; / 与边或弧相关的信息, 如权值 struct LinkNode *nextarc ; / 指向下一个表结点 LinkNode ; /* 表结点类型定义 */ typedef struct VexNode VexType data; / 顶点信息 int indegree ; / 顶点的度, 有向图是入度或出度或没有 LinkNode *firstarc ; / 指向第一个表结点 VexNode ; /* 顶点结点类型定义 */ 邻接链表 n存储结构 typedef struct ArcType VexType vex1, vex2 ; /* 弧或边所依附的两个顶点 */ InfoType info ; / 与边或弧相关的信息, 如权值 ArcType ; /* 弧或边的结构定义 */ typedef struct int vexnum ; VexNode AdjListMAX_VEX ; ALGraph ; /* 图的结构定义 */ 最短路径 n问题： 两地之间是否有通路？ 若存在多条通路，哪条路最短？ n两点之间的最短路径问题 单源点最短路径：求从某个源点到其余各点的 最短路径（ Dijkstra算法） 每一对顶点之间的最短路径（Floyd算法） 单源点最短路径 n给定带权有向图G = (V，E)及源点Vs，求 Vs到G的其余各顶点的最短路径。 nDijkstra提出了一种按路径长度递增的次 序产生最短路径的算法，即Dijkstra算法 。 AE B C D 100 50 20 5 60 30 10 F 10 起点终点最短路径路径长度 AB无 C(A,C)10 D(A,E,D)50 E(A,E)30 F(A,E,D,F)60 Dijkstra算法 n设给定源点为Vs，S为已求得最短路径的 终点集，开始时令S = Vs 。当求得第一 条最短路径(Vs ,Vi)后，S为Vs,Vi 。 n求下一条最短路径：设下一条最短路径终 点为Vj ，则Vj只有： 源点到终点有直接的弧； 从Vs 出发到Vj 的这条最短路径所经过的所有 中间顶点必定在S中。 Dijkstra算法 n定义一个数组distn disti表示当前所找到的从Vs出发到Vi的最短 路径的长度 下一条最短路径的终点Vj必定是不在S中且值 最小的顶点，即： distj = Min disti| ViV - S 利用上述公式就可以依次找出下一条最 短路径。 Dijkstra算法的步骤 令S = Vs ，用带权的邻接矩阵表示有向 图，对图中每个顶点Vi按以下原则置初值 ： Wsi i s且E， wsi为弧上的权值 i s且不属于E disti= 0 i = s 单源点最短路径 选择一个顶点Vj ，使得： distj=Min disti| ViV-S Vj就是求得的下一条最短路径的终点，将Vj 并 入到S中，即S = SVj 。 对V-S中的每个顶点Vk ，修改distk，方 法是： 若distj+Wjk vexnum; j+) prej = v ; finalj = FALSE ; distj = G-adjvj ; /* 各数组的初始化 */ distv = 0; finalv = TRUE ; /* 设置S=v */ for ( j = 0; j vexnum-1; j+) /* 其余n-1个顶点 */ m = 0 ; while (finalm) m+; /*