2.2. Linear Lists ¶
2.2.2. Sequential Allocation ¶
ํ ๋
ธ๋์ ๋ค์ด์๋ WORD์ ์๊ฐ c๊ฐ๋ผ๋ฉด ๋ค์๊ณผ ๊ฐ์ด ์ธ ์ ์๋ค.
์์ L0๋ฅผ base address๋ผ๊ณ ํ๋ค๋ฉด ๋ค์๊ณผ ๊ฐ์ด๋ ์ธ ์ ์๋ค.
Sequential Allocation์ stack์ ๋ค๋ฃจ๋๋ฐ ํธ๋ฆฌํ๋ค.
์ค๋ฒํ๋ก์ฐ์ ์ธ๋ํ๋ก์ฐ๊ฐ ์ผ์ด๋ฌ์ ๋ ์ด๋ป๊ฒ ํด์ผ ํ ๊น? ์ธ๋ํ๋ก์ฐ๋ ํ๋์ ์๋ฏธ์๋ ์กฐ๊ฑด - ์๋ฌ ์ํฉ์ด ์๋๋ผ - ์ด๋ค. ํ์ง๋ง ์ค๋ฒํ๋ก์ฐ๋ ๋ ๋ค์ด๊ฐ ๊ณต๊ฐ์ด ์๋๋ฐ ๋ค์ด๊ฐ ์ ๋ณด๊ฐ ๋จ์์์ด์ ์๋ฌ์ด๋ค. ๋ฐ๋ผ์ ์ค๋ฒํ๋ก์ฐ๊ฐ ์๊ธฐ๋ฉด ์ฉ๋ํ๊ณ๋ฅผ ๋์ด์์ ํ๋ก๊ทธ๋จ์ด ์ข ๋ฃํ๋ค.
์์ L0๋ฅผ base address๋ผ๊ณ ํ๋ค๋ฉด ๋ค์๊ณผ ๊ฐ์ด๋ ์ธ ์ ์๋ค.
Sequential Allocation์ stack์ ๋ค๋ฃจ๋๋ฐ ํธ๋ฆฌํ๋ค.
''์ ์์ ๋ฃ๊ธฐ(To place a new element Y on top)
queue๋ deque๋ฅผ ๋ํ๋ด๋ ๊ฒ์ ์ข๋ ๋ณต์กํ๋ค.T โ T + 1; XT โ Y;
๋ง์ง๋ง ์์ ๋นผ๊ธฐ(setting Y equal to the top node and delete)''์ ์์ ๋ฃ๊ธฐ(inserting an element at the rear of the queue)
ํ์ง๋ง ๊ณต๊ฐ๋ญ๋น๊ฐ ๋ฌดํํ ์ ์๋ค.( F, R์ด ๊ณ์์ฆ๊ฐํ๊ธฐ ๋๋ฌธ์ด๋ค.) ๋ฐ๋ผ์ ์ด๋ฐ ๋ฌธ์ (the problem of the queue overrunning memory)๋ฅผ ํด๊ฒฐํ๋ ค๋ฉด, M๊ฐ์ ๋
ธ๋(X1...XM)๊ฐ ์ํํ๋๋ก ํ๋ค.R โ R + 1; XR โ Y;
๋งจ ์ ์์ ๋นผ๊ธฐ(removing the front node)''if R = M then R โ 1, otherwise R โ R + 1; XR โ Y.
if F = M then F โ 1, otherwise F โ F + 1; Y โ XF.''
์ฌํ๊น์ง๋ ๋ฌธ์ (๋ ๋ฃ์ ๊ณต๊ฐ์ด ์๊ฑฐ๋, ๋ ์ง์ธ ๊ฒ์ด ์๋ ๊ฒฝ์ฐ)๊ฐ ์๋ค๊ณ ๊ฐ์ ํ๋ค. ์ด ๋ฌธ์ ๊น์ง ๊ณ ๋ คํ ๊ณผ์ ์ด ๋ค์๊ณผ ๊ฐ๋ค.if F = M then F โ 1, otherwise F โ F + 1; Y โ XF.''
p.245 (2a),(3a),(6a),(7a)
(6a),(7a)์์๋ ์ด๊ธฐ ์กฐ๊ฑด์ด F = R = 1์ด๋ค. ๋ง์ฝ F = 0์ด๋ผ๋ฉด ์ค๋ฒํ๋ก์ฐ๊ฐ ์๊ธฐ์ง ์๊ธฐ ๋๋ฌธ์ด๋ค.์ค๋ฒํ๋ก์ฐ์ ์ธ๋ํ๋ก์ฐ๊ฐ ์ผ์ด๋ฌ์ ๋ ์ด๋ป๊ฒ ํด์ผ ํ ๊น? ์ธ๋ํ๋ก์ฐ๋ ํ๋์ ์๋ฏธ์๋ ์กฐ๊ฑด - ์๋ฌ ์ํฉ์ด ์๋๋ผ - ์ด๋ค. ํ์ง๋ง ์ค๋ฒํ๋ก์ฐ๋ ๋ ๋ค์ด๊ฐ ๊ณต๊ฐ์ด ์๋๋ฐ ๋ค์ด๊ฐ ์ ๋ณด๊ฐ ๋จ์์์ด์ ์๋ฌ์ด๋ค. ๋ฐ๋ผ์ ์ค๋ฒํ๋ก์ฐ๊ฐ ์๊ธฐ๋ฉด ์ฉ๋ํ๊ณ๋ฅผ ๋์ด์์ ํ๋ก๊ทธ๋จ์ด ์ข ๋ฃํ๋ค.
๊ฐ๋ฅํ ๊ณต๊ฐ์ ๋ฆฌ์คํธ๊ฐ ๋ ๊ฐ ์๋ค๋ฉด (๊ณ ์ ๋)bottom์ ๊ฐ์ด ์ธ ์ ์๋ค. (p.246 ๊ทธ๋ฆผ ์ฐธ๊ณ ) ์ด๋ฐ ๊ฒฝ์ฐ ๋ ๋ฆฌ์คํธ๊ฐ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ๋ชจ๋ ์จ๋ฒ๋ฆด ๋๊น์ง ์ค๋ฒํ๋ก์ฐ๋ ์๊ธฐ์ง ์๋๋ค. ์ด๋ฐ ํํ๋ ๋งค์ฐ ์์ฃผ ์ฐ์ธ๋ค.
ํ์ง๋ง ๋ฆฌ์คํธ๊ฐ ๋ ๋ง์ผ๋ฉด bottom์ด ์์ง์ผ ์ ์์ด์ผ ํ๋ค.(we must allow the "bottom" elements of the lists to change therir positions.) MIX์์ I๋ฒ์งธ ํ WORD๋ฅผ rA์ ๊ฐ์ ธ์ค๋ ์ฝ๋๋ ๋ค์๊ณผ ๊ฐ๋ค.
(p.248์ (12)์ ๊ทธ๋ฆผ 4๋ ์์ ์ด๋ค. ๊ทผ๋ฐ ์ด๋ ต๋ค. 3๋ฒ์ ํด๋ณด์์ผ๋ ์ ๋๋ก ๋์ค์ง ์์๋ค.)
''LD1 I ;I๋ฅผ rI2์ ๋ฃ๋๋ค.
LDA BASE(0:2) ;BASE์ ์ ์ฅ๋ L0์ฃผ์๋ฅผ rA์ ๋ฃ๋๋ค.
STA *+1(0:2) ;๊ทธ ์ฃผ์๋ฅผ ๋ค์ ๋ฉ๋ชจ๋ฆฌ(LDA *,1์ด ์๋)์ ๋ฃ๋๋ค.
LDA *,1 ;์ฌ๊ธฐ์ I๋ฅผ ๋ํ ์ฃผ์๋ก ๊ฐ์ ๊ทธ ๊ฐ์ rA์ ๋ฃ๋๋ค.''
n๊ฐ์ ์คํ์ด ์๋ ๊ฒฝ์ฐ i๋ฒ์งธ(1โคiโคn) ์คํ์ ์์๋ฅผ ๋ฃ๊ณ ๋นผ๋ ๊ณผ์ ์ ๋ค์๊ณผ ๊ฐ์ด ์ ์ ์ ์๋ค.LDA BASE(0:2) ;BASE์ ์ ์ฅ๋ L0์ฃผ์๋ฅผ rA์ ๋ฃ๋๋ค.
STA *+1(0:2) ;๊ทธ ์ฃผ์๋ฅผ ๋ค์ ๋ฉ๋ชจ๋ฆฌ(LDA *,1์ด ์๋)์ ๋ฃ๋๋ค.
LDA *,1 ;์ฌ๊ธฐ์ I๋ฅผ ๋ํ ์ฃผ์๋ก ๊ฐ์ ๊ทธ ๊ฐ์ rA์ ๋ฃ๋๋ค.''
p.247 (9) (10) ์ฐธ๊ณ
์ฌ๊ธฐ์ i๋ฒ์งธ ์คํ์์ ์ค๋ฒํ๋ก์ฐ๊ฐ ์๊ธฐ๋ฉด ๋ฉ๋ชจ๋ฆฌ ์ฌ๋ฐฐ์น(repack memory)๋ฅผ ํ ์ ์๋ค. ๋ช๊ฐ์ง ๋ฐฉ๋ฒ์ด ์๋๋ฐ ์ง๊ธ๋ถํฐ ์์ธํ ์์๋ณด์.''์ด๊ธฐ ์กฐ๊ฑด : p.247 (11) ์ฐธ๊ณ
i๋ฒ์งธ ์คํ์์ ์ค๋ฒํ๋ก์ฐ๊ฐ ์๊ฒผ์ ๋''
a) ์๋ก ํ์นธ์ฉ ๋ฐ๊ธฐ(moving things up)'''
i๏ผkโคn์ธ k ๊ฐ์ด๋ฐ TOPk < BASEk+1์ธ ๊ฐ์ฅ ์์ k๋ฅผ ์ฐพ๋๋ค. ์ฐพ์ผ๋ฉด TOPk โฅ L๏ผBASEi+1์ธ L์ ๋ํด์ ๋ค์์ ํ๋ค.
b) ์๋๋ก ํ์นธ์ฉ ๋ฐ๊ธฐ(moving things down)''' a)์ ํด๋นํ๋ k๊ฐ ์์ ๊ฒฝ์ฐ
iโคk๏ผn์ธ k ๊ฐ์ด๋ฐ TOPk < BASEk+1์ธ ๊ฐ์ฅ ํฐ k๋ฅผ ์ฐพ๋๋ค. ์ฐพ์ผ๋ฉด TOPi โฅ L๏ผBASEk+1์ธ L์ ๋ํด์ ๋ค์์ ํ๋ค.
c) ์ง์ง ์ค๋ฒํ๋ก์ฐ
๊ณต๊ฐ์ ์ฐพ์ ์ ์๋ค. ํฌ๊ธฐํด์ผ ํ๋ค.
''i๋ฒ์งธ ์คํ์์ ์ค๋ฒํ๋ก์ฐ๊ฐ ์๊ฒผ์ ๋''
a) ์๋ก ํ์นธ์ฉ ๋ฐ๊ธฐ(moving things up)'''
i๏ผkโคn์ธ k ๊ฐ์ด๋ฐ TOPk < BASEk+1์ธ ๊ฐ์ฅ ์์ k๋ฅผ ์ฐพ๋๋ค. ์ฐพ์ผ๋ฉด TOPk โฅ L๏ผBASEi+1์ธ L์ ๋ํด์ ๋ค์์ ํ๋ค.
CONTENTS(L+1) โ CONTENTS(L) (L์ ํฐ ๊ฒ๋ถํฐ ๋ฏผ๋ค. ํด๋น์ฌํญ ์์ผ๋ฉด ์๋ฌด๊ฒ๋ ํ์ง ์๋๋ค.)
๊ทธ๋ฆฌ๊ณ ๋ง์ง๋ง์ผ๋ก i๋ณด๋ค ํฌ๊ณ k๋ณด๋ค ํฌ์ง ์์ ๋ชจ๋ BASE์ TOP์ ํ๋์ฉ ์๋ก ๋ฏผ๋ค.b) ์๋๋ก ํ์นธ์ฉ ๋ฐ๊ธฐ(moving things down)''' a)์ ํด๋นํ๋ k๊ฐ ์์ ๊ฒฝ์ฐ
iโคk๏ผn์ธ k ๊ฐ์ด๋ฐ TOPk < BASEk+1์ธ ๊ฐ์ฅ ํฐ k๋ฅผ ์ฐพ๋๋ค. ์ฐพ์ผ๋ฉด TOPi โฅ L๏ผBASEk+1์ธ L์ ๋ํด์ ๋ค์์ ํ๋ค.
CONTENTS(L-1) โ CONTENTS(L) (L์ ์์ ๊ฒ๋ถํฐ ๋ฏผ๋ค. ํด๋น์ฌํญ ์์ผ๋ฉด ์๋ฌด๊ฒ๋ ํ์ง ์๋๋ค.)
๊ทธ๋ฆฌ๊ณ ๋ง์ง๋ง์ผ๋ก k๋ณด๋ค ํฌ๊ณ i๋ณด๋ค ํฌ์ง ์์ ๋ชจ๋ BASE์ TOP์ ํ๋์ฉ ์๋๋ก ๋ฏผ๋ค.c) ์ง์ง ์ค๋ฒํ๋ก์ฐ
๊ณต๊ฐ์ ์ฐพ์ ์ ์๋ค. ํฌ๊ธฐํด์ผ ํ๋ค.
(p.248์ (12)์ ๊ทธ๋ฆผ 4๋ ์์ ์ด๋ค. ๊ทผ๋ฐ ์ด๋ ต๋ค. 3๋ฒ์ ํด๋ณด์์ผ๋ ์ ๋๋ก ๋์ค์ง ์์๋ค.)
์ด๊ธฐ๊ฐ์ผ๋ก ํจ์จ์ ์ธ ์์ ์์น๋ฅผ ์ฃผ๋ ๊ฒ์ด ๊ฐ๋ฅํ๋ค. (p.248 (13), ํ๊ท ์ ์ผ๋ก BASE๋ฅผ ๋ถํฌ์ํจ๋ค.)
ํ ๋ฒ ๋ฉ๋ชจ๋ฆฌ ์ฌ๋ฐฐ์น๋ฅผ ํ ๋๋ง๋ค ๊ณต๊ฐ์ ์ ๋นํ ๋ง๋ จํ๋ ๋ฐฉ๋ฒ๋ ๊ฐ๋ฅํ๋ค.( ๊ทธ๋ฌ๋ ์ดํดํ์ง ๋ชปํ๋ค.p.250์ ์ค๊ฐ์ ๋ณด๋ฉด ์ ์๊ณ ๋ฆฌ์ฆ(Algorithm G๋ R)๊ณผ ๋น์ทํ ๋์ ๋ฉ๋ชจ๋ฆฌ ํ ๋น ์๊ณ ๋ฆฌ์ฆ์ ์ํ์ ๋ถ์์ ๋งค์ฐ ์ด๋ ต๋ค๊ณ ๋์์๋ค. )
