[자료구조] 7. 트리

7장. 트리 1. 트리의 개념 트리로 나타낸 트리 계층형 구조 데이터 표현에 적합한 자료구조 ex1) Tree -> Binary Tree / m-way Tree ex2) Nodes : 모차르트, 바흐, 베토벤, 세잔, 피카소, 아인슈타인, 뉴턴 Root : 위인 -> 예술가 / 학자 2. 용어 노드 (정점) 트리를 구성하는 항목 서브트리 특정 노드 하위로 파생되는 새로운 트리 루트노드 부모 노드를 가지지 않는 최상위 노드 리프노드 자식 노드를 가지지 않는 최하위 노드 진입 차수 노드로 들어오는 선의 개수 루트노드는 0이며 나머지 노드는 무조건 1이다. 2이상인 경우 그래프가 된다. 진출 차수 노드로 부터 나가는 선의 개수 노드의 차수를 결정한다. (degree of a node) 최대 차수가 트리 전체의..

• format_list_bulleted 노트/자료구조
• · 2022. 1. 27.
• textsms

[자료구조] 6. 연결리스트의 응용

연결 리스트의 변형 연결 리스트 종류 단일 연결 리스트 이중 연결 리스트 단일/이중 원형 연결 리스트 단일 연결 리스트 헤드부터 순차적으로 검색 이중 연결 리스트 특정 노드의 선행 노드에 접근하기 용이하도록 개선 원형 연결 리스트 꼬리 노드의 링크가 항상 Null 인 것을 개선하여 처음으로 돌아갈 수 있도록 개선 (검색성능 향상) 이중 원형 연결 리스트 이중 연결 리스트와 원형 연결 리스트의 장점을 합친 것으로, 연결리스트 내에서 선행 노드와 후행 노드의 접근이 자유로우며 첫 노드와 마지막 노드를 연결해두어 순환구조로 인덱싱을 한층 더 자유롭게 만든 자료구조 이다.

• format_list_bulleted 노트/자료구조
• · 2022. 1. 27.
• textsms

[자료구조] 5. 연결 리스트

5장. 연결 리스트 EX) C언어 프로그램 실행 중 구조체 메모리 할당 int a, *p_a; float b, *p_b; p_a = (int*)malloc(sizeof(int)); p_b = (float*)malloc(sizeof(float)); *p_a = 10; 1. 리스트의 개념 ❗ **논리적인 순서에 의해 결정된 원소들의 나열 → 물리적인 순서와 무관하게 논리적인 순서만 유지** 2. 배열을 이용한 리스트 구현 배열을 이용하여 리스트를 구현한 자료형 배열로 구성한 리스트 중간 인덱스에 자료가 삽입되는 경우 배열을 이용하여 리스트를 구현하면, 논리적인 순서와 함께 물리적인 순서 또한 일정하게 유지 된다. 이로 인해 중간에 데이터를 삽입이나 삭제하는 경우가 생긴다면 뒤의 인덱스 자료형들의 물리적 공간..

• format_list_bulleted 노트/자료구조
• · 2022. 1. 6.
• textsms

[자료구조] 4. 큐

4강. 큐 1. 큐의 개념 ⭐ **가장 먼저 대기 줄에 들어간 작업이 가장 처음에 처리되는 작업 (First-In-First-Out) 한 쪽에서 삭제, 다른 한 쪽에서 삽입 연산이 발생한다.** queue 의 자료 입출력 2. 큐의 추상 자료형 Queue Create_q(maxQueueSize) 큐의 크기가 maxStackSize인 빈 큐를 생성하고 반환한다. Boolean IsFull_q(queue, maxQueueSize) 큐에 저장되어있 자료의 갯수를 파악하여 저장공간이 남아 있는지 확인한다. Queue Add_q(queue, item) 큐에 저장공간이 있다면 rear 영역에 item을 삽입한다. Boolean IsEmpty_q(queue) 큐의 front 포인터와 rear 포인터가 같은 주소를 가..

• format_list_bulleted 노트/자료구조
• · 2022. 1. 6.
• textsms

[자료구조] 3. 스택

3강. 스택 1. 스택의 개념 💡 객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 추상 자료형 가장 나중에 들어온 자료가 가장 먼저 나가는 형태(LIFO, 후입선출) TOP : 스택에서 가장 최근에 삽입 된 자료의 메모리 주소를 지칭 push : 스택에 자료 하나를 삽입하는 함수. 스택의 저장공간이 충분한지 확인해야 한다. pop : 스택의 최상단 자료형을 반환(제거) 하는 함수. 스택에 데이터가 존재하는지 확인해야 한다. 2. 스택의 추상 자료형 Stack CreateS(maxStackSize) 스택의 크기가 maxStackSize인 빈 스택을 생성하고 반환한다. Boolean IsFull(stack, maxStackSize) 스택이 가득 찼는지 여부를 확인하여 반환한다. Stack Push(s..

• format_list_bulleted 노트/자료구조
• · 2022. 1. 6.
• textsms

[자료구조] 2. 배열

1. 배열의 정의 💡 배열 : 일정한 차례와 간격에 따라 벌여 놓은 자료형 1.1 배열의 정의 인덱스와 원소값(index, value) 의 쌍으로 구성된 집합으로 정의된 각 인덱스는 그 인덱스와 관련된 값을 가진다. 1.2 배열의 특성 원소들이 모두 같은 자료형, 즉 동질의 값과 기억 공간의 크기가 같다. 배열의 각 원소의 물리적인 위치(메모리 주소)의 순서가 배열의 인덱스 순서(논리적 순서) 와 일치한다. 배열의 인덱스 값을 이용해서 배열의 원소값에 직접 접근(direct access) 한다. → 배열의 인덱스 번호는 사람(개발자)가 이해할 수 있도록 정의한 (추상화) 값이다. 배열에서 인덱스 번호를 알고 있을 때 원소를 찾아내는 방법의 시간복잡도를 O(1)로 두는 이유에 대해 궁금했었는데, 이는 배열..

• format_list_bulleted 노트/자료구조
• · 2021. 12. 20.
• textsms