6. 자료구조 1
1) malloc과 포인터 복습
int main(void)
{
int *x; //정수를 가리키는 포인터 변수 x
int *y;
x = malloc(sizeof(int)); //정수 크기 만큼의 메모리를 x에 할당
*x = 42; //그 주소로 가서 42를 할당하라
*y = 13;
}! 오류
why?
x는 주소와 메모리를 할당했고, 역참조 연산자*을 사용해서 그 주소로 간 다음 42를 저장함.
y는 변수에 대한 메모리공간을 할당하지 않았음. int *y 만으로는 쓰레기 값이 있다고 가정.
y는 포인터로만 선언되었을 뿐이지, 어디를 가리킬지에 대해서는 아직 정의가 되지 않음
-->>> 이렇게 포인터를 초기화 시키지 않고 값을 저장하면 임의로 다른 곳을 가리키고 있기 때문에 값 저장시에 오류가 남. 어디에도 위치하지않은 쓰레기 값으로 메모리상에 존재
2) 배열의 크기 조정하기
포인터와 malloc의 개념을 응용해서, 이미 정의된 배열의 크기를 바꾸기
-> 새로운 공간에 큰 크기의 메모리를 다시 할당하고 기존 배열의 값들을 하나씩 옮겨주기
#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);
}- 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;
}
// list가 tmp와 같은 곳을 가리키도록 지정
list = tmp;
// 새로운 list의 네 번째 값 저장
list[3] = 4;
// list의 값 확인
for (int i = 0; i < 4; i++)
{
printf("%i\n", list[i]);
}
//list 의 메모리 초기화
free(list);
}3) 연결 리스트: 도입
- 데이터 구조 중 하나
데이터 구조
: 컴퓨터 메모리를 더 효율적으로 관리하기 위해 새로 정의하는 구조체
일종의 메모리 레이아웃, 또는 지도
연결리스트
배열에서는 각 인덱스의 값이 메모리상에서 연이어 저장.
이와달리
각 값이 메모리상의 여러 군데 나뉘어져 있다고 하더라도 바로 다음 값의 메모리 주소만 기억하고 있다면 여전히 값을 연이어서 읽어들일 수 있음
각 인덱스의 메모리 주소에서 자신의 값과 함께 바로 다음 값의 주소(포인터)를 저장
typedef struct node
{
int number;
struct node *next;
}
node;- node 라는 이름의 구조체는 number 와 *next 두 개의 필드가 함께 정의
- number는 각 node가 가지는 값
- *next 는 다음 node를 가리키는 포인터
4) 연결 리스트: 코딩
#include <stdio.h>
#include <stdlib.h>
//연결 리스트의 기본 단위가 되는 node 구조체를 정의합니다.
typedef struct node
{
//node 안에서 정수형 값이 저장되는 변수를 name으로 지정합니다.
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).numer”와 동일한 의미입니다.
// 즉, 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;
}
}5) 연결 리스트와 배열
연결리스트의 장점
- 유동적인 구조,
- 새로운 값을 추가할 때 다시 메모리를 할당하지 않아도 된다
- 배열과는 다르게 움직일 필요 없음.
연결리스트의 단점
- 임의 접근이 불가능함.
-> 포인터가 가리키는 곳으로 따라가야 함. 중간에 접근 불가. - 연결 리스트의 크기가 n 일때 그 실행 시간은 O(n) -> 배열의 경우 임의 접근이 가능하기 때문에 (정렬 되어 있는 경우) 이진 검색을 이용하면 O(log n)의 실행 시간이 소요 되는 것에 비해서 다소 불리
roundy