Data Structure

정점(데이터)끼리의 연결관계를 저장한 자료형 [용어정리] 정점 : 연결의 대상이 되는 개체 간선 : 개체 사이의 연결 무방향 그래프(양방향 가능) 방향 그래프 가중치 그래프 완전 그래프 : 각각의 정점에서 다른 모든 정점을 연결한 그래프 부분 그래프 : 원 그래프의 일부 정점 및 간선으로 이워진 그래프 그래프 G의 정점 집합 V(G)={A, B, C, D} 그래프 G의 간선 집합 E(G)={(A,B), } (* ()는 무방향, 는 방향 그래프) [그래프의 두가지 구현방법] 인접 행렬 기반 그래프 (두 정점이 연결되어 있으면 1, 연결되어 있지 않으면 0으로 표시) 인접 리스트 기반 그래프 ▶ 그래프의 ADT 필요한 기능 : 그래프 초기화, 그래프 리소스 해제(그래프 자체 없엠), 연결된 간선 추가, 모든..

고유값 key(made by 해쉬함수)을 이용해서 배열에 저장함 ≒ #include [테이블] 키와 값이 하나의 쌍을 이루어 저장되는 데이터의 유형 O(1)의 시간 복잡도 #include typedef struct _empInfo { int empNum; //이것이 고유번호가 될것이여 int age; //실제 저장할 대상 }EmpInfo; int main(void) { EmpInfo empInfoArr[1000]; EmpInfo ei; int eNum; printf("사번과 나이 입력: "); scanf("%d %d", &(ei.empNum), &(ei.age)); empInfoArr[ei.empNum] = ei; printf("확인하고픈 직원의 사번 입력: "); scanf("%d", &eNum); e..

들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다 [우선순위 큐의 종류] 배열을 기반으로 구현하는 방법 (삽입/삭제시 모든 데이터 뒤로 밀거나 당겨야함, 모든 데이터와 우선순위를 비교해야함) 연결리스트를 기반으로 구현하는 방법 (모든 데이터와 우선순위를 비교해야함) 힙을 이용하는 방법 힙 = 완전이진트리 + 모든 노드에 저장된 값은 자식노드에 저장된 값보다 크거나 같음(최대 힙) [힙을 이용하여 만드는 우선순위 큐] 힙≠우선순위 큐 이다 → 힙은 우선순위 큐 구현에 딱 어울리는 자료구조일 뿐이다. (데이터 추가 방식) 1. 새로운 데이터는 우선순위가 가장 낮다고 가정하고 마지막 위치에 저장함 2. 부모 노드와 비교해서 위치가 바뀌어야 하면 바꿈 3. 제대로 된 위치를 찾을때 까지 반복 (데이터..

트리는 계층적 관계를 표현하는 자료구조 [트리] 단순히 무엇을 저장하고 꺼내는 것이 아닌 무언가를 표현하는 자료구조 노드 - 트리의 구성요소 간선 - 노드를 연결하는 연결선 루트 노드 - 트리 구조에서 최상위 노드 단말 노드 - 아래에 더 이상 노드가 없는 말단 노드 부모 노드가 같은 노드끼리는 형제 노드 루트 노드를 중심으로 둘로 나누어지는 서브 트리 레벨 : 각 층 별로 숫자를 매긴 것 (루트 노드가 레벨 0) 높이 : 트리의 최고 레벨=높이 포화 이진트리 : 레벨이 꽉 찬 이진트리 완전 이진트리 : 노드가 위에서 아래로 & 왼쪽에서 오른쪽 순서대로 채워짐 특징 → 노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면 공집합 노드가 존재하는 것으로 간주 [배열 기반의 이진트리] ★부모노드를 참고할때 ..

양방향으로 넣고 뺄수 있는 자료구조 deque : double ended queue [양방향 연결리스트를 기반으로 구현된 덱] 양방향 연결리스트를 이용하여 만들며, head와 tail을 각각 가리킨다 ▶ ADT 필요한 기능 : 덱 초기화, 덱 비었는지 확인, 덱의 머리/꼬리에 데이터 저장, 덱의 머리/꼬리에 데이터를 반환 및 소멸, 덱의 머리/꼬리에 있는 데이터를 소멸하지 않고 반환 void DequeInit(Deque * pdeq); int DQIsEmpty(Deque * pdeq); void DQAddFirst(Deque * pdeq, Data data); void DQAddLast(Deque * pdeq, Data data); Data DQRemoveFirst(Deque * pdeq); Data D..

선입 선출의 자료구조. [큐의 종류] 배열을 기반으로 구현된 큐 리스트를 기반으로 구현된 큐 [배열을 기반으로 구현된 큐] = 원형 큐 ※ 스택과 큐는 차이가 별로 없어보이지만 구현방법에는 차이가 크다 ! ▶ ADT 필요한 기능 : 큐 초기화, 큐 비었는지 확인, 큐에 데이터 넣기, 큐에서 데이터 꺼내기, 다음에 나올 데이터 들여다보기 void QueueInit(Queue * pq); int QIsEmpty(Queue * pq); void Enqueue(Queue * pq, Data data); //데이터 삽입 Data Dequeue(Queue * pq); //데이터 삭제 Data QPeek(Queue * pq); ▶ 배열을 기반으로 구현된 리스트의 문제점 ★ 위 그림에서 front의 index를 1씩 ..

후입 선출. [스택의 종류] 배열을 기반으로 구현한 스택 연결리스트를 기반으로 구현한 스택 [배열을 기반으로 구현한 스택] → 인덱스 0의 배열요소가 스택의 바닥 ! (길이와 상관없이 무조건 인덱스 0이 바닥이기 때문) ▶ ADT 필요한 기능 : 스택 초기화, 스택이 빈 경우 true 반환, 스택에 데이터 저장, 마지막에 저장된 요소 삭제, 마지막에 저장된 요소 들여다보기 void StackInit(Stack * pstack); // 스택 초기화 int SIsEmpty(Stack * pstack); // 스택 비었는지 확인 void SPush(Stack * pstack, Data data); // 스택에 데이터 삽입 Data SPop(Stack * pstack); // 스택에서 데이터 반환&삭제 Data..

[자료구조 공부법 -BY 윤성우씨] 1. 자료구조의 ADT 정의 2. 정의한 ADT의 구현 3. 구현이 완료된 자료구조의 활용 [연결리스트의 종류] 배열을 기반으로 구현된 리스트 동적할당을 기반으로 구현된 리스트 단순 연결 리스트 원형 연결 리스트 양방향 연결 리스트 ADT(추상 자료형) : 구체적인 기능의 완성과정을 언급하지 않고, 순수하게 "기능이 무엇인지" 나열한것 (ex. 리스트 자료구조의 데이터를 저장하는 기능인 LInsert) ▷ 추상 자료형은 사람에 따라서 정의하는 방식이 다르므로 "표준" 이란것이 없다 [배열을 기반으로 구현된 리스트] → 노드 개념이 없음 장점 : 데이터 참조가 쉽다(by 인덱스) 단점 : 배열의 길이가 한정되어 있다, 삭제할때마다 데이터 이동;; ▶ ADT 필요한 기능 ..