✨𝐃𝐚𝐭𝐚 𝐃𝐞𝐬𝐢𝐠𝐧 𝐚𝐧𝐝 𝐈𝐦𝐩𝐥𝐞𝐦𝐞𝐧𝐭𝐚𝐭𝐢𝐨𝐧✨

하핫,, 언제 개강을 했죠,,,,?😥 개강한 기념 수업시간에 배우는 자료구조 내용을 꾸준히 정리해보도록 하겠습니닷,,~~~ 갓생 살자. . 사실 매주 퀴즈본다고 하시길래 매주 고통스러울 예정, , ,~😫

수업 내용 정리에 관한 썸네일은 안 예쁘지만 통일감을 주기 위해 우리 교재로 정했습니닷😟 챕터1은 도저히 정리하기 싫어서 패스해야즤,,ㅋㅋㅎ

---

이번 챕터에서는 자료구조에 대한 전반적인 설명과 자료구조 중 배열에 대해 공부하였다.

💡 Data

📌 데이터란?
데이터란 명사로 표현된다:

• 객체지향프로그래밍에서는 객체로 표현
• 절차지향프로그래밍에서는 information으로 표현

데이터는 복잡한 형태이기 때문에 데이터를 분류해주는 작업이 필요하다.
▶ 데이터 Abstraction와 데이터 Encapsulation

💡 Data Encapsulation

데이터를 Application과 Logical 레벨로 분리해서 생각하는 것

📌 Encapsulated C++ 자료형 int

int형 표현은 64bit Logical 레벨에서 실행 과정에 대한 이해가 필요한데 현재 우리가 Application레벨에서 사용할 때는 그 실행 과정을 이해하지 않고 사용할 수 있음.

💡 Abstract Data Type (ADT)
내가 만든 자료구조를 실제로 사용하는 사람이 실행하는데 있어서 구현 과정의 이해없이도 간단한 설명만으로 사용할 수 있도록 만드는 자료형이다!

📌 Application(User) 레벨과 Implementation 레벨이 소통하기 위해 필요한 ADT

그렇다면 자료구조는 무엇인가?

💡 Data Structure

📌 자료구조란?

• 데이터 요소들의 집합이다.
• ADT로 데이터들의 실행을 구현한다.

자료구조를 구현하기 위해서는 ADT의 연산자들이 필요한데, 다음과 같다.

• Constructor
  새로운 객체를 생성했을 때 연산자
• Transformer
  자료구조의 데이터 값을 변경하기 위한 연산자
• Observer
  자료구조의 데이터 값을 바꾸진 않고 참고하기 위한 연산자
• Iterator
  자료구조의 다음 데이터 값을 접근하기 위한 연산자

📒 Abstraction and Built-in Types

추상 자료형에는 int 나 float 처럼 기계어 레벨의 연산자의 간단한 built-in 자료형도 있고, 프로그래밍 언어로 제공되는 composite 자료형도 있다.

📌 Composite Data Type

• 개별 데이터 집합 하나의 변수로 저장
• 개별 데이터 접근 허용

을 목적으로 하는 자료형이다.

예를 들면, int a; float b; 를 변수 AB라는 이름으로 각각의 데이터에 접근할 수 있도록 하는 것이다.

Composite자료형은 두 종류로 나눌 수 있는데, 다음과 같다.

C++에서 Built-In 자료형과 Composite 자료형을 정리해보면 🔽아래 그림🔽과 같이 나타낼 수 있다.

💡 레벨 별 Records 에 대한 이해

📗 Records at the Logical Level

Record는 c++에서의 구조체나 클래스와 같은 의미이다.
위와 같은 Record에서 각각의 멤버는 다른 자료형을 가진 데이터의 집합으로 이루어져있다.

struct CarType
{
	int year;
    	char maker[10];
        float price;
};
CarType thisCar; //Cartype형 변수
CarType myCar;

위와 같이 구조체의 멤버에 접근하기 위해서는 member selection operator(period .)연산자를 사용한다. myCar.year나 thisCar.maker[4]처럼 각각의 변수(객체)의 멤버에 접근할 수 있다.

📌 구조체타입 변수의 연산자

• 같은 자료형의 구조체 변수에 할당

CarType thisCar;
CarType myCar;
thisCar = myCar;

• 함수에서 매개변수로 전달
  (pass-by-value 혹은 pass-by-reference)

void f(CarType a) //void f(CarType &a)
{
.
.
.
}

f(thisCar);

• 함수에서 구조체 변수 값 반환

📒 Records at the Application Level

Application 레벨에서 Record는 객체를 의미한다.

• 객체에 대한 다양한 유형의 데이터 수집
• 단일 이름으로 전체 객체 참조
• 객체의 여러 멤버를 이름으로 참조

📕 Records at the Implementation Level

지금까지 우리가 사용하는 자료구조는 Application 레벨에서 사용해왔다. 그렇다면 이러한 Records가 어떻게 구현되는지, 즉 메모리에 어떻게 할당되는지 생각해봐야한다.

• Base address
  record에서 첫 번째 요소를 저장하는 위치
• Member-length-offest 표
  record의 각 멤버에 필요한 위치

구조체에서 각 멤버 변수가 가지는 메모리 크기를 생각해서 앞의 CarType 구조체의 표를 작성해볼 수 있다.

멤버변수	메모리 위치
year	0
maker	4
price	14

int형 변수 year은 4byte를 차지하고,그 뒤에 char형 변수 maker은 1byte인데 10크기를 가지는 배열이므로 총 10byte를 차지하고, float형 변수가 그 뒤에 나온다.

여기서 Base address가 8000이라면 각각의 멤버 변수의 메모리 할당 위치는 8000, 8004, 8014가 되는 것이다.

💡 레벨 별 일차원배열에 대한 이해

📗 One-Dimensional Array at the Logical Level

1차원 배열은 같은 자료형의 집합으로 유한하고 고정된 크기(컴파일 타임에 알아야함)를 가져야하는 자료구조이다.

📚 배열은 할당 연산자가 존재하지 않는다.
int a[4]];
b = a;
.
.
따라서 배열 자체가 return되지 않음. 배열 변수가 return되는 경우는 시작 주소가 반환되는 경우이다.

📚 배열은 컴파일 타임에 결정됨
int a = 4;
int b[a];
배열은 컴파일 타임에 결정되어야하기 때문에 배열의 크기를 정할 때 변수가 들어갈 수 없음.

• 모든 요소들에 상대적 위치가 있고 직접 접근할 수 있음.
• 배열 연산 : 인덱스값에 접근하여 수행함.
  생성, 값 저장, 값 검색

📚 배열은 함수의 매개변수로 전달될 때 pass-by-reference로 전달됨.

void f(int array[]) 
//void f(int *array)로 표현할 수 있음.
{
.
.
.
}

📒 One-Dimensional Array at the Application Level

일차원 배열은 Application 레벨에서 데이터의 요소의 리스트로 저장할 때 사용한다.

◻ 배열 예시

• 식료품 리스트
• 가격 리스트
• 전화번호 리스트
• character의 리스트 (문자열)

📕 One-Dimensional Array at the Implementation Level

그림보고 이해하라고 ㅋㅋ~
넘겨야징ㅋㅎ
.
.
.
배열에는 일차원이 아닌 이차원, 삼차원 등 다차원 배열도 존재한다. 연산은 일차원 배열과 동일하다. 이차원의 경우 row, column 인덱스 값을 가진다.

• 이차원 배열은 보통 테이블 형태에서 표현할 때 사용한다.
  이것도 그림을 보면 쉽게 이해할 수 있다😆 교수님께서 이 테이블 그림은 마음 속에 있다고 하신다,,, '마음'이란 단어를 정말 좋아하시는 것 같다,,^^

📌 이차원 배열의 메모리 저장
이차원 배열에서 먼저 row(행)의 메모리 위치를 저장하고 그 다음 column(열)의 row로 넘어가 메모리 위치를 순차적으로 저장한다.
(대부분의 언어에서는 row-order 방식으로 저장한다.)

위의 내용을 그림으로 정리하면 🔽아래🔽와 같다.
행과 열이 정해져 있기 때문에 실제 런타임에서 바로 계산할 수 있음.