1. 트리의 운행 - 트리의 각 노드를 한번씩만 순회해야함 1.1 이진트리 운행법 1 ) 전위 운행법 (PreOrder Traverse)1. 루트2. 왼쪽 서브트리를 전위 순회로 순회3. 오른쪽 서브트리를 전위 순회로 순회 2 ) 중위 운행법 (InOrder Traverse)1. 왼쪽 서브트리를 중위 순회로 순회2. 루트3. 오른쪽 서브트리를 중위 순회로 순회 3 ) 후위 운행법 (PostOrder Traverse)1. 왼쪽 서브트리를 후위 순회로 순회2. 오른쪽 서브트리르 후위 순회로 순회3. 루트 1.2 스레드 이진트리널 링크를 이용한 이진트리 1.3 트리의 경로길이 E(T)외부노드 : 모든 Internal 디그리를 2로함I(T)내부노드 : 일반적인 노드까지의 길이 E(T) = I(T) + 2*n
1. 2WAY 합병정렬기억공간 : S = 2N수행시간 : O(nlog2n) 2개씩 묶어서 선택정렬을 호출 2. 기수정렬(Radix) = 버킷정렬기수 : K값이 취할 수 있는 값의 개수(10진수는 0-9로 10개, 8진수는 0-8은 9개)큐의 길이 : n개, n은 최대크기 1. 기수의 개수만큼 버킷을 생성2. LSK(일의자리부터) MSK(십의자리부터) 선택3. 정렬 [ LSK 정렬 ]19, 01, 26, 43, 92, 87, 21, 38, 11, 73 [1단계]01 - 01, 21, 112 - 923 - 43, 73456 - 267 - 878 - 389 - 19 01, 21, 11, 92, 43, 73, 26, 87, 38, 19 [2단계]0 - 011 - 11, 192 - 21, 263 - 384 - 4..
1. 선택정렬 키 값의 크기 순으로 리스트에서 제일 작은 원소를 찾아 첫번째 위치에 있는 원소와 교환하고 다음에는 두번째로 작은 원소를 찾아 두번째 위치에 있는 원소와 교환한다. 이런 방법으로 반복적으로 수행하는 방식 5 2 8 3 1min 비교회수 1 2 8 3 55번방 4 1 2 8 3 52번방 3 1 2 3 8 54번방 2 1 2 3 5 85번방 1 기억공간 : s = n수행시간 : O(n^2) 5 2 8 3 1 비교회수 1 5 8 3 2 4 1 2 8 5 3 3 1 2 3 8 5 2 1 2 3 5 8 1 2. 셸정렬 주어진 리스트를 적당한 매개변수 값만큼 서로 떨어진 레코드들과 비교하여 교환하는 과정을 매개변수 값을 바꾸어가며 반복한다. 매개변수 h = (1, 3, 5)초기상태 h = 5 3. 퀵..
- 정렬 1. 내부정렬 정렬할 대상의 크기가 크지 않아 주 기억 장치에서 정렬이 이루어지는 방식 삽입법 : 삽입(Insertion), 셀(Shell)교환법 : 버블(Bubble), 퀵(Quick), 선택(Selection)선택법 : 히프(Heap)합병법 : 2-way(2-way merge) 합병분배법 : 기수(radix) 1.1 삽입 정렬(Internal Sort)Data의 개수 -1개의 횟수를 거친다.처음 데이터는 정렬되어있는 것으로 가정한다.TEMP 앞방의 번호와 비교했을 때, TEMP가 더 크면 STOP 이외의 경우는 자리를 뒤로 이동하고 바꾼 자리에서 또 앞의 것과 비교한다. 비교가 끝났을 때 방에 TEMP값을 삽입한다. 끝나는 경우 : TEMP와 앞방보다 큰 경우 5 6 4 9 7 temp 비교..
1. 배열을 이용한 STACKPUSH (stack, top, item, max)// stack -> 배열, top -> 스택의 맨 위, item -> 집어넣을 값, max -> 최대 스택if(top == max){exit 0}stack[top++] = item POP (stack, top, item)if(top == 0){exit 0}item = stack[top--] 2. 단순연결리스트를 이용한 STACKPUSH(top, item)CALL GETNODE(I)I->link=toptop=I POP(top, item)tmp = topitem = tmp->datatop = tmp->linkCALL RET(tmp) 3. PREFIX, POSTFIX, INFIXinfix : 연산자 중심으로 양쪽에 피연산자가 위치..
1. 원형 연결리스트 원형리스트에서의 삽입은 총 3가지로 구분할 수 있다.1. Head의 값이 NULL 일때 (즉, 아무 리스트도 존재하지 않을 때)2. Head의 앞에 값을 넣어야할 때3. 중간에 삽입 if(head == NULL)I->link = Ihead = IelseI->link=X->linkX->link=Iif(X->link == head)head=I if(X->link == X)head = NULLelse if(Y->link == head)Y->link=X->linkhead = X->linkelseY->link = X->link
1. 프로그램의 동작 1. 변수 (자료형, 범위, 할당)2. 제어문3. 부 프로그램 호출 위와같은 세가지로 프로그램이 동작하게 된다. 2. 자료구조 1. 선형구조 - 선형리스트(배열), 연결리스트(단순, 원형, 이중, 이중원형), 스택, 큐, 데크2. 비선형 구조 - 트리, 그래프3. 정렬4. 검색 3. 리스트(LIST)3.1 선형 리스트- 장점가장 간단한 구조기억 메모리 밀도가 1 (제일 높음)검색 효율이 좋다. - 단점삽입 삭제의 단점(중간에 삽입하려면 그 뒤의 모든것을 한칸씩 뒤로 미루어야하기 때문)낭비가 심함 3.2 단순연결 리스트한 노드가 데이터와, 링크 부분으로 구성되어있다. 시작과 끝이있고, 한 방향으로 진행하는것이 단순연결 리스트라고한다. 시작을 Head Pointer, 끝을 Tail Po..