<問題> 図6.7 (p.132)のグラフに関する隣接リストを、リスト構造に格納、表示せよ
<ヒント>
STEP3.2のリストのプログラムをそのまま利用します。
1つのヘッダファイルと、2つのソースファイル
<コンパイル>
gcc -c list.c
gcc -c 0502.c
gcc -o 0502 0502.o list.o
実行は
./0502 ( ./0502 スペースはどこにも入れないことに注意)
<実行結果> (各頂点から、どの頂点に隣接しているのかを、リストにしたもの。1 -> 2 -> 5という意味ではなく、1 ->2 と 1
-> 5の2つの辺)
vertex1
2
5
vertex2
3
5
6
vertex3
6
vertex4
1
5
vertex5
4
6
vertex6
3
7
vertex7
5
6
解答例
以下、list.h #include <stdio.h> #include <stdlib.h> /* リスト構造体 */ typedef struct list { struct list *next; char data; } List; /* 関数のプロトタイプ宣言 */ List *create(void); char access(List *L, int i); void insert(List *L, int i, char x); void delete(List *L, int i); void initialize(List *L); int empty(List *L); void printlist(List *L); void FreeData(List *L); 以下、list.c #include "list.h" List *create(void){ List *p; p = (List *)malloc(sizeof(List)); p->next = NULL; p->data = '\0'; return (p); } char access(List *L, int i) { if (L->next != NULL) { if (i > 1) { return (access(L->next,i-1)); } else { return (L->next->data); } } else { printf("List L ends before arriving "); printf("at the position.\n"); return('\0'); } } void insert(List *L, int i, char x) { List *p; if (L != NULL) { if (i > 1) { /* 再帰条件 */ insert(L->next,i-1,x); } else { p = create(); p->data = x; p->next = L->next; L->next = p; } } else { printf("List L ends before arriving "); printf("at the position.\n"); } } void delete(List *L, int i) { List *del; if (L->next != NULL) { if (i > 1) { delete(L->next,i-1); } else { del = L->next; L->next = L->next->next; free(del); } } else { printf("List L ends before arriving "); printf("at the position.\n"); } } void initialize (List *L) { while (!empty(L)) { delete(L,1); } } int empty(List *L){ if (L -> next == NULL) { return(1); } return(0); } /* Step3.2のまま、dataを、char として出力する */ void printlist (List *L) { printf("\n"); while (L != NULL) { if (L -> data != '\0') printf("%c \n", L -> data); L = L -> next; } } /* 再帰 */ void FreeData(List *L) { if (L != NULL) { FreeData(L -> next); free (L); } } 以下、0502.c #include "list.h" #define N 7 List *Out[N+1]; /* 配列の各要素はList 個数は0から始まらないのでN+1にする*/ void printlist1 (List *L); /* List構造体のdataメンバーを、intとして出力するための関数 */ void printlist1 (List *L) { while (L != NULL) { if (L -> data != '\0') printf("%d \n", L -> data); L = L -> next; } } int main(void){ int i; /* 頂点のidを1からとするので、i=0は使用しない */ for(i=1;i<N+1;i++){ Out[i]=create(); } /* 図6.7のデータ */ insert(Out[1],1,2); insert(Out[1],2,5); /* insert(Out[1], 1, '2')としないで、このまま使う */ insert(Out[2],1,3); insert(Out[2],2,5); insert(Out[2],3,6); insert(Out[3],1,6); insert(Out[4],1,1); insert(Out[4],2,5); insert(Out[5],1,4); insert(Out[5],2,6); insert(Out[6],1,3); insert(Out[6],2,7); insert(Out[7],1,5); insert(Out[7],2,6); /* Outは、添え字にあたる各頂点に、対応するOutリストを持つ。つまり、Outはリストへのポインターを要素とする配列 */ for(i=1; i<N+1; i++){ printf("vertex%d\n", i); printlist1(Out[i]); } /* 今回は、Freeしていません */ return(0); }