同樣是以範例程式，完成其中缺少的 unzip函數。這個函數的作用是將 a list of pairs 變成 a pair of lists。
底下的表示法，方括號 [] 代表 list，圓括弧 () 代表 pair。
譬如原本的 list of pairs 是 [(1,"a"),(2,"b"),(3,"c")]，經過 unzip 之後變成 ([1,2,3],["a","b","c"])。
如果有兩個 lists [1,2,3] 和]["a","b","c"]，先做第一題描述的兩次 zip，變成
[("a",(1,"a")),("b",(2,"b")),("c",(3,"c"))] 之後，如果再做一次 unzip 就變成
(["a","b","c"],[(1,"a"),(2,"b"),(3,"c")])
這一題要做的就是，輸入兩個 lists，經過 N 次 zip 之後，再做一次 unzip，然後輸出最後產生的 pair。
上述的操作已經寫在範例程式中，只要將 unzip 正確寫出，就能產生上述的執行結果。
範例程式:
#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);
int main(void)
{
List *s1, *s2, *s3;
Pair *p;
int N, i;
s1 = read_list();
s2 = read_list();
scanf("%d", &N);
for (i=0; istr[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] = 'Θ';
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;
}
/* 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;
}
}
Pair* unzip(List *lptr)
{
Atom *h;
Pair *p, *newp;
List *l1, *l2;
if (lptr==NULL) {
newp = pair_list(NULL, NULL);
return newp;
}
h = ???; // // 取出 lptr 的開頭第一個 atom
p = ???; // 利用 unzip 對剩下的 lptr 遞迴繼續處理
l1 = ???; // 兩個 lists 分別來自兩個 cons
l2 = ???; // 一個 cons 組合左邊的 list 另一個組合右邊的 list
newp = ???; // // 利用 pair_list 從兩個 lists 產生新的 pair
free_list(l1);
free_list(l2);
free_pair(p);
return newp;
}
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);
}
}
與第一題相同。輸入資料會有五行。
第一行是一個整數 M1，代表第一個 list 包含的資料筆數，第二行則是 M1 筆資料，每筆用空白隔開。
第三行是一個整數 M2，代表第二個 list 包含的資料筆數，第四行則是 M2 筆資料，每筆用空白隔開。
第五行則是一個整數 N。代表執行 zip 的次數。
輸出只有一行，列出經過 N次 zip 之後再做一次 upzip 得到的 pair 內容。最後有換行。