단순 연결리스트를 이용한 다항식과 계산 구현 8x^12 + (-3x^10) + 10x^6과 같이 여러개인 수식을 다항식이라 부릅니다. 단순 연결리스트를 통해서 다항식을 구현할 수 있습니다. 다항식 구현에는 특수한 헤더 노드가 추가로 사용됩니다. 헤더 노드의 헤드는 리스트의 앞부분을, 테일은 리스트의 끝부분을 가리키도록 합니다. #include #include // 노드의 타입 typedef struct { int coef; int expon; struct ListNode* link; } ListNode; // 리스트 헤더의 타입 typedef struct { int size; ListNode* head; ListNode* tail; } ListType; // 오류 함수 void error(char* me..

연결리스트로 구현된 리스트 연결리스트(Linked List)는 리스트의 항목들을 노드(node)에 분산하여 저장하는 리스트입니다. 노드의 구성으로는 데이터 필드와 링크 필드가 있습니다. 데이터 필드 : 리스트의 원소, 즉 데이터 값을 저장하는 곳 링크 필드 : 다른 노드의 주소값을 저장하는 장소 (포인터) 연결리스트의 장점으로는 삽입과 삭제가 용이하며 연속된 메모리 공간이 필요 없고 크기 제한이 없다는 점이 있습니다. 반면에 단점으로는 구현이 어렵고 까다로우며 오류가 발생하기 쉬운 점이 있습니다. 연결리스트의 종류에는 단순 연결리스트, 원형 연결리스트, 이중 연결리스트가 존재합니다. 단순 연결리스트는 가장 끝의 노드는 항상 NULL을 가리키게 되며 원형 연결리스트는 NULL이 위치한 곳이 없습니다. 이중..

리스트 리스트란 n개의 element형으로 구성된 순서 있는 모임을 말합니다. 리스트를 구현하는 방법에는 배열을 이용한 구현과 연결리스트를 이용한 구현이 있습니다. 리스트 Abstract Data Type insert(list, pos, item) ::= pos 위치에 요소를 추가한다. insert_last(list, item) ::= 맨 끝에 요소를 추가한다. insert_first(list, item) ::= 맨 처음에 요소를 추가한다. delete(list, pos) ::= pos 위치의 요소를 제거한다. clear(list) ::= 리스트의 모든 요소를 제거한다. get_entry(list, pos) ::= pos 위치의 요소를 반환한다. get_length(list) ::= 리스트의 길이를 구한..

덱 Deque(Double-ended-queue) 덱(deque)은 double-ended queue의 줄임말로써 후단(rear)으로만 데이터를 삽입했던 기존 선형 큐, 원형 큐와 달리 큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐입니다. 덱에 사용되는 Abstract Data Type ▪ create() ::= 덱을 생성한다. ▪ init(dq) ::= 덱을 초기화한다. ▪ is_empty(dq) ::= 덱이 공백상태인지를 검사한다. ▪ is_full(dq) ::= 덱이 포화상태인지를 검사한다. ▪ add_front(dq, e) ::= 덱의 앞에 요소를 추가한다. ▪ add_rear(dq, e) ::= 덱의 뒤에 요소를 추가한다. ▪ delete_front(dq) ::= 덱..

큐 Queue 나중에 들어온 데이터가 먼저 나가는 스택 자료구조와 달리 큐는 먼저 들어온 데이터가 먼저 나가는 자료구조입니다. 선입선출(FIFO: First-In First-Out) 큐를 사용하는 방식에는 선형 큐, 원형 큐, 덱이 있습니다. 선형 큐 배열을 선형으로 사용하여 구현된 큐이며, 삽입을 계속하기 위해서는 요소들을 이동시켜야 합니다. 데이터를 넣을때마다 번거로움이 있다는 문제점이 있는 방식입니다. 또한 인덱스를 감소하지는 않고 증가만 하면서 사용하는 방식이기에, 실제로 앞부분에는 데이터가 없을 때에도 비어있는 공간을 활용할 수 없기 때문에 비효율적인 부분이 있습니다. #include #include #define MAX_QUEUE_SIZE 5 typedef int element; typedef..

스택을 응용한 예시로는 괄호 검사, 스택의 응용1 : 괄호 검사 프로그램 괄호의 종류에는 대괄호 [ , ] 중괄호 { , } 소괄호 ( , ) 가 있습니다. 프로그램을 구현하기 위해 다음 조건을 만족해야 합니다. 1. 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다. 2. 같은 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다. 3. 괄호 사이에는 포함 관계만 존재한다. 검사가 필요해 보이는 잘못된 괄호 사용의 예시 (a(b) a(b)c) a{b(c[d]e}f) 알고리즘 문자열에 있는 괄호를 차례대로 조사하면서 왼쪽 괄호를 만나면 스택에 삽입하고, 오른쪽 괄호를 만나면 스택에서 삭제한 후 짝이 맞는지를 검사합니다. 이 때, 스택이 비어 있으면 조건1 또는 조건2 등을 위배하게 되고 괄호의 짝이..