선형구조 리스트,선형리스트,인접리스트,연결리스트,스택, 큐, 데크 CHAPTER 2 선형구조 리스트,선형리스트,인접리스트,연결리스트,스택, 큐, 데크

선형구조 리스트(list) 선형리스트 스택과 큐 원소(atom) 혹은 노드(node) 기억공간에 연속적으로 저장되어 있는 자료 기억매체의 접근 1차원 선형리스트 모든 항목들이 일대일 관계를 갖는 리스트 연접리스트(인접리스트) 순차적인 할당으로 이루어짐 연결리스트 연결할당(포인터에 의한)으로 이루어짐 스택과 큐 자료구조의 한쪽부분에서만 제한적으로 삽입 삭제가 이루어짐 원소(atom) 혹은 노드(node) 리스트를 구성하는 기본요소

2.1 연접 리스트(연속 배열 저장) 기억장소에 연속적으로 저장되는 리스트 i번째 원소의 저장 장소 위치 = B + (i - 1)l B : 첫번째 원소의 위치, l : 원소의 길이 임의의 배열이 연속적으로 접근하는 경우 항목 i+1 이 항목 I 다음에 접근이 가능 기억공간의효율성(밀도) = 정보비트수/총비트수 연접 리스트는 기억공간의 낭비가 없으므로 1 연결리스트는 기억공간의 낭비가 발생 1 2 3 i i+1 B l data 포인터 data 포인터 data 포인터

2.1 연접 리스트(연속 배열 저장) 삽입 삽입을 위한 공간 확보->원소를 뒤로 이동 평균 이동횟수 = (n+1)/2 이순신 전우치 이율곡 최치원 이순신 삽입 전우치 홍길동 홍길동 이율곡 최치원

2.1 연접 리스트(연속 배열 저장) n개의 노드로 구성된 연접 리스트에서 임의의 노드를 삽입하기 위한 평균 이동회수(mi) ….. 노드 i에 삽입  (n-i) + 1회 이동 노드 n에 삽입  (n-m) + 1회 이동 모든 노드를 삽입할 경우에는 임의의 노드가 대상이 될 확률 Pi = 1/n

2.1 연접 리스트(연속 배열 저장) 제거 삭제된 뒤의 원소들을 앞으로 이동 평균 이동횟수 = (n-1)/2 index data data 1 2 3 4 5 이순신 전우치 이순신 전우치 이율곡 최치원 삭제 홍길동 홍길동 이율곡 최치원

2.1 연접 리스트(연속 배열 저장) n개의 노드로 구성된 연접 리스트에서 임의의 노드를 제거하기 위한 평균 이동회수(md) ….. 노드 i를 제거  (n - i) 이동 노드 n을 삽입  (n-m) 이동 모든 노드를 제거할 경우에는 임의의 노드가 대상이 될 확률 Pi = 1/n

2.1 연접 리스트(연속 배열 저장) 노드수가 많은 연접리스트에서 삽입과 제거 예제 자료를 삽입하거나 제거할 때 많은양의 자료를 이동 시간이 많이 소요 됨 예제 500,000개의 원소로 구성된 전화번호부 목록이 있다. 삽입과 삭제시 평균이동 횟수 md = mi = 500,000 / 2 = 250,000 1개의 원소를 이동하는 시간이 100마이크로초라면 평균이동시간 Td = Ti = 250,000 * 100 * 106 삽입과 삭제되는 원소가 하루에 1%발생한다면 전체시간은 시간 = 25초 * 500,000 * 0.01 = 35시간

2.2 배열과 행렬 2.2.1 배열(Array) 배열의 정의 배열의 표현 동종의 데이터형의 요소를 저장한 연속적인 기억장소의 집합 정해진 값 + 인덱스의 쌍으로 구성 첨자를 이용하여 순서를 표시 배열의 표현 배열변수명(하한:상한) (하한 .. 상한) 1차원 배열 : arr(1:30) arr[1 .. 30] 2차원 배열 : arr(1:3, 1:5) arr[1..3, 1..5] 프로그래밍 언어에서의 선언 예 fortran : integer arr(10) 혹은 dimension arr(10) c : int arr[10] ; basic : dim arr(10) as integer cobol : 01 array-r. 03 arr pic 99 occurs 10. ARR(1) ARR(2) ARR(3) ARR(4) ARR(5) ARR(6) ARR(8) ARR(7) ARR(10) ARR(9)

2.2.1 배열(계속) 1차원 배열 배열의 i번째 요소의 주소 = 배열의 시작 주소 + ( 배열의 첨자 - 1) *요소의 크기 요소의 크기가 4바이트인 경우의 주소 지정, 시작주소 : 1024 ARY[1..10] 1024 1028 1032 1036 1040 1044 1048 1052 1056 1060 전체배열의 요소  10개 기본주소  1024 ARY(i) 의 주소는 1024 + (i – 1) * 4 ARY(5)의 주소는 1024 + (5-1) * 4 = 1040 ARR(1) ARR(2) ARR(3) ARR(4) ARR(5) ARR(6) ARR(8) ARR(7) ARR(10) ARR(9)

2.2.1 배열(계속) 2차원 배열 행우선 열우선 arr(1,1) arr(1,2) arr(1,3) 행우선 순서 arr(1,1), arr(1,2), arr(1,3),..,arr(3,1), arr(3,2), arr(3,3) C, COBOL, Pascal 열우선 순서 arr(1,1), arr(2,1), arr(3,1),..,arr(1,3), arr(2,3), arr(3,3) Fortran a(1..u1,1..u2) 행우선순서 = 시작주소 + (i -1) u2 + (j -1) 열우선순서 = 시작주소 + (j -1) u1 + (i -1) 행우선 열우선 arr(1,1) arr(1,2) arr(1,3) arr(2,1) arr(2,2) arr(2,3) arr(3,1) arr(3,2) arr(3,3)

2.2.1 배열(계속) 2차원 배열 A[1 .. U1, 1 .. U2] 이차원배열의 주소 계산 행우선순서  [Base]address + (i-1) * U2 + (j-1) 열우선순서  [Base]address + (j-1) * U1 + (i-1) A[1..4, 1..5]가 있으며, 시작주소가 48번지이며, 한 요소 당 1byte 차지한다. A[3,4]의 주소는 행우선순서  48 + (3-1) * 5 + (4-1) = 61 열우선순서  48 + (4-1) * 4 + (3-1)= 62

2.2.1 배열(계속) 3차원 배열 arr(2,1,1) arr(2,1,2) arr(2,1,3) a(1..u1, 1..u2, 1..u3) 행중심 순서 (1,1,1),(1,1,2),(1,1,3),(1,2,1),(1,2,2),(1,2,3),(1,3,1),(1,3,2),(1,3,3) (2,1,1),(2,1,2),(2,1,3),(2,2,1),(2,2,2),(2,2,3),(2,3,1),(2,3,2),(2,3,3) 시작주소 + (i-1) u2u3 + (j-1) u3 + (k-1) 열중심 순서 (1,1,1), (2,1,1),(1,2,1),(2,2,1),(1,3,1),(2,3,1) (1,1,2), (2,1,2),(1,2,2),(2,2,2),(1,3,2),(2,3,2) (1,1,3), (2,1,3),(1,2,3),(2,2,3),(1,3,3),(2,3,3) 시작주소 + (k-1) u1u2 + (j-1) u1 + (i-1) arr(1,1,1) arr(1,1,2) arr(1,1,3) arr(1,2,1) arr(1,2,2) arr(1,2,3) arr(1,3,1) arr(1,3,2) arr(1,3,3)

2.2.1 배열(계속) 2차원 배열 A(2:5, 3:7) A(m,n)으로 변경하면, 크기 = (상한 – 하한 ) + 1 행우선 순서에서 A(4,6)은 몇번째 원소? 열우선 순서에서 A(4,6)은 몇번째 원소?

2.2.2 행렬(Matrix) 행렬의 개요 정방행렬(Square matrix) 수들의 배열, 1850년 실베스터(수학자) m행 n열의 배열 : m x n 행렬 i번째 행, j번째 열의 요소 : Aij a11 a12 .......... a1n a21 a22 .......... a2n A = . . . . . . am1 am2 .......... amn 정방행렬(Square matrix) 행과 열의 갯수가 같은 행렬 : n x n 행렬 주대각원소 : a11, a22, .... , ann 대각 행렬 : 주대각 이외의 원소가 모두 0인 행렬 aij = 0, I < > j

2.2.2 행렬(계속) 전치행렬(Transpose matrix) 행과 열의 원소를 서로 바꾸어 놓은 행렬 aij aji 전치행렬 변환 알고리즘 begin for i = 1 to m do for j = 1 to n do AT(i, j) = A(j, I) end;

2.2.2 행렬(계속) 희박한 행렬(희소행렬:Sparse matrix) 행렬의 원소들 중 0의 값을 갖는 것이 비교적 많은 행렬을 효율적으로 표현한 행렬 0 0 15 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 3 0 0 0 -13 0 0 0 0 0 0 0 7 0 희소행렬의 표현법 메모리 절약, 빠른 탐색 수정의 복잡 6:행의 수, 7:열의 수, 5:0이 아닌 원소수 0이 아닌 원소들의 (행, 열, 값)

2.2.2 행렬(계속) 희박한 행렬(계속) 희소행렬의 전치행렬 변환 알고리즘 1 희소행렬의 전치행렬 변환 알고리즘 2 for (각 i 행에 대해) do 전치행렬원소(j, i, 값) = 희소행렬원소(i, j, 값) end 희소행렬의 전치행렬 변환 알고리즘 2 for ( j 열에 있는 모든 원소에 대해) do

2.3 연결리스트 리스트 내의 모든 노드가 다음 노드의 위치를 가리키기 위한 포인터 소유 장점 단점 노드의 삽입, 삭제가 용이 연속적인 기억공간이 없어도 저장 가능 단점 링크 필드를 위한 추가 공간이 필요 알고리즘 구현이 복잡 노드 검색시 무한 루프에 빠질 수 있다. 연결 리스트의 노드 구조 데이터 링크 헤드 가 나 다 라 ^

2.3.1 단순 연결 리스트(singly linked list) 하나의 노드는 데이타 필드와 하나의 링크 필드로 구성 자료 검색은 한방향으로만 진행 단순 연결 리스트의 노드 삽입 삽입과정 GETNODE(I) DATA(I) <- ‘C’ LINK(I) <- LINK(X) LINK(X) <- I X .... Head A B D Z ^ C I

2.3.1 단순 연결 리스트(계속) 삽입 알고리즘 procedure INSERT(Head, item, X) /* X : X가 가리키는 노드 다음에 삽입 */ /* 공백조건 : Head = Nil */ call GETNODE(I) DATA(I) <- item if (Head = Nil) then Head <- I LINK(I) <- Nil else LINK(I) <- Link(X) LINK(X) <- I end INSERT

2.3.1 단순 연결 리스트(계속) 단순연결리스트의 노드 제거 제거 알고리즘 제거과정 LINK(Y) <- LINK(X) call RET(X) 제거 알고리즘 procedure DELETE(X, Y, Head) /* X : 제거할 노드를 가리키는 포인터 */ if (Y = Nil) then Head <- LINK(Head) 혹은 Head <- LINK(X) else end DELETE Y X Z A B C Head ^ .... D

2.3.1 단순 연결 리스트(계속) 연결리스트를 이용한 사용가능 공간 리스트 활용 예 GETNODE(I) RET(X) .... Avail A B C D Z ^ A .... B C D Z ^ I Avail X A .... B C D Z ^ Avail

2.3.2 원형 연결 리스트 마지막 노드의 링크 필드가 널 링크가 아닌 첫번째 노드 주소 한 노드에서 모든 노드로의 접근이 가능 삽입과 삭제가 용이 검색시 무한 루프 -> 헤드 노드로 보완 .... Head A B C Z

2.3.3 이중 연결 리스트 선행 노드와 후속 노드에 대한 링크(두개의 포인터) 양방향 검색 이중 연결 리스트의 노드삽입 삽입과정 GETNODE(I) DATA(I) <- ‘C’ RLINK(I) <- RLINK(X) RLINK(X) <- I LLINK(I) <- LLINK(RLINK(I)) LLINK(RLINK(I)) <- I LLINK DATA RLINK X .... Head ^ A B D .... Z C I

2.3.3 이중 연결 리스트(계속) 삽입 알고리즘 procedure INSERT_DOUBLE(Head, item, X) call GETNODE(I) DATA(I) <- item if (Head = Nil) then Head <- I LLINK(I) <- Nil RLINK(I) <- Nil else RLINK(I) <- RLINK(X) RLINK(X) <- I LLINK(I) <- LLINK(RLINK(I)) LLINK(RLINK(I)) <- I end INSERT_DOUBLE

2.3.3 이중 연결 리스트(계속) 이중 연결 리스트의 노드 제거 제거과정 RLINK(Y) <- RLINK(X) LLINK(RLINK(X)) <- LLINK(X) call RET(X) X Y .... Head ^ A B C D .... Z

2.3.3 이중 연결 리스트(계속) 제거 알고리즘 procedure DELETE_DOUBLE(X, Y, Head) if (Y = Nil) then Head <- LLINK(Head) else RLINK(Y) <- LLINK(X) LLINK(RLINK(X)) <- LLINK(X) call RET(X) end DELETE_DOUBLE

2.3.4 이중 원형연결 리스트 이중 연결 리스트 + 원형 연결 리스트 마지막 노드의 RLINK는 첫번째 노드의 위치 첫번째 노드의 LLINK는 마지막 노드의 위치 널링크가 없다 Head - Head A B D Z ....

다항식 배열로 표현 가능 다항식 : 형태의 항들의 합, 즉 a : 계수, x : 변수, e : 지수 다항식의 차수(degree) : 다항식의 최고차 항의 지수

다항식 <표현 1> 지수들의 올림차순으로 표현 차수 : n → n+1개의 항목을 갖는 배열을 이용하여 표현 장점 : 연산을 위한 알고리즘이 간단 단점 : 다항식이 희소(sparse)한 경우기억 공간의 낭비 대부분의 계수가 0인 아닌 경우 사용 1 n a0 a1 an

다항식 <표현 2> 계수와 지수의 쌍으로 표현 <표현 2> 계수와 지수의 쌍으로 표현 대부분의 계수가 0인 경우 사용 예제 1 다항식 를 계수와 지수의 쌍으로 표현 계수 → 5 4 지수 → 100

다항식 <예> A(x)=4+2x+3x2 B(x)=1+3x2+10x3 C(x)=5+2x+6x2+10x3 A 1 2 4 1 2 4 3 B 10 C 5 6

다항식 head [표현 3] 연결 리스트를 사용한 다항식의 표현 각 항을 위한 노드 정의 : PolyNode PloyNode 구조 coef exp link head ^

다항식 <예> 다음 다항식 의 표현 A 5 3 8 2 4 B 9 4 -3 2 6 1

2.4 스택(stack)과 큐(queue) 2.4.1 스택(stack)의 입출력 선형리스트의 특별한 경우 top이라는 자료구조의 끝에서만 삽입과 삭제 발생하는 자료구조 후입선출 구조(LIFO : Last-In Firtst-Out) 삽입순서 : A, B, C, D 제거순서 : D, C, B, A 삽입(push) 제거(pop) Top(stack pointer) dn . d2 d1 bottom

스택(stack) 용어정리 예 Push a Push b pop pop Push c Push d pop pop b d a a a stack pointer(top) : 스택에서 삽입과 삭제가 일어나는 포인터 push : 스택에 데이터를 삽입 pop : 스택에서 데이터 하나를 제거 응용 : 컴퓨터언어에서 서브루틴의 복귀주소 예 리스트 abcd 를 스택을 이용하여 badc로 바꾸고자 한다. 리스트 abcd를 스택을 이용하여 bcda로 바꾸고자 한다. 연산 순서는? Push a Push b pop pop Push c Push d pop pop b d a a a c c c b ba ba ba bad badc

2.4.1 스택의 입출력(계속) 기차가 차량기지를 거쳐서 철로로 진입할 수 있는 순열은? C B A 차량기지(stack) 진행방향

2.4.1 스택의 입출력(계속) 삽입 알고리즘 procedure ADD(item, STACK, n, top) if (top >= n ) then call STACK_FULL top <- top + 1 STACK(top) <- item end ADD 제거 알고리즘 procedure DELETE(item, STACK, top) if (top <= 0 ) then call STACK_EMPTY item <- STACK(top) top <- top - 1 end DELETE

2.4.1 스택의 입출력(계속) 연결리스트를 이용한 스택 표현 연접 리스트를 이용한 스택 표현 index stack 5 TOP : 스택을 동작시키기 위한 포인터 연접 리스트를 이용한 스택 표현 index stack 5 4 TOP 3 2 1 TOP D C B A ^ A D B C

2.4.2 큐(queue)의 입출력 선입선출(FIFO:First-In First-Out) 제거는 앞(front)에서, 삽입은 뒤(rear)에서 발생 공백상태(empty)를 구분하기 위하여 front : 실제 앞보다 1이 작은 위치를 가리킨다. rear : 마지막으로 삽입된 원소를 가리킨다. 큐(queue)의 입출력 입력순서 : ABCD 출력순서 : ABCD A B C D front rear

2.4.2 큐의 입출력(계속) 삽입 알고리즘 제거 알고리즘 procedure ADDQ(item, Q, n, rear) if (rear = n ) then call QUEUE_FULL rear <- rear + 1 Q(rear) <- item end ADDQ 제거 알고리즘 procedure DELETEQ(item, Q, n, rear) if ( front = rear ) then call QUEUE_EMPTY front <- front + 1 item <- Q(front) end DELETEQ

2.4.2 큐의 입출력(계속) 원형큐(circular queue) 큐가 비어있는데 QUEUE_FULL발생하는 단점을 보완 크기가 n인 배열 Q(0:n-1)를 원형으로 간주 n-1개의 원소만 저장 가능 front : 큐의 첫번째 원소로부터 반시계방향으로 하나 앞의 위치 rear : 큐에 마지막으로 삽입된 원소의 위치 Q(5) Q(4) E . front =1 front = 0 rear = 4 D . . rear = 5 . Q(3) C . B Q(n-3) Q(2) A Q(n-2) Q(1) Q(0) Q(n-1)

2.4.2 큐의 입출력(계속) 삽입 알고리즘 제거알고리즘 procedure ADDCQ(item, Q, n, front, rear) if (rear = n-1) then rear <- 0 else rear <- rear + 1 if (front = rear) then call QUEUE_FULL else Q(rear) <- item end ADDCQ 제거알고리즘 procedure DELETECQ(item, Q, n, front, rear) if (front = rear) then call QUEUE_EMPTY else front <- (front + 1) mod n item <- Q(front) end DELETECQ

2.4.2 큐의 입출력(계속) 큐의 활용 개별적인 큐를 갖는 세개의 서버 예 단일 큐를 갖는 세개의 서버 예 queue 1 server1 queue 2 server2 queue 3 server3 server1 shared queue server2 server3

2.4.3 데크(deque) Double Ended Queue 리스트의 처음과 마지막 원소에 대해 삽입과 삭제 수행 스택과 큐의 혼합형 자료구조 L-pointer : 데크의 왼쪽끝을 가리키며, 삽입과 삭제 발생 R-pointer : 데크의 오른쪽끝을 가리키며, 삽입과 삭제 발생 A B C D A B C D A B C D 입력제한데크:SCROLL 출력제한데크:SHELF

수식의 표현 수식의 표현 ○ 수식 표기 방법 - 연산자의 위치에 따른 분류 ① 중위 표기(infix notation) : 연산자가 피연산자들 사이에 존재 ② 전위 표기(prefix notation) : 연산자가 피연산자들 앞에 존재 ③ 후위 표기(postfix notation) : 연산자가 피연산자들 다음에 존재 표현 예 6 + 4 * 2 42*6+ +6*42 컴퓨터에서 수식 계산 중위 표기법 → 후위 표기법 → 계산 스택 이용

수식의 표현 [풀이] a / b – c + d * e – a * c → ((((a / b)-c)+(d*e))-(a*c)) 중위 표기식을 후위 표기식으로 바꾸는 알고리즘 ① 식을 연산자 우선 순위에 따라 전부 괄호로 묶음 ② 이항 연산자들을 우선 순위에 따라 모두 자기 오른쪽에 가장 가까운 닫는 괄호의 위치로 이동 ③ 모든 괄호를 제거 중위 표기법으로 표현된 수식을 후위 표기법 변환 a/b-c+d*e-a*c [풀이] a / b – c + d * e – a * c → ((((a / b)-c)+(d*e))-(a*c)) → a b / c –d e * + a c * -

수식의 계산 후위 표기식의 계산 알고리즘 ① 수식을 왼쪽에서 오른쪽으로 검사하면서 연산자를 만날 때까지 피연산자들을 스택에 저장 ② 연산자를 만나면, 필요한 수만큼의 피연산자를 스택에서 꺼내어 연산하고, 그 결과를 다시 스택에 저장 ③ 수식의 끝에 도달할 때까지 위 과정들을 반복

수식의 계산 후위식 표기법으로 표현된 수식 “6 2 / 3 - 4 2 * +”의 계산 과정 토 큰 스 택 6 $6 2 $6 2 “6 2 / 3 - 4 2 * +”의 계산 과정 토 큰 스 택 6 $6 2 $6 2 / $3 ← 6/2 3 $3 3 - $0 ← 3-3 4 $0 4 $0 2 * $0 8 ← 4*2 + $8 ← 0+8