[C언어] #10 스택, 큐, 연결리스트, 해시테이블

Ilhoon·2022년 2월 24일
Cc언어스택연결리스트큐
1

C언어 제대로 정리해보자

목록 보기
10/10
post-thumbnail

스택

스택의 검색

  • 요소를 다 제거했다가 다시 원상복구해야 함
    • 제거할 때 임시로 다른 스택에 저장해놓으면 복구할 때 아주 편함
  • O(n) (제거O(n), + 복구 O(n))

스택의 용도

  • 일련의 자료들의 순서를 뒤집는데 유용
  • 재귀함수를 제거할 수 있다.
  • 중위 표현식을 후위 표현식으로 간단하게 바꿀 수 있다.

큐

큐의 삽입

void enqueue(int n){
	s_nums[s_back] = n;
    s_back = (s_back + 1) % MAX_NUMS;	// 원형 큐를 만들어주는 연산, s_back+1 이 MAX_NUMS와 같으면 s_back은 0으로
    s_num_count++;
}

큐의 삭제

  • 일반 배열 형태로 만들면 삭제된 자리를 앞으로 땡기는 로직이 필요하다. O(n)
  • 원형 큐 형태 (링버퍼) 로 만들면 O(1)로 가능하다
int deque(void){
    int ret;
    ret = s_nums[s_front];
    
    --s_num_count;
    s_front = (s_front + 1) % MAX_NUMS;
    
    return ret;
}

큐의 검색

  • 모든 요소를 다 제거했다가 다시 원상복구해야 함
  • O(n) (제거O(n), + 복구 O(n))

큐의 용도

  • 데이터 유입 속도가 데이터 소모 속도보다 빠른 경우
  • 멀티 쓰레딩
  • 입출력 스트림
  • 대기줄이 필요한 경우에 모두 적용가능



연결리스트

연결 리스트는 매우 훌륭한 면접문제

자료들이 메모리에 산재해 있다.

  • 동적 메모리 할당으로 필요에 따라 각 노드를 할당

노드에 다음 데이터를 가리키는 포인터가 있다. (마지막은 노드는 널포인터)

연결 리스트의 검색

  • 첫 노드(헤드)부터 처음부터 찾아야함 O(n)
  • 메모리에 산재해 있기 때문에 색인으로 접근 불가능

연결 리스트 전체를 출력하는 예제

typedef struct node {
    int value;
    node_t* next;
} node_t;

void print_node(const node_t* head){
    node_t* p;
    
    p = head;
    while (p != NULL){
        /* 출력 */
        p = p->next
    }
}

헤드 노드

  • 연결리스트의 첫 번째 노드를 가리키는 포인터
  • 처음 시작할 때 값은 NULL (아직 가리킬 것이 없다)
    • 동적할당으로 헤드에 대입, 헤드 다음 노드도 동적할당으로..!
    • 동적할당을 했으면? 반드시 free()를 생각

연결리스트를 다 사용하고 할당받은 메모리를 해제할 코드

void destroy(node_t* head){
	node_t* p = head;
    while(p != NULL){
        node_t* next = p->next;
        free(p);
        p = next;
    }
}

연결리스트의 삽입

  • 이미 삽입할 위치를 알면 O(1)
  • a, c 노드 사이에 b노드를 추가하려면?
    • a노드의 포인터 -> b위치로 변경
    • b노드의 포인터 -> c위치로 변경
    • 끝

연결 리스트 맨 앞에 삽입하는 코드

head -> first_insert

head -> second_insert -> first_insert

3줄 요약

  1. 새로운 node의 동적 할당이 필요하다
  2. 기존에 head가 가리키던 주소를 new_node의 next 값에 대입한다.
  3. head가 가리키는 주소 값을 new_node의 주소값으로 바꿔준다.
// 맨 앞에 삽입하는 코드
void insert_front(node_t** phead, int n){
    node_t* new_node;
    new_node = malloc(sizeof(node_t));
    new_node->value = n;
    new_node->next = *phead;
    *phead = new_node;
}

int main(void){
    node_t* head = NULL;
    
    insert_front(&head, 3);
    destroy(head);
    head = NULL;
}

왜 phead는 이중 포인터인가?

  • 그냥 포인터 변수라면? phead 값을 아무리 바꿔줘도 원본에 접근할 수 없다!
  • main함수에 선언된 head변수의 원본 값을 변경해주기 위해서

오름차순을 유지하면서 삽입하는 코드

void insert_soerted(node_t** phead, int n){
    node_t** pp;
    node_t* new_node;
    
    new_node = malloc(sizeof(node_t));
    new_node->value = n;
    
    pp = phead;
    while (*pp != NULL){
        if((*pp)->value >= n){
            break;
        }
        pp = &(*pp)->next;
    }
    new_node->next = *pp;
    *pp = new_node;
}

int main(void){
    node_t* head = NULL;
    
    insert_front(&head, 2);
    insert_front(&head, 5);
    insert_front(&head, 3);
    destroy(head);
    head = NULL;
}

연결 리스트의 삭제

void remove(node_t** phead, int n){
    node_t** pp;
    
    pp = phead;
    while (*pp != NULL){
        if((*pp)->value == n){
            node_t* tmp = *pp;	// 삭제할 노드의 다음노드 임시저장
            *pp = (*pp)->next;
            free(tmp);
            break;
        }
        pp = &(*pp)->next;
    }
}
    
int main(void){
    node_t* head = NULL;
    
    remove(&head, 2);
    remove(&head, 5);
    
    destroy(head);
    head = NULL;
}

연결 리스트의 용도

  • 최대 길이를 특정할 수 없고, 삽입 삭제가 빈번한 경우
  • 오늘날에는 동적 배열을 더 많이 사용
    • 최신 하드웨어 특징 상 인접한 메모리를 사용(배열형태)하면 성능에 유리하기 때문에



해시테이블

해시테이블 만드는 과정

  1. 값을 해시함수에 입력해서 해시코드로 변환
  2. 해시코드를 해시테이블의 크기만큼 나머지 연산을 통해 인덱스를 찾음
    • 해시테이블의 크기는 최소 2배 이상인 소수로!
    • 소수로 나눠야 동일한 색인이 안 나올 가능성이 제일 높음

해시함수

임의의 크기를 가진 데이터를 고정크기의 값에 대응하게 하는 함수

  • 무제한 입력 --> 32비트정수

입력값이 같으면 출력값은 언제나 같다.

입력값은 다른데 출력값이 같을 수 있다. (해시충돌)

데이터 -> 해시함수 -> 해시값

해시 충돌이 적을 수록 좋은 해시함수

해시 맵

키 배열, 값 배열 2개의 배열로 만들 수 있다.

같은 인덱스에 매핑되는 쌍이 저장되어있다.

해시충돌

해시충돌을 방지할 수 있다면?

  • char* 문자열을 저장하려고 동적메모리할당 안해도된다.

    • 키값이 문자열로 구성된 해시테이블이라면, 키배열에 문자열을 저장하지 않아도 된다.

    • 해시값만 저장해도된다(해시충돌이 없기때문에 가능)

해시충돌을 방지할 수 있는 조건?

  • 미리 만들어놓은 데이터 파일 읽어서 테스트 가능

중복색인 문제 해결

  1. 찾은 색인 위치 이후에 빈 공간을 찾아 저장

    • 배열에서 비어있는 위치를 알 수 있어야한다

      • 어떤 특정 값을 저장해서 비어있다는 사실을 표시 (배열에 입력될 수 없는 값으로 초기화)
      • 같은 인덱스가 계속 중복된다면 비어있는 위치를 찾으러 계속 가야된다. (최악의 경우 O(n))

    • 실제 값을 저장해야함

#define TRUE(1)
#define FALSE(0)
#define SIZE(23) // 소수로 크기 설정

int s_numbers[SIZE];

void init_hashtable(void){
    /* 극한 값 혹은 배열에 입력될 수 없는 값으로 초기화 */
}

// 해시테이블에 값이 있는지 찾는 코드
int has_value(int value){
    int i;
    int start_index;
    
    start_index = value % SIZE;
    if(start_index < 0){
        start_index += SIZE;
    }
    i = start_index;
    do {
        if (s_number[i] == value){
            return TRUE;
        } else if (s_number[i] == INIT_VAL){
            return FALSE;
        }
        
        i = (i+1) % SIZE;
    }while(i != start_index);
    
    return FALSE;
}
  1. 배열의 각 요소에 연결리스트를 사용
    • 최악의 경우는 O(n)이지만 앞의 경우 보다는 O(n)이 될 할 확률이 적다.
    • 동적할당을 해야하기 때문에 성능상 단점이 있을 수 있다.
      • 성능이 중요한 경우에는, 일반 배열로 중복색인 저장하고 해당 배열 크기 이상의 중복색인 값이 들어오면 assert로 잡고 배열크기 늘려주는 방식도 있다.

베스트 프랙티스

  • 기본적으로 배열이 최고
    • 가장 간단하고 성능이 좋다.
  • 빈번한 데이터 삽입 또는 삭제가 필요한 경우?
    • 연결리스트
  • 데이터 양이 많은데 검색을 자주해야하는 경우
    • 해시테이블
profile
Ilhoon
꾸준하게!
이전 포스트

[C언어] #9 동적메모리사용 (malloc, free, memset)

0개의 댓글