C 언어 자료구조 스터디 [5] <순차 선형 리스트의 삽입과 삭제 및 희소행렬>

 

 

 배열 프로그램을 이용하여 구현할 자료들을 논리적인 순서로 메모리에 연속 저장하는 방식의 순차 자료구조를 구현할 수 있다. 앞서 학습한 포인터는 이와 반대되는 연결 자료구조에서 쓰이며, 순차 자료구조와는 다른 양상을 띈다. 순차 자료구조는 메모레의 저장 시작 위치부터 빈 공간을 만들지 않은 채로 자료를 순서대로 연속해 저장한다. 논리적인 순서와 물리적 순서가 일치하는 것이다. 또한, 삽입이나 삭제를 하여도 빈자리는 생기지 않는다. 

 

 자료들 간에 순서를 갖는 리스트인 '선형 리스트'라는 개념은 순차 자료구조와 연결 자료구조 둘 다로 구현할 수 있는데, 순차 자료구조로는 이렇게 나타낼 수 있다. int arr[100]; 이 그 예이다. 다음으로, 삽입을 하는 방법은 이렇다. 먼저 삽입 로직을 짠 후 배열에서 어떤 방식으로 삽입할 것인지를 생각하여 코드를 구성한다. 가장 많이 쓰는 방법은 한 칸씩 뒤로 자리를 이동하는 것이다. 그 뒤에 밀려 준비된 빈 자리에 원소를 삽입한다. 이것이 하나의 알고리즘을 이룬다. 

 

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

void insert(int arr[], int *n, int index, int value) {
	/* 리스트 크기: n
	삽입할 위치: index
	삽입할 값: value */

	for (int i = *n - 1; i >= index; i--) {
		arr[i + 1] = arr[i];
	}

	arr[index] = value;
	(*n)++;
}

	int main() {
		int n, index, value;
		printf("리스트의 크기를 입력하시오.");
		scanf("%d", &n);
		int *arr = (int*)malloc(sizeof(int) * (n + 1));


		if (n > MAX_SIZE) {
			printf("최대 크기를 초과합니다.");
			return -1;
		}

		printf("%d개의 값을 입력하시오.");
		for (int i = 0; i < n; i++) {
			scanf("%d", &arr[i]);
		}

		printf("삽입할 위치를 입력하시오.");
		scanf("%d", &index);

		printf("삽입할 값을 입력하시오.");
		scanf("%d", &value);

		insert(arr, &n, index, value);

		printf("삽입 결과:");
		for (int i = 0; i < n; i++) {
			printf("%d ", arr[i]);
		}

		return 0;
	}

 

 처음 이 순차 선형 리스트에 어떻게 삽입할 수 있는지를 맞닥뜨렸을 땐 정말 머리가 아팠다. 그러나 한 번 이해하고 나면 생각보다 별 거 아니었다는 것을 깨달을 수 있다. 위 코드는 리스트의 중간에 삽입할 값인 value를 입력받고, 그 뒤의 자리한 원소들을 한 칸씩 미뤄 자리를 만들어주는 형태의 알고리즘을 구성한다. 삽입 로직의 구성은 이러하다.

 

 void insert(int arr[], int *n, int index, int value) {

    for (int i = *n - 1; i >= index; i--) {

        arr[i + 1] = arr[i];

    }

    arr[index] = value;

    (*n)++;

}

 

 맨 처음 insert 함수를 선언하여 삽입에 사용될 배열, 크기, 삽입 위치, 삽입 값을 지정한다. 이후 반복문을 통해 삽입될 위치부터 끝까지 있던 원소들을 한 칸씩 뒤로 이동시켜 빈 공간을 만든다. 이 반복이 끝나면, 새로 삽입할 값(value)을 지정한 위치(index)에 저장한다. 마지막으로 리스트의 크기를 하나 증가시켜 삽입된 데이터까지 포함되도록 관리한다. 이때 MAX_SIZE는 예외처리를 위한 것이다. 따라서 return -1;로 확실한 오류임을 나타낸다.

 

 반복문은 왜 저렇게 짜여졌는지 뜯어보자. 지정한 위치 이후의 데이터를 뒤로 이동시켜야 하는 것이기 때문에, *n - 1, 즉 마지막부터로 i를 초기화한다. 이때 그냥 n이라고 쓰지 않는 것은 n이 포인터 변수이므로 단순히 n으로 둔다면 주소값을 가리키는 꼴이 된다. 이것만 알면 뒤의 구성은 바로 이해가 된다. 리스트의 크기를 증가시킬 때 괄호로 감싸는 이유가 연산자 우선순위로 인한 것임만 기억해두자.

 

 삽입이 아닌 삭제의 경우 위의 삽입 로직을 삭제 로직으로 바꾸면 된다. 예시는 이렇다.

 

 void delete(int arr[], int *n, int index) {

    for (int i = index; i < *n - 1; i++) {
        arr[i + 1] = arr[i];
    }
    (*n)--;
}

 

 삽입문과 거의 비슷하지만, 반복문의 구성이 달라지고 배열의 크기를 늘렸던 삽입과는 달리 줄이는 것을 볼 수 있다. 삭제할 인덱스 번호부터 시작해서 이번엔 왼쪽으로 한 칸씩 원소들을 옮긴다. 이러한 배열의 삽입과 삭제는 자료구조의 기본이다. 

 

 또한, 행렬을 선형 리스트로 표현할 수 있는데, 선형대수학을 접한 사람이라면 이부분을 크게 무리없이 이해할 수 있을 것이라 추측한다. 물론 쉬운 개념은 아니라 생각한다. 2차원 논리 순서를 1차원 물리 순서로 변환할 때, 행 우선 순서 방법과 열 우선 순서 방법이 있다. 대부분의 경우 행 우선 순서 방법을 훨씬 더 자주 쓰게 된다. 왜냐하면, C언어나 파이썬같은 현대 프로그래밍 언어의 태반이 기본적으로 행 우선 방법을 사용하기 때문이다. 

 

 행 우선 순서 방법은 말 그대로 2차원 배열의 첫 번째 인덱스인 행 번호를 기준으로 변환한다. 이때 원소의 위치를 편리하게 계산하는 관계식이 있다. m x n 행렬인 2차원 배열 A[m][n]에서 시작주소가 a고 원소의 길이가 l일 때, i행 j열 원소, 즉 a[i][j]의 위치를 구힌다면 계산식은 이렇게 작성된다. a + ( i * n + j ) * l 우리는 이 계산식을 통하여 원소의 위치를 쉽게 구해낼 수 있다. 덧붙여 희소 행렬에 대한 2차원 배열 역시 표현할 수 있는데, 이는 세 가지의 순서로 이루어진다.

 

 먼저 희소 행렬에서 0이 아닌 원소를 추출하여 <행 번호, 열 번호, 원소의 값> 의 형태로 배열에 저장한다. 그 후, 추출한 순서쌍을 2차원 배열에 행으로 저장하며, 마지막으론 원래의 행렬에 대한 정보를 0번째 행에 저장하면 된다. 예시로 5행 6열의 희소행렬을 만들어보고 이를 2차원 배열로 표현해 보겠다.

0	0	0	9	0	0
0	0	0	0	0	0
4	0	0	0	0	2
0	0	5	0	0	0
0	7	0	0	8	0

 

 여기서 0이 아닌 원소를 구해 정리하면, (배열은 0부터 시작함을 잊지 말아야 한다.)

 

<0, 3, 9>

<2, 0, 4>

<2, 5, 2>

<3, 2, 5>

<4, 1, 7>

<4, 4, 8>

 

 로 정리된다. 이를 2차원 배열에 행으로 저장할 때 가장 맨 위엔 원래의 행렬에 대한 <전체 행의 개수, 전체 열의 개수, 0이 아닌 원소의 개수>를 꼭 붙여주어야만 한다. 따라서 최종 배열 표는 이러하다. 

 

5	6	6
0	3	9
2	0	4
2	5	2
3	2	5
4	1	7
4	4	8

 

 한 발짝 더 나아가 이를 전치로도 구할 수 있다! 희소행렬의 전치는 행과 열을 뒤바꾸는 것으로, 바꾼 행과 열을 따르는 배열을 재구성할 수 있다. 값은 그대로 두면 된다. 전치한 버전은 다음과 같다:

 

<3, 0, 9>

<0, 2, 4>

<5, 2, 2>

<2, 3, 5>

<1, 4, 7>

<4, 4, 8>

 

6	5	6
0	2	4
1	4	7
2	3	5
3	0	9
4	4	8
5	2	2