準備 STEP 6.1　例題の重み付きグラフを、リスト構造に格納、表示
(STEP5.2は、重みのない有向グラフ。改良する）

• 上の文字列str中、２番目の動物を表示する。

解答例
以下、list1.h

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

typedef struct list {
   struct list *next;
   int data; /* グラフの頂点 intにする */
   int dist; /* 距離 グラフの重みにあたる。追加。関係する関数変更 */
} List;

/* 関数のプロトタイプ宣言 */
List *create(void);

int access(List *L, int i); /* 戻り値をintに変更 */
void insert(List *L, int i, int x, int y);  /* 距離データの追加 */
void delete(List *L, int i);
void initialize(List *L);
int empty(List *L);
void printlist(List *L);
void FreeData(List *L);


以下、list1.c
#include "list1.h"

List *create(void){
   List *p;
   p = (List *)malloc(sizeof(List)); /* mallocの使い方に注意。sizeofで確保して、得られたアドレスをキャストする */
   p->next = NULL;
   p->data = -1; /* ダミー判別用にありえない値で初期化しておく。*/
   p->dist = -1; /* ダミー判別用にありえない値で初期化しておく。*/
                   /* ダミー以外は、正しい情報で上書きされる */
   return (p);
}

int 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, int x, int y) {
   List *p;
   if (L != NULL) {
      if (i > 1) {
         insert(L->next,i-1,x, y);
      } else {
         p = create();
         p->data = x;
         p->dist = y;
         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; /* そのセルのnextを、前のセルのnextにポインタ ーをつなぎかえ。自分はとばされる*/
         free(del); /* 不要になった（どこともつながっていない）セルを、freeする */
      }
   } else {
      printf("List L ends before arriving "); /* 例外処理 */
      printf("at the position.\n");
   }
}

/* 使っていないぞ、という指摘。正しい。これはリストを空にしている */
void initialize (List *L) {
   while (!empty(L)) {
      delete(L,1);
   }
}

/* 空リストかどうかを判定する。真 TRUEなら、1 */
int empty(List *L){
   if (L -> next == NULL) {
      return(1);
   }
      return(0);
}

/* 非再帰. whileループでNULLでない間。次を辿っていく */
void printlist (List *L) {
   while (L != NULL) {
     if (L -> data != -1) /* ありえない-1だったら、ダミー。プリントしない */
        printf("to %d: dist:%d\n", L -> data, L -> dist);
     L = L -> next;
   }
}

/* 再帰 */
void FreeData(List *L) {
   if (L != NULL) { /*　再帰条件。NULLでないなら、残りのリストをFreeDataし、自分をfree */
      FreeData(L -> next);
      free (L);
   } /* 停止条件は、何もしないで、正常終了 */
}


以下、0601.c

#include "list1.h"

#define N 7
List *Out[N+1];  /* 配列の各要素はList 個数は0から始まらないのでN+1にする*/

int main(void){
   int i;

   /* 頂点のidを1からとするので、i=0は使用しない */
   for(i=1;i<N+1;i++){
      Out[i]=create();
   }

   /* 隣接リスト(重み；距離つき)を、リスト構造に格納 */
   /* 図6.7と問6.3のデータ。教科書には距離つきの図がない */
   insert(Out[1],1,2,4); insert(Out[1],2,5,5);
   insert(Out[2],1,3,9); insert(Out[2],2,5,6); insert(Out[2],3,6,2);
   insert(Out[3],1,6,3);
   insert(Out[4],1,1,3); insert(Out[4],2,5,2);
   insert(Out[5],1,4,2); insert(Out[5],2,6,8);
   insert(Out[6],1,3,3); insert(Out[6],2,7,5);
   insert(Out[7],1,5,7); insert(Out[7],2,6,5);

   /* 各頂点について、隣接リストの表示 */
   for(i=1; i<N+1; i++){
      printf("vertex%d\n", i);
      printlist(Out[i]);
   }

   /* ダイクストラ法で、頂点1から、最短距離を求めよ*/
   /*   Dijkstra(1);  Out配列は大域変数にしてあるので、引数に使わないことにします */

   /* Freeするなら */
   for(i=1; i<N+1; i++){
      FreeData(Out[i]);
   }

   return(0);
}