'programming/C++프로그래밍 개념' 카테고리의 글 목록

programming/C++프로그래밍 개념

[C로 배우는 쉬운 자료구조] Chapter3(순차 자료구조와 선형 리스트) 정리 및 연습문제

2021. 5. 27. 09:05

내용 정리

※ 순차 자료구조
구현할 자료들을 논리적인 순서대로 메모리에 연속하여 저장하는 구현 방식
구현 방식 → 배열

※ 순차 자료구조 vs 연결 자료구조
순차 자료구조 - 메모리에 연속하여 저장하여, 논리적인 순서와 물리적인 순서가 일치 (배열)
연결 자료구조 - 메모리에 저장된 위치에 상관없이, 링크에 의해 논리적인 순서를 표현 (포인터)

※ 선형 리스트 vs 연결 리스트
선형 리스트 - 메모리에 저장하는 구현 방식에 따라 순차 방식으로 구현
연결 리스트 - 메모리에 저장하는 구현 방식에 따라 연결 방식으로 구현

→ 순차 방식으로 구현한 리스트 = 선형 리스트
연결 방식으로 구현한 리스트 = 연결 리스트

순차 방식의 리스트는
논리적 순서와 물리적 순서가 일치하기 때문에
원하는 정보가 어떤 인덱스에 있는지 알 수 있다.
→ 간단하게 배열로 구현 가능
구현 용이, but 메모리 공간 낭비, 삽입 삭제에서 원소들의 물리적 이동 연산에 대한 오버헤드 발생

	1월	2월	3월	4월
판매 량	1024	1050	2000	850

위와 같은 데이터가 있고, 배열로 데이터를 저장한다면
판매량만 저장하여도 원소들의 위치를 알 수 있다. (3월 판매량은 index 2에 저장되어있다.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include
int main()
{
    int a[4] = { 1024, 1050, 2000, 850 };
    int search;
 
    printf("몇 월의 판매량을 알고 싶은가?? ");
    scanf("%d", &search);
 
    printf("%d월의 판매량은 %d입니다.", search, a[search-1]);
 
    return 0;
}
 
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter


 

이렇게 말이다. 인덱스 하나로 원하는 정보를 얻을 수 있는 것이다.

시작 위치의 주소가 a이고

원소 1개의 크기가 k이면

n번째 원소의 위치는 = a+(n-1)k이다.

원소 삭제, 삽입은

데이터의 논리적 순서와 물리적 순서가 일치하게 유지하기 위해서

매번 원소의 위치를 조정해야 한다.

예를 들어서

2015년 데이터가 인덱스 0에

2017년 데이터가 인덱스 1에

2018년 데이터가 인덱스 2에 있다면

2016년 데이터를 인덱스 1에 저장해야 하기 때문에

2017, 2018 데이터를 하나씩 뒤로 밀어야 한다.

책에서는 몇 개의 데이터를 옮겨야 하는지 공식으로 정리하였는데

굳이 공식을 알 필요 없이 상황에 맞게 생각하면 금방 알 수 있다.

1차원 배열뿐만 아니라

2차원, 3차원 배열도 순차방식으로 데이터를 다룰 수 있다.

행 우선 순서 방법으로 메모리에 저장된다.

연습문제 풀이

이번 챕터는 연습문제가 부실한 것 같다.

책에서는 다항식의 덧셈을 구조체를 이용하여

다항식의 차수와 각 항의 계수를 저장할 배열을 이용하였다.

나는 간단하게 배열을 사용하여 풀이해보겠다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

//다항식의 덧셈
#include <stdio.h>
#include <stdlib.h>
 
void add(int* a, int* b, int* c)
{
    int i;
    for (i = 0; i < 5; i++)
    {
        c[i] = a[i] + b[i];
    }
}
 
void print(int* arr)
{
    int i;
 
    printf("C(x)= ");
    for (i = 4; i >= 0; i--)
    {
        printf("%dx^%d + ",arr[i],i);
    }
    printf("\b\b");
}
 
int main()
{
    //배열에 다항식의 역순으로 저장 (연산 편하게 하기 위해서)
    int a[5] = { 0, 5, 3, 4, 0 }; //배열 크기 맞춰줌 맨뒤에 0 삽입
    int b[5] = { 1, 2, 0, 1, 3 };
    int c[5]; //a+b저장할 다항식 배열
 
    add(a, b, c);
 
    print(c);
 
    return 0;
}
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

'programming > C++프로그래밍 개념' 카테고리의 다른 글

[C로 배우는 쉬운 자료구조] Chapter2(자료구조 구현을 위한 C프로그래밍 기법) 정리 및 연습문제 (0)	2021.05.26

[C로 배우는 쉬운 자료구조] Chapter2(자료구조 구현을 위한 C프로그래밍 기법) 정리 및 연습문제

2021. 5. 26. 17:02

Chapter2 에는 여러 가지 기법이 있지만

어렵다고 생각되는, 이중 포인터, 재귀호출 이 두 가지를 정리해보겠다.

포인터

내용 정리

포인터에 관련된 내용은 C프로그래밍에서 배웠으니, 이중 포인터만 정리하고 넘어간다.

※ 이중 포인터
포인터의 포인터 즉, 포인터를 가리키고 있는 포인터.

char **ptr의 모습

연습 문제

바로 이중포인터 연습문제 풀이를 통해서, 쉽게 이해 하자.

예제 2-11 포인터 배열과 포인터의 포인터 사용하기.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <stdio.h>
 
int main()
{
    char *ptrarr[2];
    char **dptr;
    int i;
 
    ptrarr[0] = "Seoul";
    ptrarr[1] = "Mapo";
 
    //이중 포인터 변수에 포인터변수의 주소를 할당(배열명은 포인터와 유사)
    dptr = ptrarr;  
    
    //포인터 배열 이용한 출력
    printf("\n ptrarr[0]의 주소 (&ptrarr[0]) = %u", &ptrarr[0]);
    printf("\n ptrarr[0]의 값 (ptrarr[0]) = %u", ptrarr[0]);
    printf("\n ptrarr[0]의 참조값 (*ptrarr[0]) = %c", *ptrarr[0]);
    printf("\n ptrarr[0]의 참조 문자열 (*ptrarr) = %s \n", *ptrarr);
 
    printf("\n ptrarr[1]의 주소 (&ptrarr[1]) = %u", &ptrarr[1]);
    printf("\n ptrarr[1]의 값 (ptrarr[1]) = %u", ptrarr[1]);
    printf("\n ptrarr[1]의 참조값 (*ptrarr[1]) = %c", *ptrarr[1]);
    printf("\n ptrarr[1]의 참조 문자열 (*(ptrarr+1)) = %s \n", *(ptrarr+1));
 
    //이중 포인터 이용한 출력
    printf("\n dptr의 주소 (&dptr) = %u", &dptr);
    printf("\n dptr의 값 (dptr) = %u", dptr);
    printf("\n dptr의 1차 참조값 (*dptr) = %u", *dptr);
    printf("\n dptr의 2차 참조값 (**dptr) = %c", **dptr);
    printf("\n dptr의 2차 참조 문자열 (*dptr) = %s \n", *dptr);
 
    printf("\n ptrarr의 주소 (&ptrarr) = %u", &ptrarr);
    printf("\n ptrarr의 값 (ptrarr) = %u", ptrarr);
    printf("\n ptrarr의 1차 참조값 (*ptrarr) = %u", *ptrarr);
    printf("\n ptrarr의 2차 참조값 (**ptrarr) = %c", **ptrarr);
    printf("\n ptrarr의 2차 참조 문자열 (*ptrarr) = %s \n\n", *ptrarr);
 
    return 0;
}

Colored by Color Scripter

cs

line 10 까지 실행되면, 메모리 구조는 아래와 같다.

line 13 까지 실행되면, dptr도 ptrarr이 가리키고 있는 포인터 배열의 주소를 가리킨다.

파란색 박스는, 실제 메모리 구조는 아니지만, 이해하기 쉽게 하기 위해 그림.

배열명 = 포인터처럼

포인터 배열도 이중 포인터처럼 사용 가능하다.

코드 실행 결과에서 확인 가능하다.

ptrarr의 값 = dptr의 값 = ptrarr[0]의 시작 주소
*ptrarr = *dptr = ptrarr의 값 = Seoul문자열의 시작 주소

포인터는 복잡한 설명보다는, 메모리 구조를 직접 그려보며 이해 하는것이 좋다.

재귀호출

내용 정리

※ 재귀호출
함수가 자기 자신을 호출하여 순환하여 수행되는 것

재귀호출을 사용하면 프로그램을 간단하게 작성할 수 있는 이점이 있다.

같은 유형의 하위 작업이 필요할 때 사용한다.

한 번에 해결할 수 있는 가장 작은 단위의 하위 작업을 베이스케이스라고 한다.

베이스케이스를 잘 정의하고, 재귀호출이 베이스케이스를 향하게 코딩해야 한다.

재귀호출 함수를 가장 잘 보여주는 팩토리얼 문제를 확인해보자.

예제 2-14 재귀호출을 이용해 팩토리얼 값 구하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <stdio.h>
 
unsigned int fact(int);
 
int main()
{
    int n, result;
 
    printf("정수를 입력하세요: ");
    scanf("%d", &n);
    result = fact(n);
    printf("\n\n %d의 팩토리얼 값은 %d입니다.", n, result);
 
    return 0;
}
 
unsigned int fact(int n)
{
    int value;
    if (n <= 1)
    {
        printf("\n fact(1)함수 호출!");
        printf("\n fact(1)함수 반환!");
        return 1;
    }
    else
    {
        printf("\n fact(%d)함수 호출!",n);
        value = (n * fact(n-1));
        printf("\n fact(%d) 값 %d 반환!", n,value);
        return value;
    }
}
Colored by Color Scripter


cs

 

재귀함수인 fact 함수에서

베이스케이스는 n <= 1 인 경우이다.

나머지의 경우는 베이스케이스를 향해 함수를 반복 실행한다.

실행결과를 참고하면 재귀호출의 기본적인 원리를 알 수 있다.

재귀함수는 함수 실행 중 내부 함수 실행

내부 함수 실행 중 또 내부 함수 실행

이때, 베이스 케이스를 만나면

마지막에 실행됐던 함수부터 리턴이 되는 방식이다.

그림으로 표시하면 아래와 같은 순서로 코드가 흘러간다.

다른 대표적인 예로 하노이탑 문제가 있는데, 생략하겠다.

저작자표시 (새창열림)

'programming > C++프로그래밍 개념' 카테고리의 다른 글

[C로 배우는 쉬운 자료구조] Chapter3(순차 자료구조와 선형 리스트) 정리 및 연습문제 (0)	2021.05.27

PREV 1 NEXT

초보개발자