Kim Ji Soo

I am an amazing person.

순차구조

순차 자료구조(sequential structure)

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

논리적인 순서와 물리적인 순서가 항상 일치함
순차 자료구조는 배열을 이용하여 구현함

구분 순차 자료구조 연결 자료구조
메모리 저장 방식 - 메모리의 저장 시작 위치 부터 빈자리 없이 자료를 순서대로 연속하여 저장
- 논리적인 순서와 물리적인 순서가 일치하는 구현 방식 		메모리에 저장된 물리적 위치나 물리적 순서와 상관없이 링크에 의해 논리적인 순서를 표현하는 구현 방식
연산 특징 - 삽입, 삭제 연산을 해도 빈자리 없이 자료가 순서대로 연속하여 저장
- 변경된 논리적인 순서와 저장된 물리적인 순서가 일치 		삽입, 삭제 연산을 하여 논리적인 순서가 변경되어도, 링크 정보만 변경되고 물리적인 순서는 변경되지 않음
프로그램 기법 배열을 이용한 구현 포틴터를 이용한 구현


선형 리스트 (linear list)

개요

자료를 구조화하는 가장 기본적인 방법으로서 자료를 나열한 목록 또는 자료들 간에 순서를 갖는 리스트

  • 순서 -> 원소의 특성에 의한 논리적 순서
  • 리스트 -> 원소들을 일렬로 정렬해 놓은 것
  • 리스트의 자료는 노드(node)또는 요소(element)라고 함

특징

자료들이 순서대로 연속적으로 메모리에 저장됨

  • 원소들의 논리적 순서와 같은 순서로 기억공간에 저장(순차구조)
  • 원소들의 논리적 순서 = 원소들이 저장된 물리적 순서

삽입, 삭제 시 순서에 변함이 없음
접근속도(access time)가 빠름
알고리즘이 간단함

표현 형식

선형 리스트(선형 순차리스트)에서 원소를 나열한 순서는 원소들의 순서가 됨

표기 => L = (e1,e2,…,en)

  • L = 리스트 이름
  • ei = 자료형이 같은 원소
  • 공백리스트(원소가 하나도 없음) => L = ()

순서 이름 음식 과일
1 소문 김치찌개 사과
2 홍길동 짜장면 딸기
3 이순신 된장찌개 토마토
4 윤봉길 비빔밥 귤


선형 리스트의 ADT(Abstract Data Type)


ADT Linearlist
데이터
{0, 1, 2, 3, 4}와 같이 자료형이 같은 원소의 유한집합
연산자 및 연산내용 // L∈List, i∈Index, x∈Element, n∈integer
List create() //하나의 공백 리스트를 생성
Boolean isEmpty(L) //리스트가 공백이면 true, 그렇지 않으면 false를 반환
integer length(L) //리스트 L의 길이(원소의 개수)를 계산
Element retrieve(L, i) //리스트 L의 i번째 원소를 검색(1≤i≤L)
List replace(L, x, y) //리스트 L의 원소 x를 원소 y로 대체
Element delete(L, x) //리스트 L에서 원소 x를 삭제, 리스트 길이는 하나 감소
List insert(L, i, x) //리스트 L에 원소 x를 i번째에 삽입, 리스트 길이는 하나 증가
End Linearlist



선형 리스트의 저장

선형 리스트의 저장과 원소 위치 계산

원소들이 나열된 논리적인 순서와 메모리에 저장되는 물리적인 순서가 일치하는 순차 자료구조 방식(배열)으로 구현

  • 원소를 논리적인 순서대로 메모리에 연속하여 저장
  • 선형 연결 리스트 - 연결 방식으로 구현(포인터)

e.g.) 학생 이름 리스트가 메모리에 저장된 경우

스크린샷 2023-09-09 211047

  • 리스트가 저장된 시작 위치 = α
  • 원소의 길이 = ℓ
  • i번째 원소의 위치 = α + (i-1)ⅹℓ


선형 리스트의 원소 삽입

원소의 삽입

선형리스트 중간에 원소가 삽입되면 그 이후의 원소들은 한 자리씩 자리를 뒤로 이동하여 물리적 순서를 논리적 순서와 일치시켜야 함

삽입 방법

원소를 삽입할 빈 자리 만들기 => 삽입할 자리 이후의 원소들을 한 자리씩 뒤로 자리 이동
준비한 빈 자리에 원소 삽입

삽입할 자리를 만들기 위한 자리이동 횟수

(n+1)개의 원소로 이루어진 순서리스트에서 k번째 자리에 원소를 삽입하는 경우

  • k번째 원소부터 마지막 n번째 원소까지 (n-k+1)개의 원소를 이동
  • 이동횟수 = n-k+1 = 마지막 원소의 색인 - 삽입할 자리의 색인 + 1

스크린샷 2023-09-09 211850
</br>

선형 리스트의 원소 삭제

원소의 삭제

선형리스트 중간에 원소가 삭제되면 그 이후의 원소들은 한 자리씩 자리를 앞으로 이동하여 물리적 순서를 논리적 순서와 일치시킴

삭제 방법

원소를 삭제
삭제한 빈 자리 채우기 => 삭제한 자리 이후의 원소들을 한 자리씩 앞으로 자리 이동

삭제 후, 빈 자리를 채우기 위한 자리이동 횟수

(n+1)개의 원소로 이루어진 순서리스트에서 k번째 자리의 원소를 삭제한 경우

  • (k+1)번째 원소부터 마지막 n번째 원소까지(n-(k+1)+1)개의 원소를 이동
  • 이동횟수 = n-(k+1)+1 = n - k = 마지막 원소의 색인 - 삭제한 자리의 색인


선형리스트의 삽입/삭제 연산

특징

  • 삭제/삽입 시 후속 원소들을 한자리씩 전/후로 이동
  • 일정시간 내에 리스트의 원소들에 대한 검색 및 갱신이 가능
  • 삽입 시 평균 이동횟수(mi) = n + 1 / 2
  • 삭제 시 평균 이동횟수(md) = n - 1 / 2
  • 리스트의 길이가 클 경우 = (삽입,삭제) ≈ n / 2

배열

정의

동일한 자료형(기본 자료형, 구조체, 포인터 등)들이 <색인, 원소>의 순서쌍으로 집단화한 선형 자료구조(순차적 저장, 유한 집합)

특징

하나의 변수에 여러 값을 저장하는 데 쓰이는 정적 리스트 구조임

  • 원소의 개수가 정해져서 항상 마지막 원소가 존재함

색인(index)를 이용해서 자료형이 같은 데이터를 관리 및 집합 내에서 상대적인 위치 식별(접근)이 가능함

  • 순차적 접근 => 주소 계산이 쉬움
  • 임의 접근 => 주소만 있으면 일정 시간 내에 접근 가능

시스템 데이터 형으로 주로 연속적인 기억공간 할당으로 구현되며 기억공간 할당 방식과는 독립적임

정보의 은닉 => 색인을 가지고 어떻게 원소 값에 접근하느냐는 사용자는 몰라도 됨

배열의 ADT


ADT Array
데이터
<index, element> 쌍들의 집합, index는 순서를 나타내는 1차원 이상의 원소들의
유한집합
연산자 및 연산내용 //a∈Array, i∈Index, e∈Element, n∈integer
Array create(n) //n개의 원소를 가지는 하나의 배열을 생성
Element retrieve(a, i) //<i, e>∈a인 색인 i인 원소를 반환, 
//그렇지 않으면 오류 반환
Array store(a, i, e) //i ∈ Index이면 a∈Array인 배열의 i번째에 원소 e를 저장
//그렇지 않으면 오류 반환
End Array


연산

순회

  • 배열의 모든 원소에 대한 인쇄 및 합산
    • 반복 구조를 이용
    • 실행시간을 빠르게 하기 위해서는 프로그래밍 언어의 저장방법에 맞게 작성 삽입/삭제
  • 각 원소들을 이동해야 하기 때문에 삽입/삭제가 빈번할 경우 배열은 효과적인 자료구조가 아님 => 연결리스트 구조를 이용 정렬 및 탐색

배열의 크기

배열 요소를 참조하기 위해 행/열에 대한 두 개 이상의 색인을 사용

  • 1차원 = (상한1 - 하한1 + 1)
  • 2차원 = (상한1 - 하한1 + 1) x (상한2 - 하한2 + 1)
  • 3차원 = (상한1 - 하한1 + 1) x (상한2 - 하한2 + 1) x (상한3 - 하한3 + 1)


선형 리스트의 구현

배열을 이용하는 방법의 특징

배열의 색인은 배열 원소의 순서를 나타냄

  • 물리적 순서로 논리적 순서를 표현
  • 리스트 원소 ei 와 ei+1 => 배열 색인 i와 i+1에 대응

L = (e1,e2,…,en)

스크린샷 2023-09-09 212349

원소의 크기가 1이고 시작 주소가 b일때

  • n번째 원소의 시작주소(bn) = b + (n - 1) x c

기억장소 이용률 = 정보들의 총수 / 비트들의 총수 = 100%

1차원 배열을 이용한 구현

논리적 구조

  • int sale[4] = {160, 245, 139, 450};

스크린샷 2023-09-09 212523

물리적 구조

스크린샷 2023-09-09 212605

배열의 원소에 대한 물리적 주소를 확인하는 프로그램


#include <stdio.h>
int main(){
    int i, sale[4]={160, 245, 139, 450};
    for (i=0; i<4; i++){
        printf("address of sale[%d]=%d: %u \n", i, sale[i], &(sale[i]));
        }
    return 0;
}

실행 결과

address of sale[0]=160: 6487552
address of sale[1]=245: 6487556
address of sale[2]=139: 6487560
address of sale[3]=450: 6487564


배열에 원소를 삽입하는 프로그램


#include <stdio.h>
#define MAX_SIZE 100
int main(){
    int arr[MAX_SIZE];
    int i, size, num, pos;

    printf("Enter size of the array : "); //배열의 크기를 입력
    scanf("%d", &size); 

    printf("Enter elements in array : "); //배열에 임의의 원소를 입력
    
    for( i=0; i<size; i++){
        scanf("%d", &arr[i]);
    }

    printf("Enter element to insert : "); //삽입할 새로운 원소를 입력
    scanf("%d", &num);

    printf("Enter the element position : "); //삽입할 위치를 입력
    scanf("%d", &pos);

    if(pos > size+1 || pos <= 0){ //삽입 위치에 대한 조건 검사
        printf("Invalid position! Please enter position between 1 to %d", size);
    }
    else {
        for(i=size; i>=pos; i--) { //오른쪽으로 이동, 삽입할 원소의 빈 공간 확보
            arr[i] = arr[i-1];
        }

        arr[pos-1] = num; //새로운 원소를 주어진 위치에 삽입
        size++; //size를 하나 증가
        printf("Array elements after insertion : "); //삽입후 전체 원소 출력
        for(i=0; i<size; i++){printf("%d\t", arr[i]);}
    }

    return 0;
}

실행 결과

Enter size of the array : 4
Enter elements in array : 10 20 30 40
Enter element to insert : 15
Enter the element position : 2
Array elements after insertion : 10 15 20 30 40


배열에서 원소를 삭제하는 프로그램

#include<stdio.h>
#define MAX_SIZE 100

int main(){
    int arr[MAX_SIZE];

    int i, size, pos;

    printf("Enter size of the array: "); // 배열 크기 입력
    scanf("%d", &size);

    printf("Enter elements in array : "); //배열에 임의의 원소를 입력

    for(i=0; i<size; i++){
        scanf("%d", &arr[i]);
    }

    printf("Enter the element position to delete : "); //삭제할 원소의 위치를 입력
    scanf("%d", &pos);

    if(pos < 0 || pos > size){ //삭제 위치에 대한 조건 검사
        printf("Invalid position! Please enter position between 1 to %d", size);
    }
    else{
        for(i=pos-1; i<size-1; i++){ //현재 원소 값을 다음 원소 값으로 복사
            arr[i] = arr[i + 1];
        }
        size--; // size 를 하나 감소
        //삭제 후 전체 원소 출력
        printf("\nElements of array after delete are : ");
        for(i=0; i<size; i++){
            printf("%d\t", arr[i]);
        }
    }

    return 0;
}

실행결과

Enter size of the array : 5
Enter elements in array : 10 20 30 40 50
Enter the element position to delete : 3
Elements of array after delete are : 10 20 40 50


2차원 배열을 이용한 구현

논리적 구조

int sale[2][4] = { {67, 88, 45, 98}, {70, 86, 60, 78} };

스크린샷 2023-09-09 212656

물리적 구조

  • 원소의 위치 계산 방법
    • 행의개수= ni, 열의개수= nj
    • 시작주소= α, 원소의길이=ℓ
    • 행중심 α + (iⅹnj+ j)ⅹℓ
    • 열중심 α + (j ⅹ ni+ i)ⅹℓ

스크린샷 2023-09-09 212733



2차원 배열을 이용한 구현

배열의 크기를 구하는 프로그램


#include <stdio.h>
int main(){
    int numArr[3][4] = { { 11, 22, 33, 44 }, { 55, 66, 77, 88 },
    { 99, 110, 121, 132 } };

    printf("배열의 크기는 %d이다.\n", sizeof(numArr)); //정수 = 4바이트

    int col = sizeof(numArr[0]) / sizeof(int); //배열의 가로 크기

    int row = sizeof(numArr) / sizeof(numArr[0]); //배열의 세로 크기

    printf("배열의 가로 크기는 %d이다.\n", col); 
    printf("배열의 세로 크기는 %d이다.\n", row); 

    return 0;
}

실행결과

배열의 크기는 48이다.
배열의 가로 크기는 4이다.
배열의 세로 크기는 3이다.


배열의 원소에 대한 물리적 주소를 확인하는 프로그램


#include <stdio.h>
int main(){
    int i, j, sale[3][4] = { { 11, 22, 33, 44 }, { 55, 66, 77, 88 }, 
    { 99, 110, 121, 132 } };

    for(i=0; i<3; i++){
        for(j=0; j<4; j++){
            printf("address of sale[%d][%d]=%d: %u \n", i, j, numArr[i][j], &(numArr[i][j]));
        }
    }

    return 0;
}

실행결과

address of sale[0][0]=11: 6487520
address of sale[0][1]=22: 6487524
address of sale[0][2]=33: 6487528
address of sale[0][3]=44: 6487532
address of sale[1][0]=55: 6487536
address of sale[1][1]=66: 6487540
address of sale[1][2]=77: 6487544
address of sale[1][3]=88: 6487548
address of sale[2][0]=99: 6487552
address of sale[2][1]=110: 6487556
address of sale[2][2]=121: 6487560
address of sale[2][3]=132: 6487564


3차원 배열을 이용한 구현

논리적 구조

int sale[2][2][4] = { { {67, 88, 45, 98}, {70, 86, 60, 78} },
{ {55, 80, 50, 87}, {66, 43, 92, 76} } };

스크린샷 2023-09-09 212811



물리적 구조

  • 원소의 위치 계산 방법
    • 면의개수 = nj, 행의개수 = nj
    • 열의개수 = nk, 시작주소 = α
    • 원소의 길이 = ℓ
    • 면중심 => α+{(i ⅹ nj x nk)+(j ⅹ nk) + k} ⅹ ℓ
    • 열중심 => α+{(k ⅹ njⅹ ni)+(j ⅹ ni) + i} ⅹ ℓ



배열의 원소에 대한 물리적 주소를 확인하는 프로그램

#include <stdio.h>
int main(){
    int i, j, k, sale[2][2][4]={ { {67, 88, 45, 98}, {70, 86, 60, 78} },{ {55, 80, 50, 87}, {66, 43, 92, 76} } };

    for(i=0; i<2; i++){
        for(j=0; j<2; j++){
            for(k=0; k<4; k++){
                printf("address of sale[%d][%d][%d]]=%d: %u \n", i, j, k, sale[i][j][k], &(sale[i][j][k]));
            }
        }
    }

    return 0;
}

실행결과

address of sale[[0][0][0]]=67: 6487504
address of sale[[0][0][1]]=88: 6487508
address of sale[[0][0][2]]=45: 6487512
address of sale[[0][0][3]]=98: 6487516
address of sale[[0][1][0]]=70: 6487520
address of sale[[0][1][1]]=86: 6487524
address of sale[[0][1][2]]=60: 6487528
address of sale[[0][1][3]]=78: 6487532
address of sale[[1][0][0]]=55: 6487536
address of sale[[1][0][1]]=80: 6487540
address of sale[[1][0][2]]=50: 6487544
address of sale[[1][0][3]]=87: 6487548
address of sale[[1][1][0]]=66: 6487552
address of sale[[1][1][1]]=43: 6487556
address of sale[[1][1][2]]=92: 6487560
address of sale[[1][1][3]]=76: 6487564


학습정리

리스트, 스택, 큐와 같은 순차구조와 트리, 그래프와 같은 비순차구조는 프로그램으로 구현하는 방식에 따라 순차 자료구조와 연결 자료구조로 나눌 수 있다.

순차 자료구조는 구현할 자료들을 논리적인 순서대로 메모리에 연속하여 저장하는 구현 방식이다. 따라서 순차 자료구조는 논리적인 순서와 물리적인 순서가 항상 일치해야 한다.

일반적으로 순차 자료구조는 배열을 통해 구현하고, 연결 자료구조의 경우는 포인터 개념을 이용하여 구현할 수 있다.

선형 리스트(순차 리스트)는 자료를 구조화하는 가장 기본적인 방법으로서 자료를 나열한 목록 또는 자료들 간에 순서를 갖는 리스트이다.

선형 리스트의 삭제/삽입 시 원소들의 순서를 만족하기 위해 후속 원소들을 한 자리씩 전후로 이동해야 한다.

배열은 동일한 자료형(기본자료형, 구조체, 포인터등)들이 <색인,원소>의 순서쌍으로 집단화한 선형 자료구조(순차적저장, 유한집합)이다.

You may also enjoy