片方向リストの実現について

Question

リストでスタックを実現したいのですが、以下の関数の使い分けが全く分かりません。addlist()とmidlist()の違いは何でしょうか。どちらも先生が用意した関数なのですが、説明は以下のようなのですが、どうやってスタックを実現すればいいのでしょうか。とりあえずデータを積む動作を実現したいのです。まずaddlist()の説明は以下のようです。

struct LIST * addList( struct LIST ** pstart){
        struct LIST *p, *new;
        p = *pstart;
        if((new=(struct LIST *) malloc(sizeof(struct LIST)))==NULL){
           return NULL;        /* メモリ確保失敗 */
        }
        new->next = NULL;
        if(p!=NULL){                /* リストに要素が存在するとき */
           while(p->next!=NULL){    /* リストの末尾を探す */
              p=p->next;
           }
           p->next = new;           /* リストの末尾につなげる */
        }else{
           *pstart = new;           /* 最初の要素の場所を *pstart に */
        }
        return new;
    }

リストでは後戻りは出来ないので、先頭のオブジェクトへのポインタは 必ず覚えていなければならない。上の関数 addList() はそうした リストの先頭オブジェクトへのアドレスを引数に取る。関数内部では、 まず、新しいオブジェクトを malloc() で割り当て、 それの後ろにはもうデータがないので最初から next に NULL を代入し ておく。 次に、先頭のオブジェクトへのポインタが NULL でないならば、リストにいくらかの オブジェクトが連なっているのであるから、 先頭から順に次のオブジェクトへのアドレスを取り出し、最後のオブジェクト になるまで移動し、先に確保したオブジェクトをこのリストの最後の オブジェクトの後ろにぶら下げるために、そのアドレス(new)を 最後のオブジェクトの next に入れている。一方、引数を struct LIST ** にしているのは次の削除 との関係で統一をとっているからであり、使うときには実際の リストの先頭へのアドレスを保持しているポインタ変数のアドレスを 渡すようにする。これは特にリストの先頭へのポインタが外部の関数に あるときに、どうやってその先頭へのポインタの中身を書き換えるかと いう問題であり、実際上の例でもリストに要素が一個もない時には、 このリストの先頭へのポインタを pstart に保存しておく必要 があるのであった。従って、この関数を実際に使う場合には以下のように して使う必要がある。

 struct LIST *start=NULL;
    ...
    addList(&start);

この説明を見る限り,addlist()はスタックを実現する際、先頭は1つだけなので、実行するのは1度だけでいいという事でしょうか。
midlidt()の説明は以下のようです。

struct LIST * midList( struct LIST *before, struct LIST *new){
        struct LIST *p = before;
        new->next = before->next;
        before->next = new;
        return new;
    }

ここで、before はオブジェクトを挿入したい場所の前に位置する リンクのオブジェクトであり、new は新たに挿入したいオブジェクトである。 ポイントは、before の次に new が来るようにし、new の後ろに 元々 before の後ろに位置していたオブジェクトを繋げる事である。 但し、このプログラムでは先頭にオブジェクトを入れることができない 点には注意しよう

データを積む際にはこのmidlist()を使えばいいのでしょうか。けど、malloc()でメモリをかくほしていないので、無理じゃないかと思っているのですが、どうなのでしょう。

Comments

[ttyp03]

まずは文章に適度な改行を！読みづらい。

Answer 1

たぶん、下記のような使用方法と思います。
ソースコードを見れば、だいたいの使用方法がわかると思いますので
復習がてらいろいろと試せば良いと思います。

int main() {
    struct LIST *start=NULL;

    addList(&start);

    printf("構造体のアドレスは%p\n", start);
    printf("start->nextのアドレスは%p\n", start->next);

    struct LIST *nextA = addList(&start);
    printf("nextAのアドレスは%p\n", nextA);
    printf("start->nextのアドレスは%p\n", start->next);
  
    struct LIST *nextB = addList(&start);
    printf("nextBのアドレスは%p\n", nextB);
    printf("nextA->nextのアドレスは%p\n", nextA->next);
  
    struct LIST *nextC = addList(&start);
    printf("nextCのアドレスは%p\n", nextC);
    printf("nextB->nextのアドレスは%p\n", nextB->next);
  
    struct LIST *nextD = addList(&start);
    printf("nextDのアドレスは%p\n", nextD);
    printf("nextC->nextのアドレスは%p\n", nextC->next);

    printf("--------------------\n");

    midList(nextA, nextC);
    printf("nextA->nextのアドレスは%p\n", nextA->next);
    printf("nextBのアドレスは%p\n", nextB);
    printf("nextC->nextのアドレスは%p\n", nextC->next);
    return 0;
}

Answer 2

このmidListは

A -> B

というListがあったときにmidList(A, C)とすることで

A -> C -> B

にする関数みたいです．

けど、malloc()でメモリをかくほしていないので

これに関してはmidListは呼び出し元がすでにCを用意していることを前提にしており，
AとCのnextの張替えしかしていません

Answer 3

疑問があるなら、その先生に聞きましょう。

ここはあなたの不満を聞く場所ではないです