Description

回到上一周的範例
這次要寫出 map 函數
以及搭配 map 使用的 atom_toupper 函數

map 的作用是傳入一個 list 以及一個函數指標
最後會產生一個新的 list
新的 list 的每個 atom
都是經過函數指標所指到的函數所處理過後的新的 atom
譬如某個 list 是 [1,2,3,4,5]
用 map 套用 atom_square 函數 (作用是將 atom 的值變成平方)
結果得到一個新的 list [1,4,9,16,25]
又例如某個 list 是["aa","bb","cc","dd","ee"] 
套用 atom_toupper 函數 (作用是把字串的每個字元都變成大寫)
結果得到 ["AA","BB","CC","DD","EE"]

範例程式：

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

#define STR_EXPAND(tok) #tok
#define STR(tok) STR_EXPAND(tok)
#define STR_LEN 20

/* incomplete struct Atom */
struct Atom;

/* a pair of atom */
typedef struct Pair {
    struct Atom *left;
    struct Atom *right;
} Pair;

/* a list of atoms */
typedef struct List {
    struct Atom *data;
    struct List *next;
} List;

/* an atom can be a string, an int, a pair of atoms, or a list */
typedef struct Atom {
    char str[STR_LEN+1];
    int val;
    Pair *pair;
    List *lst;
    int dtype; /* 0 for string, 1 for int, 2 for pair, 3 for list*/
} Atom;


/* functions for creating an atom */
Atom* atom_str(char *str);
Atom* atom_val(int val);

Atom* copy_atom(Atom *aptr);
void print_atom(Atom *aptr);
void free_atom(Atom *atpr);

/* convert an atom to a single-atom list */
List* atom_to_list(Atom *a);

/* this function is important */
/* useful for creating a new copy of an existing list */
List* cons(Atom *a, List *b);

void print_list(List *lptr);
void free_list(List *lptr);
int length(List *lptr);
List* read_list_helper(List *l, int n);
List* read_list(void);

Atom* head(List *lptr);
List* tail(List *lptr);

List* zip(List *lptr1, List *lptr2);
Pair* unzip(List *lptr);

List* take(int n, List *l);
List* drop(int n, List *l);

Pair* pair_list(List *lptr1, List *lptr2);
Pair* split_at(int n, List *l);

void print_pair(Pair* p);
void free_pair(Pair* p);

Atom* atom_toupper(Atom *a);
Atom* atom_square(Atom *a);
List* map(List *lptr, Atom* (*f)(Atom *));

int main(void)
{
    List *s1, *s2, *s3, *s4;

    s1 = read_list();
    s3 = read_list();

    s2 = map(s1, atom_square);
    s4 = map(s3, atom_toupper);

    print_list(s2);
    printf("\n");

    print_list(s4);
    printf("\n");

    return 0;
}

List* read_list_helper(List *l, int n)
{
    Atom *a;
    int x;
    char str[STR_LEN+1];
    List *l1, *l2;

    if (n==0) {
        return l;
    } else {
        if (scanf("%d", &x)==1) {
            a = atom_val(x);
        } else {
            scanf("%"STR(STR_LEN)"s", str);
            while(!isspace(getchar()));
            a = atom_str(str);
        }
        l1 = read_list_helper(l, n-1);
        l2 = cons(a, l1);
        free_list(l1);
        return l2;
    }
}

List* read_list(void)
{
    int ndata;

    scanf("%d", &ndata);

    return read_list_helper(NULL, ndata);
}
/* Given a string, create a new atom */
Atom* atom_str(char *str)
{
    Atom *aptr = (Atom*) malloc(sizeof(Atom));
    if (str==NULL) {
        aptr->str[0] = '\0';
    } else {
        strncpy(aptr->str, str, STR_LEN);
    }
    aptr->val = 0;
    aptr->pair = NULL;
    aptr->lst = NULL;
    aptr->dtype = 0;
    return aptr;
}

/* Given a value, create a new atom */
Atom* atom_val(int val)
{
    Atom *aptr = (Atom*) malloc(sizeof(Atom));
    aptr->str[0] = '\0';
    aptr->val = val;
    aptr->pair = NULL;
    aptr->lst = NULL;
    aptr->dtype = 1;
    return aptr;
}

Atom* copy_atom(Atom *aptr)
{
    Atom *aptr_new;

    aptr_new = (Atom*) malloc(sizeof(Atom));

    if (aptr_new==NULL) return NULL;
    if (aptr==NULL) return NULL;

    aptr_new->dtype = aptr->dtype;

    if (aptr->dtype == 0) {
        strncpy(aptr_new->str, aptr->str, STR_LEN);
    } else if (aptr->dtype == 1) {
        aptr_new->val = aptr->val;
    } else if (aptr->dtype == 2) {
        if (aptr->pair == NULL) {
            aptr_new->pair = NULL;
        } else {
            aptr_new->pair = (Pair *) malloc(sizeof(Pair));
            aptr_new->pair->left = copy_atom(aptr->pair->left);
            aptr_new->pair->right = copy_atom(aptr->pair->right);
        }
    } else if (aptr->dtype == 3) {
        if (aptr->lst==NULL) {
            aptr_new->lst = NULL;
        } else {
            aptr_new->lst = cons(head(aptr->lst), tail(aptr->lst));
        }
    }
    return aptr_new;
}

void print_atom(Atom *aptr)
{
    if (aptr==NULL) {
        printf("Empty");
        return;
    }
    switch (aptr->dtype) {
    case 0:
        printf("\"%s\"", aptr->str);
        break;
    case 1:
        printf("%d", aptr->val);
        break;
    case 2:
        print_pair(aptr->pair);
        break;
    case 3:
        print_list(aptr->lst);
        break;
    default:
        printf("Undefined.");
    }

}
/* Given an atom, create a list containing the atom. */
List* atom_to_list(Atom *a)
{
    List *b;
    b = (List*) malloc(sizeof(List));
    b->next = NULL;
    b->data = copy_atom(a);
    return b;
}

/* create a new list and add the atom to the head */
List* cons(Atom *a, List *b)
{
    List *c;

    c = atom_to_list(a);
    if (b!=NULL) {
        c->next = cons(head(b), tail(b));
    }

    return c;
}

void print_list(List *lptr)
{
    printf("[");
    while (lptr!=NULL) {
        print_atom(lptr->data);
        if (lptr->next != NULL)
            printf(",");
        lptr = lptr->next;
    }
    printf("]");
}

int len_helper(List *lptr, int len)
{
    if (lptr==NULL) return len;
    else return len_helper(lptr->next, len+1);
}
int length(List *lptr)
{
    return len_helper(lptr, 0);
}

void free_atom(Atom *aptr)
{
    if (aptr != NULL) {
        if (aptr->dtype==2) {
            free_pair(aptr->pair);
        } else if (aptr->dtype==3) {
            free_list(aptr->lst);
        }
        free(aptr);
    }
}

void free_list(List *lptr)
{
    List *p;
    if (lptr!=NULL) {
        p = tail(lptr);
        if (head(lptr)!=NULL) {
            free_atom(head(lptr));
        }
        free_list(p);
    }
}

Atom* head(List *lptr)
{
    return lptr->data;
}

List* tail(List *lptr)
{
    return (lptr==NULL) ? NULL : lptr->next;
}

Pair* pair_list(List *lptr1, List *lptr2)
{
    Pair *p;
    Atom a;

    p = (Pair*)malloc(sizeof(Pair));
    a.dtype = 3;

    a.lst = lptr1;
    p->left = copy_atom(&a);

    a.lst = lptr2;
    p->right = copy_atom(&a);

    return p;
}


void print_pair(Pair *p)
{
    printf("(");
    print_atom(p->left);
    printf(",");
    print_atom(p->right);
    printf(")");
}

void free_pair(Pair* p)
{
    if (p!=NULL) {
        free_atom(p->left);
        free_atom(p->right);
        free(p);
    }
}


Atom* atom_toupper(Atom *a)
{
    Atom *b;
    /* your code here */
    return b;
}
Atom* atom_square(Atom *a)
{
    Atom *b;
    b = copy_atom(a);
    b->val = b->val * b->val;
    return b;
}
List* map(List *lptr, Atom* (*f)(Atom *))
{
    Atom *a;
    List *l1, *l2;
    if (lptr==NULL) return NULL;
    else {
        l1 = ??? /* 用遞迴的方式 利用 map 處理 list 剩下的部分   並且用 l1 指標  記住結果 */
        a = ??? /* 把 lptr 開頭的 atom 代入 f  得到新的 atom */
        l2 = ??? /* 接著再利用 cons 組合 處理過的頭跟尾 */
        free_atom(a);
        free_list(l1);
        return l2;
    }

 

Input

總共會有 2 個 list
第 1 個 list 會用來套用 atom_square 函數
第 2 個 list 會用來套用 atom_toupper 函數

第一行的數字代表第 1 個 list 有幾個元素
第二行是 list 中的每個元素內容，分別以空白隔開
最後兩行以相同格式紀錄第 2 個 list

Output

第一行輸出第 1 個 list 套用 atom_square 函數的結果
第二行輸出第 2 個 list 套用 atom_toupper 函數的結果

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

輸入不同面值的銅板，然後輸入一個金額，將全部可能的找零方式列出。
譬如有 3 種銅板面值分別是 1 元、5元、10元，假設要湊出 17 元，如果把找零方法表示成 "(1元個數,5元個數,10元個數)"，總共會有下列幾種方法
(2,1,1)
(2,3,0)
(7,0,1)
(7,2,0)
(12,1,0)
(17,0,0)
排列順序的規則: 例如 (7,0,1) 先於 (12,1,0) 因為 7 比 12 小；而 (7,0,1) 和 (7,2,0) 的順序，因為第一個數目7 和 7 相等，這時候就要比第二個數目，而由於 0 小於 2 所以 (7,0,1) 先於 (7,2,0)。

Input

第一個數字 N 代表有幾種不同面值的銅板 (N <= 5)
接下來就是 N 個整數，表示 N 種對應的銅板面值
最後一個數字是要需要找零的金額

Output

列出每一種找零方法，用括號框住每個銅板的數量，數量之間用逗號隔開，每一種找零方法後面要換行。
不同的找零方法的排列順序要依照題目的規定。

 

Sample Input  Download

Sample Output  Download

Tags

Discuss