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

내용 정리

 

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

 

 

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

 

 

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

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

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

 

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

 

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

 

 

#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;
}
 
 

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

 

 

시작 위치의 주소가 a이고

원소 1개의 크기가 k이면

 

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

 

 

 

원소 삭제, 삽입은

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

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

 

 

예를 들어서

2015년 데이터가 인덱스 0에

2017년 데이터가 인덱스 1에

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

 

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

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

 

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

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

 

1차원 배열뿐만 아니라

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

 

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

 

 

 

연습문제 풀이

 

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

 

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

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

 

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

//다항식의 덧셈
#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;
}
 

 

다항식의 덧셈 실행결과