[알고리즘] 순자 자료구조와 선형 리스트(자료구조5)

목차

# 순차 자료구조의 개념

자료는 구조화하는 방법에 따라 리스트, 스택, 큐, 데크, 트리, 그래프 등으로 나뉘는데 이러한 자료구조 유형을 프로그램으로 구현하는 방식에는 순차 자료구조와 연결 자료구조가 있다.

 

순차 자료구조

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

연산 특징 : 삽입, 삭제 연산을 해도 빈자리 없이 자료가 순서대로 연속하여 저장되며 변경된 논리적인 순서와 저장된 물리적인 순서가 일치.

 프로그램 기법 : 배열을 이용하여 구현

 

연결 자료구조

메모리 저장 방식 :  연결 자료 구조는 노드라고 하는 여러 개의 메모리 청크에 데이터를 저장하며, 메모리에 저장된 물리적 위치나 순서와 상관없이, 링크에 의해 논리적인 순서를 표현하는 방식.

연산 특징 : 삽입, 삭제 연산을 하여 논리적인 순서가 바뀌어도, 링크 정보만 변경되며 물리적인 순서는 변하지 않는다.

 프로그램 기법 : 포인터를 이용하여 구현

# 선형 리스트의 표현

자료의 특징(추상 자료형)과 주로 사용할 연산(알고리즘)에 따라 최적의 형태로 자료를 구조화하는데, 자료를 구조화하는 가장 기본적인 방법은 나열하는 것이다.

밑에 표처럼 전화번호나 이름 또는 생일을 나열한 것을 목록 리스트라고 하며

전화번호		이름		생일
010-1111-1111		홍00		2000-01-11
010-2222-2222		김00		2000-03-19
010-3333-3333		나00		2000-07-20
010-4444-4444		권00		2000-010-30
010-5555-5555		서00		2000-12-22

원소들을 순서대로 나열한 리스트를 선형 리스트 또는 순서 리스트라고 한다.

전화번호			이름				생일
1	010-1111-1111		1	홍00		1	2000-01-11
2	010-2222-2222		2	김00		2	2000-03-19
3	010-3333-3333		3	나00		3	2000-07-20
4	010-4444-4444		4	권00		4	2000-010-30
5	010-5555-5555		5	서00		5	2000-12-22

선형 리스트는 메모리에 저장하는 구현 방식에 따라 순차 방식으로 구현하는 순차 리스트와 연결 방식으로 구현하는 선형 연결 리스트로 나뉜다. 일반적으로 선형 순차 리스트를 선형 리스트라고 하며, 선형 연결 리스트를 연결 리스트라고 한다.

선형 리스트의 배열 표현

밑에 코드는 선형 리스트로 메모리 주소가 순서적으로 4바이트씩 증가하며, 원소의 값을 출력하는 원소의 논리적, 물리적 순서를 확인하는 코드이다.

sizeof(money)는 12를 반환하며, 이에 sizeof(int)로 나눈다면 배열의 길이를 알 수 있다.

#include <stdio.h>

int main(int argc, char* argv[]){
    int i;
    int money[4] = {100, 200, 300, 400};
    
    for(int i = 0; i < sizeof(money) / sizeof(int); i++){
        printf("메모리 주소 : %u, 원소 값 : %d\n", &money[i], money[i]);
    }
    return 0;
}
--------------------
메모리 주소 : 1876947520, 원소 값 : 100
메모리 주소 : 1876947524, 원소 값 : 200
메모리 주소 : 1876947528, 원소 값 : 300
메모리 주소 : 1876947532, 원소 값 : 400

밑에 코드는 2차원 배열을 사용한다. 밑에 코드도 1차원 배열과 마찬가지로 메모리 주소가 4씩(int의 크기 = 4byte) 증가한다.

#include <stdio.h>

int main(int argc, char* argv[]){
    int i;
    int money[2][4] = {100, 200, 300, 400, 500, 600, 700, 800};
    
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 4; j++)
            printf("메모리 주소 : %u, 원소 값 : %d\n", &money[i][j], money[i][j]);
    return 0;
}
----------------------
메모리 주소 : 1876947504, 원소 값 : 100
메모리 주소 : 1876947508, 원소 값 : 200
메모리 주소 : 1876947512, 원소 값 : 300
메모리 주소 : 1876947516, 원소 값 : 400
메모리 주소 : 1876947520, 원소 값 : 500
메모리 주소 : 1876947524, 원소 값 : 600
메모리 주소 : 1876947528, 원소 값 : 700
메모리 주소 : 1876947532, 원소 값 : 800

밑에 코드는 3차원 배열을 사용한다. 밑에 코드도 1, 2차원 배열과 마찬가지로 메모리 주소가 4씩(int의 크기 = 4byte) 증가한다.

#include <stdio.h>

int main(int argc, char* argv[]){
    int i;
    int money[2][2][4] = {100, 200, 300, 400, 500, 600, 700, 800, 100, 200, 300, 400, 500, 600, 700, 800};
    
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 4; k++)
                printf("메모리 주소 : %u, 원소 값 : %d\n", &money[i][j][k], money[i][j][k]);
    return 0;
}
------------------------------
메모리 주소 : 1876947480, 원소 값 : 100
메모리 주소 : 1876947484, 원소 값 : 200
메모리 주소 : 1876947488, 원소 값 : 300
메모리 주소 : 1876947492, 원소 값 : 400
메모리 주소 : 1876947496, 원소 값 : 500
메모리 주소 : 1876947500, 원소 값 : 600
메모리 주소 : 1876947504, 원소 값 : 700
메모리 주소 : 1876947508, 원소 값 : 800
메모리 주소 : 1876947512, 원소 값 : 100
메모리 주소 : 1876947516, 원소 값 : 200
메모리 주소 : 1876947520, 원소 값 : 300
메모리 주소 : 1876947524, 원소 값 : 400
메모리 주소 : 1876947528, 원소 값 : 500
메모리 주소 : 1876947532, 원소 값 : 600
메모리 주소 : 1876947536, 원소 값 : 700
메모리 주소 : 1876947540, 원소 값 : 800

별거 아니지 않나? 그냥 배열과 같은 개념이라고 보면된다.

선형 리스트 프로그램

위의 개념을 이용해서 프로그램을 만들 수 있다. 삽입(push)과 삭제(pop) 기능을 구현해 볼 것이다.

// 배열에 몇개의 원소가 있는지 확인하는 함수.
int countList(int list[]){
    int count = 0;
    for(int i = 0; NULL != list[i]; i++){
        count++;
    }
    return count;
}

// 선형 리스트 출력하는 함수
void printList(int list[]){
    for(int i = 0; i < countList(list); i++){
        printf("%d ", list[i]);
    }
    puts("\n");
}

// push 함수
void insertElement(int list[], int x){
    if (countList(list) >= MAX) {
            printf("배열이 가득 찼습니다. 더 이상 요소를 추가할 수 없습니다.\n");
            return;
        
    } else if( countList(list) == 0){
        list[0] = x;
        printList(list);
        return;
    }
    
    for(int i = 0; i < countList(list); i++){
        if(list[i] <= x && (i == countList(list) - 1 || x <= list[i + 1])){
            for(int j = countList(list) - 1; j > i; j--){
                list[j + 1] = list[j];
            }
            list[i + 1] = x;
            break;
        }
    }
    printList(list);
}

// pop 함수
void deleteElement(int list[], int x){
    if(countList(list) == 0){
        printf("배열이 비어있습니다.\n");
        return;
    }
    for(int i = 0; i < countList(list); i++){
        if(list[i] == x){
            for(int j = i; j < countList(list); j++){
                list[j] = list[j + 1];
            }
            break;
        } else if (i == countList(list) - 1){
            printf("입력한 %d가 배열의 원소에 없습니다.\n", x);
            break;
        }
    }
    printList(list);
}

// 메인 함수
int main(int argc, char* argv[]){
    int s, x;
    while(s != 0){
        printf("삽입(1)\n");
        printf("삭제(2)\n");
        printf("번호를 입력 : "); scanf("%d", &s);
        if(s == 1){
            printf("값을 입력 : "); scanf("%d", &x);
            insertElement(list, x);
        }
        else if(s == 2){
            printf("값을 입력 : "); scanf("%d", &x);
            deleteElement(list, x);
        } else{
            return 0;
        }
    }
}