포인터 (Pointer)
메모리의 주소값을 저장하는 변수이다. 이 변수에 어떤 값의 주소를 제공해주면 해당 주소를 가리키고, 이를 따라 접근도 가능하다. char형 변수는 문자를 저장하고, int형 변수는 정수를 저장하는 것처럼 포인터는 주소값을 저장한다.
포인터의 연산자는 주소 연산자(&), 참조 연산자(*)로 나뉜다.
- 주소 연산자 : 변수의 이름 앞에 사용하여 해당 변수의 주소값을 반환
- 참조 연산자 : 포인터의 이름이나 주소 앞에 사용하여 포인터에 가리키는 주소에 저장된 값을 반환
#include <stdio.h>
int main(){
int a = 1;
printf("%x", &a);
return 0;
}
결과 : 6fdff118
주소 연산자를 알아내기 위해서 변수 이름 앞에 '&'를 붙여 출력했다. 변수 a는 메모리 주소 6fdff118에 저장되어 있다. 이는 메모리 주소이기 때문에 절대값이 아니고 컴퓨터마다 다르다. 6fdff118 주소로 찾아가면 1이 저장되어 있다. %x는 서식지정자로 부호없는 16진정수를 의미한다.
타입* 포인터이름 = &변수이름;
타입* 포인터이름 = 주소값;
int x = 1;
int *ptr = &x;
int *pptr = &ptr;
포인터는 타입* 포인터이름 형태로 선언한다. 타입이란 포인터가 가리키고자 하는 변수의 타입을 명시하고, 포인터이름은 포인터가 선언된 후에 포인터에 접근하기 위해 사용된다. 포인터를 선언한 후 참조 연산자를 사용하기 전에 포인터는 반드시 초기화 되어 있어야 한다. 그렇지 않으면 의도치 않은 메모리의 값을 변경할 수도 있기 때문이다. 위 코드처럼 포인터의 선언과 동시에 초기화를 해주는 것이 좋다.
ptr 변수는 변수 x의 주소값을 가리키고 있다.
이때 포인터 변수의 주소는 &ptr이 된다.
#include <stdio.h>
int main(){
int a = 1;
printf("%d", a); // 1
a = 2;
printf("%d", a); // 2
return 0;
}
위 코드는 a 변수에 2를 재할당 해준 것이다. 포인터를 이용하여 재할당할 수도 있다.
#include <stdio.h>
int main(){
int a = 1;
printf("%d", a); // 1
int *ptr = &a;
*ptr = 2;
printf("%d", a); // 2
return 0;
}
ptr은 a의 메모리상 주소를 가리키고 있는데 해당 주소로 가서 그 주소에 해당하는 값을 2로 바꿨기 때문에 재할당과 같은 결과를 얻을 수 있다. 이렇게 메모리상의 주소를 알고 있으면 즉 포인터 변수를 이용하면 언제든 해당 값을 변경시킬 수 있다.
포인터 변수의 크기는 모두 동일하다. 32비트 시스템에선 4바이트, 64비트에선 8바이트이다. 하지만 자료형에 따라 선언이 달라지는 이유는 가리키는 주소가 어떤 자료형을 갖고 있는지 알려주기 위함이다. int형은 4바이트만큼 차지하고, double은 8바이트씩이므로 int보다 4바이트 더 읽어들여야 한다.
앞서 말했듯이 int형 데이터는 4바이트의 크기를 차지하지만 주소값은 시작 주소 1바이트만을 가리킨다. 만약 포인터에 1을 더하면 주소값은 어떻게 될지 예상해보자.
#include <stdio.h>
int main(){
int a = 3;
int* ptr = &a;
printf("%p\n", ptr);
ptr = ptr + 1;
printf("%p", ptr);
}
각각의 출력은 0x16fdff11c, 0x16fdff120이고 이를 알아보기 쉽게 10진수로 변환하면 6171914528, 6171914524이다. 즉 int 자료형의 크기였던 4바이트만큼 늘어난 주소값으로 변경이 되었다. 만약 double 자료형으로 했다면 1을 더했을 때 8바이트씩 더해졌을 것이다. 포인터의 이러한 특성을 사용하여 배열을 순회할 수 있다. C언어에서 배열은 연속적인 메모리 공간을 가지므로 int 배열이라면 4바이트씩 연속적으로 할당되어 있다는 말이다.
#include <stdio.h>
int main(){
int arr[] = {1, 2, 3, 4, 5};
for (int i = 0; i < 5; i++){
printf("%x\n", &arr[i]);
}
}
#include <stdio.h>
int main() {
int arr[] = { 1, 2, 3, 4, 5};
int* ptr = arr;
for(int i = 0; i < 5; i++){
printf("%d\n", ptr[i]);
}
}
1
2
3
4
5
배열의 첫번째 요소를 가리키는 ptr을 선언하면 포인터를 통해 일반적으로 배열의 값을 순회하는 것과 똑같은 결과를 얻을 수 있다. 한마디로 포인터를 배열과 동일하게 사용할 수 있다.
#include <stdio.h>
int main()
{
int arr[] = {1, 2, 3, 4, 5};
int* ptr = arr;
printf("%d\n", sizeof(arr));
printf("arr 요소 개수 : %d\n", sizeof(arr) / sizeof(int));
printf("%d\n", sizeof(ptr));
return 0;
}
20
arr 요소 개수 : 5
8
arr 배열의 sizeof 결과는 20이다. int 자료형 하나가 4바이트이기 때문에 요소가 5개 있는 배열 arr의 크기는 4 * 5 = 20 이다. 배열 내부의 요소의 개수를 구하기 위해선 배열이 차지하는 메모리 크기를 해당 자료형의 메모리 크기로 나누는 것이다. 포인터의 sizeof 결과는 8이다. 포인터로 가리키고 있는 것이 배열 첫번째 요소이고, 사용하고 있는 컴퓨터가 64바이트이므로 8바이트만큼 할당된 것이다.
구조체 (Structure Type)
Java, JavaScript를 사용해본 적이 있다면 객체라는 자료형에 익숙할 것이다. C언어를 통해 이와 유사한 형태를 만드는 일종의 클래스같은 개념이 구조체이다. 즉, 하나 이상의 변수를 묶어 그룹화하는 사용자 정의 자료형이다. 이름, 나이, 번호 등을 한번에 연관지어 변수에 담아보자. 이때 구조체에서 필요한 것은 3가지이다.
- 구조체명
- 구조체 멤버 변수
- 구조체 변수
우리의 상황에 대입해보면 구조체명은 새로운 자료형이므로 '사람'이 될 것이고, 구조체 멤버 변수는 이름, 나이, 번호 등이 해당된다. 구조체 변수는 사람1이 될 것이다. struct 키워드를 이용하여 구조체를 정의한다.
struct person
{
char* name;
int age;
char* phone;
};
person이 구조체명, char* name; int age; char* phone;이 구조체 멤버 변수이다. 구조체 변수는 구조체를 사용할 수 있도록 해주는 것으로 구조체 멤버 변수에 접근 가능하게 해준다.
#include <stdio.h>
struct person
{
char name[15];
int age;
char phone_number[14];
};
int main()
{
struct person p;
printf("이름 : ");
scanf("%s", p.name);
printf("나이 : ");
scanf("%d", &p.age);
printf("번호 : ");
scanf("%s", p.phone_number);
printf("이름 : %s, 나이 : %d, 번호 : %s\n", p.name, p.age, p.phone_number);
return 0;
}
struct person p; 를 구조체 변수라고 한다. 이를 이용하여 구조체 멤버 변수를 초기화해서 사용할 수 있다.
이중 연결 리스트 (Doubly Linked List)
단방향 연결 리스트와 달리 양방향으로 데이터에 접근이 가능하다. prev, next라는 2개의 양방향을 가리키는 포인터를 가지는 자료구조이다. prev는 이전의 노드를 가리키는 포인터, next는 다음 노드를 가리키는 포인터이다. 또한 처음을 가리키는 노드인 Head, 마지막을 가리키는 노드인 Tail을 가진다. 굉장히 직관적인 이름이다.
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
struct Node* head;
Node라는 구조체를 만들고 구조체 멤버 변수로 저장할 data, 이전과 다음의 노드를 가리키는 포인터 객체 next, prev가 존재한다. 또한 head로 사용할 Node를 하나 만든다.
struct Node* CreateNode(int x) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = x;
newNode->prev = NULL;
newNode->next = NULL;
printf("변수 data의 시작주소 = %d\n",&newNode->data);
printf("포인터변수 prev 시작주소 = %d\n",&newNode->prev);
printf("포인터변수 next 시작주소 = %d\n",&newNode->next);
printf("포인터 구조체 변수 newNode의 주소 = %p\n",&newNode);
printf("newNode가 가진 구조체의 주소 = %d\n\n",newNode);
return newNode;
}
이중 연결 리스트의 구조체 메모리를 할당하고 초기화 해준다. malloc 함수는 프로그램 실행중에 동적으로 메모리를 할당하는 동적할당을 한다. 당연하게도 Heap 영역에 할당한다. 이 함수를 사용하기 위해서는 <stdlib.h> 헤더파일이 필요하다. 이때 메모리 누수 방지를 위하여 할당한 메모리는 반드시 해제 해줘야 한다. sizeof()는 괄호 안의 자료형을 바이트로 연산해주는 연산자이다. 우리가 이용할 자료형은 Node 구조체이므로 인자로 넣어준다. 마지막으로 새로 만든 Node의 주소값을 반환한다.
void InsertAtHead(int x) {
struct Node* newNode = CreateNode(x);
if(head == NULL) {
head = newNode;
return;
}
head->prev = newNode;
newNode->next = head;
head = newNode;
}
void InsertAtTail(int x) {
struct Node* temp = head;
struct Node* newNode = CreateNode(x);
if(head == NULL) {
head = newNode;
return;
}
while(temp->next != NULL) temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
각각 이중 연결 리스트의 헤드 노드를 삽입하는 메소드, 마지막을 가리키는 노드인 Tail을 덧붙이는 메소드이다. 초기에 생성된 헤드는 자기 자신을 가리킨다.
while문에서는 마지막 노드를 검색하고 그 노드를 이제 만든 노드와 붙인다. 이제 생성된 노드를 차례로 출력해보자.
void Print() {
struct Node* temp = head;
printf("Forward: ");
while(temp != NULL) {
printf("%d ",temp->data);
temp = temp->next;
}
printf("\n");
}
양방향이기 때문에 당연히 다시 뒤로 돌아갈수도 있다. 이번엔 역순으로 출력해보자.
void ReversePrint() {
struct Node* temp = head;
if(temp == NULL) return;
while(temp->next != NULL) {
temp = temp->next;
}
printf("Reverse: ");
while(temp != NULL) {
printf("%d ",temp->data);
temp = temp->prev;
}
printf("\n");
}
헤드가 NULL일 때 종료되며, temp의 위치를 맨 끝으로 이동시켜 다시 돌아오면서 출력한다.
int main() {
int node_data[] = {1, 4, 5, 7, 3};
head = NULL;
for(int i = 0; i < 5; i++){
InsertAtTail(node_data[i]);
}
Print();
ReversePrint();
}
Forward: 1 4 5 7 3
Reverse: 3 7 5 4 1
정상적으로 출력된 것을 볼 수 있다.
이진 트리 (Binary Tree)
트리 구조는 리스트처럼 분명한 순회 순서(Traversal Order)를 가지지 않고 여러개의 순회 순서를 정의할 수 있다. 총 4가지 방법으로 정의할 수 있다.
- 전위 순회 (Preorder traverse) : root를 먼저 타는 방법
- 중위 순회 (Inorder traverse) : root를 중간에 타는 방법
- 후위 순회 (Postorder traverse) : root를 나중에 타는 방법
- 층별 순회 (Levelorder traverse) : 층별로 타는 방법
전위, 중위, 후위 순회는 재귀 호출을 이용해야 한다.
중위 순회는 LVR 탐색이 이루어진다. 왼쪽 서브 트리 - 루트 노드 - 오른쪽 서브 트리 탐색이 재귀 호출 방식으로 이루어진다.
root를 기준으로 왼쪽부터 순회한다.
하위의 노드가 있기 때문에 또 D를 root로 삼는다.
결과는 G이다.
그 다음 루트 노드 D이다.
그 다음 오른쪽 노드 H이다.
왼쪽 서브 트리를 다 돌았으므로 다시 루트 노트였던 B를 읽는다.
그 다음 오른쪽 트리인 E를 읽는다. 더 이상 서브 트리의 하위 노드가 없으므로 초기의 루트 노드로 돌아가서 A를 읽는다. 그 다음 C가 루트 노트처럼 되고, 왼쪽 서브 트리가 없으므로 C를 읽는다. 다시 오른쪽 서브 트리로 중위 탐색을 한다. F가 루트 노트처럼 되고, 왼쪽 서브 트리인 I를 읽는다. 이후 루트 노드인 F를 방문한다.
결과적으로 G -> D -> H -> B -> E -> A -> C -> I -> F 순으로 순회를 한다.
#include <stdio.h>
#include <stdlib.h>
typedef struct node_struct{
int data;
struct node_struct *left;
struct node_struct *right;
} node;
node* insert_node(node* root, int value)
{
if(root == NULL)
{
root=(node *)malloc(sizeof(node));
root->left = root->right = NULL;
root->data = value;
}
else
{
if(root->data > value) root->left = insert_node(root->left, value);
else root->right = insert_node(root->right, value);
}
return root;
}
void inOrderTraversal(node* root)
{
if(root)
{
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}
int main()
{
node *root = NULL;
root = insert_node(root, 10);
root = insert_node(root, 4);
root = insert_node(root, 3);
root = insert_node(root, 7);
root = insert_node(root, 1);
root = insert_node(root, 11);
printf("이진트리 중위 순회 : ");
inOrderTraversal(root);
free(root);
return 0;
}
// 이진트리 중위 순회 : 1 3 4 7 10 11
자신을 참조하는 구조체를 만들고, insert_node를 통해 트리에 값을 삽입한다. root->data(부모노드)보다 값이 작으면 왼쪽으로 삽입, 크면 오른쪽으로 삽입한다. 10, 4, 3, 7, 1, 11 순으로 값을 넣고 중위 순회 방법으로 출력을 하면 다음의 결과와 같다.
* 아래의 자료들을 참고하였습니다.
이중 연결 리스트
이중 연결 리스트란? 항상 그렇듯, 설명에 대한 자세한 개요는 나보다 더 좋은 블로거들이 이미 잘 쓰셨다....
blog.naver.com
[C언어 강좌] #13-1 포인터(Pointer)
안녕하세요 파일입니다. 앞에서 다차원 배열을 다룬 뒤로 거점 한 달쯤에 뵙네요! 앞의 연도가 바뀐 건 기분 탓입니다 ㅎㅎ.. 가 아니고 저 글을 작성하고 많이 바빠졌는데 까먹고 강의를 강제
pgh268400.tistory.com
코딩교육 티씨피스쿨
4차산업혁명, 코딩교육, 소프트웨어교육, 코딩기초, SW코딩, 기초코딩부터 자바 파이썬 등
tcpschool.com
[C언어 강좌] #14-1 구조체(Structure Type)
안녕하세요 파일입니다. 드디어 지겹던 포인터가 끝나고 새로운 강좌명으로 상쾌한 시작을 할 수 있게 되었습니다 ! * 하지만 포인터는 포인터가 끝난뒤에도 항상 어디서나 등장합니다.. 여기서
pgh268400.tistory.com
[C언어와 함께 자료구조를] 이진트리 순회 (Binary Tree Traverse)
트리(Tree)구조는 배열과 리스트 처럼 분명한 순회 순서(Traversal Order)를 갖지 않고 여러개의 순회 순서를 정의 할 수 있습니다. 트리(Tree)의 모든 노드들을 한 번씩 중복없이 순회하는 방법 4가지에
hellmath.tistory.com
[C언어][자료구조] 이진 탐색 트리 구현, 전위 순회, 중위 순회, 후위 순회
이진 탐색 트리란(Binary Search Tree)? 이진 탐색 트리는 각각의 노드가 최대 2개의 자식 노드를 가지...
blog.naver.com
댓글