1、高级语言程序设计高级语言程序设计(一一)(C Programming)第四讲：程序设计方法第四讲：程序设计方法-模块化与模块化与算法设计算法设计本章目标本章目标n进一步掌握模块化设计思想进一步掌握模块化设计思想n掌握常用的数据查找及排序方法掌握常用的数据查找及排序方法n了解全局变量了解全局变量n了解递归程序设计思想了解递归程序设计思想问题问题4.1【问题描述问题描述】从文件中查找包含给定字符串的行。从文件中查找包含给定字符串的行。【输入形式输入形式】从标准输入中分两行分别输入被查找的文件及要查找的字符串（中间不含空格）。从标准输入中分两行分别输入被查找的文件及要查找的字符串（中间不含空格）。【
2、输出形式输出形式】在屏幕上输出文件中包含给定字符串的行。在屏幕上输出文件中包含给定字符串的行。【样例输入样例输入】在键盘输入如下文件名及字符串在键盘输入如下文件名及字符串:test.txtthe文件文件test.txt内容如下：内容如下：Now is the timefor all goodmen to come to the aidof their party【样例输出样例输出】屏幕输出为：屏幕输出为：this is the timemen to come to the aidof their party问题问题4.1：算法设计：算法设计n设设 int index ( char s , ch
3、ar t )函数用来在字符串函数用来在字符串s中查找字符串中查找字符串t。若。若找到则反回找到则反回t在在s中出现的位置，否则返回中出现的位置，否则返回-1。其主要查找算法如下：。其主要查找算法如下：0 1 20输入串输入串0 1给定串主要算法分析主要算法分析0 1给定串在字符串在字符串s中查找字符串中查找字符串t ：for(i=0; si != 0; i+) for(j=i,k=0; tk != 0; j+,k+) sj和和tk进行比较进行比较遍历输入字符遍历输入字符串中每个字符串中每个字符依次与给定串中依次与给定串中每个字符比较。每个字符比较。j为为s中每次开始中每次开始比较的位置。比较的
4、位置。不同时不同时break；找到的条件是：找到的条件是：tk=0问题问题4.1：算法设计（续）：算法设计（续）主要算法如下：主要算法如下：设变量设变量filename,s,linefilename,s,line分别用于存储文件名、查找串及文件中一行；分别用于存储文件名、查找串及文件中一行；从标准输入中读入文件名和要查找的串到从标准输入中读入文件名和要查找的串到filenamefilename和和s s中；中；以读方式打开文件以读方式打开文件filenamefilename；while while 文件中还有内容时读一行到文件中还有内容时读一行到lineline中中如果如果 index(lin
5、e, s) = 0index(line, s) = 0 输出输出line;line;如何从文件中读入一行？如何从文件中读入一行？char char * *fgets(char fgets(char * *s, int n, FILE s, int n, FILE * *fp)fp)从从fpfp上最多读入上最多读入n-1n-1个字符，放入个字符，放入s s 字符数组中。字符数组中。返回返回s s，到达文件尾部返回，到达文件尾部返回NULLNULL。利用利用fgets从标准输入读取从标准输入读取一行字符串放在字符数组一行字符串放在字符数组s中，中，s的大小是的大小是101：fgets( s , 1
6、01 , stdin );问题问题4.1：代码实现：代码实现#include #define MAXLINE 1000int index(char s , char t );int main( ) char filename64, s81, lineMAXLINE; FILE *fp;scanf(%s, filename);scanf(%s, s);if(fp = fopen(filename, r) = NULL) printf(Cant open file %s!n, filename);return 1;while(fgets(line, 81, fp) != NULL) if(inde
7、x(line, s) = 0) printf(%s, line); return 0;int index(char s , char t )int i, j, k;for(i =0; si != 0; i+)for(j=i,k=0;tk!=0&sj= tk; j+,k+);if(tk = 0)return ( i);return ( -1);使用使用scanf的缺点是不能输入带的缺点是不能输入带空格的字符串。可换成空格的字符串。可换成gets(s);来实现查找带空格的字符串。来实现查找带空格的字符串。由于打开一个文件操作可能失败由于打开一个文件操作可能失败，因此，好的风格应判断，因此，好的风格
8、应判断fopen函数的返回值，进行错误处理。函数的返回值，进行错误处理。注意：由于上述循环当没有相应匹注意：由于上述循环当没有相应匹配字符时也退出。因此，要依据配字符时也退出。因此，要依据t中中所有字符都匹配（即所有字符都匹配（即tk=0）来）来判断查找是否成功。判断查找是否成功。问题问题4.1：测试：测试当要查找的文件为当要查找的文件为“test.txt”,要查找的串为要查找的串为”the”，且文件，且文件test.txt中内容为：中内容为：Now is the timefor all goodmen to come to the aidof their party则屏幕输出：则屏幕输出：t
9、his is the timemen to come to the aidof their party问题问题4.1：测试（续）：测试（续）n其它考虑点：其它考虑点：l要查找的串在一行的头、尾要查找的串在一行的头、尾l要查找的串在文件中不存在要查找的串在文件中不存在问题问题4.1：思考：思考1n问题问题4.1实现了大小写相关的字符串查找，即字符实现了大小写相关的字符串查找，即字符串串“the”和和“The”是不同字符串。请实现是不同字符串。请实现大小写大小写无关无关的字符串查找。的字符串查找。n算法分析：算法分析：在比较字符时，可将比较字符均转换为小写或大在比较字符时，可将比较字符均转换为小写
10、或大写既可实现大小写无关查找。写既可实现大小写无关查找。设函数设函数char tolower(char c)char tolower(char c)用于将字符用于将字符c c转换转换为相应小写字符，则上面为相应小写字符，则上面indexindex可改为：可改为：int index(char s , char t )int i, j, k;for(i =0; si != 0; i+)for(j=i,k=0;tk!=0&tolower(sj)= tolower(tk); j+,k+);if(tk = 0)return ( i);return ( -1);问题问题4.1：函数：函数tolower实现
11、实现n方法一：方法一：char tolower(char c)if( c =A & c=A&c (B) ?(A) : (B)于是语句于是语句x = max(p+q, r+s); 可替换为：可替换为：x = (p+q) (r+s) ? (p+q) : (r+s);注意：注意：a.宏定义名与参数间不能有空格，如宏定义名与参数间不能有空格，如max(A,B); b.参数应用括号括起来，如参数应用括号括起来，如(A)(B)?(A) : (B) #define isupper(c ) (c =A & c=Z)?1:0反例：反例：#define prod(x,y) x*y则：则：a=prod(b+c,d+
12、e);被替换为：被替换为：a=b+c*d+e;问题问题4.1：思考：思考1（代码实现）（代码实现）#include #define MAXLINE 1000#define tolower(c) (c=A&c= 0) printf(%s, line); return 0;int index(char s , char t )int i, j, k;for(i =0; si != 0; i+)for(j=i,k=0;tk!=0&tolower(sj)= tolower(tk); j+,k+);if(tk = 0)return ( i);return ( -1);问题问题4.1：思考：思考2n其它实
13、现方法？其它实现方法？n问题问题4.1中中index只能查找的是子字符串的首次出现只能查找的是子字符串的首次出现。请考虑如何查找子字符串的最后一次出现？。请考虑如何查找子字符串的最后一次出现？n如果要查找一个字符串在一个文件中的出现次数如果要查找一个字符串在一个文件中的出现次数，或查找一个字符串在一个文件中的所有出现行，或查找一个字符串在一个文件中的所有出现行列位置，如何实现？（注意，列位置，如何实现？（注意，index只能查找子字只能查找子字符串首次出现，如果一行中有多个子字符串怎样符串首次出现，如果一行中有多个子字符串怎样办？）办？）问题问题4.2【问题描述问题描述】某班有不超过某班有不超
14、过200名的学生，从文件中输入某班学生成绩，对输入成绩按由高到低进行排序，并输名的学生，从文件中输入某班学生成绩，对输入成绩按由高到低进行排序，并输出到另一个文件中。出到另一个文件中。【输入形式输入形式】从文件从文件scorelist.in中读入学生成绩，学生成绩以整数形式按行存放。注意，学生成绩数目不确定。中读入学生成绩，学生成绩以整数形式按行存放。注意，学生成绩数目不确定。【输出形式输出形式】将排序结果按行写到文件将排序结果按行写到文件sorelist.out中。中。【样例输入样例输入】若文件若文件scorelist.in中有如下成绩中有如下成绩:5875628698【样例输出样例输出】程
15、序运行结束后文件程序运行结束后文件scorelist.out中内容为：中内容为：9886756258问题问题4.2：算法分析：算法分析n问题可分解为如下几个部分：问题可分解为如下几个部分：算法：算法：int socrelistNUM,n=0;while(!feof(in) fscanf(in, “%d”, &scorelistn+);函数函数feof用来测试是否已读写到文件尾用来测试是否已读写到文件尾,若若到文件尾到文件尾,则返回则返回1,否则返回否则返回0。函数函数fscanf用来从文件中读数据。与标准用来从文件中读数据。与标准输入输入scanf不同的是第一个参数为文件指针不同的是第一个参数
16、为文件指针。算法：算法：for(i=0; in; i+) fprintf(out,“%d “,scorelisti);函数函数fprintf用来从文件中读数据。与标准输入用来从文件中读数据。与标准输入printf不同的是第一个参数为文件指针。不同的是第一个参数为文件指针。算法：算法：设一个函数专门用来对学生成绩进设一个函数专门用来对学生成绩进行排序，函数原型为：行排序，函数原型为：void sortScore(int list, int len )从文件中读入学生成绩从文件中读入学生成绩对学生成绩排序对学生成绩排序输出排序后成绩到文件中输出排序后成绩到文件中打开输入打开输入/输出文件输出文件算
17、法：算法：FILE *in, *out;in = fopen(“scorelist.in”, “r”);out = fopen(“scorelist.out”,”w”);问题问题 4.2：算法分析：算法分析- 选择排序（续）选择排序（续）n有许多经典的算法用来对数据进行排序，如选择有许多经典的算法用来对数据进行排序，如选择排序（排序（selection sort）、插入排序（）、插入排序（insertion sort）和快速排序（和快速排序（quick sort）等。有关排序算法及分）等。有关排序算法及分析主要在析主要在数据结构数据结构课程中讲授。课程中讲授。n在问题在问题4.2中将使用中将使
18、用选择排序选择排序算法对学生成绩进行算法对学生成绩进行排序。排序。问题问题 4.2：算法分析：算法分析- 选择排序（续）选择排序（续）n选择排序的核心思想是先通过找到选择排序的核心思想是先通过找到数组中未排序数组中未排序部分的最大元素部分的最大元素，然后将其，然后将其移到未排序部分的最移到未排序部分的最前端来前端来排序一个数组（从大至小排序）。即首先排序一个数组（从大至小排序）。即首先在整个数组中查找最大元素，将其换到第一个位在整个数组中查找最大元素，将其换到第一个位置；然后从数组中第二个元素开始查找最大元素置；然后从数组中第二个元素开始查找最大元素，以此类推。下面以图示来说明：，以此类推。下
19、面以图示来说明：问题问题 4.2：算法分析：算法分析- 选择排序（续）选择排序（续）16 3024 725 62 45 565 501032465879未排序最大元素交换65 3024 725 62 45 516 501032465879未排序最大元素交换65 6224 725 30 45 516 501032465879问题问题 4.2：算法分析：算法分析- 选择排序（续）选择排序（续）n选择排序包括以下步骤：选择排序包括以下步骤：1.找到最大元素找到最大元素2.将最大元素移到未排序部分的第一个位置上将最大元素移到未排序部分的第一个位置上index = 0;for(i=1; iN; i+)
20、if(arrayindex arrayi) index = i;通过交换两个元素即可。如：通过交换两个元素即可。如：int tmp;tmp = arrayi;arrayi = arrayindex;arrayindex = tmp;问题问题 4.2：代码实现（排序函数）：代码实现（排序函数）void sortArray(int array, int n) int i,j,tmp, index; for(i=0; in; i+) index = i; for (j=i; jn; j+) if(arrayindex arrayj) index = j; tmp = arrayi; arrayi =
21、 arrayindex; arrayindex = tmp; 找最大元素找最大元素将最大元素移到未排将最大元素移到未排序部分的头部序部分的头部问题问题 4.2：代码实现（主函数）：代码实现（主函数）#include #define NUM 200void sortArray(int array, int n);int main() int scorelistNUM, i, n=0; FILE *in, *out; if(in = fopen(scorelist.in,r) = NULL) printf(Cannt open file scorelist.in!n); return 1; if(
22、out = fopen(scorelist.out,w) = NULL) printf(Cannt open file scorelist.out!n); return 1; while(!feof(in) fscanf(in,%d,&scorelistn+ ); sortArray(scorelist, n); for(i=0; in; i+) fprintf(out, %dn,scorelisti); fclose(in); fclose(out); return 0;C程序设计基础22问题问题 4.2：一种模块化更好的实现一种模块化更好的实现#include #define NUM 20
23、0int readList(int array );void sortArray(int array , int n);void writeList(int array , int n);int main() int scorelistNUM, n; n = readList(scorelist); sortArray(scorelist, n); writeList(scorelist, n); return 0;int readList(int array ) FILE *in; int n=0; if(in = fopen(scorelist.in,r) = NULL) printf(C
24、annt open file scorelist.in!n); exit(1); while(!feof(in) fscanf(in,%d,&arrayn+ ); fclose(in); return n;void writeList(int array , int n) FILE *out; int I; if(out = fopen(scorelist.out,w) = NULL) printf(Cannt open file scorelist.out!n); exit(1); for(i=0; in; i+) fprintf(out, %dn,arrayi); fclose(out);
25、问题问题 4.2：测试及常见问题：测试及常见问题n若文件若文件scorelist.in文件尾有一个回车，文件尾有一个回车，则会发生什则会发生什么现象么现象？如何调试？如何调试？若文件若文件scorelist.in内容为：内容为：5875628698程序运行后文件程序运行后文件scorelist.out内容为：内容为：9886756258问题问题 4.2：修改主函数：修改主函数#include #define NUM 200void sortArray(int array, int n);int main() int scorelistNUM, i, n=0; FILE *in, *out; i
26、f(in = fopen(scorelist.in,r) = NULL) printf(Cannt open file scorelist.in!n); return 1; if(out = fopen(scorelist.out,w) = NULL) printf(Cannt open file scorelist.out!n); return 1; while(fscanf(in,%d,&scorelistn )0) n+; sortArray(scorelist, n); for(i=0; in; i+) fprintf(out, %dn,scorelisti); return 0;问题
27、问题 4.2：另一个常用排序方法（冒泡排序）：另一个常用排序方法（冒泡排序）*void sortArray(int array, int n) int i, j, tmp; for(i=0; in; i+) for(j=i; jn; j+) if(arrayi arrayj) tmp = arrayi; arrayi = arrayj; arrayj = tmp; 问题问题 4.2：另一个常用排序方法（冒泡排序）：另一个常用排序方法（冒泡排序）*/从后往前从后往前,即最先排好的是头部即最先排好的是头部void sortArray(int array, int n) int i, j, tmp;
28、 for(i=1;i=i;j-)if(arrayjarrayj-1)tmp = arrayj-1; arrayj-1 = arrayj; arrayj = tmp; /从前往后从前往后,即最先排好的是尾部即最先排好的是尾部void sortArray(int array, int n) int i, j, tmp; for(i=0;in-1;i+) for (j=0;jn-1-i;j+) if(arrayjarrayj+1) tmp = arrayj+1; arrayj+1 = arrayj; arrayj = tmp; 问题问题 4.2：另一种方法：另一种方法n在上述方法中，学生成绩一次全部
29、读入，然后再在上述方法中，学生成绩一次全部读入，然后再排序后输出。排序后输出。n还有一种方法为每读入一个数据，就将其加到一还有一种方法为每读入一个数据，就将其加到一个有序数据集中的相应位置上，无需最后个有序数据集中的相应位置上，无需最后排序排序。其具体算法如下：其具体算法如下：问题问题 4.2：另一种算法：另一种算法1.1.设整型数组设整型数组scorelistscorelist存放排序后成绩，存放排序后成绩，n n为其中学生成绩个数，初始为其中学生成绩个数，初始n n为为0 0；2.2.分别以读和写方式打开文件分别以读和写方式打开文件scorelist.inscorelist.in和和sco
30、relist.out;scorelist.out;3.while 3.while 读文件中还有成绩时，读入一个成绩到读文件中还有成绩时，读入一个成绩到scorescore将将scorescore插入到有序数组插入到有序数组scorelistscorelist中相应位置；中相应位置；4.4.输出数组输出数组scorelistscorelist到写文件中；到写文件中；5.5.关闭读写文件；关闭读写文件；设函数设函数void insertData(int array ,int data);将一个变量插入到有序（从大到小）数组将一个变量插入到有序（从大到小）数组array中中,插入后数组仍有序。插入后
31、数组仍有序。问题问题 4.2：函数：函数insertData算法算法l找到数组找到数组arrayarray中第一个比中第一个比datadata小的数组元素小的数组元素，设其下标为，设其下标为i i；l将下标大于等于将下标大于等于i i的所有数组元素向后移动一的所有数组元素向后移动一个位置；个位置；larrayi=data;arrayi=data;l数组元素个数数组元素个数n n加加1 1；数组实际元素个数需要在数组实际元素个数需要在insertData和和main函数中都用到，如何在程序中函数间函数中都用到，如何在程序中函数间共享数据共享数据？1）通过函数参数传递。但函数参数方式为）通过函数参
32、数传递。但函数参数方式为传值，若要通过函数调用改变实参的值，传值，若要通过函数调用改变实参的值，要用到要用到指针指针。2）通过）通过return语句返回值。注意只能返回语句返回值。注意只能返回一个值。一个值。3）使用）使用全局变量全局变量。问题问题 4.2：另一种代码实现：另一种代码实现/c4_2b.c#include #define NUM 200int N = 0;void insertData(int array, int data);int main() int scorelistNUM,score, i; FILE *in, *out; if(in = fopen(scorelist
33、.in,r) = NULL) printf(Cannt open file scorelist.in!n); return 1; if(out = fopen(scorelist.out,w) = NULL) printf(Cannt open file scorelist.out!n); return 1; while(fscanf(in,%d,&score )0)insertData(scorelist, score); for(i=0; iN; i+) fprintf(out, %dn,scorelisti); fclose(in); fclose(out); return 0;void
34、 insertData( int array , int data )int i, j;for( i=0; iarrayi)break;for( j=N; ji; j- )arrayj = arrayj-1;arrayi=data;N+;查找要插入的位置查找要插入的位置从插入位置开始所有元素向后移动一从插入位置开始所有元素向后移动一个元素。个元素。N为一个全局变量为一个全局变量 。全局变量访问全局变量访问外部变量外部变量*n外部变量（外部变量（global variable ）：在函数外面定义的）：在函数外面定义的变量。变量。l作用域（作用域（scope）为整个程序，即可在程序的所）为整个程序
35、，即可在程序的所有函数中使用。有函数中使用。l外部变量有隐含初值外部变量有隐含初值0。l生存期（生存期（life cycle）：外部变量（存储空间）：外部变量（存储空间）在程序执行过程中始终存在。在程序执行过程中始终存在。外部变量说明（外部变量说明（extern）*nC程序可以分别放在几个文件上，每个文件可作为程序可以分别放在几个文件上，每个文件可作为一个编译单位分别编译。一个编译单位分别编译。外部变量只需在某个文外部变量只需在某个文件上定义一次件上定义一次，其它文件其它文件若要引用此变量时，若要引用此变量时，应应用用extern加以说明加以说明。（外部变量定义时不必加。（外部变量定义时不必加
36、extern关键字）。关键字）。n在同一文件中，若前面的函数要引用后面定义的在同一文件中，若前面的函数要引用后面定义的外部（在函数之外）变量时，也应在函数里加以外部（在函数之外）变量时，也应在函数里加以extern说明。说明。外部变量说明（外部变量说明（extern）（续）（续）*n例如，对问题例如，对问题4.2的代码实现中，如果外部变量的代码实现中，如果外部变量N不在程序头部定义不在程序头部定义，则需要用，则需要用extern加以说明。加以说明。extern int N;int main()int N = 0;void insertData(int array, int data) 外部变量
37、定义外部变量定义 外部变量说明外部变量说明外部变量说明（外部变量说明（extern）（续）（续）*n使用外部变量的原因：使用外部变量的原因：l 解决函数单独编译的协调；解决函数单独编译的协调；l 与变量初始化有关；与变量初始化有关；l 外部变量的值是永久的；外部变量的值是永久的；l 解决数据共享；解决数据共享；n外部变量的副作用：外部变量的副作用：l使用外部变量的函数独立性差，通常不能使用在其他的使用外部变量的函数独立性差，通常不能使用在其他的程序中。而且，如果多个函数都使用到某个外部变量，程序中。而且，如果多个函数都使用到某个外部变量，一旦出现差错，就很难发现问题是由哪个函数引起的。一旦出现
38、差错，就很难发现问题是由哪个函数引起的。在程序中的某个部分引起外部变量的错误，很容易误以在程序中的某个部分引起外部变量的错误，很容易误以为是由另一部分引起的。为是由另一部分引起的。递归（递归（Recursion）*n通过调用自身解决问题的过程称为递归。递归是解决某些复通过调用自身解决问题的过程称为递归。递归是解决某些复杂问题的有效方法。如：杂问题的有效方法。如：001*1nnnnxxx11)!1(*1!nnnnn010) 1(*)(nnnfxnf111) 1(*)(nnnfnnf递归（续）递归（续）*例：求例：求n!#include int fact(int n);main( )printf(
39、“3!=%d, 5!=%dn”, fact(3), fact(5);int fact(int n) int res=0; if( n 0 ) hanoi(n-1, a, c, b);printf(“MOVE %d: %c %cn”, n, a, c);hanoi(n-1, b, a, c);main( )int n;printf(“Please input the number of hanoi tower:”);scanf(“%d”, &n);hanoi(n, A, B, C);BAC如果要移动如果要移动64个盘子个盘子,则移动次则移动次数为数为264-1.如果每秒移动一个盘如果每秒移动一个
40、盘子子,则需要约则需要约5*1011年年.一般认为一般认为地球的寿命为地球的寿命为50亿年亿年(约约5*109).以每秒以每秒10亿次的移动速度计算亿次的移动速度计算,约需要约需要500年年.问题问题4.3： 一个经典递归程序示例一个经典递归程序示例*问题问题4.4：生成全排列数：生成全排列数* 【问题描述问题描述】输入整数输入整数N( 1 = N = 10 )，生成从，生成从1N所有整数的全排列。所有整数的全排列。 【输入形式输入形式】输入整数输入整数N。【输出形式输出形式】输出有输出有N!行，每行都是从行，每行都是从1N所有整数的一个全排列，各整数之间以空格分隔。各行上的所有整数的一个全排
41、列，各整数之间以空格分隔。各行上的全排列不重复。输出各行遵循全排列不重复。输出各行遵循“小数优先小数优先”原则原则, 在各全排列中，较小的数尽量靠前输出。如果将每行在各全排列中，较小的数尽量靠前输出。如果将每行上的输出看成一个数字，则所有输出构成升序数列。具体格式见输出样例。上的输出看成一个数字，则所有输出构成升序数列。具体格式见输出样例。【样例输入样例输入1】3 【样例输出样例输出1】1 2 31 3 22 1 32 3 13 1 23 2 1【样例说明样例说明1】输入整数输入整数N=3，要求整数，要求整数1、2、3的所有全排列的所有全排列, 共有共有N!=6行。且先输出行。且先输出1开头的
42、所有排列开头的所有排列数，再输出数，再输出2开头的所有排列数，最后输出开头的所有排列数，最后输出3开头的所有排列数。在以开头的所有排列数。在以1开头的所有全排列中同样遵循此开头的所有全排列中同样遵循此原则。原则。【样例输入样例输入2】10 【样例输出样例输出2】1 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 10 91 2 3 4 5 6 7 9 8 101 2 3 4 5 6 7 9 10 81 2 3 4 5 6 7 10 8 91 2 3 4 5 6 7 10 9 8【样例说明样例说明2】输入整数输入整数N=10，要求整数，要求整数1、2、3、10的所有全排列。上
43、例显示了输出的前的所有全排列。上例显示了输出的前10行。行。 问题问题4.4：算法分析：算法分析*n对于对于N的全排列：的全排列：M MN NM MN-1N-1M Mn nM M1 1其中其中M Mn n的值应为的值应为1,2,1,2,N,N数字中不为数字中不为M MN NM MN-1N-1M Mn+1n+1的数字，并且应的数字，并且应从小到大取值。因此，可设一个数组从小到大取值。因此，可设一个数组int MarkNint MarkN用来分别标识用来分别标识一个数字是否已被使用。因此，对于一个数字是否已被使用。因此，对于生成生成M Mn n数字数字的算法如下：的算法如下：If(n=0)If(n
44、=0)/ /* *当前排列已生成当前排列已生成* */ /输出数字串输出数字串M MN NM MN-1N-1M Mn nM M1 1; ;结束；结束；for(i=1; i=N; i+)for(i=1; i=N; i+)If(Marki = 0) /If(Marki = 0) /* *表示该数字表示该数字i i未使用未使用* */ /Marki = 1; /Marki = 1; /* *数字数字i i将被使用将被使用* */ /将数字将数字i i放到全排列位置放到全排列位置n n上（即上（即M MN NM MN-1N-1M Mn n的的M Mn n ）生成生成M Mn-1n-1 数字；数字；Ma
45、rki = 0; /Marki = 0; /* *数字数字i i将被释放将被释放* */ /使用递归方法！使用递归方法！问题问题4.4：代码实现：代码实现*#include #define MAX 10int MarkMAX = 0; /*标记数组，用来标记某个数字是否已被使用成为标记数组，用来标记某个数字是否已被使用成为*/char StackMAX+1; /*全排列数字串全排列数字串*/void rank(int m, int n); /* m记录下一个要生成的全排列数字应放在记录下一个要生成的全排列数字应放在Stack中的位置，中的位置，n表示还剩几个数字需要表示还剩几个数字需要生成生成
46、*/int N;int main () scanf (%d, &N); rank(0,N); return 0;void rank(int m, int n)int i;if( n = 0) Stackm = 0;puts(Stack);/* 输出全排列数字串输出全排列数字串*/return;for(i=1; i=N; i+)if(Marki = 0 )Marki = 1; /* 标记该数字已被使用标记该数字已被使用*/Stackm = 0+i; /*将当前数字加到全排列数字串中将当前数字加到全排列数字串中*/rank(m+1,n-1); /* 生成全排列中下一个数字生成全排列中下一个数字 */Marki = 0;/*释放该数字释放该数字*/递归（续）：递归问题总结递归（续）：递归问题总结*p通常包含如下特性的问题适合应用递归方法解决通常包含如下特性的问题适合应用递归方法解决:问题包含一个问题包含一个(或多个或多个)基本实例，如基本实例，如 0! = 1问题的解可以简化为包含比当前问题更简单一问题的解可以简化为包含比当前问题更简单一步的问题的解，并且最终问题解可归结到基本步的问题的解，并且最终问题解可归结到基本实例，如实例，如 n! = n*(n-1)!, 0!=1。
