[컴퓨터공학개론] 8. 데이터 추상화

본 게시물은 컴퓨터공학개론 과목의 강의영상과 강의자료를 바탕으로 작성한 학습용 게시물입니다.

---

기본 데이터 구조 

(p.410)

• 배열 (Array, 동질성 배열)
• 집합체 (Aggregates, 이질성 배열 )
• 리스트 - 스택 / 큐 
• 트리 

# 배열 

• 배열 : 그 안의 항목들이 모두 동일한 타입인 데이터 블록 
• 2차원 배열 : 행들과 열들로 이루어짐 
• 인덱스 : 각 원소의 위치를 표시 

# 집합체 

• 집합체 : 타입과 크기가 다를 수도있는 데이터 항목들의 블록 
• 각 항목은 필드라고 불린다. 
• 필드에 대한 접근은 이름을 통해 이루어진다. 

#리스트 

• 리스트 : 항목을 순차적으로 배열하는 데이터 집합
• 헤드 : 리스트의 시작
• 테일 : 리스트의 끝 

# 스택

• 스택 : 항목들에 대한 제거와 삽입이 헤드에서만 이루어지는 리스트
• LIFO(Last-In-First-Out) : 후입선출 
• top : 스택의 헤드
• bottom : 스택의 테일 
• pop : 스택 상단에서 항목 제거 
• push : 스택 상단에 항목 삽입 

# 큐 

• 큐 : 항목들에 대한 제거는 헤드에서 일어나고 삽입은 테일에서 이루어지는 리스트 
• FIFO (First-In-First-Out) : 선입선출 

# 트리 

• 트리 : 항목들이 계층적 구성을 갖는 데이터 조합 
• 노드(node) : 트리 안의 항목 
• 루트(root)노드 : 최상단의 노드 
• 단말노드(terminal , leaf node) : 하단의 노드 
• 부모(parent) : 지정된 노드 바로 위의 노드
• 자식(child) : 지정된 노드 바로 아래 노드
• 조상(ancestor) : 부모, 부모의부모, ...
• 자손(descendent) : 자식, 자식의자식, ...
• 형제(sibiling) : 공통의 부모를 갖는 노드들 
• 이진트리(binary tree) : 모든 노드에서 자식의 수가 둘 이하인 트리 
• 깊이(depth) : 루트에서 단말에 이르는 가장 긴 경로상의 노드 수 

트리 관련 용어

---

관련 개념 

(p.415)

• 추상화 
  - 사용자에게서 실제 저장장치의 세부사항들을 감춘다
• 정적 구조와 동적 구조 
  - 정적 데이터 구조 : 데이터 구조의 크기와 형태가 변하지 x
  - 동적 데이터 구조 : 데이터 구조의 크기와 형태가 변할 수 있음 
• 포인터 
  : 데이터 항목이 저장되어 있는 주소를 값으로 갖는 메모리 영역 

---

8.3 데이터 구조의 구현 

(p.418)

• 데이터 구조들은 종종 고급 프로그래밍 언어에서 프리미티브 구조로 제공된다.
• 이러한 데이터 구조들은 주기억장치에 저장된 데이터를 조작하는 기계어 명령들로 변환된다.

# 배열의 저장 

• 특정 셀의 메모리 주소를 계산할 수 있다.
• 행 우선 순서 / 열 우선 순서 
• 주소 다항식 : 특정 배열 원소의 주소 계산 
  - c : 한 행의 컬럼 수 
  - x + (( c * ( i - j )) + ( j - 1 ) 
  - (( c * ( i - 1)) + ( j - 1 ) : ( i 행 j 열) 

# 집합체의 저장 

• 필드들을 차례대로 연속된 셀들의 블록에 저장할 수 있다. 
  - 각 필드의 메모리 셀 주소를 계산할 수 있다.
• 각 필드를 별도의 장소에 저장하고 이들을 포인터로 연결할 수도 있다.

# 리스트의 저장 

• 연속형 리스트 : 배열에 항목들을 저장하는 리스트
• 연결 리스트 : 항목들이 포인터로 연결되는 리스트 
  - 헤드 포인터 : 리스트의 첫 번째 항목에 대한 포인터 
  - null 포인터 : 리스트의 끝을 표시하기 위해 사용되는 정상적인 포인터가 아닌 값 

연결 리스트의 구조

 

# 스택과 큐의 저장 

• 스택은 대개 연속형 리스트로 저장된다.
• 큐는 대개 순환형 큐로 저장된다. 
  - 첫번째 항목은 마지막 항목 다음에 위치하는 것으로 간주되는 연속형 블록에 저장된다.
  - 큐가 할당된 저장 공간을 벗어나지 않게 한다. 

# 이진트리의 저장 

• 연결 구조 
  - 노드 = 데이터 셀 + 두개의 자식 포인터 
  - 루트 노드에 대한 포인터를 통해 접근 
• 연속형 배열 구조 
  - A[1] = 루트 노드 
  - A[2], A[3] : A[1]의 자식들 
  - A[4], A[5], A[6], A[7] = A[2]와 A[3]의 자식들 

이진트리에서의 노드 구조

# 데이터 구조의 조작 

• 이상적으로는 데이터 구조에 대한 모든 조작은 사전 정의된 함수들에 의해 이루어져야 한다
  - 이러한 함수들을 갖춘 데이터 구조는 완전한 추상적 도구를 형성한다. 

---

맞춤형 데이터 타입 

(p.439)

 

# 맞춤형 데이터 타입

• 프리미티브 데이터 타입 : 정수형, 실수형, 문자형, 부울형 
• 프로그래머는 특정 응용 프로그램에서 사용하기에 적합한 맞춤형 데이터 타입을 정의할 수 있다.

# 사용자정의 데이터 타입 

• 새로운 타입 정의를 위해 집합체 구조 사용 
• ex) C언어의 구조체 

# 추상 데이터 타입 

• 데이터와 함수 모두를 포함할 수 있는 사용자 정의 데이터타입
• ex) interface 

---

클래스와 객체 

(p.443)

• 클래스 ㅣ 추가 기능을 갖는 추상 데이터 타입 
  - 특성들에 대한 상속이 가능
  - 새로운 객체를 초기화하기 위한 생성자 존재 
  - 내용에 대한 캡슐화가 가능
• 객체 : 쿨래스의 인스턴스 

 

---

기계어에서의 포인터 

• 즉석 주소지정 방식
  : 명령 자체에 데이터를 포함 
  - 명령코드 2 : RXY → 비트 패턴 XY를 R번 레지스터에 LOAD하라  
• 직접 주소지정 방식
  : 명령 안에 데이터의 주소를 포함 
  - 명령코드 1 : RXY → 주소가 XY인 메모리 셀 안의 비트 패턴을 R번 레지스터에 LOAD하라
  - 명령코드 3 : RXY → R번 레지스터의 비트 패턴을 주소가 XY인 메모리 셀에 STORE하라
• 간접 주소지정 방식
  : 명령 안에 데이터의 주소가 들어있는 위치를 포함