C语言程序设计第二版课后习题--第三章

部分答案参考了网络上的答案和官方题解。代码在gitee上面。

exercise3-1

在上面有关折半查找的例子中，while 循环语句内共执行了两次测试，其实只要一次就足够（代价是将更多的测试在循环外执行）。重写该函数，使得在循环内部只执行一次测试。比较两种版本函数的运行时间。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h>
#include <time.h>

int binsearch(int x, int v[], int n)
{
    int low, mid, high;
    low = 0;
    high = n - 1;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (x < v[mid])
            high = mid - 1;
        else if (x > v[mid])
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}

int binsearch2(int x, int v[], int n)
{
    int low, high, mid;
    low = 0;
    high = n - 1;
    mid = (low + high) / 2;
    while (low <= high && v[mid] != x)
    {
        if (v[mid] > x)
            high = mid - 1;
        else
            low = mid + 1;
        mid = (low + high) / 2;
    }
    if (v[mid] == x)
        return mid;
    return -1; /* no match */
}

int main()
{
    int n = 200, testtime = 1000000;
    int data[n];
    for (int i = 0; i < n; i++)
        data[i] = i;
    int x = n / 2;

    clock_t start, end;
    start = clock();
    for (int i = 0; i < testtime; i++)
        binsearch(x, data, n);
    end = clock();
    printf("binsearch time: %lf seconds\n", (double)(end - start) / CLOCKS_PER_SEC);

    start = clock();
    for (int i = 0; i < testtime; i++)
        binsearch2(x, data, n);
    end = clock();
    printf("binsearch2 time: %lf seconds\n", (double)(end - start) / CLOCKS_PER_SEC);
}

运行：

经过六次测试，在数组元素个数为200，运行次数为100万的条件下，两种方法其实并无多大差异，在六次测试中，优化后的方法消耗时间更少的次数为4次。

binsearch	binsearch2
0.024170	0.024276
0.024337	0.019407
0.025760	0.020651
0.023006	0.017759
0.022969	0.016554
0.020334	0.025866

exercise3-2

编写一个函数 escape(s, t)，将字符串 t 复制到字符串 s 中，并在复制过程中将换行符、制表符等不可见字符分别转换为\n、\t 等相应的可见的转义字符序列。要求使用 swich 语句。再编写一个具有相反功能的函数，在复制过程中将转义字符序列转换为实际字符。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdio.h>
#include <string.h>

#define MAXLENGTH 1024

void getString(char t[]) {
    int i = 0, c;
    while ((c = getchar()) != EOF)
        t[i++] = c;
}

// 将换行符、制表符等不可见字符分别转换为\n、\t 等相应的可见的转义字符序列
void escape(char s[], char t[]) {
    int len = strlen(t);
    int i = 0, j = 0;

    while (i < len) {
        switch (t[i]) {
        case '\n':
            s[j++] = '\\';
            s[j++] = 'n';
            i++;
            break;
        case '\t':
            s[j++] = '\\';
            s[j++] = 't';
            i++;
            break;
        case '\v':
            s[j++] = '\\';
            s[j++] = 'v';
            i++;
            break;
        default:
            s[j++] = t[i++];
        }
    }
}

// 将转义字符序列转换为实际字符
void enter(char s[], char t[]) {
    int len = strlen(t);
    int i = 0, j = 0;
    while (i < len) {
        if (t[i] == '\\') {
            switch (t[i + 1]) {
            case 'n':
                s[j++] = '\n';
                i += 2;
                break;
            case 't':
                s[j++] = '\t';
                i += 2;
                break;
            case 'v':
                s[j++] = '\v';
                i += 2;
                break;    
            default:
                s[j++] = t[i++];
                break;
            }
        } else {
            s[j++] = t[i++];
        }
    }
}

int main() {
    char s[MAXLENGTH] = {0}, t[MAXLENGTH] = {0}, newt[MAXLENGTH] = {0};
    printf("Please input T(end with EOF):\n");
    getString(t);
    escape(s, t);
    printf("S is:\n%s\n", s);
    enter(newt, s);
    printf("NewT is:\n%s\n", newt);
}

运行：

1
2
3
4
5
6
7
8
Please input t(end with EOF):
this    is a    go
od idea
S is:
this\tis a \tgo\nod idea\n
NewT is:
this    is a    go
od idea

exercise3-3

编写函数 expand(s1, s2)，将字符串 s1 中类似于 a-z 一类的速记符号在字符串 s2 中扩展为等价的完整列表 abc…xyz。该函数可以处理大小写字母和数字，并可以处理 a-b-c、a-z0-9 与-a-z 等类似的情况。作为前导和尾随的-字符原样排印。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int check(char str[], int idx) {
    int len = strlen(str);
    if (idx == 0 || idx == len - 1) 
        return 0;
    char prev = str[idx - 1];
    char next = str[idx + 1];

    if ((prev >= '0' && prev <= '9' && next >= '0' && next <= '9' && prev < next) ||
        (prev >= 'a' && prev <= 'z' && next >= 'a' && next <= 'z' && prev < next) ||
        (prev >= 'A' && prev <= 'Z' && next >= 'A' && next <= 'Z' && prev < next)) 
        return 1;

    return 0;
}

void expand(char s1[], char s2[]) {
    int len = strlen(s1);
    int i = 0, j = 0;
    while (i < len) {
        if (s1[i] == '-' && check(s1, i)) {
            int sublen = s1[i + 1] - s1[i - 1];
            for (int k = 1; k < sublen; k++)
                s2[j++] = s1[i - 1] + k;
            i++;
        } else {
            s2[j++] = s1[i++];
        }
    }
    printf("%s\n", s2);
}

int main() {
    char s1[] = "a-c-e9";
    char s2[MAXLINE] = {0};
    expand(s1, s2);
}

运行：

1
2
3
Please input s1:
a-d-f991-8
s2 is:abcdef991234567

exercise3-4

在数的对二的补码表示中，我们编写的 itoa 函数不能处理最大的负数，即 n 等于 $-2 ^{字长-1}$ 的情况。请解释其原因。修改该函数，使它在任何机器上运行时都能打印出正确的值。

因为在原来的程序中，对于n为负数的处理：

1
2
if ((sign = n) < 0) /* record sign */
    n = -n; /* make n positive */

如果 n 为 $-2 ^{字长-1}$ ，那么取n = -n的操作就无法顺利完成，因为 n 最大的正数为 $2 ^{字长-1} - 1$。因此可以修改程序：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
void itoa(int n, char s[])
{
    int i, sign;
    long temp = ((sign = n) < 0 ? -n : n);  // 使用一个 long 型变量来存储
    i = 0;
    do
    {                          /* generate digits in reverse order */
        s[i++] = n % 10 + '0'; /* get next digit */
    } while ((n /= 10) > 0); /* delete it */
    if (sign < 0)
        s[i++] = '-';
    s[i] = '\0';
    reverse(s);
}

或不对 n 取反，直接在do while循环内部进行 abs()操作。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
/* itoa: convert n to characters in s */
void itoa(int n, char s[])
{
    int i, sign = n;
    i = 0;
    do
    {                          
        s[i++] = abs(n % 10) + '0'; 
    } while (n /= 10); 
    if (sign < 0)
        s[i++] = '-';
    s[i] = '\0';
    reverse(s);
}

exercise3-5

编写函数 itob(n, s, b)，将整数 n 转换为以 b 为底的数，并将转换结果以字符的形式保存到字符串 s 中。例如，itob(n, s, 16)把整数 n 格式化成十六进制整数保存在 s 中。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#define MAXLEN 65

char bases[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

void reverse(char s[]) {
    int len = strlen(s);
    int i = 0, j = len - 1;
    while (i < j) {
        char temp = s[i];
        s[i] = s[j], s[j] = temp;
        i++, j--;
    }
}

void itob(int n, char s[], int b)
{
    int i, sign;
    if ((sign = n) < 0)
        n = -n;
    i = 0;
    do {
        s[i++] = bases[n % b];
    } while (n /= b);
    if (sign < 0) 
        s[i++] = '-';
    reverse(s);
}

int main()
{
    int n, b;
    printf("Please input n and b: ");
    scanf("%d %d", &n, &b);
    char s[MAXLEN] = {0};
    if (b < 2 || b > 36)
    {
        printf("wrong base!\n");
        return 0;
    }
    itob(n, s, b);
    printf("%s\n", s);
}

运行：

1
2
Please input n and b: 123 11
102

exercise3-6

修改 itoa 函数，使得该函数可以接收三个参数。其中，第三个参数为最小字段宽度。为了保证转换后所得的结果至少具有第三个参数指定的最小宽度，在必要时应在所得结果的左边填充一定的空格。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void reverse(char s[]) {
    int len = strlen(s);
    int i = 0, j = len - 1;
    while (i < j) {
        char temp = s[i];
        s[i] = s[j], s[j] = temp;
        i++, j--;
    }
}

void itob(int n, char s[], int minlen)
{
    int i, sign;
    if ((sign = n) < 0)
        n = -n;
    i = 0;
    do 
        s[i++] = n % 10 + '0';
    while (n /= 10);
    
    if (sign < 0) 
        s[i++] = '-';
    while (i < minlen) 
        s[i++] = ' ';
    
    reverse(s);
}

int main()
{
    int n, minlen;
    printf("Please input n and minlen: ");
    scanf("%d %d", &n, &minlen);
    char s[MAXLEN] = {0};
    if (minlen <= 0)
    {
        printf("wrong base!\n");
        return 0;
    }
    itob(n, s, minlen);
    printf("%s\n", s);
}

运行：

1
2
Please input n and minlen: -123 10
      -123

exercise3-1#

exercise3-2#

exercise3-3#

exercise3-4#

exercise3-5#

exercise3-6#