Data Structure - 노드와 연결리스트의 이해(2)

티스토리 뷰

Development/Data Structure

Data Structure - 노드와 연결리스트의 이해(2)

ShinyOcean 2021. 2. 17. 19:04

Data Structure(자료 구조)를 주제로 한 다섯번째 포스팅은 저번포스팅에 이어 자료의 구조중 실제 프로그래밍에서 많이 사용되는 연결리스트를 다루어보겠습니다.

이번 포스팅에서는 리스트를 이용한 예제를 해결해 보겠다 했었는데요, 예제문제는 다음과 같습니다.

"단어 10개이상으로 구성된 연결리스트를 만들고 리버스하여 출력하라"

문제 해결을 시작해 보겠습니다.

먼저 단어를 저장할수 있는 연결리스트를 만들기 위해서,

element를 배열을 포함하는 구조체로 정의했습니다

typedef struct {

char name[100];

}element;

리스트의 Print함수 또한 저장된 문자열을 출력할수 있도록 수정했습니다.

void print_lsit(listnode* head)

{

for (listnode* p = head; p != NULL; p = p->link)

printf("%s->", p->data.name); // %s로 받고 data안의 name을 출력할수 있도록

printf("NULL\n");

}

그리고 연결 리스트를 역순으로 만들기위해 세개의 포인터, p,q,r을 사용하여 연결리스트를 순회하며

링크의 방향을 역순으로 바꾸어 줄수 있게 했습니다.

그림으로 표현하면

이런식으로 각각의 포인터가 이전의 노드로 돌아가며 역순으로 가리키게 했습니다.

이떄 p는 역순으로 만들 리스트

q는 현재 역순으로 만들 노드를 가리키며

r은 이미 역순으로 변경된 리스트를 가리킨다.

r은 q, q는 p를 차례대로 따라간다.

전체 코드)

#define _CRT_SECURE_NO_WARNINGS //strcpy함수 사용을 위한 define

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

typedef struct {

char name[100]; //단어를 저장할 문자열 생성

}element;

typedef struct listnode {

element data;

struct listnode* link; // 연결리스트 생성

}listnode;

void error(char* message)

{

fprintf(stderr, "%s\n",message);

exit(1);

}

listnode* insert_first(listnode* head, element value)

{

listnode* p = (listnode*)malloc(sizeof(listnode));

p->data = value;

p->link = head;

head = p;

return head;

}

void print_lsit(listnode* head)

{

for (listnode* p = head; p != NULL; p = p->link)

printf("%s->", p->data.name);

printf("NULL\n");

}

listnode* reverse(listnode* head)

{

listnode* p, * q, * r; //순회 포인터로 p,q,r을 사용

p = head; //p는 역순으로 만들 리스트

q = NULL; //q는 역순으로 만들 노드

while (p != NULL) {

r = q; //r은 역순으로 된 리스트, r은 q, q는 p를 차례대로 따라간다

q = p;

p = p->link;

q->link = r; //q의 링크 방향을 바꾼다.

}

return q;

}

int main(void)

{

// -----------------그냥 출력------------------------------

listnode* head = NULL;

element data;

printf("---------------단어 연결리스트-------------\n"); 한단어씩 저장, 출력

strcpy(data.name, "나연");