[데이터 구조] 6차시 선형 리스트와 다항식 추상 데이터 타입 | C의 데이터 타입

모듈1. C에서의 데이터 타입

1) 선언과 정의

• 선언(declaration)과 정의(definition)를 구분하는 기준은 "memory address binding의 유뮤"
• 어떤 대상의 이름에 대해 그에 대응하는 메모리 상의 주소가 정해진다면 그것은 정의
• 그렇지 않고 이름만 알려준다면 그것은 선언

int x;	//선언함과 동시에 변수를 정의함
int x = 5;	//선언함과 동시에 변수를 정의하고, 값을 할당함
int x(){ return 0; }	// 선언과 동시에 정의, 호출 시 jump해야 하기 때문

struct x { int i; }
// 선언과 동시에 정의
// 구조체가 구조체 변수로 인스턴스화 할 때 어떻게 메모리가 배치될 지를 알려주는 문장

extern int x;	// 선언, 다른 모듈에서 정의된 변수를 이름만 임포트
int x();	// 선언, 함수의 프로토타입 선언
struct x;	// 선언, 이름만 컴파일러에게 알려주는 행위
typedef int INT;	// 선언, 타입 이름 자체가 메모리 바인딩될 수 없음

 

 

2) C에서의 데이터 타입

(1) C의 배열 타입
: 정수(int), 문자(char), 부동소수(double) 등의 원시 타입은 물론, 구조체 타입의 배열도 허용

 

(2) 배열의 선언

• 대괄호([ ])와 함께 표기
• 일반 변수와 같은 형식으로 선언
• 예) 정수 배열 선언 - int a[100];

 

(3) 배열을 접근하는 연산

• 검색과 저장
• 배열 이름과 인덱스로 표현
  eg) k = a[5];   a[2] = 6;
• 선언된 배열의 원소 값들이 지정되기 전에는 모두 미정(undefined)

 

(4) 인덱스 범위(index range)

• 하단 경계와 상단 경계 사이의 값
  ▶ 하단 경계(lower bound): 제일 작은 인덱스 값, 항상 0
  ▶ 상단 경계(upper bound): 제일 큰 인덱스 값, 선언할 때 명시함
  * 하단 경계와 상단 경계는 변경 불가능함
  
  
• 인덱스가 이 범위를 넘어 지칭하면, 프로그램에서 에러 발생

 

(5) 배열의 크기(길이)

• 상단 경계 - 하단경계 + 1
• 배열의 선언과 동시에 정의되고 고정됨

 

(6) 심벌 상수(symbolic constant)

- 배열 선언을 보다 융통성 있게 만들기 위해서 이용

 

- 배열을 상수로 초기화하는 프로그램(심벌 상수로 초기화하는 프로그램과 비교해 볼 것)

int a[100];
for(i=0; i<100; ++i)
	a[i]=0;

 

- 배열을 심벌 상수로 초기화하는 프로그램

#define N 100

int a[N];
for (i=0; i<N; ++i)
	a[i]=0;

 

(7) 배열의 선언과 초기화 동시에 가능

// 예시
int a[100] = {0};
float f[5] = {0.0, 1.0, 2.0, 3.0, 4.0};

// 정수형(integer) 배열의 선언과 초기화 예시
int a[4] = {0, 1, 3, -4};
int a[] = {0, 1, 3, -4};

// 문자(character) 배열의 선언과 초기화 예시
char s[] = "abc";
char s[] = {'a', 'b', 'c', '\0'}; // '\0'은 끝을 나타내는 널(null) 문자

 

 

(8) C에서의 2차원 배열

- 행(row)과 열(column)을 표현하는 2개의 인덱스로 명세

- 행 우선(row-major)으로 표현

 

 

 

(9) C에서의 3차원 배열

- 면(plane), 행(row), 열(column)을 표현하는 3개의 인덱스로 명세

 

 

(10) 구조(struct) 데이터 타입의 배열

- Struct Data Type

• 이질 데이터(heterogeneous data)를 그룹 지어 처리
• 사용자로 하여금 데이터 타입을 정의하여 사용할 수 있도록 허용
• structure의 준말
• 몇 개의 상이한 필드 즉 멤버(member)로 구성

 

 

(11) 배열 vs 구조

- 배열(array): 타입이 같은 데이터들을 하나로 묶는 방법

- 구조체(structure): 타입이 다른 데이터를 하나로 묶는 방법

 

 

 

 

 

 

 

 

 

 

모듈2. 선형 리스트

1) 선형 리스트

(1) 리스트(list)

: 원소들의 순열(sequence)로써 원소들을 일렬로 정렬해 놓은 것

 

 

(2) 선형 리스트(linear list)

• 순서를 가진 원소들의 순열(sequence)
• 물리적 순서가 아닌 원소의 특성에 의한 논리적 순서를 의미
• 리스트는 기본적으로 순서 개념을 가지므로 선형 리스트라고 볼 수 있음

 

(3) 리스트의 표기

 

 

2) 리스트 ADT

(1) 리스트 처리 연산의 정의

• createList(): 초기에 공백리스트 L을 생성
• isEmpty(L): 리스트 L이 공백인지 아닌지 결정
• length(L): 리스트 L의 길이를 계산함. 여기서 리스트 길이는 리스트에 포함된 원소의 수. 공백 리스트의 길이는 0
• retrieve(L, i): 리스트 L의 i원소를 검색(1 <= i <= L의 길이)
• replace(L, x, y): 리스트 L의 원소 x를 새로운 원소 y로 대체
• delete(L, x): 공백이 아닌 리스트 L로부터 원소 x를 제거. 이때 리스트 L의 길이는 하나 감소
• insert(L, i, x): 새로운 원소 x를 리스트 L의 지정된 위치 i에 삽입. 리스트 L의 길이는 1 증가

insert(L, i, x)의 결과

 

3) 리스트의 표현

- 배열을 이용한 표현: 순차 표현 리스트

✅ 삽입, 삭제 시에 후속 원소들을 한 자리씩 밀거나 당겨야 하는 오버헤드가 치명적인 약점

 

 

 

 

 

 

모듈3. 다항식 추상 데이터 타입

1) 다항식

- 다항식(Polynomial)은 계수 X 변수^지수의 형태를 가지는 항들의 집합으로 구성된다.

 

 

 

2) 다항식 ADT

이게 뭐람 ....

 

3) 다항식 연산의 구현

(1) 다항식 생성 ⭐

- 모든 다항식은 기본적으로 연산 zeroP()와 addTerm()을 이용해 생성할 수 있음

 

(2) 다항식의 표현 시 가정

• 모든 항은 지수에 따라 내림차순으로 정렬
• 모든 항의 지수는 상이함
• 계수가 0인 항은 포함하지 않음

 

(3) 다항식의 덧셈: 두 다항식의 항들의 지수를 비교하여 합병, 복사, 삭제를 수행

 

 

4) 다항식의 표현

(1) 모든 "차수"에 대한 "계수값"만을 배열에 저장하는 방법 - 하나의 다항식을 하나의 배열로 표현

- 문제점: Space 낭비(0인 coefficient가 매우 많아 공간 낭비)

eg) 2 * x^1000 + 1

 

 

 

(2) 계수와 지수가 존재하는 항만을 골라서 쌍으로 표현하는 방법

 

- 예제: 계수와 지수가 존재하는 항만을 쌍으로 저장하기 위한 C 선언문

#define MAX_TERMS 100 /*지수가 존재하는 term 최대수 가정*/

typedef struct{
    float coef; //계수
    int expon; //지수-쌍으로 저장함
} polynomial;

polynomial term[MAX_TERMS];
int avail = 0; /*다음 번 빈 슬롯의 array index 번호 유지*/

 

 

- 예제: 다항식 두 개를 하나의 배열에 표현

• 장점1: 0항이 많은 다항식(polynomial)에 유용함
• 장점2: 여러 개의 다항식을 하나의 배열에 저장 가능함
  
  
• 단점: 모든 항이 0이 아니면, memory를 최대 2배나 더 소모하게 됨(다항식의 표현법 1보다, 지수항까지도 추가로 더 저장해야 하므로)