전체 글 (64) 썸네일형 리스트형 [자료구조] 연결리스트로 구현한 큐(queue) 1. 연결된 큐(Linked queue) 연결리스트로 구현한 스택과 마찬가지로 큐 자료구조를 배열이 아닌 연결리스트로 구현한 것이다. 기본적인 큐 구조는 Last In First Out : LIFO 로 동일하며 큐의 rear단에서 삭제가 일어나고, front단에서 삽입이 일어난다. 2. 삽입 연산(enqueue) 삽입할 경우 큐의 rear의 링크가 새로운 노드를 가리키게 한다. 큐가 공백 상태일 경우에는 새로 만든 노드가 큐의 front, rear 모두 가리키게 한다. //큐가 공백 상태인지 확인하는 함수 int is_empty(LinkedQueueType *q){ return q->front == NULL; } //삽입 함수 void enqueue(LinkedQueueType *q){ int data;.. [자료구조] 배열로 구현한 스택(stack) 1. 스택(stack)이란? - 컴퓨터에서 많이 사용되는 자료구조 중 하나이다. - 후입선출(LIFO : Last In First Out) 구조를 가지고 있다. - 스택의 기본적인 연산으로 스택에 삽입하는 push 연산과 삭제하는 pop 연산이 있다. - 스택의 맨 상단은 stack top이라 하고 맨 하단을 stack bottom이라 한다. 스택의 입출력은 top에서만 일어난다. 즉 스택의 한쪽 끝에서만 삽입, 삭제하는 구조이다. - 함수 호출 시 함수 실행이 끝나면 자신을 호출한 지점으로 다시 돌아가야 하기 때문에 스택을 이용해 복귀할 주소를 저장한다. 2. 배열로 스택 구현하기 - 정수형 배열을 이용하여 스택을 구현해본다. - push, pop 모두 배열의 top에서 이뤄진다. #include #d.. [자료구조] 연결리스트로 구현한 스택(stack) 1. 연결된 스택(Linked Stack) 스택은 First In First Out (FIFO) 형태의 자료구조이다. 연결된 스택은 스택을 배열이 아닌 연결리스트로 구현한 것이다. 겉으로 보기에는 배열로 구현한 것과 별 차이가 없지만 연결리스트로 구현할 경우 동적 메모리 할당을 하기 때문에 메모리 크기에 제한받지 않는다. 다만 구현이 조금 까다롭다(라고 보통 말하던데 까다로운가..? 잘 모르겠다..) 2. 삽입 연산(push) 삽입을 할 경우 새로 만든 노드의 링크는 현재 스택의 top이 가리키는 링크가 되게 하고 그리고 새로 만든 노드가 top이 되게 하면 새로 만든 노드가 가장 위에 있는 스택 구조가 된다. void push(LinkedStackType *s){ int data; StackNode* .. [데이터베이스] 관계형 데이터베이스 설계 1. 관계형 데이터베이스 설계의 목표 불필요한 데이터의 중복을 막는다. 불필요한 중복은 디스크 공간을 낭비하고 함수적 종속으로 인한 삽입, 삭제, 갱신 이상의 발생 가능성이 높아진다. 이러한 불필요한 데이터 중복을 막도록 함수적 종속을 이용한 정규화를 통해 관계형 데이터베이스를 설계하여 중복을 막는다. 2. 관계형 데이터베이스 설계 과정 1) 요구 분석 2) 개념적 설계 : ER 모델링 (결과물 : ER Diagram) 3) 논리적 설계 : 매핑룰을 이용하여 테이블 만들기 -> 테이블 정규화하기(3NF or BCNF로) 4) 물리적 설계 3. 보이스카드 정규형(BCNF) 1) 정의 모든 함수적 종속 각각에 대해, 아래 두 조건 중 하나라도 만족하면 스키마 R은 보이스 카드 정규형에 있다. 가) a→b가 .. [데이터베이스] 정규형(Normal form)과 정규화(Normalization) 1. 이상(Anomaly) 1) 이상이란? 테이블에서 일부 속성들의 함수적 종속으로 인해 데이터의 중복이 발생하고 이 중복으로 인해 테이블을 삽입, 삭제, 갱신 시 문제가 발생하는 현상 2) 이상 종류 - 삽입 이상 - 삭제 이상 - 갱신 이상 2. 정규화(Normalization) 1) 정규화란 테이블을 손실 없이 분해하여 가능한 한 중복을 제거하고 테이블 삽입, 삭제, 갱신 시 이상이 발생하는 것을 줄이는 것이다. 2) 제 1 정규형(First Normal Form : 1NF) 테이블 R에 속한 모든 속성의 도메인이 원자 값으로만 되어야 한다. 제 1 정규형 방법 : 함수적 종속 PK → A가 있고, B는 PK와 A를 제외한 속성들의 집합일 때 PK와 A로 이루어진 테이블과 PK와 B로 이루어진 테이.. [자료구조] 원형 연결리스트(Circular LinkedList) 원형 연결리스트 - 마지막 노드가 첫번째 노드를 가리키는 리스트이다. 선형 연결리스트는 마지막 노드가 NULL을 가리키지만 원형 연결리스트는 첫번째 노드의 주소를 가리킨다. - 이렇게 된다면 선형 연결리스트보다 삽입, 삭제가 더 쉬워진다. 선형 연결리스트는 맨 마지막 노드에 삽입하고자 할 때 head 노드부터 마지막 노드까지 전부 지나가야 하지만 원형 연결리스트는 head->link에 삽입하고 새로운 노드를 head가 되도록 하면 되므로 훨씬 쉬워진다. - 노드를 맨 앞에 삽입하는 함수 //노드를 맨 앞에 삽입하는 함수 //원형 연결리스트이므로 head->link에 노드를 삽입하면 맨 앞에 삽입할 수 있다. ListNode* insert_first(ListNode* head){ int data; List.. [자료구조] 연결리스트(Linked List) //연결리스트 #include #include typedef struct ListNode{ int data; struct ListNode *link; }ListNode; //노드 생성 함수 ListNode* create_node(int data){ ListNode* node; node = (ListNode*)malloc(sizeof(ListNode)); node->data = data; node->link = NULL; return node; } //노드를 제일 앞에 삽입하는 함수 //삽입하는 노드가 head가 된다. ListNode* insert_first(ListNode* head){ int data; ListNode* new_node; printf("input data : "); scanf("%d".. [데이터베이스] 함수적 종속(Functional Defendency) 1. 함수적 종속(Functional Defendency, FD) 1) 함수적 종속이란? 함수적 종속은 어떤 테이블 인스턴스 R에 있는 모든 투플의 짝 t1, t2에 대하여 t1.a = t2.a 이면 t1.b = t2.b라면 그 스키마에 함수적 종속 a → b가 있다고 한다. 이때 a는 결정자, b는 종속자라고 한다. 간단히 말해 특성 속성 a가 정해지면 특정 속성 b를 결정지을 수 있는 관계를 함수적 종속이라 한다. 예를 들어 학생 테이블의 학생의 학번 속성이 정해지면 학생 테이블의 이름 속성이 정해진다. 학생의 학번은 기본키이므로 학생의 이름을 당연히 알 수 있다. 이런 경우를 함수적 종속이라 하고 다음과 같이 쓸 수 있다. FD : {학번} → {이름} 2) 수퍼키의 정의 함수적 종속으로 수퍼키를 .. 이전 1 ··· 3 4 5 6 7 8 다음