#include <stdio.h>
#include <stdlib.h>    /* exit(  ) malloc(  ) free(  ) で必要 */
#include <string.h>    /* strcpy(  ) strcmp(  ) で必要 */

#define NUM_STATION 28
#define  MAX_STATION_NAME  14

typedef struct station station_t;

struct  station {
    char name[MAX_STATION_NAME];
    station_t  *previous;
    station_t  *next;
};

station_t *SetData(void);
void FreeData(station_t *head);
void main(void);

const char *stationname[ ] = {
            "Shinagawa", "Tamachi", "Hamamatsuchou", "Shinbashi",
            "Yurakuchou", "Tokyo", "Kanda", "Akihabara",
            "Okachimachi", "Ueno", "Uguisudani", "Nippori",
            "Nishinippori", "Tabata", "Komagome", "Ootsuka",
            "Ikebukuro", "Mejiro", "Takadanobaba", "Shinookubo",
            "Shinjuku", "Yoyogi", "Harajuku", "Shibuya", "Ebisu",
            "Meguro", "Gotanda", "Oosaki"
};

  /* 構造体のメモリを確保して、駅名をセット */
  /* 最初の構造体へのポインタを返す */
station_t *SetData(void)
{
    station_t *head, *p, *q;
    short i;
	
    if ((head = p = (station_t *)malloc(sizeof(station_t))) == NULL)
        exit(2);    /* メモリ割り当てに失敗したら、シェルに戻る */

    strcpy((*head).name, stationname[0]);	

    for (i = 1; i < NUM_STATION; i++) {
        if ((q = (station_t *)malloc(sizeof( station_t))) == NULL)
            exit(2);    /* メモリ割り当てに失敗したら、シェルに戻る */

        strcpy((*q).name, stationname[i]);

        /* 以下の操作を理解するには、図示してみると良い */
			
        q->previous = p;    /* ひとつ前の構造体へのポインタ ( p ) を */
                            /* q->previous に代入 */
		
        p->next = q;        /* 最後に割り当てた構造体へのポインタ ( q ) を */
                            /* p->next に代入 */

        p = q;              /* 次のループに備える */
    }

    p->next = head;         /* この2行で、最初の構造体 ( head )と、 */
    head->previous = p;     /*  最後の構造体 (p) とを、ポインタでつなぐ */
    return (head);
}

  /* メモリの解放 */
void FreeData(station_t *head)
{
    station_t *next;		/* 作業用ポインタ */

/*
注："Oosaki" は最後に malloc(  )  でメモリを割り当てられた駅です。
ポインタを使って環状の構造にしてあるので、終わりがありません。
そこで、strcmp(  ) を使って、"Oosaki" が現れるまで、メモリを解放しています。
*/
    while (strcmp((*head).name, "Oosaki")) {
        next = head-> next;        /* 次の構造体のアドレスを保存 */
        free(head);                /* メモリを解放 */
        head = next;               /* 次の構造体のアドレスを */	
    }                              /* head に代入 */
    free(head);                    /* "Oosaki" を解放 */
}

void main(void)
{
    station_t *head, *station;
    int c;

    head = SetData(  );
    station = head;        /* head を station にコピー */
                           /* head は最後に使う */

    printf( "  私たちは今%s駅にいます。\n", (*station).name );

    while (1) {
        printf("p: 前の駅  n: 次の駅  e: 終了\n");
        fflush(stdin);        /* 前の入力で stdin に残っている改行コードを捨てる */
        c = getchar(  );
        switch (c) {
            case ('n'):                         /* 入力された文字が n ならば */
                station = station->next;        /* 次の駅名を表示 */
                printf(" %s 駅へ着きました。\n",  (*station).name);
                break;
            case ('p'):                         /* 入力された文字が p ならば */
                station = station->previous;    /* 前の駅名を表示 */
                printf(" %s 駅へ戻りました。\n",  (*station).name);
                break;
            case ('e'):                         /* 入力された文字が e ならば */
                FreeData(head);                 /* malloc(  ) で割り当てたメモリブロックを解放 */
                exit(EXIT_SUCCESS);             /* プログラムを正常終了 */
            default:
                break;
        }
    }
}