《程序设计方法》word版.doc

程序设计方法一、计算机硬件环境对软件设计方法的限制计算机的发明到现在已经60年了，计算机程序设计方法也伴随着计算机硬件技术的提高而不断发展。硬件环境对软件设计既有严重的制约作用，也有积极的推动作用。在我的大学母校(此处删除6个字)，数学系的一些老师，有幸成为了我国第一代的计算机DIY一族。呵呵，不要以为是组装PC机呦，他们组装的可是小型机。一人多高铁皮柜大小的主机，加上纸带机(后期改进为读卡机)，组装好后，除了供学校自己的科研使用外，还在全国各地销售了十几台。当时(七十年代)一台的售价是10几万元人民币，如果换算到今天，相当于价值大约为100多万元，非常高档的小型计算机了。下面大家猜猜，这么高档的计算机，它的内存是多少那?(都把嘴闭好了，我要公布答案了)-4K。一块50公分见方的内存板，插入到主机箱中，好了-1K；再插一块内存板，好了-2K；再插一块内存板，好了-3K；再插一块内存板，好了-4K；再.不行了，插不起了，太贵了！这就是当时的环境。这样的环境下，用什么写程序那?当然只有机器码了。先用汇编写，然后翻阅手册手工改写为机器码，然后打卡或穿纸带，输入运行。可以想象，在当时的条件下，什么叫好的程序那?什么叫优秀的程序那?-技巧！程序设计的最初始阶段，是讲究技巧的年代。如何能节省一个字节，如何能提高程序运行的效率，这些都是要严肃考虑的问题。而所谓的程序的易读性，程序的可维护性根本不在考虑范围之内。今天，35岁以上的学习过计算机的朋友可能都使用过一种个人计算机-APPLE-II(中国也生产过这种计算机的类似产品中华学习机)。主频1M，内存48K(扩展后，最多可达到64K)。我就是使用这样的计算机长大的：)。当年，类似的个人计算机产品，还有PC1500，Layser310等。这种计算机上已经固化了BASIC语言，当然只是为学习使用。要想开发出真正的商业程序，则必须使用汇编，否则的话，程序就比蜗牛还要慢了。于是，程序设计中对于技巧的运用，是至关重要的了。题外话1：比尔盖茨是BASIC的忠实拥护和推动者。当年，他在没有调式环境的状况下，用汇编语言写出了一款仅有4K大小的BASIC解释器，且一次通过。确实另人佩服。(不象现在微软出品的程序，动辄几十兆。)这也许就是比尔对BASIC情有独钟的原因，每当微软推出(临摹)一个新技术，则他会立刻在BASIC中提供支持。题外话2：在APPLE-II上有一款游戏软件警察抓小偷，当年熬夜玩游戏，乐趣无穷。后来这款游戏被移植到了PC上，咳根本没有办法玩，因为小偷还没跑就被警察抓到了。硬件的速度提升，令我无法再回味以前的时光了。二、结构化程序设计随着计算机的价格不断下降，硬件环境不断改善，运行速度不断提升。程序越写越大，功能越来越强，讲究技巧的程序设计方法已经不能适应需求了。记得是哪本书上讲过，一个软件的开发成本是由：程序设计30%和程序维护70%构成。这是书上给出的一个理论值，但实际上，从我十几年的工作经验中，我得到的体会是：程序设计占10%，而维护要占90%。也许我说的还是太保守了，维护的成本还应该再提高。下面这个程序，提供了两种设计方案，大家看看哪个更好一些那?题目：对一个数组中的100个元素，从小到大排序并显示输出。(BASIC)方法1：冒泡法排序，同时输出。FOR I=1 TO 100 FOR J=I+1 TO 100 IF AIAJTHEN T=AJ：AJ=AI：AI=T NEXT J?AINEXT I方法2：冒泡法排序，然后再输出。FOR I=1 TO 100 FOR J=I+1 TO 100 IF AIAJTHEN T=AJ：AJ=AI：AI=T NEXT NEXT FOR I=1 TO 100?AINEXT显然，方法1比方法2的效率要高，运行的更快。但是，从现在的程序设计角度来看，方法2更高级。原因很简单：(1)功能模块分割清晰-易读；(2)也是最重要的-易维护。程序在设计阶段的时候，就要考虑以后的维护问题。比如现在是实现了在屏幕上的输出，也许将来某一天，你要修改程序，输出到打印机上、输出到绘图仪上；也许将来某一天，你学习了一个新的高级的排序方法，由冒泡法改进为快速排序、堆排序。那么在方法2的基础上进行修改，是不是就更简单了，更容易了?！这种把功能模块分离的程序设计方法，就叫结构化程序设计。三、对程序设计中技巧使用的思考我几乎可以肯定，大家在开始学习程序设计的时候，绝大多数都做过这样一个题目：求100以内的素数。老师在黑板上，眉飞色舞地写出了第一个程序：(C程序)方法1：for(i=1；i 100；i+)for(j=2；j i；j+)if(i%j=0)break；if(j=i)printf(%d,i)；然后，老师开始批判这个程序这个叫什么呀?太慢了！因为我们都知道大偶数不可能是素数了，因此，要排除掉！于是，意尤未尽地写出了第二个程序：方法2：printf(2,)；for(i=3；i 100；i+=2)for(j=2；j i；j+)if(i%j=0)break；if(j=i)printf(%d,i)；老师说：看！我们只改动了一点点，程序运行的速度就提高了一倍多。然后运用诱导式教学法继续提问程序的效率，还能再提高吗?能！，得意地写出第三个程序：方法3：printf(2,)；for(i=3；i 100；i+=2)不考虑大偶数for(j=3；j i/2；j+=2)不考虑用偶数去测试，而且只验算到一半就足够了if(i%j=0)break；if(j=i)printf(%d,i)；大家看，我们又只改动了一点点，运行速度又提高了一倍多。可以了吗?不可以！我们还能再提高。于是又高傲地写出了第四个程序：方法4：printf(2,)；for(i=3；i 100；i+=2)int k=sqrt(i)；for(j=3；j=k；j+=2)if(i%j=0)break；if(j=k)printf(%d,i)；然后，开始证明为什么我们判断素数的时候，只需要验算到平方根就足够了：假设p是合数，那么令：p=a*b。反正法：由于我们已经判断了p的平方根以内的整数都不能被p整除，于是a SQRT(p)。基于同样的理由b SQRT(p)。于是p=a*b SQRT(p)*SQRT(p)=p得出矛盾，命题得正。的确，方法4的确比方法1的运行速度要提高了好几倍，甚至好几十倍。但我们仔细分析测试看看。(1)程序4到底比程序1快了多少那?我在某台计算机上进行测试(P4，1.5G)得到的速度对比表：计算范围100100010000100000速度差0.00秒0.01秒0.18秒15秒(2)在10万以上，才会看出一些差别。而这种差别根本就不够底偿程序设计阶段的付出。如果计算的范围再大，那么不管是方法1，还是方法4都不是好的算法。(计算素数的另外一个比较优秀的算法叫漏筛法)(3)写出方法1，只要具有小学四年级的数学水平就够了，而方法4则需要初中三年级的水平并且还要具备一些数论的知识。(4)从维护性看，如果你写的程序需要另外一个程序员来维护，或者若干时间以后，你重新来阅读这段程序，那么就会对这个程序产生很多疑问：这个求平方根是干什么用的?其实，就这个题目来说，使用到方法3就已经足够了。总结发言：I.计算机的价格每年下降一半，而运算速度每年提高一倍，因此我们应该把速度提高的任务交给硬件实现。II.从易读性、维护性出发，程序员只负责按定义给出软件实现。算法的问题是数学家解决的。题外话：多年以来，人们一直在寻找动态图象(影视)的存储和回放的算法，但效果都不理想。直到有人发现，原来在200多年前的数学家早就帮我们解决了这个问题-傅立叶(Fourier)级数展开。因此我要说，优秀的算法不是我们程序员要考虑的问题，我们的任务只要按照数学家给出的算法翻译为计算机程序语言而已。(这句话恐怕要遭到大多数程序员抛出的板砖袭击)再比如，计算一元多次方程解的问题。我们使用的就是牛顿的迭代算法。不要怪我瞧不起你，你能发明这个方法的话，那就是当代的牛顿了。四、程序的易读性与书写方法程序是否容易阅读和维护，与怎么书写有很大的关系。说实在的，C语言中为了方便程序员书写，允许使用+,-,&，?.这些运算符号。但很多人经常乱用，以为自己写的程序多么简洁，效率多高。其实，当你分行书写的话则更加容易阅读和维护，效率也不会降低，因为编译程序早就帮你优化为最快捷的代码了。先看一个简单的例子：计算一个整数乘255(C语言)方法1：a*=255；方法2：因为移位运算比乘法运算要快很多倍，因此a*255的运算书写为：a=(a 8)-a；/a*255=a*256-a=(a 8)-a方法1的书写非常简单，直截了当，显然更容易维护。而方法2的书写运用了移位的技巧，不容易阅读，但效率最高。是不是真的是这样那?把这两个程序编译为汇编代码看看。原来无论是方法1还是方法2，它们的汇编代码都是一样的：mov ecx,eax shl eax,8 sub eax,ecx也就是说，你认为非常技巧的书写方法，其实编译器的优化功能早就帮你想到了。那么方法2的方式就很值得批判了。下面是几个有关C语言书写方面的重要原则：尽量表达愿义，多加注释；变量名称和函数名称，要使用有意义的符号，并且遵守匈牙利命名法；不要为俭省内存，使一个变量在一个模块中表达多个含义。在某个模块中，前半部分用i表示计数器，由于后半部分不再使用计数器了，于是又用i来保存某个中间的结果。等你维护这段程序的时候，保证你肯定会犯傻的。在使用条件表达式的时候，不要混合书写运算表达式；经常有人在书写for循环的时候，使用这样的方式：for(int a=1,s=0；a=100&(s+=a)；a+)；天呀，这样写是不会提高程序运行效率的，尤其是当运算表达式复杂的时候，就更不容易阅读了，还是把运算写到for的循环体中吧。int s=0；for(int a=1；a=100；a+)s+=a；/计算1+2+.+100这不很好吗?！再比如，if(a=b)这个写法在语法上是允许的，但不要使用。要使用也要if(0！=(a=b)这样的方式。还有值得一提的是慎用,(逗号运算符)。不要连续使用+,-,，*，&.这样的运算符号。a=b+-(-c 1+e&0x0f 1)；/这个人有病。出这个题目考试的老师，也有病。常量要写在条件表达式的左边；if(5=a)这是正确的写法，这样书写可以避免误输入而导致的if(a=5)这样的错误。避免程序中的嵌套层次太深；最多4层。如果必须大于4层，那么写成调用子函数或宏的方式。尽量多地使用断言；当你在书写程序的过程中，凭你的智慧，你一定是知道：程序运行到我正书写的这行代码的时候某个变量一定是某个值。好啦，那么不要忧郁，马上加上一句代码：ASSERT(nnn=xxx)；。将来在调式维护这段代码的时候，你会得到无限美妙的回报。书写需要成对匹配使用的代码的时候，在写使用代码之前，就先把结束写出来；file.Open(.)；/当要打开文件的时候char*lp=new char100；/当要申请内存的时候./先不要写这段代码./先不要写这段代码file.Close()；/马上写关闭delete lp；/马上写释放xxx.Loack()；/当某个对象需要锁定的时候for(.)./先不要写这段代码/写大括号的时候xxx.Unlock()；/马上写解锁/马上写大括号结束和这个道理相同，在C+的类中，如果需要申请内存，那么先在构造函数中给出lp=NULL；然后马上在析构函数中书写if(lp)delete lp；可以适当地使用goto；在结构化程序设计中，goto是被排斥的。但是，如果适当地使用goto不但不影响斜率，而且还能提高程序的可读性。题目：合并2个文件到一个新文件中。(不要挑我的毛病呀，我使用的是类C的方式书写的。)方法1：FILE*f1,*f2,*f3；if(Open(f1)成功)if(Open(f2)成功)if(Open(f3)成功)./这里是真正干活的地方Close(f1)；Close(f2)；Close(f3)；else/f3不成功Close(f1)；Close(f2)；.else/f2不成功Close(f1)；.else/f1不成功.=方法2：FILE*f1=NULL,*f2=NULL,*f3=NULL；if(Open(f1)不成功)goto err；if(Open(f2)不成功)goto err；if(Open(f3)不成功)goto err；./这里是真正干活的地方err：if(f3)Close(f3)；if(f2)Close(f2)；if(f1)Close(f1)；方法1是最最标准的结构化设计，好吗?不好！尤其是当的层次比较深的时候，估计你寻找真正干活的代码的地方都找不到。而使用方法2的程序，不但程序容易读，而且没有的深度。在C+中，又提供了异常try/catch的设计结构，而异常的结构则比goto的结构更好、更完善了。五、面向对象的程序设计随着程序的设计的复杂性增加，结构化程序设计方法又不够用了。不够用的根本原因是代码重用的时候不方便。面向对象的方法诞生了，它通过继承来实现比较完善的代码重用功能。很多学生在应聘工作，面试的时候，常被问及一个问题你来谈谈什么是面向对象的程序设计，学生无言，回来问我，这个问题应该怎么回答。我告诉他，你只要说一句话就够了面向对象程序设计是对数据的封装；范式(模板)的程序设计是对算法的封装。后来再有学生遇到了这个问题，只简单的一句对答，对方就对这个学生就刮目相看了(学生后来自豪地告诉我的)。为什么那?因为只有经过彻底的体会和实践才能提炼出这个精华。面向对象的设计方法和思想，其实早在70年代初就已经被提出来了。其目的就是：强制程序必须通过函数的方式来操纵数据。这样实现了数据的封装，就避免了以前设计方法中的，任何代码都可以随便操作数据而因起的BUG，而查找修改这个BUG是非常困难的。那么你可以说，即使我不使用面向对象，当我想访问某个数据的时候，我就通过调用函数访问不就可以了吗?是的，的确可以，但并不是强制的。人都有惰性，当我想对i加1的时候，干吗非要调用函数呀?算了，直接i+多省事呀。呵呵，正式由于这个懒惰，当程序出BUG的时候，可就不好捉啦。而面向对象是强制性的，从编译阶段就解决了你懒惰的问题。巧合的是，面向对象的思想，其实和我们的日常生活中处理问题是吻合的。举例来说，我打算丢掉一个茶杯，怎么扔那?太简单了，拿起茶杯，走到垃圾桶，扔！注意分析这个过程，我们是先选一个对象-茶杯，然后向这个对象施加一个动作-扔。每个对象所能施加在它上面的动作是有一定限制的：茶杯，可以被扔，可以被砸，可以用来喝水，可以敲它发出声音.；一张纸，可以被写字，可以撕，可以烧.。也就是说，一旦确定了一个对象，则方法也就跟着确定了。我们的日常生活就是如此。但是，大家回想一下我们程序设计和对计算机的操作，却不是这样的。拿DOS的操作来说，我要删除一个文件，方法是在DOS提示符下：c：del文件名回车。注意看这个过程，动作在前(del)，对象在后(文件名),和面向对象的方法正好顺序相反。那么只是一个顺序的问题，会带来什么影响那?呵呵，大家一定看到过这个现象：File not found.啊，我错了，我错了，文件名敲错了一个字母，于是重新输入：c：del文件名2回车。不幸又发生了，计算机报告：File read only.哈哈，痛苦吧：)。所以DOS的操作其实是违反我们日常生活中的习惯的(当然，以前谁也没有提出过异议)，而现在由于使用了面向对象的设计，那么这些问题，就在编译的时候解决了，而不是在运行的时候。obj.fun()，对于这条语句，无论是对象，还是函数，如果你输入有问题，那么都会在编译的时候报告出来，方便你修改，而不是在执行的时候出错，害的你到处去捉虫子。同时，面向对象又能解决代码重用的问题-继承。我以前写了一个狗的类，属性有(变量)：有毛、4条腿、有翘着的尾巴(耷拉着尾巴的那是狼)、鼻子很灵敏、喜欢吃肉骨头.方法有(函数)：能跑、能闻、汪汪叫.如果它去抓耗子，人家叫它多管闲事。好了，狗这个类写好了。但在我实际的生活中，我家养的这条狗和我以前写的这个狗类非常相似，只有一点点的不同，就是我的这条狗，它是：卷毛而且长长的，鼻子小，嘴小.。于是，我派生一个新的类型，叫哈巴狗类在狗类的基础上，加上新的特性。好了，程序写完了，并且是重用了以前的正确的代码-这就是面向对象程序设计的好处。我的成功只是站在了巨人的肩膀上。当然，如果你使用VC的话，重用最多的代码就是MFC的类库。六、组件(COM)程序设计有了面向对象程序设计方法，就彻底解决了代码重用的问题了吗?答案是：否！硬件越来越快，越来越小了，软件的规模却也越来越大了，集体合作越来越重要，代码重用又出现的新的问题。我用C+写的类，不能被BASIC重用-不能跨语言；你要干什么，想重用我的代码?不行，这样你就看见了我的设计思想-只能在源程序级别重用，不能在二进制级别(可执行代码及)重用；我耗尽毕生的精力，写了一个包罗万象的类库，但没有人用。因为他们说：你这个太大了，我的程序只有1K，你却给我一个10000MB的库-MFC的尴尬；太好了，我终于找到了程序中的一个BUG，已经修改完成，而且是只改动了一个字节。接下来我要重新向我的用户分发新的版本，我的用户有.10万个-如果升级的不够健壮、平滑，不是我分发累死了，就是用户重新安装累死了。我想写一个集大成的软件，这个软件的功能是我中有你，你中有我。既能实现文字编辑，又能实现电子表格计算，又能实现自动翻译，还能画图，还能实现数据库检索，还可以看电影.只要用了我的这个软件，想要什么就有什么，我要强占整个软件的市场-OLE实现的重用功能，只要学会了COM，这些都不是问题了；用户甲要求我的软件窗口上下分割，用户乙要求我的软件窗口左右分割.我需要在我的软件基础上，派生出100个类型，可怎么办呀?将来怎么维护呀?-在脚本的支持下，实现同一程序的的灵活配置而重用，问题迎刃而