cs/자료구조37 [Trees]20. Tree 목차 1. Tree(트리) 2. Tree Terminology 3. Tree ADT 1. Tree(트리) Tree(트리)는 hierachical structure(계층 구조)를 지닌 추상 모델입니다. Tree는 각각 element를 지닌 node들을 parent-child relation(부모-자식 관계)로 묶어서 분류한다는 점을 특징으로 삼을 수 있습니다. 2. Tree Terminology Tree를 구성하는 요소들은 다음과 같습니다. 1) Root: - parent를 가지지 않는 node이다. - (A) 2) Internal node: - 최소한 하나의 children를 지닌 node이다. - (A, B, C, F) 3) External node(leaf): - children를 지니고 있지 않는 .. 2021. 2. 21. [Vector/List]19. Double Linked List 구현 목차 1. class Node 2. class D_linked_list 3. insert() 4. erase 5. 테스트 1. class Node class Node: def __init__(self, e: object): self.element = e # node가 저장하는 element self.front = None # 앞에 있는 node의 주소 저장 self.back = None # 뒤에 있는 node의 주소 저장 2. class D_linked_list class D_linked_list: def __init__(self): self.head = Node('head') # head역할을 하는 node 지정 self.tail = Node('tail') # tail역할을 하는 node 지정 def .. 2021. 2. 21. [Vector/List]18. Position ADT, List ADT 목차 1. Position ADT 2. List ADT 3. Doubly Linked List 4. Performance 1. Position ADT Position ADT(위치)은 특정 data 구조가 저장되어있는 위치를 알아내는 ADT입니다. 이는 특정 array의 cell, 혹은 linked list의 node의 주소를 알고싶을 때, 주로 사용됩니다. 주요 기능은 p.element()입니다. 2. List ADT List ADT는 임의의 데이터를 저장하는 ADT입니다. 1) 특징 - List ADT는 2가지 특징을 지니고 있다. - element의 위치를 지정해야 함 - 특정 위치의 앞과 뒤의 element에 access할 수 있어야 함 2) 기능들 - size(): list의 크기를 반환한다. -.. 2021. 2. 21. [Vector/List]17. Vector ADT 목차 1. Vector ADT 2. Application of Vector 3. Array-based Vector 1. Vector ADT Vector ADT(벡터)는 배열과 비슷하며, 여러 특징을 지니고 있습니다. 1) 특징 - 초기에 크기 지정을 하지 않는다. - Vector의 element는 index에 따라서 접근되거나, 삽입/삭제 된다. 2) 주요 기능 - at(int i): index i에 저장되어 있는 element를 반환한다. - set(int i, object o): index에 저장되어 있는 element를 o로 바꾼다. - insert(int i, object o): 새로운 element o를 index i 자리에 삽입한다. - erase(int i): index i의 위치하고 있는 .. 2021. 2. 21. [Queue]16. Array-base Queue 구현 목차 1. class Queue_array 2. 테스트 1. class Queue_array class Queue_array: def __init__(self): self.queue = [] # queue 저장할 리스트 self.f = 0 # queue의 front idx self.r = -1 # queue의 rear idx def size(self)-> int: # queue의 크기 반환하는 함수 return len(self.queue) def empty(self)-> bool: # queue가 비어있는지 여부를 반환하는 함수 return len(self.queue)==0 def front(self)-> object: # front의 element를 반환하는 함수 if self.empty(): # qu.. 2021. 2. 20. [Queue]15. Queue 종류 목차 1. Array-base Queue(배열 기반 큐) 2. Array-base Circular Queue(배열 기반 원형 큐) 3. Linked list-base Queue(연결 리스트 기반 큐) 1. Array-base Queue(배열 기반 큐) Array-base Queue(배열 기반 큐)는 제목과 같이, queue를 array에 저장하는 방식을 말합니다. 위의 그림과 같이 배열의 앞부분을 front, 뒷부분을 rear로 놓고 사용합니다. 일반 배열 기반 큐의 특징은 값을 계속 enqueue할 경우, 앞의 메모리 공간이 비어있는 상태로 방치된다는 단점이 있습니다. 물론 파이썬을 기반으로 구현하면 그렇지 않지만, c++, java 등 array를 선언할 시 배열의 크기가 정해지는 경우, 이는 심각한.. 2021. 2. 20. [Queue]14. Queue(큐) 목차 1. Queue(큐) ADT 2. Applications of Queue(활용하는 곳) 1. Queue(큐) ADT Queue(큐) ADT는 줄서기 알고리즘이라고 생각하면 됩니다. 1) 특징 - 임의의 데이터를 저장한다. - FIFO(First In First Out, 먼저 들어간 데이터가 먼저 나옴), 선입선출의 개념을 따른다 - rear(데이터가 들어오는 곳)에서 insertion이 이루어지며, front(데이터가 나가는 곳)에서 removal이 이루어짐 2) 주요 기능 - enqueue(object): element를 insert하는 함수(queue의 end에) - dequeue(): element를 remove하는 함수(queue의 front에서) 3) 부가 기능 - object front(.. 2021. 2. 20. [Stacks]13. 후위 표기식 연산 구현 (Stack 응용) 목차 1. 중위 표기법, 후위 표기법 2. 후위 표기식 연산 방법 3. class Cal_post_fix 4. 테스트 1. 중위 표기법, 후위 표기법 1) 중위 표기법(Infix Notation) - 연산자를 피연산자의 가운데 표기하는 방법을 말한다. ex) A+B, A*B-C/D, A-B*C+D 2) 후위 표기법(Postfix Notation) - 연산자를 피연산자 뒤에 표기하는 방법을 말한다. ex) AB+, AB*CD/-, ABC*-D+ 2. 후위 표기식 연산 방법 후위 표기식을 입력받아 연산하는 방법은 다음의 과정과 같다. 1. 피연산자를 만나면 스택에 push한다. 2. 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고, 연산 결과를 다시 스택에 push한다. 3. 수식이 끝.. 2021. 2. 20. 이전 1 2 3 4 5 다음
