컴퓨터과학개론 -자료구조, 선형리스트, 연결리스트

2. 자료구조

자료구조란? 
- 자료 사이의 논리적 관계를 컴퓨터나 프로그램에 적용하기 위해서는 자료의 추상화가 필요로 하며, 자료의 논리적 관계를 구조화 한 것

※ 추상화 : 공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의 한 것

데이터의 추상화 : 다양한 객체를 컴퓨터에서표현하고 활용하기 위해 필요한 데이터의 구조에 대해서 공통의 특징만을 뽑아 정의한 것.

자료구조

- 미리 정의된 자료구조
   • 기본 자료구조 
        1. 정수 (Integer)
        2. 실수 (Real Number)
        3. 문자 (String)

  • 파생된 자료구조
       1. 배열 (Array)
       2. 구조체 (Struct , enum , Union)
       3. 포인터 (*)

- 사용자 정의 자료구조
       1. 리스트
       2. 스택
       3. 큐
       4. 트리
       5. 그래프

1. 배열 (Array)
배열이란 동일한 자료형을 갖는 여러개의 데이터를 동일한 변수의 이름방에 일렬로 저장하는 자료의의 집합체를 의미한다.


배열의 원소에 접근하기 위해선 인덱스(Index) 또는 첨자(Subscript)를
사용한다.

C언어의 경우 0번째 인덱스에서 시작한다.


1.1 1차원 배열

배열의 첫 번째 원소 Score[0]의 메모리를 a라 하고, 각 자료형의 크기를 k를 알면
간단한 계산에의해 score[i]의 주소 값을 알 수 있다.

 a= 메모리의 시작 주소
 i= 인덱스
 k= 배열의 크기 

A[i]의 저장주소는    


1.2 다차원배열

2차원배열은 바둑판 모양이라 생각하면 좋다.

※컴퓨터 메모리에 저장하는 순서

1. 열 우선 순서 행렬 (Column major order )
저장되는 순서

2. 행 우선 순서 행렬  ( Row-major order )
저장되는 순서

1.3 희소 행렬

위 행렬에 원소값이 0인 원소가 그렇지 않은 원소보다 상대적으로 많다. 
오른쪽같은 행렬을 희소 행렬이라고 한다.(sparse matrix)

컴퓨터 메모리의 낭비를 막고 처리의 효율성을 높이기 위해서 희소 행렬의 0인 원소는 저장하지 않고 0이 아닌 각원소를 저장하는 방법이다.

설명 :
 0번째 행 , 1번째 열에 값이 20이 있다는 뜻.
 0번째 행 , 5번째 열에 값이 8이 있다는뜻.
※ 행과 열의 시작은 0부터 시작한다.
print matrix[0][1] ;            // 20 이 출력
print matrix[0][5] ;            // 8이 출력



2. 리스트 

2.1 선형 리스트
선형 리스트(Linear List), 순서 리스트(Ordered List)라고 하며, 1개 이상의 원소들이 순서를 가지고 구성된다.

선형 리스트 에는 삽입(Insert), 삭제(Delete), 호출(Called), 갱신(Update), 검색(Search), 정렬(Sort)등 다양한 연산이 적용될수 있다.
예) 
   요일 리스트 : {월 , 화, 수 , 목 , 금 , 토 ,일}
2.2 선형 리스트 구현

‘수요일’ 인덱스 삭제과정

요일 선형 리스트의 이름은 day라고 한다.

원소들의 순서를 그대로 유지하면서 원소를 삽입/삭제를 해 야하기 때문에 한칸씩 앞으로 이동시킨다
※ 선형리스트를 배열로 구현할 경우 비효율적인 성능을 가져올 수 있다, 
※ 선형리스트 구현을 위해 7개의 배열의 크기를 잡았을 경우 데이터를 삽입할 때, 7개 원소 이상 삽입 할수 없는 단점도 가지고 있다.


선형리스트를 구현하는 다른 방법으로 포인터를 활용한 연결 리스트(Linked list)를 사용하는 것이다.
 
1 단일 연결 리스트

2 이중 연결 리스트

3 단일/이중 원형  연결 리스트