[알고리즘] 기초 데이터구조(1) - 설명

* 가장 기본이되면서, 중요하기 때문에 모르겠으면 알때까지 공부하세요

데이터를 구축하는 방법으로는 배열과 연결리스트가 있다

배열은 인덱스를 이용해 접근하기 때문에, 접근하기가 쉽다

하지만 추가와 삭제의 경우에는 불편하다

중간에 추가를 하는경우, 한칸씩 미뤄줘야하고 / 삭제의 경우에도 한칸씩 땡겨줘야하기 때문이다

1차원배열을 만드는 코드

int *arr = (int*)malloc(sizeof(int)*100)                                                 또는    int arr[100]

2차원배열을 만드는 코드

int **arr = (int**)malloc(sizeof(int*)*100)

for(int i=0; i<100; i++){

arr[i] = (int*)malloc(sizeof(int)*100);                                        또는 int arr[100][100]

}

메모리할당을 통해서 생성을 했다면 해제도 해주어야한다.

1차원배열 메모리해제

free(arr);

2차원배열 메모리해제

for(int i=0; i<100; i++){

free(arr[i]);

}

free(arr);

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

연결리스트에서 접근할 때에는 주로 반복문을 통해 접근한다

따라서 접근의 경우에는 불편하다

하지만 추가와 삭제의 경우 편리하다

주로 구조체를 이용하기때문에

단일연결리스트의 경우

struct node{

int num;

struct node *next;

};

이중연결리스트의 경우

struct node{

int num;

struct node *next;

struct node *prev;

};

이런식으로 만들어서 연결한다

포인터를 잘 공부했다면 이해하기 쉽겠지만, 안된경우 이해하기가 어렵다

글쓴이는 처음에 구조체안에 구조체가 들어간다고 잘못 이해하고 있었는데, 알고보니 그게아니라 말그대로 구조체는 그대로있고 서로 가리켜주는 것이었다

생성의 경우

struct node *new_node = (struct node*)malloc(sizeof(struct node));

메모리해제의 경우(주의점 - 앞이나 뒤에 연결리스트가 있다면, 연결을 바꿔줘야한다)

free(new_node);

연결리스트는 종류에 따라서 단일연결리스트, 이중연결리스트, 원형연결리스트등 여러가지가 있는데, 다 비슷비슷하다

접근을 한쪽으로하냐, 양쪽으로하냐 / 연결이 계속되어있냐 등으로 나뉘어있는 것이다

출처

제목: 알고리즘 원리와 응용

저자: 국형준

출판사: 21세기사