전체 글
-
[자료구조] 10강 트리, 이진트리, 순회, 응용, 스레드 이진트리, 이진 변환프로그래밍/자료구조 2014. 4. 22. 05:27
* 이진 트리 이진 트리는 모든 노드가 정확하게 두 서브 트리를 가지고 있는 트리로 왼쪽 서브 트리와 오른쪽 서브 트리를 분명하게 구별할 수 있는 트리이다.종류에는 완전이진트리, 포화이진트리, 편향이진트리 등이 있다.이진트리의 주요 성질은 레벨 I의 최대 노드 수는 2i+1개 이고 높이가 h인 이진 트리의 최대 노드 수는 2h+1-1개이다. 완전 이진 트리는 높이가 h이고 노드 수가 n인 이진 트리에서 노드의 레벨 순서 번호들의 각 위치가 포화 이진 트리 번호 1에서 n까지 모두 일치하는 트리포화 이진 트리는 높이가 h이고 노드 수가 2h+1-1인 이진 트리로 트리의 높이에 모든 자식 노드들이 채워진 트리를 의미편향 이진 트리는 루트 노드를 기준으로 자식 노드가 한쪽 방향에만 존재하는 트리 * 이진 트리..
-
[자료구조] 9강 트리프로그래밍/자료구조 2014. 4. 22. 04:52
정의- 그래프 중에서 사이클을 포함하지 않는 연결 그래프로서의 임의의 노드에서 다른 노드로의 경로가 하나 밖에 없는 것을 트리라한다.트리는 계층적인 자료구조로 노드와 각 노드를 연결하는 간선들로 구성노드 중에서 단 하나의 루트 노드가 존재하고 루트 노드에서 다른 하위노드들이 간선들로 연결된 비선형 구조의 계층 구조트리의 종류에는 이진트리, 전 이진 트리, 포화 이진 트리, 사향 트리들이 있다.트리의 응용 분야는 계층적인 조직, 디택토리 구조, 인공지능에서 의사결정 구조등을 표현하는 결정 트리를 표현하는데 사용된다. 2. 용어노드와 차수 : 밑으로 나뉘는 개수 (한 노드가 가지고 있는 서브 트리의 수)단말 노드와 비단말 노드 : 단말 노드는 차수가 0인 노드를 말한다., 리프,노드 또는 터미널 노드라고도 ..
-
[자료구조] 8강 동적 연결된 스택과 큐~ 연결리스트프로그래밍/자료구조 2014. 4. 22. 04:51
동적 연결된 스택과 큐 순차 표현방법은 스택이나 큐가 하나만 있을 때는 효율적이나 여러 개의 스택이나 큐가 동시에 있을 때 이들을 순차적으로 표현할 효율적인 방법이 X , 이 경우에는 연결 리스ㅡ로 표현을 하여 스택은 top pointer로 첫 번 째 노드를 가리키게 하고, 큐의 경우에는 첫 번째와 마지막 노드를 front와 rear pointer가 가리킴으로써 삽입/삭제가 가능하도록 할 수 있다. 비사용 기억 공간 1. 순차 가용 공간에서의 노드 획득2. 초기 가용 공간에서의 연결 리스트 생성3. 연결 리스트 가용 공간에서의 노드 획득4. 연결 리스트로 된 가용 공간에 삭제 노드의 반환 연결 리스트의 응용 1. 다항식의 단순 연결 리스트 표현2. 다항식의 덧셈3. 단순 연결 리스트로 표현된 다항식의 노..
-
[자료구조] 7강 1-2절 연결리스트의 필요성 ~ 단순 연결 리스트프로그래밍/자료구조 2014. 4. 22. 04:50
연결 리스트의 필요성 순서 리스트는 배열을 이용하여 구현 -> 메모리 사용 측면에서의 비효율적인 문제점이 나타난다.순서리스트에서 삽입 연산이나 삭제 연산 후에 연속적인 물리 주소를 유지하기 위해서 원소들을 이동시키는 추가적인 작업과 시간이 소요되는 점이 가장 큰 부담-> 따라서 순서리스트에서 나타나는 문제점을 개선할 자료표현방법이 필요 순서리스트에서 원소의 삽입과 삭제시 빈번한 자리이동으로 복잡도가 증가하고 부담이 증가.이미 사용중인 크기를 변경하고자 하는 경우에는 연속적인 공간의 여유가 있는 경우에서는 문제가 되지 않지만 사용 중인 공간 이후에 여유 공간이 부족하면 기억공간에서 확장할 크기를 포함하는 기억 공간을 다시 할당 받아야하는 문제가 발생한다.연속적인 자료에 대한 추가,삭제가 빈번하다면 순서 리..
-
[자료구조] 6강 3장 스택과 큐 - 4절 스택의 응용프로그래밍/자료구조 2014. 4. 17. 19:03
6강 3장 스택과 큐 - 4절 스택의 응용 *연산자의 우선순위연산자를 괄호를 묶을 경우 우선순위가 달라진다.연산자 우선순위에 따라 연산하는 과정은 스택을 이용하여 표기하기도 함 *수식의 표기법전위 표기식 : 연산자를 피연산자의 앞에 표기하는 방법예: +AB중위 표기식 : 연산자를 피연산자의 가운데에 표기하는 방법예: A+B후위 표기식 : 연산자를 피연산자의 뒤에 표기하는 방법예: AB+ *수식의 표기법중위 표기식 표현A/B+C-D*E전위 표기식 표현-+/ABC*DE후위 표기식 표현AB/C+DE*- *중위 표기를 후위 표기로 변환스택의 응용 분야 : 중위 표기를 후위 표기로 변환하기 위한 용도수식의 연산자에 대해서 우선순위에 따라 괄호를 표현각 연산자를 그에 대응하는 오른쪽 괄호 뒤로 이동괄호를 제거 *다..
-
[자료구조] 5강 3장 스택과 큐 - 2절 큐프로그래밍/자료구조 2014. 4. 17. 17:39
5강 3장 스택과 큐 - 2절 큐 *큐의 정의리스트의 한쪽 끝에서 원소를 삽입, 다른 한쪽 끝에서는 원소의 삭제가 일어나는 구조가장 먼저 삽입된 원소가 가장 먼저 삭제된다고 해서 선입선출(FIFO : First In First Out) 구조 *데크리스트의 양쪽에서 삽입/삭제스택과 큐를 혼합한 구조데크의 종류에는 입력 제한 데크(스크롤), 출력 제한 데크(셀프)가 있다. *요점정리큐는 FIFO 선입선출큐의 삽입 및 삭제 과정 – Front pointer, Rear pointer선형 큐의 문제점을 보완하기 위한 원형큐큐의 적용 분야들 – 작업 스케줄링리스트의 양쪽에서 입출력이 가능한 데크 (입력제한, 출력제한 데크) 순서 있는 리스트- 삽입 연산은 한쪽 끝에서일어난다(rear라고 부른다)-삭제 연산은 삽입의..
-
[자료구조] 4강 3장 스택과 큐 - 1절 스택프로그래밍/자료구조 2014. 4. 17. 16:33
3장 스택과 큐 - 1절 스택 * 스택의 정의스택 : 선형 자료 구조의 한 종류비선형 구조 : 트리, 그래프선형 구조 : 스택, 리스트, 배열 (각각의 원소들이 순서를 가지고 있다)선형 자료 구조의 한 종류원소의 삽입과 삭제가 리스트의 한쪽 끝에서만 이루어지는 구조가장 마지막에 삽입된 원소가 가장 마지막에 삭제되는 구조로서 후입선출(LIFO: Last In First Out)구조삽입(push) : 스택에 원소를 삽입하는 과정삭제(pop) : 스택에서 원소를 꺼내오는 과정top pointer :주로를 가리키는 포인터 값 * 시스템 스택프로그램에서 호출과 복귀에 따른 수행 순서를 관리하기 위한 스택함수 호출이 발생하면 스택 프레임에 여러 정보들을 저장하여 시스템 스택에 삽입호출한 함수 수행에 필요한 지역 변..
-
[자료구조] 3강 2장 배열 - 1절 개요프로그래밍/자료구조 2014. 4. 17. 16:31
자료구조 2장 배열 - 1절 개요 * 배열이란?- 같은 자료형을 가진 원소가 순서를 가지고 만들어진 집합- 배열 원소들은 인덱스(0부터 시작한다) 에 의해 참조- 배열의 인덱스는 배열 원소의 순서를 의미 * 배열을 사용하는 경우 이점- 많은 요소들에 각각의 변수명을 생성하지 않으므로 메모리와 검색 효율이 좋음ex) int I,j,k,l,m,n; 변수선언을 해주었을 경우에는 변수 테이블을 따로 만들어 주어야한다. -> 메모리가 더 쓰인다. -> 배열로 선언해주는 것이 좋다. - 첨자 값만으로 액세스함으로써 배열의 원소값을 참조하는데 있어서 효율적인 표현이 가능ex) z=i+j+k+l+m; -> I,j,k,l,m 이 무엇인지 따로 int로 선언해 주어야한다. 자료형 배열 이름[배열의 크기] = {초깃값 리스..