자료구조 | Structure, Array, 다항식

여경·2021년 6월 10일

TIL 자료구조

CS

목록 보기

9/16

21/06/09 자료구조 및 실습 반추

Basic - 4. structure

Structure란?

structure - 하나의 데이터 타입이 아니라 여러개의 데이터 타입이 모여서 하나의 개체를 설명하기위해 선언하는 것.
각각의 요소들에 대해서 메모리 공간을 할당해준다.

사람에 대해 그 사람의 이름, 나이, 급여를 관리한다.

struct {
char name[10];
int age;
float salary;
} person;

사람이라는 변수 하나가 세가지의 정보들을 가지고 있는 것. 사람 한명 당 매번 새로운 변수로 선언하여 복붙해줘야하는 상황 발생

구조체 데이터 타입을 선언해주어 typedef, 사용자가 자체적으로 데이터 타입을 선언해주는 것이 가능하고 선언이 되고 나서는 person1, person2, person array 등의 선언이 가능해짐. 변경사항이 있다면 데이터 타입만 수정 하면 모든 부분을 바꿀 수 있다!

union이란?

union: 모여 있는 것 (합집합의 개념), 단일 메모리 사용

예시1

typedef struct sexType {
 enum tagField {female, male} sex;
 union {
   int children;
   int beard;
   } u;
};

u에 어떤 때에는 children, 어떤 때에는 beard로 부르며 메모리 공간을 하나만 할당해놓고 사용함.

예시2

typedef struct humanbeing {
    char name[10];
    int age;
    date dob;
    sexType sexInfo;
    };

sexType이라는 데이터 타입을 선언하고, 성별에 대한 명칭을 가지고 있고 그에 대한 성 정보를 저장한다는 것을 의미함. 여성,남성 각각을 위한 데이터타입을 선언하지 않고 성이라는 데이터타입을 선언하고 여성일 때, 남성일 때 다르게 사용하겠다는 뜻.

예시1과 2의 사용방법

person1.sexInfo.sex=male;
person1.sexInfo.u.beard=FAlSE;
//person1 = 남성, 수염없음
//또는
person1.sexInfo.sex=female;
person1.sexInfo.u.childern=4;
//person1 = 여성, 자녀4명

female, beard=true 로 한다면 컴파일 오류?
오류라고 판단하지 않음. 모름. union의 context는 프로그래머가 결정하기 때문에 유의해야함!

pointer
자기자신에 대한 포인터를 선언하고 그것을 요소로 갖고 있음.
linked list, tree할 때 많이 사용하게 됨.

typedef struct list *listPtr;
typedef struct list {
        char data;
        listPtr link;
};

Array 응용 예제

polynomial (다항식)
d 를 초기화
a 나 b가 비어있지 않으면
a와 b의 가장 앞에 있는 값의 거듭제곱 항을 비교하여
작으면?
크면?
같으면?

다항식 표현 방식 1 이 다항식 자체를 하나의 데이터 타입으로 완성한다.
이 다항식의 최고 거듭제곱이 얼마인지, 그 각각의 항에서의 계수값이 얼마인지 저장하는 법

문제는? max_degree
모든항에 계수를 가지고 있지 않기 때문에 낭비가 심함. 거듭제곱의 값이 많이 크지 않고, 항들이 잘 채워진 경우에 유용함.

다항식 표현방식 2 항들의 집합이니 각 항의 계수가 얼마고, 거듭제곱이 얼마인지 저장하여 array로 표현
항하나를 표현하기 위해서 거듭제곱과 계수값을 갖는 배열을 만듦.
ex) 다항식 A의 계수 2의 거듭제곱 1000, 계수 1의 거듭제곱 0 값을 저장하고, 그 뒤에는 B 다항식 시작. B의 계수 1의 거듭제곱 4, 10의 3... 그 이후 남는 공간에 A와 B의 덧셈을 해서 만들어진 값을 저장한다. 목표는 A,B, 그리고 더해진 값들의 저장을 끝내고 그 다음 비어있는 공간을 가리키게 하고있는 것이 목표
A와 B식, 그리고 더해진 값을 모두 저장하기 때문에 그 값들이 시작하는 위치를 기억하고 있어야함!
output parameter로 위치 값을 기억하도록 변수 선언할것.