자료구조

 데이터는 의미나 목적없이 단순히 수집된 정보로, 해당 데이터를 의미와 목적으로 구분해서 저장할 필요가 있다. 이럴 때 사용되는 개념이 자료구조 개념이다. 자료구조란 데이터를 물리적 또는 논리적으로 구분하여 컴퓨터에 저장하는 방법으로, 알고리즘을 통해 데이터를 구별하는 나열 방식을 코드로 구성한다.

 

자료구조의 종류

 사용자가 데이터를 사용하기 위해서는, 목적에 따라 데이터를 구별하고, 해당 구별된 데이터를 컴퓨터에 종류별로 저장함으로써 메모리의 공간을 확보한다. 그래서 자료구조를 통한 데이터의 구별 방식은 중요하다.

 

 자료구조는 데이터를 저장하기 위해서는 저장공간이 필요하다. 이때 저장공간을 노드라고 하며, 노드는 여러 데이터를 저장해야 하는 경우가 많기 때문에, 구조체를 통해 해당 노드에 어떠한 데이터를 저장할지 결정한다.

 

 노드를 생성할 때, 어떤 구조로 구성되어 있냐에 따라 선형구조와 비선형구조로 나뉜다.

• 선형 구조 : 데이터를 1:1 관계로 하나씩 나열 시킨 구조로, list, stack, queue가 해당 구조에 해당한다.
• 비선형 구조 :  데이터를 1:n 관계로 나열 시킨 구조로, Heap, Tree가 해당 구조에 해당한다.

 

C언어 자료구조의 기본

  모든 언어의 기본이 C언어인듯이 C언어의 자료구조가 모든언어의 기본이 된다. 그래서 C언어의 자료구조에 대해서 알아야 한다.

 언어마다 다르겠지만 C언어의 경우에는 기본적으로 구조체, 포인터로 이루어져 있다.

• 포인터

포인터의 기본

 포인터란 저장공간(변수, 배열)을 선언할 때, 부여받은 메모리 주소를 저장하는 변수로, 주소를 통해 간접적으로 해당 저장공간에 접근하기 위해서 사용한다.

포인터형 * 변수명 = &저장공간; 

 위의 방식은 포인터를 선언하고, 해당 포인터에 변수의 주소를 저장하는 초기화 방식으로, "*"을 통해 해당 변수는 포인터임을 선언하며, "&"연산자를 통해 해당 저장공간의 주소를 저장한다.

 변수를 선언할때 포인터 형을 같이 선언하는데, 해당 포인터 변수를 통해 변수에 값을 저장할 때, 포인터 변수가 받을 값의 형태로, 저장되어있는 주소값의 변수의 자료형을 선언해야 한다.

 

 

• 구조체

구조체 기본

 구조체란 여러 자료형의 변수를 모아만든 사용자 정의 데이터 자료형으로, 속성마다 데이터를 저장할 수 있는 멤버변수와  필드, 멤버변수에 저장하는 데이터인 레코드로 구성되어있다.

구조체 자료형 생성방법(구조체 선언)	구조체 변수 생성방법
struct 구조체명{     자료형 변수명1;  //멤버 변수명1     자료형 변수명2;  //멤버 변수명2 };	struct 구조체명 변수명

 

 

---

자기 참조 구조체와 외부 참조 구조체

 구조체에서 포인터는 구조체 포인터를 사용해서 구조체 변수를 "->"연산자로 간접접근하는 방식으로 사용될 수도 있으며, 구조체의 멤버변수로 사용하는 방법도 존재한다.

#include<stdio.h>

struct point {
	int* x;
	int* y;
};

int main(void) {
	int num1 = 5;
	int num2 = 6;

	struct point p1;

	p1.x = &num1;
	p1.y = &num2;

	printf("num1, num2 = %d, %d", num1,num2);
	printf("*p1.x, *p1.y = %d, %d", *p1.x, *p1.y);

	return 0;
}

• 자기 참조 구조체

 자기참조 구조체란 자신과 동일한 구조체를 가리키는 포인터 변수를 멤버 변수로 가지는 구조체로, 같은 구조체로 만든 변수를 연결할 때 사용한다.

struct 구조체명 {    int a;    struct 구조체명* b;  };

include<stdio

struct student {
	char UID[10];
	char name[10];
	struct student* link;
};

int main() {
	struct student std1 = { "20192255","Kim",NULL};
	struct student std2 = { "20192256","Lee",NULL};
	struct student std3 = { "20192257","Park",NULL};

	std1.link = &std2;
	std2.link = &std3;
	std3.link = &std1;

	printf("%s, %s \n", std1.UID, std1.name);
	printf("%s, %s \n", std1.link->UID, std1.link->name);
	printf("%s, %s \n", std1.link->link->UID, std1.link->link->name);

	return 0;
}

 위의 코드는 자기 참조 구조체를 이용한 코드로, student 구조체를 통해 만든 std2변수가 student구조체를 통해 만든 std1변수의 link변수에 저장되는 것을 확인 할 수 있다. 이를 그림으로 표현하면 다음과 같다.

 

• 외부 참조 구조체

 외부 참조 구조체란 자신과 다른 구조체를 가리키는 포인터 변수를 멤버 변수로 가지는 구조체로, 다른 구조체로 만든 변수를 연결할 때 사용한다.

struct 구조체명 1 {    int a;  }; struct 구조체명 2 {    int a;    struct 구조체명 1* b;  };

struct point{
	int x;
	int y;
};

struct student {
	char name[10];
	struct point* link;
};

int main() {
	struct student std1 = {"Lee",NULL };
	struct student std2 = {"kim",NULL };
	struct point p1 = { 30,40 };
	struct point p2 = { 50,60 };

	std1.link = &p1;
	std2.link = &p2;
	

	printf("std1.name: %s, std1.link->x: %d, std1.link->y: %d \n", std1.name, std1.link->x, std1.link->y);
	printf("std2.name: %s, std2.link->x: %d, std2.link->y: %d \n", std2.name, std2.link->x, std2.link->y);

	return 0;
}

 위의 코드는 외부 참조 구조체를 이용한 코드로, point구조체를 통해 만든 std1,std2 변수가 point구조체를 통해 만든 p1,p2변수의 주소를 link 포인터 변수에 저장되는 것을 확인 할 수 있다. 이를 그림으로 표현하면 다음과 같다.