01. 자료구조 lists: array, structure, linked list, stack, queue

01. lists: array, stack, queue, structure, linked list

자료구조, 리스트, 배열, 스택, 큐, 링크드 리스트

---

지난 학기에 배운 내용들이다. 잊은 학생들을 위해 복습 느낌으로 넣은 듯 하다.

 

 

1. Array

 

배열이라고도 부른다. 번호(인덱스)와 번호에 대응하는 데이터들로 이루어진 자료구조를 나타낸다.

자료형이 같은 데이터를 일렬로 나열하는 것이 특징이며, 보통 첫번째 칸의 인덱스는 0부터 시작한다.

아마 c를 배울 때 가장 먼저 배우는 자료구조다.

 

아래와 같은 방식으로 선언을 할 수 있다.

int a[5]; #선언
int a[5] = {0, }; #선언과 초기화
int a[5] = {1, 2, 3, 4, 5}; #선언과 초기화

자료형 이름[개수]

 

처음 배열을 만들게 되면 안에 쓰레기 값이 들어가 있기 때문에, 꼭 초기화를 해줘야 한다. 0으로 초기화 하는 경우,

 

{0, }

 

으로 써주게 되면 자동으로 0으로 초기화가 된다. 다른 수는 적용되지 않는다. 만약, 다른 수로 전체 초기화를 해주고 싶다면 memset 함수를 이용하면 된다. 맨 아래 코드가 실행된다면 다음과 같이 저장이 된다. 위는 그 데이터에 접근하기 위한 인덱스고, 아래가 저장된 데이터다.

array

인덱싱(그 값에 접근) 하는 법은 다음과 같다.

print("%d", a[3]);
a[2] = 5;

a배열은 int형 배열이기 때문에 int서식지정자인 %d를 이용해서 출력할 수 있다. 배열에 다른 수를 넣어주고 싶다면 넣어주고 싶은 인덱스에 다른 수를 대입해 주면 된다. 단 처음에 a[n]으로 선언했다면, 범위는 0부터 n-1까지 임을 잊지 말자.

 

 

2. Structure

 

구조체라고 부른다. 쉽게 말해서 여러 자료형들을 합쳐서 하나의 새로운 자료형을 만드는 방법! 이라고 할 수 있다.

구조체 안에 있는 변수들은 멤버라고 부른다.

 

다음과 같이 정의한다.

struct node {
	int date;
	char name[10];
    int money = 100;
};

struct <tag_name> {

  <type> <member_name1>;

  <type> <member_name2>;

  } ;

 

뒤에 꼭 세미콜론 ; 을 붙여줘야 한다! (뭐 vs에서 tap키 누르면 알아서 만들어 주긴 하는데)

여기서 node가 새로운 자료형의 이름, 그리고 안의 data, name, money가 node의 member가 된다.

 

선언은 다음과 같이 할 수 있다.

struct node a;
struct node a = {10, 'nana', 200};

선언만 해도 되고, 선언과 초기화를 같이 할 수도 있다. 심지어는 정의, 선언, 초기화를 동시에 할 수도 있다.

struct node {
	int date;
	char name[10];
    int money = 100;
} a = {10, 'nana', 100};

더 자세한 부분은 아래 링크를 참조하면 좋을 것 같다.

https://dojang.io/mod/page/view.php?id=407

C 언어 코딩 도장: 48.0 구조체 사용하기

 

 

3. linked list

 

구조체 + 동적 할당의 합작으로 이뤄지는 연결 리스트! 너무 헷갈려서 처음 배울 때 머리 깨지는 줄 알았다.

어느정도 크기의 배열을 잡아야 할지 모르겠을 때, 사용하면 좋다.

 

연결리스트는 노드가 데이터를 담은 채로 연결되어 있는 자료구조다. 데이터와 포인터를 갖고 있는 노드들이 연결되어 있는데, 노드의 포인터는 다음 노드를 가리킨다. 즉, 노드 = 데이터 + 포인터 인데 그 노드 안의 포인터들이 다음의 노드를 가리키는 셈이다. 보통, head라는 포인터가 첫번째 노드를 가리키고, 마지막 노드인 tail의 포인터는 NULL을 가리킨다.

연결리스트는 배열과는 다르게 중간에 삽입하거나 제거할 때, 원소를 움직여줄 필요가 없다. 대신, n번째 원소를 찾을 때, 앞에서 부터 훑어야 하기 때문에 찾는 과정이 오래 걸린다.

아래는 코드다.

---

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

typedef struct NODE {
	int key;
	struct NODE* next;
}Node;

typedef Node* Head; //head를 node의 포인터 변수로 변환.

Node* findLostNode(Head head);



//마지막 노드 찾기
Node* findLostNode(Head head) {
	if (head == NULL)return NULL;
	else {
		Node* node = head;
		while (node->next != NULL) {
			node = node->next;
		}
		return node;
	}
}

//리스트가 비어있는지 확인
int isEmpty(Head head) {
	if (head == NULL)return 1;
	else return 0;
}

//모든 노드 출력
void printAllNode(Head head) {
	if (isEmpty(head))return;
	else {
		NODE* node = head;
		while (node) {
			printf("%d\n", node->key);
			node = node->next;
		}
	}
}

//검색
NODE* searchNode(Head head, int key) {
	Node* node = head;
	if (isEmpty(head))return NULL;
	else {
		while (node) {
			if (node->next->key == key) {
				return node; //찾는 노드의 앞 노드를 반환
			}
			node = node->next;
		}
	}
	return NULL;
}


//맨 뒤에 삽입
void insertLast(Head head, int key) { //나중에 유연하게 대처하려면 Node넘겨주는게 좋음.
	Node* lastnode = findLostNode(head);
	Node* newNode = (NODE*)malloc(sizeof(NODE));
	newNode->key = key;
	newNode->next = NULL;

	if (lastnode == NULL) {
		head = newNode;
	}
	else {
		lastnode->next = newNode;
	}
}

//맨 앞에 삽입
void insertfirst(Head head, int key) {
	Node* newNode = (NODE*)malloc(sizeof(NODE));
	newNode->key = key;

	if (isEmpty(head)) {
		head = newNode;
		newNode->next = NULL;
	}
	else {
		newNode->next = head->next;
		head = newNode;
	}
}

//맨 뒤에 삭제
void deleteLast(Head head) {
	Node* node = head;
	Node* preNode = head;
	if (isEmpty(head))return;
	else {
		while (node->next != NULL) {
			preNode = node;
			node = node->next;
		}
		free(node);
		preNode->next = NULL;
	}
}

//맨 앞에 삭제
void deletefirst(Head head) {
	if (isEmpty(head))return;
	else {
		head = head->next->next;
		free(head->next);
	}
}

//삭제하고 싶은 얘 삭제(중간에 노드 삭제)
void deleteNode(Head head, int key) {
	if (isEmpty(head))return;
	NODE* predel_node = searchNode(head, key); //삭제하고 싶은 얘 앞 노드를 받음
	NODE* nextnode = predel_node->next->next;
	free(predel_node->next);
	predel_node->next = nextnode;
}


int main(void) {

	Head head = NULL;

	int key;

	while (1) {
		printf("=================\n");
		printf("1. 앞에 노드 삽입\n");
		printf("2. 중간에 노드 삽입\n");
		printf("3. 뒤에 노드 삽입\n");
		printf("4. 앞에 노드 삭제\n");
		printf("5. 중간에 노드 삭제\n");
		printf("6. 뒤에 노드 삭제\n");
		printf("7. 리스트 출력\n");
		int num;
		scanf("%d", &num);

		switch (num) {
		case 1:
			printf("앞에 입력하고 싶은 data를 입력하세요 : ");
			scanf("%d", &key);
			insertfirst(head, key);
			break;
		case 2:
			printf("중간에 입력하고 싶은 data를 입력하세요 : ");
			scanf("%d", &key);
			break;
		case 3:
			printf("끝에 입력하고 싶은 data를 입력하세요 : ");
			scanf("%d", &key);
			insertLast(head, key);
			break;
		case 4:
			deletefirst(head);
			break;
		case 5:
			int key;
			printf("삭제하고 싶은 data를 입력하세요 : ");
			scanf("%d", &key);
			deleteNode(head, key);
			break;
		case 6:
			deleteLast(head);
			break;
		case 7:
			printAllNode(head);
			printf("\n");
			break;
		default:
			return 0;
		}
	}
}

---

 

4. Stack

 

스택이라고 읽고, 프링글스 통이라고 본다!

 

이 자료형은 후입 선출, Last in First out, LIFO다. 마치 프링글스 통 처럼, 먼저 들어간게 맨 나중에 나오고, 나중에 들어간게 맨 먼저 나온다고 생각하면 된다.

 

들어가는 것을 push, 나오는 것을 pop이라고 한다.

 

스택의 특성을 시각적으로 나타내 보았다. 정말 프링글스 통이랑 똑같다. 프링글스 먹고싶네...

Stack

C에서 스택을 만드는 방법은 두가지가 있는데, 배열을 이용하는 것과 연결리스트를 이용하는 것이다.

먼저 배열을 이용해 stack을 만든 코드이다. 최대 크기는 5로 설정했다.

---

#include <stdio.h>
#define max 5
int ds[max];
int top = -1;

int get(int*);
int put(int);
int is_full();
int is_empty();
void printall();

int main(void) {
	int is_while = 1;
	while (is_while) {
		printf("1. put\n2. get\n3. is_full\n4. is_empty\n5. printall\n");
		int n, ck;
		int item = NULL;
		scanf("%d", &n);

		switch (n) {
		case 1:
			scanf("%d", &item);
			put(item);
			break;
		case 2:
			ck = get(&item);
			if(ck==0) printf("%d\n", item);
			break;
		case 3:
			is_full();
			break;
		case 4:
			is_empty();
			break;
		case 5:
			printall();
			break;
		default:
			is_while = 0;
			break;
		}
	}
}

int get(int *item) {//pop
	if (is_empty()) {printf("stack is empty!\n");  return -1;}
	*item = ds[top];
	top--;
	return 0;
}

int put(int newitem) { //push
	if (is_full()) { printf("stack is full!\n");  return -1; }
	top++;
	ds[top] = newitem;
	return 0;
}

int is_full() {
	if (top == max-1)return 1;
	else return 0;
}

int is_empty() {
	if (top == -1)return 1;
	else return 0;
}

void printall() {
	for (int i = 0; i <= top; i++) {
		printf("%d ", ds[i]);
	}
	printf("\n");
}

---

그런데 배열로 스택을 만들면 최대 크기 이상은 넣어줄 수가 없다는 문제점이 있다. 이를 보완하기 위해 연결리스트로 만든 스택이 있다. 

 

다음은 연결리스트를 이용해 Stack을 만든 코드이다.

---

#include <stdio.h>
#include <stdlib.h>
struct node {int key; struct node* next;}; //연결리스트를 위한 구조체

void addElement(int);
void push(int);
void pop();
void print_all();
void empty();

struct node* head = NULL;
int top = -1;

int main(void) {
	int is_true = 1, ck, value; //while을 계속 돌릴 변수 is_true
	while (is_true) {
		printf("Enter command (1.push / 2.pop / 3.empty / 4.print all)? ");
		scanf("%d", &ck);
		switch (ck) {
		case 1: //push
			printf("push value? ");
			scanf("%d", &value);
			push(value);
			break;
		case 2: //pop
			pop();
			break;
		case 3: //empty ( all free )
			empty();
			break;
		case 4: //print
			print_all();
			break;
		default: //이 외의 수가 들어왔을 시, 종료.
			is_true = 0;
			break;
		}
	}

}


void addElement(int key)
{
	//노드를 새로 만들어서 값을 넣어주고 마지막에 NULL을 줌
	struct node* newnode = (struct node*)malloc(sizeof(struct node));
	newnode->key = key; 
	newnode->next = NULL;

	struct node* ptr = head;

	if (head == NULL) { //top == -1일 때, stack에 들어가는 첫번째 값 일때
		head = newnode;
		return;
	}

	while (ptr->next != NULL) { ptr = ptr->next; } //stack에 이미 값이 있을 때 마지막 노드까지 찾아감.
	ptr->next = newnode; //마지막 노드 next와 새로만든 노드를 연결
}

void push(int k) {
	if (top == 4) { //stack이 꽉 찼을때
		printf("Cannot push anymore\n");
		return;
	}
	top++;
	addElement(k); //stack에 값을 넣어주는 addElement호출
}

void pop() {
	if (top == -1) { //stack이 비어있을 때
		printf("Stack is empty now\n");
		return;
	}

	top--;
	struct node* ptr = head;
	if (top == -1) { //stack에 요소가 1개만 남아있을 경우!
		printf("%d\n", ptr->key);
		free(ptr);
		head = NULL; //이제 stack에 아무것도 없음.
		return;
	}

	while (ptr->next->next != NULL) {ptr = ptr->next;} //그 외의 경우
	printf("%d\n", ptr->next->key);
	free(ptr->next); //마지막 노드 프리해줌
	ptr->next = NULL; 
	return;
}

void print_all()
{
	struct node* ptr;	// 내가 처리하고(가리키고) 있는 노드
	ptr = head;

	while (ptr != NULL) { //하나씩 프린트하면서 ptr이 뒤로 옮겨감.
		printf("%d ", ptr->key);
		ptr = ptr->next;
	}
	printf("\n");
}

void empty() {
	if (top == -1)return; //이미 비어있다면 걍 리턴
	top = -1; //이제 비니까 -1넣어줌.
	struct node* ptr = head;
	struct node* temp;
	while (ptr->next != NULL) { //하나씩 훑으면서 free
		temp = ptr;
		ptr = ptr->next;
		free(temp);
	}

	head = NULL; //가진게 없는 head에는 NULL을 줌
}

---

C에서는 이렇게 코드를 직접 짜야하지만, C++ 같은 경우 STL라이브러리의 <stack>을 사용하면 손 쉽게 스택 자료구조를 이용할 수 있다.

 

 

5. Queue

 

큐는 마치 호스같다. 들어가는 입구와 나가는 입구가 정해져 있다! 그런데 통로가 앞지를 수는 없으니, 먼저 들어가면 먼저 나오고, 나중에 들어가면 나중에 나온다! 즉, 선입 선출, First in Fisrt out, FIFO 구조라고 할 수 있다.

 

들어가는 것을 enqueue, 나오는 것을 dequeue라고 한다.

 

큐를 시각적으로 나타내보았다.

Queue

C에서 큐를 만드는 방법은, 스택과 마찬가지로 배열과, 연결리스트를 이용해서 만들 수 있다.

 

먼저 배열을 이용해서 만든 코드인데, 단순히 배열을 이용해서 만들게 된다면 만약 큐에 5번 데이터를 넣어버린다면, 다시 뺀다고 해도 여러번 쓸 수 없는 코드가 되어버린다. 이를 방지하기 위해 mod(%)를 이용해서 원형 큐로 만들게 된다면,  다음과 같이 짤 수 있다.

---

#include <stdio.h>

int ds[5] = { 0, };
int front = 0, back = 0;

int is_full() {
	if (back - front == 5) return 1;
	else return 0;
}
int is_empty() {
	if (front == back) return 1;
	else return 0;
}

void print_all() {
	int i = front;
	while (i != back) {
		printf("%d ", ds[i%5]);
		i++;
	}
	printf("\n");
}

int get(int* k) { //dequeue
	if (is_empty()) {
		printf("queue is empty\n");
		return 1;
	}
	*k = ds[front%5];
	front++;
	return 0;
}

int put(int newitem) { //enqueue
	if (is_full()) {
		printf("queue is full\n");
		return 1;
	}
	ds[back%5] = newitem;
	back++;
	return 0;
}


void main() {

	int is_true = 1;
	while (is_true) {
		printf("enter (1. put/ 2.get/ 3.printall) ");
		int n, item, ck;
		scanf("%d", &n);

		switch (n) {
		case 1:
			printf("what value? ");
			scanf("%d", &item);
			put(item);
			break;
		case 2:
			ck = get(&item);
			if(ck==0) printf("%d\n", item);
			break;
		case 3:
			print_all();
			break;
		default:
			is_true = 0;
			break;
		}
	}
}

---

다음은 연결리스트를 이용해서 만든 큐인데, 연결리스트로 큐를 만들 땐 어디를 머리로 할지 생각을 잘 해야 한다. 연결리스트는 head와 tail이 있는데, 큐의 입구를 head로 할지, 출구를 head로 할 지 잘 생각해야 한다는 말이다.

 

내 생각엔, 출구를 head로 하는 것이 더 효율적이고 시간을 절약할 수 있다.

즉, 다음과 같다고 생각하면 편하다. 만약 head가 입구고 tail이 출구라면, dequeue를 할 때, head부터 tail까지 반복문을 돌려야 할 것이다. 하지만, head가 출구라면, dequeue를 할 때 하로 반복문을 돌 필요가 없이 뽑아줄 수 있다. 사실 head뿐만 아니라 tail도 따로 포인터를 만들어 준다면, 어떻게 하던 상관은 없다.

 

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


typedef struct _node {
	int key;
	struct _node *next;
} node_t;

node_t *head = NULL, *tail = NULL;

void insert_node(int n) {
	node_t *new_node = (node_t*)malloc(sizeof(node_t));

	new_node->key = n;
	new_node->next = NULL;

	if (head == NULL) {
		head = new_node;
		tail = new_node;
	}
	else {
		tail->next = new_node; //원래 마지막 노드의 포인터
		tail = new_node; //tail
	}
}

int delete_node() {
	node_t *node;
	int r;

	if (head == NULL) {
		return -1;
	}

	node = head;
	head = head->next;

	if (head == NULL) {
		tail = NULL;
	}

	r = node->key;
	free(node);
	return r;

}

 

---

reference

https://ko.wikipedia.org/wiki/%EB%B0%B0%EC%97%B4

https://dojang.io/mod/page/view.php?id=407

문제로 풀어보는 알고리즘(황인욱, 김용혁)