第四次上机实验内容-字符串排序.ppt
n字符串排序字符串排序 6 19 31(6 19 31(字符串一般排序）字符串一般排序）n（45 70 95 45 70 95 左右比较）左右比较）6868（指针）（指针）类型四类型四字符串排序字符串排序 函数函数ReadDatReadDat()()实现从文件实现从文件IN.DATIN.DAT中读取一篇英文文章存入到字符串数中读取一篇英文文章存入到字符串数组组xxxx中；请编制函数中；请编制函数SortCharASortCharA(),(),其函数的功能是其函数的功能是:以行为单位对以行为单位对字符按从小到大的顺序进行排序字符按从小到大的顺序进行排序,排序后的结果仍按行重新存入字符排序后的结果仍按行重新存入字符串数组串数组xxxx中。最后中。最后main()main()函数调用函数函数调用函数WriteDatWriteDat()()把结果把结果xxxx输出到文输出到文件件OUT.DATOUT.DAT中。中。例例:原文原文:dAe,BfCdAe,BfC.CCbbAACCbbAA 结果结果:,.:,.ABCdefABCdef AACCbbAACCbb 原始数据文件存放的格式是原始数据文件存放的格式是:每行的宽度均小于每行的宽度均小于8080个字符个字符,含标点含标点符号和空格。符号和空格。注意注意:部分源程序存放在部分源程序存放在PROG1.CPROG1.C中。中。请勿改动主函数请勿改动主函数main()main()、读数据函数、读数据函数ReadDatReadDat()()和输出数据函数和输出数据函数WriteDatWriteDat()()的内容。的内容。（0606套）套）#include#include#include#include char xx5080;char xx5080;unsigned unsigned intint maxlinemaxline=0;=0;/*/*文章的总行数文章的总行数*/intint ReadDat(voidReadDat(void););void void WriteDat(voidWriteDat(void););void void SortCharA(voidSortCharA(void)void main()void main()if(ReadDatif(ReadDat()()printfprintf(数据文件数据文件IN.DATIN.DAT不能打开不能打开!n007);!n007);return;return;SortCharASortCharA();();WriteDatWriteDat();();int ReadDat(void)FILE*fp;int i=0;char*p;if(fp=fopen(c:testIN.DAT,r)=NULL)return 1;while(fgets(xxi,80,fp)!=NULL)p=strchr(xxi,n);if(p)*p=0;i+;maxline=i;fclose(fp);return 0;void WriteDat(void)FILE*fp;unsigned int i;fp=fopen(c:testOUT.DAT,w);for(i=0;i maxline;i+)printf(%sn,xxi);fprintf(fp,%sn,xxi);fclose(fp);n本题的关键是对字符串进行排序本题的关键是对字符串进行排序n每行字符串存放在二维字符数组每行字符串存放在二维字符数组xxxx中中 需要解决的问题需要解决的问题 1 1、整个二维数组有多少行、整个二维数组有多少行 2 2、每行有多少字符、每行有多少字符编程点拨Maxline,循环的次数每次循环内，进行排序不是80，需通过strlen函数求得sryu0ebq0na0 xx0 xx1xx2strlen函数形参第0行字符个数strlen(xx)还是strlen(xx0)strlen(xx00)代码 void void SortCharA(voidSortCharA(void)char char chch;unsigned unsigned intint i,j,k,i,j,k,lenlen;for(ifor(i=0;i =0;i maxlinemaxline;i+);i+)maxline 是全局变量其值已经获得对maxline行进行排序for(j=0;j len-1;j+)for(k=j+1;k xxik)ch=xxik;xxik=xxij;xxij=ch;len=strlen(xxi)对第i行字符串进行排序先求得该行的字符个数用比较交换法对第i行字符串进行排序函数函数readDatreadDat()()是从文件是从文件in.datin.dat中读取中读取2020行数据存放到字符串数组行数据存放到字符串数组xxxx中中(每行字符串长度均小于每行字符串长度均小于80)80)。请编制函数。请编制函数jsSortjsSort(),(),其函数的功能是其函数的功能是:以行为单位对字符串变量的下标为奇数的位置上的字符按其以行为单位对字符串变量的下标为奇数的位置上的字符按其ASCIIASCII值值从小到大的顺序进行排序从小到大的顺序进行排序,下标为偶数的位置上的字符仍按原来位置下标为偶数的位置上的字符仍按原来位置存放存放,排序后的结果仍按行重新存入字符串数组排序后的结果仍按行重新存入字符串数组xxxx中中,最后调用函数最后调用函数writeDatwriteDat()()把结果把结果xxxx输出到输出到out.datout.dat文件中。文件中。例如例如:位置位置 0 1 2 3 4 5 6 70 1 2 3 4 5 6 7 源字符串源字符串 h g f e d c b ah g f e d c b a 则处理后字符串则处理后字符串 h a f c d e b gh a f c d e b g 注意注意:部分源程序存在文件部分源程序存在文件PROG1.CPROG1.C文件中。文件中。请勿改动数据文件请勿改动数据文件in.datin.dat中的任何数据、主函数中的任何数据、主函数main()main()、读函数、读函数readDatreadDat()()和写函数和写函数writeDatwriteDat()()的内容。（的内容。（1919套）套）#include#include#include#include void void readDatreadDat();();void void writeDatwriteDat();();char xx2080;char xx2080;void void jsSortjsSort()()void main()void main()readDatreadDat();();jsSortjsSort();();writeDatwriteDat();();void readDat()FILE*in;int i=0;char*p;in=fopen(c:testin.dat,r);while(i 20&fgets(xxi,80,in)!=NULL)p=strchr(xxi,n);if(p)*p=0;i+;fclose(in);void writeDat()FILE*out;int i;out=fopen(c:testout.dat,w);for(i=0;i 20;i+)printf(%sn,xxi);fprintf(out,%sn,xxi);fclose(out);n本题是要求对字符串中的字符按其本题是要求对字符串中的字符按其ASCIIASCII值值的升序进行排序。的升序进行排序。n对对2020行字符串进行排序，所以需要循环行字符串进行排序，所以需要循环2020次次 每次循环每次循环 实现一个字符串按奇数下标排序实现一个字符串按奇数下标排序 代码void void jsSortjsSort()()char char chch;intint i,j,k;i,j,k;for(ifor(i=0;i 20;i+)=0;i 20;i+)对20行字符串进行处理每行字符串按奇数下标排序for(j=1;j (int)strlen(xxi)-1;j+=2)for(k=j+2;k xxik)ch=xxik;xxik=xxij;xxij=ch;外循环j下标从1开始，步长为2内循环k从j+2开始，步长为2n字符串左右排序字符串左右排序 函数函数readDatreadDat()()是从文件是从文件in.datin.dat中读取中读取2020行数据存放到字符串数组行数据存放到字符串数组xxxx中中(每行字符串长度均小于每行字符串长度均小于80)80)。请编制函数。请编制函数jsSortjsSort(),(),其函数的功能是其函数的功能是:以行为单位对字符串按下面给定的条件进行排序以行为单位对字符串按下面给定的条件进行排序,排序后的结果仍按排序后的结果仍按行重新存入字符串数组行重新存入字符串数组xxxx中中,最后调用函数最后调用函数writeDatwriteDat()()把结果把结果xxxx输出输出到文件到文件out.datout.dat中。中。条件条件:从字符串中间一分为二从字符串中间一分为二,左边部分按字符的左边部分按字符的ASCIIASCII值降序排序值降序排序,右边部分按字符的右边部分按字符的ASCIIASCII值升序排序。如果原字符串长度为奇数值升序排序。如果原字符串长度为奇数,则则最中间的字符不参加排序最中间的字符不参加排序,字符仍放在原位置上。字符仍放在原位置上。例如例如:位置位置 0 1 2 3 4 5 6 7 80 1 2 3 4 5 6 7 8 源字符串源字符串 a b c d h g f ea b c d h g f e 1 2 3 4 9 8 7 6 5 1 2 3 4 9 8 7 6 5 则处理后字符串则处理后字符串 d c b a e f g hd c b a e f g h 4 3 2 1 9 5 6 7 8 4 3 2 1 9 5 6 7 8 注意注意:部分源程序存在文件部分源程序存在文件PROG1.CPROG1.C文件中。文件中。请勿改动数据文件请勿改动数据文件in.datin.dat中的任何数据、主函数中的任何数据、主函数main()main()、读函数、读函数readDatreadDat()()和写函数和写函数writeDatwriteDat()()的内容。（的内容。（4545套套)#include#include#include#include#include#include char xx2080;char xx2080;void void jsSortjsSort()()void main()void main()readDatreadDat();();jsSortjsSort();();writeDatwriteDat();();readDat()FILE*in;inti=0;char*p;in=fopen(in.dat,r);while(i20&fgets(xxi,80,in)!=NULL)p=strchr(xxi,n);if(p)*p=0;i+;fclose(in);writeDat()FILE*out();inti;clrscr();out=fopen(out.dat,w);for(i=0;i20;i+)printf(%sn,xxi);fprintf(out,%sn,xxi);fclose(out);需要编程实现需要编程实现n有有2020行，所以循环行，所以循环2020次次n每次循环完成：每次循环完成：n每行 左半部排序，左半部位置如何确定 xxixxi 指向第指向第i i行字符串，求长度行字符串，求长度 lenlen=strlen(xxistrlen(xxi)中间一分为二后，排中间一分为二后，排序的个数序的个数half=len/2half=len/2n左右半部分别排序 外循环下标和内循环下标如何确定1010202030301010404050506060n排序位置的确定排序位置的确定1010202030301010404050506060左半部分外循环从0开始右半部分：当字符串长度的奇数，外循环的下标strlen(xxi)/2+1当字符串长度的偶数，外循环的下标strlen(xxi)/2代码void void jsSortjsSort()()char char chch;intint i,j,k,i,j,k,lenlen,half;,half;for(ifor(i=0;i 20;i+)=0;i 20;i+)if(len%2)half+;len=(int)strlen(xxi);half=len/2;for(j=0;j (half-1);j+)for(k=j+1;k half;k+)if(xxij xxik)ch=xxik;xxik=xxij;xxij=ch;利用外循环for语句依次取出每行的字符串xxi。取字符串一半的位置half 再利用二重循环for语句对字符串的左边按降序排序。（交换方法）如果字符串xxi的长度是否是奇数，则half+指向下一字符，如果是偶数，则half值不变。for(j=half;j (len-1);j+)for(k=j+1;k xxik)ch=xxik;xxik=xxij;xxij=ch;再利用二重循环for语句对字符串的右边按升序排序 函数函数readDatreadDat()()是从文件是从文件in.datin.dat中读取中读取2020行数据存放到字符串数组行数据存放到字符串数组xxxx中中(每行字符串长度均小于每行字符串长度均小于80)80)。请编制函数。请编制函数jsSortjsSort(),(),其函数的功能是其函数的功能是:以行为单位对字符串按下面给定的条件进行排序以行为单位对字符串按下面给定的条件进行排序,排序后的结果仍按排序后的结果仍按行重新存入字符串数组行重新存入字符串数组xxxx中中,最后调用函数最后调用函数writeDatwriteDat()()把结果把结果xxxx输出输出到文件到文件out.datout.dat中。中。条件条件:从字符串中间一分为二从字符串中间一分为二,左边部分按字符的左边部分按字符的ASCIIASCII值降序排序值降序排序,右边部分不作处理，排序后，左边部分与右边部分按例子所示进行交右边部分不作处理，排序后，左边部分与右边部分按例子所示进行交换。如果原字符串长度为奇数换。如果原字符串长度为奇数,则最中间的字符不参加处理则最中间的字符不参加处理,字符仍放字符仍放在原位置上。在原位置上。例如例如:位置位置 0 1 2 3 4 5 6 7 80 1 2 3 4 5 6 7 8 源字符串源字符串 a b c d h g f ea b c d h g f e 1 2 3 4 9 8 7 6 5 1 2 3 4 9 8 7 6 5 则处理后字符串则处理后字符串 h g f e d c b ah g f e d c b a 8 7 6 5 9 4 3 2 1 8 7 6 5 9 4 3 2 1 注意注意:部分源程序存在文件部分源程序存在文件PROG1.CPROG1.C文件中。文件中。请勿改动数据文件请勿改动数据文件in.datin.dat中的任何数据、主函数中的任何数据、主函数main()main()、读函数、读函数readDatreadDat()()和写函数和写函数writeDatwriteDat()()的内容。的内容。70套n有有2020行，所以循环行，所以循环2020次次n每次循环完成：每次循环完成：n每行 左半部排序，左半部位置如何确定 xxixxi 指向第指向第i i行字符串，求长度行字符串，求长度 lenlen=strlen(xxistrlen(xxi)中间位置中间位置half=len/2half=len/2n左右半部交换1010202030301010404050506060代码void void jsSortjsSort()()intint i,len,half,j,ki,len,half,j,k;char char chch;for(ifor(i=0;i20;i+)/*=0;i20;i+)/*行循环行循环 i i行号行号*/分析分析:对每一行（对每一行（2020行）行）先采用冒泡法对左边部分进行升序先采用冒泡法对左边部分进行升序排序排序然后将排序后的左半与右半按对应然后将排序后的左半与右半按对应位进行调换。（位进行调换。（2020行，行，2020次循环）次循环）外循环外循环有有2020行，循环行，循环2020次次/half/half每行中间位置每行中间位置内循环内循环每行左半部降序交换排序每行左半部降序交换排序中间位置：中间位置：half=strlen(xxi/2)half=strlen(xxi/2)HalfHalf即排序的字符数即排序的字符数len=strlen(xxi);half=len/2;/中间位置for(j=0;jhalf-1;j+)/*每行的第j个位置*/for(k=j+1;khalf;k+)if(xxij=0;j-,k-)ch=xxij;xxij=xxik;xxik=ch;/交换
