[자료구조] 리스트 (연결 리스트 부터 이중 연결 리스트까지)
오늘 알아볼 자료구조는 리스트입니다 :) 리스트란? 순서를 가지고 일렬로 나열한 원소들의 모임으로 데이터 목록을 다루는 자료구조로 기본 연산으로는 삽입, 삭제, 탐색이 있습니다. 리스트 구현 방법 1. 배열 이용 (순차적인 메모리 공간 할당) 2. 연결 리스트 이용 (노드에 분산 저장) 리스트의 연산 init(list) - 리스트 초기화 is_empty(list) - 리스트 공백 유무 검사 is_full(list) - 리스트 포화상태 유무 검사 insert(list, pos, item) - pos 위치에 item 추가 insert_last(list, item) - 리스트 맨 끝에 item 추가 delete(list, pos) - pos 위치의 요소 제거 get_entry(list, pos) - pos 위..
[자료구조] 큐(QUEUE)를 알아보자!
큐 먼저 들어온 데이터가 먼저 나가는 자료구조 -> 선입선출(First-In First-Out) ex) 매표소 대기줄: 먼저 온 사람이 먼저 계산 종류: 선형큐, 원형 큐, 덱... enqueue: 큐의 끝에 데이터 추가 dequeue: 큐 맨 앞의 데이터 제거 & 반환 ● 큐의 연산 init(q) - 큐 초기화 is_empty(q) - 큐가 공백상태인지 검사 is_full(q) - 큐가 포화상태인지 검사 enqueue(q,e) - 큐의 끝에 데이터(e) 추가 dequeue(q) - 큐의 맨 앞 데이터 제거 및 반환 peek(q) - 큐의 맨 앞 데이터 반환 ● 선형큐(Linear Queue) 배열을 이용해 선형 큐를 구현해 보겠습니다. #include #include #define MAX_QUEUE_S..
[자료구조] 스택(stack) 이란?
스택 스택(stack) - 쌓아놓은 더미, 한쪽 끝에서 자료를 넣거나 뺄 수 있는 선형 자료구조, 후입선출(Last-In First-Out)구조로 가장 최근에 들어온 데이터가 가장 먼저 나간다. push - 스택에 데이터 추가 pop - 스택에서 데이터 삭제 ● 스택의 연산 create() - 스택 생성 is_full(s) - 스택이 포화상태인지 검사 is_empty(s) - 스택이 공백상태인지 검사 push() - 스택에 데이터 추가 pop() - 스택에서 데이터 삭제 peek(s) - 요소를 스택에서 제거하지 않고 보기만 하는 연산 ● 배열을 이용한 스택 구현 배열을 이용해 스택을 구현해 봅시다 ㅎㅎ 1차원 배열을 이용해 스택을 구현할 거고, 위에 적은 연산을 각각 함수로 구현할 겁니다! #inclu..
[자료구조] 배열, 구조체 그리고 포인터
구조체 구조체(structure) - 타입이 다른 데이터를 하나로 묶는 방법 ● 구조체 선언 // 구조체 선언 struct person { char name[10]; int age; float height; }; // 구조체 변수 선언 struct person a; ● typedef를 이용한 구조체 선언 (typedef를 사용하면, 구조체 변수를 선언할 때, struct를 붙이지 않아도 됩니다.) // typedef를 이용한 구조체 선언 typedef struct person{ char name[10]; int age; float height; } person; // 구조체 변수 선언 person a; ● 자체참조 구조체 (필드 중에 자기 자신을 가리키는 포인터가 한 개 이상 존재하는 구조체) typed..
[자료구조] 순환(Recursion) with C
순환 순환 (재귀) - 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법 예) 팩토리얼 값 구하기, 피보나치수열, 하노이 탑 등... 순환호출을 사용하여 factorial 구하기 int factorial(int n) { if(n 무한정 호출, 프로그램이 종료되지 않음 순환(recursion)과 반복(iteration)의 차이 순환 - 순환 호출 이용, 순환적인 문제에 자연스러움, 함수 호출의 오버헤드 발생 가능성 반복 - 수행속도가 빠름, 순환적인 문제에 대해서 프로그램 작성이 어려움 모든 순환은 반복으로 바꾸어 작성이 가능합니다 But!!, 매우 불편하거나 어려운 경우가 많습니다. ㅎ 순환(recursion)의 작동 원리 순환호출의 경우 복귀 주소를 시스템 스택에 저장하고..
자료구조에 대한 이해, 자료구조란?
우리 주변을 살펴보면 많은 부분에 있어 규칙이 정해져 있고, 조직화되어 있는 것을 볼 수 있습니다. 이렇게 하는 이유는, 효율적이기 때문인데요. 예를 들면 해야할 일을 리스트로 정리한다던가, 매표소에서 줄을 서서 구매하는 것 등등 여러 가지가 있습니다. (만약 매표소에서 줄을 서지 않고 표를 구매할 수 있다면, 엉망진창이 되겠죠?) 일상에서 볼수 있는 예와 자료구조를 비교해보면 아래와 같이 나타 낼 수 있습니다. 우리가 만들게 되는 프로그램은 적절한 자료구조와 알고리즘으로 이뤄집니다. 그래서 많은 회사들이 자료구조와 알고리즘을 중요하게 생각하는 것이죠! 만약 최대값을 찾는 프로그램을 작성한다고 가정해봅시다. 최댓값을 찾는 프로그램의 경우 다양한 방법이 있겠지만, 배열이라는 자료구조와 순차탐색이라는 알고리..