배열
- <index , element> 쌍의 집합
- 각 항목의 값은 인덱스 번호로 위치가 계산되어 참조
- 직접 접근 방식, 접근 시간 복잡도 : O(1)
ADT
객체 : < Index, element> 쌍의 집합
연산
- create(size) ::= size개의 요소를 저장할 수 있는 배열 생성
- get(A, i) ::= 배열 A의 i번째 요소 반혼
- set(A, i, v) ::= 배열 A의 i번째 위치에 값 v 저장
1차원 배열의 주소
- 가장 첫 번째 인덱스 base
- 인덱스를 n이라고 했을 때 arr [n] = base + nsizeof(자료형)
- ex) int A [6]
- A [0] : base
- A [2] : base + 2*sizeof(int)
2차원 배열의 주소
- 현재 사용하는 것은 행우선 배열(row-major order array)
Call by value vs Call by reference
- 배열을 매개변수로 전달하는 것은 주소를 전달 → Call by reference
#include <stdio.h>
void callByValue(int x){
x += 1;
}
void callByReference(int a[],int len){
for(int i = 0; i< len; i++){
a[i] += 1;
}
}
int main(){
int x = 1;
int a[5] = {1,1,1,1,1};
int len = 5;
printf("전 x = %d, 전 %d %d %d %d %d\n",x,a[0],a[1],a[2],a[3],a[4]);
callByValue(x);
callByReference(a,5);
printf("후 x = %d, 전 %d %d %d %d %d",x,a[0],a[1],a[2],a[3],a[4]);
}
- Call by Value : 매개변수의 복사가 일어나 원본 x에 영향을 주지 못함
- Call by Reference : 매개변수의 주소를 참조했기 때문에 원본 배열의 영향을 줌
구조체
- 타입이 다른 데이터를 하나로 묶는 방법
구조체 사용 방식
- 구조체의 선언과 구조체 변수의 생성
struct person{
int age;
float height;
char* name;
}
int main(){
struct person p;
}
- typedef 이용
//person 생략 가능
typedef struct person{
int age;
float height;
char* name;
}person;
int main(){
person p;
}
배열과 구조체 응용 구현 : 다항식
다항식의 모든 항에 배열 저장
- 모든 차수에 대한 계수값을 배열로 저장
- 하나의 다항식을 하나의 배열로 표현
#define MAX_DEGREE 100
typedef struct {
int degree;
int arr[MAX_DEGREE];
}polynomial;
int main(){
polynomial poly = {5,{10,0,0,0,6,3}};
}- 장점 : 다항식의 각종 연산 간단 구현 가능
- 단점 : 대부분의 항의 계수가 0이면 공간 낭비가 심해짐
다항식 덧셈 연산 구현
#include <stdio.h>
#define MAX_DEGREE 100
typedef struct {
int degree;
int arr[MAX_DEGREE+1];
}polynomial;
polynomial add1(polynomial a, polynomial b){
polynomial c;
int a_degree = a.degree;
int b_degree = b.degree;
int aPos = 0,bPos = 0,cPos = 0;
c.degree = (a.degree > b.degree)? a.degree : b.degree;
while(aPos <= a.degree && bPos <= b.degree){
if(a_degree > b_degree){
c.arr[cPos++] = a.arr[aPos++];
a_degree--;
}
else if(a_degree == b_degree){
c.arr[cPos++] = a.arr[aPos++] + b.arr[bPos++];
a_degree--;
b_degree--;
}
else{
c.arr[cPos++] = b.arr[bPos++];
b_degree--;
}
}
return c;
}
int main(){
polynomial a = {5,{10,1,2,3,4,5}};
polynomial b = {3,{10,1,2,3}};
polynomial c = add1(a,b);
printf("%d\n",c.degree);
for(int i = 0; i <= c.degree; i++) printf("%d ",c.arr[i]);
}
다항식 출력
void poly_read(polynomial a){
for(int i = 0; i < a.degree; i++){
printf("(%dx^%d)+",a.arr[i],a.degree-i);
}
printf("%d",a.arr[a.degree-1]);
}
int main(){
polynomial a = {5,{10,1,2,3,4,5}};
poly_read(a);
}
포인터
- 다른 변수의 주소를 가지고 있는 변수
&연산자 : 변수의 주소 추출*연산자 : 포인터가 가리키는 곳의 내용을 추출
int main(){
int a = 32;
int *p; //포인터 선언
p = &a; // 변수 a의 주소 참조
printf("%d\n",*p);
*p = 4; // 포인터 p가 가리키는 내용 변경
printf("%d",*p);
}
자체 참조 구조체
- 필드 주에 자기 자신을 가리키는 포인터가 한 개 이상 존재하는 구조체
- 연결 리스트나 트리에 많이 등장
#include <stdio.h>
typedef struct{
int age;
Person* link; // 자체 참조
char test;
}Person;
포인터의 포인터
#include <stdio.h>
int main(){
int a = 1;
int *p;
int **pp;
p = &a; // 변수 a의 주소 참조
pp = &p; // 포인터 p의 주소 참조
printf("a의 값 : %d p의 값 : %d pp의 값 : %d\n",a,*p,**pp);
printf("변수 a의 주소 : %d p가 가리키는 주소 : %d *pp가 가리키는 주소 : %d\n",&a,p,*pp);
printf("p의 주소 : %d pp가 가리키는 주소 : %d",&p,pp);
}
- 모두 변수 a의 주소를 참조하고 있기 때문에 값은 1로 같다
- 두 번째 출력에서 주소가 모두 같은 것을 확인할 수 있다.
- 세 번째 출력은 p의 주소인데, 이는 pp가 중간에 p를 한번 참조했다가 다시 한번 참조하는 이중포인터라는 뜻
포인터 관련 연산자
*p++: 포인터가 가리키는 값을 가져온 다음, 포인터를 한 칸 증가*p--: 포인터가 가리키는 값을 가져온 다음, 포인터를 한 칸 감소
(*p)++: 포인터가 가리키는 값을 증가**pp: 포인터를 가리키는 포인터void *p: p는 아무것도 가리키지 않는 포인터void (*f)(int): f는 함수를 가리키는 포인터- 포인터의 형변환 : 필요할 때마다 형변환이 가능
void *p→pi = (int *) p;
- 포인터의 형변환 : 필요할 때마다 형변환이 가능
함수 포인터 매개변수
- 포인터는 주소를 참조하는 것이기 때문에 당연히 Call by Reference
void swap(int* x, int* y){
int tmp = *x;
*x = *y;
*y = tmp;
}
int main(){
int a = 1,b = 2;
swap(&a,&b);
printf("a = %d b = %d",a,b);
}
포인터 사용 시 주의사항
- 포인터가 아무것도 가리키고 있지 않을 때는 NULL로 설정
- int *pi = NULL; → 초기화가 안된 상태에서 사용 금지
- 포인터 타입 간의 변환 시에는 명시적인 타입 변환 사용
int *pi;
float *pf;
pf = (float*)pi;
동적 메모리 할당
정적 메모리 할당- 메모리의 크기를 프로그램 시작 전 결정 → 도중에 크기 변경 불가
- 처음 결정된 크기보다 입력이 더 크면 처리 못하고 더 작으면 메모리 낭비
동적 메모리 할당- 프로그램의 실행 도중에 메모리 할당받는 것
- 필요한 만큼만 할당받고 필요한 때의 사용하고 반납 → 메모리 효율적 사용
- Heap(힙) 사용
동적 메모리 할당 코드
(자료형 *) malloc(sizeof(자료형): 동적 메모리 할당free(동적할당한 변수): 동적 메모리 반납sizeof(자료형): 변수나 타입의 크기 반환(바이트 단위)
struct Person{
int age;
char* name;
};
int main(){
struct Person *p;
p = (struct Person*)malloc(2*sizeof(struct Person));
p ->age = 1;
p->name = "high";
(p+1) ->age = 2;
(p+1) -> name = "How";
free(p);
}