쌓고 쌓다

스택 (배열) #include #define MAX_SIZE 5 int arr[5]; int top=-1; void push(int x) { if (top + 1 == MAX_SIZE) { printf("빈자리 없음.\n"); return; } arr[++top] = x; return; } int pop() { if (top == -1) { printf("비어있음.\n"); return -1; } return arr[top--]; } int is_empty() { if (top == -1) return 1; else return 0; } void Top() { if (top == -1) { printf("비어있음.\n"); return; } printf("%d\n", arr[top]); return; }..

노드 설정 struct Node { int data; Node* prev; Node* next; }; GetNewNode 함수 Node* GetNewNode(int x) { Node* tmp = (Node*)malloc(sizeof(Node)); tmp->data = x; tmp->prev = NULL; tmp->next = NULL; return tmp; } 전역 변수로 head 존재함. Node* head; Head에 삽입 ( 맨 앞에 ) void InsertAtHead(int x) { Node* tmp = GetNewNode(x); if (head == NULL) { head = tmp; return; } head->prev = tmp; tmp->next = head; head = tmp; } Ta..

반복문 정방향 출력 ( 싱글 + 더블 ) void Print() { Node* tmp = head; while (tmp != NULL) { printf("%d->", tmp->data); tmp = tmp->next; } } 반복문 역방향 출력 (더블) void ReversePrint() { Node* tmp = head; if(tmp==NULL) return; while (tmp->next != NULL) { tmp = tmp->next; } while (tmp != NULL) { printf("%d->", tmp->data); tmp = tmp->prev; } } 재귀 함수 정방향 출력 ( 싱글 + 더블 ) void Print(Node* p) { if (p != NULL) { printf("%d->"..

1. 전역 변수 head와 노드 포인터 prev, cur, next로 뒤집기 전체 코드 #include #include struct Node { int data; Node* next; }; Node* head = NULL; void InsertAtHead(Node** phead, int x) { Node* tmp = (Node*)malloc(sizeof(Node)); tmp->data = x; tmp->next = NULL; if (*phead != NULL) tmp->next = *phead; *phead = tmp; } void Reverse() { Node* prev = NULL; Node* cur = head; Node* next = NULL; while (cur != NULL) { next = ..

싱글 링크드 리스트에서 삽입을 크게 아래 3가지 방법으로 구현한다. 1. head 포인터를 전역변수 2. main안 로컬 변수로 head 포인터 3. 로컬 변수 head 포인터이나 삽입 함수에서 리턴 없이 구현 1. head 포인터를 전역변수 1-1) head에 노드 삽입 #include #include struct Node { int data; Node* next; }; Node* head; void InsertAtHead(int x) { Node* tmp = (Node*)malloc(sizeof(Node)); tmp->data = x; tmp->next=NULL; if(head!=NULL) tmp->next = head; head = tmp; return; } int main(void) { Inser..

탐색 여러 개의 자료 중 원하는 자료를 찾는 것 탐색키 : 항목과 항목을 구별해주는 키(key) 배열, 연결 리스트, 트리 그래프 등 다양한 방법으로 탐색 자료구조로 씀 순차 탐색 (sequential search) 탐색 방법 중 가장 간단하고 직접적인 방법 정렬 안된 배열을 처음부터 마지막까지 검사 평균 비교 횟수 성공 시 : (n+1)/2번 비교 -> 한 번에 찾을 경우 1, 최악의 경우 n이니 나누기 2 실패 시 : n번 비교 시간 복잡도 : O(n) 예시 코드 int seq_search(int key, int low, int high) { for (int i = low; i right)); } return height; } int get_balance(AVLNode* node) { if (node..

Priority queue 우선순위를 가진 항목들을 저장하는 큐 FIFO 순서가 아니라 우선 순위가 높은 데이터가 먼저 나가게 된다. 스택이나 큐(FIFO)를 우선순위 큐로 구현할 수 있다. 스택 -> 가장 최근에 들어온 데이터가 삭제 ( 시간이 우선순위 ) 큐 -> 가장 먼저 들어온 데이터가 삭제 ( 시간이 우선순위 ) 우선순위 큐 -> 가장 우선순위가 높은 데이터 최소 우선순위 큐 최대 우선순위 큐가 존재 우선순위 큐의 추상자료형 (Abstract Data Type) 객체 n개의 element형의 우선순위를 가진 요소 연산 create() : 우선순위 큐를 생성 init(q) : 우선순위 큐 q를 초기화 is_empty(q) : 우선순위 큐 q가 비어있는지를 검사 is_full(q) : 우선순위 큐 ..

해싱 대부분 탐색 방법은 키 값 비교로 탐색하고자 하는 항목에 접근하지만 해싱은 바로 접근한다. 즉, 키 값에 대한 산술적 연산으로 테이블의 주소를 계산하여 항목에 접근 key를 넣었더니 value가 나오는 것 해시 테이블(hash table) : 키 값의 연산으로 직접 접근이 가능한 구조로 키 값으로 value를 찾는 것이다. 해시 함수(hash function) 키를 input으로 넣었더니 value로 해시 주소(hash address)를 생성하는 함수이다. 이 해시 주소가 배열로 구현된 해시 테이블(hash talbe)의 인덱스이다. 헤시 테이블 ht M개의 버켓(bucket)으로 구성된 테이블 ht[0], ht[1], ... , ht[M-1]의 원소를 가짐. 하나의 버켓에 s개의 슬롯(slot) ..