1、软件体系结构软件体系结构 编程回顾编程回顾林荣恒林荣恒北京邮电大学北京邮电大学2 2北京邮电大学北京邮电大学主要内容主要内容o 编程概述编程概述o 程序风格程序风格o 算法与数据结构算法与数据结构o 小结小结设计、调试和测试这里不再介绍设计、调试和测试这里不再介绍3 3北京邮电大学北京邮电大学编程概述编程概述o 程序程序o 编程编程Programmingo 编程语言编程语言4 4北京邮电大学北京邮电大学程序程序o 计算机的工作是由程序来控制的计算机的工作是由程序来控制的o 程序程序：程序是为解决某一问题而编写的语句序列。：程序是为解决某一问题而编写的语句序列。通俗的说，将解决一个实际问题的具体
2、操作步骤用通俗的说，将解决一个实际问题的具体操作步骤用某种计算机语言描述出来，就形成了程序。某种计算机语言描述出来，就形成了程序。n 语句序列：指令语句序列：指令o 计算机可以识别的命令计算机可以识别的命令n 实际问题的具体操作步骤：算法实际问题的具体操作步骤：算法o 求解问题的方法，是在有限的步骤内求解某一问题所使求解问题的方法，是在有限的步骤内求解某一问题所使用的一组定义明确的规则，是计算机处理问题所需要的用的一组定义明确的规则，是计算机处理问题所需要的过程过程5 5北京邮电大学北京邮电大学高质量的程序所具备的条件高质量的程序所具备的条件o 建立正确的数学模型和确定有效的计算方法建立正确的
3、数学模型和确定有效的计算方法o 运行结果必须正确，且在精度和其它各方面运行结果必须正确，且在精度和其它各方面均满足要求均满足要求o 程序本身具有良好的结构，逻辑清晰，易读程序本身具有良好的结构，逻辑清晰，易读易懂易懂o 程序运行时间尽可能短，同时尽可能合理地程序运行时间尽可能短，同时尽可能合理地使用内存使用内存o 便于检查、修正、移植和维护便于检查、修正、移植和维护6 6北京邮电大学北京邮电大学编程编程o 编程编程(Programming)：就是编写程序，：就是编写程序，它是在对算法进行正确描述的基础上进行的，它是在对算法进行正确描述的基础上进行的，是用计算机语言（程序设计语言）实现算法是用计
4、算机语言（程序设计语言）实现算法的过程。的过程。n 算法转变程序的过程算法转变程序的过程7 7北京邮电大学北京邮电大学编程的一般过程编程的一般过程o对于简单问题，前三步可看作一步，即分对于简单问题，前三步可看作一步，即分析问题、设计算法。析问题、设计算法。o维护？维护？8 8北京邮电大学北京邮电大学程序语言程序语言o 机器语言机器语言由计算机硬件系统可以识别的二进制指令由计算机硬件系统可以识别的二进制指令组成组成o 汇编语言将机器指令映射为一些可以被人读懂的助汇编语言将机器指令映射为一些可以被人读懂的助记符，如记符，如ADD、SUB等等o 高级语言高级语言屏蔽了机器的细节，提高了语言的抽象层屏
5、蔽了机器的细节，提高了语言的抽象层次次n程序中可以采用具有一定含义的数据命名和容易理解的程序中可以采用具有一定含义的数据命名和容易理解的执行语句执行语句n在书写程序时可以联系到程序所描述的具体事物在书写程序时可以联系到程序所描述的具体事物o 面向过程面向过程o 面向对象面向对象9 9北京邮电大学北京邮电大学选择计算机语言的原则选择计算机语言的原则o 根据自己所处理事务的特点来选择计算机语言根据自己所处理事务的特点来选择计算机语言o 符合现代程序设计的要求符合现代程序设计的要求o 适合使用者的硬件和软件环境适合使用者的硬件和软件环境o 考虑软件执行效率考虑软件执行效率o 考虑使用者的工作性质考虑
6、使用者的工作性质1010北京邮电大学北京邮电大学高级程序语言学习要点高级程序语言学习要点o数据结构数据结构n基本、复合基本、复合o变量变量n类型类型n声明方法声明方法o操作符操作符o语句语句n赋值、计算赋值、计算n结构控制语句：条件、分支、循环结构控制语句：条件、分支、循环n过程调用语句过程调用语句o功能块功能块/操作操作n函数、过程函数、过程n类中的方法或成员变量类中的方法或成员变量1111北京邮电大学北京邮电大学高级程序语言学习要点高级程序语言学习要点(2)o模块模块n.c文件文件n类类o类库或者库函数：该语言或者第三方提供的，不用自己编写的类库或者库函数：该语言或者第三方提供的，不用自己
7、编写的n系统调用系统调用n输入输出：文件、键盘、网络输入输出：文件、键盘、网络n随机数、随机数、Stringn线程线程no作用域作用域nPublic、static、private、protected、friendly、externo异常处理异常处理1212北京邮电大学北京邮电大学高级程序语言学习要点高级程序语言学习要点(3)o 可执行程序的构成和组织可执行程序的构成和组织n主程序、主程序、Main函数、函数、Main类类n模块文件、类文件模块文件、类文件n目录结构目录结构o 程序编辑、编译、链接和执行方法程序编辑、编译、链接和执行方法n依赖于环境依赖于环境o 该语言有特色的地方该语言有特色的地
8、方o 可视化程序设计可视化程序设计n实质是去使用开发环境提供的可视化库函数或者类库实质是去使用开发环境提供的可视化库函数或者类库1313北京邮电大学北京邮电大学主要内容主要内容o 编程概述编程概述o 程序风格程序风格o 算法与数据结构算法与数据结构o 小结小结1414北京邮电大学北京邮电大学程序风格程序风格o 引言引言o 名字名字o 表达式和语句表达式和语句o 一致性和习惯用法一致性和习惯用法o 函数宏函数宏o 神秘的数神秘的数o 注释注释1515北京邮电大学北京邮电大学程序风格程序风格o 引言引言o 名字名字o 表达式和语句表达式和语句o 一致性和习惯用法一致性和习惯用法o 函数宏函数宏o
9、神秘的数神秘的数o 注释注释1616北京邮电大学北京邮电大学看看这个代码看看这个代码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,
10、1.,7.,0.,0.,0.,.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*int
11、ersect(P,D)vec P,D;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&utmin?best=s,u:tmin;return best;vec trace(level,P,D)vec P,D;double d,eta,e;vec N,color;struct sphere*s,*l;if(!level-)return black;if(s=int
12、ersect(P,D);else return amb;color=amb;eta=s-ir;d=-vdot(D,N=vunit(vcomb(-1.,P=vcomb(tmin,D,P),s-cen);if(d0)N=vcomb(-1.,N,black),eta=1/eta,d=-d;l=sph+5;while(l-sph)if(e=l-kl*vdot(N,U=vunit(vcomb(-1.,P,l-cen)0&intersect(P,U)=l)color=vcomb(e,l-color,color);U=s-color;color.x*=U.x;color.y*=U.y;color.z*=U.
13、z;e=1-eta*eta*(1-d*d);return vcomb(s-kt,e0?trace(level,P,vcomb(eta,D,vcomb(eta*d-sqrt(e),N,black):black,vcomb(s-ks,trace(level,P,vcomb(2*d,N,D),vcomb(s-kd,color,vcomb(s-kl,U,black);main()printf(%d%dn,32,32);while(yx32*32)U.x=yx%32-32/2,U.z=32/2-yx+/32,U.y=32/2/tan(25/114.5915590261),U=vcomb(255.,tra
14、ce(3,black,vunit(U),black),printf(%.0f%.0f%.0fn,U);你写的比它好多少？你写的比它好多少？1717北京邮电大学北京邮电大学想写出高质量的代码吗？想写出高质量的代码吗？o 高质量代码的四个基本特性：高质量代码的四个基本特性：n 正确性正确性n 简单性简单性n 可读性可读性n 可测试性可测试性o 可读性可读性（清晰性）是（清晰性）是“易于维护、易于重构易于维护、易于重构的程序的程序”最有价值的特性最有价值的特性n 采用好的程序设计风格进行编码是实现可读性采用好的程序设计风格进行编码是实现可读性的必要保障的必要保障1818北京邮电大学北京邮电大学为什么
15、要有可读性？为什么要有可读性？o 编程首先是与人交流，其次才是与计算机交流，采编程首先是与人交流，其次才是与计算机交流，采用好的风格编写出可读性好的代码，可以降低与人用好的风格编写出可读性好的代码，可以降低与人交流的复杂度：交流的复杂度：n编程编程o 阅读代码的次数要比编写代码多得多，即使在开发的初阅读代码的次数要比编写代码多得多，即使在开发的初期也是如此期也是如此 n维护维护o 代码的维护者会感激你使代码容易理解代码的维护者会感激你使代码容易理解 n将来的维护者很可能就是你自己，到时候你得尝试记起自己将来的维护者很可能就是你自己，到时候你得尝试记起自己六个月以前在想什么六个月以前在想什么 o
16、 软件的首要技术使命是管理复杂度，许多编程实践软件的首要技术使命是管理复杂度，许多编程实践背后的动机正是为了降低程序的复杂度背后的动机正是为了降低程序的复杂度1919北京邮电大学北京邮电大学怎样提高可读性？怎样提高可读性？o 名字，最常见的有类名、子程序名、变量名；名字，最常见的有类名、子程序名、变量名；o 长度，比如类的长度、数据成员的数目、子程序的长度，比如类的长度、数据成员的数目、子程序的长度、子程序的参数数目、语句的嵌套层数；长度、子程序的参数数目、语句的嵌套层数；o 复杂度，包括表达式的复杂度、语句逻辑的复杂度复杂度，包括表达式的复杂度、语句逻辑的复杂度等；等；o 格式，包括缩进、空
17、格、注释等；格式，包括缩进、空格、注释等；o 耦合度，包括由于共享数据（含全局数据）导致的耦合度，包括由于共享数据（含全局数据）导致的耦合、类之间耦合（继承、组合、友元）、子程序耦合、类之间耦合（继承、组合、友元）、子程序之间的耦合等；之间的耦合等；2020北京邮电大学北京邮电大学程序风格程序风格o 引言引言o 名字名字o 表达式和语句表达式和语句o 一致性和习惯用法一致性和习惯用法o 函数宏函数宏o 神秘的数神秘的数o 注释注释2121北京邮电大学北京邮电大学名字：名不正，则言不顺！名字：名不正，则言不顺！o 类名、子程序名、变量名等，用于标识相应类名、子程序名、变量名等，用于标识相应的对象
18、的对象o 可以使用切合实际的命名约定，但一旦使用可以使用切合实际的命名约定，但一旦使用了，就一定要始终如一地坚持你的命名约定了，就一定要始终如一地坚持你的命名约定n frontsize,frontSize,front_size2222北京邮电大学北京邮电大学一些基本的命名规则一些基本的命名规则o全局变量使用具有说明性的名字，作用范围越大，所携带的信全局变量使用具有说明性的名字，作用范围越大，所携带的信息应该越多息应该越多n好名字：好名字：ocurrentDate、todaysDaten坏名字：坏名字：oX,y,d,cd,td,x,y,dateo局部变量可以使用短名字局部变量可以使用短名字n例如
19、，如果循环只有寥寥数行，而且只是单层循环，那么可以例如，如果循环只有寥寥数行，而且只是单层循环，那么可以用用i、j等等n 如果循环行数较多，或者有嵌套，则需要更长而且有意义的如果循环行数较多，或者有嵌套，则需要更长而且有意义的名字名字o试比较：试比较：nscoreteamIndexeventIndex 和和 scoreijo下标串化问题下标串化问题2323北京邮电大学北京邮电大学一些基本的命名建议（续一些基本的命名建议（续1）o 研究发现，当变量名的平均长度在研究发现，当变量名的平均长度在10到到16个字符的时候，调试程序所需花费的气力是个字符的时候，调试程序所需花费的气力是最小的。平均名字长
20、度在最小的。平均名字长度在8到到20个字符的程个字符的程序也几乎同样容易调试。序也几乎同样容易调试。n 太短的名字无法传达足够的信息太短的名字无法传达足够的信息 n 太长的名字很难写，同时也会使得程序的视觉太长的名字很难写，同时也会使得程序的视觉结构变得模糊不清结构变得模糊不清2424北京邮电大学北京邮电大学一些基本的命名建议（续一些基本的命名建议（续2）o 保持一致性保持一致性n 坏的命名：坏的命名：n 好的命名：好的命名：Class UserQueue int noOfItemsInQ,frontOfQueue,queueCapacity;public int noOfUsersInQue
21、ue()Class UserQueue int nUsers,front,capacity;public int getNoOfUsers()2525北京邮电大学北京邮电大学一些基本的命名建议（续一些基本的命名建议（续3）o 函数采用动作性的名字：用动作性的动词，后面跟函数采用动作性的名字：用动作性的动词，后面跟着名词着名词n如：如：n比较：比较：o If(checkoctal(c)和和 if(isoctal(c)o 要准确：名字不仅是个标记，它还携带着给读程序要准确：名字不仅是个标记，它还携带着给读程序人的信息人的信息now=date.getTime();putchar(n);2626北京邮
22、电大学北京邮电大学程序风格程序风格o 引言引言o 名字名字o 表达式和语句表达式和语句o 一致性和习惯用法一致性和习惯用法o 函数宏函数宏o 神秘的数神秘的数o 注释注释2727北京邮电大学北京邮电大学表达式和语句表达式和语句o 用缩行显示程序的结构用缩行显示程序的结构n Bad:n Good:For(n=0;n100;fieldn+=0;*i=0;return(n);For(n=0;n100;n+)Fieldn=0;*i=0;return(n);2828北京邮电大学北京邮电大学表达式和语句（续表达式和语句（续1）o 使用表达式的自然形式使用表达式的自然形式n Badn GoodIf(!(bl
23、ock_id=unblocks)If(block_id=actblks)|(block_id unblocks)2929北京邮电大学北京邮电大学表达式和语句（续表达式和语句（续2）o 用加括号的方式排除二义性用加括号的方式排除二义性n 在混合使用相互无关的运算符时，多加几个括在混合使用相互无关的运算符时，多加几个括号没有坏处号没有坏处o 尤其是尤其是C语言语言n 即使不必要，加了括号也能把意图表现得更明即使不必要，加了括号也能把意图表现得更明白白n 小窍门：使用括号使得你不用去记那些操作符小窍门：使用括号使得你不用去记那些操作符的优先级的优先级3030北京邮电大学北京邮电大学表达式和语句（续表
24、达式和语句（续3）o 分解复杂的表达式分解复杂的表达式n Bad：n Good*x+=(*xp=(2*k (n-m)?ck+1:dk-);If(2*k (n-m)*xp=cK+1;Else*xp=dk-;*x+=*xp;3131北京邮电大学北京邮电大学表达式和语句（续表达式和语句（续4）o 当心副作用当心副作用n Bad code：n Good code：stri+=stri+=;Stri+=;Stri+=;3232北京邮电大学北京邮电大学表达式和语句（续表达式和语句（续5）o 使用空行将代码分为有机的各个部分使用空行将代码分为有机的各个部分#include#include int main(
25、int argc,char*argv)/*Set the input to no-echo,character-at-time *(cbreak)mode,*and remember the old mode in t0*/struct termios t0,t1;tcgetattr(0,&t0);t1=t0;t1.c_lflag&=!(ECHO|ICANON);tcsetattr(0,0,&t1);run();/*Set the terminal back to its original mode*/tcsetattr(0,0,&t0);return 0;3333北京邮电大学北京邮电大学表达
26、式和语句（续表达式和语句（续6）o 子程序、函数、方法的代码行数最好不要超子程序、函数、方法的代码行数最好不要超过过200行行n 可读性不好可读性不好n 新手可以先编长的，再进行分离。新手可以先编长的，再进行分离。o 每一行只写一条语句每一行只写一条语句3434北京邮电大学北京邮电大学程序风格程序风格o 引言引言o 名字名字o 表达式和语句表达式和语句o 一致性和习惯用法一致性和习惯用法o 函数宏函数宏o 神秘的数神秘的数o 注释注释3535北京邮电大学北京邮电大学一致性和习惯用法一致性和习惯用法o 一致性带来更好的程序一致性带来更好的程序n命名的一致性命名的一致性n语句的一致性语句的一致性n
27、相同实现方法的一致性：如果相同的计算每次总是采用相同的相同实现方法的一致性：如果相同的计算每次总是采用相同的方式，任何变化就预示着是经过了深思熟虑，要求读程序的人方式，任何变化就预示着是经过了深思熟虑，要求读程序的人注意注意o 其他的一致性：其他的一致性：n算法算法n数据结构数据结构n出错处理方式出错处理方式n高层设计模式高层设计模式n3636北京邮电大学北京邮电大学一致性和习惯用法（续一致性和习惯用法（续1）o 使用一致的缩排和加括号的方法使用一致的缩排和加括号的方法if(month=FEB)if(year&4=0)if(day 29)legal=FALSE;else if(day 28)l
28、egal=FALSE;if(month=FEB)if(year&4=0)if(day 29)legal=FALSE;else if(day 28)legal=FALSE;Wrong code(else matches“if day 29”)Right code 3737北京邮电大学北京邮电大学一致性和习惯用法（续一致性和习惯用法（续2）o 为了一致性，使用习惯用法为了一致性，使用习惯用法n just“so-so”coden Good codei=0;while(i=n-1)arrayi+=1.0;for(i=0;in;i+)arrayi=1.0;3838北京邮电大学北京邮电大学一致性和习惯用法
29、（续一致性和习惯用法（续3）o 用用else-if表达多路选择表达多路选择njust“so-so”code:nGood code:if(x vmid)low=mid+1;else return mid;if(x vmid)low=mid+1;else return mid;245781017low=0high=6mid=310 xv3939北京邮电大学北京邮电大学程序风格程序风格o 引言引言o 名字名字o 表达式和语句表达式和语句o 一致性和习惯用法一致性和习惯用法o 函数宏函数宏o 神秘的数神秘的数o 注释注释4040北京邮电大学北京邮电大学函数宏函数宏o 避免函数宏避免函数宏n 函数宏的缺
30、点远远超过它能带来的好处函数宏的缺点远远超过它能带来的好处o 给宏的体和参数都加上括号给宏的体和参数都加上括号n Bad code：n Good code:#define square(x)x*x#define square(x)(x)*(x)4141北京邮电大学北京邮电大学程序风格程序风格o 引言引言o 名字名字o 表达式和语句表达式和语句o 一致性和习惯用法一致性和习惯用法o 函数宏函数宏o 神秘的数神秘的数o 注释注释4242北京邮电大学北京邮电大学神秘的数神秘的数o 神秘的数包括各种常数、数组的大小、字符神秘的数包括各种常数、数组的大小、字符位置、变换因子以及程序中出现的其他以文位置、
31、变换因子以及程序中出现的其他以文字形式写出的数值。字形式写出的数值。o 给神秘的数起一个好名字给神秘的数起一个好名字n MINROW、MINCOL、MAXROW、MAXCOL4343北京邮电大学北京邮电大学神秘的数（续神秘的数（续1）o 把数定义为常数，不要定义为宏把数定义为常数，不要定义为宏n Const int MAXROW=24;n Static final int MAXROW=24;o 使用字符形式的常数，不用整数使用字符形式的常数，不用整数n Bad：if(c=65&c=A&c=Z)n Good:if(issupper(c)o Java：if(Character.isUpperCa
32、se(c)4444北京邮电大学北京邮电大学神秘的数（续神秘的数（续2）o 利用语言去计算对象的大小利用语言去计算对象的大小char buf1024;fgets(buf,sizeof(buf),stdin);char buf=new char1024;For(int i=0;I buf.length;i+)4545北京邮电大学北京邮电大学程序风格程序风格o 引言引言o 名字名字o 表达式和语句表达式和语句o 一致性和习惯用法一致性和习惯用法o 函数宏函数宏o 神秘的数神秘的数o 注释注释4646北京邮电大学北京邮电大学注释注释o 程序中的注释是程序员与日后的程序读者之程序中的注释是程序员与日后的
33、程序读者之间通信的重要手段。间通信的重要手段。o 注释绝不是可有可无的。注释绝不是可有可无的。o 一些正规的程序文本中，注释行的数量占到一些正规的程序文本中，注释行的数量占到整个源程序的整个源程序的13到到12，甚至更多。，甚至更多。o 注释分为注释分为序言性注释序言性注释和和功能性注释功能性注释。4747北京邮电大学北京邮电大学序言性注释序言性注释o通常置于每个程序模块的开头部分，它应当给出程序的整体说通常置于每个程序模块的开头部分，它应当给出程序的整体说明，对于理解程序本身具有引导作用。明，对于理解程序本身具有引导作用。n有些软件开发部门对序言性注释做了明确而严格的规定，要求有些软件开发部
34、门对序言性注释做了明确而严格的规定，要求程序编制者逐项列出。程序编制者逐项列出。o有关项目包括：有关项目包括：n程序标题程序标题；n有关本模块有关本模块功能功能和和目的目的的说明；的说明；n 主要算法主要算法；n 接口说明接口说明：包括调用形式，参数描述，子程序清单；：包括调用形式，参数描述，子程序清单；n 有关有关数据描述数据描述：重要的变量及其用途，约束或限制条件，以：重要的变量及其用途，约束或限制条件，以及其它有关信息；及其它有关信息；n 模块位置模块位置：在哪一个源文件中，或隶属于哪一个软件包；：在哪一个源文件中，或隶属于哪一个软件包；n 开发简历开发简历：模块设计者，复审者，复审日期
35、，修改日期及有：模块设计者，复审者，复审日期，修改日期及有关说明等。关说明等。4848北京邮电大学北京邮电大学功能型注释功能型注释o 功能性注释嵌在源程序体中，用以描述其后的语句或程功能性注释嵌在源程序体中，用以描述其后的语句或程序段是在做什么工作，或是执行了下面的语句会怎么样。序段是在做什么工作，或是执行了下面的语句会怎么样。而而不要不要解释下面怎么做解释下面怎么做n Badn Good/*Add Amount to Total*Total=amount+total/*Add Monthly-Sales to Annual-Totol*Total=amount+total4949北京邮电大学
36、北京邮电大学基本建议基本建议o 给类、方法、函数、全局数据加注释给类、方法、函数、全局数据加注释o 描述一段程序，而不是每一个语句描述一段程序，而不是每一个语句n Purpose of code,not every detail n Tricks usedn Reasons for unusual coding o 用缩进和空行，使程序与注释容易区别用缩进和空行，使程序与注释容易区别o 注释要正确，不要与代码矛盾注释要正确，不要与代码矛盾o 不要注释差的代码，重写它不要注释差的代码，重写它5050北京邮电大学北京邮电大学基本建议（续基本建议（续1）o 不要大谈明显的东西不要大谈明显的东西Zer
37、ocount+;/*Increment zero entry counter*/While(c=getchar()!=EOF&isspace(c);/*skip white space5151北京邮电大学北京邮电大学基本建议（续基本建议（续2）o 澄清情况，不要添乱澄清情况，不要添乱n If it takes longer to read the comment than to read the code,dont add a comment!n Bad：n Good:/*string comparison routine returns-1 if s1 is above s2*/In an
38、ascending order list,0 if equal,1 if s1 below s2*/*strcmp:return 0 if s10 if s1s2,0 if equal*/5252北京邮电大学北京邮电大学小结小结o 程序必须是写给人看的，仅仅偶尔才在机器上执行。程序必须是写给人看的，仅仅偶尔才在机器上执行。o 好习惯很重要，因为程序员做的大部分事情都是无好习惯很重要，因为程序员做的大部分事情都是无意识完成的意识完成的 n初涉编程时，就应端正态度来学，尽快培养良好的习惯初涉编程时，就应端正态度来学，尽快培养良好的习惯o 甚至你在工作压力下写出的代码也会更好甚至你在工作压力下写出的
39、代码也会更好o 富于技巧富于技巧(tricky)、聪明、聪明(clever)可算是代码的可算是代码的恶劣品质，编程不是为了炫耀自己的聪明程度，这恶劣品质，编程不是为了炫耀自己的聪明程度，这样写程序简直是歪门邪道样写程序简直是歪门邪道n通过你自己的程序你想体现什么？通过你自己的程序你想体现什么？5353北京邮电大学北京邮电大学最后最后请把修改你代码的人记在心上请把修改你代码的人记在心上与人方便，与己方便与人方便，与己方便5454北京邮电大学北京邮电大学主要内容主要内容o 编程概述编程概述o 程序风格程序风格o 算法与数据结构算法与数据结构o 小结小结5555北京邮电大学北京邮电大学算法与数据结构
40、算法与数据结构o 数据结构概述数据结构概述o 算法概述算法概述o 实例实例o 小结小结5656北京邮电大学北京邮电大学算法与数据结构算法与数据结构o 数据结构概述数据结构概述o 算法概述算法概述o 实例实例o 小结小结5757北京邮电大学北京邮电大学基本概念基本概念o 数据：在计算机科学中是指所有能输入到计数据：在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。算机中并被计算机程序处理的符号的总称。n 数据是信息的载体数据是信息的载体n 数据是计算机程序加工的原料数据是计算机程序加工的原料n 数据的含义极为广泛，且不断丰富数据的含义极为广泛，且不断丰富o 数据元素：是数据的
41、基本单位，在计算机程数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。序中通常作为一个整体进行考虑和处理。n 比如电话号码表中的每一行信息便是一个数据比如电话号码表中的每一行信息便是一个数据元素（它包含三个数据项）。元素（它包含三个数据项）。n 此概念是相对的此概念是相对的5858北京邮电大学北京邮电大学基本概念（基本概念（2）o 数据结构：组成数据的元素之间的结构关系。数据结构：组成数据的元素之间的结构关系。n 线性结构、树型结构和图结构是线性结构、树型结构和图结构是数据结构数据结构中的几类常见的数据结构形式。中的几类常见的数据结构形式。n 如果数据中的元素之间没有关
42、系，则构成集合，如果数据中的元素之间没有关系，则构成集合，这也是一种结构。这也是一种结构。5959北京邮电大学北京邮电大学基本概念（基本概念（3）o 数据结构的内容：数据结构的内容：n 逻辑结构：逻辑结构：数据元素之间的逻辑关系数据元素之间的逻辑关系o 线性结构线性结构：线性表、数组、栈、队列、串等：线性表、数组、栈、队列、串等o 非线性结构：非线性结构：树、图等树、图等n 物理结构（存储结构）：物理结构（存储结构）：数据元素及其关系在数据元素及其关系在计算机存储器内的表示计算机存储器内的表示o 顺序存储结构、链式存储结构、索引存储结构、散顺序存储结构、链式存储结构、索引存储结构、散列存储结构
43、列存储结构n 数据的运算：数据的运算：即对数据所施加的操作即对数据所施加的操作o 检索、插入、删除、更新、排序等检索、插入、删除、更新、排序等6060北京邮电大学北京邮电大学举例：分析如下电话号码表数据结构举例：分析如下电话号码表数据结构编号姓名电话号码1张三35501232李四35401233李七80987894张彬78967545丁丁12345676黄七98087547张发99878778丁一90909609黄三56448891、逻辑结构、逻辑结构2、存储结构、存储结构3、数据的运算、数据的运算分析：分析：开始结点开始结点终端结点终端结点排在其前排在其前(后后)面且与其相邻面且与其相邻的结
44、点称为该的结点称为该结点的结点的直接前直接前趋趋(后继后继)结点结点有且仅有一个有且仅有一个开始结点和一开始结点和一个终端结点，个终端结点，并且所有结点并且所有结点都最多只有一都最多只有一个直接前趋和个直接前趋和一个直接后继，一个直接后继，这就是该数据这就是该数据结构的逻辑结结构的逻辑结构构6161北京邮电大学北京邮电大学算法与数据结构算法与数据结构o 数据结构概述数据结构概述o 算法概述算法概述o 实例实例o 小结小结6262北京邮电大学北京邮电大学定义定义o 算法：是在有限步骤内求解某一问题所使用的算法：是在有限步骤内求解某一问题所使用的一组定义明确的规则一组定义明确的规则。描述描述算法算
45、法设给定两个正整数设给定两个正整数m=112和和n=64，利用辗转相除法，利用辗转相除法，求它们的最大公约数。求它们的最大公约数。（1）112除以除以64，余数为，余数为48；（2）64除以除以48，余数为，余数为16；（3）48除以除以16，余数为，余数为0；答答:112和和64的最大公约数为的最大公约数为16。6363北京邮电大学北京邮电大学算法的特征算法的特征o 输入：一个算法有零个或多个输入；输入：一个算法有零个或多个输入；o 确定性：算法的每一个步骤必须要确切地定确定性：算法的每一个步骤必须要确切地定义；义；o 有穷性：一个算法在执行有穷步之后必须结有穷性：一个算法在执行有穷步之后必
46、须结束；束；o 输出：算法有一个或多个输出；输出：算法有一个或多个输出；o 能行性：算法中有待执行的运算和操作必须能行性：算法中有待执行的运算和操作必须是相当基本的（运算和操作能精确地执行）是相当基本的（运算和操作能精确地执行）6464北京邮电大学北京邮电大学算法的描述算法的描述问题描述自然语言流程图伪代码设计一个设计一个算法，求算法，求出出100以以内能被内能被3整除的所整除的所有正整数。有正整数。令令I=1；如果如果I能被能被3整整除，则输除，则输出出I；I=I+1；如果如果I100，则返回第则返回第步；步；结束。结束。I=1DOIF I MOD 3=0 THEN PRINT II=I+1
47、LOOP WHILE I 100开始I=1I能被3整除I=I+1I 100结束输出I是否否是6565北京邮电大学北京邮电大学算法设计的要求算法设计的要求o 1、正确性：、正确性：算法应当满足具体问题的需求。“正确”一词的含义在通常的用法中有很大差别，大体可分为四个层次：n 程序不含语法错误。n 程序对几组输入数据能够得出满足规格说明要求的结果。n 程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果。n 程序对于一切合法的输入数据都能产生满足规格说明要求的结果。6666北京邮电大学北京邮电大学算法设计的要求（算法设计的要求（2）o 2、可读性：、可读性：可读性好
48、有助于人对算法的理解。o 3、健壮性：、健壮性：当输入数据非法时，算法也能适当做出反应或进行处理，而不会产生莫名其妙的输出结果。o 4、效率与低存储量需求：、效率与低存储量需求：效率指算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。6767北京邮电大学北京邮电大学算法的评价算法的评价o 评价算法的标准：评价算法的标准：评价一个算法主要看这个算法评价一个算法主要看这个算法所占用机器资源的多少，而这些资源中时间代价与所占用机器资源的多少，而这些资源中时间代价与空间代价是两个主要的方面，通常是以算法执行所空间代价是两个主要的方面，通常是以算法执行所需的机器时间和所占用的存储空间来判断
49、一个算法需的机器时间和所占用的存储空间来判断一个算法的优劣。的优劣。n时间复杂度时间复杂度n空间复杂度空间复杂度o 在算法时间与空间效率的两方面，着重分析时间效在算法时间与空间效率的两方面，着重分析时间效率，即算法的时间复杂度，因为我们总是希望程序率，即算法的时间复杂度，因为我们总是希望程序在较短的时间内给出我们所希望的输出。在较短的时间内给出我们所希望的输出。6868北京邮电大学北京邮电大学典型算法典型算法o 递归与分治递归与分治o 动态规划动态规划o 贪心算法贪心算法o 回朔法回朔法o 分支限界法分支限界法o 概率算法概率算法6969北京邮电大学北京邮电大学算法与数据结构算法与数据结构o
50、数据结构概述数据结构概述o 算法概述算法概述o 实例实例o 小结小结7070北京邮电大学北京邮电大学实例实例o 问题描述问题描述o 算法和数据结构分析算法和数据结构分析o C语言实现语言实现7171北京邮电大学北京邮电大学实例实例o 问题描述问题描述o 算法和数据结构分析算法和数据结构分析o C语言实现语言实现7272北京邮电大学北京邮电大学问题描述问题描述o 随机产生出一些可以读的英文文本随机产生出一些可以读的英文文本n 随机字母随机字母?o Xpdtqwt asfasg kfuwnhn 字母在英语里出现的权重？字母在英语里出现的权重？o Idtefoae tcs trdern 从字典里随机
