자료구조론 (4) 썸네일형 리스트형 [소프트웨어공학] 원형 큐 원형 큐 (circular queue) 1) 특징 - 초기 자료가 없을 때, front = rear = 0 또는 -1; - 입력 : rear 증가 자료 입력 - 출력 : front 증가 자료 출력 - mod 연산을 통해 front와 rear 값 계산 2) 공백상태 포화상태 구별 i) flag 변수 사용 flag = 0 //빈상태 flag = 1 //포화상태 ii) 기억장소 하나 포기 포화상태라도 front =/= rear임! 공백상태 : front = rear 포화상태 : front == rear+1 3) 알고리즘 //2019 국가 7급 자료구조론 #define MAX_QUEUE_SIZE 10 //크기가 10인 큐 int queue[MAX_QUEUE_SIZE]; int front = rear = -1; .. [자료구조론] C 언어 포인터 기호 (*과 &) 포인터를 나타내는 연산자 *와 &가 어떤 의미인지 헷갈려서 찾아 보았다. 포인터란? 데이터의 주소를 가지는 변수 & : 변수의 주소를 저장하도록 하는 연산자 int main(void) { int i = 1; char c = 2; printf("i의 주소: %u\n", &i); // i의 주소: 2205393044 printf("c의 주소: %u\n", &c); // c의 주소: 2205393043 return 0; } 위 코드에서 &는 주소값 반환의 역할을 한다. * : 포인터가 가르치는 값(내용물)을 반환하는 연산자 int main(void) { int i = 1; int *p = &i; //포인터 변수인 p는 i를 가르킴 (주소값을 가짐) printf("%d\n", *p); // 1 *p = 2; /.. [자료구조론] 탐색구조 - AVL 트리 균형트리 O(log n) : AVL, 2.3트리, 래드 블랙 트리, B트리, B+트리 비균형트리 : 이진탐색, m원탐색 - Andelson-Velskii와 Landis가 제안 특징 1) 이진탐색 2) BF(balance factor) -1, 0, 1 - 서브트리 좌 우 높이 차이 cf) 임계노드 : BF가 -1, 1인 노드 회전 종류 [2012년 국가 7급] 12 11 10 5 3 7 6 1 13 2 4 AVL 생성시 옳지 않은 것은? ① AVL트리에서 7을 검색하기 위해서는 4번의 비교가 필요하다. ② AVL트리의 루트 값은 5이다. ③ 4가 삽입될 때, AVL 트리의 균형이 깨져서 재구성이 발생한다. ④ 6은 리프노드이다. 답 : 1번 -> 3번의 비교가 필요하다. [자료구조론] 정렬 정렬의 수행시간 수행시간 최악의 경우 수행시간 선택 정렬 O(n^2) '' 거품 정렬 O(n^2) '' 삽입 정렬 O(n^2) '' 셀 정렬 O(n^2) '' 퀵 정렬 O(nlogn) O(n^2) 합병 정렬 O(nlogn) '' 힙 정렬 O(nlogn) '' 기수 정렬 O(k(n+q) '' ※ 퀵정렬의 경우 이미 정렬되어 있을 때 최악의 수행시간을 가진다. ※ 선택정렬에서 최악의 자료이동횟수는 n회 안정 배열 - 같은 값을 가지는 배열 정렬시, 그 순서가 같은거 - 거품정렬, 삽입정렬, 합병정렬, 기수정렬 제자리정렬 - 추가 메모리를 거의 사용하지 않는 것 - 제자리정렬이 아닌 것 : 합병정렬 , 기수정렬 정렬의 특징 특징 선택 정렬 최댓값 또는 최솟값을 선택한 후 맨 앞 또는 맨 뒤로 자리 변경 거품 .. 이전 1 다음
