자료구조의 기본 개념, 순차 데이터 표현(배열, 구조체)

자료 구조

 

- 자료 구조 : 자료들의 상호 연관 관계 -> 어떤 연관 관계를 가지냐에 따라 선형구조와 비선형구조로 구분

 

• 선형구조
  - 데이터의 항목 사이의 관계가 1:1이며, 선후 관계가 명확한 1개의 선의 형태를 갖는 리스트 구조
  - 배열, 리스트(연결 리스트, 선형 리스트), 스택, 큐, 덱으로 나뉨
  
  
• 비선형구조
  - 데이터의 항목 사이에 1:n 또는 n:m의 관계를 갖는 그래프적 특성을 갖는 형태
  - 트리, 그래프가 이에 속함
  - 그래프는 사이클을 허용하며, 트리는 사이클을 허용하지 않음
  
  
  
  

알고리즘

 

- 컴퓨터로 문제를 풀기 위한 단계적인 절차
- 특정한 일을 수행하는 명령어들의 집합

• 알고리즘의 특성
  - 입력 (Input) : 외부에서 제공되는 자료가 있을 수 있음
  - 출력 (Ouput) : 반드시 한 개 이상의 결과를 생성해야함
  - 명확성 : 각 명령들은 명확하고, 모호하지 않아야 함
  - 유한성 : 어느 한정된 수의 단계 뒤에는 반드시 종료
  - 실제성 : 알고리즘의 모든 명령은 실행 가능
  - 유효성 : 원칙적으로 모든 명령들은 종이와 연필만으로 수행될 수 있게 기본적이어야 함
  
  
  
  

배열 (Array)

 

• 배열의 특성
  - 배열은 정의(선언)될 때 이름, 크기, 데이터 타입이 결정
  - <인덱스, 원소> 쌍의 집합으로, 각 쌍은 어느 한 인덱스가 주어지면 그와 연관된 원소 값이 결정되는 대응 관계를 나타냄
  - 원소들이 모두 같은 타입이고 크기도 같음
  - 반드시 유한성을 가짐
  - 배열의 접근 방법은 순서에 따라 접근하지 않고 인덱스에 따라 직접 접근함
  - 배열의 주된 연산은 정보를 저장하고 탐색하는 연산
  - 기준주소에서부터 시작하여 연속적인 메모리 주소를 할당하여 배열의 논리적 순서와 메모리의 물리적 순서가 같도록 표현한 것
  
  
• 1차월 배열
  int A[6];

A[0]

A[1]

A[2]

A[3]

A[4]

A[5]

배열 요소	메모리 주소
A[0]	기본 주소 A
A[1]	A + 1 * sizeof(int)
A[2]	A + 2 * sizeof(int)
A[3]	A + 3 * sizeof(int)
A[4]	A + 4 * sizeof(int)
A[5]	A + 5 * sizeof(int)

 

* A[i]의 주소 : 배열 A의 시작주소 + 첨자 * int형 기억장소 크기(바이트) = A + i

 

• 2차원 배열
  - 가로줄을 행(row), 세로줄을 열(column)
  - 전체 배열의 크기가 A(m, n)이고 시작 주소가 A(k, l)일 때, 현재 위치 A(i, j)의 주소를 구한다고 할 때,
  -> 행우선 순서로 접근(행의 변수가 정해지고 열의 변수가 전체적으로 변하는 접근 방식) : base + ((i - k)n + (j - l)) * byte 크기
  -> 열우선 순서로 접근(열의 변수가 정해지고 행의 변수가 전체적으로 변하는 접근 방식) : base + ((j - l)m + (i - k)) * byte 크기

* 3차원 배열
- p개의 2차원 배열로 구성되며 면, 행, 열로 표시

- 3차원 배열 A(p, m, n)에서 A(k, i, j)의 주소를 구한다고 할 때(시작 위치 A(1, 1, 1) = base이고 한 원소의 크기는 1byte)
-> 행우선 순서로 접근 : base + (k - 1)mn + (i - 1)n + (j - 1)
-> 열우선 순서로 접근 : base + (k - 1)mn + (j - 1)m + (i - 1)

 

Q. int a[5][6]으로 선언되는 2차원 배열이 열우선 순서로 저장되고 a[0][0]의 주소가 1000이며 정수 크기는 4byte라고 가정했을 때 a[2][3]의 주소는?

A. 1068

 

-> 1000 + ((3 - 0) * 5 + (2 - 0)) * 4 = 1068

 

 

 

 

구조체 (structure) -> JAVA에서는 존재하지 않는 개념

 

• 구조체의 정의
  - 배열이 타입이 같은 데이터의 모임이라면 구조체는 타입이 다른 데이터를 묶는 방법으로 사용자 정의 데이터형
  - typedef을 사용하면 구조체 변수들을 보다 쉽게 만들 수 있음

typedef struct person {
	char name[10];
    int age;
} person
person a;

 

• 자기 참조 구조체 (self-referential structure)
  - 특별한 구조체로서 구성 요소 중에 자기 자신을 가리키는 포인터가 한 개 이상 존재하는 구조체
  - 연결리스트나 트리를 구성할 때 많이 등장
  - 일반적으로 항목의 개수를 미리 예측할 수 없는 경우에 자기 참조 구조체를 정의해놓고 동적으로 기억장소를 할당받아서 이들을 포인터로 연결하여 자료 구조를 구성 (구조체 안에 구조체 자체를 참조할 수는 없음)

typedef struct ListNode {
	char data[10];
    struct ListNode *link;
} ListNode;