Javaでデータ構造

質問

最近Javaの学習を開始しました。
入門書をちょっと読んでみたのですが、気になったことがあります。

2分木などのデータ構造は、一つのオブジェクトの中に入れるのでしょうか?
それとも、オブジェクトをつないでデータ構造を組み立てるのでしょうか?
直感的に、前者のような気がしているのですが、ハッキリ分かりません。

参考：
お遊びのプログラムしか作ったことが無いのですが、一応Cは一通りやりました。

回答No.6

ranx · ベストアンサー

「データ構造」という語の使われ方に二通りあります。

一つは、部分と部分が相互に関連し合っているデータが全体としてどういう形になっているかという意味です。
例えば、氏名と出身県が書かれたレコードが集まったデータがあったとします。このデータが氏名順にソート
されている場合と出身県順にソートされている場合とでは、構造が異なります。木のようなデータであれば、
それはまたそれなりの構造があるわけで、恐らくdet_mul2さんの使い方はこれに近いと思います。

もう一つは、一まとまりの情報がどのような形式で実現されているかという意味です。先の例で言うと、氏名の
後に出身県が書かれている場合と出身県の後に氏名が書かれている場合とでは構造が違うというわけです。
「抽象データ型が表現している数学モデルをコンピュータの記憶内に実装したものがデータ構造である。」と
いう表現は、こちらに近いと思います。

実のところ、後者の意味での「データ構造」という用語の使用は、私は誤用だと思っています。（つまり
det_mul2さんが正しい。）ですから、三つの概念の関係で言えば、抽象データ型の概念を発展させたものが
クラスであって、データ構造とは必ずしも結びつく概念ではないと、私は思います。（テキストを書かれた方は、
また違った考え方なのでしょうけれど。）

お礼

ありがとうございました。

解りましたー！なぜこんなに話が食い違っていたのかが…。
要は、ぼくと回答者の方々との間で、言葉の定義が違っていたということなんですね。

例のテキストをもう一度注意深く読んでみたところ、そのテキストでの
抽象データ型の定義は、やはり、
「抽象データ型～データ構造」（～は、左辺を右辺で定義するという意味）
というものでした。それは、スタックのデータ構造を引き合いに出して、これは
抽象データがただ、という記述があったので、間違いありません。
つまり、このテキストは、
・抽象データ型の定義が、現在に於いては正しくない。
・データ構造という言葉の使い方は、ranxさんの意味で、一応正しい。

ぼくと回答者のかたがたとの間で、「抽象データ型」という言葉の
定義が食い違っていたのですね。
ぼくの「抽象データ型」の定義は、テキストの定義に基づき、
「抽象データ型～データ構造」
ranxさんは、
「抽象データ型～(Cでいえば）構造体に関数を足したみたいなもの。(Javaでいえば）クラス」

実は例のテキストは、今から十数年も前に書かれた本なのです。
書かれてから今までの間に、「抽象データ型」という言葉のメジャーな定義が
変わってしまったのかもしれませんね。

>三つの概念の関係で言えば、抽象データ型の概念を発展させたものが
>クラスであって、データ構造とは必ずしも結びつく概念ではないと、私は思います。

そうだったんですか～。つまり、
「抽象データ型≠データ構造」
「抽象データ型＝クラス」(これにより、No.5のお礼に書いた「抽象データ型≠クラス」は否定された。）
ということだったのですね。

おかげで完全に問題は解決しました。暫くしたら閉じようと思います。
ありがとうございました。

P.S.自分の頭の中を整理しようとしながら書いてしまった結果、またまたこんなに長くなってしまったことをお詫びします。

回答No.9

mrt136

ranx さん
ご回答ありがとう御座います。
参考URL見ました。（JavaHouseを出されるとグゥの音も出ないですね。。。）
なるほど。と言った感じです。
私自身、CからC++経由でJavaにたどり着いたので、ポインタ＝Cのポインタ＝アドレス参照
言う固定概念があったのかも知れません。

>例えばPASCALという言語にもポインタの概念があります。しかし、PASCALの
>ポインタにはアドレスの概念はありません。ポインタに数値を加えるといった
>操作もありません。それでもポインタはポインタです。字義通りにとれば

残念ながらPASCALを知りませんが、ポインタの本来の意味を知れと言う事ですね。
どうも、結果的にポインタと同じであるとは理屈では分かっているつもりなんですが、
「Javaにポインタがある」「Javaは全てがポインタである」と言う事に若干の抵抗を感じてしまいますね。。。
参考URLにあるような、「今時のプログラマ．．．」ではないと言う事でしょうね。。。
う～ん、微妙だ。。。

でも、おっしゃる事はよく理解出来ました。
ありがとうございました。

det_mul2さん、最初から最後まで横槍で申し訳ありませんでした。

お礼

>最初から最後まで横槍で申し訳ありませんでした。

いや、僕も、お二人のやり取りから学ぶことが在ったので、
むしろ歓迎でした。

それでは、閉めたいと思います。
本当は6/3(月)の夜に閉めようと思っていたのですが、サッカーW杯に夢中になって
忘れていました。遅くなってごめんなさい。6/4

回答No.8

ranx

やっぱり蛇足だったな。（笑）

> ポインタとはどういったものでしょう。。。
> 私の理解ではメモリ上のアドレスを指すものと言う認識しかありません。
> それは、Javaには無いんじゃぁないでしょうか？

例えばPASCALという言語にもポインタの概念があります。しかし、PASCALの
ポインタにはアドレスの概念はありません。ポインタに数値を加えるといった
操作もありません。それでもポインタはポインタです。字義通りにとれば
ポインタとは「point＝指し示す」機能を持ったものに他なりません。それで
十分にプログラミング上の概念としては構成できるわけです。Cのポインタは、
そうした意味からすれば、少し拡張されたものと考えることもできます。
ある程度の機械志向性を持っていることがCの特性ですから、Cの志向するもの
から言えば妥当な拡張と言えますが、操作概念としての「ポインタ」と
「アドレス」を混同すべきではないと思います。

Javaの場合、「参照型」という語をよく使います。プリミティブ型以外の変数
はすべて参照型です。参照型の変数を宣言しても、それだけではそのクラスの
実体が作られるわけではありません。newという演算子を働かせることによって
初めて実体（インスタンス）が作られます。（もう既に十分ご存知のことです
よね。）参照型の変数は、それを「指し示すもの」として使われます。つまり
ポインタです。

以上、質問者への直接の回答ではありませんが、参考になれば幸いです。

参考URL：

http://java-house.jp/ml/archive/j-h-b/028662.html#body

回答No.7

mrt136

すみません　det_mul2さん。。。
ranx さんにお尋ねします。。。

>蛇足ですが、「Javaにはポインタが無い」という表現はよく聞きますが、全くの誤解です。むしろ、プリミティブ
>型を除けば、Javaにはポインタしか無いと考えるべきです。（「ポインタ」という語こそ使いませんが。）

との事ですが、ポインタとはどのようなものを指すのでしょうか。。。
「Java にはポインタしか無い」と言うのは、少し誤解を招くような気がしますが。。。
ポインタとはどういったものでしょう。。。
私の理解ではメモリ上のアドレスを指すものと言う認識しかありません。
それは、Javaには無いんじゃぁないでしょうか？
ポインタに１つ加算したら、メモリ上の次のアドレスを指すとか。。。
まぁ、広い意味では上の意見には賛成なんですが、そう言い切ってしまうと変に誤解を招くような気がします。

もし、私の考えが間違っていると言う事なら、もう一度ご回答頂ければと思います。。。

私の質問では無いところで、このような返しはあまり良く無いとは承知していますが、
私の今後の勉強の為にもご教授頂ければと思います。
私のこの意見に対しての発言だと思いましたので、あえてご質問させて頂きました。
　　　　　　　↓
>いえ、可能です。ポインタと言う概念はＪａｖａにはありませんが。
>クラスをメンバとして持たせる事がポインタを持たせる事と結果的に
同じだと思いますが。。。

既に自信なしになっていますが。。。

回答No.5

ranx

> Javaの「クラス」って、Cの構造体に関数を足しただけみたいなもの
「だけ」というのは気に入りませんが、データの型とその処理方法を一まとめにしたものを
抽象データ型といい、オブジェクト指向の出発点として重要な概念です。データへのアクセスが
発生する箇所が限定されるため、プログラマが追跡しやすくなるためです。

もちろん、これだけならば、おっしゃるようにＣでもある程度似たようなことはできます。
オブジェクト指向が有用であるのは、クラスを拡張して新しいクラスを作るといったことが簡単に
できるところにあります。

Ｃの構造体の場合、一つの構造体は別の構造体を内部に含むことができます。こんな感じです。
struct CPU {
/* CPU の属性等 */
}
struct Computer {
struct CPU cpu;
/* その他のComputerの属性等 */
}
A Computer has a CPU. という関係になるわけです。

Javaのクラスでも、こうした関係はもちろん可能ですが、それに加えて、あるクラスが別のクラスの
サブクラスとなるという関係が記述されます。
class Computer {
/* Computerの属性等 */
}
class NotebookComputer extends Computer {
/* NotebookComputerの属性等 */
}
NotebookComputerはComputerの属性等を継承します。A NotebookComputer is a Computer. という関係です。
NotebookComputerのインスタンスはそのままComputerのインスタンスとして扱うことができます。
Ｃのように"has a"という関係だけで、これに近い関係を記述しようとすれば、NotebookComputerがComputerを
内部に持っているという形式で表現せざるをえないでしょう。ComputerとしてのNotebookComputerを扱おうと
すれば、内部に持っているComputerを引っ張り出さなくてはなりません。本当はNotebookComputerがComputerを
内部に持っているという関係が事実を反映したものではないので、このような扱いにくさが出てしまうのです。

ご質問に対する直接の回答ではないかもしれませんが、オブジェクト指向における階層構造が"has a"と"is a"
という二種類の系統で成り立っていることを理解しないと、それ以前の方法論との違いがよく分からないと
思い、補足させて頂きました。

蛇足ですが、「Javaにはポインタが無い」という表現はよく聞きますが、全くの誤解です。むしろ、プリミティブ
型を除けば、Javaにはポインタしか無いと考えるべきです。（「ポインタ」という語こそ使いませんが。）

お礼

ありがとうございました。

>「だけ」というのは気に入りませんが、データの型とその処理方法を一まとめにしたもの
>を抽象データ型といい、オブジェクト指向の出発点として重要な概念です。

「抽象データ型」という言葉を出すと、ややこしくなってしまうかも…と思って今まで出さないで来たのですが、知っておられたのですね。^。^
ぼくは、実は学生で、アルゴリズム論の講義を受けているのですが、そこで使っているテキストに、
「抽象データ型が表現している数学モデルをコンピュータの記憶内に実装したものがデータ構造である。」
という記述があるのです。つまりこれは、形は違えど、「抽象データ型＝データ構造」といっているわけです。
Javaのクラスの解説を読んだ時、「クラス＝抽象データ型なのかな？すなわち、クラス＝データ構造なのかな?…きっとそうなんだろう。」と思ってしまったのです。つまり、「一つのオブジェクトの中に、データ構造がまるまる入っているのかな？きっとそうなんだろう。でも、それを明示する記述は本のどこにもない。不安だな…。」と思っていて、それで今回の質問に至ったのです。今回それが間違っていたことが分かりました。「クラス≠抽象データ型」である。つまり、「一つのオブジェクトの中に、(ポインタでデータ同士をリンクした)データ構造をまるまる含むことはできない。」ということだったのですね。

>もちろん、これだけならば、おっしゃるようにＣでもある程度似たようなことはできます。

という御発言も、それを支えてくれているということですよね？(まだちょっと不安なのです…)

>オブジェクト指向が有用であるのは、クラスを拡張して新しいクラスを作るといったこと>が簡単にできるところにあります。

すみません。「継承」のところは、まだ、最初の概要説明みたいなところしか読んでいないのです…。(全部読まずに質問してごめんなさい。ぼくは我慢弱いのです…)
だから、CとJavaの違いを認識できなかったんですね…。
要は、「Javaの真価は継承にある。」ということだったんですね。（これを知る前は、「Javaの真価は、データ構造を一つのオブジェクトと捉えることだ。」とか思っていたのです。…この捉え方にはあまり価値はないのかな…。）

>オブジェクト指向における階層構造が"has a"と"is a"
>という二種類の系統で成り立っていることを理解しないと、
ここの所をしっかと踏まえた上で、これから継承について学習していこうと思います。

P.S.自分の頭の中を整理しようとしながら書いてしまった結果、こんなに長くなってしまったことをお詫びします。
また、
自分ではもう、「みなさんのおかげで問題解決しました。」と思っているのですが、まだ何か勘違いがあるかもしれないので、後3日程閉じずにいようと思います。

回答No.4

mrt136

＞Javaでは、一つのクラスのなかにメンバとして
＞「ポインタでリンクされたデータ群」は含めることはできない。
＞もともとJavaで提供されている型の変数(int型,double型などの変数)
＞しか一つのクラスの中にメンバとして含めることはできない。
＞ということでいいのでしょうか？

いえ、可能です。ポインタと言う概念はＪａｖａにはありませんが。
クラスをメンバとして持たせる事がポインタを持たせる事と結果的に
同じだと思いますが。。。
node クラスは node クラスを管理する。と、言う事は、管理されている
node クラスは node クラスを管理しているのです。。。
＃なんか、訳わからんけど。。。Ｃで言うところの自己参照型構造体と一緒か。。。

何か、お互いに誤解がありそうなので、確認したいのですが、

det_mul2 さんは、
＞2分木みたいなデータ構造とそれに対する操作(Insert,Delete,Minimumなど)
＞をカプセル化して一つのオブジェクトとみなしてやるのかな？と思っていまし
た。

とは、どの様なものを想定されているのでしょうか？
具体的に示して頂けますか？
Ｃだったらこうしますけど、Ｊａｖａだったらどうします？
みたいな質問だったらもう少し要領を得た回答が得られるかも知れません。。。

補足

ありがとうございました。

>どの様なものを想定されているのでしょうか？

上のNo.5のお礼の欄に書いてあるようなものです。つまりぼくは、
「(Javaの)クラス＝データ構造なのかな？」と思っていたというわけなのです。
それで、それは否定されました。(多分)

>Ｃで言うところの自己参照型構造体と一緒か。。。

この御発言も、それを裏付けていますよね。

回答No.3

mrt136

横槍ですみません。。。
要は、「会社」と言うクラスと、「社員」と言うクラスを作り、「会社」クラスは
「社員」クラスを管理するクラスと言う事になります。
２分木に関しては、No.2の方もおっしゃっていますが、例が悪いですね。
上の例を使ってみると、node クラスは node クラスを管理するクラスと言う事に
なるのかな？
それらの繋がりで必要な２分木を作成する様になるんじゃないかな？
とりあえず、オブジェクト指向の勉強されると良いかも知れませんね。
Ｃとは考え方がかなり違いますので。

補足

ありがとうございました。

>横槍ですみません。。。

そんな...ぜんぜん横槍じゃないですよ。

>上の例を使ってみると、node クラスは node クラスを管理するクラスと言う事に
>なるのかな？

Javaでは、一つのクラスのなかにメンバとして
「ポインタでリンクされたデータ群」は含めることはできない。
もともとJavaで提供されている型の変数(int型,double型などの変数)
しか一つのクラスの中にメンバとして含めることはできない。
ということでいいのでしょうか？
いいとすると、Javaの「クラス」って、Cの構造体に関数を足しただけみたいなもの、
ということになると思うのですが...。もしこの解釈があってるとすると、やっぱり、
CとJavaってそんなに変わらないんじゃないのかな...と思えてくるのですが...

JavaとCとの違いって、もともと提供されている変数(int型,double型などの変数)
へのアクセスが厳しくチェックされているかどうかだけ、なのかな？と思えて来ました。
この捉え方は正しいのでしょうか？

えと、No.2の方への捕捉にも書いたとおり、ぼくは表現があまりうまくないので、
不明な点があれば、遠慮無く指摘をおねがいします。

回答No.2

ranx

話が抽象的すぎて、仰りたいことが今ひとつはっきりしないように思うのですが、

> 2分木みたいなデータ構造とそれに対する操作(Insert,Delete,Minimumなど)
> をカプセル化して一つのオブジェクトとみなしてやるのかな？と思っていました。
> こう考えたら、抽象度が高くてヒトにやさしいプログラミングができそう…、
> と思ったので。

2分木の場合、各ノードはそれ自体2分木ですよね。そう考えればデータ構造全体に
対するメソッドも部分に対するメソッドもある意味で変わりはないわけで、その
違いを明確にしたいという主旨のご質問であれば、挙げた例が悪すぎるように
思います。

一般的には、単位的なデータも集合的なデータもそれぞれにオブジェクトとして
扱われると思います。「会社」というクラスと「社員」というクラスがあったと
して、「会社」のインスタンスに対するリクエストを「会社」インスタンスは
「社員」へのリクエストに分解することで処理するでしょう。要はそういう話
だと思いますが．．．。

お礼

下の補足の欄で、
「質問してください。」→「指摘してください。」
に訂正します。
質問者は僕なのに、何か変ということで…

補足

ありがとうございました。

>話が抽象的すぎて、仰りたいことが今ひとつはっきりしないように思うのですが、
>一般的には、単位的なデータも集合的なデータもそれぞれにオブジェクトとして
>扱われると思います。
>「会社」というクラスと「社員」というクラスがあったと
>して、「会社」のインスタンスに対するリクエストを「会社」インスタンスは
>「社員」へのリクエストに分解することで処理するでしょう。要はそういう話
>だと思いますが．．．。

ええと、ぼくが言いたかったのは、集合的なデータもオブジェクトとして
扱えたら良いんじゃないのかな…というモノでした。(分かりやすい表現をお借りします。)
ところで、この、「会社」と「社員」の例の、「会社」にあたるクラスを、Javaでは定義できるんでしょうか?No.1の方の回答からすると、出来ないという事になると思うのですが、
>一般的には、単位的なデータも集合的なデータもそれぞれにオブジェクトとして
>扱われると思います。
この文章を見ると少し迷ってしまいます。要は、Javaでクラスとして厳密に定義はできないが、プログラマーはみんなクラスのインスタンスと見なしている(ポインタが必要なデータ構造を)、と言うことであっていますでしょうか?

ぼくは、考えていることを言葉に表現するのが余り得意ではないので、曖昧なところがあるかもしれません。そのときは質問してください。よろしくおねがいします。

回答No.1

wolv

私なら，nodeをひとつのclassとしてコーディングしておき，
実際に２分木をつくるときには，
複数の node classのインスタンスを使って一つの２分木とする，
と思います．
つまり，どちらかというと後者のやり方です．

補足

ありがとうございました。

そうなんですか？
2分木みたいなデータ構造とそれに対する操作(Insert,Delete,Minimumなど)
をカプセル化して一つのオブジェクトとみなしてやるのかな？と思っていました。
こう考えたら、抽象度が高くてヒトにやさしいプログラミングができそう…、
と思ったので。要するに都合のいいように解釈していたのです…。

でも違うんですね…。オブジェクトをノードとしてデータ構造を構成するんですね…。
あの、これって、Cとあまり変わらないんじゃ…と思うのですが、どうなのでしょうか？データ構造全体を一つのオブジェクトと見なす考え方って無いんでしょうか?僕はこっちの方が良いような気がしているのですが、どう思いますか?この考え方を、実際に採用すると、実は不都合があるってことなのでしょうか?