슬라이드 1

Transcription

1 선형구조 배열 : 장기본개념 스택 : 큐 : 연결리스트 : 4 자료와정보 컴퓨터 주기억장치 트리 비선형구조 그래프 자료 정보 보조기억장치 자료, 프로그램 자료구조 자료저장, 이용알고리즘 프로그램 I = P() : N N : M 5 기본개념 선형구조 자료구조 배열 ( 연속리스트 (contnuous lst) 스택 (stack), 큐 (queue) 연결리스트 (lnked lst) 비선형구조 트리 (tree), 그래프 (graph) 자료구조응용 탐색, 정렬 알고리즘과프로그램 알고리즘 (algorthm) 특정문제를해결하기위해기술한일련의논리의순서 프로그램 (program) 알고리즘을컴퓨터가이해하고실행할수있는특정 프로그래밍언어로표현한것 program = algorthm + data structure 3 6

2 알고리즘의특징 자료의종류와표현 () 입력 : 외부제공자료가있을수있음 출력 : 한가지이상의결과생성 명확성 : 각명령은명확 유한성 : 한정된단계실행후종료 유효성 : 컴퓨터처리가능 7 문자형자료 영문자 : byte, 한글문자 : byte 는 SII 코드인 이저장 논리형자료 참 (true, ) 또는거짓 (false, 0) &&(N), (OR),!(NOT) 포인터형자료 저장장소의주소를표현하기위한자료형 nt, *p : 는정수변수, p 는정수에대한포인터변수 p = & : & 는 의주소값을 p 의값으로지정 *p = 0 : 포인터 p 가가리키는장소에 0 을저장 0 알고리즘기술언어사용 자연어에의한표현 한글또는영문슈도코드 (PSEUO OE) 도형에의한표현 알고리즘기술방법 흐름도 (FLOW HRT) 박스 (OX) 다이어그램 자료 자료와자료형 현실세계의관찰이나측정을통해수집된값이나사실 프로그램의처리대상이되는모든것 자료형 자료의집합과이자료에적용할수있는연산의집합 예 ) nteger 자료형 - 자료 : 정수 ( -,-,0,, ), 연산자 : +, -, *, /, mod 추상자료형 (T) 은객체의명세와그연산의명세가그객체의표현과연산의구현으로부터분리된자료형 8 자료의종류와표현 () 정수형자료 4byte (short : byte, nt 와 long : 4byte) 0 진수 35 표현 부호부 실수형자료 정수부 4byte (float : 4byte, double 과 long double : 8byte) 0진수 표현 부호부 지수부 가수부 9 추상자료형 추상화 (abstracton) 자세한것은무시하고, 필수적이고중요한속성만으로단순화시키는과정 추상자료형 (abstracton data type : T) 자료형의논리적정의 자료와연산의본질에대한명세만정의한자료형 자료가무엇이고, 각연산의기능을정의 추상화와구체화의관계 추상화 구체화 자료 추상자료형 자료형 연산 알고리즘 프로그램

3 자연수의추상자료형 T Natno object : { nteger, 0} functon : for all x, y Natno zero() ::= return 0; szero(x) ::= f (x=0) then return true else return false; succ(x) ::= return x + ; add(x, y) ::= return x + y; subtract(x, y) ::= f x < y then return 0 else return x - y; equal(x, y) ::= f x = y then return true else return false; End Natno Factoral 순환함수 () 순환알고리즘 Factoral(n) // n 은음이아닌정수 f (n <= ) then return else return (n factoral(n-)); end Factoral() Factoral(4) = (4 Factoral(3)) = (4 (3 Factoral())) = (4 (3 ( Factoral()))) = (4 (3 ( ))) = (4 (3 )) = (4 6) = 순환의종류 직접순환 : 간접순환 : 순환방식의적용 순환 (recurson) 분할정복 (dvde and conquer) 의특성을가진문제에적합 어떤복잡한문제를직접간단하게풀수있는작은문제로분할하여해결하려는방법 성능분석과성능측정 성능분석 (performance analyss) 프로그램을실행하는데필요한시간과공간추정 성능측정 (performance measurement) 컴퓨터가실제로프로그램을실행하는데걸리는시간측정 4 7 순환알고리즘과비순환알고리즘 n! 의계승 (factoral) 함수를정의 n! n ( n ) 순환정의 n! n ( n )! n 일때 n 일때 n 일때 n 일때 성능분석 공간복잡도 Sp = Sc + Se 고정공간 + 가변공간 시간복잡도 Tp = Tc + Te 컴파일시간 + 실행시간 5 8 3

4 연산시간표기법 g-oh (O), g-omega (Ω), g-theta (θ) g-oh (O) 연산시간표기법 f, g가양의정수를갖는함수일때, 두양의상수 a, b가존재하고, 모든 n b에대해 f(n) a g(n) 이면, f(n) = O(g(n)) f(n) = 3n + : f(n) = O(n) (a=4, b=) f(n) = 000n +00n 6 : f(n) = O(n ) (a=00, b=00) f(n) = 6 n + n : f(n) = O( n ) (a=7, b=4) f(n) = 00 : f(n) = O() (a=00, b=) 배열 (array) 자료를컴퓨터기억장치내의연속적인기억장소에저장하여순차적으로또는임의적으로접근할수있는가장간단한선형자료구조 < 인덱스, 원소 > 쌍의집합 원소들은모두같은형 (type), 같은크기 접근방법은직접접근 배열이름이 a 라면, a[ 인덱스 ]= 원소값 인덱스 원소값 연산시간함수의변화 배열 (array) 차원배열 n n 3 n nlog n log n n [0] [] [] [3].. [99] (L) (L+) (L+) (L+3).. (U) 원소또는멤버 배열원소의수 : U( 상한값 ) L( 하한값 ) + [00] 이라고배열을선언하면 [0] 부터 [99] 까지사용 [-:3] 은 [-], [-], [0], [], [], [3] 을나타냄. ( 다른언어에서사용 ) ddress() = ddress((l)) + K*(+L) 0 3 배열 (array) 차원배열 () 차원배열 (n m) 행 (row) 장배열과레코드 열 (olumn) [0][0] [0][] [0][] [0][m-] [][0] [][0]. [n-][0] [n-][m-] 4 4

5 배열 (array) 차원배열 () 차원배열 (n m) 차원배열의저장방법 행우선저장방법 [0][0] [0][] [0][] [0][m-] [][0] [][0]. [n-][0] [n-][m-] ddress((,j)) = ddress((l,l)) + (-L)*(U-L+)*k + (j-l)*k 5 배열의표현 - 차원배열 (5) 차원배열 a[m, n] 일경우, 처음원소 : a[0,0] 주소가 α 일때, 임의의원소 a[,j] 의주소 행우선 : α + *n +j 열우선 : α + j*m [,3] 일때 [,0] 의주소행우선 : +x3+0 열우선 : +0x+ 8 배열 (array) 차원배열 (3) 차원배열 (n m) 차원배열의저장방법 열우선저장방법 [0][0] [0][] [0][] [0][m-] [][0] [][0]. [n-][0] [n-][m-] 순서리스트 () 순서를가진원소들의순열 물리적순서가아닌원소의특성에의한논리적순서를의미 리스트 (lst) 는단순히원소들의순열 (sequence) 리스트 L=(e, e,, e n ) L 은리스트이름, e 는리스트원소 공백리스트 ( 원소가하나도없는리스트 ) 의표현 : L=( ) 리스트의각원소는선행자 (predecessor) 와후속자 (successor) 를가짐 요일 = ( 월, 화, 수, 목, 금, 토, 일 ) ddress((,j)) = ddress((l,l)) + (j-l)*(u-l+)*k + (-L)*k 6 9 배열의표현 - 차원배열 (4) 순서리스트 () 차원배열의선언 : a[n, n ] n : 행의수, n : 열의수, 원소수 :n n 차원배열을 차원메모리표현 [,3] 열 0 0 행 [0,0] [0,] [0,] [,0] [,] [,] 행우선 0 행 행 [0,0] [,0] [0,] [,] [0,] [,] 열우선 0 열 열 열 7 S = (a,a,,a n ) 리스트길이 (n) : 유한 리스트읽음 (left rght, rght left) : access 번째원소검색 ( n) : retreve 번째에새로운값저장 ( n) : update 번째에새로운원소삽입 : nsert + 번째원소삭제 : delete

6 다항식의 차원배열표현 () 희소행렬의표현방법 < 표현 > 계수를순서적으로표현 p(x)=a n x n +a n- x n- + +a x+a 0 a n a n- a n- a a 0 coef[o] [] [] [n-] [n] X 4 +0X 3 +X +6 : (, 0,, 0, 6) < 표현 > 0 이아닌계수만을취한표현 b(x)=b m- x em- +b m- x em- + +b 0 x e0 (e m-, b m-, e m-, b m-,, e 0, b 0 ) X 4 +0X 3 +X +6 : (4,, 3, 0,,, 0, 6) 행렬은 < 행, 열, 값 > 으로원소를식별 0 이아닌원소에대해열이 3 인 차원배열로표현 효율적인연산을위해행과열을오름차순으로저장 = [9,3] b[0] [] [] [3] [4] [5] [6] [7] [8] [0] [] [] 다항식의 차원배열표현 () 예 )=5X 0 + 일경우 < 표현> =(n, a n, a n-,, a, a 0 ) < 표현> =(m,e m-,b m-,e m-,b m-,,e 0,b 0 ) 희소행렬의전치 전치행렬 (transposed matrx) 원소의행과열을교환시킨행렬 원소 <, j, v> <j,, v>, 예 ) <0, 4, 3> <4, 0, 3> 간단한전치행렬알고리즘 ( 행우선표현 ) for ( j 0; j <= n- ; j j+ ) do for ( 0; <=m- ; + ) do b[ j, ] a[, j]; 희소행렬의전치 행우선, 행내에선열오름차순으로저장된경우, 각열별로차례로모든원소를찾아행의오름차순으로저장하는작업을반복 3 35 다항식의 차원배열 X 8-6X 5 +0X 3 +X - : (8,, 5, -6, 3, 0,,, 0, -) < 표현 > 0 이아닌계수만을취한표현방법으로 p[5,] 에표현 p[0] [] [] [3] [4] 지수 [0] 계수 [] 문자열연결 #defne MX_SIZE 00 /* 문자열의최대크기 */ char s[mx_size]="dog"; char t[mx_size]="house"; char s[]="dog"; char t[]="house"; s[0] s[] s[] s[3] d o g \0 t[0] t[] t[] t[3] t[4] t[5] h o u s e \0 s[0] s[] s[] s[3] s[4] s[5] s[6] s[7] s[8] s[9] d o g h o u s e \0 문자열 s 와 t 를 strcat(s, t) 연결함수로연결한결과

7 레코드 스택의정의 논리적으로서로연관이있는자료원소들의집합체 집합체의이름 : 레코드이름 레코드집합체내의각자료원소 : 필드 ( 항목, feld) 학번 이름 나이 출생지 성별 홍길동 8 서울 M nt char short char har 4byte 9byte byte 5byte byte 자료의입력과출력이한쪽 끝에서만이루어짐 후입선출리스트 (LIFO, Last In Frst Out) PUSH, POP 연산 top 포인터로삽입과삭제가이루어짐 top 삽입 P x Y 삭제 5 여유 4 3 공간 Z 0 bottom 레코드와파일 스택의자료삽입과삭제 레코드들의모음 ( 집합체 ) : 파일 (fle) 순차파일 (sequence fle) : 파일내의모든레코드들의논리적구조가동일한파일 키필드 (key feld) : 레코드를구별할수있는특정필드 키순차파일 (key-sequenced fle) : 키필드의값에따라레코드들이정렬된파일 학번이름나이출생지성별 삽입 : Push, 삭제 : Pop top 을스택포인터 (stack ponter) 라함 top top top top 홍길동 8 서울 M 김철수 0 경기 M 766 박영희 9 충남 W 7665 이기수 전북 M 7674 정미영 0 경남 W 768 최미숙 강원 W top top top top E 38 4 스택의순차표현 3 장스택과큐 차원배열, Stack[n] 을이용한순차표현 스택을표현하는가장간단한방법 n 은스택에저장할수있는최대원소수 스택의 번째원소는 Stack[-] 에저장 변수 top 은스택의톱원소를가리킴 ( 초기 : top = -) 첫번째원소두번째원소 stack[0] stack[] 번째원소 stack[-] n 번째원소 stack[n-] 4 7

8 배열을이용한스택의구현 () #nclude <stdo.h> #nclude <stdlb.h> #defne STK_SIZE 00 typedef nt element; /* element 를 nt 타입으로정의 */ element stack[stk_size]; vod push(nt *top, element tem) { f(*top >= STK_SIZE - ) { /* 스택이만원인경우 */ prntf(" Stack s full\n"); return;} stack[++(*top)] = tem;} /* top 은 top+ 로 */ 스택의응용분야 시스템스택, 서브루틴호출 인터럽트처리, 컴파일러 수식의계산 순환 큐의응용분야 작업스케줄링 버퍼관리 스택과큐의응용분야 배열을이용한스택의구현 () element pop(nt *top) { f (*top == -){ /* 스택이공백인경우 */ prntf("stack s empty\n"); ext();} else return stack[(*top)--]; } /* top 은 top- 로 */ 스택의응용분야 () 시스템스택 프로그램간의호출과복귀에따른실행순서관리 항상스택의톱에는현재실행되는함수의활성화레코드존재 element delete(nt *top) { f (*top == -){ /* 스택이공백인경우 */ prntf("stack s empty\n"); ext();} else return stack[(*top)--]; } /* top 은 top- 로 */ p : man() f () 호출 α: end f () f () f () 호출 β: end end 스택 β α 배열을이용한스택의구현 (3) nt sempty(nt *top) { f (*top = = -) return ; /* 공백이면, 공백이아니면 0 */ else return 0;} element peek(nt top) { f (top == -) { /* 스택이공백인경우 */ prntf("stack s empty\n"); ext();} else return stack[top]; } 수식의표현 수식의표기법 중위표기 : + 전위표기 : + 후위표기 :

9 스택을이용한수식계산 () 수식의표기법 : +*-/E 중위표기 : +*-/E 전위표기 : -+*/E 후위표기 : *+E/- 스택을이용한후위표기식의계산 후위표기식 *+E/- T +E/- T E/- T T - T 4 T 연산 * T +T T 3 /E T 4 T T 3 스택을이용한수식계산 (4) 후위표기식수동변환방법. 중위표기식을완전하게괄호로묶는다.. 각연산자를묶고있는괄호의오른쪽괄호로연산자를이동시킨다. 3. 괄호를모두제거한다. (( + ( * ))-( / E)) *+E/ 스택을이용한수식계산 () 공백스택 T T * T +T T *+E/- *+E/- *+E/- *+E/- *+E/- *+E/- 큐의표현 자료의삽입과삭제가서로다른끝에서이루어짐 선입선출 (FIFO) 에서 Q[n] 을이용한순차표현 n : 큐에저장할수있는최대원소수 초기화 : front = rear = - ( 공백큐 ) 공백큐 : front = rear, 만원 : rear = n- E 계산완료 T T 3 3 /E T 4 T -T 3 T 4 : 결과 T T T T 4 T 4T 4 *+E/- *+E/- *+E/- *+E/- *+E/- 배열 Q - f r 0... n 스택을이용한수식계산 (3) 후위표기식계산 evalpostfx(exp) // 후기표기식의계산. 후위표기식의끝은 이라고가정 stack[n]; // 피연산자를저장하기위한스택 top -; whle (true) do { token gettoken(exp); // 식에서토큰을읽어옴 case { token = operand : push(stack, token); token = operator : { 토큰이연산자인경우 stack에서피연산자들을삭제하여계산을하고그결과를다시 stack에삽입 }; else : prnt(pop(stack)); // 토큰이 인경우 } } end evalpostfx() - 0 front rear - 0 front - 0 front 큐의자료삽입과삭제 rear - 0 front rear 삽입 (add) - 0 삭제 (delete) 3-0 rear front - 0 front front rear rear 3 rear

10 순차큐의문제 rear=n-인경우 만원이지만, 반드시 n개의원소가큐에있지는않음 큐의앞에서삭제로인해빈공간이생길수있음 빈공간을없애기위해앞쪽으로이동, front rear재설정 데크 (ouble Ended Queue) 리스트의처음과마지막원소에대해삽입, 삭제 삽입 삽입 삭제 삭제 left rght 시간, 연산의지연문제 순차큐 0... n- 삽입삭제 삽입삭제 스크롤 (scroll) 쉘프 (shelf) 삭제 삽입 원형큐 데크의삽입, 삭제예 n 개의원소를갖는배열 Q[n] 원형으로운영 mod(modulus) 연산자이용 rear (rear+) mod n : front (front+) mod n 처음상태, l=, r= a b rear = (+) mod = / 나머지 n- 원형큐 Q(5) Q(4) E Q(3) Q() Q(n-3) Q() Q(n-) Q(0) Q(n-)..... l 에 c 삽입, l=, r=3 r 에 d 삽입, l=, r=4 l 에 c 삭제, l=, r=4 c c a a a b b b d d 원형큐의삭제예제 f=0 r=0 초기상태 ( 공백큐상태 ) f=0 r=3 65,7,35의삽입 4 장연결리스트 7 f= r=3 65 의삭제 f= r=0 48,5 의삽입 ( 만원큐상태 )

11 노드구조와포인터 에서의포인터 () 비순차표현또는연결표현 원소의물리적순서가리스트의논리적순서와일치할필요없음 원소를저장할때이원소의다음원소에대한주소도함께저장해야함 노드 : < 원소, 주소 > 쌍의저장구조 노드 (node) 자료필드 : 리스트의원소, 즉자료값을저장하는곳 링크필드 : 다음노드의주소값을저장하는장소 ( 포인터 ) 노드의구조 : 포인터 다른어떤변수 (varable) 의주소 (address) 를그의값으로저장하는변수 언어에서는모든변수가주소를가지고있기때문에모든타입에대해서포인터타입이존재 포인터선언 데이터타입이름뒤나변수이름 ( 식별자 ) 앞에 * 를붙임 예 ) char 타입의변수와포인터선언 char c = k ; char *pc; /* 또는 char* pc; */ pc c pc = &c; K 6 64 연결리스트 () 각노드는자료필드 (data feld) 와다음노드의주소값을가지는링크필드 (lnk feld) 로구성되는자료구조 삽입 / 삭제시원소이동발생없음 종류 단순연결리스트 (lnked lst) 원형연결리스트 (crcular lnked lst) 이중연결리스트 (double lnked lst) 이중원형연결리스트 (double crcular lnked lst) 에서의포인터 () 값참조 포인터가지시하는주소의값 ( 내용 ) 을참조하기위해서는포인터역참조 (dereference) 를해야함 즉, 포인터 pc 에저장되어있는주소를참조해그주소를따라가서거기에저장되어있는내용 ( 값 ) 을검색 이역참조는포인터변수앞에 * 를붙여표현함 예 ) char c = k ; char *pc; /* 또는 char* pc; */ pc = &c; L eat fat hat mat vat - prntf ("c s %c\n", c); - prntf ("c s %c\n", *pc); 이두명령문은같은값을출력 6 65 연결리스트 () 구조체포인터타입 () 링크에주소값이저장 마지막노드링크는 을저장 연결리스트전체는포인터변수 L 로나타냄 공백리스트의경우 L 의값은 이됨 널포인터 노드의필드선택은점연산자를이용 L.data : L 이가리키는노드의 data 필드값, eat L.lnk.data : L 이가리키는노드의 lnk 값이가리키는노드의 data 값, fat L eat 004 fat 00 hat 0 mat 0 vat 자체참조구조 (self-referental structure) struct의멤버는같은타입의또다른 struct를지시하는포인터도될수있음 리스트의노드를정의하는데유용함 struct char_lst_node { char letter; struct char_lst_node *next; }; struct char_lst_node *p; p = p->next; 와같이포인터를순회시킴으로써, 이포인터 p 가가리키는노드에연결된다음노드접근 63 66

12 구조체포인터타입 () 에서의단순연결리스트 () typedef 키워드 typedef struct char_lst_node *lst_ponter; struct char_lst_node{ char letter; lst_ponter next; }; lst_ponter p = NULL; 포인터타입 lst_ponter 는아직정의되지않은 char_lst_node 라는 struct 타입을이용하여정의 포인터 p 는 NULL 값으로초기화 vod nsert(lst_ponter t, lst_ponter x) { lst_ponter ; 3 =(lst_ponter)malloc(szeof(lst_node)); 4 ->data=3305; 5 f (*t==null) { 6 7 } *t=; ->lnk=null;} else{->lnk=x->lnk; x->lnk=; } (a) t (c) X (d) 데이터링크 (b) t= 일때 포인터의할당과반환 메모리의동적할당 nt, *p; float f, *pf; p = (nt *)malloc(szeof(nt)); pf = (float *)malloc(szeof(float)); *p = 0; *pf = 3.4; prntf("an nteger = %d, a float = %f\n",*p, *pf); free(p); free(pf); p pf f 에서의단순연결리스트 (3) vod delete(lst_ponter x, lst_ponter y, lst_ponter t) { f (*y==null){ t=t->lnk; } 3 else{ y->lnk=x->lnk; } 4 free(x); 5 } y=0일때 t (a) 3305 x y=0일때 ( 삭제전 ) (c) x 3305 y= ( 삭제후 ) 반환 (b) y 가 이아닐때 y x 자유공간리스트 68 7 에서의단순연결리스트 () 에서의단순연결리스트 (4) typedef struct lst_node *lst_ponter; typedef struct lst_node{ 3 nt data; 4 lst_ponter lnk; }; vod create(lst_ponter t){ lst_ponter ; 5 =(lst_ponter)malloc(szeof(lst_node)); 6 *t=; ->data=3304; 7 =(lst_ponter)malloc(szeof(lst_node)); 8 t->lnk=; 9 ->lnk=null; ->data=3308; } (a) t (c) t (d) t (e) 데이터링크 t (b) 데이터링크 vod prnt(lst_ponter t){ lst_ponter p; 3 p=t; 4 whle(p){ 5 prntf("%d",p->data); 6 p=p->lnk; 7 } 8 } t p

13 자유공간리스트 () 연결리스트를이용한스택과큐 필요에따라요구한노드를할당할수있는자유메모리풀 자유공간관리를위해연결리스트구조를이용하기위해서는초기에사용할수있는메모리를연결리스트로만들어놓아야함 초기자유공간리스트 lnk Free... 노드할당요청이오면리스트앞에서부터공백노드를할당 스택 top 큐 front data lnk data lnk data lnk data lnk data lnk rear data 자유공간리스트 () 새로노드를할당하는함수 (getnode) getnode() f (Free = ) then underflow(); // 언더플로우처리루틴 newnode Free; Free Free.lnk; return newnode; end getnode() 노드를할당한뒤의자유공간리스트 원형연결리스트 () 마지막노드가다시첫번째노드를가리키는리스트 한노드에서다른어떤노드로도접근할수있음 리스트전체를가용공간리스트에반환할때리스트의길이에관계없이일정시간에반환할수있음 ` data lnk... data lnk data lnk Free... data lnk newnode 자유공간리스트 (3) 단순연결리스트노드삽입 & 삭제 삭제된노드를자유공간리스트에반환 returnnode(p) p.lnk Free; Free p; end returnnode() 삭제된노드 p 를자유공간리스트 Free 에반환 Free data p data lnk data lnk 찾아야할노드 P T 5 x (a) 삽입할때 X 찾아야할노드 T (b) 삭제할때 6 삽입할노드 5 x 6 x P 삭제할노드 78 3

14 이중연결리스트 () 다항식의리스트표현 한노드에서후속노드와선행노드를가리키는포인터를가지는리스트 p = RLINK(LLINK(p)) =LLINK(RLINK(p)) LLINK 데이터 RLINK LEFT RIGHT p 헤드노드를갖는이중연결원형리스트 LLINK 데이터 RLINK 헤드노드 p 각항을하나의노드로표현 각노드는계수 (coef) 와지수 (exp), 다음항을가리키는링크 (lnk) 필드로구성 다항식노드 : coef exp lnk 다항식 (x)=x 4 +x +6 과 (x)=6x 4-5x 3 +7x 을표현 coef exp lnk 이중연결리스트 () vod ddelete(lst_ponter x, lst_ponter L) L { f (x == L) { 3 no_more_nodes(); 3 5 return; } p x 3 x->llnk->rlnk=x->rlnk; L 4 x->rlnk->llnk=x->llnk; 5 free(x); X } p x 80 p L X 5 R q q X q 3 일반리스트 n 0 개의원소 e, e, e n 의유한순차 리스트의원소가원자일뿐아니라리스트도허용 리스트는 L=(e, e, e n ) 과같이표현 head(l) : n 인경우첫번째원소 e tal(l) : 첫번째원소를제외한나머지리스트 (e, e n ) 공백리스트에대해서는 head 와 tal 은정의되지않음 정의속에다시리스트를사용하고있기때문에순환적정의 노드구조 : tag data lnk 83 이중연결리스트 (3) vod dnsert(lst_ponter p, lst_ponter x) { p->llnk=x; 3 p->rlnk=x->rlnk; 4 x->rlnk->llnk=p; 5 x->rlnk=p; } =( a, (b,c) ) =(,, ( ) ) =((a, (b,c)), (a, (b,c)), ()) =( a, ) =(a,(a,(a, ) =( ) 일반리스트의예 0 a tag data lnk 0 b 0 c x p x 0 0 a =()

15 트리 (3) 5 장트리 트리용어 () 레벨 (level) : 루트의레벨은, 나머지는부모노드레벨 ( 루트의레벨을 로정의하기도함 ) 높이 (heght), 깊이 (depth) : 최대레벨값 레벨 E F G 레벨 레벨 3 H I N 레벨 4 88 비선형구조의자료구조 트리 () 자료사이의계층적관계를구조화 가계도 : 자신, 부모, 형제, 조부모, 선조, 후손 기억장소의할당및자료저장과탐색에이용 정렬, 검색에많이응용 이진트리 () 모든노드가정확하게두서브트리를가지고있는트리 왼쪽서브트리와오른쪽서브트리를분명하게구별 이진트리자체가노드가없는공백이될수있음 정의 : 이진트리 (bnary tree: T) 노드의유한집합 공백이거나루트와두개의분리된이진트리인왼쪽서브트리와오른쪽서브트리로구성 (a) (b) 트리용어 () 트리 () 노드 (node) : 저장된정보항목, 에지 (edge, 계층관계 ) 항목으로구성 루트 : 트리의정점노드 차수 (degree) : 노드의부트리의개수트리의차수는트리에속한노드의최대차수 리프 (leaf) : 단말노드, 차수가 0 인노드 내부노드 (nternal node) : 비단말노드 부모노드 (parent) : 부트리의루트에대하여루트는부모노드 자식노드 (chld) : 부트리의루트는루트의자식노드 형제노드 (brother, sblng) : 부모가같은자식노드들 선조 (ancestor) : 자신부터루트까지의노드집합 후손 (descendants) : 자신과, 부트리의모든노드집합 완전이진트리 (complete bnary tree) 높이가 k 일때, k- 레벨까지는노드가차있고, k 레벨에서는노드가왼쪽부터차있는트리 노드수 : k- - < n <= k - H I 이진트리 () E F G

16 포화이진트리 (full bnary tree) 각레벨에노드가모두차있는이진트리 포화이진트리 완전이진트리 노드수 : k - 개 이진트리 (3) a 3 b c d e f g 이진트리의표현 ( 연결리스트 ) LHIL T RHIL T LHIL RHIL root root 9 94 이진트리정리 이진트리의 level 에서최대노드수는 - ( ) root node 의 level 이 0 일때 : ( 0) 깊이가 k 인이진트리의최대노드수는 k - (k ) root 의 depth 가 0 일때 : k+ - (k 0). (= 0 ) (= ) 이진트리에서각노드를차례로방문순회방법 :LR,LR,LR,RL,RL,RL 중위순회 :LR 후위순회 :LR 전위순회 :LR 이진트리순회 () E F G 3(= ) 9 이진트리의표현 ( 배열 ) 이진트리의순회 () H -L-R 전위순회 T E F G I H L--R 중위순회 E F G I T H E F G I L-R- 후위순회 T

17 이진트리순회 (3) 스레드이진트리 () 중위순회 (T T 0 T ) (T T 0 T ) (T T 0 T ) T T 0 + T T 0 / T 0 * T T T T T ** 0 E (T T 0 T ) T T E F E F I H I I H I 중위순회 히프추상데이터타입 vod INORER(tree_ponter T){ f (T){ INORER(T->LHIL); prntf("%d", T->T); INORER(T->RHIL); } } vod IN() IN() P() IN(3) vod IN(3) IN(0) p() IN(0) vod IN() IN(4) p() IN(0) vod IN(4) IN(0) p() IN(0) 98 최대트리 (max tree) 는각노드의키값이 ( 자식이있다면 ) 그자식의키값보다작지않은트리이다. 최대히프 (max heap) 는최대트리인완전이진트리이다. 최소트리 (mn tree) 는각노드의키값이 ( 자식이있다면 ) 자식의키값보다크지않은트리이다. 최소히프 (mn heap) 는최소트리이면서완전이진트리이다. 0 스레드이진트리 () 최대히프의예 널링크들을낭비하지않고스레드 (thread) 를저장해활용 스레드 : 트리의어떤다른노드에대한포인터 트리를순회하는정보로활용 스레드이진트리생성방법 노드 p 의 rght 가널 : 중위순회에서중위후속자에대한포인터저장 노드 p 의 left 가널 : 중위순회에서중위선행자에대한포인터저장

18 최소히프의예 최대히프에서의삽입과정 (a) 삽입전의히프 (b) 새로운노드 7의초기위치 (c) 히프에 차수행 (d) 완성된히프 04 8