c言語 リスト 配列

[asdf]

整数値が入ったint型の配列 A[0], A[1], ... , A[N-1] が与えられたとき、次に示すようなリストを配列で構成せよ。

header → A[0] → A[1] → ... → A[N-1]

また、リストを操作する２つの関数を作成せよ。
（１）追加関数　n番目の後に新たなデータを追加する
（２）削除関数　n番目のデータを削除する

という問題なのですが、一体何をすればよいのか全然分かりません。リストを調べても、ポインタを用いたものしかなく、配列を使ったものが見つかりませんでした。

とりあえず自分で考えたのは、

まず、Aに適当な整数値を入れておき、（１）の追加関数は、n+1番目以降の要素を１つずつ後ろにずらしてから、n+1番目の要素にデータをセットする。（２）の削除関数は、n+1番目以降の要素を１つずつ前にずらす。

という感じです。このようなプログラムを組めばよいのでしょうか？しかし、→をどう表現したらよいか分かりません。また、このようなプログラムを組む場合、構造体、ポインタは使わなくてもよいのでしょうか？

よろしくお願いします。

[組木紙織]

この場合の"リスト"ってどのような意味ですか？

>→をどう表現したらよいか分かりません。
右矢印の意味はどのように定義されてますか？
それに依存します。

>また、このようなプログラムを組む場合、構造体、ポインタは使わなくてもよいのでしょうか？
状況によっては構造体や、(明示的に)ポインタを使わなくてもできます。

問題は出題者がどのような意図をもって問題を出したのかですね。
それが分からないと、できるかもしれないし、できないかもしれないとしか言いようがないです。

[asdf]

本当は、添付した図に示すようなリストを配列で構成せよ。という問題でした。

この図で、この場合の"リスト"がどのような意味かわかりますでしょうか？

意図は、おそらく次回から本格的なリストを勉強するから、まずは配列でやれということだと思います。

[組木紙織]

＞この図で、この場合の"リスト"がどのような意味かわかりますでしょうか？
大体予想はつきますが、口頭か文章で説明があったはずなので、それを聞いています。


＞意図は、おそらく次回から本格的なリストを勉強するから、まずは配列でやれということだと思います
なら配列にデータを入れて(1)と(2)の関数を用意してあげれば十分かな。
まだ良くどのような実装にすればよいかが分からないけど。(以下参照)


最初の文章から以下のような実装を思いつきました。
(1)配列に要素を入れて、直接外部から配列をインデックス順に操作することでリストの要件を満たす。
(2)配列に要素と次のインデックスを入れて、インデックスをたどりながらリストの操作をする。
(3)配列に要素を入れて、配列へのポインタを要素としたリンクリストを作って操作をする。
(4)複数の要素を入れた配列を要素に持つリンクリストを作る。

で、多分、返答から確実なところは出題者に聞かないと分かりませんが、
一番実装が楽な(1)何じゃないかと想像しました。

[asdf]

＞大体予想はつきますが、口頭か文章で説明があったはずなので、それを聞いています。
(2)配列に要素と次のインデックスを入れて、インデックスをたどりながらリストの操作をする。
のようなプログラムだったと思います。また、ポインタは使わないと言っていました。

しかし、プログラムをどのように組めばよいか全然思いつきません。
どのようにすればよいのでしょうか？

[組木紙織]

本来は動的配列を使わないといけないのですが、
組み方が分かるようにサンプル組んでみました。
(無意味に)少しだけ難読化かけてます。
適当にいじってください。


#include <stdio.h>
typedef struct Node
{
int num;
int next_index;

} Node;
int main(void)
{

Node list[10];
int i=0;
b: list.num =i;
list.next_index =i+1;
if(++i<10)goto b;
a: printf("num:%d\tnext_index:%d\n",list[i-10].num,list[i-10].next_index);
i=list[i-10].next_index+10;
if(i<20)goto a;
return 0;
}

[asdf]

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

#define N 5

struct List {
    int val;
    int next;
};


int main(void) {
    int i;
    struct List A[N];
    
    for (i=0; i<N; i++) {
            A.next = i+1;
            A.val = rand();
    }
    for (i=0; i<N; i++)
        printf("A[%d]: %d\tnext_index: %d\n", i, A.val, A.next);
    return 0; 
}

と同じですよね。

結局のところ、あの→やheaderはどうすればよいのでしょうか？
追加の場合、例えば n=2　とされた場合、値をとりあえずA[N-1]に格納しておき、A[1].next=N-1,
A[N-1].next=2 とすればよいのでしょうか？

[組木紙織]

表示部がちょっと違います。
forループで回さないでください。
するのなら以下のように。
i=0;
while(i<10)
{
　printf("num:%d\tnext_index:%d\n",list.num,list.next_index);
　i=list.next_index;
}

右矢印は次のノードを示しているものなので、next_indexの事を意味しています。
headerは最初のノードを指示しているものです。それに相当するものをサンプルには使っていません。

＞追加の場合、例えば n=2　とされた場合、値をとりあえずA[N-1]に格納しておき、A[1].next=N-1,
＞A[N-1].next=2 とすればよいのでしょうか？
やってみたらどうですか？

[asdf]

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

#define N 5

struct List {
    int val;
    int next;
};

struct List header;

void Add(struct List A[/url]);

int main(void) {
    int i;
    struct List A[N];
    int count = 0;

    for (i=0; i<N-1; i++) {
            A.next = i+1;
            A.val = i;
    }
    header.val = -1;
    header.next = 0;
    A[N-1].val = -1;
    A[N-1].next = 0;
    i = 0;
    while (count < N-1) {
        printf("A[%d]: %d\n", i, A.val);
        i = A.next;
        count++;
    }

    Add(A);
    //Del(A);
    
    return 0;
}

void Add(struct List A[/url]) {
    int i, n, val;
    int count = 0;

    puts("リストのn番目の後に追加する");
    do {
        printf("n  : ");        scanf("%d", &n);
    } while (n < 0 && n >= N);
    printf("val: ");         scanf("%d", &val);

    A[N-1].val = val;
    A[N-1].next = n;

    if (n == 0)
        header.next = N-1;
    else
        A[n-1].next = N-1;

    i = header.next;
    while (count < N) {
        printf("A[%d]: %d\n", i, A.val);
        i = A.next;
        count++;
    }
}

とりあえず作ってみました。こんな感じでよいのでしょうか？

また、添付した図で、A[N-1]に斜線があるのですが、あれはどういう意味なんでしょうか？

[box]

> また、添付した図で、A[N-1]に斜線があるのですが、あれはどういう意味なんでしょうか？

リストの終わりを示しています。
自己参照型構造体でいうと、

typedef struct CELL {
int value;
struct CELL *next;
} CELL;

のようなケースで、nextがNULLだってことです。

[asdf]

ありがとうございます。
ということは、あのプログラムは、A「N-1]を使っているのでおかしいのでしょうか？
しかし、これを使わなかったらどうすればよいのでしょうか？

[ドラ]

>リストの終わり
配列の要素を指す添字として使わない数値を使いましょう。
-1とかでいいのではないですか？

それから、挿入するときにA[N-1]に決め打ちでデータを格納するのはおかしいす。
2回連続で挿入すると必ずデータを壊します。
配列の中で未使用の要素を探す必要があります。

後、配列ではn番目の要素はA[n-1]かもしれませんが、
連結リストとして扱っているのですからheaderから順番にたぐっていかなければ
n番目のデータが配列内のどこに存在するか分かりません。

[asdf]

回答ありがとうございます。

＞配列の中で未使用の要素を探す必要があります。
未使用の要素などあるのでしょうか？

あのプログラムでだめなら、もう何をすればよいのか全く分かりません・・・

[組木紙織]

＞あのプログラムでだめなら、もう何をすればよいのか全く分かりません・・・

どこまでが大丈夫で、どこからがだめか理解していますか？
それなしには改善は不可能です。
あと、リストの概念をしってますか？
授業で習ったと思われるので飛ばして実装についてだけ話していたのですが、理解できていないような感じ
を受けました。リストというものはどのようなものか把握しておいてください。

以下問題点
1:要素数が5までしか扱えない、リストは要素数は固定ではなく、理論上無限の要素数を扱える必要がある。
2:挿入時に配列の最後の要素に入れるようにしているが、
　一度削除が行われた後だと、配列の途中が空白になるときがある。
　その時は配列のあいてある部分に入れたほうが空間効率がよくなる。
3:表示時にリストの要素数をあらかじめ知っていないと表示出来ないようになっている。
あらかじめ要素数を知らなくても表示可能にする方がリストとしては自然。
4:問題要件は入力配列の要素をリストの初期値に使うとしてあるのに初期化時の要素の内容が固定である。
5:リストはheaderさえ知っていればどのような操作も(基本的には)可能である構造であるのに、
　挿入関数にheader以外の部分を渡すようにしている。
番外編
コメントが一切存在しない

1は動的配列を扱う方法を知っていれば、実装してください。
知らない場合はそれなりに大き目の配列を用意してごまかしましょう。
2はドラさんが書いている前半部分と同じことを意味しています。
3はリストの最後の要素の中身を考えれば実装できます。
4は今はとりあえず無視で、後でいくらでも直せます。
5を直すのも後でいいです。先に2や3を直すべきかと。

[asdf]

とりあえず、追加するのはいくらでもできるようにはできました。（配列の要素数までですが）
と思っていたら、できませんでした。とりあえず、Add関数で、n=0のときだけはできました。
どこがおかしいでしょうか？

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

#define N 5
#define M 1000

struct List {
    int val;
    int next;
};

struct List header;
int j = N;    //データ数

void Add(struct List A[/url]);
void Del(struct List A[/url]);

int main(void) {
    int i, k;
    struct List A[M];

    srand(time(NULL));

    for (i=0; i<N; i++) {
            A.next = i+1;
            A.val = rand();
    }
    A[N-1].next = -1;
    for (i=N; i<M; i++) {
        A.next = -1;
        A.val = -1;
    }
    header.val = -1;
    header.next = 0;

    puts("List");
    i = 0;
    while (i != -1) {
        printf("A[%d]: %d\n", i, A.val);
        i = A.next;
    }
    do {
        puts("データをどうしますか？（追加：０　削除：１ やめる場合：３）");
        scanf("%d", &k);
        switch (k) {
            case 0:        Add(A);    break;
            case 1:        Del(A);    break;
            default:    break;
        }
    } while (k == 0 || k == 1);
    
    return 0;
}

void Add(struct List A[/url]) {
    int i, n, val;

    puts("リストのn番目の後にデータを追加する");
    do {
        printf("n  : ");    scanf("%d", &n);
    } while (n < 0 || n > j);
    printf("val: ");         scanf("%d", &val);

    A[j].val = val;
    if (n == 0)
        A[j].next = header.next;
    else if (n != j)
        A[j].next = A[n-1].next;
    if (n == 0)
        header.next = j;
    else
        A[n-1].next = j;

    i = header.next;
    while (i != -1) {
        printf("A[%d]: %d\n", i, A.val);
        i = A.next;
    }
    j++;
}

また、
＞問題要件は入力配列の要素をリストの初期値に使うとしてあるのに初期化時の要素の内容が固定である
これは、どういう意味でしょうか？

[組木紙織]

とりあえず、実行可能なプログラムをあげてもらいたいと思います。

＞＞問題要件は入力配列の要素をリストの初期値に使うとしてあるのに初期化時の要素の内容が固定である
＞これは、どういう意味でしょうか？

最新のではランダムになっているようですが、そのような意味ではなく、
最初の問題文では配列Aを与え、その値を初期値としたリストをつくうようになっています。
そのためリストを作るときは、配列を用意し、その配列から値を引っ張ってリストを
作るようにすべきということです。

この挿入関数は必ず配列の最後の部分に値を入れますが、削除したら配列の間があくと思います。
あいた要素はそのままにして、配列の最後に値を入れたいと思いますか？

[asdf]

すみません。
＞最新のではランダムになっているようですが、そのような意味ではなく、
最初の問題文では配列Aを与え、その値を初期値としたリストをつくうようになっています。
そのためリストを作るときは、配列を用意し、その配列から値を引っ張ってリストを
作るようにすべきということです。

の意味がよく分からないです。値を引っ張るとはどういうことでしょうか？初めにrand()で値を入れている部分が不要ということでしょうか？できれば、例となるプログラムを呈示して欲しいです。

[組木紙織]

いま、この課題の解答と書いていて、その一部の初期化関係部分を抜粋しました。
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

/*最後のノードを表すフラグ*/
#define END -1
/*使われていないノードを表すフラグ*/
#define NUL -2
/*入力データ配列の要素数*/
#define N 2
/*リスト配列の要素数*/
#define LIST_SIZE 100

struct List {
int val;
int next;
};

/*表示関数*/
void print(struct List list[LIST_SIZE]);
/*初期化関数*/
void initialize(int A[N]/*初期化用データ*/,struct List list[LIST_SIZE]/*リスト*/);
int main(void)
{
struct List list[LIST_SIZE];
int A[/url] ={1,2};
initialize(A,list);
print(list);


}

void initialize(int A[N],struct List list[LIST_SIZE])
{
int i;
assert(N<=LIST_SIZE);
list[0].val =0;
list[0].next =1;

for(i=1;i<=N;++i)
{
list.val = A[i-1];
list.next =i+1;
}
list[i-1].next =END;
for(;i<LIST_SIZE;++i)
{
list.next =NUL;
}
}

[asdf]

これは、要するにリストを表す配列とは別にint型の配列を定義しろというでしょうか。

とりあえず、追加の関数を作っていたのですが、どうにもうまくいきません。
最後と最初に挿入するのはできるのですが、他の場合ができません。
Add関数の

else if (n != j) {
        A[k].next = A[n-1].next;
        A[n-1].next = k;
}

のn-1の部分がおかしいのは分かるのですが、どうすればよいか分かりません。どうすればよいのでしょうか？

以下、ソースコードです。（削除の部分は無視してください）

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

#define N 5
#define M 1000

struct List {
    int val;
    int next;
};

struct List header;
int j = N;    //最後尾データ

void Add(struct List A[/url]);
void Del(struct List A[/url]);

int main(void) {
    int i, k;
    struct List A[M];
    int b[N];

    srand(time(NULL));
    for (i=0; i<N; i++)
        b = rand();
    for (i=0; i<N; i++) {
            A.next = i+1;
            A.val = b;
    }
    A[N-1].next = -1;
    for (i=N; i<M; i++) {
        A.next = -1;
        A.val = -1;
    }
    header.val = -1;
    header.next = 0;

    puts("List");
    i = 0;
    while (i != -1) {
        printf("A[%d]: %d\n", i, A.val);
        i = A.next;
    }
    do {
        puts("データをどうしますか？（追加：０　削除：１ やめる場合：３）");
        scanf("%d", &k);
        switch (k) {
            case 0:        Add(A);    break;
            case 1:        Del(A);    break;
            default:    break;
        }
    } while (k == 0 || k == 1);
    
    return 0;
}

void Add(struct List A[/url]) {
    int i, k, n, val;

    puts("リストのn番目の後にデータを追加する");
    do {
        printf("n  : ");    scanf("%d", &n);
    } while (n < 0 || n > j);
    printf("val: ");         scanf("%d", &val);

    for (k=0; k<=j; k++)
        if (A[k].val == -1) {
            A[k].val = val;
            break;
        }
    
    if (n == 0) {
        A[k].next = header.next;
        header.next = k;
    }
    else if (n != j) {
        A[k].next = A[n-1].next;
        A[n-1].next = k;
    }
    else {
        A[k].next = -1;
        A[n-1].next = k;
    }

    i = header.next;
    while (i != -1) {
        printf("A[%d]: %d\n", i, A.val);
        i = A.next;
    }
        j++;
}

[ドラ]

Add関数内で「リストのｎ番目の要素の添字」を求める処理が存在していません。
headerから始まってｎ回たぐっていかないとリストのｎ番目の要素の添字は分かりません。

>if (n == 0) {
> A[k].next = header.next;
> header.next = k;
>}
>else if (n != j) {
> A[k].next = A[n-1].next;
> A[n-1].next = k;
>}
>else {
> A[k].next = -1;
> A[n-1].next = k;
>}
つまり↑の部分が間違っていて、↓こんな感じです。


if (n == 0) {
A[k].next = header.next;
header.next = k;
}
else {
int nth_index; // リストのｎ番目の要素の添字

nth_index = header.next;
for (i = 1; i < n; ++i) {
nth_index = A[nth_index].next;
}

A[k].next = A[nth_index].next;
A[nth_index].next = k;
}
　

[asdf]

回答ありがとうございます。質問してからもずっと考えていて、ドラさんと一緒の方法を思いつき、なんとかできました。

作れたので、これで解決ということにします。組木紙織さん、どうもありがとうございました。

[組木紙織]

＞作れたので、これで解決ということにします。
お疲れさまでした。
以下のコードは私が作ったものです。
処理が分かりやすいように素直に作ったつもりです。
自分が作ったのと比較して見てください。


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

/*最後のノードを表すフラグ*/
#define END -1
/*使われていないノードを表すフラグ*/
#define NUL -2
/*入力データ配列の要素数*/
#define N 2
/*リスト配列の要素数*/
#define LIST_SIZE 100

struct Node {
int val;
int next;
};

/*挿入関数*/
void incert(int number/*挿入する位置*/,int data/*挿入するデータ*/,struct Node list[LIST_SIZE]/*リストのデータ配列の最初の要素*/);
/*消去関数*/
void erease(int number/*削除するノードの位置*/,struct Node list[LIST_SIZE]/*リストのデータ配列の最初の要素*/);
/*表示関数*/
void print(struct Node list[LIST_SIZE]);
/*初期化関数*/
void initialize(int A[N]/*初期化用データ*/,struct Node list[LIST_SIZE]/*リスト*/);
int main(void)
{
struct Node list[LIST_SIZE];
int A[/url] ={1,2};
initialize(A,list);
print(list);
printf("ccccccccccccccccccccc\n");
incert(1,3,list);
print(list);
printf("ccccccccccccccccccccc\n");
erease(1,list);
print(list);
return 0;
}

void initialize(int A[N],struct Node list[LIST_SIZE])
{
int i;
assert(N<=LIST_SIZE);
/* list[0]はheader*/
list[0].val =0;
list[0].next =1;

/*配列からリストの構築*/
for(i=1;i<=N;++i)
{
list.val = A[i-1];
list.next =i+1;
}
list[i-1].next =END;
/*使われていない部分のデータをNULで埋める*/
for(;i<LIST_SIZE;++i)
{
list.next =NUL;
}
}

void print(struct Node list[LIST_SIZE])
{
int next =list[0].next;
while(next!=END)
{
printf("A[%d]: %d\n", next, list[next].val);
next =list[next].next;
}
}

void incert(int number,int data,struct Node list[LIST_SIZE])
{
int i,next;
/*あいている配列の要素を探す*/
for(i=0;i<LIST_SIZE;++i)
{
if(list.next == NUL)break;
}

if(i>=LIST_SIZE)
{
printf("err/n");
exit(1);
}
assert(i<LIST_SIZE);

/*挿入場所を探す*/
next = 0;
while(number>0)
{
next =list[next].next;
--number;
if(next==END)
{
printf("err\n");
exit(1);
}
}
/*挿入*/
list.val = data;
list.next = list[next].next;
list[next].next = i;
}

void erease(int number,struct Node list[LIST_SIZE])
{
int next=0,buf;
/*削除場所を探す*/
while(number>0)
{
if(list[next].next==END)
{
printf("err\n");
exit(1);
}
next =list[next].next;
--number;

}
if(list[next].next==END)
{
printf("err\n");
exit(1);
}
/*削除*/
buf = list[list[next].next].next;
list[list[next].next].next =NUL;
list[next].next =buf;
}

[asdf]

組木紙織さん、わざわざありがとうございます。

参考にさせて頂きます。