C和指针 第13章 高级指针话题 13.10 编程练习

1. 编写一个程序，从标准输入读取一些字符，并根据下面的分类计算各类字符所占的百分比。
    控制字符
    空白字符
    数字
    小写字母
    大写字母
    不可打印字符
这些字符的分类是根据ctype.h中的函数定义的。不能使用一系列的if语句。 
解析：
这个问题是在第9章给出的，但那里没有对if语句施加限制。这个限制的意图是促进你考虑其他实现方法。函数is_not_print的结果是isprint函数返回值的负值，它避免了主循环处理特殊情况的需要，每个函数保存了函数指针、标签以及每种类型的计数值。
/* 
** 计算从标准输入的几类字符的百分比。 
*/ 
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h> 
/*
** 定义一个函数，判断一个字符是否为可打印字符。这可以消除下面代码中这种类型的特殊情况。 
*/
int is_not_print( int ch ){
    return !isprint( ch );
} 

/*
** 用于区别每种类型的分类函数的跳转表。 
*/
static int(*test_func[])( int ) = {
    iscntrl,
    isspace,
    isdigit,
    islower,
    isupper,
    ispunct,
    is_not_print
};

#define N_CATEGORIES (sizeof(test_func) / sizeof(test_func[0]))

/*
** 每种字符类型的名字。 
*/
const char *label[] = {
    "control",
    "whitespace",
    "digit",
    "lower case",
    "upper case",
    "punctuation",
    "non_printable"
};

/*
** 目前见到的每种类型的字符数以及字符的总量。 
*/
int count[N_CATEGORIES]; 
int total;

int main( void ){
    int ch;
    int category;
    
    /*
    ** 读取和处理每个字符。 
    */
    while( (ch = getchar()) != EOF ){
        total += 1;
        
        /*
        ** 为这个字符调用每个测试函数。如果结果为真，增加对应计数器的值。 
        */
        for( category = 0; category < N_CATEGORIES; category += 1 ){
            if( test_func[category]( ch ) ){
                count[category] += 1;
            }
        } 
    }
    
    /*
    ** 打印结果。 
    */ 
    if( total == 0 ){
        printf( "No characters in the input!\n" );
    } else{
        for( category = 0; category < N_CATEGORIES; category += 1 ){
            printf( "%3.0f%% %s characters\n", count[category] * 100.0 / total, label[category] );
        }
    }
    
    return EXIT_SUCCESS;
}
/* 输出：

*/
2. 编写一个通用目的函数，用于遍历一个单链表。它应该接受两个参数：一个指向链表第一个节点的指针和一个指向一个回调函数的指针。回调函数应该接受单个参数，也就是指向一个链表节点的指针。对于链表中的每个节点，都应该调用一次这个回调函数。这个函数需要知道链表节点的什么信息？
解析：
需要知道这个节点是否为空，不为空则打印列表信息。 
#include <stdio.h>
#include <stdlib.h>

#define ELEMENT_TYPE int
typedef struct NODE{
    ELEMENT_TYPE value;
    struct NODE *link;
} Node;
 
void print( Node *node );
void traverse( Node *first, void (*pf)( Node * ) );
int main( void ){
    Node third;
    Node second;
    Node first;
    
    third = (Node){ 3, NULL };
    second = (Node){ 2, &third }; 
    first = (Node){ 1, &second };
    printf( "traverse the single linked list:\n" );
    traverse( &first, print );
    
    return EXIT_SUCCESS;
}

void print( Node *node ){
    printf( "%d ", node->value );
}

void traverse( Node *first, void (*pf)( Node * ) ){
    while( first ){
        pf( first );
        first = first->link;
    } 
    printf( "\nIt arrives the end of single linked list.\n" );
}
/* 输出：

*/ 
3. 转换下面的代码段，使它改用转移表而不是switch语句。
    Node *list;
    Node *current;
    Transaction *transaction;
    typedef enum {
        NEW, DELETE, FORWARD, BACKWARD, SEARCH, EDIT } Trans_type;
    } Trans_type; 
    ...
    switch( transaction->type ){
        case NEW:
            add_new_trans( list, transaction );
            break;
        case DELETE:
            current = delete_trans( list, current );
            break;
        case FORWARD:
            current = current->next;
            break;
        case BACKWARD:
            current = current->prev;
            break;
        case SEARCH:
            current = search( list, transaction );
            break;
        case EDIT:
            edit( current, transaction );
            break;
        default:
            printf( "Illegal transaction type!\n" );
            break;    
    }
#include <stdio.h>
#include <stdlib.h>

typedef enum { NEW, DELETE, FORWARD, BACKWARD, SEARCH, EDIT } Trans_type;
#define ELEMENT_TYPE int
typedef struct TRANSACTION{
    Trans_type type;
    ELEMENT_TYPE value;
} Transaction;
typedef struct NODE{
    Transaction value;
    struct NODE *prev;
    struct NODE *next;
} Node;
int add_new_trans( Node *, Transaction * );
int delete_trans( Node *, Transaction * );
int search_trans( Node *, Transaction * );
int edit( Node *, Transaction * );
int main( void ){
    Node *list;
    Node *current;
    Transaction *transaction;
    /* ... */
    /* conversion table */ 
    int (*pf[])( Node *, Transaction * ) = {
        add_new_trans, delete_trans, search_trans
    };
    if( transaction->type == FORWARD ){
        current = current->next;
    } else if( transaction->type == BACKWARD ){
        current = current->prev;
    } else if( transaction->type == EDIT ){
        edit( current, transaction );
    }
    else if( transaction->type >= NEW && transaction->type <= SEARCH ){ 
        for( int i = 0; i < 3; ++i ){
            pf[i]( list, transaction );
        }
    } else{
        printf( "Illegal transaction type!\n" );
    }
    return EXIT_SUCCESS;
}
int add_new_trans( Node *, Transaction * ){
}
int delete_trans( Node *, Transaction * ){
}
int search_trans( Node *, Transaction * ){
}
int edit( Node *, Transaction * ){
}
/* 你能想到其他方法吗？或者你有更正确的方法可以畅所欲言呢？*/

/*
4. 编写一个名叫sort的函数，它用于对一个任何类型的数组进行排序。为了使数组更为通用，其中一个参数必须为一个指向比较回调函数的指针，该回调函数由调用程序提供。比较函数接受两个参数，也就是两个需要进行比较的值的指针。如果两个值相等，函数返回零；如果第1个值小于第2个值，函数返回一个小于零的整数；如果第1个值大于第2个值，函数返回一个大于零的整数。
sort函数的参数将是：
1. 一个指向需要排序的数组的第一个值的指针；
2. 数组中值的个数；
3. 每个数组元素的长度；
4. 一个指向回调函数的指针。
sort函数没有返回值。
不能根据实际类型声明数组参数，因为函数应该可以对不同类型的数组进行排序。如果把数据当作一个字符数组使用，则可以用第3个参数寻找实际数组中每个元素的起始位置，也可以用它交换两个数组元素（每次1字节）。
对于简单的交换排序，可以使用下面的算法，当然也可以使用你认为更好的算法。
for i = 1 to 元素数-1 do
    for j = i + 1 to 元素数 do
        if 元素i > 元素j then
            交换元素i和元素j
*/     
#include <stdio.h>
#include <stdlib.h>

/* swap data byte by byte */ 
void swap( void *a, void *b );
/* compare data byte by byte */
int compare( void const *a, void const *b );
/* sort data byte by byte */
void sort( void *base, int element_num, int element_size, int (*compare)( void const *a, void const *b ) );

int main( void ){
    int i;
    int array[] = { 9, 20, 7, 8, 6, 5, 4, 3, 2, 1 };
    char str[] = "hello, world";
    int arr_len;
    int arr_len_2;
    int elem_size;
    int elem_size_2; 
    
    arr_len = sizeof(array) / sizeof(*array);
    arr_len_2 = sizeof(str) / sizeof(*str);
    elem_size = sizeof(*array);
    elem_size_2 = sizeof(*str);
    printf( "print original elements of array:\n" );
    for( i = 0; i < arr_len; ++i ){
        printf( "%d ", array[i] ); 
    } 
    printf( "\n" );
    sort( array, arr_len, elem_size, compare );
    printf( "after sort function, print elements of array:\n" );
    for( i = 0; i < arr_len; ++i ){
        printf( "%d ", array[i] );
    }
    printf( "\n" );
    printf( "print original elements of str:\n" );
    for( i = 0; i < arr_len_2; ++i ){
        printf( "%c ", str[i] ); 
    } 
    printf( "\n" );
    sort( str, arr_len_2 - 1, elem_size_2, compare );
    printf( "after sort function, print elements of str:\n" );
    for( i = 0; i < arr_len_2; ++i ){
        printf( "%c ", str[i] );
    }
    
    return EXIT_SUCCESS;
}

void swap( void *a, void *b ){
    char temp;
    temp = *(char*)a;
    *(char*)a = *(char*)b;
    *(char*)b = temp;
}

int compare( void const*a, void const *b ){
    return *(char const *)a - *(char const *)b; 
}

void sort( void *base, int element_num, int element_size, int (*compare)( void const *a, void const *b ) ){
    int i;
    int j;
    int k;
    int flag; /* check the necessity of swop. */ 
    
    for( i = 0; i < element_num - 1; ++i ){
        for( j = i + 1; j < element_num; ++j ){
            flag = 0; /* no swop */
            for( k = 0; k < element_size; ++k ){ /* compares byte by byte */
                if( compare( (char const*)base + i * element_size + k, (char const *)base + j * element_size + k ) > 0 ){
                    flag = 1; /* need swop */
                    break;
                }     
            }
            if( flag == 1 ){
                for( k = 0; k < element_size; ++k ){
                    swap( (char*)base + i * element_size + k, (char*)base + j * element_size + k );
                }
            }
        }
    }
}

/* 输出：

*/ 
5. 编写代码来处理命令行参数是十分乏味的，所以最好有一个标准函数来完成这项工作。但是，不同的程序以不同的方式处理它们的参数。所以，这个函数必须非常灵活，以便它能用于更多程序。在本题中，你将编写这样一个函数，这个函数通过寻找和提取参数来提供灵活性。用户所提供的的回调函数将执行实际的处理工作。
下面是函数的原型。注意，它的第4个和第5个参数是回调函数的原型。
    char **
    do_args( int argc, char **argv, char *control, void (*do_arg)( int ch, char *value ), void (*illegal_arg)( int ch ) );
头两个参数就是main函数的参数，main函数对它们不做修改，直接传递do_args的第3个参数是个字符串，用于标识程序期望接受的命令行参数。最后两个参数都是函数指针，它们是用户提供的。
do_arg函数按照下面的方式处理命令行参数：
    跳过程序名参数
    while 下一次参数以一个横杠开头
        对于参数横杠后面的每个字符
            处理字符
    返回一个指针，指向下一个参数指针
为了“处理字符”，首先必须观察该字符是否位于control字符串内。如果它并不位于那里，调用illegal_arg所指向的函数，把这个字符作为参数传递过去。如果它位于control字符串内，但它的后面并不是一个+号，那么就调用do_arg所指向的函数，把这个字符和一个NULL指针作为参数传递过去。
如果该字符位于control字符串内并且后面跟一个+号，那么就应该有一个值与这个字符相联系。如果当前参数还有其他字符，它们就是我们需要的值；否则，下一个参数才是这个值。在任何一种情况下，都应该调用do_arg所指向的函数，把这个字符和指向这个值的指针传递过去。如果不存在这个值（当前参数没有其他字符，且后面不再有参数），则应该改而调用illegal_arg函数。注意，必须保证这个值中的字符以后不会被处理。
当所有以一个横杠开头的参数被处理完毕后，应该返回一个指向命令行参数的指针的指针（也就是一个诸如&argv[4]或者argv+4的值）。如果所有的命令行参数都以一个横杠开头，就返回一个指向“命令行参数列表中结尾的NULL指针”的指针。
这个函数必须既不能修改命令行参数指针，也不能修改参数本身。为了说明这一点，假定程序prog调用这个函数。下面的例子显示了几个不同集合的参数的执行结果。
命令行：                    $prog -x-y z
control：                    "x"
do_args调用：          (*do_arg)( 'x', 0 );
                                  (*illegal_arg)( 'y' ) 
并且返回：                &argv[3]
命令行：                    $prog -x-y-z
control:                      "x+y+z+"
do_args调用：           (*do_arg)( 'x', "-y" )
                                   (*illegal_arg)( 'z' )
并且返回：                 &argv[4]
命令行：                     $prog -abcd -ef ghi jkl
control:                       "ab+cdef+g"
do_args调用：            (*do_arg)( 'a', 0 )
                                    (*do_arg)( 'b', "cd" )
                                    (*do_arg)( 'e', 0 )
                                    (*do_arg)( 'e', 0 )
                                    (*do_arg)( 'f', "ghi" );
并且返回：                  &argv[4]
命令行：                      $prog -a b -c -d -e -f
control:                        "abcef"
do_args调用：             (*do_arg)( 'a', 0 )
并且返回：                   &argv[2] 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void do_arg( int ch, char *value );
void illegal_arg( int ch ); 
char **do_args( int argc, char **argv, char *control, 
                void (*do_arg)( int ch, char *value ), 
                void (*illegal_arg)( int ch ) );

int main( int argc, char **argv ){
    char control[] = "x";
    char control_2[] = "x+y+z+";
    char control_3[] = "ab+cdef+g";
    char control_4[] = "abcdef";
    char **p;
    char **p2;
    char **p3;
    char **p4;
    /*
    p = do_args( argc, argv, control, do_arg, illegal_arg ); 
    printf( "p = %p, &argv[3] = %p\n", p, &argv[3] );
    */
    /*
    p2 = do_args( argc, argv, control_2, do_arg, illegal_arg );
    printf( "p2 = %p, &argv[4] = %p\n", p2, &argv[4] );
    */
    /*
    p3 = do_args( argc, argv, control_3, do_arg, illegal_arg );
    printf( "p3 = %p, &argv[4] = %p\n", p3, &argv[4] );
    */
    
    p4 = do_args( argc, argv, control_4, do_arg, illegal_arg );
    printf( "p4 = %p, &argv[2] = %p\n", p4, &argv[2] );
    
    return EXIT_SUCCESS;
}

void do_arg( int ch, char *value ){
    /* 跳过程序名参数 */ 
    printf( "(*do_arg( '%c',", ch );
    if( value == NULL ){
        printf( "0 )\n" );
    } else{
        printf( "\"%s\" )\n", value );
    }
}

void illegal_arg( int ch ){
    printf( "(*illegal_arg( '%c' ))\n", ch ); 
}

char **do_args( int argc, char **argv, char *control, 
                void (*do_arg)( int ch, char *value ), 
                void (*illegal_arg)( int ch ) ){
    /* 跳过程序名参数 */ 
    ++argv;
    /* 下一次参数以一个横杠开头 */ 
    while( *argv && **argv == '-' ){
        char ch;
        while( ch = *++*argv ){
            /* 字符不位于control字符内 */ 
            char *pc; 
            if( (pc = strchr( control, ch )) == NULL ){
                illegal_arg( ch );
            } else{ /* 字符位于control字符内 */
                char ch2;
                ch2 = *(pc + 1);
                if( ch2 == '+' ){ /* 控制字符+后面跟一个加号 */ 
                    char ch3 = *++*argv; 
                    if( ch3 == '\0' ){
                        if( *++argv == NULL ){
                            illegal_arg( ch );
                            return argv;
                        } else{
                            do_arg( ch, *argv );
                            break;
                        }
                    } else{
                        do_arg( ch, *argv );
                        break;
                    }
                } else{ /* 控制字符后面不跟一个加号 */ 
                    do_arg( ch, NULL );
                }
            }
        }    
        ++argv;
    }
    return argv;
}

/* 输出：

*/