School/DataStructure

Data-Structure - Linked list ( Applications )

Polynomials 우리는 다음과 같은 polynomials를 구조체를 통해서 구현을 했었습니다. 근데 이는 linked-list를 통해서도 더욱 효율적이고 간편하게 만들 수 있습니다. 바로 이렇게 생긴 구조체와 자기참조 구조체를 통해서 linked-list를 구현하면 됩니다. data칸에 float형 coef(계수)와 int형 expon(지수)를 넣고 다음 linked-list를 가리킬 link를 만들어 주면 됩니다. 간단합니다!! 각각의 a, b다항식을 위와같이 linked-list로 표현을 해 주었습니다. 기본적인 추가 규칙은 구조체를 활용해서 간단히 구현했을때와 다른것이 없습니다. 그냥 expon(지수)를 비교해서 각각의 경우에 다르게 처리해 주면 끝입니다. 하지만 linked-list답게 포인..

Data-Structure - Linked Lists

Sequential Representation은 연속적인 노드들의 데이터가 고정된 거리만큼 떨어져서 존재함을 의미합니다. 하지만 임의 데이터의 Insertion(삽입)과 deletion(삭제)가 매우 비용 효율적이지 못한 작업이 됩니다. 즉 삽입과 삭제에 과도한 행동이 필요하다는 것입니다. 하지만 Linked Representation은 메모리의 어디든지 분포할 수가 있습니다. 또한 ordered list와 달리 안의 데이터들이 모두 다 같은 타입일 필요가 없습니다. Linked Representation은 data fields와 다음 노드를 가리킬 link or pointer fields를 가집니다. 이는 Sequential Representation과 다르게 임의의 데이이터의 삽입과 삭제가 매우 빠릅..

Data-Structure - Circular Queues

기존의 queue에는 위와 같은 문제가 있다. 당연히 남는 array의 메모리 공간이 있을테고, 이를 앞으로 다시 땡겨와야 하는 문제가 있다. 이의 시간 복잡도는 O(MQS)인데 무시를 못한다. Circular Queues(1) 기본적인 형태는 위와 같습니다. 또한 동작방식을 정리하자면 아래와 같습니다. Addition을 할 때에는 rear가 움직이고 Deletion을 하면 front가 움직이는 그러한 간단한 구조입니다. 또한 Circular Queue에는 중요한 규칙이 하나 더 있습니다. The position next to MQS-1 is 0 The position that precedes 0 is MQS-1 MQS가 최대 용량, 즉 위의 그림에서는 7이라고 한다면 0~7인덱스중 MQS-1인 6번 i..

Data-Structure - Queue

#include #include #include #define MAX_QUEUE_SIZE 100 #define ERROR_KEY -100 #define MALLOC(p, s) \ if (!((p) = malloc(s))) \ { \ fprintf(stderr, "Insufficient memory"); \ exit(EXIT_FAILURE); \ } #define REALLOC(p, s) \ if (!((p) = realloc(p, s))) \ { \ fprintf(stderr, "Insufficient memory"); \ exit(EXIT_FAILURE); \ } typedef struct { int key; } element; element *queue; int capacity = 1; int rea..