안경잡이개발자

728x90
반응형

  스택(Stack)을 구현하는 방법은 크게 단순 배열(Array)을 이용한 방법과 단방향 연결 리스트(Linked List)를 이용한 방법이 있습니다. 이번 시간에는 연결 리스트(Linked List)를 이용한 방법에 대해 간단히 알아보도록 하겠습니다.


※ 스택 선언하기 ※


  스택 선언은 기존의 연결 리스트와 동일하게 진행합니다.


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


#include <stdio.h>

#include <stdlib.h>


typedef struct Node *NodePointer;

typedef struct Node {

int data;

NodePointer next;

} Node;


NodePointer top = NULL;


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


※ 스택에 삽입하기 ※


  스택 삽입도 기존의 연결 리스트와 흡사하게 진행합니다. 다만 단방향이라서 top을 기준으로만 삽입해주면 됩니다.


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


int push(int data) {

NodePointer ptr;

ptr = (NodePointer) malloc(sizeof(Node));

// 컴퓨터에 남은 메모리가 없는 경우 

if(ptr == NULL) {

printf("메모리 할당에 실패했습니다.\n");

return -1;

}

ptr->data = data;

// 스택이 비어있는 경우 

if(top == NULL) {

ptr->next = NULL;

}

// 스택이 비어있지 않은 경우

else {

ptr->next = top;

}

// 새 노드를 최상단 노드로 설정합니다. 

top = ptr;

return 1;

}


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


※ 스택 정보 출력하기 ※


  top부터 출발해서 NULL을 만날 때까지 모든 원소를 출력해주기만 하면 됩니다.


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


void show() {

NodePointer ptr = top;

while(ptr != NULL) {

printf("%d\n", ptr->data);

ptr = ptr->next;

}

}


int main(void) {

push(5);

push(7);

push(3);

show();

return 0;

}


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


  실행 결과는 다음과 같습니다.




728x90
반응형

Comment +0

728x90
반응형

  이번 시간에는 이중 연결 리스트(Double Linked List)에 대해서 알아보도록 하겠습니다. 이중 연결 리스트는 말 그대로 모든 노드가 이전 노드와 다음 노드에 대한 정보를 모두 저장하고 있는 리스트를 의미합니다. 표현해보면 다음과 같이 표현할 수 있습니다.



※ 선언하기


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


#include <stdio.h>

#include <stdlib.h>


typedef struct Node *NodePointer;

typedef struct Node {

int data;

NodePointer prev;

NodePointer next;

} Node;


NodePointer head, tail;


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


※ 삽입 함수 ※


  삽입이 이루어질 때는 기본적으로 자신이 들어갈 위치를 찾습니다. 저는 data를 기준으로 오름차순 정렬이 이루어지도록 삽입 함수를 작성했습니다. 이 때 i라는 별도의 변수가 사용됩니다. 결과적으로 i는 삽입될 직전의 위치를 알려주는 역할을 수행합니다. 이후에 총 4번 링크를 수행해 새로운 변수를 삽입하게 됩니다. 그 형태는 다음과 같습니다.



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


void insert(int data) {

NodePointer i, element;

i = head->next;

while(i->data <= data && i != tail)

i = i->next;

element = (NodePointer) malloc (sizeof(Node));

element->data = data;

i->prev->next = element;

element->prev = i->prev;

i->prev = element;

element->next = i;

}


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


※ 출력하기 ※


  출력할 때는 head의 next부터 하나씩 tail에 도달하기 전까지 노드를 방문해 출력하면 됩니다.


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


void show() {

NodePointer i;

i = head->next;

while(i != tail) {

printf("%d ", i->data);

i = i->next;

}

}


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


※ 실제로 사용하기 ※


  초기 상태를 다음과 같이 설정해주어야 한다는 것만 잊지 않으시면 됩니다.



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


int main(void) {

head = (NodePointer) malloc (sizeof(Node));

tail = (NodePointer) malloc (sizeof(Node));

head->next = tail;

head->prev = head;

tail->next = tail;

tail->prev = head;

insert(7);

insert(1);

insert(8);

show();

return 0;

}


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


  실행 결과는 다음과 같습니다.



728x90
반응형

Comment +0

728x90
반응형

  연결 리스트(Linked List)포인터를 이용한 선형 구조로서 다양한 종류가 있습니다. 대표적인 것이 선형 리스트, 원형 리스트, 연결 스택, 연결 큐 등이 있습니다. 연결 리스트는 일반적으로 시험 문제로 출제가 될 때 실제 소스코드 구현과 관련한 문제가 출제된다는 점에서 포인터(Pointer)를 활용한 실질적인 구현 방법에 대해서 이해하고 있으셔야 합니다. 다만 이후에 트리(Tree) 구조 등과 관련한 개념에서는 실질적인 구현을 물어보지는 않고 그 동작 원리에 대해서만 자세히 물어본다는 특징이 있습니다.


  사실 연결 리스트는 단일 연결리스트만 확실히 이해해도 다른 것들은 무난하게 넘어가실 수 있습니다. 대표적인 단일 연결 리스트(Singly Linked List)의 예제에 대해서 알아보도록 합시다.


※ 삽입 함수 ※


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


struct Student {

int id; /* 학번 */

int score; /* 학생 성적 */

struct Student *next; 

};


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

  위와 같이 하나의 학생(Student)이라는 노드를 정의해봅시다. 이를 단일 연결리스트로 표현하면 다음과 같은 형태가 될 것입니다.



  삽입 함수는 매우 기본적인 로직을 따릅니다. 단순히 자신이 들어갈 위치까지 계속해서 넘어가다가 들어갈 위치를 찾으면 비로소 그 때 들어가면 됩니다. 기본적으로 사용자 정보들은 학번을 기준으로 오름차순으로 정렬되고, 동일한 학번은 입력되지 않는다고 했을 때 삽입(Insert) 함수는 다음과 같이 작성될 수 있습니다.


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


void insert(struct Student **head, int id, int score) {

struct Student *prevptr; // 삽입하려는 위치의 직전 노드 

struct Student *ptr; // 삽입하려는 위치의 노드

struct Student *element; // 삽입하려는 노드

element->id = id;

element->score = score;

element->next = NULL;

// 리스트가 비어있는 경우 

if((*head) == NULL) {

(*head) = element;

return;

// 리스트가 비어있지 않은 경우 

prevptr = NULL;

ptr = (*head);

while(ptr != NULL) {

// 들어갈 위치를 찾지 못한 경우 

if(ptr->id < id) {

prevptr = ptr;

ptr = ptr->next;

}

// 들어갈 위치를 찾은 경우 

else {

// 첫 번째 원소로 들어가는 경우 

if(prevptr == NULL) (*head) = element;

// 첫 번째 원소로 들어가지 않는 경우 

else prevptr->next = element;

element->next = ptr;

return;

}

}

// 마지막 원소로 들어가는 경우

ptr->next = element; 

}


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


※ 역체인 ※


  역체인(Reverse Chain)은 연결리스트를 뒤집는 함수입니다. 만약 1부터 4까지 데이터가 노드로 연결이 되어있다면 다음과 같이 4부터 1까지 데이터가 노드로 연결이 되도록 바꾸는 과정이 역체인 과정이라고 할 수 있습니다.



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


typedef struct Node *NodePointer;

typedef struct Node {

int data;

NodePointer next;

};


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


  위와 같이 노드가 선언이 되어있다고 했을 때 역체인 함수는 다음과 같이 구현할 수 있습니다.


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


void reverse(NodePointer *head) {

NodePointer one, two, three;

int cout = 0;

two = NULL;

one = three = *head;

while(three != NULL) {

three = three->next;

// 실질적으로 역체인이 수행되는 라인 

two->next = one; 

one = two;

two = three;

}

}


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

  처음 보았을 때는 어렵게 느껴질 수 있는데 간단히 생각해보면 다음과 같이 동작하는 겁니다. 연결되어있는 링크의 위치를 반대로 뒤집으려면 총 세 개의 변수가 필요한데 one, two, three 변수를 계속해서 오른쪽으로 이동시켜가며 역으로 연결해주는 거에요.





728x90
반응형

Comment +0