21/09/21

모두를 위한 컴퓨터 과학 (CS50 2019) - 자료구조

 

 

1) malloc과 포인터 복습

💬포인터를 초기화시키지 않고 값을 저장하면 쓰레기값이 발생한다.

 

 

 

2) 배열의 크기 조정하기

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

int main(void)
{
    //int 자료형 3개로 이루어진 list 라는 포인터를 선언하고 메모리 할당
    int *list = malloc(3 * sizeof(int));

    // 포인터가 잘 선언되었는지 확인
    if (list == NULL)
    {
        return 1;
    }

    // list 배열의 각 인덱스에 값 저장
    list[0] = 1;
    list[1] = 2;
    list[2] = 3;

    //int 자료형 4개 크기의 tmp 라는 포인터를 선언하고 메모리 할당
    int *tmp = malloc(4 * sizeof(int));

    if (tmp == NULL)
    {
        return 1;
    }

    // list의 값을 tmp로 복사
    for (int i = 0; i < 3; i++)
    {
        tmp[i] = list[i];
    }

    // tmp배열의 네 번째 값도 저장
    tmp[3] = 4;

    // list의 메모리를 초기화
    free(list);

    // list가 tmp와 같은 곳을 가리키도록 지정
    list = tmp;

    // 새로운 배열 list의 값 확인
    for (int i = 0; i < 4; i++)
    {
        printf("%i\n", list[i]);
    }

    // list의 메모리 초기화
    free(list);
}

예제에서 list = tmp; 부분 설명.

해당 라인 이전까지 list 의 메모리 공간을 바꾸기 위해서 tmp를 이용한 것이다.

list 에 있는 데이터를 tmp 에 다 옮기고 새로운 데이터까지 추가했으니 tmp라는 임시 이름을 바꿔주는 것이다.

 

💬이미 할당된 메모리 크기를 조절할 때 임시 메모리를 새로 할당해주지 않는다면, 근처 메모리 공간을 덮어쓸 수 있기 때문이다.

 

 

 

3) 연결 리스트 : 도입

💬연결리스트를 배열과 비교했을 때의 장단점

장점 : 메모리 공간이 연속적으로 존재하지 않아도 할당이 가능하다는 점에서 속도가 빠르다.

단점 : 노드 하나에 다음 노드 정보도 가지고 있으므로 메모리 공간이 더 필요하다.

 

 

 

4) 연결 리스트 : 코딩

💬연결리스트 중간에 node 추가/삭제 코드

1 -> 2 -> 4 가 있다고 가정하고 2와 4 중간에 3 노드를 추가한다.

// 중간에 추가
n = malloc(sizeof(node));
if (n == NULL)
{
	return 1;
}

n->number = 3;
n->next = list->next->next; // 4를 바라본다.

list->next->next = n; // 2가 n을 바라보게 한다.


// 다시 삭제
tmp = malloc(sizeof(node));
if (tmp == NULL)
{
	return 1;
}

tmp->number = *(list->next->next->next).number; // tmp 변수에 4 값을 저장
tmp->next = NULL;

list->next->next = tmp;

 

 

 

4) 연결 리스트 : 시연

💬배열이 정렬되지 않았을 때 검색 소요 시간을 연결리스트의 것과 비교

둘 다 O(n) 

정렬되지 않았기 때문에 모든 노드를 일일이 따라가봐야한다.

 

 

 

5) 연결 리스트 : 트리

💬이진 검색 트리가 정렬되어 있으면 기본 연결 리스트보다 속도가 확실히 빠르다. 하지만 한 노드에 두개의 노드 값을 가져야 하므로 메모리 공간을 많이 차지한다.