作业|学习资料|算法|题解

程序设计-20161206

凝神长老 · 12月6日 · 2016年 923次已读

本文写于 2016年12月06日,距今已超过 1 年,距 2020年03月26日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


第十周的编程题是有史以来质量最高的一组题。

Lab10_01,EOJ3107。

这道题目出题是有歧义的,又或许是故意出成这样作为题目的难点,这一点下文会细说。

输入输出部分不难。

void input ( int* p, int n ) {
    for ( int i = 0; i < n; i++ ) {
        scanf ( "%d", p++ );
    }

    return;
}
void output ( int* p, int n ) {
    for ( int i = 0; i < n; i++ ) {
        printf ( "%d ", *p++ );
    }

    return;
}

输出部分,仍然是那个问题,最后一个数字后面没有空格,而是一个换行符。

关键在于Process()怎么写。

首先定义两个指针,min指向最小值所在的地址,max指向最大值所在的地址。

 int *min=p,*max=p;

然后逐次比较数组中的各个元素,如果某个数字比最小值小,那么min指向的地址变更为那个元素的地址,如果某个数字比最大值大,那么max指向的地址变更为那个元素的地址。需要注意的是,这里变动的是min和max指向的地址,也就是指针min和指针max的值,而不是min和max的值。

for ( int i = 0; i < n; i++ ) {
    if ( * ( p + i ) < *min ) {
        min = p + i;

    } else if ( * ( p + i ) > *max ) {
        max = p + i;
    }
}

全部比完以后,就是交换了,交换的操作与之前交换int a和int b的操作是一样的,只是这里变成了指针而已。

int t;
//临时变量
t = *min;
*min = *p;
*p = t;
//交换min
t = *max;
*max = * ( p + n - 1 );
* ( p + n - 1 ) = t;
//交换max

所以,Process()的完整代码是:

void process ( int* p, int n ) {
    int *min = p, *max = p;

    for ( int i = 0; i < n; i++ ) {
        if ( * ( p + i ) < *min ) {
            min = p + i;

        } else if ( * ( p + i ) > *max ) {
            max = p + i;
        }
    }

    int t;
    t = *min;
    *min = *p;
    *p = t;
    t = *max;
    *max = * ( p + n - 1 );
    * ( p + n - 1 ) = t;

    return;
}

可是,这样交上去是错的。

根据测试的结果来说,诸如 5 / 3 2 1 10 8 这样的数字,是能够得到正确答案的,但是对于 3 / 3 2 1 这样的数字,输出的结果是 3 2 1 不变。

Debug后可以发现,这是因为比较过程中确定了max指向3的地址、min指向1的地址,而3和1恰恰又是数组的第一个元素和最后一个元素,也就是我们最终需要存放最大值和最小值的地方。所以,结束循环以后,3和1交换,1和3交换,最终的结果看上去就像没交换一样,事实上不是没交换,而是交换过头了。

于是,我们需要在交换前再给一个判断条件。

if ( max == p ) {
    t = *p;
    *p = *min;
    * ( p + n - 1 ) = t;

} else {
    t = *min;
    *min = *p;
    *p = t;
    t = *max;
    *max = * ( p + n - 1 );
    * ( p + n - 1 ) = t;
}

除此而外,另外一个出题不严谨的地方——如果有两个最大(或者最小)数,应该和哪一个交换?

譬如输入的数字是 1 2 3 2 3 2 ,那么显然最小数是1,但是最大数有两个,应该把哪一个3交换到末尾呢?换句话说,究竟应该是 1 2 3 2 2 3 ,还是 1 2 2 2 3 3 ?

题目并没有说明,所以我们也不考虑了。

因为涉及到了指针,所以需要注意两点——第一,需不需要加上“*”;第二,是不是要加1、或者要减1。

Lab10_02,EOJ3109。

从第m位开始取,直到字符串结束,也就是从m位开始取strlen(s)-m位(或者认为strlen(s)-m+1位)。

于是,我们可以借用strncpy()这个函数。

根据上面的分析,可以先写出这样的代码:

strncpy(t,&s[m],strlen(s)-m);

取出s[]的第m位的地址,从这里开始取strlen(s)-m位,复制到t中。

但是,需要说明的一点是,strncpy()的第3个参数是size_t n,它的类型是size_t,但因为复制的是字符串,所以第3个参数写成strlen(s)-m完全可以,不过,最好还是要写成(strlen(s)-m)*sizeof(char)。

一种做法是,先把t[]全部初始化为0。

for (int i=0;i<=N;i++) t[i]=0;

第二种做法是,取strlen(s)-m取完整个字符串后再多取一位,那一位就应该是s的结束符,所以应该取strlen(s)-m+1位。

strncpy(t,&s[m],(strlen(s)-m+1)*sizeof(char));

这两种方法的完整代码是:

char* strmcpy ( char* t, char* s, int m ) {
    for ( int i = 0; i <= N; i++ ) t[i] = 0;

    strncpy ( t, &s[m], ( strlen ( s ) - m ) *sizeof ( char ) );
}

以及

char* strmcpy ( char* t, char* s, int m ) {
    strncpy ( t, &s[m], ( strlen ( s ) - m + 1 ) *sizeof ( char ) );
}

注:这里的函数没有写返回值,但是程序竟然能够正常运行,并且顺利通过OJ,这一点下文会说明。

需要注意的是,这种写法并不推崇。

当然,除此以外,也可以手动模拟Copy的过程,那就是一位一位地取出s的字符放进t中。

我直接在上面那种方法上改,改成这样,竟然无法运行。

char* strmcpy ( char* t, char* s, int m ) {
    for ( int i = 0; i < strlen ( s ) - m + 1; i++ ) {
        t[i] = s[m + i];
    }
}

自己检查之后发现,这个函数的返回值类型是char*,也就是一个数组,字符数组,可是我连return都没有写,程序当然不可能是对的。

于是加上return t,就对了。

char* strmcpy ( char* t, char* s, int m ) {
    for ( int i = 0; i < strlen ( s ) - m + 1; i++ ) {
        t[i] = s[m + i];
    }

    return t;
}

可是,为什么方法1和方法2没有错误呢?

我们仔细看一下strncpy()是怎么声明/定义的:

_CRTIMP char *  __cdecl strncpy(char *, const char *, size_t);

所以说,strncpy这个函数的返回类型就是char*,并且它返回值就是我们需要的那个目标字符串t。于是,当这句话执行的时候,后面即使没有return,也相当于给出了一句return t,函数能够正常结束。

上文说到了这种写法不推崇,那么推荐的写法是:

char* strmcpy ( char* t, char* s, int m ) {
    strncpy ( t, &s[m], ( strlen ( s ) - m + 1 ) *sizeof ( char ) );
    return t;
}

当然,也可以把return合并到上面一行。

char* strmcpy ( char* t, char* s, int m ) {
    return strncpy ( t, &s[m], ( strlen ( s ) - m + 1 ) *sizeof ( char ) );
}

再看看方法3,对于这种方法来说,for循环哪来的返回值?所以不写return是绝对不行的。

其实,这里的for循环写成这样也是可以的:

for ( int i = 0; i <= N; i++ )

于是就可以写出第4种代码:

char* strmcpy ( char* t, char* s, int m ) {
    for ( int i = 0; i <= N; i++ ) {
        t[i] = s[m + i];
    }

    return t;
}

因为两个数组的长度都是一样的,所以在超出有效下标之前一定会遇到字符串结束符,所以这里可以写N。

既然这里可以写N,那么第2种方法的strncpy()也可以写成strcpy()吗?当然!但是不得不再次强调,strcpy()是不安全的函数,一种良好的习惯是无论何时都用strncpy()而不是strcpy(),因此这里全部采用的是strncpy()。

Lab10_03,EOJ3019。

这道题的难度就更小了,也是这次题目中最简单的一题。

char*  CharsReplace ( char *p ) {
    char*op = p;

    while ( *p ) {
        *p = *p + 1;

        if ( *p > 'Z' ) *p = 'A';

        p++;
    }

    return op;
}

这里需要说明一点,一开始我也写错了,写成了:

char*  CharsReplace ( char *p ) {

    while ( *p ) {
        *p = *p + 1;

        if ( *p > 'Z' ) *p = 'A';

        p++;
    }

    return p;
}

仔细想想看,后一位字母处理完了,Z到A也处理完了,于是p也指向了最后,这时返回p,怎么可能是对的呢?

所以我们需要在一开始保留下p最初的值,也就是数组第一个元素的地址,保存到op中,最后返回op。

Lab10_04,EOJ3108。

主要思路是,那最后m位保留到一个新的数组前m位,然后新的数组从m位开始后面每一位依次是原来数组的第0位开始往后。

这里最难的一点,是计算下标,下标到底是n-m,还是n-m+1,还是n-m-1,又或者是i-(n-m)等等。这里最好画个图,任意找一种特值代入检验。

这个搞定了,其他就没有难度了。

void rotate(int* p, int n, int m){
int b[N];
for (int i=n-m;i<n;i++){
    b[i-(n-m)]=p[i];
}
for (int i=0;i<n-m;i++){
    b[i+m]=p[i];
}
for (int i=0;i<n;i++){
    p[i]=b[i];
  }
}

最后一个for循环时把b[]重新放到p[]里面。

0 0 投票
文章评分
订阅评论动态
提醒
guest
1 评论
最新
最旧 得票最多
行内反馈
查看所有评论
sscjwdyzdw
sscjwdyzdw
2016年12月8日 15:18

第二条用指针怎么写啊