taocp, 2.2.2 연속 할당을 tacop 작업하는 동안 나는 몇 가지 문제로 실행했습니다

Question

순차적으로 할당 질문 페이지의 주제는 247

에서 재 포장 메모리 부분은 n은 공통 영역을 공유 스택이 위치 L0 < L이 있습니다 < LX는 처음 우리 BASE를 [J] = TOP [J] = L0 1 < = J < = N

위한 삽입 방법이나, 난 스택에 대하여 으로 요소 삭제하는 동안 오버 플로우가 발생할 때, 목표는 메모리를 재 포장하십시오. (아직 채워지지 않은 테이블 인 에서 일부를 취하여 스택 i의 공간을 확보).

a). i가 < k < n이고 TOP [k] < BASE [k + 1]가있는 경우 가장 작은 k를 찾습니다 (k 이있는 경우). TOP [k]> = L> BASE [i + 1] 마지막으로 에 대한 CONTENTS (L + 1) -> CONTENTS (L) 설정 BASE [j] -> BASE [j ] + 1, TOP [J] -> TOP [J] + 1, 난 < J 여기 < K

내 질문 있어요 :

는 어떻게 아직 작성 될 수 없습니다 스택을 찾을 수 있습니까? 스택 k? 왜 가장 작은 k를 선택 했습니까?

가 스택 k 처음에 < ==>TOP[k] < BASE[k+1]

루프 전체되지 않습니다 :

Answer 1

아직 작성되지 스택을 찾으려면이 사용되는 기본 개념은 사실이다 알고리즘의 step은 i+1에서 n까지 k을 실행하여이 조건을 만족하는 첫 번째 k을 찾습니다.

처음에는 모든 공간이 n 번째로 붙어 있으며, BASE[n] = TOP[n] = L0과 BASE[n+1]=LInfty을 설정하여 스택합니다. 그래서 모든 "상위"스택이 채워지지 않으면, 우리는 그러한 k을 발견 할 것입니다. (? 작은 등 k가 선택하는 이유) 더 쉽게 대답한다

두 번째 질문 : 247 페이지에이 알고리즘은 한 재 포장의 방법과 그에서 간단한 하나입니다. Knuth가 알고리즘 텍스트 바로 위 단락에서 언급했듯이 :

재 포장을 수행하는 몇 가지 방법은 스스로 제안합니다. ... 가장 간단한 메소드 인 을 시작한 다음 몇 가지 대안을 고려합니다.

나이트 (Knuth)는 이전의 재 포장을 고려한 재 포장 접근법을 설명하고 프로세스를 어느 정도 적응시킵니다.