コンテンツにスキップ

データ構造

出典: フリー教科書『ウィキブックス(Wikibooks)』
データ構造

本書は、効率的なデータ構造の作成と分析について説明しています。

  • 素朴なノード( node )構造。
  • 性能特性を数学的に議論するための漸近記法( asymptotic notation )
  • 組込みの 配列( arrays )
  • リスト構造( list structures )は、ノードまたは配列から構築されます。
  • イテレーター( iterators )は、シーケンス内のアイテムを列挙する抽象的なモデルです。
  • スタック( stacks )キュー( queues )は、後入れ先出しおよび先入れ先出しの順序で処理します。
  • 階層的な関係を検索したり表現するための二分法および一般的な 木( tree )構造
  • 最小および最大ヒープ( heaps )は、優先度に基づいて順序を表します。
  • グラフ構造( graph structures )は、データ要素間のより一般的な関係を表します。
  • ハッシュテーブル( hash tables )は、文字列やその他のオブジェクトを効率的に検索します。そして最後に、
  • 構造間のトレードオフ( trade-offs between the structures )、および最適な構造を選択するための戦略。

本書の内容を理解するためには、変数、演算式、if-else条件、ループ、サブルーチン(関数ともいう)、ポインター(参照またはオブジェクトハンドルともいう)、構造体(レコードまたはクラスともいう)、簡単な入出力、簡単な再帰を自分で操作して書ける程度にプログラミング言語に慣れていなければなりません。

データ構造の構築は多くの言語でアプローチが異なるため、疑似コード( pseudo-code )を使って、自分の言語に翻訳できるようにしています。

目次

[編集]


本書の開発に貢献しよう!

[編集]

本節は、英語版ウィキブックスの文章を和訳したもので、日本版ウィキブックスの現状を表していません。

ウィキブックは、オープンソースのソフトウェアプロジェクトに似た事業です。寄稿者は、他の人を助けたり、個人的に充実させたり、あるいは寄稿者自身の仕事のために何かを達成するためにプロジェクトのためのコンテンツを作成します(例:講義の準備)。

オープンブックは、オープンプログラムと同様に、完成までに時間を要しますが、読者からのささやかな貢献でも大きな恩恵を受けることができます。たとえば、よりよい本にするために、本文の「バグ」(バグは、組版、説明、技術、美学、その他にあるかもしれません)を修正することができます。バグを修正する機会を見つけたら、「編集」をクリックして、変更を加え、「保存」をクリックするだけです。他の投稿者は、あなたの変更が本にとって適切であるかどうかを確認するために、あなたの変更をレビューすることができます。もし不明な点があれば、ディスカッションのページで質問することができます。常識的な範囲でお願いします。

より大きな貢献をしたい場合は、短すぎるセクションや章など、もっと作業が必要な部分を見て、書き始めることができます! 内容の重複を避けるため、必ず最初に残りの部分に目を通すようにしてください。さらに、投稿者のためのガイドラインのページ(Guidelines for Contributors)を読んで、一貫性のあるヒントやアドバイスを得る必要があります。

一度にすべてを寄稿する必要はないことに注意してください。テンプレート「{{TODO|description of what remains to do}}」をページに追加すれば、おそらく他の人があなたの代わりにその部分を仕上げてくれるでしょう。

この本は、貢献しやすくするために、意図的に焦点を絞ってあります(そうすれば、最終目標が明確になりますから)。本書はアルゴリズムに関する3冊のコンピュータ科学の教科書のうちの1冊で、『アルゴリズム(英:Algorithms)』のアルゴリズムのテクニックに続き、『データ構造とアルゴリズム(英:Advanced Data Structures and Algorithms)』の上級編で終わります。もし、この3冊の本のどれにも載っていないトピックを投稿したい場合は、より折衷的な性格を持つAdvanced bookに載せてみてください。また、もしそのトピックが基本的なものだと思うのであれば、アルゴリズム(Algorithms)かデータ構造(Data Structures)のディスカッションページで提案することも可能です。

さらに、付録としてデータ構造の実装(AdaCC#PerlPythonJavaRubySchemeのいずれか)も歓迎されます。

脚註

[編集]
[Aho] Alfred V. Aho, Jeffrey D. Ullman, John E. Hopcroft. Data Structures and Algorithms. Addison Wesley, 1983.
[CLRS] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. McGraw-Hill, 2001.
[Knuth] Donald E. Knuth. The Art of Computer Programming, Volumes 1-3. Addison-Wesley Professional, 1998.
[Kishor] S.B. Kishor Data Structures, Edition 3. Das Ganu Prakashan, Nagpur, 2008.
[Judith] Judith L Gersting. Mathematical Structures for Computer Science. W.H. Freeman and Company,2014.

さらに、今日のアルゴリズムの範囲を示すオンラインリファレンスとして アルゴリズムの辞典 があります。