자료구조

1. 정수의 표현방법, 계산

2. 진법의 변환, 계산, 순서도

3. 부 프로그램 호출 (CALL BY VALUE, CALL BY REFERENCE)

4. 배열(원소의 개수, 주소 찾기)

5. 연결리스트(단순, 원형, 이중, 이중 원형)

6. 스택 

1. 정수의 표현방법, 계산

	부호와 절대치	부호있는 1의 보수	부호있는 2의 보수
+8	0000 1000	0000 1000	0000 1000
-8	1000 1000	1111 0111	1111 1000
-26	1001 1010	1110 0101	1110 0110

★양수일때는 보수를 취해줄 필요가 없다.!!

2. 진법의 변환, 계산

음.. 알아서.. 잘..

3. 부 프로그램 호출 (CALL BY VALUE, CALL BY REFERENCE)

x = "호"

y = "서"

z = "사이버"

call love(x, x, x+y, z)

print (z)

---

function love(a, b, c, d)

a = b + b

d = a + c

CALL BY VALUE일때는 "사이버"가

CALL BY REFERENCE일때는 "호호호서"가 출력된다.

4.

4.1 A[2:5]일 때, A(5)의 주소는?

* ) 단, 2의 주소는 101 이며, 주소는 4씩이다.

A[2], A[3], A[4], A[5]

101, 105,  109,  113

4.2 A[2:5, 3:7]일때 A의 시작주소 A(2, 3)이 10일때 열 우선으로 A(4, 6)의 주소는?

(2, 3) 10	(2, 4) 14	(2, 5) 18	(2, 6) 22	(2, 7)
(3, 3) 11	(3, 4) 15	(3, 5) 19	(3, 6) 23	(3, 7)
(4, 3) 12	(4, 4) 16	(4, 5) 20	(4, 6) 24	(4. 7)
(5, 3) 13	(5, 4) 17	(5, 5) 21	(5, 6) 25	(5, 7)

4.3 A[-1:n, 1:m] 일때 원소의 개수는?

우선 X:Y 의 원소를 가지고 있을 때 원소의 개수는 Y-X+1이다.

만약 행과 열을 가지고있다면 행의 원소의 개수와 열의 원소의 개수를 곱해준다.

(n - (-1) +1) * (m - 1 + 1) = ( n + 2 ) * m

4.4 A[3:5, 2:4, 1:3]일때 A(4,3,2)의 주소는?

* ) 단 A[3,2,1]의 주소는 200

(3 , 2, 1) 200	(3, 2, 2)	(3, 2, 3)
(3, 3, 1)	(3 , 3, 2)	(3, 3, 3)
(3, 4, 1)	(3, 4, 2)	(3, 4, 3)

첫번째 페이지만 만들어보고 내가 뽑아야할 행, 열을 선택한다.

그리고 원소의 개수를 구한다.

첫페이지가 9개이고 (4, 3, 2)를 구해야하니 14번째의 원소이다.

하지만 첫번째의 주소는 200이라고 했으니 200 + 13을 해주면 된다.

4.5 A[5:8, 2:4] 열중심일때 6번째 원소

(5, 2)	(5, 3)	(5, 4)
(6, 2)	(6, 3)	(6, 4)
(7, 2)	(7, 3)	(7, 4)
(8, 2)	(8, 3)	(8, 4)

행 열은 그대로 적은 후 열단위로 세면 된다.

4.6 A[4,3,5]일때 A의 시작주소는100, 자료형은 2byte, 행우선 저장, A(4,2,3)의 주소는?

(1, 1, 1)	(1, 1, 2)	(1, 1, 3)	(1, 1, 4)	(1, 1, 5)
(1, 2, 1)	(1, 2, 2)	(1, 2, 3)	(1, 2, 4)	(1, 2, 5)
(1, 3, 1)	(1, 3, 2)	(1, 3, 3)	(1, 3, 4)	(1, 3, 5)

4페이지의 원소를 찾는것이니 3페이지까지의 원소의 개수를 구해준다.

15 * 3 = 45

그 후 2, 3까지의 개수를 구한다.

8

45 + 8 - 1 = 52

52 * 2 = 104

100 + 104 = 204

5.

5.1 선형리스트

-장점

1. 기억밀도가 1이다.(메모리 낭비가 없음)

2. 액세스 타임이 빠르다.

- 단점

1. 자료의 삽입, 삭제시 자료의 이동이 많다.

2. 기억장소의 낭비가 있다.

- 크기가 다양한 여러개의 선형리스트를 이용할때는 각각의 리스트에 최대크기를 가진 배열을 처음부터 준비해야하므로 기억장소가 낭비된다.

5.2 단순연결리스트

- 선형 리스트에 비하여 장점

1. 노드의 삽입과 삭제가 용이

2. 연속적인 기억공간이 없어도 저장이 용이

- 단점

1. 연결부분의 사용으로 선형리스트보다 많은 기억공간을 사용

2. 알고리즘의 구현이 복잡

3. 엑세스 타임이 느림

INSERT(head, X, item)

CALL GETNODE(I)

I->data = item

if(X == NULL)

I->link=head

head=I

else

I->link=X->link

X->link=I

DELETE(head, X, Y)

if(head == X)

head = X->link

else

Y->link = X->link

5.3 원형연결리스트

- 특징

1. 임의의 노드에서 다른 노드에 접근이 가능

2. 일정시간에 노드의 삽입, 삭제가 가능

3. 특정 노드가 없으면 무한루프에 빠질 수 있으므로 헤드포인터가 필요

INSERT(head, X, item)

CALL GETNODE(I)

I->data = item

if(head == NULL)

head=I

I->link=head

else

I->link=X->link

X->link=I

DELETE(head, X, Y)

if(X == head)

if(X->link == X)

head=NULL

else

Y->link=X->link

head=X->link

else

Y->link=X->link

5.4 이중연결리스트

- 특징

1. 양쪽방향 검색가능

2. 임의의 노드포인터가 파괴되었을경우 역추적을통한 복구가능

3. 기억장소의 낭비

6.

6.1 스택

PUSH(top, item)

CALL GETNODE(I)

I->data = item

I->link=top

top=I

POP(top. item)

tmp=top

item=tmp->data

top=tmp->link

CALL RET(tmp)

6.2 Polish Notation

1. 중위표기법(Infix) - A+B

2. 전위표기법(Prefix) - +AB

3. 후위표기법(Postfix) - AB+