테이터 구조1 실습 5주차(동적 자료구조를 이용한 연결 리스트)

a. 위의 동적 자료구조의 한 개 노드를 표현하는 타입 node를 정의하라.

struct node{
    int val;    //리스트의 값을 저장하는 변수
    struct node* next;  //다음 node의 주소값을 가리키는 포인터
};

 

 

 

b. node 타입에 대한 포인터 first, p, q를 선언하라.

int main(void){
    struct node *first; //node 포인터 변수 생성
    struct node *p, *q;

 

문제에서는 10, 20, 30이 담긴 연결 리스트를 만들어야 하므로 총 3개의 노드가 필요하다.

 

first는 첫번째 노드를 가르키며 p와 q는 다음 노드를 추가할 때 사용된다.

 

 

 

c. node 타입 구조체를 동적으로 생성하고, p가 가리키게 하라.

//void* malloc(size_t size)
p = (struct node*)malloc(sizeof(struct node));  //p에 메모리를 할당

 

p에 동적 메모리를 할당하기 위해 malloc() 함수를 사용하였다. 

해당 함수를 사용하기 위해서는 stdlib.h 이라는 라이브러리 함수를 호출해야 한다.

 

 

 

d. p가 가리키는 구조체를 first가 가리키게 하라.

p -> val = 10;  //val에 10을 저장
p -> next = NULL;   //next를 NULL로 설정하여 리스트의 끝임을 표현

 

첫번째 node의 val에 10을 저장하고 next에는 NULL을 넣어주어 리스트의 끝임을 나타내준다.

 

 

 

e. p가 가리키는 구조체를 first가 가리키게 한다.

first = p;

 

해당 코드를 통해 p가 가리키고 있는 노드를 first가 가리키게 한다.

이같은 이유는 p와 q를 이용하여 리스트를 순회하여 리스트를 추가하기 때문에 첫번째 노드에 first를 따로 선언하여 주소를 가르켜야 한다.

 

 

 

f. node 타입 구조체를 동적으로 생성하고, q가 가리키게 하라.

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

 

p의 동적 메모리를 할당할 때와 동일한 방법을 사용한다.

 

 

 

g. q가 가리키는 구조체의 val 필드에 20을 할당, next 필드에 null을 할당하라.

q -> val = 20;  //val에 20을 저장
q -> next = NULL;   //next를 NULL로 설정하여 리스트의 끝임을 표현

 

q가 가리키고 있는 두번째 노드의 val 값에 20을 저장하고 next에는 NULL을 저장한다.

 

 

 

h. p가 가리키는 구조체의 next 필드가 q를 가리키게 하라.

p -> next = q; //첫번째 노드를 가리키는 p의 next값에 q가 가리키는 주소를 저장

 

이전까지 NULL을 넣어왔던 next에 q의 주소값을 저장한다.

해당 과정을 통해 첫번째 노드에서 포인터 변수 next를 통해 두번째 노드를 가리키게 된다.

 

여기까지 코드를 본다면 노드는 2개까지 만들어졌고, 첫번째 노드를 가리키고 있는 포인터는 first와 p, 두번째 노드를 가리키는 포인터는 q이다.

 

 

 

i. q가 가리키는 구조체를 p가 가리키게 하라.

p = q;

 

위 코드로 첫번째 노드를 가리키는 포인터는 first이며, 두번째 노드를 가리키는 포인터는 p와 q가 된다.

 

 

 

j. node 타입 구조체를 동으로 생성하고, q가 가리키게 하라.

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

 

q에 메모리를 할당해 3번째 노드를 생성한다.

 

 

 

k. q가 가리키는 구조체의 val 필드에 30을 할당하고, next 필드에 null을 할당하라.

q -> val = 30;
q -> next = NULL;

 

q가 가리키고 있는 세번째 노드의 val 값에 30을 저장하고 next에는 NULL을 저장한다.

 

 

 

l. p가 가리키는 구조체의 next 필드가 q를 가리키게 하라.

p -> next = q;

 

두번째 노드의 포인터 next가 q의 주소를 저장한다.

 

 

 

m ~ n. 반복구조를 사용하여 first가 가리키는 구조에 포함된 모든 노드들을 순서대로 방문하면서 노드의 val 값을 출력하라.

p = first;

    while(p != NULL){
        printf("%d ", p -> val);
        p = p -> next;
    }

 

다시 p를 first가 가리키고 있는 첫번째 노드의 주소를 저장하여 해당 노드의 val 값을 출력하고, 해당 노드의 포인터 next가 가리키는 주소를 다시 저장하여 해당 루프를 통해 노드들에 순서대로 접근할 수 있다.

 

 

 

코드 전체

#include <stdio.h>
#include <stdlib.h>

struct node{
    int val;    //리스트의 값을 저장하는 변수
    struct node* next;  //다음 node의 주소값을 가리키는 포인터
};

int main(void){
    struct node *first; //node 포인터 변수 생성
    struct node *p, *q;

    p = (struct node*)malloc(sizeof(struct node));  //p에 메모리를 할당

    p -> val = 10;  //val에 10을 저장
    p -> next = NULL;   //next를 NULL로 설정하여 리스트의 끝임을 표현

    first = p;  

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

    q -> val = 20;  //val에 20을 저장
    q -> next = NULL;   //next를 NULL로 설정하여 리스트의 끝임을 표현

    p -> next = q; //첫번째 노드를 가리키는 p의 next값에 q가 가리키는 주소를 저장

    p = q;

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

    q -> val = 30;
    q -> next = NULL;

    p -> next = q;

    p = first;

    while(p != NULL){
        printf("%d ", p -> val);
        p = p -> next;
    }
    return 0; 
}

 

 

 

실행결과