Chapter 03. 배열을 이용한 리스트의 구현

티스토리 뷰

공부 일지/자료구조 공부 일지

Chapter 03. 배열을 이용한 리스트의 구현

K◀EY 2021. 3. 8. 16:33

주의 사항!

이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
따라서 제가 이해하는 그대로의 내용이 포함됩니다.
따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

현재 배우는 리스트는 연결 리스트를 말합니다. 그렇다고 '리스트는 연결리스트다'라고 생각하면 곤란합니다.

리스트라는 자료구조는 구현 방법에 따라서 다음과 같이 크게 두 가지로 나뉩니다.

순차 리스트 : 배열을 기반으로 구현된 리스트
연결 리스트 : 메모리의 동적 할당을 기반으로 구현된 리스트

순차 리스트와 연결 리스트 두 개로 분류하였지만 이 둘의 추상 자료형(ADT)은 동일할 수 있습니다. 하지만 두 리스트의 분류는 리스트의 구현 방법의 차이에서 비롯된 것이기 때문에 이 둘의 추상 자료형이 동일하다고 해서 문제가 될 것은 없습니다. 물론 각각의 특성적 차이 때문에 추상 자료형에 차이를 두기도 합니다.

추상 자료형에 차이를 두기도 한다니? 추상 자료형이 동일할 수도 다를 수도 있다? 위 설명을 듣고 이렇게 생각했을지도 모릅니다. 각종 자료구조들의 추상 자료형은 표준이 아닙니다. 즉, 입맛에 따라서 얼마든지 추상 자료형을 수정하거나 확정하거나 할 수 있습니다. 다만, 그렇다고 해서 해당 자료구조의 기본 특성을 무시하는 형태로 추상 자료형이 정의되어서는 안 됩니다.

리스트의 추상 자료형 정의를 위해서 리스트 자료구조의 가장 기본 적이고도 중요한 특성을 소개하겠습니다.

리스트 자료구조는 데이터를 나란히 저장합니다.
그리고 중복된 데이터의 저장을 막지 않습니다.

자료구조 중에서는 중복된 데이터의 저장을 허용하지 않는 경우도 있습니다. 하지만 리스트는 이를 허용합니다. 즉, 리스트는 수학적으로 중복을 허락하지 않는 '집합'과 다릅니다. 그리고 이것이 리스트 추상 자료형을 정의하는 데 있어서 고려해야 할 유일한 요소입니다.

리스트의 추상 자료형을 정의해 보겠습니다. 그런데 아직은 직접 정의하지 말고 이 책의 저자가 우선 정의해 본 추상 자료형을 참고합니다.

void ListInit(List* plist)
//초기화할 리스트의 주소 값을 인자로 전달한다.
//리스트 생성 후 제일 먼저 호출되어야 하는 함수이다.

void LInsert(List* plist, LData data)
//리스트에 데이터를 저장한다. 매개변수 data에 전달됭 값을 저장한다.

int LFirst(List* plist, LData* pdata)
//첫 번째 데이터를 pdata가 가리키는 메모리에 저장한다.
//데이터의 참조를 위한 초기화가 진행된다.
//참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환

int LNext(List* plist, LData* pdata)
//참조된 데이터의 다음 데이터를 pdata가 가리키는 메모리에 저장한다.
//순차적인 참조를 위해서 반복 호출이 가능하다.
//참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야 한다.
//참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환

LData LRemove(List* plist)
//LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다.
//삭제된 데이터는 반환된다.
//마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다.

int LCount(List* plist)
//리스트에 저장되어 있는 데이터의 수를 반환한다.

지금 당장은 위 기능들이 어떻게 구현되고 동작할지 감이 오지 않을 것입니다. 우선 각 함수에는 리스트를 의미하는 L을 접두사로 하여 함수의 이름을 정의했습니다. 그리고 LData는 리스트에 저장할 데이터의 자료형에 제한을 두지 않기 위한 typedef 선언의 결과입니다. 이에 대해서는 잠시 후 헤더 파일에서 확인합니다.

리스트의 추상 자료형을 위와 같이 정의했으니 이를 바탕으로 main함수를 만들 차례입니다. 아래의 main 함수를 보면서 앞서 정의한 리스트 추상 자료형에서 소개하는 함수들의 기능을 완전히 이해하기 바랍니다.

//main.c 소스 파일로 저장
#include <stdio.h>
#include "ArrayList.h"

int main(void)
{
	//ArrayList의 생성 및 초기화
	List list;
	int data;
	ListInit(&list);

	//5개의 데이터 저장
	LInsert(&list, 11); LInsert(&list, 11);
	LInsert(&list, 22); LInsert(&list, 22);
	LInsert(&list, 33);

	//저장된 데이터의 전체 출력
	Printf("현재 데이터의 수 : %d\n", LCount(&list));

	if (LFirst(&list, &data))
	{
		printf("%d\n", data);
		while (LNext(&list, &data))
		{
			printf("%d\n", data);
		}
	}
	printf("\n\n");

	//숫자 22를 탐색하여 모두 삭제
	if (LFirst(&list, &data))
	{
		if (data == 22) LRemove(&list);

		while (LNext(&list, &data))
		{
			if (data == 22) LRemove(&list);
		}
	}
	
	//삭제 후 남은 데이터 전체 출력
	printf("현재 데이터의 수 : %d\n", LCount(&list));

	if (LFirst(&list, &data))
	{
		printf("%d ", data);
		while (LNext(&list, &data))
		{
			printf("%d ", data);
		}
	}
	printf("\n\n");

	return 0;
}

위 코드를 실행하기 위해서는 ArrayList.h 헤더 파일과 ArrayList.c 소스 파일이 필요합니다. 이들 파일은 잠시 후 만들게 됩니다. 우선은 위 코드에서 각각의 함수가 어떤 식으로 동작을 할지 추측해 봅니다.

제가 추측한 대로 설명해 보겠습니다. 우선, List구조체에는 저장하고 있는 데이터의 수를 나타내는 변수가 선언되어 있을 것 같습니다. 그리고 데이터를 배열의 형태로 저장할 수 있는 변수가 선언되어 있을 것 같습니다.

ListInit함수는 데이터를 어떠한 값으로 초기화 시키는 것 같습니다.

LInsert 함수는 데이터를 추가할 때 호출하는 함수입니다. list의 데이터 개수를 이용해서 다음 배열 요소에 값을 저장하거나, 동적 할당을 통해서 값을 저장하는 것으로 예상합니다.

LCount 함수는 저장된 데이터의 개수를 나타내는 변수값을 반환합니다.

LFirst함수는 저장된 데이터 배열에 접근합니다. 그런데 몇 번째 데이터에 접근할 것인지를 나타내는 변수가 LIst 구조체에 선언되어 있는 것으로 보입니다. 해당 변숫값을 가장 첫 번호로 초기화시키면서 해당 번호의 데이터를 data에 저장합니다.

LNext함수는 몇 번째 데이터에 접근할 것인지 나타내는 변수의 값을 1씩 증가시켜 가면서 해당 번호의 데이터값을 data에 저장하는 것으로 보입니다.

LRemove 함수는 LFirst 함수나 LNext함수와 마찬가지로 몇 번째 데이터에 접근할 것인지를 나타내는 변수를 이용해 해당 번호의 데이터를 지우는 역할을 합니다.

이제 리스트 자체의 구현을 해보겠습니다. 바로 앞서 보인 예에서 ArrayList.h 헤더 파일과 ArrayList.c 소스 파일을 만들어 봅니다. 리스트의 구현 방법인 크게 두 가지로 나뉜다고 앞서 말했습니다. 이번에는 배열을 이용해서 리스트를 구현해 봅니다. 먼저 스스로 시도해 보고 이후 예제를 확인하는 것을 권합니다.

다음의 코드는 제가 직접 구현한 코드입니다.

//ArrayList.h 헤더 파일로 저장
#ifndef ARRAYLIST_H
#define ARRAYLIST_H

#define TRUE 1
#define FALSE 0
#define MAX_LEN 100
#define LData int

typedef struct
{
	int count;
	int point;
	LData data[MAX_LEN];
}List;

void ListInit(List* plist);
void LInsert(List* plist, LData data);
int LFirst(List* plist, LData* pdata);
int LNext(List* plist, LData* pdata);
LData LRemove(List* plist);
int LCount(List* plist);

#endif

//ArrayList.c 소스 파일로 저장
#include "ArrayList.h"

void ListInit(List* plist)
{
	plist->count = 0;
	plist->point = 0;
}
void LInsert(List* plist, LData data)
{
	plist->data[plist->count++] = data;
}
int LFirst(List* plist, LData* pdata)
{
	plist->point = 0;
	if (plist->count == 0) return FALSE;

	*pdata = plist->data[plist->point];

	return TRUE;
}
int LNext(List* plist, LData* pdata)
{
	if (plist->point + 1 >= plist->count) return FALSE;

	plist->point++;
	*pdata = plist->data[plist->point];
	return TRUE;
}
LData LRemove(List* plist)
{
	LData data = plist->data[plist->point];
	plist->count--;
	
	int i;
	for (i = plist->point; i < plist->count; i++)
	{
		plist->data[i] = plist->data[i + 1];
	}
	plist->point--;
	return data;
}
int LCount(List* plist)
{
	return plist->count;
}

//main.c 소스 파일로 저장
#include <stdio.h>
#include "ArrayList.h"

int main(void)
{
	//ArrayList의 생성 및 초기화
	List list;
	int data;
	ListInit(&list);

	//5개의 데이터 저장
	LInsert(&list, 11); LInsert(&list, 11);
	LInsert(&list, 22); LInsert(&list, 22);
	LInsert(&list, 33);

	//저장된 데이터의 전체 출력
	printf("현재 데이터의 수 : %d\n", LCount(&list));

	if (LFirst(&list, &data))
	{
		printf("%d ", data);
		while (LNext(&list, &data))
		{
			printf("%d ", data);
		}
	}
	printf("\n\n");

	//숫자 22를 탐색하여 모두 삭제
	if (LFirst(&list, &data))
	{
		if (data == 22) LRemove(&list);

		while (LNext(&list, &data))
		{
			if (data == 22)
			{
				LRemove(&list);
			}
		}
	}
	
	//삭제 후 남은 데이터 전체 출력
	printf("현재 데이터의 수 : %d\n", LCount(&list));

	if (LFirst(&list, &data))
	{
		printf("%d ", data);
		while (LNext(&list, &data))
		{
			printf("%d ", data);
		}
	}
	printf("\n\n");

	return 0;
}

/*
실행결과

현재 데이터의 수 : 5
11 11 22 22 33

현재 데이터의 수 : 3
11 11 33

*/

이후 책에서 구현한 예제와 비교해서 다른 점이 있다면 소개하려 했으나 책에서 구현한 예제와 다르지 않아 이는 생략하겠습니다.

앞에서는 설명의 편의를 위해서 리스트에 단순히 정수를 저장했습니다. 그런데 실제로는 구조체 변수를 비롯해서 각종 데이터들이 저장됩니다. 따라서 방금 정의한 리스트에 '구조체 변수의 주소 값'을 저장해 보고자 합니다. 이를 위해서 다음의 구조체를 정의하였습니다.

typedef struct
{
	int xpos;
	int ypos;
}Point;

그리고 위의 구조체와 관련 있는 다음 함수들도 함께 정의하고자 합니다.

void SetPointPos(Point* ppos, int xpos, int ypos);    //값을 저장
void ShowPointPos(Point* ppos);                       //정보 출력
int PointComp(Point* pos1, Point* pos2);              //비교!

PointComp 함수는 두 구조체 변수에 저장된 값을 비교하여 그 결과를 반환합니다. 반환하는 값은 다음과 같이 정의하기로 합니다.

두 Point 변수의 멤버 xpos만 같으면 1 반환
두 Point 변수의 멤버 ypos만 같으면 2 반환
두 Point 변수의 멤버가 모두 같으면 0 반환
두 Point 변수의 멤버가 모두 다르면 -1 반환

이렇게 해서 구조체 Point와 이에 관련된 함수들의 선언 및 정의를 다음 두 헤더파일과 소스파일에 나누어 담았습니다.

//Point.h 헤더 파일로 저장
#ifndef POINT_H
#define POINT_H

typedef struct
{
	int xpos;
	int ypos;
} Point;

void SetPointPos(Point* ppos, int xpos, int ypos);
void ShowPointPos(Point* ppos);
int PointComp(Point* pos1, Point* pos2);

#endif

//Point.c 소스 파일로 저장
#include "Point.h"

void SetPointPos(Point* ppos, int xpos, int ypos)
{
	ppos->xpos = xpos;
	ppos->ypos = ypos;
}
void ShowPointPos(Point* ppos)
{
	printf("[%d, %d]\n", ppos->xpos, ppos->ypos);
}
int PointComp(Point* pos1, Point* pos2)
{
	if (pos1->xpos == pos2->xpos)
	{
		if (pos1->ypos == pos2->ypos) return 0;
		else return 1;
	}
	else
	{
		if (pos1->ypos == pos2->ypos) return 2;
		else return -1;
	}
}

이제 이를 바탕으로 앞서 작성했던 코드를 수정해 봅니다. 정수 데이터가 아닌 Point 구조체 변수의 주소 값을 저장할 수 있어야 합니다. 이를 위해서 수정해야 할 파일은 ArrayList.h 헤더 파일 하나밖에 없습니다.

해당 파일 내에서도 다음의 코드를

#define LData int

다음과 같이 고치기만 하면 끝입니다.

#define LData Point*

물론 Point를 자료형으로 사용하기 위해 Point.h 헤더 파일을 인클루드 해주어야 합니다.

main.c파일은 Point 구조체 변수를 다루는 것에 맞게 다음과 같이 새로 제시합니다.

//main.c 소스 파일로 저장
#include <stdio.h>
#include <stdlib.h>
#include "ArrayList.h"

int main(void)
{
	List list;
	Point compPos = {2, 0};
	Point* ppos;
	ListInit(&list);

	//4개의 데이터 저장
	ppos = (Point*)malloc(sizeof(Point));
	SetPointPos(ppos, 2, 1);
	LInsert(&list, ppos);

	ppos = (Point*)malloc(sizeof(Point));
	SetPointPos(ppos, 2, 2);
	LInsert(&list, ppos);

	ppos = (Point*)malloc(sizeof(Point));
	SetPointPos(ppos, 3, 1);
	LInsert(&list, ppos);

	ppos = (Point*)malloc(sizeof(Point));
	SetPointPos(ppos, 3, 2);
	LInsert(&list, ppos);

	//저장된 데이터의 전체 출력
	printf("현재 데이터의 수 : %d\n", LCount(&list));

	if (LFirst(&list, &ppos))
	{
		ShowPointPos(ppos);
		while (LNext(&list, &ppos))
		{
			ShowPointPos(ppos);
		}
	}
	printf("\n\n");

	//xpos가 2인 모든 데이터 삭제
	if (LFirst(&list, &ppos))
	{
		if (PointComp(ppos, &compPos) == 1)
		{
			ppos = LRemove(&list);
			free(ppos);
		}

		while (LNext(&list, &ppos))
		{
			if (PointComp(ppos, &compPos) == 1)
			{
				ppos = LRemove(&list);
				free(ppos);
			}
		}
	}
	
	//삭제 후 남은 데이터 전체 출력
	printf("현재 데이터의 수 : %d\n", LCount(&list));

	if (LFirst(&list, &ppos))
	{
		ShowPointPos(ppos);
		while (LNext(&list, &ppos))
		{
			ShowPointPos(ppos);
		}
	}
	printf("\n\n");

	return 0;
}

/*
실행결과

현재 데이터의 수 : 4
[2, 1]
[2, 2]
[3, 1]
[3, 2]


현재 데이터의 수 : 2
[3, 1]
[3, 2]

*/

위 코드에서 LRemove 함수가 삭제할 값을 반환하도록 한 이유을 알 수 있습니다. 동적 할당한 메모리 공간을 반드시 직접 회수해야 합니다. 그래서 구조체 변수의 주소 값을 삭제할 때 이 값을 반환하여 동적 할당한 메모리 공간의 회수에 쓰일 수 있도록 했습니다.

위 main.c 파일의 코드를 보면서 구조체 변수의 주소를 리스트 자료구조에 저장하는 일이 어떻게 구현되는지, 어떻게 해서 int형 변수를 저장하던 코드를 별 수정없이도 Point 구조체 변수를 저장할 수 있게 할 수 있었는지 생각해보길 권합니다.

저작자표시

'공부 일지 > 자료구조 공부 일지' 카테고리의 다른 글

Chapter 04. 연결 리스트의 개념적인 이해 (0)	2021.03.08
Chapter 03. 리스트의 활용 연습문제 1 (0)	2021.03.08
Chapter 03. 추상 자료형 : Abstract Data Type (0)	2021.03.08
Chapter 02. 하노이 타워 : The Tower of Hanoi (0)	2021.03.08
Chapter 02. 재귀의 활용 (0)	2021.03.07

공지사항

최근에 올라온 글

최근에 달린 댓글

Total

Today

Yesterday

링크

TAG more

« 2024/12 »
일	월	화	수	목	금	토
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

글 보관함

황민혁 트러블슈팅 모음집

티스토리 뷰

Chapter 03. 배열을 이용한 리스트의 구현

'공부 일지 > 자료구조 공부 일지' 카테고리의 다른 글

티스토리툴바