정보 컴퓨터 교과내용학
-
2.2.5 이중 연결 리스트 (Double Linked List)정보 컴퓨터 교과내용학/자료구조 2019. 1. 29. 21:06
2.2.5 이중연결리스트2.2.5.1 이중 연결 리스트의 개념 -> 하나의 노드가 선행 노드와 다음 노드에 대한 두 개의 링크를 가지는 연결 리스트이다. -> 이중 연결 리스트는 헤드 노드라는 특별한 노드를 가진다. 헤드노드란 데이터를 가지지 않는 노드로써 첫번째 노드를 가리킨다. 2.2.5.2 이중 연결 리스트의 장,단점 장점 단점 양 방향 탐색이 가능하다. 추가적인 메모리 공간이 필요하며, 코드가 복잡해 진다. 2.2.5.3 이중 연결 리스트의 구조 -> 이중 연결 리스트는 3개의 필드 (왼쪽 링크 필드, 데이터 필드, 오른쪽 링크 필드)로 이루어진다. -> 링크필드에는 포인터가 저장 된다. (1) 이중 연결 리스트의 초기 상태 -> 초기상태에는 헤드노드만 존재한다. -> 헤드노드의 링크 필드는 헤드..
-
2.2.4 원형 연결 리스트 (Circular Linked List)정보 컴퓨터 교과내용학/자료구조 2019. 1. 28. 16:46
2.2.4 원형 연결 리스트 2.2.4.1 원형 연결 리스트의 개념 -> 원형 연결리스트란 리스트의 마지막 노드의 링크가 첫 번째 노드를 가리키는 연결 리스트이다. 2.2.4.2 원형 연결 리스트의 장, 단점 장점 단점 한 노드에서 다른 모든 노드로의 접근이 가능하다. (노드의 삽입, 삭제가 단순해진다.) 노드의 삽입, 삭제시 선행 노드의 포인터가 필요하다. 2.2.4.3 변형된 원형 연결 리스트의 개념 -> 헤드 포인터가 마지막 노드를 가리키도록 구성한 연결 리스트이다. -> 마지막 노드는 헤드 포인터인 head가 가리키고, 첫번째 노드는 head -> link가 가리킨다. -> 그러므로 리스트의 마지막에 노드를 삽입, 삭제시 맨 끝까지 힘들게 가지 않아도 된다. 2.2.4.4 변형된 원형 연결 리스트..
-
2.2.3 단순 연결 리스트 (Simple linked list)정보 컴퓨터 교과내용학/자료구조 2019. 1. 27. 20:17
2.2.3 단순 연결리스트 - 개념 : 하나의 방향으로 연결되어 있으며, 마지막 노드의 링크 필드 값이 NULL인 연결리스트이다. - 단점 1) 한 노드에서 이전 노드나 역방향으로 노드를 탐색할 수 없다. (별도의 포인터가 필요하다.) - 단순연결리스트의 구현 (1) 노드 정의 1) 노드는 C언어 구조체를 이용하여 정의 된다. 2) 구조체 안에는 데이터를 저장하는 데이터필드와 포인터인 링크필드가 있다. 3) 노드의 구조가 구조체를 이용하여 정의 되었지만, 아직 노드는 생성되지 않았다는 것을 주의 해야 한다. (2) 노드 생성 1) 연결 리스트에서는 필요할 때 마다 동적 메모리 할당을 이용해 노드를 동적으로 생성한다. 2) 그림의 코드에서는 임시 포인터 변수 p1을 만들고, malloc 함수를 이용하여 노..
-
2.2.2 연결 리스트 (Linked List)정보 컴퓨터 교과내용학/자료구조 2019. 1. 27. 16:46
2.2.2 연결리스트 - 개념 : 1) 동적으로 크기가 변할 수 있고, 삽입이나 삭제 시 데이터 이동할 필요가 없는 리스트이다. 2) 즉 연결리스트란 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법을 말한다. - 연결리스트의 구조 1) 상자를 컴퓨터 용어로 노드라고 부른다. 2) 연결리스트는 이들 노드들의 집합이며, 노드들은 데이터를 저장하고 서로 연결되어 있다. 3) 노드들은 메모리 어느 위치에나 있을수 있으며, 다른 노드로 이동하기 위해 현재 노드가 가지고 있는 포인터를 이용하면 된다. 4) 노드는 위의 그림과 같이 데이터 필드와 링크필드로 구성되어 있다. 1) 연결리스트에서는 첫 번째 노드를 알아야만이 전체의 노드에 접근할 수 있다 2) 따라서 연결리스트마다 첫번째 노드를 가리키고 있는 변수가..
-
2.2.1 리스트, 배열로 구현한 리스트정보 컴퓨터 교과내용학/자료구조 2019. 1. 24. 19:38
2.2 리스트 (배열 리스트, 연결 리스트) - 개념 : 리스트란 순서를 가지고 일렬로 나열한 데이터들의 모임이다. (순서를 가지고 있다는 점에서 집합과 구분된다.) - 예시 : 한 주일의 요일 리스트 : (일, 월, .. 토요일), 한글 자음 리스트 (ㄱ, ㄴ, …ㅎ) 2.2.1 배열로 구현한 리스트 (개념, 장점, 단점, 삽입, 삭제) - 개념 : 메모리안에 순차적으로 공간이 할당되는 배열을 이용한 방법으로, 배열 인덱스 번호를 이용해 데이터에 접근한다. - 장, 단점 장점 단점 인덱스를 이용하여 원하는 데이터요소를 빠르게 찾을 수 있다. ( O(1) ) 1) 자료의 삽입과 삭제가 비효율 적이다. (삽입과 삭제시 모든 요소를 이동 시켜야 한다. O(N) ) 삽입) 배열에 ABCDE가 저장되어 있고, ..
-
2.1 선형 데이터 구조(배열)정보 컴퓨터 교과내용학/자료구조 2019. 1. 19. 17:03
2. 선형 데이터 구조 2.1 배열 (개념, 특징, 장단점, 종류, 연산 및 응용) 2.1.1 배열의 개념 -> 여러 개의 동일한 데이터 타입의 데이터를 연속된 메모리 공간에 한 번에 만들 때 사용 된다. ( int a1, a2, a3, a4, a5, a6 == int A[6]) -> 배열은 의 집합이다. 즉 인덱스를 사용하여 요소에 직접 접근할 수 있다. ex) int A[5] = {0,5,4,2,4} -> int A[3]의 인덱스를 사용하면, 2라는 정수형 데이터 요소에 접근할 수 있다. 2.1.2 배열의 장점과 단점 장점 단점 인덱스를 이용하여 원하는 데이터요소를 빠르게 찾을 수 있다. ( O(1) ) 1) 자료의 삽입과 삭제가 비효율 적이다. (삽입과 삭제시 모든 요소를 이동 시켜야 한다.) 삽입..
-
1. 데이터 구조 기초 (기본 자료형과 추상 자료형)정보 컴퓨터 교과내용학/자료구조 2019. 1. 17. 20:04
자료구조 정보 컴퓨터 평가 영역 및 평가 내용요소 (출처 : 교육과정 평가원) 데이터 구조 평가 영역 평가 내용 요소 데이터 구조 기초 기본 자료형과 추상 자료형 순차 데이터 구조와 연결 데이터구조 (배열의 개념 및 종류, 링크를 이용한 노드 연결 개념 및 종류) 선형데이터 구조 배열의 연산 및 응용 연결 리스트의 개념 및 연산 배열 및 연결리스트를 이용한 선형리스트의 구현 및 응용 (다항식, 가용공간 리스트) 스택과 큐의 개념 스택과 큐의 표현 및 연산 스택과 큐의 응용(괄호쌍검사, 후위수식 변환 및 계산, 환형큐, 대기큐) 트리 트리의 개념 및 기본용어 이해 이진 트리의 개념 및 특징 이진 트리의 연산 및 순회 트리의 응용(우선순위 큐, 힙정렬, 균형 이진 탐색 트리, 다원 탐색 트리, B+트리) 그..