6

マイクロソフトのインタビューの質問.

Cを使用してファイルの最後のn行を読み取る（正確に）

これを達成する方法はたくさんありますが、そのうちのいくつかは次のとおりです。

-> 最も簡単なのは、最初のパスでファイル内の行数を数え、2 番目のパスで最後の n 行を表示することです。

-> または、すべての行に対して二重にリンクされたリストを維持し、最後の n 番目のノードまでリンクリストを逆方向にたどって最後の n 行を表示することもできます。

-> ある種の tail -n fname を実装します

-> さらに最適化するために、長さが n の double ポインターを使用し、すべての行をファイルの最後に到達するまでラウンド ロビン方式で動的に格納することができます。

たとえば、ファイルに 10 行あり、最後の 3 行を読みたい場合などです。次に、バッファーの配列を buf[3][] として作成し、実行時に最後の行に到達するまで循環的にバッファーの malloc と解放を続け、カウンターを保持して配列の現在のインデックスを知ることができます。

上記のアプローチのいずれかが正しい答えまたはそのような種類の質問に対する他の一般的なアプローチ/方法を得るのに役立つ場合は、誰かがより最適化されたソリューションを手伝ってくれるか、少なくとも私を案内してくれますか?

4

3 に答える 3

9

キューを使用して、このキューに表示された最後の n 行を保存できます。eof が表示されたら、キューを印刷します。

もう 1 つの方法は、ファイルの末尾から先頭に向かって 1024 バイトのブロックを読み取ることです。文字を見つけたら停止n \nし、最後のn行を出力します。

于 2013-03-05T05:07:30.013 に答える
4

最初にファイルの先頭を指す 2 つのファイル ポインターを使用できます。

「\n」文字が見つかるまで最初のポインターをインクリメントし続けます。「\n」が見つかると、ファイル ポインターのインスタンスも格納されます。

(n+1) 番目の '\n' を見つけたら、以前に保存したファイル ポインターの最初に格納されたインスタンスを 2 番目のファイル ポインターに割り当てます。EOF まで同じことを続けます。

したがって、最初のファイル ポインタが EOF にある場合、2 番目のファイル ポインタは n '\n' バックになります。次に、2 番目のファイル ポインタから EOF までのすべての文字を出力します。

したがって、これはファイルの最後の n 行を 1 回のパスで出力できるソリューションです。

于 2013-03-05T06:03:34.027 に答える
1

メモリ マップド ファイルを使用して、ファイルを逆方向​​からスキャンしてみてはどうでしょうか。これにより、行がたまたまバッファ スペースよりも長くなった場合に、毎回バッファ ウィンドウを更新するという大変な作業が不要になります。次に、 が見つかったら、\nそのポジションをスタックにプッシュします。これはO(L)、L が出力する文字数である場合に機能します。だから、それよりも本当に良いものはありませんか？

于 2013-03-05T14:47:01.197 に答える