[sw 정글] 5/02 TIL c언어 및 Linked-list, 이진검색트리

C언어 공부내용

union

• 구조체와 비슷하며 메모리를 공유한다.
• 메모리를 공유하기 때문에 유니온은 멤버변수를 한번에 하나씩만 사용가능하다.

union student{
	int age;
	double grade;
}

• student의 age를 사용하고 있다면 grade를 사용할 수 없다.

lvalue, rvalue

대입연산자 위치를 말한다.

a = 10

a는 lvalue가 되고 10이 rvalue가 된다.

배열은 modifiable lvalue가 아니므로 대입연산자의 왼쪽에 올 수 없다.

포인터

const int* pa = &a;

*pa = 3;  //올바르지 않은 문장
pa  = &b  // 올바른 문장

int* const pa = &a;

*pa = 3 //올바른 문장
pa = &b;  // 올바르지 않은 문장

const int* pa = &a

• pa가 int형 변수를 가리키는데 그 값(데이터)을 변경하지 마라

int * const pa = &a;

• int형 변수의 주소를 가리키는 pa를 변경하지 마라

배열의 이름

• 배열자체의 주소를 출력하면 배열의 첫번째 요소의 주소값이 나온다.
• 그렇다고 배열의 이름이 배열의 첫번째를 가리키는 포인터는 아니다.

int arr[6] = {1,2,3,4,5,6,};
int * parr = arr;

sizeof arr // 24
sizeof parr  // 8

• sizeof 연산자 사용시 다른 결과값 출력
• sizeof나 & 연산자와 사용될 때를 제외하면 배열의 이름을 사용시 암묵적으로 첫번째 원소를 가리키는 포인터로 타입 변환되기 때문이다.

arr[i] 는 다음으로 변환된다. → *(arr +i)

malloc, calloc, realloc

malloc

• malloc은 단순히 메모리만 할당하는함수이기 때문에 형을 예측할 수 없음
• void포인터 형을 반환하여 개발자가 용도에 맞게 변환하여 사용할 수 있음

// 원형
void *malloc(size_t size)

//int 형으로 메모리 할당
int * i = (int*) malloc(sizeof(int));

// 배열에 할당하려면
int *arr_2 = (int*) malloc(sizeof(int)*5) // 숫자에 배열의 사이즈를 할당하면 된다.

free함수

• 힙 영역에 할당된 메모리를 해제하는 함수
• 할당된 메모리가 더이상 필요하지 않다면 해제시켜줘야한다.

calloc 함수

• calloc 함수는 malloc함수와 같은 기능을 지니지만 사용형태가 다르다.

void *calloc(size_t elt_count, size_t elt_size); //calloc 함수 원형
// elt_size 크기의 변수를 elt_count 개 만큼 저장할 수 있는 메모리 공간을 할당

// malloc과 비교
int *arr_1 = (int*) malloc(sizeof(int)*5);
int *arr_2 = (int*) calloc(5, sizeof(int));

malloc 함수와 calloc함수의 차이점

• malloc은 할당된 공간의 값을 바꾸지 않는다.
• calloc은 할당된 공간의 값을 0으로 바꾼다.
• 배열에 0으로 초기화가 필요한 경우 calloc을 사용한다.

realloc 함수

• 이미 할당된 공간의 크기를 바꿀때 realloc 함수를 사용한다.

void *realloc(void *memblock, size_t size); // realloc 함수의 원형

//사용 예시
int *arr_1 = (int*) malloc(sizeof(int)*5);
//현재 arr_1의 메모리 4*5
realloc(arr_1, sizeof(int)*10);
//arr_1의 메모리 20바이트 -> 40바이트 로 크기 변경

• 이미 할당된 포인터 변수를 memblock에 넣고, 바꾸고 싶은 공간의 크기를 size에 입력하여 사용

---

Linked-list

 단반향리스트 동작 추상화만 보고 마음대로 작성한 코드라서 예외상황이나 잘 못된 동작을 할 수도 있다. ㅎㅎ

// RB트리 전 c언어 연습하기
// 단방향 연결리스트 구현하기
// 목표: 삽입, 삭제, 조회 기능 구현
// 삽입 -> 헤더 뒤에 새로운 값 추가
// 삭제 -> 첫 요소 삭제와 원하는 요소 삭제 추가
// 조회 -> 현제 링크드리스트에 들어있는 값들 조회
#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
  struct Node *next;
  int data;  
} Node;

// 헤더 뒤에 입력값을 바로 추가한다.
void insert_first(Node *head, int k){
  Node *insert_node = malloc(sizeof (Node));
  insert_node->next = head->next;
  insert_node->data = k;
  
  head->next = insert_node;  
}

//링크드 리스트를 순회하여 마지막 노드에 새로운 노드를 추가한다.
void insert_end(Node *head, int k){
  Node *insert_node = malloc(sizeof (Node));
  insert_node->data = k;
  insert_node->next = NULL;
  Node *curr = head;
  while (curr->next != NULL){
    curr = curr->next;
  }
  curr->next = insert_node;
}

//특정 값이 있는지 찾는 함수
//있다면 1 없다면 0을 반환
int search(Node *head, int k){
  Node *curr = head->next;
  while (curr != NULL){
    if (curr->data == k){
      free(curr);
      return 1;
    }else{
      curr = curr->next;
    }
  }
  free(curr);
  return 0;
}

// 링크드 리스트에 들어있는 값들을 차례대로 출력한다.
void show(Node *head){
  Node *curr = head->next;
  while(curr != NULL){
    printf("%d\n", curr->data);
    curr = curr->next;
  }
  free(curr);
}

// 헤더 뒤에 노드를 바로 지운다.
void delete_first(Node *head){
  if (head->next != NULL)
    head->next = head->next->next;
}

// 특정 노드의 값을 삭제한다.
void delete(Node *head, int k){
  if (head->next != NULL && head->next->data == k){
    head ->next = head->next->next;
  }

  Node *curr = head->next;
  while(curr->next != NULL){
    if (curr->next-> data == k){
      curr->next = curr->next-> next;
    }else{
      curr = curr->next;
    }
  }
}

int main(){
  // 헤더 노드 링크스 리스트의 헤드
  struct Node *head = malloc(sizeof (struct Node));
  head->next = NULL;
  
  insert_first(head, 10);
  insert_first(head, 20);
  insert_first(head, 30);
  insert_first(head, 40);
  insert_first(head, 50);
  insert_first(head, 60);
  insert_end(head, 100);

  if (search(head, 70)){
    printf("숫자가 안에 있음\n");
  }else{
    printf("숫자 없음\n");
  };

  show(head);
  delete_first(head);
  delete(head, 30);
  printf("-------------\n");

  show(head);

  free(head);

  return 0;
}

이진 검색 트리

회전이 없는 기본 이진 검색 트리

이진 검색 트리의 많은 부분이 RB트리에서 사용하는 것과 비슷한 부분이 많다.

연습하고 들어간다면 조금은 쉽게 진행가능할 것 이다.

#include<stdio.h>
#include<stdlib.h>

typedef struct node{
  int key;
  struct node *left, *right;
} node;

typedef struct{
  node *root;
} binery_tree;

// 중위순회 이진 검색트리에서는 정렬되어 나온다.
void inorder(node *root){  
  if (root != NULL){
    inorder(root ->left);
    printf("%d\n", root->key);
    inorder(root ->right);
  }
}

//트리에 새로운 노드 추가
void insert(binery_tree *t, const int key){
  // 탐색 실패시 실패한 위치에 삽입한다.
  node *insert_node = (node*)calloc(1, sizeof(node));
  insert_node->key = key;

  if (t->root == NULL){
    //트리의 root가 null이면 insert_node를 트리에 root로 설정한다.
    t->root = insert_node;
    return; 
  }else{
    node *curr = t->root;
    while (curr != NULL){
      if (curr->key > key){
        if (curr->left == NULL){
          curr->left = insert_node;
          return ;
        }else{
          curr = curr->left;
        }
      }else{
        if (curr->right == NULL){
          curr->right = insert_node;
          return ;
        }else{
          curr= curr->right;
        }
      }
    }
  }
}

// 특정 data를 가진 노드가 있는 지 확인
node * search(node *root, int data){
  if (root == NULL || root->key == data){
    return root;
  }else if (root-> key > data){
    return search(root->left, data);
  }else
    return search(root->right, data);
}

// 트리 노드 삭제 함수
// 삭제하는 부분이 많이 어렵다.
node * delete(node * root, int data){
  // 반환타입을 노드 포인터로 해야하는 이유
  // 루트노드가 지워지고 아래의 값이 새 루트가 되었을 때
  // 새로운 루트노드를 반환값으로 주어야한다.

  node *p = root;
  node * parent = NULL;
  while ((p != NULL) && (p->key != data)){
    parent = p;
    if (p->key >data){
      p = p->left;
    }else{
      p = p-> right;
    }
  }
  if (p == NULL){
    printf("찾는 노드가 없음\n");
    return root;
  }

  // 차수가 0인 경우 단말노드
  if (p->left == NULL && p->right == NULL){
    //현재 노드가 루트인지 아닌지 확인해야함
    if(parent == NULL){ // 차수가 0이고 루트 인경우
      root = NULL;
    }else{
      //parent가 가리키는 p의 위치를 찾고 NULL로 할당한다.
      if (parent->left == p){
        parent->left = NULL;
      }else{
        parent->right = NULL;
      }
    }
  }else if (p->left == NULL || p ->right == NULL){ // 차수가 1인 경우
    node *child = (p->left != NULL) ? p->left : p->right;
    if(parent == NULL)
      root = child;
    else{
      if (parent->left == p){
        parent->left = child;
      }else{
        parent->right = child;
      }
    }
  }else{
    // 후계자를 찾기위해서 왼쪽 오른쪽 상관x 오른쪽으로 찾아가겠음
    node *succ_parent = p;
    node *succ = p -> right;
    while(succ->left != NULL){
      succ_parent = succ;
      succ= succ->left;
    }
    p->key = succ->key;
    // succ노드는 왼쪽자식이 없는 것이 확실
    // 있을 수 있는 succ의 오른쪽 자식을 succ_parent에 할당한다.
    if (succ_parent ->left == succ)
      succ_parent ->left = succ->right;
    else
      //삭제하기 위해서 가장 작은 값을 찾아야하는데 
      // succ_parent의 오른쪽에 succ이 있으면 더 큰 값이지 않나?
      succ_parent->right = succ->right;
    p = succ;
  }
  
  // 어떤 경우에도 p는 삭제된다.
  free(p);
  return root;
}

int main(){
  // 테스트를 위한 메인
  // 마음대로 바꿔서 테스트 해보세요
  binery_tree *t = (binery_tree*)calloc(1,sizeof(binery_tree));
    
  t->root = NULL;

  insert(t, 50);
  insert(t, 30);
  insert(t, 60);
  insert(t, 20);
  insert(t, 40);

  inorder(t->root);
  printf("-------------\n");
  delete(t->root, 20);
  inorder(t->root);
  printf("-------------");
 
  return 0;
}