《程序设计回顾》PPT课件.ppt

《《程序设计回顾》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《程序设计回顾》PPT课件.ppt（108页珍藏版）》请在三一办公上搜索。

1、软件体系结构 编程回顾,林荣恒北京邮电大学,北京邮电大学,主要内容,编程概述程序风格算法与数据结构小结,设计、调试和测试这里不再介绍,北京邮电大学,编程概述,程序编程Programming编程语言,北京邮电大学,程序,计算机的工作是由程序来控制的程序：程序是为解决某一问题而编写的语句序列。通俗的说，将解决一个实际问题的具体操作步骤用某种计算机语言描述出来，就形成了程序。语句序列：指令计算机可以识别的命令实际问题的具体操作步骤：算法求解问题的方法，是在有限的步骤内求解某一问题所使用的一组定义明确的规则，是计算机处理问题所需要的过程,北京邮电大学,高质量的程序所具备的条件,建立正确的数学模型和确定

2、有效的计算方法运行结果必须正确，且在精度和其它各方面均满足要求程序本身具有良好的结构，逻辑清晰，易读易懂程序运行时间尽可能短，同时尽可能合理地使用内存便于检查、修正、移植和维护,北京邮电大学,编程,编程(Programming)：就是编写程序，它是在对算法进行正确描述的基础上进行的，是用计算机语言（程序设计语言）实现算法的过程。算法转变程序的过程,北京邮电大学,编程的一般过程,对于简单问题，前三步可看作一步，即分析问题、设计算法。维护？,北京邮电大学,程序语言,机器语言由计算机硬件系统可以识别的二进制指令组成汇编语言将机器指令映射为一些可以被人读懂的助记符，如ADD、SUB等高级语言屏蔽了机器

3、的细节，提高了语言的抽象层次程序中可以采用具有一定含义的数据命名和容易理解的执行语句在书写程序时可以联系到程序所描述的具体事物面向过程面向对象,北京邮电大学,选择计算机语言的原则,根据自己所处理事务的特点来选择计算机语言符合现代程序设计的要求适合使用者的硬件和软件环境考虑软件执行效率考虑使用者的工作性质,北京邮电大学,高级程序语言学习要点,数据结构基本、复合变量类型声明方法操作符语句赋值、计算结构控制语句：条件、分支、循环过程调用语句功能块/操作函数、过程类中的方法或成员变量,北京邮电大学,高级程序语言学习要点(2),模块.c文件类类库或者库函数：该语言或者第三方提供的，不用自己编写的系统调用

4、输入输出：文件、键盘、网络随机数、String线程作用域Public、static、private、protected、friendly、extern异常处理,北京邮电大学,高级程序语言学习要点(3),可执行程序的构成和组织主程序、Main函数、Main类模块文件、类文件目录结构程序编辑、编译、链接和执行方法依赖于环境该语言有特色的地方可视化程序设计实质是去使用开发环境提供的可视化库函数或者类库,北京邮电大学,主要内容,编程概述程序风格算法与数据结构小结,北京邮电大学,程序风格,引言名字表达式和语句一致性和习惯用法函数宏神秘的数注释,北京邮电大学,程序风格,引言名字表达式和语句一致性和习惯用法

5、函数宏神秘的数注释,北京邮电大学,看看这个代码,typedef structdouble x,y,zvec;vec U,black,amb=.02,.02,.02;struct sphere vec cen,color;double rad,kd,ks,kt,kl,ir*s,*best,sph=0.,6.,.5,1.,1.,1.,.9,.05,.2,.85,0.,1.7,-1.,8.,-.5,1.,.5,.2,1.,.7,.3,0.,.05,1.2,1.,8.,-.5,.1,.8,.8,1.,.3,.7,0.,0.,1.2,3.,-6.,15.,1.,.8,1.,7.,0.,0.,0.,.6,

6、1.5,-3.,-3.,12.,.8,1.,1.,5.,0.,0.,0.,.5,1.5,;yx;double u,b,tmin,sqrt(),tan();double vdot(A,B)vec A,B;return A.x*B.x+A.y*B.y+A.z*B.z;vec vcomb(a,A,B)double a;vec A,B;B.x+=a*A.x;B.y+=a*A.y;B.z+=a*A.z;return B;vec vunit(A)vec A;return vcomb(1./sqrt(vdot(A,A),A,black);struct sphere*intersect(P,D)vec P,D

7、;best=0;tmin=1e30;s=sph+5;while(s-sph)b=vdot(D,U=vcomb(-1.,P,s-cen),u=b*b-vdot(U,U)+s-rad*s-rad,u=u0?sqrt(u):1e31,u=b-u1e-7?b-u:b+u,tmin=u=1e-7,你写的比它好多少？,北京邮电大学,想写出高质量的代码吗？,高质量代码的四个基本特性：正确性简单性可读性可测试性可读性（清晰性）是“易于维护、易于重构的程序”最有价值的特性采用好的程序设计风格进行编码是实现可读性的必要保障,北京邮电大学,为什么要有可读性？,编程首先是与人交流，其次才是与计算机交流，采用好的风格编

8、写出可读性好的代码，可以降低与人交流的复杂度：编程阅读代码的次数要比编写代码多得多，即使在开发的初期也是如此 维护代码的维护者会感激你使代码容易理解 将来的维护者很可能就是你自己，到时候你得尝试记起自己六个月以前在想什么 软件的首要技术使命是管理复杂度，许多编程实践背后的动机正是为了降低程序的复杂度,北京邮电大学,怎样提高可读性？,名字，最常见的有类名、子程序名、变量名；长度，比如类的长度、数据成员的数目、子程序的长度、子程序的参数数目、语句的嵌套层数；复杂度，包括表达式的复杂度、语句逻辑的复杂度等；格式，包括缩进、空格、注释等；耦合度，包括由于共享数据（含全局数据）导致的耦合、类之间耦合（继

9、承、组合、友元）、子程序之间的耦合等；,北京邮电大学,程序风格,引言名字表达式和语句一致性和习惯用法函数宏神秘的数注释,北京邮电大学,名字：名不正，则言不顺！,类名、子程序名、变量名等，用于标识相应的对象可以使用切合实际的命名约定，但一旦使用了，就一定要始终如一地坚持你的命名约定frontsize,frontSize,front_size,北京邮电大学,一些基本的命名规则,全局变量使用具有说明性的名字，作用范围越大，所携带的信息应该越多好名字：currentDate、todaysDate坏名字：X,y,d,cd,td,x,y,date局部变量可以使用短名字例如，如果循环只有寥寥数行，而且只是单

10、层循环，那么可以用i、j等 如果循环行数较多，或者有嵌套，则需要更长而且有意义的名字试比较：scoreteamIndexeventIndex 和 scoreij下标串化问题,北京邮电大学,一些基本的命名建议（续1）,研究发现，当变量名的平均长度在10到16个字符的时候，调试程序所需花费的气力是最小的。平均名字长度在8到20个字符的程序也几乎同样容易调试。太短的名字无法传达足够的信息 太长的名字很难写，同时也会使得程序的视觉结构变得模糊不清,北京邮电大学,一些基本的命名建议（续2）,保持一致性坏的命名：好的命名：,Class UserQueue int noOfItemsInQ,frontOfQ

11、ueue,queueCapacity;public int noOfUsersInQueue(),Class UserQueue int nUsers,front,capacity;public int getNoOfUsers(),北京邮电大学,一些基本的命名建议（续3）,函数采用动作性的名字：用动作性的动词，后面跟着名词如：比较：If(checkoctal(c)和 if(isoctal(c)要准确：名字不仅是个标记，它还携带着给读程序人的信息,now=date.getTime();putchar(n);,北京邮电大学,程序风格,引言名字表达式和语句一致性和习惯用法函数宏神秘的数注释,北京邮

12、电大学,表达式和语句,用缩行显示程序的结构Bad:Good:,For(n=0;n100;fieldn+=0;*i=0;return(n);,For(n=0;n100;n+)Fieldn=0;*i=0;return(n);,北京邮电大学,表达式和语句（续1）,使用表达式的自然形式BadGood,If(!(block_id=unblocks),If(block_id=actblks)|(block_id unblocks),北京邮电大学,表达式和语句（续2）,用加括号的方式排除二义性在混合使用相互无关的运算符时，多加几个括号没有坏处尤其是C语言即使不必要，加了括号也能把意图表现得更明白小窍门：使用

13、括号使得你不用去记那些操作符的优先级,北京邮电大学,表达式和语句（续3）,分解复杂的表达式Bad：Good,*x+=(*xp=(2*k(n-m)?ck+1:dk-);,If(2*k(n-m)*xp=cK+1;Else*xp=dk-;*x+=*xp;,北京邮电大学,表达式和语句（续4）,当心副作用Bad code：Good code：,stri+=stri+=;,Stri+=;Stri+=;,北京邮电大学,表达式和语句（续5）,使用空行将代码分为有机的各个部分,#include#include int main(int argc,char*argv)/*Set the input to no-e

14、cho,character-at-time*(cbreak)mode,*and remember the old mode in t0*/struct termios t0,t1;tcgetattr(0,北京邮电大学,表达式和语句（续6）,子程序、函数、方法的代码行数最好不要超过200行可读性不好新手可以先编长的，再进行分离。每一行只写一条语句,北京邮电大学,程序风格,引言名字表达式和语句一致性和习惯用法函数宏神秘的数注释,北京邮电大学,一致性和习惯用法,一致性带来更好的程序命名的一致性语句的一致性相同实现方法的一致性：如果相同的计算每次总是采用相同的方式，任何变化就预示着是经过了深思熟虑，要

15、求读程序的人注意其他的一致性：算法数据结构出错处理方式高层设计模式,北京邮电大学,一致性和习惯用法（续1）,使用一致的缩排和加括号的方法,if(month=FEB)if(year,if(month=FEB)if(year,Wrong code(else matches“if day 29”),Right code,北京邮电大学,一致性和习惯用法（续2）,为了一致性，使用习惯用法just“so-so”codeGood code,i=0;while(i=n-1)arrayi+=1.0;,for(i=0;in;i+)arrayi=1.0;,北京邮电大学,一致性和习惯用法（续3）,用else-if表达

16、多路选择just“so-so”code:Good code:,if(x vmid)low=mid+1;else return mid;,if(x vmid)low=mid+1;else return mid;,北京邮电大学,程序风格,引言名字表达式和语句一致性和习惯用法函数宏神秘的数注释,北京邮电大学,函数宏,避免函数宏函数宏的缺点远远超过它能带来的好处给宏的体和参数都加上括号Bad code：Good code:,#define square(x)x*x,#define square(x)(x)*(x),北京邮电大学,程序风格,引言名字表达式和语句一致性和习惯用法函数宏神秘的数注释,北京邮电

17、大学,神秘的数,神秘的数包括各种常数、数组的大小、字符位置、变换因子以及程序中出现的其他以文字形式写出的数值。给神秘的数起一个好名字MINROW、MINCOL、MAXROW、MAXCOL,北京邮电大学,神秘的数（续1）,把数定义为常数，不要定义为宏Const int MAXROW=24;Static final int MAXROW=24;使用字符形式的常数，不用整数Bad：if(c=65&c=A&c=Z)Good:if(issupper(c)Java：if(Character.isUpperCase(c),北京邮电大学,神秘的数（续2）,利用语言去计算对象的大小,char buf1024;f

18、gets(buf,sizeof(buf),stdin);,char buf=new char1024;For(int i=0;I buf.length;i+),北京邮电大学,程序风格,引言名字表达式和语句一致性和习惯用法函数宏神秘的数注释,北京邮电大学,注释,程序中的注释是程序员与日后的程序读者之间通信的重要手段。注释绝不是可有可无的。一些正规的程序文本中，注释行的数量占到整个源程序的13到12，甚至更多。注释分为序言性注释和功能性注释。,北京邮电大学,序言性注释,通常置于每个程序模块的开头部分，它应当给出程序的整体说明，对于理解程序本身具有引导作用。有些软件开发部门对序言性注释做了明确而严格

19、的规定，要求程序编制者逐项列出。有关项目包括：程序标题；有关本模块功能和目的的说明；主要算法；接口说明：包括调用形式，参数描述，子程序清单；有关数据描述：重要的变量及其用途，约束或限制条件，以及其它有关信息；模块位置：在哪一个源文件中，或隶属于哪一个软件包；开发简历：模块设计者，复审者，复审日期，修改日期及有关说明等。,北京邮电大学,功能型注释,功能性注释嵌在源程序体中，用以描述其后的语句或程序段是在做什么工作，或是执行了下面的语句会怎么样。而不要解释下面怎么做BadGood,/*Add Amount to Total*Total=amount+total,/*Add Monthly-Sale

20、s to Annual-Totol*Total=amount+total,北京邮电大学,基本建议,给类、方法、函数、全局数据加注释描述一段程序，而不是每一个语句Purpose of code,not every detail Tricks usedReasons for unusual coding 用缩进和空行，使程序与注释容易区别注释要正确，不要与代码矛盾不要注释差的代码，重写它,北京邮电大学,基本建议（续1）,不要大谈明显的东西,Zerocount+;/*Increment zero entry counter*/,While(c=getchar()!=EOF/*skip white s

21、pace,北京邮电大学,基本建议（续2）,澄清情况，不要添乱If it takes longer to read the comment than to read the code,dont add a comment!Bad：Good:,/*string comparison routine returns-1 if s1 is above s2*/In an ascending order list,0 if equal,1 if s1 below s2*/,/*strcmp:return 0 if s1s2,0 if equal*/,北京邮电大学,小结,程序必须是写给人看的，仅仅偶尔才在

22、机器上执行。好习惯很重要，因为程序员做的大部分事情都是无意识完成的 初涉编程时，就应端正态度来学，尽快培养良好的习惯甚至你在工作压力下写出的代码也会更好富于技巧(tricky)、聪明(clever)可算是代码的恶劣品质，编程不是为了炫耀自己的聪明程度，这样写程序简直是歪门邪道通过你自己的程序你想体现什么？,北京邮电大学,最后,请把修改你代码的人记在心上与人方便，与己方便,北京邮电大学,主要内容,编程概述程序风格算法与数据结构小结,北京邮电大学,算法与数据结构,数据结构概述算法概述实例小结,北京邮电大学,算法与数据结构,数据结构概述算法概述实例小结,北京邮电大学,基本概念,数据：在计算机科学中是

23、指所有能输入到计算机中并被计算机程序处理的符号的总称。数据是信息的载体数据是计算机程序加工的原料数据的含义极为广泛，且不断丰富数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。比如电话号码表中的每一行信息便是一个数据元素（它包含三个数据项）。此概念是相对的,北京邮电大学,基本概念（2）,数据结构：组成数据的元素之间的结构关系。线性结构、树型结构和图结构是数据结构中的几类常见的数据结构形式。如果数据中的元素之间没有关系，则构成集合，这也是一种结构。,北京邮电大学,基本概念（3）,数据结构的内容：逻辑结构：数据元素之间的逻辑关系线性结构：线性表、数组、栈、队列、串等非线性结

24、构：树、图等物理结构（存储结构）：数据元素及其关系在计算机存储器内的表示顺序存储结构、链式存储结构、索引存储结构、散列存储结构数据的运算：即对数据所施加的操作检索、插入、删除、更新、排序等,北京邮电大学,举例：分析如下电话号码表数据结构,1、逻辑结构,2、存储结构,3、数据的运算,分析：,排在其前(后)面且与其相邻的结点称为该结点的直接前趋(后继)结点,有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继，这就是该数据结构的逻辑结构,北京邮电大学,算法与数据结构,数据结构概述算法概述实例小结,北京邮电大学,定义,算法：是在有限步骤内求解某一问题所使用的一组定义明

25、确的规则。,北京邮电大学,算法的特征,输入：一个算法有零个或多个输入；确定性：算法的每一个步骤必须要确切地定义；有穷性：一个算法在执行有穷步之后必须结束；输出：算法有一个或多个输出；能行性：算法中有待执行的运算和操作必须是相当基本的（运算和操作能精确地执行）,北京邮电大学,算法的描述,北京邮电大学,算法设计的要求,1、正确性：算法应当满足具体问题的需求。“正确”一词的含义在通常的用法中有很大差别，大体可分为四个层次：程序不含语法错误。程序对几组输入数据能够得出满足规格说明要求的结果。程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果。程序对于一切合法的输入数据

26、都能产生满足规格说明要求的结果。,北京邮电大学,算法设计的要求（2）,2、可读性：可读性好有助于人对算法的理解。3、健壮性：当输入数据非法时，算法也能适当做出反应或进行处理，而不会产生莫名其妙的输出结果。4、效率与低存储量需求：效率指算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。,北京邮电大学,算法的评价,评价算法的标准：评价一个算法主要看这个算法所占用机器资源的多少，而这些资源中时间代价与空间代价是两个主要的方面，通常是以算法执行所需的机器时间和所占用的存储空间来判断一个算法的优劣。时间复杂度空间复杂度在算法时间与空间效率的两方面，着重分析时间效率，即算法的时间复杂度，因为

27、我们总是希望程序在较短的时间内给出我们所希望的输出。,北京邮电大学,典型算法,递归与分治动态规划贪心算法回朔法分支限界法概率算法,北京邮电大学,算法与数据结构,数据结构概述算法概述实例小结,北京邮电大学,实例,问题描述算法和数据结构分析C语言实现,北京邮电大学,实例,问题描述算法和数据结构分析C语言实现,北京邮电大学,问题描述,随机产生出一些可以读的英文文本随机字母?Xpdtqwt asfasg kfuwnh字母在英语里出现的权重？Idtefoae tcs trder从字典里随机选择词的方法？Polydactyl circumscribe,北京邮电大学,可能的解决思路,用任何一个现成的某种语言

28、的文本，可以构造出由本文本中的语言使用情况而形成的统计模型。通过该模型生成的随机文本将具有与原文本类似的统计性质词word之间的关系的统计模型,北京邮电大学,马尔可夫链算法,1、设置w1和w2为文本的前两个词2、输出W1和W23、循环：3.1.随机地选择出W3，它是文本中W1W2的后缀中的一个3.2.打印w33.3.把w1和w2分别换成w2和w33.4.重复循环,北京邮电大学,算法解释,原文本Show your flowcharts and conceal your tables and I will be mystified.Show your tables and your flowcha

29、rts will be obvious.(end),北京邮电大学,实例,问题描述算法和数据结构分析C语言实现,北京邮电大学,程序要做的事情,读入一段英文文本，利用马尔可夫链算法，基于文本中固定长度的短语的出现频率，产生一段新文本。前缀中词的个数是个参数如果选1？如果选3？英文适合选2本程序对词word的定义：任何实际位于空格之间的内容将标点符号界定在了词上,北京邮电大学,数据结构的选择,问题规模分析输入规模N=100 000性能秒级,北京邮电大学,数据结构的选择（2）,算法分析是否需要存储整个输入数据？需要是否需要存储整个输出数据？不需要前缀的所有后缀是否需要生成并进行存储？需要是否需要维护前

30、缀和后缀之间的关系？需要输入的顺序关系是否需要存储？不需要前缀的所有后缀的最佳生成时间是什么？输入的时候？输入和输出之间？输出的时候？,北京邮电大学,数据结构的选择（3）,对数据结构的要求能够较好表达前缀与后缀之间的关联指针？后缀是在读输入的过程中一个一个读入的，事先不知道个数链表？动态数组？能够很方便地找到某个前缀对应的后缀散列关键词：？把一个前缀和它所有可能的后缀的集合放在一起，称为一个状态,北京邮电大学,数据结构的选择（4）,初步确定数据结构每个状态由一个前缀和一个后缀链表组成所有这些信息存放在一个散列表中，以前缀作为关键码每个前缀是一个固定大小的词集合如果一个后缀在给定前缀下出现多于一

31、次，则每个出现都单独包含在有关链表里,北京邮电大学,最终的主数据结构,北京邮电大学,数据结构C语言定义,enum NPREF=2,/*number of prefix words*/NHASH=4093,/*size of state hash table array*/MAXGEN=10000/*maximum words generated*/;typedef struct State State;typedef struct Suffix Suffix;struct State/*prefix+suffix list*/char*prefNPREF;/*prefix words*/Suf

32、fix*suf;/*list of suffixes*/State*next;/*next in hash table*/;struct Suffix/*list of suffixes*/char*word;/*suffix*/Suffix*next;/*next in list of suffixes*/;State*statetabNHASH;/*hash table of states*/,北京邮电大学,程序的划分,基于算法，程序可分为两个部分输入构造表示所有短语（前缀和其所有可能后缀）的数据结构输出基于上述数据结构，生成随机的输出,北京邮电大学,主程序,1、输入读入输入文档，创建表达

33、了所有前缀及其相应后缀关系的主数据结构2、输出基于上述数据结构和马尔可夫算法，生成输出并打印。,北京邮电大学,输入模块,输入参数：输入的文本？输出：主数据结构以全局变量的形式输出，而不是以返回值的方式输出基本算法：依次读入文本的词，将其作为其NPREF个词组成的前缀的后缀加入主数据结构如果其前缀不包含在主数据结构中，其前缀需要加入。考虑：1、初始前缀应该是什么？随便找几个词？是由输入文本的前NPREF个词来组成吗？其它的？2、本模块怎么结束？,北京邮电大学,输出模块,输入：主数据结构（不是通过参数输入的）？输出：基于马尔可夫算法随机生成的可读的文本打印到标准输出，而不是通过返回参数输出基本算法

34、马尔可夫算法考虑：1、初始前缀应该是什么？随机选取NPREF个词？输入的前NPREF个词？其它？2、本模块怎么结束？,北京邮电大学,实例,问题描述算法和数据结构分析C语言实现,一个大体流程解释,北京邮电大学,北京邮电大学,主程序：Main函数,char NONWORD=n;/*cannot appear as real word*/*markov main:markov-chain random text generation*/int main(void)int i,nwords=MAXGEN;char*prefixNPREF;/*current input prefix*/FILE*str

35、eam;char filename60;/*set up initial prefix*/for(i=0;i NPREF;i+)prefixi=NONWORD;printf(Please input file name n);scanf(%s,filename);,北京邮电大学,主程序（2）,if(stream=fopen(filename,r)=NULL)printf(The file%s was not openedn,filename);return 1;/*Input Module*/build(prefix,stdin);build(prefix,stream);/*Add an e

36、nd flag*/add(prefix,NONWORD);/*Output Module*/generate(nwords);return 0;,北京邮电大学,输入模块：build函数,/*build:read input,build prefix table*/void build(char*prefixNPREF,FILE*f)char buf100,fmt10;/*create a format string;%s could overflow buf*/sprintf(fmt,%ds,sizeof(buf)-1);while(fscanf(f,fmt,buf)!=EOF)add(pre

37、fix,estrdup(buf);,北京邮电大学,Add函数,/*add:add word to suffix list,update prefix*/void add(char*prefixNPREF,char*suffix)State*sp;/*Search for the prefix,create if not found*/sp=lookup(prefix,1);addsuffix(sp,suffix);/*move the words down the prefix*/memmove(prefix,prefix+1,(NPREF-1)*sizeof(prefix0);prefixN

38、PREF-1=suffix;,北京邮电大学,lookup,State*lookup(char*prefixNPREF,int create)int i,h;State*sp;h=hash(prefix);for(sp=statetabh;sp!=NULL;sp=sp-next)for(i=0;i prefi)!=0)break;if(i=NPREF)/*found it*/return sp;,北京邮电大学,lookup(2),if(create)sp=(State*)emalloc(sizeof(State);for(i=0;i prefi=prefixi;sp-suf=NULL;sp-ne

39、xt=statetabh;statetabh=sp;return sp;,北京邮电大学,Hash 函数,/*hash:compute hash value for array of NPREF strings*/unsigned int hash(char*sNPREF)unsigned int h;unsigned char*p;int i;h=0;for(i=0;i NPREF;i+)for(p=(unsigned char*)si;*p!=0;p+)h=MULTIPLIER*h+*p;return h%NHASH;,北京邮电大学,Addsuffix 函数,/*addsuffix:add

40、to state.suffix must not change later*/void addsuffix(State*sp,char*suffix)Suffix*suf;suf=(Suffix*)emalloc(sizeof(Suffix);suf-word=suffix;suf-next=sp-suf;sp-suf=suf;,北京邮电大学,输出模块：generate函数,/*generate:produce output,one word per line*/void generate(int nwords)State*sp;Suffix*suf;char*prefixNPREF,*w;i

41、nt i,nmatch;for(i=0;i NPREF;i+)/*reset initial prefix*/prefixi=NONWORD;for(i=0;i nwords;i+)sp=lookup(prefix,0);if(sp=NULL)eprintf(internal error:lookup failed);,北京邮电大学,输出模块：generate,nmatch=0;for(suf=sp-suf;suf!=NULL;suf=suf-next)if(rand()%+nmatch=0)/*prob=1/nmatch*/w=suf-word;if(nmatch=0)eprintf(int

42、ernal error:no suffix%d%s,i,prefix0);if(strcmp(w,NONWORD)=0)break;printf(%sn,w);memmove(prefix,prefix+1,(NPREF-1)*sizeof(prefix0);prefixNPREF-1=w;,北京邮电大学,算法与数据结构,数据结构概述算法概述实例小结,北京邮电大学,小结,算法和数据结构的研究是计算机科学的基石程序算法+数据结构，设计算法与选择合适的数据结构是程序设计中相辅相成的两方面，缺一不可。数据结构的选择一直是程序设计中的重点、难点。正确地应用数据结构，往往能带来意想不到的效果。算法通常是

43、决定程序效率的关键，但一切算法最终都要在相应的数据结构上实现，许多算法的精髓就是在于选择了合适的数据结构作为基础。,北京邮电大学,小结（2）,我们不需要太担心，其实基本算法只有屈指可数的几个，几乎出现在每个程序中，而且被包含在程序库中，如：基本检索和排序但是递归分治等算法设计思想，还是要好好把握的基本的数据结构也不多。虽然有时需要更复杂的数据结构，但它们基本上都是从几个基本的东西中产生出来的,北京邮电大学,小结（3）,对于大部分程序员而言，所需要的是知道有哪些合适的、可用的算法和数据结构知道如何在各种可以替代的东西之中作出选择,北京邮电大学,小结（4）,选择算法的几个步骤参考可能的算法和数据结

44、构参考问题规模，如果不大，选择简单技术；如果数据可能增长，不再考虑不能对付大数据集合的东西如果有库或语言本身的特征可以使用，就应该使用；如果没有，先自己写或借用短的、简单的容易理解的实现。如果测试发现太慢，再改用更高级的技术。,北京邮电大学,小结（5）,实际上，在程序设计过程中，很难确定到底是先决定的算法还是先决定的数据结构有的时候，先决定数据结构有的时候，先决定算法更多的时候是在问题的分析过程中，这两方面慢慢地同时变得清晰起来只有通过大量的实践，才能够真正掌握算法和数据结构的精髓,北京邮电大学,主要内容,编程概述程序风格算法与数据结构小结,北京邮电大学,怎样学好编程？,多读源程序、多编写程序、多上机调试忌上课只听不记、忌“纸上谈兵”、忌课下不练习具体要求：上课有重点、有选择的记上机有准备：准备好课本、笔记、作业等养成Review 代码的好习惯上机实践独立完成遇到不会的尽量不要立刻向别人请教，如果实在解决不了的问题，可以先完成你会的，然后把一些特别的难点提炼出来，向高手请教问问题最好能带代码,北京邮电大学,切记,书看千遍不如做程序一遍，应该尽量尝试去写程序做程序千个不如做好程序一个 应该尽量完善你现在做的程序，而不要不断做新的程序，而每个程序都虎头蛇尾,