Slide Title,Body Text,Second level,Third level,Fourth level,Fifth level,C程序设计基础,*,Slide Title,Body Text,Second level,Third level,Fourth level,Fifth level,高级语言程序设计,(,一,),(C Programming),第四讲：程序设计方法,-,模块化与算法设计,高级语言程序设计(一)(C Programming)第四讲,本章目标,进一步掌握模块化设计思想,掌握常用的数据查找及排序方法,了解全局变量,了解递归程序设计思想,本章目标进一步掌握模块化设计思想,问题,4.1,【,问题描述,】,从文件中查找包含给定字符串的行。,【,输入形式,】,从标准输入中分两行分别输入被查找的文件及要查找的字符串（中间不含空格）。,【,输出形式,】,在屏幕上输出文件中包含给定字符串的行。,【,样例输入,】,在键盘输入如下文件名及字符串,:,test.txt,the,文件,test.txt,内容如下：,Now is the time,for all good,men to come to the aid,of their party,【,样例输出,】,屏幕输出为：,this is the time,men to come to the aid,of their party,问题4.1【问题描述】,问题,4.1,：算法设计,设,int index(char s,char t ),函数用来在字符串,s,中查找字符串,t,。若找到则反回,t,在,s,中出现的位置，否则返回,-1,。其主要查找算法如下：,0,1,2,0,输入串,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,中每次开始比较的位置。,不同时,break,；找到的条件是：,tk=0,问题4.1：算法设计设 int index(char s,问题,4.1,：算法设计（续）,主要算法如下：,设变量,filename,s,line,分别用于存储文件名、查找串及文件中一行；,从标准输入中读入文件名和要查找的串到,filename,和,s,中；,以读方式打开文件,filename,；,while,文件中还有内容时读一行到,line,中,如果,index(line,s)=0,输出,line;,如何从文件中读入一行？,char *fgets(char *s,int n,FILE *fp),从,fp,上最多读入,n-1,个字符，放入,s,字符数组中。返回,s,，到达文件尾部返回,NULL,。,利用,fgets,从标准输入读取,一行字符串放在字符数组,s,中，,s,的大小是,101,：,fgets(s,101,stdin);,问题4.1：算法设计（续）主要算法如下：如何从文件中读入一行,问题,4.1,：代码实现,#include,#define MAXLINE 1000,int 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(index(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 j+,k+),;,if(tk=0),return(i);,return(-1);,使用,scanf,的缺点是不能输入带空格的字符串。可换成,gets(s);,来实现查找带空格的字符串。,由于打开一个文件操作可能失败，因此，好的风格应判断,fopen,函数的返回值，进行错误处理。,注意：由于上述循环当没有相应匹配字符时也退出。因此，要依据,t,中所有字符都匹配（即,tk=0,）来判断查找是否成功。,问题4.1：代码实现#include in,问题,4.1,：测试,当要查找的文件为“,test.txt,”,要查找的串为”,the”,，且文件,test.txt,中内容为：,Now is the time,for all good,men to come to the aid,of their party,则屏幕输出：,this is,the,time,men to come to,the,aid,of,the,ir party,问题4.1：测试当要查找的文件为“test.txt”,要查找,问题,4.1,：测试（续）,其它考虑点：,要查找的串在一行的头、尾,要查找的串在文件中不存在,问题4.1：测试（续）其它考虑点：,问题,4.1,：思考,1,问题,4.1,实现了大小写相关的字符串查找，即字符串“,the,”和“,The,”是不同字符串。请实现,大小写无关,的字符串查找。,算法分析：,在比较字符时，可将比较字符均转换为小写或大写既可实现大小写无关查找。,设函数,char tolower(char c),用于将字符,c,转换为相应小写字符，则上面,index,可改为：,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：思考1问题4.1实现了大小写相关的字符串查找，即,问题,4.1,：函数,tolower,实现,方法一：,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);,注意：,宏定义名与参数间不能有空格，如,max(A,B);,参数应用括号括起来，如,(A)(B)?(A):(B),#define isupper(c)(c=A&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：思考1（代码实现）#include stdio,问题,4.1,：思考,2,其它实现方法？,问题,4.1,中,index,只能查找的是子字符串的首次出现。请考虑如何查找子字符串的最后一次出现？,如果要查找一个字符串在一个文件中的出现次数，或查找一个字符串在一个文件中的所有出现行列位置，如何实现？（注意，,index,只能查找子字符串首次出现，如果一行中有多个子字符串怎样办？）,问题4.1：思考2其它实现方法？,问题,4.2,【,问题描述,】,某班有不超过,200,名的学生，从文件中输入某班学生成绩，对输入成绩按由高到低进行排序，并输出到另一个文件中。,【,输入形式,】,从文件,scorelist.in,中读入学生成绩，学生成绩以整数形式按行存放。注意，学生成绩数目不确定。,【,输出形式,】,将排序结果按行写到文件,sorelist.out,中。,【,样例输入,】,若文件,scorelist.in,中有如下成绩,:,58,75,62,86,98,【,样例输出,】,程序运行结束后文件,scorelist.out,中内容为：,98,86,75,62,58,问题4.2【问题描述】,问题,4.2,：算法分析,问题可分解为如下几个部分：,算法：,int socrelistNUM,n=0;,while(!,feof,(in),fscanf,(,in,“%d”,函数,feof,用来测试是否已读写到文件尾,若到文件尾,则返回,1,否则返回,0,。,函数,fscanf,用来从文件中读数据。与标准输入,scanf,不同的是第一个参数为文件指针。,算法：,for(i=0;in;i+),fprintf,(,out,“%d“,scorelisti);,函数,fprintf,用来从文件中读数据。与标准输入,printf,不同的是第一个参数为文件指针。,算法：,设一个函数专门用来对学生成绩进行排序，函数原型为：,void sortScore(int list,int len),从文件中读入学生成绩,对学生成绩排序,输出排序后成绩到文件中,打开输入,/,输出文件,算法：,FILE*in,*out;,in=fopen(“scorelist.in”,“,r,”);,out=fopen(“scorelist.out”,”,w,”);,问题4.2：算法分析算法：算法：算法：从文件中读入学生成绩对,问题,4.2,：算法分析,-,选择排序（续）,有许多经典的算法用来对数据进行排序，如选择排序（,selection sort,）、插入排序（,insertion sort,）和快速排序（,quick sort,）等。有关排序算法及分析主要在,数据结构,课程中讲授。,在问题,4.2,中将使用,选择排序,算法对学生成绩进行排序。,问题 4.2：算法分析-选择排序（续）有许多经典的算法用来,问题,4.2,：算法分析,-,选择排序（续）,选择排序的核心思想是先通过找到,数组中未排序部分的最大元素,，然后将其,移到未排序部分的最前端来,排序一个数组（从大至小排序）。即首先在整个数组中查找最大元素，将其换到第一个位置；然后从数组中第二个元素开始查找最大元素，以此类推。下面以图示来说明：,问题 4.2：算法分析-选择排序（续）选择排序的核心思想是,问题,4.2,：算法分析,-,选择排序（续）,16,30,24,7,25,62,45,5,65,50,1,0,3,2,4,6,5,8,7,9,未排序,最大元素,交换,65,30,24,7,25,62,45,5,16,50,1,0,3,2,4,6,5,8,7,9,未排序,最大元素,交换,65,62,24,7,25,30,45,5,16,50,1,0,3,2,4,6,5,8,7,9,问题 4.2：算法分析-选择排序（续）1630247256,问题,4.2,：算法分析,-,选择排序（续）,选择排序包括以下步骤：,找到最大元素,将最大元素移到未排序部分的第一个位置上,index=0;,for(i=1;iN;i+),if(arrayindex arrayi),index=i;,通过交换两个元素即可。如：,int tmp;,tmp=arrayi;,arrayi=arrayindex;,arrayindex=tmp;,问题 4.2：算法分析-选择排序（续）选择排序包括以下步骤,问题,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=arrayindex;,arrayindex=tmp;,找最大元素,将最大元素移到未排序部分的头部,问题 4.2：代码实现（排序函数）void sortArra,问题,4.2,：代码实现（主函数）,#include,#de