대학교 2학년 1학기/자료구조 (12) 썸네일형 리스트형 8. 우선순위 큐 우선순위 큐: 우선순위를 가진 항목들을 저장하는 큐 - 일반 큐와 다른 점은 우선순위가 높은 데이터가 먼저 나감 구현 방법 1. 배열을 이용한 우선순위 큐 2. 연결 리스트를 활용한 우선순위 큐 3. 히프(heap)를 이용한 우선순위 큐 구현 별 시간 복잡도 표현 방법 삽입 삭제 순서 없는 배열 O(1) O(n) 순서 없는 연결 리스트 O(1) O(n) 정렬된 배열 O(n) O(1) 정렬된 연결 리스트 O(n) O(1) 히프 O(log n) O(log n) 히프: 노드의 키들이 다음 식을 만족하는 완전이진트리 - 최대 히프: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리 // key(부모 노드) >= key(자식 노드) - 최소 히프: 부모 노드의 키 값이 자식 노드의 키 값보다.. 7. 트리 트리: 계층적인 구조를 나타내는 자료구조 - 가족의 가계도, 회사의 조직도, 컴퓨터의 디렉터리 구조 등 - 트리는 부모-자식 관계의 노드들로 이루어짐 트리의 용어 - 노드: 트리의 구성요소 - 루트: 부모가 없는 노드 - 서브 트리: 하나의 노드와 그 노드들의 자손들로 이루어진 트리 - 단말 노드: 자식이 없는 노드 - 비단말 노드: 적어도 하나의 자식을 가지는 노드 - 자식, 부모, 형제, 조상, 자손 노드 - 레벨: 트리 각층의 번호 - 차수: 노드가 가지고 있는 자식 노드의 개수 이진트리 이진트리:모든 노드가 2개의 서브 트리를 가지고 있는 트리 - 서브 트리는 공집합일 수 있음. - 최대 2개까지의 자식 노드가 존재 - 모든 노드의 차수가 2 이하가 됨 - 서브 트리 간의 순서가 존재 이진트리의 .. 6-5. 연결리스트(스택, 큐) 1. 연결리스트로 구현한 스택 2. 연결 리스트로 구현한 큐 자료 출처: 천인국 외 1명, C언어로 쉽게 풀어쓴 자료구조, 생능출판(2019) 6-4. 연결리스트 (이중 연결 리스트) 이중 연결 리스트: 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트 헤드 노드(head node): 데이터를 가지지 않고 오로지 삽입, 삭제 코드를 간단하게 할 목적으로 만들어진 노드 - 헤드 포인터와의 구별이 필요 - 공백 상태에서는 헤드 노드만 존재 자료 출처: 천인국 외 1명, C언어로 쉽게 풀어쓴 자료구조, 생능출판(2019) 6-3. 연결리스트 (원형 연결 리스트) 원형 연결 리스트 - 마지막 노드의 링크가 첫 번째 노드를 가리키는 리스트 - 한 노드에서 다른 모든 노드로의 접근이 가능 - 헤드 포인터가 마지막 노드를 가리키게끔 구성하여 리스트의 처음이나 마지막에 노드를 삽입하기 용이 1. 원형 연결 리스트의 처음에 삽입 2. 원형 연결 리스트의 끝에 삽입 자료 출처: 천인국 외 1명, C언어로 쉽게 풀어쓴 자료구조, 생능출판(2019) 6-2. 연결리스트 (단순 연결 리스트) 연결리스트 - 리스트의 항목들을 노드(node)라고 하는 곳에 분산하여 저장 - 노드는 데이터 필드와 링크 필드로 구성 데이터 필드: 리스트의 원소, 즉 데이터 값을 저장하는 곳 링크 필드: 다른 노드의 주소 값을 저장하는 장소(포인터) 장점 - 삽입, 삭제가 용이하다. 시간 복잡도는 O(1) - 연속된 메모리 공간이 필요 없고, 크기 제한이 없다. 단점 - 구현이 어렵고, 오류가 발생하기 쉽다. 연결 리스트의 종류: 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트 단순 연결 리스트 - 하나의 링크 필드를 이용하여 연결, 마지막 노드의 링크 값은 NULL 단순 연결 리스트의 연산 - insert_first(): 리스트의 시작 부분에 항목 삽입 - insert(): 리스트의 중간 부분에 항목 삽입.. 6-1. 연결리스트 (배열을 이용한 구현) 배열로 구현된 리스트: 순차적인 메모리 공간이 할당되므로, 이것을 리스트의 순차적 표현이라고 한다 5. 큐 1. 큐의 특징 - 선입 선출: 먼저 들어온 데이터가 먼저 나감. - 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조. - 삽입이 일어나는 곳을 후단, 삭제가 일어나는 곳을 전단이라고 함. - 삽입과 관련된 변수를 rear, 삭제와 관련된 변수를 front라고 함. 큐의 추상 자료형 - create(max_size): 최대 크기가 max_size인 공백큐를 생성. - init(q): 큐를 초기화. - is_empty(q): 큐가 공백상태인지 검사. - is_full(q): 큐가 포화상태인지 검사. - enqueue(q, e): 큐의 끝에 데이터를 추가. - dequeue(q): 큐의 앞에 있는 데이터를 삭제하고 반환. - peek(q): 큐의 맨 앞에 있는 데이터를 읽어서 반환. 2.. 이전 1 2 다음
