C언어/자료구조 (38) 썸네일형 리스트형 10-1 장 해시법 (2) 1. 오픈 주소법 이해하기 오픈 주소법(open addresing) - 충돌이 발생했을 때 재해시(rehashing)를 수행하여 비어 있는 버킷을 찾아내는 방법 - 닫힌 해시법(closed hashing) - 연결 탐사법(linear probing) : 빈 버킷을 만날 때 까지 재해시 //요소의 상태 typedef enum { Occupied, Empty, Deleted }Status; //요소 typedef struct { Member data; //데이터 Status stat; // 요소의 상태 }Bucket; //해시 테이블 typedef struct { int size; //해시 테이블의 크기 Bucket *table; //해시 테이블의 첫 번째 요소에 대한 포인터 }ClosedHash; 1.1 .. 10 -1 해시법 (1) 1. 해시법 정의하기 해시법(hashing) - 데이터를 저장할 위치(인덱스)를 간단한 연산으로 구하는 것 해시값(hash value) - ex) 배열의 키 값(각 요솟값)을 배열의 요소 개수 13으로 나눈 나머지 - 데이터에 접근할 때 사용 해시 테이블 (hash table) - 해시 값이 인덱스가 되도록 원래의 키 값을 저장한 배열 해시 함수(hash function) - 키값을 가지고 해시값을 만드는 과정 - 나머지를 구하는 연산 또는 나머지 연산을 다시 응용한 연산을 사용 버킷(bucket) - 해시 테이블의 각 요소 2. 충돌 살펴보기 충돌(collision) - 저장할 버킷이 중복되는 현상 ex) 새로운 값 18 추가 (해시값 5 -> 버킷 a[5]) but a[5]에는 다른 값 저장되어 있음.. 9-2장 이진 트리와 이진 검색 트리 1. 이진 트리 정의하기 이진 트리(binary tree) - 노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리 - 각 노드의 자식은 2명 이하만 유지해야 함 - 왼쪽 자식과 오른쪽 자식을 구분 - 왼쪽 서브 트리 (left subtree) : 왼쪽 자식을 다시 루트로 하는 서브트리 - 오른쪽 서브 트리 (right subtree) : 오른쪽 자식을 다시 루트로 하는 서브트리 2. 완전 이진 트리 정의하기 완전 이진 트리 (complete binary tree) - 마지막 레벨을 제외한 레벨은 노드를 가득 채움 - 마지막 레벨은 왼쪽부터 오른쪽 방향을 노드를 채우되 반드시 끝까지 채울 필요는 없음 - 높이가 k인 완전 이진트리가 가질 수 있는 노드의 최댓값 2^k+1 -1 - n개의 노드를 저장할 수 있는 완.. 9-1장 트리 1. 트리 정의하기 트리(Tree) - 데이터 사이의 계층 관계를 나타내는 자료구조 루트(root) - 트리의 가장 윗부분에 위치하는 노드 - 하나의 트리에는 하나의 루트가 있음 리프(leaf) - 트리의 가장 아랫부분의 위치하는 노드 - 더이상 뻗어나갈 수 없는 마지막에 위치한 노드 안쪽 노드 - 루트를 포함하여 리프를 제외한 노드 자식(child) - 어떤 노드로부터 가지로 연결된 아래쪽 노드 부모(parent) - 어떤 노드에서 가지로 연결된 위쪽 노드 형제(sibling) - 같은 부모를 가지는 노드 조상(ancestor) - 어떤 노드에서 가지로 연결된 위쪽 노드 all 자손(descendant) - 어떤 노드에서 가지로 연결된 아래쪽 노드 all 레벨(level) - 루트로부터 얼마나 떨어져 .. 8-4장 원형 이중 연결 리스트 1. 원형 리스트 알아보기 원형 리스트 (circular list) - 선형 리스트의 꼬리 노드가 머리 노드를 가리킴 - 꼬리 노드의 다음 노드를 가리키는 포인터가 머리 노드의 포인터 값 - 빈 원형 리스트 //원형 리스트가 비어 있는지 확인 list->head == NULL; - 노드가 1개인 원형 리스트 //노드가 1개 인지 확인 list->head->next == list->head - 포인터가 머리 노드를 가리킴 //p가 가리키는 노드가 머리 노드인지 확인 p == list->head - 포인터가 꼬리 노드를 가리킴 //p가 가리키는 노드가 꼬리 노드인지 p->next == list->head 2. 이중 연결 리스트 알아보기 이중 연결 리스트 (doubly linked list) - 양방향 리스트.. 8-3장 커서를 이용한 연결 리스트 1. 커서로 연결 리스트 만들기 - 각 노드를 배열 안의 요소에 저장하고 그 요소를 잘 이용해 연결 리스트를 구현 - 실행 중에 데이터의 개수가 크게 바뀌지 않고 데이터 개수의 최댓값을 미리 알 수 있다면 배열을 사용해 효율적으로 연결리스트 구현 - 배열의 커서에 해당하는 값 = 다음 노드가 들어 있는 요소의 인덱스에 대한 값 - 커서(cursor) : 포인터 역할을 하는 인덱스 -> 노드 B의 커서 3은 B의 다음 노드 C가 인덱스 3인 위치에 저장되어 있음을 의미 -> 꼬리 노드의 커서는 -1 -> 노드의 삽입, 삭제 시 요소를 옮길 필요 없음 ex) 머리에 노드 G 삽입 - head를 1에서 6으로 업데이트 하고 노드 G의 커서에 1을 대입 2. 배열에 비어 있는 요소 처리하기 1) - 연결 리스트.. 8-2장 포인터를 이용한 연결 리스트(2) 1. 머리에 노드를 삽입하는 InsertFront 함수 - 연결 리스트의 머리에 노드를 삽입하는 함수 //머리에 노드를 삽입 void InsertFront(List *list, const Member *x) { Node *ptr = list->head; list->head = list->crnt = AllocNode(); SetNode(list->head,x,ptr); } 1) - 삽입 전의 머리 노드 A에 대한 머리 포인터를 ptr에 대입 Node *ptr = list->head; 2) - 삽입할 노드 G를 AllocNode 함수로 만들고 만든 노드를 가리키도록 머리 포인터 list->head를 업데이트 list->head = list->crnt = AllocNode(); 3) - SetNode 함수를.. 8-2장 포인터를 이용한 연결 리스트(1) 1. 포인터로 연결 리스트 만들기 - 노드용 구조체 Node - data : 데이터 (Member형) - next : 다음 노드에 대한 포인터 (자기 자신과 같은 구조체형을 가리키는 포인터) - 자기 참조형 (self-refernetial) - 자기 자신과 같은 자료형의 객체를 가리키는 데이터가 내부에 포함 //포인터로 만든 연결리스트 #ifndef ___LinkedList #define ___LinkedList //노드 typedef struct __node { Member data; //데이터 struct __node *next; //뒤쪽 포인터(다음 노드에 대한 포인터) }Node; //연결 리스트 typedef struct { Node *head; //머리 노드에 대한 포인터 Node *crnt;.. 이전 1 2 3 4 5 다음
