問題タブ [linked-list]

私はしばらくの間、クラスのJavaプロジェクトに取り組んでいます。これは、リンクされたリスト (ここでは と呼ばれ、 とAddressList呼ばれる単純なノードを含むListNode) の実装です。問題は、すべてを再帰アルゴリズムで行う必要があることです。私はすべてのことを1つの方法でうまく行うことができました：public AddressList reverse()

リストノード:

現在、私のreverse関数は、再帰を許可する引数を取るヘルパー関数を呼び出すだけです。

の署名を持つヘルパー関数を使用しますprivate ListNode reverse(ListNode current)。

現時点では、スタックを使用して繰り返し動作させていますが、これは仕様が要求するものではありません。私は C 言語でアルゴリズムを再帰的に逆にして手動で Java コードに変換するアルゴリズムを見つけましたが、それは機能しましたが、理解できませんでした。

編集：気にしないで、その間にそれを理解しました。

私がここにいる間、誰かこのルートに何か問題があると思いますか?

現在取り組んでいるプロジェクトのシンボル テーブルを作成しています。シンボル テーブルの保存と作成に利用できるさまざまな方法の長所と短所について、人々の意見はどうなっているのかと思っていました。

私はかなりの検索を行いましたが、最も一般的に推奨されるのは、バイナリ ツリー、リンク リスト、またはハッシュ テーブルです。上記のすべての利点と欠点は何ですか? (C++ で作業)

私はたくさんのリストと配列を使用していますが、配列リストをリンクリストと同じくらい簡単に使用できないというシナリオにはまだ遭遇していません。リンクリストが特に優れている場合の例を誰かが教えてくれることを期待していました。

C++ でリストを作成するにはどうすればよいですか? リンクされたリストを作成するために必要です。どうすればそれを行うことができますか？私が従うことができる良いチュートリアルや例はありますか?

私はデータベーステーブルレコードの構造に似たCの構造を持っています。selectを使用してテーブルをクエリすると、取得するレコードの数がわかりません。selectクエリから返されたすべてのレコードを構造体データ型の配列に格納したいと思います。

どちらの方法が最適ですか？

方法1：配列サイズを見つけて割り当てる

1. まず、テーブルからselect count（*）を実行して、レコードの数を取得します
2. 静的配列を割り当てる
3. select * from tableを実行してから、各レコードを構造内のループに格納します。

方法2：単一のリンクリストを使用する

どの実装が最適ですか？

私の要件は、すべてのレコードが揃ったら、おそらくそれらのコピーか何かを作成することです。ただし、ランダムアクセスは必要なく、特定のレコードの検索は行いません。

ありがとう

長さが不明な片方向リストがあるとします。テールまで M ステップのノードを見つけたいとします。

たとえば、単独のリストは次のようになります: (A)->(B)->(C)->(X)->(Y) および M = 2. この場合、出力は (C) へのポインターになります。

このクイズに直面したとき、私の最初の反応は、単一リンク リストをトラバースして長さ N を取得することです。次に、2 回目は単一リンク リストをトラバースしますが、NM-1 ステップだけを進めます。時間の計算量は O(n) で、空間の計算量は O(1) です。

次に、ワントラバース方式でそれを行うための解決策を見つけることに挑戦します。解決策は、2 つのポインタを持つことです。2 番目のポインターは、最初のポインターより M ステップ遅れています。これらの 2 つのポインターは、同じペースで前進します。最初のポインターが末尾に到達すると、2 番目のポインターが結果になります。

この質問について深く考えてみた結果、2 番目の「トリッキーな」解決策が最初の解決策よりも優れているとは思えません。これは 1 回のトラバースですが、2*NM ポインターの割り当ても伴います。

この質問について考えたことはありますか？本当に高速な他のソリューションはありますか?

リストをトラバースするために2つの変数のみを使用して、リンクされたリストがループするかどうかを見つけるアルゴリズムを知っている人はいますか? オブジェクトのリンクされたリストがあるとします。オブジェクトの種類は関係ありません。1 つの変数にリンクされたリストの先頭へのポインターがあり、リストを走査するための別の変数が 1 つだけ与えられます。

したがって、私の計画は、ポインター値を比較して、同じポインターがあるかどうかを確認することです。リストのサイズは有限ですが、巨大になる可能性があります。両方の変数を先頭に設定してから、他の変数でリストをトラバースし、他の変数と等しいかどうかを常に確認できますが、ループにヒットすると、ループから抜け出すことはできません。リストをトラバースしてポインター値を比較する速度が異なることに関係していると思います。何かご意見は？

リンクされたリストを自己参照データベース テーブルとして実装しました。

ここで、Id は主キーで、ParentId はリストの前のノードの ID です。最初のノードには、ParentId = NULL があります。

ここで、テーブルから SELECT を実行し、リストのノードとして表示される順序で行を並べ替えます。

例: テーブルに行が含まれている場合

次に、基準を使用して並べ替えると、次のようになります。

コントロールとしてSomeData列を使用することになっているので、 ORDER by SomeData をごまかさないでください :-)

C++でプログラミングを始めたばかりです。

アップデート

あなたたちは正しかった、問題は私のリストを繰り返すことではない。問題は、リストに何かをプッシュしようとしているときのようです。

正確なエラー：

mouse.cpp：ファンクションvoid mouseHandler(int, int, int, int)': mouse.cpp:59: error: conversion fromポイント*'から非スカラータイプの`ポイント'が要求されました

それらの行は次のとおりです。

Point *から非スカラータイプのPointへの変換は何ですか？新しいポイントを作成して、ここのリストにプッシュしようとしています。

各ノードに単一の文字を保持する二重リンクリストを実装するプログラムを c++ で作成しています。私は追加機能を介して文字を挿入しています:

この関数は次のように実装されます。

ただし、おそらく C++ の文字の処理方法に問題があると思います。リストを印刷しようとすると、リストに追加した文字を印刷することができません。これは私が印刷に使用しているものです：

印刷するだけでボロボロになります。リストに追加したことのない文字を出力します - メモリのどこかからの文字だけです。これを引き起こしている可能性があるのは何ですか？