STEP 3.2C

<問題> STEP3.2A を基に、リストの先頭に要素を追加するcons と 末尾に要素を追加するappendを作成せよ


<main関数例>
int main(void){
    List *L;
    L = create(); 
    insert (L,1,'a');
    insert (L,1,'c');
    insert (L,2,'v');
    printlist(L);

    delete (L,1);
    insert(L,2,'a');
    delete(L,3);

    printlist(L);   /* [v,a]のはず */

    cons(L, 'x');    /* [x, v, a]となって */
    append (L,'y');  /* [x, v, a, y]となる */
    printlist(L);
    FreeData(L);
    return(0);
}
<実行例> 

c
v
a  (→ここまで、1回プリント)

v
a  (→いくつかの操作のあと、最後にもう一度)
      (→ ここまでは、STEP3.2, STEP3.2Aと同じ。
          ここから、cons(L, 'x')と、append(L, 'y')を実行し、リストをプリント)

x     ( [x, v, a, y]になっている)  
v
a
y


<注意> pp.164 - 166 分割コンパイル
list.h (共有情報) ← cons関数とappend関数のテンプレートを追加せよ
list.c (リスト操作) ← cons関数とappend関数を定義せよ
0302.c (main関数) ← cons関数とappend関数を呼び出そう

gcc -c list.c
gcc -c 0302.c
gcc -o 0302 list.o 0302.o





解答例

ここから、list.hです。

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

/* リスト構造体の定義、型宣言。CELLという名前でもいいでしょう。*/
typedef struct list {
   struct list *next; /* 次のlist構造体へのポインター; 自己参照型 */
   char data; /* データは1つ。1文字。もっと、増やしてもいい */
} List; /* 型の名前は、List。typedefは構造体によく出てくるが、型の読み替えにも利用される。工学実験では多用する */

/* 関数のプロトタイプ宣言 */
List *create(void); /* create関数はアドレスを返す。(List *)だから、List型データが格納されている領域のアドレス */

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);

/* cons関数とappend関数 を追加しよう */

void cons(List *L, char x);
void append(List *L, char x);


-------------------------------
ここから、list.cです。
#include "list.h"

List *create(void){
    List *p;
    p = (List *)malloc(sizeof(List)); /* mallocの使い方に注意。sizeofで確保して、得られたアドレスをキャストする */
    p->next = NULL;
    p->data = '\0'; /* セルのデータを、ヌル文字で初期化 */ 
    /* insertで、すぐに値が代入されるので、初期化はいらないともいえるが、美しくないともいえる。後者が望ましい。
       このプログラムでは先頭がダミーになるので、ヌルを代入し、プリントしないようにする */
    return (p);
}

char access(List *L, int i) {
    if (L->next != NULL) {
        if (i > 1) { /* 再帰条件 */
            return (access(L->next,i-1)); /* 次のセルからのリストで、i-1番目にアクセス ということだ */
        } else { /* 停止条件 */
            return (L->next->data); /* 1番目ということは、先頭のセルの値 */
        }
    } 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); /* 次のセルからのリストで、i-1番目にinsertということだ */
        } else { /* 停止条件 */ /* 以下、新しいセルを確保、つなぎかえているはずだ */
            p = create(); /* セルを1つ */
            p->data = x; /* 確保したセルのdataメンバーに、xを。->演算子に注目 pはアドレスです*/
            p->next = L->next; /* 確保したセルのnextメンバーには、前のセルのnextをつなぐ。これでpからはつながった */
            L->next = p; /* 前のセルの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) { /* 再帰条件 次のセルからのリストで、i-1番目をdeleteということだ */
        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);
}

/* ここから2つは、例題集13.3の関数を、こちらに移動、調整 */
/* どちらもほぼ同じことをしている。どんどん辿って(プリントするか、freeするか)。
   上は非再帰。下は再帰で書かれていることに注意 */

/* 非再帰. whileループでNULLでない間。次を辿っていく */
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) { /* 再帰条件。NULLでないなら、残りのリストをFreeDataし、自分をfree */
        FreeData(L -> next); 
        free (L);
    } /* 停止条件は、何もしないで、正常終了 */
}



/* cons あるいは push */
void cons(List *L, char x) {
   List *p;

   p = create(); /* 新セルを1つ */
   p->data = x;  /* アドレスの実体にあるセルのdataメンバーに、x */
   p->next = L->next; /* 後ろのポインターをnextに */
   L->next = p;       /* 前のポインターに、自分を */
}

/* append あるいは、enqueue */
void append(List *L, char x) {
   List *p;

   if (L -> next == NULL) { /* 次がNULLということは、NULLの1つ前 */
         p = create(); /* セルを1つ p -> nextはNULLに初期化されている */
         p->data = x; /* アドレスの実体にあるセルのdataメンバーに、x */
         L->next = p; /* 前のポインターに、自分をつなぐ */
   } else  {
         append(L -> next, x);
   }
}

----------------------
ここから、0302.cです。
#include "list.h"

int main(void){
    List *L;
    L = create(); /* ダミーリスト(ヘッダの格納)を作成 */
    insert (L,1,'a'); /* 1番目にa */
    insert (L,1,'c');  /* (a)の1番目にc */
    insert (L,2,'v');  /* (c a)の2番目にv */
    printlist(L); /* ダミーリストから、順にプリント。ヌル文字はプリントせず */

    delete (L,1);
    insert(L,2,'a');
    delete(L,3);

    printlist(L);
/*
    while(!empty(L)){
        printf("%c",access(L,1));
        delete(L,1);
    }
    printf("\n");
*/

    cons(L, 'x');      /* [x, v, a]となって */
    append (L,'y');    /* [x, v, a, y]となる */
    printlist(L);

    FreeData(L);
    return(0);
}