C语言每日一题之No.9

再做决定之前，我还是做好自己该做的。我不希望几年后会悔恨自己为什么在最该努力的时候不愿意吃苦。尊敬的女王陛下，请接题：

一.题目：有已按升序排好顺序的字符串a，编写程序将字符串s中的每个字符按升序的规则插到字符串a中，最后输出”abdefghjkmnptwy”。

二.思路：既然是已经排好序的，就用二分法查找的思想

将字符串s中的每个字符依次作为key拿来和字符串a做比较并且插入

三.程序

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 #define SIZE 50
 5 
 6 void InsertStr(char *s,char *a,int low,int high)
 7 {
 8     int mid = 0;
 9 
10     while(*a)
11     {  
12        mid = (low+high)/2;
13 
14        //当mid位置字符<*a<mid+1位置字符或者mid位置字符等于*a时
15        if((s[mid]<*a) && (s[mid+1]>*a) || s[mid]==*a)
16        {
17            for(int j=mid+1;*(s+j);j++)
18            { 
19                s[j] = *a;//把*a插入到字符串s中mid+1的位置
20                s[j+2]=s[j+1];//并且字符串s从mid+2开始的位置全部往后挪一个位置  
21                high = high +1;//若每插入一个*a字符，则右区间要加1
22            }
23        }
24        else if(s[mid] >*a)
25        { //若mid位置对应的字符大于*a,则右区间变为mid  
26            high = mid;
27            InsertStr(s,a,low,high);
28        }
29        else if(s[mid] <*a)
30        { //若mid位置对应的字符小于*a,则左区间变为mid 
31            low = mid;
32            InsertStr(s,a,low,high);
33        
34        }
35 
36        a++;
37     }
38 
39 
40 }
41 
42 
43 int main(void)
44 {
45     char s[SIZE]={0};
46     char a[SIZE]={0};
47     
48     printf("Please input the s string:
");
49     scanf("%s",s);
50     printf("Please input the a string:
");
51     scanf("%s",a);
52 
53     InsertStr(s,a,0,strlen(s));
54     printf("%s",s);
55 
56     return 0;
57 
58 }

三.编译运行

程序出错

四.分析问题

1.在插入字符串那个if条件语句里，犯了一个错误：往后面挪的时候，前面的已经把后面的覆盖了，比如a[6]=a[5],然后a[7]=a[6],看到没，这个时候a[6]已经被a[5]覆盖了，它再往后挪都不是自己原来的值了，所以要从最后面开始挪，这样才不会被覆盖。

2.*a可以肯定的是插在s[mid+1]的位置，所以直接s[mid+1]=*a;//把*a插入到字符串s中mid+1的位置就可以了，不然s[mid+1]的值会被*a覆盖

3.每插入一个字符都需要重新获取high

五.程序

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 #define SIZE 50
 5 
 6 void InsertStr(char *s,char *a,int low,int high)
 7 {
 8     int mid = 0;
 9 
10     while(*a)
11     {  
12        
13        mid = (low+high)/2;
14 
15        //当mid位置字符<*a<mid+1位置字符或者mid位置字符等于*a时
16        if((s[mid]<*a) && (s[mid+1]>*a) || s[mid]==*a)
17        {
18            for(int j=strlen(s)-1;j>=mid+1;j--)
19            { 
20                s[j+1]=s[j];//并且字符串s从mid+2开始的位置全部往后挪一个位置   
21            }
22            s[mid+1]=*a;//把*a插入到字符串s中mid+1的位置
23            
24        }
25        else if(s[mid] >*a)
26        { //若mid位置对应的字符大于*a,则右区间变为mid  
27            high = mid;
28            InsertStr(s,a,low,high);
29        }
30        else if(s[mid] <*a)
31        { //若mid位置对应的字符小于*a,则左区间变为mid 
32            low = mid;
33            InsertStr(s,a,low,high);
34        
35        }
36 
37        a++;
38        high =strlen(s);//每个字符串a都要重新获取s字符串的长度
39     }
40 
41 
42 }
43 
44 
45 int main(void)
46 {
47     char s[SIZE]={0};
48     char a[SIZE]={0};
49     
50     printf("Please input the s string:
");
51     scanf("%s",s);
52     printf("Please input the a string:
");
53     scanf("%s",a);
54 
55     InsertStr(s,a,0,strlen(s));
56     printf("%s",s);
57 
58     return 0;
59 
60 }

还是无法跳出InsertStr()函数，突然记起来要在函数末尾加一个return

1        a++;
2        high =strlen(s);//每个字符串a都要重新获取s字符串的长度
3     }
4 
5     return;
6 }

真的可以跳出来了，但是却还是有问题，现在这样的运行结果是

六.到底哪里出了问题呢？

七.给出网上的解答版本

 1 #include<stdio.h>
 2 #include<string.h>
 3 void main()
 4 {
 5         char a[20]="bdfhjmptwy";        //升序
 6         char s[ ]="ganke";
 7         char *p1=a,*p2=s,*p=NULL;
 8         while(*p2)
 9         {
10             while(*p1)
11             {
12                 if(*p2>*p1) p1++;
13                 else break;//要有出口！！！！
14             }
15             p=p1;//保存指针的位置！！！
16             while(*p1) p1++;
17             while(p1!=p)
18             {
19                 *(p1+1)=*p1;
20                 p1--;
21             }
22             *(p1+1)=*p1;
23             *p=*p2;
24             p2++;
25             p1=a;//指针复原很重要！！！！
26         }
27         puts(a); 
28 }

八.对比

那，鉴于你有这样的毅力，明天犒劳你一个又红又脆的苹果+一盒特仑苏纯牛奶哇~