c - リンクされたリスト内の破損したポインターを解決するにはどうすればよいですか?

Question

リンク リストのポインタ (リンク) フィールドが壊れていることがわかった場合、この問題を解決するにはどうすればよいですか?

面接でこんな質問をされました。いいえ、それを解決することは不可能です。インタビュアーはその可能性を語った。方法はありますか？

Answer 1

それが双方向にリンクされたリストであると仮定します：

破損したのが「次の」ポインタである場合は、末尾から始めて「前の」ポインタを使用して、トラバースされた最後の要素への参照を維持しながら、リストを先頭に向かってトラバースできます。不正なポインタを持つ要素を見つけたら、その要素の「次の」ポインタがトラバースされた最後の要素を指すようにする必要があります。

二重リンク リストで「前の」リンクが破損している場合は、プロセスを逆にすることができます。先頭から開始し、不正な「前の」ポインタが見つかるまでトラバースし、最後にトラバースされた要素への参照を使用して修正します。

Answer 2

二重循環リンクリストでは、ポインタ（前または次のポインタ）のいずれかが破損している場合、破損したポインタを解決できます。

次のポインタが適切でない場合は、リストを逆方向にトラバースしてから修正できます。または、前のポインタが適切でない場合は、リストを順方向にトラバースして修正できます。

次に、リスト内の破損したリンク（ポインタ）を特定する方法を考える必要があります。各ノードに個別に動的メモリ（mallocまたは）を割り当てるために使用します。小さな小さなメモリを頻繁にcalloc呼び出すmallocと、システムのパフォーマンスに影響を与える可能性があります。callocこれではなく、初期段階で大量のヒープメモリを割り当ててから、ノードの作成ごとに独自のメモリ割り当て機能を実装できます。また、これはリストノードの作成にのみ使用して、リストの破損したリンクを識別します。

これにより、システムのパフォーマンスが向上し、リストに割り当てられた初期メモリの制限を確認することで、ノードのリンクが破損しているかどうかを識別するのに役立ちます。

ノードへのポインタを取得したら、そのノードのデータにアクセスする前に、まず以下のチェックを実行する必要があります。

check_limit(node);
check_limit(node->next);
check_limit(node->previous);

また、node->previousがに等しいかどうかを確認できcurrent_nodeます。

node->nextこの後、間違ったアドレスを指している可能性がありますが、初期メモリ制限内です。この場合、node->next->previous（間違ったアドレスを指していても、初期メモリ制限内であっても、クラッシュにつながることはありませんnext）、それが等しいかどうかを確認nodeできます。

また、未使用の初期メモリスペースはNULL常に（を使用してmemset）設定する必要があります。

これらの方法で、リスト内の破損したポインターの99％を見つけることができます。

Answer 3

埋め込みジョブの開発では、前方リンク キューをよく使用します。ヘッドポインターと同様にカウントを保持します。キューには、[count] 個のリンクをラウンドして実行する check() メソッドがあり、結果のポインターがヘッドと同じでない場合は重大なエラー ハンドラーを呼び出します。これは絶対確実というわけではありませんが、ダブルプッシュやその他の一般的なキュー エラーをキャッチするには十分に機能します。

注: マルチスレッド アプリでは、安全にチェックするためにキューをロックする必要があります。

Answer 4

たぶん、あなたはそれを取り除くべきですか？実際、リストの要素を他の要素で補間できない場合、一般的なケースでは不可能です。