Description
以範例程式為基礎，完成其中缺少的 zip 函數。這個函數的作用是將兩個 lists 合併，對應位置的元素組成一個 pair，然後產生一個新的 list 包含所有的 pairs。也就是從兩個 lists 變成一個 list of pairs。
底下的表示法，方括號 [] 代表 list，圓括弧 () 代表 pair。
譬如第一個 list 是 [1,2,3] 而第二個是 ["a","b","c"]，經過 zip 之後變成
[(1,"a"),(2,"b"),(3,"c")]。
接著如果再用第二個 list 和第一次 zip 之後的結果，再做一次 zip，結果會變成
[("a",(1,"a")),("b",(2,"b")),("c",(3,"c"))]
然後第一次 zip 和第二次 zip 得到的兩個 lists，再做第三次 zip 就變成
[((1,"a"),("a",(1,"a"))),((2,"b"),("b",(2,"b"))),((3,"c"),("c",(3,"c")))]
上述的操作已經寫在範例程式中，只要將 zip 正確寫出，就能產生上述的執行結果。
範例程式:
#include
#include
#include
#include
/* 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[21];
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);
int main(void)
{
List *s1, *s2, *s3;
int N, i;
s1 = read_list();
s2 = read_list();
s3 = NULL;
scanf("%d", &N);
for (i=0; istr[0] = '\0';
} else {
strncpy(aptr->str, str, 20);
}
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, 20);
} 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;
}
/* create a new list combining a string list and a value list
If the two input lists have different lengths, the new list will be
of the same length as the shorter one.
*/
List* zip(List *lptr1, List *lptr2)
{
Atom a;
List *l1, *l2;
if ( ??? ) { // lptr1 或 lptr2 兩者有一個是 NULL
return NULL;
} else {
a.pair = ???; // malloc 取得一塊 Pair 空間
a.pair->left = ???; // 利用 copy_atom 複製 lptr1 的開頭第一個 atom
a.pair->right = ???; // 利用 copy_atom 複製 lptr2 的開頭第一個 atom
a.dtype = 2;
l1 = ??? // 利用 zip 處理剩下的 lists (提示: 用遞迴)
l2 = cons(&a, l1); // 利用 cons 造出新的 list
free_pair(a.pair);
free_list(l1);
return l2;
}
}
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);
}
}
Input
輸入資料會有五行。
第一行是一個整數 M1，代表第一個 list 包含的資料筆數，第二行則是 M1 筆資料，每筆用空白隔開。
第三行是一個整數 M2，代表第二個 list 包含的資料筆數，第四行則是 M2 筆資料，每筆用空白隔開。
第五行則是一個整數 N。代表執行 zip 的次數。
Output
輸出只有一行，列出經過 zip 之後的 list 內容。最後有換行。
Tags