C 파일의 마지막 n 줄을 읽는 방법

Question

Microsoft 인터뷰 질문. C를 사용하여 파일의

읽기 마지막 n 라인 (정확하게)

그럼이를 달성하기 위해 이렇게 많은 방법이있을 수 있습니다, 그 중 몇 가지가있을 수 :

-의> 간단한 첫 번째 패스에서는 모두 파일의 줄 수를 계산하고 두 번째 패스에서는 마지막 n 줄을 표시합니다.

-> 또는 모든 행에 대해 이중 링크 된 목록을 유지하고 마지막 n 행까지 n 번째 마지막 노드까지 연결된 목록을 역순으로 탐색하여 표시 할 수 있습니다.

-> 정렬 꼬리 -n의 FNAME의 무언가를 구현

-> 우리는 N으로 길이와 우리가 끝에 도달 할 때까지 라운드 로빈 방식으로 동적으로 저장된 모든 라인 더블 포인터를 가질 수 있습니다 더를 최적화하기 위해, 파일의.

예를 들어 파일에 10 개의 행이 있고 마지막 3 개의 행을 읽으려는 경우. 우리는 버퍼의 배열을 buf [3] []로 만들 수 있고 실행시에 마지막 줄에 도달 할 때까지 mallocing을 계속하고 순환 방식으로 버퍼를 해제하고 배열의 현재 인덱스를 알 수있는 카운터를 유지할 수 있습니다.

위의 방법 중 하나라도 정답이나 이와 유사한 질문에 대한 다른 일반적인 접근 방식을 얻는 데 도움이 될 수있는 사람이라면 누구나 나를 좀 더 최적화 된 솔루션 또는 atleast 가이드로 도울 수 있습니까?

Answer 1

대기열을 사용하여이 대기열에 표시된 마지막 n 행을 저장할 수 있습니다. eof가 대기열을 인쇄하는 것을 볼 때.

또 다른 방법은 파일 끝에서 시작 부분으로 1024 바이트 블록을 읽는 것입니다. n\n자를 찾으면 마지막으로 n 줄을 인쇄하십시오.

Answer 2

처음에는 파일의 시작 부분을 가리키는 두 개의 파일 포인터가있을 수 있습니다.

'\ n'문자가 '\ n'을 찾으면 파일 포인터의 인스턴스도 저장 될 때까지 첫 번째 포인터를 계속 증가시킵니다.

(n + 1) 번째 '\ n'을 찾으면 이전에 저장 한 파일 포인터의 첫 번째 인스턴스를 두 번째 파일 포인터로 할당합니다. EOF까지 동일하게 수행하십시오.

첫 번째 파일 포인터가 EOF에있을 때 두 번째 파일은 n '\ n'에 있습니다. 두 번째 파일 포인터의 모든 문자를 EOF로 인쇄하십시오.

이렇게하면 단일 패스로 파일의 마지막 n 줄을 인쇄 할 수 있습니다.

Answer 3

메모리 맵 파일을 사용하고 파일을 역방향으로 스캔하는 방법은 어떻습니까? 이렇게하면 라인이 버퍼 공간보다 길어질 때마다 매번 버퍼 윈도우를 업데이트하는 것이 어렵습니다. 그런 다음 \n을 찾았 으면 위치를 스택으로 밀어 넣습니다. 이것은 O(L)에서 작동합니다. 여기서 L은 출력 할 문자 수입니다. 그래서 그보다 더 좋은 것은 없습니다.