강좌 : 부스트캠프 모두를 위한 컴퓨터과학(cs50 2019)
4. 자료구조
- ide.cs50.io 사이트 이용
✍배열의 크기조정하기
- 일정한 배열이 주어졌을 때 그 크기를 키우기 위해 현재 메모리 위치옆에 메모리를 덧붙이면 기존에 그 위치에 저장되어있는 데이터가 덮어씌워질 수 있다
- 새로운 공간에 큰 크기의 메모리를 다시 할당하고 기존 배열의 값들을 하나씩 옮겨줘야 한다
- 이런작업은
O(n)시간이 걸린다 - NULL은 문자 \0을 뜻하는 NUL과는 다른것이다
NULL : 포인터
#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;
for (int i = 0; i < 4; i++)
{
printf("%i\n",list[i]);
}
free(list);
}realloc
- 위와 동일한 작업을 realloc함수를 통해 조금더 간단히 실행할 수 있다
#include<stdio.h>
#include<stdlib.h>
int main(void)
{
int *list = malloc(3*sizeof(int));
if(list == NULL)
{
return 1;
}
list[0] = 1;
list[1] = 2;
list[2] = 3;
// tmp 포인터에 메모리를 할당하고 list의 값 복사
int *tmp = realloc(list, 4*sizeof(int));
if(tmp == NULL)
{
return 1;
}
tmp[3] = 4;
list = tmp;
for (int i = 0; i < 4; i++)
{
printf("%i\n",list[i]);
}
free(list);
}✍연결리스트
배열은 각 인덱스의 값이 메모리상에서연이어 저장되어있다- 연결리스트는 각 값이 메모리상의 여러군데 나뉘어져 있다고 하더라도 바로 다음값의
메모리 주소만 기억하고 있으면 여전히 값을 연이어서 읽어들일 수 있다 - 배열과 비교해서 연결리스트는 새로운 값을 추가할 때 다시
메모리를 할당하지 않아도 된다는 장점 - 하지만 이런 유동적인 구조는
임의접근이 불가능하다는 단점이 있어O(n)시간이 걸린다 배열의 경우 임의 접근이 가능하기 때문에 정렬되어있을 경우 이진검색을 사용하면O(log n)의 실행시간이 소요되는 것에 비해연결리스트가 다소 불리
도입
- 각 인덱스의 메모리주소에서 자신의 값과 함께 다음 값의 주소(포인터)를 저장
node: 직사각형으로 나타낼 수 있는 메모리 덩어리를 의미
typedef struct node
{
int number;
struct node *next;
}
node;++ typedef struct 대신에 typedef struct node라고 'node'를 함께 명시해 주는 것은, 구조체 안에서 node를 사용하기 위함
코딩
#include<stdio.h>
#include<stdlib.h>
// 연결 리스트의 기본 단위가 되는 node 구조체를 정의한다
typedef struct node
{
// node 안에서 정수형 값이 저장되는 변수를 number로 지정한다
int number;
// 다음 node의 주소를 가리키는 포인터를 *next로 지정한다
struct node *next;
}
node;
int main(void)
{
// list라는 이름의 node 포인터를 정의한다. 연결리스트의 가장 첫번째 node를 가리킬 것이다
// 이 포인터는 현재 아무것도 가리키고 있지 않기 때문에 NULL로 초기화 한다
node *list = NULL;
// 새로운 node를 위해 메모리를 할당하고 포인터 *n으로 가리킨다
node *n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
// n의 number 필드에 1의 값을 저장한다 "n->number"는 "(*n).number"와 동일한 의미이다
// 즉, n이 가리키는 node의 number 필드를 의미하는 것이다
// 간단하게 화살표 표시 '->'로 쓸수 있다 n의 number의 값을 1로 저장한다
n->number = 1;
// n의 다음에 정의된 node가 없으므로 NULL로 초기화한다
n->next = NULL;
// 이제 첫번째 node를 정의했기 때문에 list 포인터를 n 포인터로 바꿔준다
list = n;
// 이제 list에 다른 node를 더 연결하기 위해 n에 새로운 메모리를 다시 할당한다
n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
// n의 number와 next의 값을 각각 저장한다
n->number = 2;
n->next = NULL;
// list가 가리키는 것은 첫번째 node이다
// 이 node의 다음 node를 n 포인터로 지정한다
list->next = n;
// 다시 한번 n 포인터에 새로운 메모리를 할당하고 number과 next의 값을 저장한다
n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n->number = 3;
n->next = NULL;
// 현재 list는 첫번째 node를 가리키고, 이는 두번째 node와 연결되어있다
// 따라서 세번째 node를 더 연결하기 위해 첫번째 node (list)의
// 다음 node(list->next)의 다음 node(list->next->next)를 n 포인터로 지정한다
list->next->next = n;
// 이제 list에 연결된 node를 처음부터 방문하면서 각 number 값을 출력한다
// 마지막 node의 next에는 NULL이 저장되어 있을 것이기 때문에 이 것이 for 루프의 종료조건이 된다
for (node *tmp = list; tmp != NULL; tmp = tmp->next)
{
printf("%i\n", tmp->number);
}
// 메모리를 해제해주기 위해 list에 연결된 node들을 처음부터 방문하면서 free 해준다
while (list != NULL)
{
node *tmp = list->next;
free(list);
list = tmp;
}
}트리
- 연결리스트에서의 각 노드들의 연결이 1차원적으로 구성되어 있다면, 트리에서의 노드들의 연결은
2차원적으로 구성되어있다 - 각 노드는 일정한 층에 속하고, 다음 층의 노드들을 가리키는 포인터를 가지게 된다
- 가장 높은 층에서 트리가 시작되는 노드를
루트라고 부르고 다음 층의 노드들을자식 노드라고 한다 - 나무가 거꾸로 뒤집혀 있는 형태의 트리를
이진 검색 트리라고 한다 - 이진 검색 트리를 활용하였을 때 검색 실행 시간과 노드 삽입 시간은 모두
O(log n)이다
// 이진 검색 트리의 노드 구조체
typedef struct node
{
// 노드의 값
int number;
// 왼쪽 자식 노드
struct node *left;
// 오른쪽 자식 노드
struct node *right;
}
node;
// 이진 검색 함수 (*tree는 이진 감색 트리를 가리키는 포인터)
bool search(node *tree)
{
// 트리가 비어있는 경우 'false'를 반환하고 함수 종료
if (tree == NULL)
{
return false;
}
// 현재 노드의 값이 50보다 크면 왼쪽 노드 검색
else if (50 < tree->number)
{
return search(tree->left);
}
// 현재 노드의 값이 50보다 작으면 오른쪽 노드 검색
else if (50 > tree->number)
{
return search(tree->right);
}
// 위 모든 조건이 만족하지 않으면 노드의 값이 50이므로 'true' 반환
else
{
return true;
}
}
코린이