본문 바로가기

알고리즘

[알고리즘] 기본 추상자료형(7) - 설명(트리ADT, 이진트리ADT) 트리ADT는 어떤 단체의 조직구성이나 동식물의 분류체계처럼 맨 위의 대표적 체계(트리)로 시작하여 아래 방향의 가지치기로 표현되는 계층구조를 트리(tree)라고 한다 트리의 용어 루트 - 트리의 맨 위의 부모가 없는 노드 내부노드 - 적어도 한개의 자식을 가진 노드 외부노드 - 자식이 없는 노드 형제 - 같은 부모를 가진 노드 부트리 - 더 작은 트리 경로 - 조상 또는 자손을 따라 이어진 길을 말한다 EX) ABE / ABFK 등등 경로길이 - 경로내 간선의 수를 말한다. EX) ABE(2) / ABFK(3) 깊이 - 루트로부터 그 노드에 이르는 유일한 경로의 길이 EX) J의 깊이 - 3 높이 - 그 노드로부터 외부노드에 이르는 가장 긴 경로의 길이 EX) B의 높이 - 2 트리ADT메소드 1) 일반..
[알고리즘] 기본 추상자료형(6) - 예제(큐ADT/데크ADT) [문제1] 배열로 만들어진 원형큐에서 삽입, 삭제하는 프로그램 - front, rear, 배열의 초기값은 0 - front == rear이면 공백상태, front + 1 == rear이면 포화상태 - overflow의 경우 배열에 있는 모든값들을 출력 후 프로그램종료 / underflow의 경우 프로그램종료 - I value : 원형큐에 value를 삽입 - D : 원형큐에 원소삭제, 값0으로 바꿈 - P : 배열에 있는 모든 값을 출력 입력예시 출력예시6 10 I 10 I 20 P I 30 I 40 D P I 50 I 60 I 70 0 10 20 0 0 0 0 0 20 30 40 0 overflow 60 0 20 30 40 50 #include #include int *queue, queueSize, ..
[알고리즘] 기본 추상자료형(5) - 예제(스택ADT) [문제1] 스택을 이용하여 중위수식을 후위수식으로 변환하는 프로그램 - 피연산자는 영문자로 나타내고, 수식의 최대길이는 100 입력토큰연산자 우선순위 ! +(부호) -(부호) 단항연산자 6 * / 곱셈, 나눗셈 5 + - 덧셈, 뺄셈 4 > F) AB*C+DE+F*+ AB/C-DE*+FG*- AB&&C||EF>!|| #include #include #include int stackSize, top, sign; void push(char *stack, char value) { stack[++(top)] = value; } char pop(char *stack) { return stack[(top)--]; } int operand(char *inArray, int i){ if ((top != i) && (i..
[알고리즘] 기본 추상자료형(4) - 예제(스택ADT) [문제1] 스택ADT를 배열로 구현하고 테스트하는 프로그램 - push(stack, value) : stack의 top에 데이터를 추가한다 - pop(stack) : stack의 top에 있는 데이터를 반환하고 stack에서 제거한다 - peek(stack) : stack의 top에 있는 데이터를 화면에 출력한다 - duplicate(stack) : stack의 top에 있는 데이터를 pop해서 두번 push한다 - upRotate(stack, number) : stack의 맨 위의 number개의 데이터를 회전시킨다. 예를들어 n이 5이면 top에서 1,2,3,4,5로 저장되어 있다면 2,3,4,5,1로 변경 - downRotate(stack, number) : stack의 맨 위의 number개의 데..
[알고리즘] 기본 추상자료형(3) - 설명(스택ADT, 큐ADT) 스택ADT는 후입선출(마지막에 들어간것이 가장 먼저 나온다)-LIFO(Last-In First-Out)순서를 따르는 데이터구조로, top이라 불리는 위치에서 삽입과 삭제가 행해진다 스택ADT메소드 1) 주요메소드 push(e) - 원소e를 삽입 element pop() - 가장 나중에 삽입된 원소를 삭제하여 반환 2) 보조메소드 element top() - 가장 나중에 삽입된 원소를 삭제하지 않고 반환 integer size() - 스택에 저장된 원소의 수를 반환 boolean isEmpty() - 스택이 비어 있는지 여부를 반환 iterator elements() - 스택 원소 전체를 반환 3) 예외메소드 emptyStackException() - 비어 있는 스택에 대해 pop이나 top을 시도할 경우..
[알고리즘] 기본 추상자료형(2) - 예제(집합ADT) [문제1] 집합A와 B를 입력받고, A가 B의 부분집합인지를 검사하는 프로그램(단일연결리스트) - 오름차순 양의 정수로 저장 및 출력 - A ⊂ B이면 0을 출력, A ⊄ B이면 집합B에 속하지 않은 집합 A의 가장 작은 원소를 출력 입력예시 출력예시 3 5 10 15 4 5 20 25 30 10 입력예시 출력예시0 3 5 10 15 0 입력예시 출력예시 3 5 10 15 0 5 #include #include struct node { int number; struct node *next; }; void addSet(struct node *set, int number){ struct node *newElement = (struct node*)malloc(sizeof(struct node)); newEle..
[알고리즘] 기본 추상자료형(1) - 설명(리스트ADT, 집합ADT) 추상자료형이란 데이터구조의 추상형으로서, 인간이 데이터를 다루는 관점에서 데이터구조를 명세한 것이다 종류로는 리스트ADT, 집합ADT, 큐ADT, 트리ADT등이 있다 기억장소 사용량은 모두 O(n)이다 추상자료형 가운데 가장 먼저 알아야할 것은 리스트ADT로, 리스트ADT는 연속적인 임의개체들을 모델링한다 리스트ADT 메소드 1) 일반 메소드 integer size() - 리스트의 크기, 즉 원소 수를 반환 boolean isEmpty() - 리스트가 비어 있는지 여부를 반환 iterator elements() - 원소 전체를 반환 2) 접근 메소드 element get(r) - 순위r에 저장된 원소를 반환 3) 갱신 메소드 element set(r, e) - 순위r에 저장된 원소를 e로 대체 add(r..
[알고리즘] 기초 데이터구조(2) - 예제 [문제1] 이중연결리스트 + 헤더 및 트레일러 노드 프로그램 - addList: position과 element를 받아 list를 추가한다 - deletList: position을 받아 list에서 삭제한다 - getElement: position을 받아 element를 RETURN한다 - printList: list의 모든 element를 순서대로 출력한다 - freeList: list의 메모리할당을 해제한다 입력예시 출력예시9 A 1 A A 2 B A 3 C A 3 D P D 2 P A 1 E P G 4 ABDC ADC EADC invalid position #include #include struct node { char element; struct node *next; struct node *pr..

티스토리툴바