搜索
C语言高级编程技术8.1递归程序设计C语言支持函数的递归调用。递归就是函数直接或间接地自己调用自己。常见的递归算法有两种，即算术递归与操作递归。递归的基本思想是，将问题P求解的运算规模或操作步骤进行分解，使求解问题P的运算规模或操作步骤可以由求解一个简单问题以及在更小规模或更小步骤上求解相同的问题P来组成。当运算规模或操作步骤减少到一定程度时，如果问题P的求解算法可简单实现，就可以采用递归算法来实现问题P的求解。比如，求n!与求(n-1)!的运算方法是一样的；当n=0时，0!=1。8.1.1算术递归算术递归是指一切形式的递归算式都可以用递归方法求解。例8．1：用递归方法求n!。#includestdio.hlongfact(intn){if(n==0)return1;returnn*fact(n-1);}voidmain(){intn;scanf(%d,&n);printf(%d!=%ld\n,n,fact(n));}例8.2：用递归函数计算两个正整数的最大公约数。#includestdio.hintgcd(intm,intn){if(!n)returnm;returngcd(n,m%n);}voidmain(){inta,b,gcd1;scanf(%d%d,&a,&b);gcd1=gcd(a,b);printf(%d\n,gcd1);}8.1.2操作递归操作递归是指实现某种操作的递归。例8.3：用递归算法实现一维整型数组元素由小到大冒泡排序。#includestdio.hvoidsort(inta[],intn){inti,temp;if(n=0)return;for(i=0;in;i++)if(a[i]a[i+1]){temp=a[i];a[i]=a[i+1];a[i+1]=temp;}sort(a,n-1);}voidmain(){intarray[10],i;for(i=0;i10;i++)scanf(%d,&array[i]);sort(array,9);for(i=0;i10;i++)printf(%d,array[i]);}例8.4：用递归算法求一正长整型数的各位数字之和。#includestdio.hintsum(longi){if(i==0)return0;returni%10+sum(i/10);}voidmain(){longi;scanf(%ld,&i);printf(%d\n,sum(i));}8.1.3递归算法的优缺点递归函数的主要优点是可以把算法写的比使用非递归函数时更清晰更简洁，而且某些问题，特别是与人工智能有关的问题，更适宜用递归方法。递归算法的缺点，一是需要额外的内存开销，特别是当递归层次较大时，递归函数需要占用的堆栈内存空间相当大。二是函数的频繁调用会降低程序的执行效率。总之，递归算法要比解决同样问题的非递归算法效率低一些。内存空间需求更多一些。大多数用递归算法解决的问题，都可以找到相应的非递归算法，只有少数问题的求解只有递归算法。由于递归算法具有效率低、内存消耗大等缺点，在设计程序时，若有比较好的非递归算法，应尽量采用非递归算法。8．2文本的屏幕输出和键盘输入8.2.1文本的屏幕输出显示器的屏幕显示方式有两种：文本方式和图形方式。文本方式就是显示文本的模式，它的显示单位是字符而不是图形方式下的象素，因而在屏幕上显示字符的位置坐标就用行和列表示。TurboC的字符屏幕函数主要包括文本窗口大小的设定、窗口颜色的设置、窗口文本的清除和输入输出等函数。这些函数的有关信息(如宏定义等)均包含在conio.h头文件中，因此在用户程序中使用这些函数时，必须用include将conio.h包含进程序。1文本窗口的定义TurboC默认定义的文本窗口为整个屏幕，共有80列25行的文本单元。如图8-1所示，规定整个屏幕的左上角坐标为（1，1），右下角坐标为（80，25），并规定沿水平方向为X轴，方向朝右；沿垂直方向为Y轴，方向朝下。每个单元包括一个字符和一个属性，字符即ASCII码字符，属性规定该字符的颜色和强度。除了这种默认的80列25行的文本显示方式外，还可由用户通过函数：voidtextmode(intnewmode)；来显式地设置TurboC支持的5种文本显示方式。该函数将清除屏幕，以整个屏幕为当前窗口，并移光标到屏幕左上角。newmode参数的取值见表8-1，既可以用表中指出的方式代码，又可以用符号常量。LASTMODE方式指上一次设置的文本显示方式，它常用于在图形方式到文本方式的切换。图8-1表8-1方式符号常量显示列×行数和颜色0BW4040×25黑白显示1C4040×25彩色显示2BW8080×25黑白显示3C8080×25彩色显示7MONO80×25单色显示-1LASTMODE上一次的显示方式TurboC也可以让用户根据自己的需要重新设定显示窗口，也就是说，通过使用窗口设置函数window()定义屏幕上的一个矩形域作为窗口。window()函数的函数原型为：voidwindow(intleft,inttop,intright,intbottom)；函数中形参（intleft，inttop）是窗口左上角的坐标，（intright，intbottom）是窗口的右下角坐标，其中（left，top）和（right，bottom）是相对于整个屏幕而言的。例如，要定义一个窗口左上角在屏幕（20，5）处，大小为30列15行的窗口可写成：window(20,5,50,25);若window()函数中的坐标超过了屏幕坐标的界限，则窗口的定义就失去了意义，也就是说定义将不起作用，但程序编译链接时并不出错。窗口定义之后，用有关窗口的输入输出函数就可以只在此窗口内进行操作而不超出窗口的边界。一个屏幕可以定义多个窗口，但现行窗口只能有一个（因为DOS为单任务操作系统）。当需要用另一窗口时，可将定义该窗口的window()函数再调用一次,此时该窗口便成为现行窗口了。2文本窗口颜色和其它属性的设置文本窗口颜色的设置包括背景颜色的设置和字符颜色（既前景色）的设置，使用的函数及其原型为：设置背景颜色函数：voidtextbackground(intcolor)；设置字符颜色函数：voidtextcolor(intcolor)；有关颜色的定义见表8-2。表中的符号常数与相应的数值等价，二者可以互换。例如设定蓝色背景可以使用textbackground(1)，也可以使用textbackground(BLUE)，两者没有任何区别，只不过后者比较容易记忆，一看就知道是蓝色。表8-2颜色表符号常数数值含义背景或背景BLACK0黑前景、背景色BLUE1蓝前景、背景色GREEN2绿前景、背景色CYAN3青前景、背景色RED4红前景、背景色MAGENTA5洋红前景、背景色BROWN6棕前景、背景色LIGHTGRAY7淡灰前景、背景色DARKGRAY8深灰用于前景色LIGHTBLUE9淡蓝用于前景色LIGHTGREEN10淡绿用于前景色LIGHTCYAN11淡青用于前景色LIGHTRED12淡红用于前景色LIGHTMAGENTA13淡洋红用于前景色YELLOW14黄用于前景色WHITE15白用于前景色BLINK128闪烁用于前景色TurboC另外还提供了一个函数，可以同时设置文本的字符和背景颜色，这个函数是文本属性设置函数：voidtextattr(intattr)；参数attr的值表示颜色形式编码的信息，每一位代表的含义如下：位76543210Bbbbcccc闪烁背景颜色字符颜色字节低四位cccc设置字符颜色，4~6三位bbb设置背景颜色，第7位B设置字符是否闪烁。假如要设置一个蓝底黄字，定义方法如下：textattr(YELLOW+(BLUE4));若再要求字符闪烁，定义变为：textattr(128+YELLOW+(BLUE4);注意：(1)对于背景只有0到7共八种颜色，取大于7小于15的数，则代表的颜色与减7后的值对应的颜色相同；(2)用textbackground()和textcolor()函数设置了窗口的背景与字符颜色后，在没有用clrscr()函数清除窗口之前，颜色不会改变，直到使用了函数clrscr()，整个窗口和随后输出到窗口中的文本字符才会变成新颜色。(3)用textattr()函数时背景颜色应左移4位，才能使3位背景颜色移到正确位置；3窗口内文本的输入输出函数.窗口内文本的输出函数前面介绍过的printf()，putc()，puts()，putchar()等输出函数以整个屏幕为窗口的，它们不受由window设置的窗口限制，也无法用函数控制它们输出的位置，但TurboC提供了三个文本输出函数，它们受窗口的控制，窗口内显示光标的位置，就是它开始输出的位置。当输出行右边超过窗口右边界时，自动移到窗口内的下一行开始输出，当输出到窗口底部边界时，窗口内的内容将自动产生上卷，直到完全输出完为止，这三个函数均受当前光标的控制，每输出一个字符光标后移一个字符位置。这三个输出函数原型为：intcprintf(char*format，表达式表)；intcputs(char*str)；intputch(intch)；它们的使用格式同printf()，puts()和putc()，其中cprintf()是将按格式化串定义的字符串或数据输出到定义的窗口中，其输出格式串同printf函数，不过它的输出受当前光标控制，且输出特点如上所述，cputs同puts，是在定义的窗口中输出一个字符串，而putch()则是输出一个字符到窗口，它实际上是函数putc的一个宏定义，即将输出定向到屏幕。.窗口内文本的输入函数可直接使用stdio.h中的getch()或getche()函数。需要说明的是，getche()函数从键盘上获得一个字，在屏幕上显示的时候，如果字符超过了窗口右边界，则会被自动转移到下一行的开始位置。4有关屏幕操作的函数voidclrscr(void)；该函数将清除窗口中的文本，并将光标移到当前窗口的左上角，即(1,1)处。voidclreol(void)；该函数将清除当前窗口中从光标位置开始到本行结尾的所有字符，但不改变光标原来的位置。voiddelline(void)；该函数将删除一行字符，该行是光标所在行。voidgotoxy(intx,inty)；该函数很有用，用来定位光标在当前窗口中的位置。这里x，y是指光标要定位处的坐标（相对于窗口而言）。当x,y超出了窗口的大小时，该函数就不起作用了。intmovetext(intx1,inty1,intx2,inty2,intx3,inty3)；该函数将把屏幕上左上角为(xl，y1)，右下角为(x2，y2)的矩形内文本拷贝到左上角为(x3，y3)的一个新矩形区内。这里x，y坐标是以整个屏幕为窗口坐标系，即屏幕左上角为(1，1)。该函数与开设的窗口无关，且原矩形区文本不变。intgettext(intxl,intyl,intx2,inty2,void*buffer)；该函数将把左上角为(xl，y1)，右下角为(x2，y2)的屏幕矩形区内的文本存到由指针buffer指向的一个内存缓冲区内，当操作成功，返回1；否则，返回0。因一个在屏幕上显示的字符需占显示存储器VRAM的两个字节，即第一个字节是该字符的ASCII码，第二个字节为属性字节，即表示其显示的前景、背景色及是否闪烁，所以buffer指向的内存缓冲区的字节总数的计算为：字节总数=矩形内行数×每行列数×2其中：矩形内行数=y2-y1+l，每行列数=x2-xl+1（每行列数是指矩形内每行的列数）。矩形内文本字符在缓冲区内存放的次序是从左到右，从上到下，每个字符占连续两个字节并依次存放。intputtext(intx1,inty1,intx2,inty2,void*buffer)；该函数则是将gettext()函数存入内存buffer中的文字内容拷贝到屏幕上指定的位置。注意：(1)gettext()函数和