fishersheep

버블정렬(Bubble Sort) 버블정렬이란 인접한 두개의 데이터를 비교해서 정렬을 진행하는 방법이다. 버블정렬의 성능은 좋은편은 아니다. (정렬알고리즘에서 성능은 비교의 횟수와 이동의 횟수를 근거) ex) 배열에 숫자들을 오름차순으로 정렬할때 첫번째 수를 시작으로 끝의 숫자까지 인접한 수와 비교하고 이동한다. 선택정렬(Selection Sort) 선택정렬이란 제자리정렬 알고리즘중 하나이며, 오름차순으로 정렬한다면 가장 작은 최솟값을 맨앞에 놓고 그 이후의 값들을 하나씩 비교한 후 올바른 값을 선택하여 채워넣는 정렬방법입니다. 버블정렬과 비슷한 성능을 가지고 있다. 삽입정렬(Insertion Sort) 삽입정렬은 정렬대상을 정렬된 부분과 안된부분으로 두 부분으로 나눈 후 정렬안된부분의 데이터를 정렬된부분..

우선순위큐(Priority Queue) 우선순위큐는 선입선출인 큐와는 다르게 이름 그대로 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. 우선순위의 판단기준은 데이터에 근거하며, 목적에 맞게 우선순위를 결정해야 한다. 우선순위큐 구현 방법: 배열기반, 연결리스트기반, 힙(Heap)기반 우선순위큐는 배열 및 연결리스트 보다는 힙으로 구현하는 것이 가장 바람직하다. 힙을 사용해야 이유: 배열과 연결리스트는 우선순위가 낮은 데이터를 삽입할 경우 모든 데이터와 우선순위를 비교해야 한다. 하지만 힙을 사용하면 삽입과 같은 과정을 진행할때 대부분 부모노드와 자식노드사이에서 비교연산이 이루어지기 때문에 힙은 트리의 높이 만큼 비교연산을 진행하면 된다. ->힙을 사용하여 우선순위큐 구현(우선순위큐는 추상적인 개..

트리(Tree) 트리는 비선형 자료구조로서 계층적 관계를 표현하는 자료구조 입니다. 트리구조의 예시: 기업의 조직도, 컴퓨터의 디렉토리 구조 (가지를 늘려가면서 뻗어나가는 특성을 가지는 구조들) 이진트리(Binary Tree) 이진트리는 루트노드를 중심으로 두개의 서브 트리로 나누어지는 트리로서, 나누어진 두개의 서브트리 역시 이진트리여야 합니다. (=자식노드가 2개씩 있는 트리) 이진트리는 노드가 위치할 수 있는 위치에 노드가 없다면 공집합 노드가 있는 것으로 간주합니다. 때문에 서브트리가 하나인 노드가 존재하더라도 이진트리가 될 수 있습니다. 이진트리의 일부 연산은 재귀호출을 사용합니다. 이진트리는 배열기반 및 연결리스트 기반으로 구현할 수 있습니다. 포화이진트리(Full Binary Tree): 모..

덱(Deque) 덱(Deque)은 double - ended queue의 줄인 표현으로서, 양방향으로 데이터의 삽입 및 제거가 가능한 자료구조 이다. 양방향으로 데이터의 이동이 가능한 특성때문에 큐와 스택을 조합한 자료구조로 이해할 수도 있다. 덱의 핵심 기능은 앞으로데이터삽입, 앞으로데이터제거, 뒤로데이터삽입, 뒤로데이터제거 이다. 덱 또한 배열 및 연결리스트로 구현이 가능하지만 덱의 특성상 가장 잘어울리는 것은 양방향연결리스트 이다. 덱(Deque)의 ADT DequeInit: 덱의 초기화를 진행하는 함수로서 제일 먼저 수행되어야 한다. DQIsEmpty: 덱이 비어있는지 확인하는 함수이다. DQAddFirst: 덱의 머리에 데이터를 저장하는 함수로서 매개변수로 전달된 데이터를 저장한다. DQAddL..

큐(Queue)란 큐는 스택과 같은 자료구조로서 스택과의 유일한 차이는 먼저들어간 데이터가 먼저 나오는 구조입니다. 이 구조는 비유하자면 먼저 들어간 차가 먼저 나오는 터널이 있다. FIFO(First-In, First-Out): 선입선출 큐 역시 스택과 마찬가지로 배열 또는 연결리스트를 기반으로한 구현이 가능하다. Queue의 ADT QueueInit: 제일 먼저 호출해야하는 함수로서 큐의 초기화를 수행한다. QIsEmpty: 큐가 비었는지 확인하는 함수이다. 비었으면 TRUE, 비어있지않으면 FALSE를 반환한다. Enqueue: 큐에 데이터를 저장하는 함수로서 매개변수로 전달받은 데이터를 저장한다. 스택의 push와 같은 역활이다. Dequeue: 가장 앞선 데이터를 삭제하는 함수로서, 삭제된 데이..

스택(Stack) 스택이란 선형자료구조의 일종으로서 후입선출 방식의 자료구조이다. (LIFO: Last - In, First - Out) 간단하게 생각하면 한쪽만 뚫려있는 통을 생각하면 된다. 이 통에 무언가를 넣고 뺄때 먼저 들어간건이 나중에 나오게 될 것이다. 스택은 배열 또는 연결리스트를 사용하여 구현이 가능하다. (배열과 연결리스트 모두 선형 자료구조) 스택의 ADT StackInit: 스택의 초기화역활로서, 제일먼저 호출해야한다. IsEmpty: 스택이 비어있는지 확인하는 역활이다. Push: 스택에 데이터를 저장하는 역활이다. 매개 변수로 받은 데이터를 저장한다. Pop: 마지막에 저장된 요소를 삭제 및 반환한다. Peek: 마지막에 저장된요소를 반환하지만 삭제는 하지않는다. 연결리스트로 구현..

CLinkedList.h 노드와 리스트를 정의하고 사용될 함수를 선언하는 헤더파일입니다. #ifndef __C_LINKED_LIST_H__ #define __C_LINKED_LIST_H__ #define TRUE 1 #define FALSE 0 typedef int Data; typedef struct _node { Data data; struct _node* next; }Node; typedef struct _CLL { Node* tail; Node* cur; Node* before; int numOfData; }CList; typedef CList List; void ListInit(List* plist); void LInsert(List* plist, Data data); void LInsertFr..

데이터 3 -> 2 -> 7 -> 8 ->5 를 입력하고 저장하면 역순인 5 -> 8 -> 7 -> 2 ->3 으로 저장되게 하는 예제 #define _CRT_SECURE_NO_WARNINGS #include #include typedef struct _node {//node 구조체 정의 int data; struct _node* next; }Node; int main() { Node* head = NULL;//head 노드 선언 Node* tail = NULL;//tail 노드 선언 Node * cur = NULL;//cur 노드 선언, 저장된 데이터조회를 위한 변수 Node* newNode = NULL;//노드를 추가하기 위한 노드 int readData;//데이터를 저장하기 위한 변수 while (..

추상자료형(Abstract Data Type) 추상자료형 이란 간단히 ADT라고도 불리며, 프로그래밍을 공부하면 볼 수 있는 용어 입니다. ADT는 구체적인 기능의 완성과정을 언급하지 않고 단순히 기능이 무엇인지를 나열한 것 입니다. 리스트 리스트자료구조는 데이터를 나란히 저장하며, 중복된 데이터의 저장을 허용합니다. 순차리스트: 배열기반의 리스트, 메모리의 특성이 정적이다. 연결리스트: 메모리의 동적할당 기반의 리스트 배열기반리스트 배열기반리스트는 연결리스트에 비해서 참조가 쉽습니다. 또한 인덱스 값을 기준으로 사용하여 어느 위치든 한번에 참조가 가능합니다. 배열기반리스트의 단점으로는 삭제과정을 거칠때마다 데이터의 이동이 필요하기 때문에 효율이 떨어지며, 배열의 길이가 초기화할때 정해져야하며 변경이 불..

#define _CRT_SECURE_NO_WARNINGS #include #include #define TRUE 1//TRUE는 1로 정의 #define FALSE 0//FALSE는 0으로 정의 #define LIST_LEN 100//리스트의길이는 100으로 정의 typedef int LData;//int를 LData로 정의 typedef struct __ArrayList//구조체 ArrayList 정의 { LData arr[LIST_LEN]; int numOfData; int curPosition; }ArrayList; typedef ArrayList List; void ListInit(List* plist) {//리스트 초기화함수 plist->numOfData = 0; plist->curPositio..