[자료구조 알고리즘] 기초

 

. 정보 (information) : 어떤 목적에 기반한 action에 대한 직/간접적 지식 ,

. 자료 (data) : 정보를 얻기 위한 data processing system의 입력 되는 값 ( 정보의 자원 )으로 fact, concept, instruction의 총칭으로  실체의 유무와 관련이 없다.

. DPS에서 처리할 수 있도록 다양한 자료형(data type)이 정의 되며 자료의 타입으로는 int , real(float) , double precision, complex, char, List등 을 다루게 된다. 

 

자료 객체는 자료형의 실체를 구성하는 집합(set)과 요소(element)로 구성되며 data object에 대하여 주어지는 명칭은 variable이라고한다.

흔히 말하는 자료구조 (data structure)는 자료 객체의 집합 및 이러한 집합들 사이의 관계를 기술하는 것을 정의함.

그러므로 자료 객체 집합하의 element의 operation을 알고 수행방법을 정의함으로 자료 구조를 정의하게 된다.

 

추상적 자료구조의 표현 

자료구조를 추상적으로 표현하자면 domain D, function F , axiom A 라고 정의하며  d = (D, F , A) 로 

자료의 영역 d와 그 자료의 영역의 작동 함수 F 함수의 정의 A로 구상할 수 있게 된다. 

 

자료구조의 형태 분류 

자료구조를 형태상으로 분류하면 linear structure( sequencial structure), non linear structure, file structure의 세가지 형태로 구분할 수있다. 선형 구조로는 dense list, linked list( singly , doubly, circular) ,  queue, stack 이 대표적인 예이고 non - linear 구조로는 tree, graph, 그리고 file은 거대한 대량의 자료를 저장하는 파일 편성 방법을 적용하여 표현하게 된다.

1. linear structure : 데이터 상호간 1: 1 관계를 가진 구조 , 선후 관계가 명확하여 선형으로 구성이 형성되는 구조, 

1.1 Dense list 배열로 표현에 적합한 구조 

1.2 linked list  자료의 저장 위치를 가리키는 포인터를 사용하여 선후 관계를 유지할 수 있게 구성한 자료 

2022.02.23 - [programming/알고리즘] - [자료구조] linked list , double linked list , circular linked list 이해

1.3 stack - 삽입과 삭제가 한쪽 긑에서만 행해지는 형태로 FILO형태로 이루어지는 구조임 먼저 들어오고 마지막에 나가는 형식 

1.4 queue  - 삽입은 뒤에서 삭제는 앞에서 이루어지는 자료구조로 FIFO 구조로 되어있음 . 

2. non-linear structure  1:n, n:m의 관계를 가진 자료로 계층관계를 가지는 것이 특징이다.

2.1 tree 특정 자료에 종속된 하위 자료들이 존재하고 해당 자료는 다시 종속된 하위 자료들이 있는 계층 구조를 가진 자료구조 

2.2 graph 도로망이나 통신망과 같이 자료간의 상호간 n:m의 관계를 가지는 형태로 구성된 자료구조이다.