「データ構造」の版間の差分
編集の要約なし |
編集の要約なし |
||
(同じ利用者による、間の1版が非表示) | |||
1行目: | 1行目: | ||
[[Image:binary_tree.svg|thumb|[[二分木]]のデータ構造]] |
[[Image:binary_tree.svg|thumb|[[二分木]]のデータ構造]] |
||
[[File:Hash_table_3_1_1_0_1_0_0_SP.svg|リンク=https://en-two.iwiki.icu/wiki/File:Hash_table_3_1_1_0_1_0_0_SP.svg|サムネイル|ハッシュテーブルのデータ構造]] |
|||
'''データ構造'''(データこうぞう、{{lang-en-short|data structure}})とは、[[コンピュータプログラミング]]での、[[データ]]の集まりの形式化された構成である。格納された各データの参照や修正といった管理を容易にするための構成である<ref>{{Cite book|url=https://dl.acm.org/citation.cfm?id=1614191|title=Introduction to Algorithms, Third Edition|last=Cormen|first=Thomas H.|last2=Leiserson|first2=Charles E.|last3=Rivest|first3=Ronald L.|last4=Stein|first4=Clifford|date=2009|publisher=The MIT Press|isbn=978-0262033848|edition=3rd}}</ref><ref>{{cite book|last1=Black|first1=Paul E.|editor1-last=Pieterse|editor1-first=Vreda|editor2-last=Black|editor2-first=Paul E.|title=Dictionary of Algorithms and Data Structures [online]|date=15 December 2004|publisher=[[National Institute of Standards and Technology]]|chapter-url=https://xlinux.nist.gov/dads/HTML/datastructur.html|access-date=2018-11-06|chapter=data structure}}</ref><ref>{{cite encyclopedia|encyclopedia=Encyclopaedia Britannica|title=Data structure|url=https://www.britannica.com/technology/data-structure|access-date=2018-11-06|date=17 April 2017}}</ref>。一定の関係性を持たせた[[データ型]]のコレクションであり、[[値 (計算機科学)|データ値]]に適用するための[[関数 (数学)|関数]]や[[プロシージャ|手続き]]も格納されることがある<ref>{{Cite book|url=http://dl.acm.org/citation.cfm?id=1074100.1074312|title=Encyclopedia of Computer Science|last=Wegner|first=Peter|last2=Reilly|first2=Edwin D.|publisher=John Wiley and Sons|isbn=978-0470864128|location=Chichester, UK|pages=507–512|date=2003-08-29}}</ref>。データの[[代数的構造]]とも言われる。 |
|||
== 概要 == |
|||
'''データ構造'''(データこうぞう、{{lang-en-short|data structure}})とは[[コンピュータプログラミング]]において、規則化された連結関係によるデータ値(データ要素)の集合体である。[[情報工学|計算機科学]]では、効率的に参照可能かつ修正可能なデータ構成、データ管理、データ蓄積と定義されている。データ構造には[[関数 (プログラミング)|関数]]や[[演算子|オペレータ]]も付加されることがある。 |
|||
[[ソフトウェア]]開発において、データ構造についてどのような[[設計]]を行うかは、[[プログラム (コンピュータ)|プログラム]]([[アルゴリズム]])の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。多くのプログラムの設計において、データ構造の選択は主要な問題である。これは大規模システムの構築において、実装の困難さや質、最終的なパフォーマンスはベストのデータ構造を選択したかどうかに大きく依存してきたという経験の結果である。 |
[[ソフトウェア]]開発において、データ構造についてどのような[[設計]]を行うかは、[[プログラム (コンピュータ)|プログラム]]([[アルゴリズム]])の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。多くのプログラムの設計において、データ構造の選択は主要な問題である。これは大規模システムの構築において、実装の困難さや質、最終的なパフォーマンスはベストのデータ構造を選択したかどうかに大きく依存してきたという経験の結果である。 |
||
8行目: | 9行目: | ||
データ構造は専門的な、あるいは非専門的な(すなわち、あらゆる)プログラミングにとって非常に重要なので、C++における[[Standard Template Library|STL]]や、Java API、および[[.NET Framework]]のような[[プログラミング言語]]の標準ライブラリや環境において多くのデータ構造がサポートされている。データ構造が[[実装]]を表すのか[[インタフェース (情報技術)|インターフェース]]を表すのかについてはいくらか議論がある。どのように見えるかは相対的な問題なのかもしれない。データ構造は2つの関数の間にあるインターフェイスとして見ることもできるし、[[データ型]]に基づいて構成されたストレージにアクセスする方法を実装したものとして見ることもできる。 |
データ構造は専門的な、あるいは非専門的な(すなわち、あらゆる)プログラミングにとって非常に重要なので、C++における[[Standard Template Library|STL]]や、Java API、および[[.NET Framework]]のような[[プログラミング言語]]の標準ライブラリや環境において多くのデータ構造がサポートされている。データ構造が[[実装]]を表すのか[[インタフェース (情報技術)|インターフェース]]を表すのかについてはいくらか議論がある。どのように見えるかは相対的な問題なのかもしれない。データ構造は2つの関数の間にあるインターフェイスとして見ることもできるし、[[データ型]]に基づいて構成されたストレージにアクセスする方法を実装したものとして見ることもできる。 |
||
== 脚注 == |
|||
<references/> |
|||
== 関連項目 == |
== 関連項目 == |
2021年12月10日 (金) 11:04時点における版
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Binary_tree.svg/220px-Binary_tree.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7d/Hash_table_3_1_1_0_1_0_0_SP.svg/220px-Hash_table_3_1_1_0_1_0_0_SP.svg.png)
データ構造(データこうぞう、英: data structure)とは、コンピュータプログラミングでの、データの集まりの形式化された構成である。格納された各データの参照や修正といった管理を容易にするための構成である[1][2][3]。一定の関係性を持たせたデータ型のコレクションであり、データ値に適用するための関数や手続きも格納されることがある[4]。データの代数的構造とも言われる。
概要
ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム(アルゴリズム)の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。多くのプログラムの設計において、データ構造の選択は主要な問題である。これは大規模システムの構築において、実装の困難さや質、最終的なパフォーマンスはベストのデータ構造を選択したかどうかに大きく依存してきたという経験の結果である。
多くの場合、データ構造が決まれば、利用するアルゴリズムは比較的自明に決まる。しかし場合によっては、順番が逆になる。つまり、与えられた仕事をこなす最適なアルゴリズムを使うために、そのアルゴリズムが前提としている特定のデータ構造が選択される。いずれにしても適切なデータ構造の選択は極めて重要である。この洞察は、多くの定式化された設計手法やプログラミング言語において、データ構造がアルゴリズムよりもキーとなる構成要素となっていることに現れている。大半の言語は異なるアプリケーションにおいてデータ構造を安全に再利用できるよう、実装の詳細をインターフェースの背後に隠蔽するような、モジュール化のしくみを備えている。C++やJavaといったオブジェクト指向プログラミング言語はクラスをこの目的に用いている。
データ構造は専門的な、あるいは非専門的な(すなわち、あらゆる)プログラミングにとって非常に重要なので、C++におけるSTLや、Java API、および.NET Frameworkのようなプログラミング言語の標準ライブラリや環境において多くのデータ構造がサポートされている。データ構造が実装を表すのかインターフェースを表すのかについてはいくらか議論がある。どのように見えるかは相対的な問題なのかもしれない。データ構造は2つの関数の間にあるインターフェイスとして見ることもできるし、データ型に基づいて構成されたストレージにアクセスする方法を実装したものとして見ることもできる。
脚注
- ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms, Third Edition (3rd ed.). The MIT Press. ISBN 978-0262033848
- ^ Black, Paul E. (15 December 2004). “data structure”. In Pieterse, Vreda; Black, Paul E.. Dictionary of Algorithms and Data Structures [online]. National Institute of Standards and Technology 2018年11月6日閲覧。
- ^ "Data structure". Encyclopaedia Britannica. 17 April 2017. 2018年11月6日閲覧。
- ^ Wegner, Peter; Reilly, Edwin D. (2003-08-29). Encyclopedia of Computer Science. Chichester, UK: John Wiley and Sons. pp. 507–512. ISBN 978-0470864128