Cコーディングトレーニングの実際の使用例

Question

a recent question私は、クォードツリーのような他のものに取り組む前に、バイナリツリー、レッドブラックツリーなどの基本的なデータ構造を試してみることが奨励されました。

Cでの私の経験はかなり限られています。私は参照、malloc、reallocなどの簡単な操作に精通していますが、単純なデータ（2Dグリッド、イメージストレージ、文字列など）のポインタを使用することを恐れています。このような構造を理論から取り除くことを難しくするCの「ハード」部分には慣れていないので、私はこれに作業コードをコピーしたくありません。

私が知りたいことは、基本的な木に取り組むためには、それらのための実用的なアプリケーションです。実践的な目的を知ることができるように、いくつかのガイドライン（「これをしないでください」または「パフォーマンスを殺す」または「これをしないでください」または「メモリがリークします」）私が理論を覚えていても、その応用を理解するためにどのような実験を行うべきかはまだ分かりません。

私は大部分がプレーンCを使用しようとしていますが、それを読むときにはC++ /＃コードを理解できませんが、役立つ場合はルア言語を精通しています。

これまでは、Luaを辞書検索とデータ（およびロジックの一部）を組み合わせてコーディングし、すべてのビデオとオーディオのストレージ、重い数学とC言語の「世界」ストレージを残していました（グリッド構造と、あまりにも強烈な衝突検出アプローチ（マップの1/24にオブジェクトを配置するための線形配列を使用し、コード用語では複雑なものはありません））。私はいつもルアのソリッドコードをいくつかの関数に依存することができるので、C言語をもっと学ぶのを怠りましたが、今は知識の不足でそれを支払っています。

したがって、「データツリーの基本的なユースケースは何ですか？」という質問を作成するには私が今までに持っている唯一のアイデアは、文字列（ファイル名？）をテクスチャにマッチさせるためにスプレイツリーを使用することです。それは有効な使用ですか？私はそれから始めるべきですか？

Answer 1

データツリーの用途の1つは、パーサ/コンパイラを作成するときでした。ソースを分割して（レキシカル分析）、構文解析（文法の検証）を実行した後、ソースコード（Syntactic tree）のツリー構造を構築し、コンパイラの次の部分が繰り返し訪れました。

ツリーの別の使用法は、文字列が非常に短時間でメモリに格納されている場合にDAWG（Directed acyclic word graph）を使用することができます。

最後に、古典的な使用方法は、データツリーを使用してTravelling Salesman problemのソルバを作成し、都市をメモリに格納することです。

古典的なSedgewick Algorithms in C, Part 5: Graph Algorithmsには、アクセス権がある場合でも例がたくさんあります。