[C] 자기 참조 구조체와 연결리스트

자기 참조 구조체

 자기 참조 구조체는 자신과 동일한 구조체를 가리킬 수 있는 포인터 변수를 필드 변수로 가지는 구조체입니다. 형태는 다음과 같습니다.

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

struct Node

{

int a;

struct Node* b; // 자신의 구조체를 가리키는 포인터 변수

};

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

연결리스트

 연결리스트는 컴퓨터 관련 공부나 자격증 공부를할 때 많이 들어보셨을 단어입니다. 연결리스트는 구조체와 포인터를 이용해 유동적으로 데이터를 저장할 수 있는 자료구조로 자기 참조 구조체를 연결해 사용합니다. 아래 그림과 같이 a의 주소만 알고있다면 b와 c에 접근이 가능한 구조입니다.

 struct Node *head;와 같이 구조체를 정의했을 때 위 그림의 a,b,c노드에 접근하는 방법은 아래 표와 같습니다

a.n	head → n
b.n	head → next → n
c.n	head → next → next → n

 

 위의 그림을 봤을때 각 노드는 다음 노드의 주소를 가리킵니다. 마지막 노드는 어떤 주소를 가리킬까요? 마지막 노드는 NULL값을 저장합니다. 이 NULL값은 더이상 연결된 노드가 없음을 의미합니다.

 아래 코드는 정수를 입력받아 연결리스트를 구성해서 출력하고 메모리를 반환한뒤에 종료하는 코드입니다. 반복문에서는 p = p->next; 와같은 문장을 이용해 참조를 이동할 수 있습니다.

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

#include <stdio.h>

#include <stdlib.h>

#pragma warning(disable:4996)

struct Node{

int n;

struct Node *next;

};

void showMenu(); // 반복문안에서 입력을 받기위한 문자열을 출력하는 함수

void printNodes(struct Node* p); // 입력받은 정수를 출력하기 위한 함수

void freeNodes(struct Node* p); // 사용이 끝난 노드의 메모리를 반환하는 함수

int main(){

int flag = 1; // 반복문을 실행하기 위한 변수로 1로 초기화 하고 0이 될때 반복문이 종료됩니다.

int input; // 입력받을 정수

struct Node *head; // 노드의 처음

struct Node *last; // 노드의 끝

struct Node *node; // 추가될 노드의 주소를 임시로 저장할 포인터 변수

head = NULL; // 추가된 노드가 없기때문에 head와 last를 NULL로 초기화

last = NULL;

while (flag){

showMenu();

scanf("%d", &input);

if (input == 0) // 0을입력하면 종료

{

flag = 0;

}

else{

node = (struct Node*)malloc(sizeof(struct Node)); // 구조체 역시 sizeof연산자를 이용할 수 있습니다. 구조체를 동적할당

node->n = input; // 생성된 Node 구조체에 값을 설정합니다.

node->next = NULL;

if (head == NULL) // 연결 리스트가 비어있을 경우, head에 생성된 node 의 주소를 저장

{

head = node;

}

else // 연결 리스트가 비어있지 않을 경우, 마지막 노드의 next에 생성된 node 의 주소를 저장합니다.

  {

last->next = node;

}

last = node; // 연결 리스트에 추가된 node 의 주소를 last 에 저장합니다.

}

}

  // 반복문이 종료되면 printNodes함수와 freeNodes함수를 실행합니다.

printNodes(head); 

freeNodes(head);

}

void showMenu(){

printf("저장할 정수를 입력하세요. \n 종료 0 >");

}

void printNodes(struct Node* p)

{

while (p != NULL){  // 마지막 노드가 아닌 경우

printf("%d\n", p->n); // 노드를출력하고,

p = p->next; // 다음 노드를 가리킵니다.

}

}

void freeNodes(struct Node* p){

struct Node *temp;

while (p != NULL){ // 마지막 노드가 아닌 경우

temp = p; // temp에 p를 저장해서

p = p->next; 

free(temp); // 반환합니다.

}

}

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

 실행 결과는 아래와 같습니다.

* 출처 : 한국기술교육대학교 온라인평생교육원 C 프로그래밍_2 

          스타일 C프로그래밍 저.김종훈,김종진 출.WellBook