算法竞赛入门经典Chap5笔记

65 阅读 0 评论 43 点赞

我是靠谱客的博主沉静小懒猪，最近开发中收集的这篇文章主要介绍算法竞赛入门经典Chap5笔记，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

5.1.1 wertyu

把手放在键盘上时，稍不注意就会往右错一位。这样的话，Q会变成W，J会变成K等。输入一个错位敲出的字符串，输出打字员本来想打出的句子。

样例输入：O S,GOMR YPFSU/

样例输出：I AMFINE TODAY.

  #include 
   
   
    
    
   int main(){
           char* s="`1234567890-=qwertyuiop[]\asdfghjkl;'zxcvbnm,./";
           int c;
           int i;
           while((c=getchar())!=EOF){
                   for(i=0;s[i]&&s[i]!=c;i++);
                   if(s[i]==c)
                           putchar(s[i-1]);
                  else
                          putchar(c);
          }
          return 0;
  }

总结：

1. for(i=0;s[i]&&s[i]!=c;i++); 内含退出循环的两种情况：1，s[i]==c,即在数组中找到了输入的字符。2，遍历数组后仍未找到字符，即s[i]为空（因为在字符数组里，存在的C语言方法，如strlen(s)，计算字符串的长度，其中s为指针，strlen要计算字符串长度，必须知道哪里是结尾，因此使用表示结尾。只有字符数组才有的概念，其它类型(int)的数组没有这个概念。因为其他类型的数组或者指针，没有strlen这种方法，而字符数组尾巴上的这个位置正好可以做哨兵。）

2. i的作用域不限于for循环，并且循环体为空，循环的目的就是找到合适的i；

3. getchar() 的返回值是输入的字符的ASCII码。

5.2.1小学生算数

要求程序能连续处理多组数据，直到读到两个0作为结束标记。

while(scanf(%d%d,&a,&b)==2){

}

总结：scanf函数的返回是正确输入的个数，如果遇到数据类型不符的输入，将不计数并退出，遇到输入结束标志，将返回-1，使用这种循环条件的好处是，确保输入内容是符合题目要求的数据类型。

5.3.2字母重排

   #include 
    
    
     
     
   #include 
     
     
      
      
   #include 
      
      
       
       
   char word[2000][10];
   char sorted[2000][10];
   int cmp_string(const void *_a, const void *_b){
           char *a=(char*) _a;
           char *b=(char*) _b;
           return strcmp(a,b);
  }
  int cmp_word(const void *_a, const void *_b){
        char *a=(char*) _a;
          char *b=(char*) _b;
          return *a>*b;
  }
  
  int main(){
          int n=0;
          while(1){
                  scanf("%s",word[n]);
                  if(word[n][0]=='*')
                          break;
                  n++;
          }
          qsort(word,n,sizeof(word[0]),cmp_string);
          for(int i=0;i

 
  
  总结： 
  
  
  1 qsort函数的四个参数分别是（起始地址，元素个数，每个元素的大小，比较函数）；比较函数的形参里不要遗漏const，两个参数均为void类型指针。 
  
  
  2 n为元素个数，26行处的循环，新设变量i来限制循环次数，不要用while(n){n--;}，因为while后面还要用。