자료구조 / 데이터베이스

자료구조 

1. 자료 구조의 분류

- 선형구조 (배열,스택,큐,데크,리스트)

- 비선형구조(트리, 그래프)

 

2. 배열

- 정적인 자료 구조, 기억장소의 추가가 어렵고, 메모리의 낭비가 발생

- 첨자를 이용

- 반복적인 데이터 처리 작업에 적합

- 데이터마다 동일한 이름의 변수를 사용해 처리가 간편

 

3. 스택

- 리스트의 한쪽 끝으로만 삽입, 삭제가 이루어짐

- 후입선출

 

4. 큐

- 리스트의 한쪽에서는 삽입, 반대 쪽에서는 삭제가 이루어짐

- 선입선출

- 시작과 끝을 표시하는 두 개의 포인터가 있다.

- 운영체제의 작업 스케줄링에 사용

 

5. 데크

- 리스트의 양쪽 끝에서 삽입과 삭제작업을 할 수 있는 구조

 

6. 리스트

- 연속 리스트

• 배열과 같이 연속되는 기억장소에 저장되는 자료 구조
• 기억장소를 연속으로 배정 받아, 기억 장소 이용 효율이 좋다.
• 중간에 데이터를 삽입하기 위해 연속된 빈 공간이 있어야 한다.
• 삽입, 삭제 시 자료의 이동이 필요함

- 연결 리스트

• 자료들을 반드시 연속적으로 배열시키지 않고 임의의 기억공간을 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용해 서로 연결시킨 자료 구조 
• 노드의 삽입, 삭제 작업이 용이하다.
• 기억 공간이 연속적으로 놓여 있지 않아도 저장이 가능하다.
• 연속 리스트에 비해 기억 공간의 효율이 안좋다.
• 검색이 느리다.
• 노드 연결이 끊어지면 다음 노드를 못 찾는다.

 

7. 트리

- 정점(Node)와 선분(Branch)를 이용해 싸이클을 이루지 않도록 구성한 그래프의 특수한 형태

- 노드 : 트리의 기본 요소, 자료 항목과 다른 항목에 대한 가지를 합친 것

- 근 노드 : 트리의 맨 위에 있는 노드

- 디그리 : 가지의 수

- 단말 노드 : 자식이 없는 노드

- 자식 노드 : 어떤 노드에 연결된 다음 노드

- 부모 노드

- 형제 노드 : 동일한 부모를 갖는 노드들

- 트리의 디그리 : 디그리 중 가장 높은 수

 

8. 그래프

- 방향 그래프

정점을 연결하는 선에 방향이 있는 그래프

n개의 정점으로 구성된 방향 그래프의 최대 간선 수 = n(n-1)

 

- 무방향 그래프

정점을 연결하는 선에 방향이 없는 그래프

n개의 정점으로 구성된 무방향 그래프의 최대 간선 수 = n(n-1)/2

 

---

데이터베이스

1. 데이터베이스

- 공용 데이터 : 공동으로 소유하고 유지하는 자료

- 통합된 데이터 : 중복을 최대로 배제한 데이터

- 운영 데이터 : 없어선 안 될 자료

- 저장된 데이터 : 저장 매체에 저장된 자료

 

2. DBMS(Database Management System : 데이터베이스 관리 시스템)

- 사용자 요구에 따라 정보를 생성해주고, 데이터베이스를 관리해 주는 소프트웨어

- 정의 기능(DDL) : 데이터베이스에 저장될 데이터의 타입과 구조에 대한 정의,이용 방식, 제약 조건 명시

- 조작 기능(DML) : 사용자와 데이터베이스 사이 인터페이스 수단을 제공하는 기능

- 제어 기능(DCL) : 데이터베이스에 접근하거나 객체에 권한을 주는 등의 역할