자료구조 정리

배열

 

행우선 A[i][j] : a + in + j

열우선 A[i][j]: a + jm + i

 

희소행렬

 

행렬요소 대부분이 0으로 구성된 행렬

 

연결리스트

 

배열 구조의 문제점인 삽입과 삭제의 어려움을 해결하기 위해 고안한 자료구조, 삽입과 삭제가 빈번한 작업

노드를 크게 데이터 필드와 링크 필드로 나누어 다음 노드가 기억된 공간의 주소를 이전 노드의 링크 필드에 기억시키는 방식

논리적 데이터 순서와 물리적 데이터 순서 동일하지 않으므로 후속 데이터 액세스를 위해 포인터 필요

기억 공간을 효율적으로 활용할 수 있다

 

수식표기방법

 

Infix(중위표기법): A + B 

Prefix(전위표기법): + A B

Postfix(후위표기법): A B +

 

이진 트리

 

전위(PreOrder)

중간->왼쪽->오른쪽

 

중위(InOrder)

왼쪽->중간->오른쪽

 

후위(PostOrder)

왼쪽->오른쪽->중간

 

힙트리

 

최대 힙트리는 각 노드의 키 값이 그 자식의 키 값보다 작지 않은 트리

 

최소 힙트리는 각 노드의 키 값이 그 자식의 키 값보다 크지 않는 트리

 

정렬

 

삽입 정렬, 쉘 정렬

버블 정렬, 퀵 정렬

선택 정렬, 힙 정렬

2원 합병정렬

기수 정렬