제 1 장 기본개념

◁ 학습 내용 ▷

◦ 자료구조의 개념

◦ 자료구조의 영역

◦ 알고리즘

◦ 자료 추상화

◦ SPARKS의 구성

◦ 순환(recursion)

◦ 성능분석

우리에게 주어지는 사회 제반 현상의 문제를 해결하기 위한 도구로서의 컴퓨터를 자료처리 측면에서 볼 때 다음의 요소들과 연관지어 설명할 수 있다.

∙ 자    료 : 현실 세계로부터 단순한 관찰이나 측정을 통해 수집된 사실이나 값

∙ 정    보 : 자료가 프로그램에 의해 처리된 원하는 결과

∙ 자료구조 : 자료를 기억 공간 상에 표현 및 저장하기 위한 논리적 구조

∙ 알고리즘 : 자료를 이용하여 정보를 구하기 위한 문제 해결 논리기술

∙ 프로그램 : 알고리즘을 프로그래밍 언어를 이용하여 실행논리로 구현한 것

* 자료 구조의 영역

廣義 자료 구조

狹義 자료 구조

기본 자료	선  형 : 레코드, 배열	화일 구조

스택, 큐

연결리스트	데이터베이스 구조

비선형 : 트리, 그래프

∙ 기본 자료 : 수치 자료(정수형, 실수형), 문자 자료, 논리 자료, 포인터 자료

∙ 화일 구조 : 순차 화일 구조, 직접 화일 구조, 인덱스된 순차 화일 구조

∙ 데이터베이스 구조 : 계층 구조, 망 구조, 관계 구조, 객체지향 구조

* 교재의 구성

기본 개념

선형   구조 :	배열

스택, 큐

연결리스트

비선형 구조 :	트리

그래프

자료 구조 응용 :	탐색, 정렬

* 선형(線形) 구조

배      열 :

스      택 :

큐 :

연결리스트 :

∙ 배 열 : 임의의 위치에 삽입, 삭제

∙ 스 택 : top이라고 하는 한쪽 끝을 통해 삽입, 삭제

∙ 큐 : 한쪽 끝에서 삽입, 다른 쪽 끝에서 삭제

∙ 연결 리스트 : 인접하지 않은 기억 공간의 자료를 포인터에 의해 연결된 개념으로 활용

스택과 큐는 배열 또는 연결 리스트를 활용하여 나타낼 수 있다.

* 비선형(非線形) 구조

트리	그래프

∙ 트리 : 노드들 간의 계층 구조(1:n)

∙ 그래프 : 노드들 간의 다중 구조(n:m)

*  알고리즘의 특성

∙ 입  력 : 외부 제공 자료가 있을 수 있음.

∙ 출  력 : 한 가지 이상의 결과 생성

∙ 명확성 : 각 명령은 명확

∙ 유한성 : 한정된 단계 실행 후 종료

∙ 유효성 : 컴퓨터 처리 가능

자료 표현은 배열 및 연결 리스트를 이용하여 나타낼 수 있다.

∙ 알고리즘 : 문제 해결을 위한 논리 구성

*  알고리즘 기술 방법

∙ 알고리즘 기술 언어 사용

∙ 자연어에 의한 표현

- 한글 또는 영문

- 슈도 코드(pseudo code)

∙ 도형에 의한 표현

- 흐름도(flow chart)

- 박스(box) 다이어그램

∙ 프로그램 : 컴퓨터가 실행할 수 있는 프로그래밍 언어에 의한 실행 논리 구현

본 교재에서는 SPARKS라고 하는 알고리즘 기술 언어를 사용한다.

* 추상화 구조에 의한 자료 구조 정의

d = ( P, F, A)

P = { natno, boolean }

F = { ZERO, SUCC, ADD 등 }

A = { NATNO의 ⑦행부터 ⑪행 }

∙ 자료 추상화의 개념 : 하나의 자료형(data type)과 관련된 연산들 그리고 그 표현 형태를 모아 두는 기법

정의 구역의 집합 P

지정된 정의 구역 d ∈ P

함수 집합 F

공리 집합 A

*여기에서 NATNO 또는 natno 는 자연수(natural number)를 의미하는 약자임.

* 프로시저 간의 자료 전달

∙ call by value

∙ call by reference

∙ call by name

* 입출력문

read(argument list)

print(argument list)

∙

* 지정문

p ← X : q ← 0

LINK(p) ← r

a ← a + 1

* procedure문

procedure NAME(parameter list)

call NAME(parameter list)

return(expr)

추상 자료형(ADT) : 객체의 명세와 그 연산의 명세가 그 객체 표현과 연산의 구현으로부터 분리되는 자료형을 의미

추상 자료형은 프로그램의 자료 구조에 기반을 둔 기준들을 이용해서 프로그램을 모듈들로 구성하는 프로그래밍 언어의 기능이다. 모듈의 표시는 허용되는 자료의 값들과 연산 효과를 포함해서 그 자료형 (data type)을 사용하는 데 필요한 모든 정보를 제공해 주어야 한다. 그러나 자료의 표현과 연산을 실행하는 알고리즘과 같은 자세한 것은 모듈 안에 숨겨져 있다고 볼 수 있으며, 자료형의 구현과 모듈의 표시는 독립적이라는 것이 추상 자료형의 중심적 사상이다.

* SPARKS의 특성

∙ 지정문

∙ 조건문(if, while, repeat)

∙ case문

∙ 반복문(loop ~ forever, for)

∙ procedure문

∙ 입출력문

* 순환(recursion)

직접 순환 : A → A´

간접 순환 : A → B → A

∙ 직접 순환 : 프로시저가 수행을 완료하기 전에 자기 자신을 호출하는 것

procedure PERM(A, k, n)

if k = n then [print(A) : return]

B ← A

for i ← k to n do

call INTERCHANCE(A, k, i)

call PERM(A, k+1, n)

A ← B

end

end PERM

∙ 간접 순환 : 자신을 호출하는 프로시저를 다시 호출하는 것

if k = n then [print(A) : return]

B ← A

for i ← k to n do

call INTERCHANCE(A, k, i)

call PERM(A, k+1, n)

A ← B

end

end PERM

if k = n then [print(A) : return]

B ← A

for i ← k to n do

call INTERCHANCE(A, k, i)

call PERM(A, k+1, n)

A ← B

end

end PERM

(예 1 - 1) 문자열 A(a, b, c)가 있을 때, 3개의 원소로 구성되는 순열을 순환적 구조의 알고리즘으로 나타냄.

∙ INTERCHANCE(A, k, i)는 문자열 A = (a, b, c)에서 k번째와 i번째 문자를 교환하는 서브루틴이다. 예를 들어, INTERCHANCE(A, 2, 3)이면, A(a, b, c)는 (a, c, b)가 된다.

∙

proc PERM(k)

if k = n then

[print(A) : return]

―

―

―

call PERM(k+1)

―

―

―

end

순열을 위한 순환적 구조를 다시 설명하면 다음과 같다.

이와 같이 호출문에 의해 순환이 되며, 조건문 if k = n 에서 k값이 호출될 때마다 같아질 때 print(A)를 하고, return문에 의해 해당 프로시저의 실행을 종료한다.

∙ 본교재 p.17 윗부분에 있는 알고리즘을 풀어서 설명한 것이 p.17의 아랬부분과 p.18까지이다.

이 알고리즘의 실행 결과는 (a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, b, a), (c, a, b) 순으로 출력이 이루어진다.

* 성능 분석

∙ 공간 복잡도

고정 공간 + 가변 공간

S(P) = c + Sp(I)

∙ 시간 복잡도

빈도수 계산

TP(n) = CaADD(n) + CaADD(n) ․․․

proc PERM(k)

if k = n then

[print(A) : return]

―

―

―

call PERM(k+1)

―

―

―

end

* big 'Ｏ'

모든 n, n≥n0에 대해 f(n)≤cg(n)인, 이 조건을 만족하는 두 양의 상수 c와 n0가 존재하기만 하면 f(n)≤Ｏ(g(n)) 이다.

f(n)은 입력 자료량 n에 대한 어떤 알고리즘의 계산이고, 알고리즘은 어떤 컴퓨터에서 수행할 때 같은 종류의 자료에 대해, 계산 시간 f(n)의 상한선 ｜g(n)｜을 Ｏ(g(n))이라 표기한다.

proc PERM(k)

if k = n then

[print(A) : return]

―

―

―

call PERM(k+1)

―

―

―

end

예) 어떤 m차 다항식 P(n) = amnm + am-1nm-1  + ․․․ + a1n + a0 이 주어졌다고 할 때 P(n) = O(nm) 이다.

<증명>

｜Pn｜ = ｜amnm + am-1nm-1  + ․․․ + a1n + a0｜

≤ ｜am｜nm + ｜am-1｜nm-1  + ․․․ + ｜a1｜n + ｜a0｜

≤  nm(｜am｜ + ｜am-1｜/n  + ․․․ + ｜a1｜/nm-1 + ｜a0｜/nm)

≤  nm(｜am｜ + ｜am-1｜ + ․․․ + ｜a1｜ + ｜a0｜) , n ≥1

2개의 상수 n0 와 c를

n0 = 1

c = ｜am｜ + ｜am-1｜ + ․․․ + ｜a1｜ + ｜a0｜

라 하면

｜P(n)｜ ≤ c ․ nm , n≥n0가 성립

따라서 P(n) = O(nm) 이 된다.

이를 차수 표시법이라고도 한다.

* O-notation

f(n) = 3n +2	O(n)

f(n) = 10n2 + 4n + 5	O(n2)

f(n) = 6 * 2n + n2	O(2n)

f(n) = 5x3 - 600x	O(x3)

f(n) = 100x - 1000	O(x)

어떤 문제의 알고리즘이 A(10n). B(½n2) 이라고 할 때, 자료수 n에 따른 연산 시간은 다음과 같다.

자료의 수 n < 20 인 경우 알고리즘 B가 유리하나 n > 20인 경우, 알고리즘 A가 유리하다. 대부분 자료량이 많은 경우 일반적으로 O(n) 이 O(n2) 보다 유리한 것이다.

n	알고리즘 A(10n)	알고리즘 B(½n2)
1 5 10 15 20 25 30	10 50 100 150 200 250 300	0.5 12.5 50 112.5 200 312.5 450

* big 'Ω'

모든 n, n≥n0 에 대해 f(n) ≥cg(n)을 만족하는 두 양의 상수 c와 n0 가 존재하기만 하면, f(n) ≥ Ω(g(n)) 이다.

Ω(g(n))은 O(g(n)) 에 대응되는 개념으로 g(n)은 f(n)의 하한값을 나타낸다.

* big 'θ'

모든 n, n≥n0 에 대해 상한값과 하한값을 모두 갖기만 하면 f(n) ≥ θ(g(n)) 이다. 이것은 어떤 알고리즘에 대한 최선의 경우와 최악 상태의 자료에 대한 계산 시간이 상수 배수차이로 비슷하다는 것을 의미한다.

* 연산 시간 표현

O(1) = 상수

O(log2n) = 로그형

O(n) = 선형

O(n2) = 평방형

O(n3) = 입방형

O(2n) = 지수형

O(1) < O(log2n) < O(n) < O(n2) < O(n3) < O(2n)

◁ 학습 내용 ▷

◦ 배열의 개요

◦ 순서리스트

◦ 배열의 표현

◦ 희소 행렬과 전치 행렬

제

* 배열의 추상화 자료 구조

structure ARRAY(value, index)

① declare CREATE(	) → array

②	RETRIEVE(value, index) → value

③	STORE(array, index, value) → array :

④ for all A ∈ array, i , j ∈ index, x ∈ value let

⑤	RETRIEVE(CREATE, i ) : : = error

⑥	RETRIEVE(STORE(A, i , x) : : =

⑦	if EQUAL(i , j ) then x

else RETRIEVE(A, j) end

end ARRAY

2 장 배열

* 순서리스트

∙ 리스트 길이(n) : 유한

∙ 리스트 읽음(left → right, right → left) : access

∙ i번째 원소 검색(1≤i≤n) : retrieve

∙ i번째에 새로운 값 저장 (1≤i≤n) : update

∙ i번째 새로운 원소 삽입(1≤i≤n) : insert

i→i+1

∙ i번째 원소 삭제(1≤i≤n) : delete

1+i→i

* 다항식의 덧셈

① C ← ZERO

② while not ISZERO(A) and not ISZERO(B) do

③	case

④	: EXP(A) < EXP(B)

⑤	C ← ATTACH(C, COEF(B, EXP(B)), EXP(B))

⑥	B ← REM(B, EXP(B))

⑦	: EXP(A) = EXP(B)

⑧	C ← ATTACH(C, COEF(A, EXP(A))

+ COEF(B, EXP(B)), EXP(A))

⑨	A ← REM(A, EXP(A)) : B ← REM(B, EXP(B))

⑩	: EXP(A) > EXP(B)

⑪	C ← ATTACH(C, COEF(A, EXP(A)), EXP(A))

⑫	A ← REM(A, EXP(A))

⑬	end

⑭ end

⑮	insert any remaining terms in A or B into C

∙알고리즘의 전제 사항

1) 지수는 유일하고 내림차순(decending)이다.

2) EXP(poly) → exp는 다항식의 최고 차수의 지수값을 돌려 주는 함수이다. 다항식

* 다항식의 배열 표현

<표현 1> 계수를 순서적으로 표현

A(x) = amxm + am-1xm-1  + ․․․ + a1x + a0

A = ( n, an, an-1, ․․․ , a1 , a0)

길이 : n + 2

<표현 2> 0이 아닌 계수만을 취한 표현

A´(x) = bm-1xem-1 + bm-2xem-2 + ․․․ + b0e0

A´= ( m, em-1, bm-1, em-2, bm-2, ․․․ ,e0, b0)

길이 : 2m + 1

A = 4x2 + 2x일 때, 처음 EXP(A)는 3, 다음의 EXP(A)는 1이고, 처음 COEF(A,           EXP(A))는 4이다.

∙위의 알고리즘은 두 다항식 A, B를 더하여, 새로운 다항식 C를 생성시키는 것이다.

두 다항식의 지수를 비교하여 덧셈을 하여, ②행 while 조건에서 둘 중의 하나가 ISZERO    가 되는 경우 ⑮행으로 제어가 넘어가 A나 B의 나머지 항을 C에 삽입한다.

* A = 5x10 + 2 일 경우

<표현 1>

<표현 2>

10	5	0	0	0	0	0	0	0	0	0	2

2	10	5	0	2

* 다항식 덧셈 알고리즘

procedure PADD(A, B, C)

// A(1 : 2m+1), B(1 : 2n+1), C(1 : 2(m+n)+1) //

① m ← A(1) : n ← B(1)

② p ← q ← r ← 2

③ while p ≤ 2m and q ≤ 2n do

④	case

⑤	: A(p) = B(q) : C(r+1) ← A(q+1)+B(q+1)

⑥	if  C(r+1) ≠ 0

then [C(r) ←A(p) : r ← r+2]

⑦	p ← q + 2 ; q ← q + 2

⑧	: A(p) < B(q) : C(r+1) ← B(q+1) ; C(r) ←B(q)

⑨	q ← q + 2 ; r ← r + 2

⑩	: A(p) > B(q) : C(r+1) ← A(q+1) ; C(r) ←A(q)

⑪	p ← p + 2 ; r ← r + 2

⑫	end

⑬ end

⑭ while p ≤ 2m do

⑮	C(r) ← A(p) ; C(r+1) ← A(p+1)

⑯	p ← p+2 ; r ← r+2

⑰ end

⑱ while q ≤ 2n do

⑲	C(r) ← B(q) ; C(r+1) ← B(q+1)

⑳	q ← q+2 ; r ← r+2

21  end

22  C(1) ← r/2 - 1

end PADD

본 교재에서는 <표현2>의 방식으로 배열을 표현함

이 알고리즘의 연산시간은 O(m+n)이다.

* 1차원 배열

A(n)    :

A(l : u) :

* A( l : u )

배열 원소 : A(1), A(2), ․․․, A(i), ․․․, A(u)

주     소 :  α,  α+1,        α+i-1,     α+u-1

원소 크기가 L일 때 : α + [i -1] ․ L

A(1)	A(2)	․․․	A(n)

A(l)	A(l+1)	․․․	A(u)

* 행 우선과 열 우선

A(3, 2)

열                (1, 1)	1행	(1, 1)

(1, 2)	(2, 1)   1열

행	(2, 1)	2행	(3, 1)

(2, 2)	(1, 2)

(3, 1)   3행	(2, 2)   2열

(3, 2)	(3, 2)

행 우선	열 우선

행 우선 순서 방식은 COBOL이나 PASCAL에서 채택하고 있는 배열에서의 저장 장소 할당 방법으로, 행(row)을 중심으로 변한 다음 열(column)을 변환시키는 방법이다.

즉, 배열 A(3, 4)일 경우에 A(1, 1), A(1, 2), A(1, 3), A(1, 4), A(2, 1), ․․․, A(3, 4) 이다.

열 우선 순서 방식은 FORTRAN에서 채택하고 있는 방법으로 열을 먼저, 다음 행을 변화시키는 방법이다.

즉, A(1, 1), A(2, 1), A(3, 1), A(1, 2) 의 순이다.

* 행 우선 주소 계산 공식

A(l1 : u1, l2 : u2), A(l1, l2) = α

A(l1 , 2) = α + 1

A(i , l2)  = α + (i - l1) ․ u2

A(l1 , j)  = α + [(i - l1) ․ u2 + (j - l2)] ․ L

* 열 우선 주소 계산 공식

A(l1 : u1, l2 : u2), A(l1, l2) = α

A(2 , l2) = α + 1

A(l1 , j)  = α + (j - l2) ․ u1

A(,i , j)  = α + [(j - l2) ․ u1 + (,i - l1)] ․ L

<3차원 배열> A(l1 : u1, l2 : u2, l3 : u3 )

∙ 행 우선

A(l1 , l2 , l3 ) 의 주소 α

A(i , l2 , l3)  = α + (i - l1) ․ u2․ u3

A(i , j , l3)  = α + (i - l1) ․ u2․ u3 + (j - l2)․ u3

A(i , j , k)  = α + (i - l1) ․ u2․ u3 + (j - l2)․ u3 + (k - l3)

원소의 크기가 L일 때

A(i , j , k)  = α + [(i - l1) ․ u2․ u3 + (j - l2)․ u3 + (k - l3)] ․ L

∙ 열 우선

A(l1 , l2 , l3 ) 의 주소 α

A(i , l2 , k)  = α + (k - l3) ․ u1․ u2

A(l1 , j , l3)  = α + (k - l3) ․ u1․ u2 + (j - l2)․ u1

A(i , j , k)  = α + (k - l3) ․ u1․ u2 + (j - l2)․ u1 + (i - l3)

원소의 크기가 L일 때

A(i , j , k)  = α + [(k - l1) ․ u1․ u2 + (j - l2)․ u2 + (i - l1)] ․ L

* 희소 행렬

행렬은 m개의 행(row)과 n개의 열(column)에 의해 구성되는 2차원 배열이다. 행렬 중 많은 원소의 값이 0으로 채워진 행렬을 희소 행렬(sparse matrix)이라 한다.

열   1    2    3    4    5    6

행

1	15    0    0   22    0  -15

2	0   11    3    0    0    0

3	0    0    0   -6    0    0

4	0    0    0    0    0    0

5	91    0    0    0    0    0

6	0    0   28    0    0    0

위 행렬을 (행의 위치, 열의 위치, 원소의 값) → (i, j, 값)의 형태로 기억시키면 다음의 배열

B	1 2 3
0 1 2 3 4 5 6 7 8	6 6 8 1 1 15 1 5 91 2 2 11 3 2 3 3 6 28 4 1 22 4 3 -6 6 1 -15

A와 같다. 배열 A의 행과 열의 위치를 바꾸어 재구성한 것이 배열 B이다.

A	1 2 3
0 1 2 3 4 5 6 7 8	6 6 8 1 1 15 1 4 22 1 6 -15 2 2 11 2 3 3 3 4 -6 5 1 91 6 3 28

* procedure TRANSPOSE(A, B)

① (m, n, t) ← (A(0, 1), A(0, 2), A(0, 3))

② (B(0, 1), B(0, 2), B(0, 3)) ← (n, m, t)

③ if t ≤ 0 then return

④ q ← 1

⑤ for col ← 1 to n do

⑥	for p ← 1 to t do

⑦	if A(p, 2) = col

⑧	then [B(q, 1), B(q, 2), B(q, 3)) ←

⑨	A(p, 1), A(p, 2), A(p, 3))

⑩	q ← q + 1]

⑪	end

⑫	end

end TRANSPOSE

배열 A와 B의 0번행은 행의 수, 열의 수, 값의 개수를 나타낸 것이다. 배열 A에서 배열 B로 바꾸는 알고리즘이 TRANSPOSED와 FAST-TRANSPOSE이다.

A	1 2 3
1 2 7 8	1 1 15 1 4 22 ․ ․ ․ ․ 5 1 91 ② 6 3 28

B	1 2 3
1 2 8	1 1 15 1 5 91 ․ ․ ․ ․ ․ 6 1 -15

①

이 알고리즘의 실행 과정을 소개하면 다음과 같다

⑫ for i ← 1 to t do

⑬	j ← A(i, 2)

⑭	(B(T(j), 1), B(T(j), 2), B(T(j), 3)) ←

⑮	(A(i, 2), A(i, 1), A(i, 3))

⑯	T(j) ← T(j) + 1

⑰ end

end FAST-TRANSPOSE

2	1	2	2	0	1

1	3	4	6	8	8

배열 A로부터 배열 B가 만들어지는 과정을 위에서부터 순서대로 값이 결정된다.

* procedure FAST-TRANSPOSE(A, B)

declare S(1 : n), T(1 : n)

① (m, n, t) ← (A(0, 1), A(0, 2), A(0, 3))

② (B(0, 1), B(0, 2), B(0, 3)) ← (n, m, t)

③ if t ≤ then return

④ for i ← 1 to n do S(i) ← 0 end

⑤ for i ← 1 to t do

⑥	S(A(i, 2)) ← S(A(i, 2)) + 1

⑦ end

⑧ T(i) ← 1

⑨ for i ← 2 to n do

⑩	T(i) ← T(i - 1) + S(i - 1)

⑪ end

이 알고리즘은 앞에서 제시된 TRANSPOSE보다 1차원 배열 2개를 더 사용함으로써 실행 시간을 빠르게 한 알고리즘이다.

연산 시간은 O(n + t) 로서 t가 mn일 경우 O(mn)이 된다.

이 알고리즘의 연산 시간은 O(nt)이며 t가 mn일 경우 O(n2m)이 된다.

배열 S                    는 배열 B의 행이 되는 것인, 배열 A의 열에서 1부터 6까지의 각각의 합계 배열

배열 T                     는 배열 B의 1부터 6까지의 시작위치이다.

알고리즘의 실행 과정을 간략히 소개하면 다음과 같다.

A	1 2 3
1 2 3	1 1 15 1 4 22 1 6 -15 ․ ․

A	1 2 3
1 6 8	1 1 15 ․ ․ ․ 4 1 22 6 1 -15

①

②

③

제 3 장 스택 & 큐

◁ 학습 내용 ▷

◦ 스택의 정의 및 삽입, 삭제 알고리즘 스택의 응용

◦ 스택의 응용

◦ 큐의 정의 및 삽입, 삭제알고리즘

◦ 원형 큐의 삽입, 삭제 알고리즘

◦ 수식의 표기법

◦ 다중 스택

스택은 top이라는 인덱스 위치를 통해 삽입 및 삭제가 이루어지며 초기

상태의 top은 0이다. 스택에서 top의 현재 위치에는 데이터가 저장된 상태를 나타낸다.

* 스택의 정의

․STACK(1 : n)

(1차원 배열 형태)

․한쪽 끝에서 삽입․삭제

․LIFO(Last In First Out)

후입 선출 알고리즘

⑤번의 경우 top의 위치를 변경하여 현재 유효한 값은 B이다. 이 때 스택 상의

C는 의미가 없는 값이다.

* 스택의 삽입

procedure ADD(item, STACK, n, top)

if top≥n then call STACK-FULL

top←top+1

STACK(top)←item

end ADD

경계조건 검사는 top=n인 경우이며, top<n인 경우 즉 스택에 데이터를 삽입할 공간이 있는 경우 top의 위치를 증가시킨 다음, 값(item)을 STACK이라는 배열의 top위치에 삽입한다.

* 스택의 삭제

procedure DELETE(item, STACK, top)

if top≤0 then call STACK-EMPTY

item←STACK(top)

top←top-1

end DELETE

경계조건 검사는 top=0인 경우이며, top≠0인 경우 즉 스택에 삭제할 데이터가 있는 경우, top위치에 있는 값을 item을 통해 삭제하고, top의 위치를 조정한다.

* 스택의 응용(서브루틴 호출)

스택의 첫 번째 q는 주 프로그램인 MAIN이 제어를 돌려줄 운영 체제

(operating system)내의 주소이다.

․스택의 응용 분야 : 시스템 스택, 수식 계산, 인터럽트, 컴파일러, 순환

등

∙스택의

* 큐의 정의

∙ QUEUE(1 : n) : 1차원 배열 형태

∙ FIFO(First In First Out)

삭제 ←                          ← 삽입

↑              ↑

front            rear

응용 분야 : 시스템 스택, 수식 계산, 인터럽트, 컴파일러, 순환 등

큐는 선입 선출구조로서 rear를 통해 삽입, front를 통해 삭제가 이루어진다.

1      2      3      4

초기상태

↑↑

f r

1      2      3      4

A의 삽입

↑   ↑

f    r

1      2      3      4

B의 삽입

↑         ↑

f          r

1      2      3      4

A의 삭제

↑    ↑

f     r

A

A	B

	B

큐의 초기 상태는 front와 rear가 모두 0이다. 삽입을 위해서는 rear를 증가시킨 후 데이터를 삽입하고, 삭제는 front를 증가 시켜 삭제를 행한다. 큐에서 rear의 현재 위치에는 유효한 데이터가 존재하고, front의 현재 위치에는 값이 없다.

* 큐의 적용 분야 : 작업 스케줄링, 버퍼 관리 등

* 큐의 삽입

procedure ADDQ(item, Q, n, rear)

if rear = n then call QUEUE-FULL

rear ← rear + 1

Q(rear) ← item

end ADDQ

순차 큐의 경우 경계조건은 rear=n이며, rear≠n이 경우 즉 큐에 삽입 할 공간이 있는 경우, rear의 위치를 증가시키고, 해당 위치에 값(item)을 삽입한다.

* 큐의 삭제

procedure DELETEQ(item, Q, front, rear)

if front = rear then call QUEUE-EMPTY

front ← front + 1

item ← Q(front)

end DELETEQ

순차 큐에서 삭제를 위한 경계조건은 front = rear 이며, front ≠ rear인 경우, 즉 큐에 삭제할 데이터가 있는 경우, front의 값을 증가시킨 위치의 값을 삭제한다.

* 순차 큐의 단점

Q(1 : 6)

1     2     3     4     5     6

↑	↑

f	r

rear = n 만원 큐

1     2     3     4     5     6

↑	↑

f	r

			D	E	F

D	E	F

순차 큐에서의 문제점은 rear = n이 반드시 만원 큐를 의미하지는 않는다.

따라서 rear = n인 경우, front의 위치를 점검하여, front가 0이 아니라면, front의 위치를

0의 위치로 옮기는 과정을 수행하여야 한다.

이러한 문제를 해결하기 위해 제안된 것이 원형 큐이다.

*원형 큐

원형 큐는 rear나 front의 위치를 결정하기 위해 mod연산자를 사용

한다. mod연산자를 사용함으로써 n개의 원소인 경우, 위치번호는 0

부터 n-1이 된다.

원형 큐의 삽입은 rear의 위치를 증가시킨 다음 front = rear의 조

건으로 만원 큐인가를 검사한다. front ≠ rear인 경우, 값(item)을

큐에 삽입한다.

원형 큐의 경우 경계조건은 삽입인 경우나 삭제인 경우 모두 front = rear이다.

* 원형 큐의 삭제

procedure DELETEQ(item, Q, n, front, rear)

if front = rear then call QUEUE-EMPTY

front ← (front+1) mod n

item ← Q(front)

end DELETEQ

* 원형 큐의 삽입

procedure ADDQ(item, Q, n, front, rear)

rear ← (rear+1) mod n

if front = rear then call QUEUE-FULL

Q(rear) ← item

end ADDQ

원형 큐에서의 삭제는 경계 조건(front = rear) 즉 공백 큐인가를 검사한 다음

front ≠ rear인 경우, front를 증가시켜 해당 위치의 원소를  삭제한다.

순차 큐는 rear=n인 경우, front의 위치가 0이 아니라면  front의 위치를 0이 되도록 모든 테이터를 왼쪽으로 옮기는 과정을 실행 해야한다. 그러나 원형 큐는 n-1 다음에 0번째로 이동이 되므로 순차 큐와 같은 문제는 없어진다.

* 수식의 표기법

중위 표기 :  A + B

전위 표기 :  +AB

후위 표기 :  AB+

∙ A * (B+C)의 경우 전위와 후위 표기는 다음과 같다.

전위 : * A+ BC

후위 : ABC + *

중위 표기는 연산자가 피연산자의 가운데 위치하며, 전위는 앞에, 후위는 뒤에 위치하도록

나타낸 표기방법이다.

* procedure EVAL(E)

②  top ← 0 //STACK을 초기화//

③  loop

④    x ← NEXT-TOKEN(E)

⑤    case

⑥      : x = '∞' : return//결과는 STACK(1)에//

⑦      : x is an operand : call ADD(x,STACK,n,top)

⑧      : else :

⑨      call DELETE(OP2, STACK, top)

⑩      call DELETE(OP2, STACK, top)

⑪      case

⑫      : x = '＋' : call ADD(OP1＋OP2, STACK, n, top)

⑬      : x = '—' : call ADD(OP1—OP2, STACK, n, top)

⑭      : x = '* ' : call ADD(OP1*OP2, STACK, n, top)

⑮      : x = '/ ' : call ADD(OP1/OP2, STACK, n, top)

⑯      : x = '**' : call ADD(OP1＋OP2, STACK, n.

top)

⑰   end

⑱  end

⑲ forever

end EVAL

위의 알고리즘에서 ④ x ← NEXT-TOKEN(E) 은 주어진 식에서 왼쪽부터 한 노드씩 읽어

x 로 나타낸 것이다. 이 알고리즘에서  x 값의 종류는 세 가지 이다. '∞'인 경우 식의 끝

을 나타낸 것이고,  x is an operand 즉 피연산자인 경우 스택에 삽입하는 과정을 수행하며,

그 나머지 else 에 해당되는 경우는 연산자인 경우이다. 이 경우 스택에서 두개의 값을 꺼내

어 연산을 한다음, 다시 스택에 삽입한다.

⑦, ⑫～⑯행의 ADD프로시저는 본교재 p.65의 ADD 알고리즘과 parameter를 연관시켜 이

해하기 바라며, ⑨, ⑩의 DELETE 프로시저는 p.66의 DELETE 알고리즘과 parameter를 연

관시켜 보기 바란다.

*후위 표기식의 연산

A * (B+C),    A = 3, B = 4, C = 5

⇒ABC+*      345+*

위의 알고리즘에 따라 후위 표기식에 의해 수식을 계산하는 과정이다.

* 수식의 변환

* 중위 → 후위 변환 알고리즘

① 토큰이 ∞이면 스택의 최하단에 스택을 비운다.

② 피연산자이면 출력한다.

③ “)” 이면 “(”가 나올 때 까지 연산자를 출력하고, “(”는 삭제한다.

④ ISP≥ICP 연산자 출력

⑤ 아니면 연산자를 스택에 저장

* 후위 표기식 변환 과정

A * (B+C)∞

A   -∞                              A

*   -∞    *                         A

(   -∞     *     (                   A

B   -∞    *     (                   AB

+   -∞    *     (     +             AB

C   -∞    *     (     +             ABC

)   -∞    *                          ABC

∞   -∞                               ABC+*

* 다중 스택

다중 스택이란 하나의 연속 공간에 두개 이상 여러 개의 스택을 나타낸 것이다. 두개의 스택을 나타낸 경우는 양쪽 끝을 bottom으로 하고, 가운데를 top으로 한 것이다.

전체 m개의 공간에 n개의 스택을 나타낼 경우 m/n개로 분할하여 n개의 스택을 나타낸 것이다.

*다중 스택의 삽입

procedure ADD(i, X)

if T(i) = B(i+1) then call STACK-FULL(i)

T(i) ← T(i) +1

V(T(i)) ← X

end ADD

i번째 스택에 삽입을 위한 경계조건은 top인 T(i)가 다음 스택의 bottom인 B(i+1)가 되었을 때, 노드를 삽입할 수 없는 조건이 되도, 그 이외의 경우 top을 증가시켜 해당 위치에 데이터 값 X를 삽입한다.

*다중 스택의 삭제

procedure DELETE(i, X)

if T(i) = B(i) then call STACK-EMPTY(i)

X(i) ← V(T(i))

(T(i)) ← T(i) - 1

end DELETE

삭제를 위한 다중 스택의 경계조건은 top인 T(i)가 bottom인 B(i)가 되는 경우, 삭제할 수

없는 상황이 된다. 그 외의 경우 노드가 존재하는 상황이므로 X(i)를 통해 삭제하고, top의

위치를 감소 시킨다.

제 4 장 연결 리스트(Ⅰ)

◁ 학습 내용 ▷

◦ 연결 리스트의 필요성

◦ 단순 연결 리스트

◦ 사용 공간과 비사용 기억 공간

◦ 동적으로 연결된 스택과 큐

*단순 연결 리스트의 노드

연결 리스트 구성을 위한 노드 구성은 자료값을 저장시키기

위한 데이터 부분과 다음에 연결될 기억 장소를 나타내기 위한

링크 부분으로 구성된다.

*단순 연결 리스트의 노드

연결리스트는 기억 공간상의 인접하지 않은 공간을 활용한다.

* 사용 공간과 비사용 기억 공간

연결리스트의 사용은 기억공간 전체를 사용공간과 비사용기억공간으로 나눈다. 사용공간에는 프로그램 및 현재 사용중인 기억장소들이 연결되어 있고, 비사용기억공간은 사용되기 위한 기억장소들의 집합이다. GETNODE와 RET프로시져는 노드의 사용과 반환을 위한 프로시져이다.

* 단순 연결 리스트의 생성

procedure CREATE(T)

call GETNODE(I)

T ← I ; DATA(I) ← '3304'

call GERNODE(I)

LINK(T) ← I

LINK(I) ← ; DATA(I) ← '3308'

end CREATE

위의 알고리즘은 두 개의 새로운 노드를 가져와 새로운 연결리스트를 생성하는 알고리즘이다. GETNODE는 비 사용기억공간으로부터 하나의 노드를 가져오기 위한 알고리즘이다.

T ← I 는 T가 가리키는 리스트를 만들기 위한 것이다. DATA(I) ← '3304'는 I의 데이터 부분에 데이터를 삽입하는 것이다. LINK(T) ← I는 I의 번지를 T의 링크부분에 저장하여 리스트의 연결관계를 나타낸다.

* 노드 삽입

procedure INSERT(T, X)

call  GETNODE(I)

DATA(I) ← '3305'

if T = 0 then [T ← I ; LINK(I) ← 0]

else  [LINK(I) ← LINK(X)]

[LINK(X) ← I]

end INSERT

T가 가리키는 리스트에 새로운 노드를 삽입하기 위한 알고리즘으로 X다음에 새로운 노드를 삽입하기 위한 알고리즘이다.

T = 0인 경우는 리스트에 노드가 존재하지 않는 경우이고,  T가  0이 아닌 경우, 즉 리스트에 노드가 존재하는 경우는 else이하의 구문을 실행하게 된다. [LINK(I) ← LINK(X)],

[LINK(X) ← I]는 새로운 노드 I를 X다음에 삽입하는 내용이다.

*노드 삭제

procedure DELETE(X, Y, T)

if Y = 0 then T ← LINK(T)

else LINK(Y) ← LINK(X)

call RET(X)

end  DELETE

위의 알고리즘은 T가 가리키는 연결 리스트에서 Y의 다음 노드 X를 삭제하는 알고리즘이다.

* 노드 출력

procedure PRINT(T)

P ← T

while P ≠ 0 do

PRINT (DATA(P))

P ← LINK(P)

end

end PRINT

procedure PRINT(T) 알고리즘은 T가 가리키는 리스트의 모든 노드를 출력하는 알고리즘이다.  P ← T는 리스트 T를 순회를 위해 P로 설정한 것이며, P = 0인 경우는 리스트의 끝인 경우이다. PRINT (DATA(P))는 P의 데이터를 프린트하고, P ← LINK(P)는 다음노드로 이동하는 과정을 나타낸 것이다.

* 연결 리스트를 이용한 스택과 큐

*다중 스택과 큐의 경계 조건

T(i) : i번째 스택의 톱(top)  1 ≤ i ≤ n

F(i) : i번째 큐의 앞(front)  1 ≤ i ≤ n

R(i) : i번째 큐의 뒤(rear)   1 ≤ i ≤ n

<초기 조건>

T(i) : 0  1 ≤ i ≤ n   //스택이 존재하지 않음//

F(i) : 0  1 ≤ i ≤ n  //큐가 존재하지 않음//

<경계조건>

T(i) : 0  // i번째 스택이 비어 있음//

F(i) : 0  // i번째 큐가 비어 있음//

*연결된 스택의 노드 추가

procedure	ADDS(Y)

call GETNODE(X)

DATA(X) ← Y

LINK(X) ← T

T ← X

end ADDS

위의 알고리즘은 연결리스트로 구현된 스택에 데이터 값 Y를 삽입하는 알고리즘이다. T를 이 스택의 top으로 생각하면 된다.

procedure ADDS(i,Y)

call GETNODE(X)

DATA(X) ← Y

LINK(X) ← T(i)

T(i) ← X

end ADDS

* 이 알고리즘은 다중 스택에서 임의의 i(1≤i≤n)번째 스택에

노드를 삽입하는 알고리즘이다.

* 연결된 스택에서 노드 삭제

procedure DELETES(Y)

if T = 0 then call STACK-EMPTY

X←T

Y←DATA(X)

T←LINK(X)

call RET(X)

end DELETES

위의 알고리즘은 연결리스트로 구현된 스택에서 top노드인 T의 데이터를 Y를 통해 삭제

하는 알고리즘이다.

알고리즘의 수행 단계별 처리는 다음 그림과 같다.

procedure DELETES(i,Y)

if T(i) = 0 then call STACK-EMPTY

X ← T(i)

Y(i) ← DATA(X)

T(i) ← LINK(X)

call RET(X)

end DELETES

* i(1≤i≤n)는 여러 개의 스택 중 임의의 스택을 나타낸 것임.

* 연결된 큐에 노드 추가

procedure ADDQ(Y)

call GETNODE(X)

DATA(X) ←  Y; LINK(X) ← 0

if F = 0 then [F ← R ← X]

else [LINK(R) ← X ; R ← X]

end ADDQ

위의 알고리즘은 새로운 노드 X를 GETNODE하여 데이터 Y를 저장하고, 큐에 삽입하는

알고리즘이다. 여기에서 큐의 rear는 리스트의 끝이므로 링크 부분은 0이 된다. 큐에 삽입을

위해서는 R(rear)의 위치를 변경해야한다.

procedure ADDQ(i, Y)

call GETNODE(X)

DATA(X) ← Y ; LINK(X) ← 0

if F(i) = 0 then [F(i) ← R(i) ← X(i)]

else [LINK(R(i)) ← X;R(i) ← X]

end DELETEQ

* i(1≤i≤n)는 여러 개의 큐 중 임의의 큐를 나타낸 것임.

* 연결된 큐에 노드 삭제

procedure DELETEQ(Y)

if F = 0 then call QUEUE-EMPTY

else[X←F ; F←LINK(X)

Y←DATA(X) ; call RET(X)]

end DELETEQ

큐에서의 노드 삭제는 F(front)를 이동시켜 리스트에서 삭제하고, call RET(X)에 의해 비사

용 기억공간으로 반환한다.

procedure DELETEQ(i,Y)

if F(i) = 0 then call QUEUE-EMPTY

else[X ← F(i) ; F(i) ← LINK(X)

Y ← DATA(X) ; call RET(X)]

else DELETEQ

* 비사용 기억 공간의 활용

<순차 공간에서 사용노드 획득>

procedure GETNODE(I)

if AV > n then call NO-MORE-NODES

I ← AV

AV ← AV+1

end GETNODE

위의 알고리즘은 크기가 n인 순차적 연속 공간에서 기억장소의 활용을 지원하기 위한 알고

리즘이다. AV는 비사용 기억공간의 시작주소이다. AV를 1씩 증가시키며, 노드를 획득한다.

< 연결 리스트 공간에서 가용 노드 획득>

procedure GETNODE(X)

if AV > 0 then call NO-MORE-NODEs

X ← AV

AV ← LINK(AV)

end GETNODE

위의 알고리즘은 불 연속적인 기억 공간상에서 가용 노드를 획득하기 위한 알고리즘이다.

여기에서도 AV는 비사용 기억공간의 시작주소이며, AV ← LINK(AV)에 의해 AV를 갱신

시키며, 비사용 기억공간을 운용한다.

* 노드 반환

procedure RET(X)

LINK(X) ← AV

AV  ← X

end RET

프로그램에서 사용이 끝나고, 비사용 기억공간으로 노드를 반환하기 위한 프로시저가 procedure RET이다. 반환된 노드 X를 새로운 AV로 하기 위한 과정, LINK(X) ← AV,  AV  ← X를 수행한다.

* 다항식의 연결 리스트 표현

A = 3x14 + 2x8 + 1

A

3   14           2   8            1   0   0

B = 8x14 -3x10 + 10x6

B

8   14           -3 10            10  6   0

위의 다항식의 연결리스트 표현을 2장에서 공부했던 배열의 표현과 비교하며, 내용을 정리

하기 바라며, 아울러 다항식의 덧셈 알고리즘도 배열을 이용한 알고리즘과 함께 프로그램으

로 구현하여 실행시켜 보기 바랍니다.

◁ 학습 내용 ▷

◦ 원형 연결 리스트

◦ 연결 리스트 응용

◦ 이중 연결 리스트

◦ 일반 리스트

제 4 장 연결 리스트(Ⅱ)

* 노드 반환 알고리즘

procedure ERASE(T)

if T = 0 then return

p ← T

while LINK(p) ≠ 0 do

p  ←  LINK(p)

end

LINK(p)  ←  AV

AV  ←  T

end ERASE

위의 알고리즘은 연결리스트의 끝을 찾아 노드를 전부 반환하기 위한 알고리즘이다. T = 0

라면 리스트내에 노드가 없으므로 실행을 중지하기위한 경계조건이며, while문에서

LINK(p) ≠ 0 즉 리스트내의 노드가 있는 동안 p  ←  LINK(p)에 의해 끝을 찾는다. 끝을 찾아 LINK(p)  ←  AV 와 같이 AV와 연결하고, AV  ←  T에 의해 AV를 갱신한다.

* 원형 연결 리스트

A = 3x14 + 2x8 + 1의 표현

* 연결 리스트의 노드 반환

procedure CERASE(T)

if T = 0 then return

X ←  LINK(T)

LINK(T) ←  AV

AV ← X

end CERASE

원형 연결리스트는 리스트의 끝 노드의 링크부분이 처음노드를 가리켜 원형구조를 만든것임.

연결리스트에서 T = 0 는 공백 리스트인가를 묻는 경계조건이며, X ←  LINK(T)는 T의 두 번째 노드를 X로 한 것이고, AV의 주소를 T의 링크 부분에 연결하고, X를 새롭게 AV로 한다.

* 헤드 노드를 가진 다항식

다항식 A = 3x14 + 2x8 + 1은

와 같이 표현할 수 있다.

헤드 노드는 가상(dummy)이며, 이러한 표현은 알고리즘을 단순하게 해주는 의미를 갖는다.

*헤드 노드를 가진 원형 리스트 반환

procedure CERASE1(T)

X ← LINK(T)

LINK(T) ← AV

AV ← X

end CERASE1

위의 알고리즘은 앞에서 설명한 노드를 반환하는 알고리즘 procedure CERASE(T)보다 경계 조건의 검사를 생략할 수 있는 등 실행 과정을 간략하게하는 특징이 있다.

교재 145쪽의 원형리스트를 이용한 다항식의 덧셈 알고리즘은 교재 132쪽에서 설명하고있는

다항식 덧셈 알고리즘보다 훨씬 단순해진 구조를 볼 수 있다.

* 단순 연결 리스트의 역순

이 알고리즘은 p, q, r 이라는 세 개의 포인터 변수를 이용하여, q는 p를 따르고, r은 q를 따르도록하여 리스트를 역순 구조로 바꾼 연결리스트의 응용이다.

procedure INVERT(X)

p ← X ; q ← 0

while p ≠ 0 do

r ← q ; q ← p

p ← LINK(p)

end

X ← q

end INVERT

이 알고리즘의 연산 시간은 m ≥ 1개의 노드를 가진 리스트에 대해서 while 반복문이  m번 수행되므로 연산 시간은 O(m)이 된다.

* 단순 연결 리스트의 결합

procedure CONCATENATE(X, Y, Z)

Z ← X

if X = 0 then [Z ← Y ; return]

if Y = 0 then return

p ←  X

while LINK(p) ≠ 0 do

p ← LINK(p)

end

LINK(p) ← Y

end CONCATENATE

이 알고리즘은 두 개의 리스트를 단순 결합시키기 위한 내용으로 연산 시간은 노드 수에 비례한다.

* 원형 연결 리스트의 앞에 노드 삽입

procedure INSERT-FRONT(A, X)

if A = 0 then [A ← X

LINK(X) ← A]

else [LINK(X) ← LINK(A)

LINK(A) ← X]

end INSERT-FRONT

이 알고리즘은 원형 연결리스트를 응용한 알고리즘으로 노드 X를 원형리스트에서 A의 앞 노드로 삽입하는 알고리즘이다. 이 알고리즘의 연산 시간은 상수로 결정되며, O(c)이다.

* 원형 연결 리스트의 길이 계산

procedure LENGTH(A)

i ← 0

if A≠0 then [ptr ← A

repeat

i ← i + 1 ; ptr ← LINK(ptr)

until ptr = A]

return(i)

end LENGTH

procedure LENGTH(A)는 A≠0 동안, ptr ← LINK(ptr)에 의해 순회하면서, i ← i + 1에 의해 노드의 개수를 계산하기 위한 알고리즘이다. return(i)는 계산 결과를 출력하기 위한 구문이다.

* 이중 연결 리스트의 필요성

이중 연결리스트는 단순 연결리스트에 비해 링크 필드를 가지므로서 기억공간을 더 많이 사

용하기는 하지만, 리스트의 노드를 찾고자 할 때, 선행 노드를 쉽게 찾을 수 있는 장점이 있

다.

이중 연결 리스트는 비선형구조인 트리를 표현하며, 응용 분야는 운영 체제의 동적 메모리

관리(dynamic memory management)에 적용되고 있다.

* 정의

x = RLINK(LLINK(x))

= LLINK(RLINK(x))

RLINK(Right LINK)는 노드의 오른쪽 링크를 나타내고, LLINK(Left LINK)는 노드의 왼쪽 링크를 나타낸다.

RLINK(LLINK(x))는 x의 왼쪽 링크를 가리키는 오른쪽 링크를 나타낸다.

LLINK(RLINK(x))는 x의 오른쪽 링크를 가리키는 왼쪽 링크를 나타낸다.

결과적으로, x나 RLINK(LLINK(x)), LLINK(RLINK(x))는 같은 노드이다.

*노드 삭제

procedure DDLETE(X, L)

RLINK(LLINK(X)) ← RLINK(X)

LLINK(RLINK(X)) ← LLINK(X)

call RET(X)

end DDELETE

X의 왼쪽 링크를 X의 왼쪽 링크를 가리키는 옆 노드의 오른쪽 링크로, X의 오른쪽 링크는 X의 오른쪽 링크를 가리키는 옆 노드의 왼쪽 링크로 옮기므로서, X는 리스트에서 삭제된다.

call RET(X)에 의해 비사용 기억공간으로 반환된다.

* 노드 삽입

procedure DINSERT(P, X)

LLINK(P) ← X

RLINK(P) ← RLINK(X)

LLINK(RLINK(X)) ← P

RLINK(X) ← P

end DINSERT

procedure DINSERT(P, X)는 노드 P를 X의 오른쪽에 삽입하기 위한 알고리즘이다.

LLINK(P) ← X는 X의 주소를 P의 왼쪽 링크로 하고, RLINK(P) ← RLINK(X)는 X의 오른쪽 링크를 P의 오른쪽 링크로 한다. LLINK(RLINK(X)) ← P는 P의 주소를 X의 오른쪽 링크를 가리키는 왼쪽링크로 한다. RLINK(X) ← P는 P를 X의 오른쪽 링크로 한다.

* 일반 리스트 (generalized list)

[정의] 일반 리스트 A는 원자 또는 리스트 원소들의 유한순차

a1, …, an(n≥0)이다. 원소 ai(1≤i≤n)가 리스트인 경우 이를

A의 서브 리스트라 한다.

* 일반 리스트

리스트 A = (a1, a2, …, an)에서

A : 리스트의 이름 , 대문자 표기

n : 리스트의 길이

a : 원소, 소문자 표기

n≥1인 경우 a1을 A의 head.

(a2, …, an)을 A의 tail이라고 한다.

* 일반 리스트의 예

① D = ( )

② A = (a, (b, c))

③ B = (A, A,( ))

④ C = (a, C)

위의 리스트 ①은 길이가 0인 공백리스트이며, ②는 길이가 2인 리스트이다. head(A)='a'이고, tail(A)=((b,c))이다. ③은 길이가 3인 리스트로서 head(B)=A, tail(B)=(A,( ))이고, head(tail(A))=A이고, tail(tail(B))=(( ))이다.

* 태그 필드를 사용한 리스트 표현

① D = (  )       D = 0

② A = (a, (b, c))

③ B = (A, A, ())

④ C = (a, C)

앞에서 제시한 리스트를 태그 필드를 사용하여 나타내면 그림 오른쪽과 같다. 노드 구성에서 처음 필드는 태그 필드로서 1인 경우 두 번째 필드가 링크 필드임을 나타내며, 0인 경우 데이터 값을 갖는다. 세 번째 필드는 리스트의 링크 관계를 나타낸다.

* 다중 변수 다항식의 일반 리스트 표현