[컴퓨터] 선형과 비선형

소개글

잘 정리 되어 있슴돠..^^

목차

1장 선형구조
1.1 배열(array)
(1) 배열의 특징
(2) 배열의 종류
(3) 희소 행렬(Sparse Matrix)
1.2 리스트(LIST)
1.2.1 선형리스트(Linear List)
1.2.2 연결리스트(Linked List)
1.3 스택(Stack)
1.4 큐(Queue)
1.5 데크(Deque)

제2장 비선형 구조
2.1 트리(TREE)
2.1.1 트리의 개요 및 종류
2.1.2 트리의 표현과 저장법
2.1.3 패스의 길이(Path Length)
2.1.4 트리의 운행(Traversal)
2.1.5 스레드(Thread) 이진 트리
2.1.6 허프만 트리(Huffman tree)
2.2 그래프(Graph)
2.2.1 그래프의 개요 및 종류
2.2.2 그래프의 표현
2.2.3 그래프의 운행
2.2.4 신장 트리(Spanning tree)

본문내용

1.1 배열(array)
(1) 배열의 특징
1) 크기와 성격이 동일한 기억장소가 메모리에 연속적으로 할당되어 데이터를 기억하는 자료구조
2) 배열명과 첨자로 구별된다, 인덱스와 값의 쌍으로 구성, 임의 접근 가능, 순차구조
3) 배열은 메모리에서 연속적으로 기억된다, 동일 데이터 타입으로 구성, 직접화일 구조와 비슷한 성격
4) 기억장소에 할당되는 배열의 요소번호는 언어에 따라 다르다
5) 배열을 이용한 표현 가능한 자료구조 연산
- 순서화 리스트에 의한 이진 탐색, 최소힙에서의 최소값 탐색, 큐의 제거연산, 트리에는 부적합

(2) 배열의 종류
1) 1차원 배열
- 메모리에 같은 크기의 기억장소가 연속으로 할당되며 첨자가 하나
- 배열원소의 개수는 선언한 첨자와 같다
2) 2차원 배열
- 행과 열을 의미하는 첨자가 2개이고 구분은 행과 열로 하지만 실제 메모리에서는 1차원으로 기억
- 행 고정(우선) 열 변환(행 방향 순서) : 행은 고정이고 열이 변화하는 순서에 따라 기억 ; COBOL, C, PASCAL, PL/I
- 열 고정(우선) 행 변환(열 방향 순서) : 열은 고정이며 행이 변하는 배열; FORTRAN
* 배열 A(m, n)에서 A(i, j)의 위치
가) 행 우선 : n(i-1) + j
나) 열 우선 : n(j-1) + i
3) 3차원 배열
- A(p, m, n)으로 정의된 3차원 배열에서 A(i, j, k)의 위치
가) 행 우선 : m*n(i - 1) + n(j - 1) + k
나) 열 우선 : m*n(i - 1) + m(k - 1) + j
- 메모리에 기억되는 번지 수 : 첫 번째 원소의 번지수를 locA111이라고 한다
가) 행 우선 : locA111 + m*n(i - 1) + n(j - 1) + (k - 1)
나) 열 우선 : locA111 + m*n(i - 1) + m(k - 1) + (j - 1)

(3) 희소 행렬(Sparse Matrix)
- 행렬의 많은 원소들이 0으로 되어 있어서 0이 아닌 원소의 수가 거의 없을 때
- 기억장소의 낭비가 심해서 비효율적 ⇒ linked list로 표현하면 기억장소 절약

참고 자료

대충 간단하게 설명해봤습니다..