- TAOCP/InformationStructures
= 2.2. Linear Lists =
== 2.2.2. Sequential Allocation ==
Sequential Allocation은 stack을 다루는데 편리하다.
''새 원소 넣기(To place a new element Y on top)
T ← T + 1; X[T] ← Y;
마지막 원소 빼기(setting Y equal to the top node and delete)
Y ← X[T]; T ← T - 1;''
''새 원소 넣기(inserting an element at the rear of the queue)
맨 앞 원소 빼기(removing the front node)
F ← F + 1; Y ← X[F]; if F = R, then set F ← R ← 0''
하지만 공간낭비가 무한할 수 있다.( F, R이 계속증가하기 때문이다.) 따라서 이런 문제(the problem of the queue overrunning memory)를 해결하려면, M개의 노드(X[1]...X[M])가 순환하도록 한다.
''if R = M then R ← 1, otherwise R ← R + 1; X[R] ← Y.
if F = M then F ← 1, otherwise F ← F + 1; Y ← X[F].''
가능한 공간에 리스트가 두 개 있다면 (고정된)bottom을 같이 쓸 수 있다. (p.246 그림 참고) 이런 경우 두 리스트가 메모리를 모두 써버릴 때까지 오버플로우는 생기지 않는다. 이런 형태는 매우 자주 쓰인다.
하지만 리스트가 더 많으면 bottom이 움직일 수 있어야 한다.(we must allow the "bottom" elements of the lists to change therir positions.) MIX에서 I번째 한 WORD를 rA에 가져오는 코드는 다음과 같다.
STA *+1(0:2) ;그 주소를 다음 메모리(LDA *,1이 있는)에 넣는다.
a) ''''위로 한칸씩 밀기(moving things up)'''
i＜k≤n인 k 가운데 TOP[k] < BASE[k+1]인 가장 '''작은''' k를 찾는다. 찾으면 TOP[k] ≥ L＞BASE[i+1]인 L에 대해서 다음을 한다.
CONTENTS(L+1) ← CONTENTS(L) (L은 큰 것부터 민다. 해당사항 없으면 아무것도 하지 않는다.)
그리고 마지막으로 i보다 크고 k보다 크지 않은 모든 BASE와 TOP을 하나씩 위로 민다.
Found 1 matching page out of 7540 total pages
You can also click here to search title.
