1 算法与程序实践习题 解 答 3字符串处理字符串在程序设计中特别在ACM 比赛中引用的非常广泛，尤其是在输入输出当中，下面来介绍一些操作字符串的函数和方法：#include /C+ 的头文件#include /C 语言的头文件字符、字符串的输入输出char c; char *str=new char; scanf( “%c ” ,c) printf(“%c ”,c); scanf( “%s ” str); /以“空格”作为间隔符； printf(“%s ”,str); cinstr;/以“空格”作为间隔符； cout #include int main() int n; int i; char str1001; int characters26; / 用来存储每个字符出现的次数,下标和字母对应，0-a int pos=0; /用来存储出现次数最多的那个字符的下标/ freopen(“in.txt“,“r“,stdin); scanf(“%d“, while(n-) for(i=0;icharacterspos) pos=i; printf(“%c %dn“,pos+a,characterspos); return 0; CS32 ：487-3279 （来源： poj.grids.cn 2974，程序设计导引及在线实践（李文新）例4.3 P107 ）问题描述：企业喜欢用容易被记住的电话号码。让电话号码容易被记住的一个办法是将它写成一个容易记住的单词或者短语。例如， 你需要给滑铁卢大学打电话时，可以拨打TUT-GLOP 。有时，只将电话号码中部分数字拼写成单词。当你晚上回到酒店，可以通过拨打310-GINO 来向 Ginos 订一份 pizza。让电话号码容易被记住的另一个办法是以一种好记的方式对号码的数字进行分组。通过拨打必胜客的“三个十”号码3-10-10-10，你可以从他们那里订pizza。电话号码的标准格式是七位十进制数，并在第三、 第四位数字之间有一个连接符。电话拨号盘提供了从字母到数字的映射，映射关系如下：A、B 和 C 映射到 2 D、E 和 F 映射到 3 G、H 和 I 映射到 4 J、K 和 L 映射到 5 M、 N 和 O 映射到 6 P、R 和 S 映射到 7 T、U 和 V 映射到 8 W、X 和 Y 映射到 9 Q 和 Z 没有映射到任何数字，连字符不需要拨号，可以任意添加和删除。TUT-GLOP的标准格式是888-4567， 310-GINO的标准格式是310-4466，3-10-10-10的标准格式是310-1010。 如果两个号码有相同的标准格式，那么他们就是等同的（相同的拨号）。你的公司正在为本地的公司编写一个电话号码薄。作为质量控制的一部分，你想要检查是否有两个和多个公司拥有相同的电话号码。输入：输入的格式是，第一行是一个正整数，指定电话号码薄中号码的数量（最多100000） 。余下的每行是一个电话号码。每个电话号码由数字，大写字母（除了Q 和 Z）以及连接符5 组成。每个电话号码中只会刚好有7 个数字或者字母。输出：对于每个出现重复的号码产生一行输出，输出是号码的标准格式紧跟一个空格然后是它的重复次数。 如果存在多个重复的号码，则按照号码的字典升序输出。如果输入数据中没有重复的号码，输出一行：No duplicates. 样例输入：12 4873279 ITS-EASY 888-4567 3-10-10-10 888-GLOP TUT-GLOP 967-11-11 310-GINO F101010 888-1200 -4-8-7-3-2-7-9- 487-3279 样例输出：310-1010 2 487-3279 4 888-4567 3 解题思路：为了便于记忆，将电话号码翻译成单词、短语，并进行分组。同一个电话号码，有多种表示方式。为判断输入的电话号码中是否有重复号码，要解决两个问题。(1)将各种电话号码表示转换成标准表示：一个长度为8 的字符串，前三个字符是数字、第4 个字符是 -、后四个字符是数字。(2)根据电话号码的标准表示，搜索重复的电话号码。办法是对全部的电话号码进行排序，这样相同的电话号码就排在相邻的位置。此外， 题目也要求在输出重复的电话号码时，要按照号码的字典升序进行输出。用一个二维数组telNumbers1000009 来存储全部的电话号码，每一行存储一个电话号码的标准表示。每读入一个电话号码，首先将其转换成标准表示，然后存储到二维数组telNumbers 中。全部电话号码都输入完毕后，将数组telNumbers 作为一个一维数组，其中每个元素是一个字符串，用C/C+ 提供的函数模板qsort 对进行排序。用字符串比较函数strcmp 比较 telNumbers 中相邻的电话号码，判断是否有重复的电话号码、并计算重复的次数。参考程序：#include #include #include 6 char map=“22233344455566677778889999“;/ 为了统一处理， 这里把 Q 和 Z 也编在这里， 因此会有 4 个 7 char str80,telNumbers1000009; /为函数模板sort 定义数组元素的比较函数int compare(const void * elem1,const void *elem2) return(strcmp(char *)elem1,(char *)elem2); void standardizeTel(int n) int j,k; j=k=-1; while(k=A noduplicate=false; if(noduplicate) printf(“No duplicates.n“); return 0; 实现技巧：(1)用一个字符串map表示从电话拨号盘的字母到数字的映射关系：mapj 表示字母 j+A 映射成的数字。将输入的电话号码转换成标准形式时，使用map将其中的字母转换成数字，简化程序代码的实现。刚开始学习写程序时，常常不习惯用数据结构来表示问题中的事实和关系， 而容易用一组条件判断语句来实现这个功能。虽然也能够实现，但程序代码看起来不简洁，也容易出错。(2)尽量使用 C/C+ 的函数来完成程序的功能，简化程序代码的实现。在这个程序中，使用函数模板 sort进行电话号码的排序；使用字符串比较函数strcmp查找重复的电话号码。(3)对程序进行模块化，把一个独立的功能作为一个函数，并用一个单词、短语对函数进行命名。上面的参考程序中，对电话号码标准化是一个独立的功能，最好定义一个函数standardizeTel，使得整个程序的结构清晰、简洁、易读。不同的程序模块需要共同访问的数据，作为全局变量，即可简化函数的参数接口，又可以降低函数调用的参数传递开销。例如在上面的参考程序中，数组map和telNumbers都作为全局变量。常见错误在输出中，要注意输出数据的格式要求、区分输出数据中的字母大小写：(1)输出重复电话号码时，要按照标准格式输出：电话号码的前三位数字和后四位数字之间，有一个字符-。8 (2)无重复电话号码时，输出提示信息“No duplicates.“ ，问题要求提示信息的第一个字母要大写。CS33 ：子串（来源： poj.grids.cn 2744，程序设计导引及在线实践（李文新）例4.4 P112 ）问题描述：现在有一些由英文字符组成的大小写敏感的字符串，你的任务是找到一个最长的字符串x，使得对于已经给出的字符串中的任意一个y，x或者是 y的子串，或者x中的字符反序之后得到的新字符串是y的子串。输入：输入的第一行是一个整数t(1 #include int t,n; char str100101; / 下面给出了strrev的实现，这个在vc 中的 string.h已经定义了，但在GCC/G+ 中没有#if !defined(_linux_) #define _strrev strrev #endif char* strrev(char* szT) if ( !szT ) / 处理传入的空串. return “; int i = strlen(szT); int t = !(i%2)? 1 : 0; / 检查串长度 . for(int j = i-1 , k = 0 ; j (i/2 -t) ; j- ) char ch = szTj; szTj = szTk; szTk+ = ch; return szT; int searchMaxSubString(char * source) /搜索最大子串 int subStrLen=strlen(source),sourceStrLen=strlen(source); int i,j; bool foundMaxSubStr; char subStr101,revSubStr101; /子串和反转后的子串while(subStrLen0) /搜索不同长度的子串，从最长的子串开始 for(i=0;i #include void decipher(char message); int main() char message201; gets(message); while(strcmp(message,“START“)=0) decipher(message); printf(“%sn“,message); gets(message); return 0; void decipher(char message) char plain27=“VWXYZABCDEFGHIJKLMNOPQRSTU“; char cipherEnd201; int i,cipherLen; gets(message); cipherLen=strlen(message); for(i=0;i=A char message101,tmp101; char source101,dest101; / freopen(“in.txt“,“r“,stdin); scanf(“%d“, getchar(); /取走 n后换行符while(n-) gets(message); /获取第一个字串/去掉空格j=0; for(i=0;messagei!=0;i+) 14 if(messagei!= ) sourcej+=messagei; sourcej=0; gets(message); /获取第二个字串/去掉空格j=0; for(i=0;messagei!=0;i+) if(messagei!= ) destj+=messagei; destj=0; /忽略大小写进行比较if(stricmp(source,dest)=0) printf(“YESn“); else printf(“NOn“); gets(tmp);/获取空行，不做任何处理 return 0; /需要注意的是如果使用GCC/G+ 编译器，则需要增加stricmp函数的定义int stricmp(const char *str1,const char *str2) char *p1,*p2; int i=0,len=0; if(str1=NULL) if(str2!=NULL) return -1; if(str2=NULL) return 0; p1=str1; p2=str2; len=