STEP 5.2 図6.7の隣接リストを、リスト構造に格納、表示

<問題> 図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);
}