C言語によるリスト構造について質問があります

質問

データ構造とアルゴリズム(岩波書店)という参考書のpascalのソースを元にC言語で作って来るという課題(下に書きます)が出たのですが、
手元にある参考書を見たり、インターネットで調べてもわからなかったので質問させていただきます。(ソースはすべてpascalです)
1.リストの先頭へのデータ挿入
proceder inserthead(val :datatype);
var q:list;
begin
new(q);
with q↑ do
begin
element:=val;
next:=listhead;
end;
listhead:=q;
end;

2.リストの先頭からデータの削除
proceder deletehead;
var q:list;
begin
q:=listhead;
listhead:=q↑.next;
dispose(q);
end;

3.リストを画面に出力するプログラム
この3つが出題された課題です。
最初、C言語によるリストを作る方法がわからずほかの授業で使用したテキストを見てポインタと配列を使うものだと思い、それを主にインターネットなどで検索しましたが、char型の値を用いたものを出力するためのソースがありましたが、それを自分に必要なソースに書き直すことができませんでした。
LSI C-86用のCPadを使って書いていたのですが、「警告: ポインタの型が合わない (=)」や、実行できてもなぜか延々とprintf命令が実行され続け、暴走？したり自分では解決できそうにありません。
ご教授お願いします。
詳しく解説されている(初級と中級レベルそれぞれについて)サイトや書籍がありましたらそちらもお願いいたします。

回答No.4

noname#119918 · ベストアンサー

>C言語でリストを作成するときに構造体を利用するのは、
>ポインタ？と要素を格納するからということでいいのでしょうか？
アップしたソースのリストは単方向リストというものでして、
1つのセルに、次のセルへのポインタ（リンクと言い替えても良いかもしれません）を持たせることで、先頭のセルから末尾まで順番にたどることができます。
ですから、1つのリストをたどるためには先頭のセルが絶対に必要であり、
また、逆にそれ以外のセルは必要ありません。

list.cを読んでもらえばわかりますが、
make_listは実際には先頭セルの領域を確保することが目的です。
つまり、リストの実体は先頭セルそのものだということです。

「セル」というものを表面化させたくなかったため、
typedef struct struct_list
{
cell* head; // 先頭ダミーセル
} list;
のようなlist構造体を用意し、
操作は全てlist構造体に対して行うという書き方をしました。
（この書き方の方が、いかにも「リスト」らしく見えるということもあります。）

もちろん、このような書き方をせずに、直接セルそのものを操作するような関数を書くことも可能でしょう。

>あと、回答１への補足に置いたソースなのですが、
>実際PASCALでは構造体を使っているのですが、
>C言語で配列のみで書いたこのソースはリストではないという
>認識でよろしいのでしょうか。
PASCALは全く知らないので、この質問に完全に答えることはできないのですが、Cでは普通、「配列」と「リスト」は別物です。
一般に配列は固定長であり、リストは可変長です。
そのため、リストは通常、メモリ確保関数 + ポインタを使って実現されます。

お礼

リストには配列は不向きということなんですね。
しかし、構造体とポイントについて処理の流れが今ひとつ
理解できてないので、申し訳ありませんがまた改めて質問することにします。

回答No.3

noname#119918

この手のものはあれこれ説明するよりも、
ソースを見て頂く方がわかりやすいだろうと思うので、
ざっと書いてみました。
文字数制限に引っかかりそうでしたので、
以下にアップしてあります。
http://knet.eco.coocan.jp/src/list.h ヘッダファイル
http://knet.eco.coocan.jp/src/list.c リスト操作関数
http://knet.eco.coocan.jp/src/list_main.c 上2つを利用するプログラム
動作を確認し、存分に改造してみてください。

補足

回答ありがとうございます。
ただ、構造体とポインタについて１から勉強してる最中で、ヘッダなどがまだ理解できていないので、まだ改造できそうにありません。
このレベルで今さら質問というのも厚かましいのは自覚していますが、
HKBさんの回答とは関係なくて申し訳ないのですけれど、
C言語でリストを作成するときに構造体を利用するのは、ポインタ？と要素を格納するからということでいいのでしょうか？
あと、回答１への補足に置いたソースなのですが、
実際PASCALでは構造体を使っているのですが、
C言語で配列のみで書いたこのソースはリストではないという
認識でよろしいのでしょうか。

回答No.2

sakusaker7

うーん、Cの初歩も危ない感じですね。
課題で使うというのだから授業なり講義なりあったと思いますが
ちゃんと受けてました?

int *p;
max = 4;
*p = &box[0];

ポインタ変数を宣言するときは
int *p;
ですけど、ポインタを更新するときには
p = &box[0];
のように、アスタリスクはつけません。

*p = ... と書いてしまうと、ポインタがさしている先に対する
操作になってしまいます。なので　p の値が未定義　になってしまうと。

>C言語のリストというのは構造体を使うのが普通なのでしょうか。

普通というか、構造体を使わずに連結リストを表現するのはまずやらないと思います。参考書のPascalプログラムでも、レコードを使っているのだし。

あと、元の質問にある
> 実行できてもなぜか延々とprintf命令が実行され続け、暴走？したり自分では解決できそうにありません。

ですが、多分連結リストの終端をきちんと認識できてないのだと思います。
多分連結リストの最後の要素の、次の要素へのポインタは特別な値
Pascalなら nil になっていると思われるので、Cに書き換えたときに
NULL なり、なんなりの値が最後の要素のポインタに入っているように
しておいて、それを見つけるまで繰り返しというようにします。

#1の回答であげたページの例で言うと
// 追加したデータの次のポインタをNULLにする
pend->pnext = NULL;
こういうことしているでしょ。

問題にあるPascalのプログラムだと、連結リストのアタマにくっつける方式なので
これとはちょっと違いますけど。

補足

補足のソースをご指摘通りに修正しましたら、
コンパイラエラーが起きず、ちゃんと配列の中身が表示されました。
ただ、アドレスについて合っているのかわからず、ポインタについて
もう一度おさらいすることにしました。

恥ずかしながら、構造体とポインタに触れるのがこの課題が出題されて初めてで、
さらにC言語自体が初心者用参考書を見てどうにかなる程度の課題しか解けません。
教えていただいたサイトに載っていた解説については、ほとんど課題に即した内容だと思うのですが、
私がそれを改造できるスキルを持ち合わせていないため
構造体についてテキストを読んでみます。

回答No.1

sakusaker7

とりあえず、その動かないC版のプログラムを貼り付けた方が
いい回答もらえるんじゃないかな。

元のPascalのを貼り付けて、Cに書き換えられません。じゃ
丸投げと大差ない。

データ構造
http://www5c.biglobe.ne.jp/~ecb/c/14_04_02.html

補足

おっしゃるとおりです、申し訳ありませんでした。
一応、質問する前に作ったものですが、
test2.c 10: 警告: p の値が未定義
test2.c 10: 警告: ポインタの型が合わない (=)
というエラーが出ました。
#include<stdio.h>

int main()
{
int box[] = {1,5,13,23,31};
int i;
int max;
int *p;
max = 4;
*p = &box[0];
for( i = 0; i <= max; i++ )
{
printf("box[%d] = %d, adress = %d\n",i,box[i],sizeof(int));
}
return 0;
}
挿入と削除については、教えていただいたサイトにありましたが、
C言語のリストというのは構造体を使うのが普通なのでしょうか。