[JAVA ] 자료구조- 단순구조 선형구조 비선형구조 해싱

컴퓨터는 자료의 특성에 따라 다양한 자료구조 기법을 사용합니다. 자료구조에는 단순구조, 선형구조, 비선형구조가 있습니다.

단순구조 :  정수, 실수, 문자, 문자열 등 자료의 형태

선형 구조 :  자료 간의 연결 관계가 [1:1] 관계를 가지는 형태로 자료들이 기다란 선처럼 연결되어 있는 구조

비선형구조 :  자료 간의 연결 관계가 [하나 : 여러 개] 또는 [여러 개 : 여러 개] 의 관계를 가지는 형태로, 나뭇가지 모양이나 그물 모양처럼 얽혀 있는 구조

 

추가 - 해싱 : 자료 검색을 위한 구조 

 

선형 구조 : 자료를 구성하는 데이터를 순차적으로 나열시킨 형태

• 선형 자료구조란 하나의 자료 뒤에 하나의 자료가 존재하는 것이다.
• 자료들 간의 앞뒤 관계가 1:1의 선형관계

1) 배열 (Arrays) : 

동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖고 있는 집합.

논리적 저장 순서와 물리적 저장 순서가 일치하기 때문에 인덱스로 해당 원소에 접근함.

정해진 크기의 메모리를 먼저 할당 받아사용 하여, 정적인 자료 구조로 기억 장소의 추가가 어렵고 데이터 삭제 시 데이터가 저장되어 있던 기억 장소는 빈 공간으로 남아있어 메모리 낭비가 발생

 

 

 

2) 연결 리스트(Liked List) :

자료를 연속적으로 배열 시키지않고 자료가 추가될때마다 메모리를 할당 받음, 각 원소들은 이전, 다음  위치를 기억하여 삽입, 삭제 하므로 동적인 크기를 가짐. 논리적위치와 물리적위치가 다름.  index로 찾아가는 배열보다 순차적으로 위치를 찾아감으로써 소요되는 시간은 크다. 

3) 스택(Stack) :

한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어진다.

LIFO(Last In First Out): 가장 나중에 삽입된 자료가 가장 먼저 삭제

 

Stack<Integer> nStack = new Stack();

 nStack.push(1);

 nStack.push(2);

 nStack.push(3);

 nStack.push(4);//넣기

 

nStack.pop(); //빼기 - 4부터제거

 

4) 큐(Queue) : 

한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어진다.

FIFO(First In First Out): 가장 먼저 삽입된 자료가 가장 먼저 삭제

* Queue는 인터페이스 구현체인 Linked List의 생성자를 사용

Queue<Integer> iQ  = new LinkedList<Integer>();

iQ.offer(1);

iQ.offer(2);

iQ.offer(3);

iQ.offer(4);

iQ.offer(5);

iQ.offer(6);// 넣기

iQ.poll();//빼기 - 1부터 제거

 

비선형 구조 : 선형 구조와는 달리 비선형적인 계층 구조

• 비선형 자료구조란 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 것이다.
• 자료들 간의 앞뒤 관계가 1:n, 또는 n:n 의 관계
• 단순한 반복으로 탐색할 수가 없기 때문에 스택(stack)이나 큐(queue)와 같은 자료구조를 활용해 탐색할 방법과 순서를 만들어 탐색하는 것이 일반적 ( 트리에서 노드가 n번일때, 왼쪽 자식노드는 2*n 오른쪽 자식노드는 2*n + 1의 관계)
  
  

1) 그래프(graph) : 정점(노드)과 선분(간선)의 집합

노드와 간선으로 이루어져있는 사이클 형태의 그래프

정점(vertex)  : 객체(= 노드)

간선(edge) : 연결관계(= 링크) ,방향성이 있기도 없기도함.

 

G(V,E) 로 표현 - G : graph, V : vertex, E : edge

 

종류 : 

• 방향성(Directed) 그래프: 간선에 방향성이 포함된 그래프
• 무방향성(Undirected) 그래프: 방향성이 없는 그래프
• 가중치(Weight) 그래프: 간선에 가중치 정보가 포함된 그래프
• 부분(Sub) 그래프: 본래 그래프의 일부 정점 및 간선으로 이루어진 그래프

구현 방법 에 따라 인접행렬, 인접리스트 , 탐색 방법에 따라 BFS(Bread First Search), DFS(Depth First Search) 로 구분 

2) 트리(Tree)

부모노드와 자식 노드간의 연결로 구성, 부모 자식간 계층구조가 명확함 ,그래프의 일종

한노드는 여러노드를 가리킬수 있고 여러 노드가 한노드를 가리킬수 는 없으므로 모든노드는 단하나의 부모노드를 가짐

다른 노드와 연결되지 않는 노드는 존재하지 않는다.

 

• node: 트리를 구성하고 있는 각 요소
• Edge(간선): 트리를 구성하기 위해 노드와 노드를 연결하는 선
• Root Node: 최상위 계층에 존재하는 노드
• level: 트리의 특정 깊이를 가지는 노드의 집합(루트노드로 부터 깊이를 말하며 루트노드의 level 은 1이다)
• degree(차수): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수(부속트리개수)
• Terminal Node ( = leaf Node, 단말 노드) : 하위에 다른 노드(자식노드)가 연결되어 있지 않은 노드 (차수가 0임)
• Internal Node (내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.(차수가 1이상)
• Sibling Node (형제노드) : 부모가 같은 노드 
• Sub tree : 트리안의 트리 (부속트리를 말함)

 

종류 : 

완전 이진 트리(Completable Binary Tree), 포화 이진 트리(Perfect Binary Tree), 전 이진 트리(Full Binary Tree)

 

반응형

 

 

* 해싱 (Hashing)

 해싱은 키에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다.

 

• 해시 테이블(hash table) : 이렇게 키에 대한 연산에 의해 직접 접근이 가능한 구조
• 해싱(Hashing) : 어떤 항목의 키만을 가지고 바로 항목이 들어 있는 배열의 인덱스를 결정하는 기법으로 해시 테이블을 이용한 탐색
• 해시 함수 : 키를 입력으로 받아 해시 주소(hash address)를 생성하고 이 해시 주소를 해시 테이블(hash table)의 인덱스로 사용

키값 k를 입력받아 해시 함수 h(k)로 연산한 결과인 해시 주소 h(k)를 인덱스로 사용하여 해시 테이블에 있는 항목에 접근한다. 해시 테이블 ht는 M개의 버킷(bucket)으로 이루어지는 테이블로서 ht[0], ht[1], ..... , ht[M-1]의 원소를 가진다.