컴퓨터공학에서의 추상 자료형(Abstract Data Type)
추상자료형, ADT라고 불리는 이것은 컴퓨터 공학에서 흔히 등장하는 용어이다.
등장하는 영역에 따라서 의미상 약간 차이가 있는 것 처럼 느껴질 수 도 있지만, 실제 의미에서 조금 확장된 개념으로도 사용되기도 한다. 하지만 실제로 차이를 보이는 것은 아니고, 이해가 완전히 되지 않아서 그렇게 느낄 뿐이다.
자료구조에서의 추상 자료형
구체적인 기능의 완성 과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것
typedef struct _wallet
{
int coin100Num; //100원짜리 동전수
int bill5000Num; //5000원 짜리 지폐의 수
}Wallet;
이렇게 C언어를 기반으로 구조체를 정의 했다면
구조체를 기반으로 지갑을 의미하는 Wallet이라는 자료형을 정의했다 라고 말할 수 있다.
C언어 에서 제공하는 연산이 아닌 Wallet을 기반으로 제공할 수 있는 기능관련 연산에 대해 말해모녀
돈을 꺼내는 연산 int TakeOutMoney(Wallet * pw, int coinNum, int billNum)
돈을 넣는 연산 void PutMoney(Wallet * pw, int coinNum, int billNum);
이렇 듯 C언어에서는 구조체에서 필요로 하는 연산을 함수를 이용해 정의한다. 그리고 위의 두 연산이 Wallet과 관련이 있는 연산의 전부라고 하면, 이 둘이 더해져서 Wallet에 대한 자료형의 정의는 완성이 된다.
결론은 '자료형'의 정의에 '기능' 혹은 '연산'과 관련된 내용을 명시할 수 있는 것이다. 따라서 추상 자료형이라 하여 그것에 기능 혹은 연산과 관련된 내용을 명시할 수 없다는 생각은 버려야 된다.
구조체 Wallet의 추상 자료형 정의
Wallet의 추상자료형을 정의해보자.
구조체 Wallet도 자료구조의 일종이다.
구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지 나열한 것을 가리켜 '추상 자료형' 또는 ADT라 한다.
이문장을 다시 읽고 정리해보면
Wallet의 ADT
int TakeOutMoney(Wallet *pw, int coinNum, int billNum)
-첫 번째 인자로 전달된 주소의 지갑에서 돈을 꺼낸다.
-두 번째 인자로 꺼낼 동전의수, 세 번째 인자로 꺼낼 지폐의 수를 전달한다.
-꺼내고자 하는 돈의 총액이 반환된다, 그리고 그 만큼 돈은 차감된다.
void PutMoney(Wallet *pw, int coinNum, int billNum)
-첫 번째 인자로 전달된 주소의 지갑에 돈을 넣는다.
-두 번째 인자로 넣을 동전의 수, 세번째 인자로 넣을 지폐의 수를 전달한다.
-넣을 만큼 동전과 지폐의 수가 증가한다.
명시해야할 정보인 '기능'을 충분히 묘사하면된다.
우리는 C언어의 파일 입출력을 공부할 때 FILE 구조체의 내부를 궁금해 하지 않는다. FILE 구조체의 내부를 몰라도 파일과 관련된 모든 연산을 처리할 수 있기 때문이다. 그러므로 FILE 구조체의 내부를 궁금증은 불필요하다.
다음엔 리스트 자료구조를 만들 건데 순서를 말하면.
1. 리스트 자료구조의 ADT를 정의한다.
2. ADT를 근거로 리스트 자료구조를 활용하는 main함수를 정의한다.
3. ADT를 근거로 리스트를 구현한다.
리스트에는 크게 2가지의 종류가 있다.
순차 리스트 : 배열을 기반으로 하는 리스트
연결 리스트 : 메모리의 동적 할당을 기반으로 구현된 리스트
이는 리스트의 구현방법의 차이에서 비롯된 것이기 때문에 이 둘이 ADT가 동일하다고 해서 문제될건 없다. 하지만 각각의 특성적 차이 때문에 ADT에 차이를 두기도 한다.
ADT는 정의하는 사람에 따라서 , 필요에 따라서 차이가 난다. 물론 필요로 의해 확장도 가능하다 .그렇다고 해서 해당 자료구조의 기본특성을 무시하는 형태로 ADT가 정의되는 것은 아니다.
"리스트 자료구조는 데이터를 나란히 저장한다, 그리고 중복된 데이터의 저장을 막지 않는다"
자료구조 중에서 중복된 데이터의 저장을 허용하지 않는 경우도 있다.하지만 리스트는 허용한다. 리스트는 수학적으로 중복을 허용하지 않는 '집합'과 다르다. 이것이 리스트 ADT를 정의 하는데 있어서 고려해야 할 유일한 요소이다.
리스트 ADT
나란히 저장된다는 특성을 기반으로 제공해야 할 기능들을 정의해야 한다.
리스트 자료구조의 ADT
void ListInit(List * plist);
-초기화할리스트의 주소값을 인자로 전달한다.
-리스트 생성 후 제일 먼저 호출되어야 하는 함수이다.
void LInsert(List *plist, LData data);
-리스트에 데이터를 저장한다. 매개변수 data에 전달된 값을 저장한다.
int LFirst(List *plist, LData *pdata);
-첫 번째 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장된다.
-순차적인 참조를 위해서 반복 호출이 가능하다.
-참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야 한다.
-참조 성공시 TRUE(1), 실패 시 FALSE(0)반환
LData LRemove(List *plist);
-LFirst 또는 LNext함수의 마지막 반환데이터를 삭제한다.
-삭제된 데이터는 반환된다.
-마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다.
int LCount(List *plist);
-리스트에 저장되어 있는 데이터의 수를 반환한다.
LData는 리스트에 저장할 데이터의 자료형에 제한을 두지 않기 위한 typedef 선언의 결과이다.
사실 위의 정보만 가지고 리스트의 활용방법을 정확하기 이해하기는 힘들다. 이를 위해서는 헤더파일과 위의 함수들을 호출하는 main함수를 보아야 한다. 그러나 위의 정보만 가지고도 리스트 자료구조가 제공하는 기능을 어느 정도 예측 할수 있어야 한다.
리스트의 ADT를 정의하였으니 , 이를 기반으로 main함수를 만들어야 한다.
//ListMain.c
#include <stdio.h>
#include "ArrayList.h"
int main()
{
//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
위의 실행결과를 직접 확인하기 위해서는 다음 세 개의 파일을 하나의 프로젝트에 담아서 컴파일을 해야 한다.
ArrayList.h 리스트 자료구조의 헤더파일
ArrayLisy.c 리스트 자료구조의 소스파일
ListMain.c 리스트 관련 main함수가 담긴 소스파일
이 예제는 아래에 있다.
//ArrayList.h
#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__
#define TRUE 1
#define FALSE 0
/*** ArrayList의 정의 ****/
#define LIST_LEN 100
typedef int LData;
typedef struct __ArrayList
{
LData arr[LIST_LEN];
int numOfData;
int curPosition;
} ArrayList;
/*** ArrayList와 관련된 연산들 ****/
typedef ArrayList 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 <stdio.h>
#include "ArrayList.h"
void ListInit(List* plist)
{
(plist->numOfData) = 0;
(plist->curPosition) = -1;
}
void LInsert(List* plist, LData data)
{
if (plist->numOfData > LIST_LEN)
{
puts("저장이 불가능합니다.");
return;
}
plist->arr[plist->numOfData] = data;
(plist->numOfData)++;
}
int LFirst(List* plist, LData* pdata)
{
if (plist->numOfData == 0)
return FALSE;
(plist->curPosition) = 0;
*pdata = plist->arr[0];
return TRUE;
}
int LNext(List* plist, LData* pdata)
{
if (plist->curPosition >= (plist->numOfData) - 1)
return FALSE;
(plist->curPosition)++;
*pdata = plist->arr[plist->curPosition];
return TRUE;
}
LData LRemove(List* plist)
{
int rpos = plist->curPosition;
int num = plist->numOfData;
int i;
LData rdata = plist->arr[rpos];
for (i = rpos; i < num - 1; i++)
plist->arr[i] = plist->arr[i + 1];
(plist->numOfData)--;
(plist->curPosition)--;
return rdata;
}
int LCount(List* plist)
{
return plist->numOfData;
}
우선 위의 main함수에서 제일 먼저 등장하는 리스트의 생성 및 초기화 관련 문장을 보자.
int main()
{
List list; //리스트의 생성
...
ListInit(&list); //리스트의 초기화
}
위에를 보면 List를 기반으로 변수 list를 선언하고 있는데, 앞으로 이것을 리스트라 칭한다. 그리고 모든 자료구조는 내부적으로 다양한 정보를 담게된다. 그저 데이터만 담는게 아니라 그 데이터를 효율적으로 저장 및 참조하기 위한 정보들도 담기기 마련이다. 따라서 이와 관련된 변수들의 초기화가 진행되어야 하며 이를 담당하는 함수가 ListInit이다.
이어서 데이터의 저장방법을 살펴보자.
int main()
{
LInsert(&list, 11); LInsert(&list, 11); //리스트에 11을 각각 1회씩 저장
LInsert(&list, 22); LInsert(&list, 22); //리스트에 22를 각각 1회씩 저장
LInsert(&list, 33); //리스트에 33을 저장
...
}
LInsert함수를 호출하면 리스트의 주소 값을 첫 번째 인자로, 그리고 리스트에 담을 데이터를 두번째 인자로 전달하고 있다. 만약에 &연산자를 이용해서 list의 주소값을 전달하는 이유를 이해하지 못한다면 포인터와 함수의 관계를 복습해야한다.
이번에는 '데이터의 참조방식'을 살펴보겠다 . 참고로 본래 데이터의 저장보다 참조가 더 복잡하다. 아래의 코드에서는 저장된 순서대로 데이트를 참조하여 출력을 진행하되, 마지막 데이터 까지 참조하여 출력을 진행하고 있다.
int main()
{
if(LFirst(&list, &data)) //첫 번째 데이터를 변수 data에 저장
{
printf("%d ", data);
while(LNext(&list, &data)) //두 번째 이후의 데이터를 변수 data에 저장
printf("%d ", data);
}
...
}
앞서 리스트 ADT에서는 다음과 같이 언급하였다.
"순서대로 참조하려면 먼저 LFirst를 호출해서 첫 번째 데이터를 얻고, 그리고 두 번째 이후의 데이터는 LNext를 호출해서 얻으면 된다. 그리고 LFirst함수와 LNext함수는 더 이상 참조할 데이터가 없으면 FALSE를 반환한다."
LNext함수의 호출을 통해서 다음번 데이터를 얻는다는 사실은 어렵지 않게 이해할 수 있다. 그런데 굳이 LFirst함수의 호출을 요구하는 이유는 무엇일까? LFirst함수를 호출하도록 ADT를 디자인한 이유는 무엇일까?
이에 대한 해답은 "LNext함수를 호출할 때마다 다음에 저장된 데이터를 얻을 수 있다"라는 사실에서 찾을 수 있다.
이것이 가능한 이유는 리스트 내에서 '데이터의 참조위치'를 기록하기 때문이다. 따라서 처음 부터 참조를 새롭게 시작하기 위해서는 바로 이정보를 초기화 해야한다. 그리고 이를 목적으로 LFirst함수의 호출을 요구하는 것이다 .때문에 리스트에 저장된 모든 데이터를 참조하려면 함수의 호출순서를 다음과 같이 구성해야 한다.
LFirst->LNext->LNext->LNext->LNext->LNext->LNext->...
이제 마지막으로 삭제 관련 코드를 설명한다. 이는 바로 위에서 설명한 탐색관련 코드와 관련이 깊다.
삭제를 위해서는 탐색이 선행되어야 하기 때문이다.
int main()
{
if(LFirst(&list, &data))
{
if(data==22)
LRemove(&list); //위의 LFirst 함수를 통해 참조한 데이터 삭제
while(LNext(&list, &data))
{
if(data==22)
LRemove(&list); //위의 LNext함수를 통해 참조한 데이터 삭제
}
}
...
}
위의 코드에서는 리스트에 저장된 숫자 22를 찾아서 모두 삭제하고 있다.
LRemove함수가 호출되는 시점을 보면
함수 LFirst가 호출된 이후
함수 LNext가 호출된 이후
즉 LRemove 함수가 호출되면, 바로 직전에 LFirst 또는 LNext함수의 호출을 통해서 참조된 데이터가 삭제된다.
배열 기반의 리스트 구현 1 : 헤더파일 정의
앞서 보인 main함수에 리스트의 구현과 관련된 어떠한 코드도 등장하지 않았다.
말 그대로 우리는 리스트 자료구조를 그냥 가져다 썻다! 그리고 이는 우리가 리스트의 ADT를 나름 잘 저으이 했다는 뜻도 된다. 이렇듯 어떠한 자료구조이건 간에 '자료구조의 구현'과 '구현된 자료구조의 활용'을 완전히 구분되도록 ADT를 정의해야 함을 기억해야 한다.
이제 리스트를 구현해보겠다.
리스트의 구현방법은 크게 두가지로 나뉘는데, 먼저 그 중하나인 배열을 이용하는 방법을 보인다.
그리고 첫번째 순서로 배열 기반의 리스트 구현을 위해 정의된 헤더파일을 소개한다.
//ArrayList.h
#ifndef __ARRAY_LIST_H__ //중복선언을 방지한다. // #pragma once 선언으로 대신 가능(VS++)
#define __ARRAY_LIST_H__
#define TRUE 1 //'참'을 표현하기 위한 매크로 정의
#define FALSE 0 //'거짓'을 표현하기 위한 매크로 정의
#define LIST_LEN 100
typedef int LData; //LData에 대한 typedef 선언
typedef sturct __ArrayList //배열 기반 리시트를 정의한 구조체
{
LData arr[LIST_LEN]; //리스트의 저장소인 배열
int numofData; //저장된 데이터의 수
int curPosition; //데이터의 참조위치를 기록(인덱스 값)
}ArrayList;
typedef ArrayList 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에는 데이터의 저장 공간이 배열로 선언되었고, 저장된 데이터의 수를 기록하기 위한 멤버도 존재한다. 그리고 참조의 위치를 기록하기 위한 , 다시 말해서 LFirst와 LNext, 그리고 LRemove 함수를 위한 멤버도 존재한다. 그리고 리스트에 다양한 종류의 데이터를 저장할 수 있게 하기 위한 typedef 선언도 다음과 같이 존재한다.
typedef int LData; //리스트에 int형 데이터의 저장을 위한 선언
리스트의 구현을 완료한 다음에, 위의 typedef선언을 변경하여 구조체 정보를 저장하는 리스트도, 구조체 변수의 주소값을 저장하는 리스트도 생성할 것이다.
typedef ArrayList List; //List는 배열 기반 리스트이다
이렇듯 ArrayList에 List라는 이름을 별도로 부여한 것이 당장에는 큰 의미가 없어 보인다. 하지만 ArrayList라는 이름에도 typedef선언을 해 놓으면, 다음과 같이 List에 다른 이름을 부여하는 것만으로도 사용하는 리스트의 종류를 바꿀수 있다.
typedef LinkedList List; //List는 연결 리스트 기반이다.
그래서 앞서 보인 main함수에서 ArrayList가 아닌 List라는 이름을 이용하여 예제를 작성한 것이다. 때문에 mainㅎ마수를 변경하지 않고도 main함수 내에서 사용하는 리스트를 다른 것으로 대체할 수 있다.
배열 기반의 리스트 구현 2 : 삽입과 조회
이제 남은 것은 위의 헤더파일에 선언된 함수들을 정의하는 것이다.
void ListInit(List *plist); //초기화
void LInsert(List * plist, LData data); //데이터 저장
먼저 초기화를 담당하는 ListInit 부터 채워보자. 이를 채우기 위해서는 앞서 정의한 구조체 ArrayList를 보면서 초기화할 대상이 무엇인지 파악해야 한다.
void ListInit(List *plist)
{
(plist->numOfData) = 0; //리스트에 저장된 데이터의 수는 0
(plist->curPosition) = -1; //현재 아무 위치도 가리키지 않음
ArrayList의 멤버 curPosition에는 배열의 인덱스 값이 저장된다. 그리고 이 변수에 저장된 값을 통해서 LFirst함수와 LNext함수가 참조해야 할 배열의 위치를 알게 할 수 있다. 그래서 curPosition은 0이 아닌 -1로 초기화 한것 이며, 여기에는 아직 데이터의 참조가 진행되지 않았다는 의미가 담겨있다.
void LInsert(List *plist, LData data)
{
if(plist -> numOfData >=LIST_LEN) //더 이상 저장할 공간이 없다면
{
puts("저장이 불가능합니다.");
return;
}
plist->arr[plist->numOfData] = data; //데이터 저장
(plist->numOfData)++; //저장된 데이터의 수 증가
}
이 함수는 단순하다. 우선 데이터의 수가 배열의 길이를 초과했는지 검사하고 초과하지 않았다면 일반적인 데이터의 저장과정을 진행한다. 물론 저장할 때에는 배열의 앞 부분부터 채워나간다.
int LFirst(List * plist, LData *pdata); //첫 번째 조회
int LNext(List *plist, LData * pdata); //두 번째 이후의 조회
int LFirst(List * plist, LData *pdata); //첫 번째 조회
{
if(plist->numOfData==0) //저장된 데이터가 하나도 없다면
return FALSE;
(plist->curPosition) = 0; //참조 위치 초기화, 첫번째 데이터의 참조를 의미
*pdata = plist->arr[0]; //pdata가 가리키는 공간에 데이터를 저장
return TRUE;
}
int LNext(List *plist, LData * pdata); //두 번째 이후의 조회
{
if(plist->curPosition >= (plist ->numOfData)-1) //더이상 참조할 데이터가 없다면
return FALSE;
(plist ->curPosition)++;
*pdata = plist->arr[plist->curPosition];
return TRUE;
}
위 함수의 실질적인 차이점은 다음 한 문장에 있다.
LFirst 함수의 중간에 삽입된 문장 (plist->curPosition) =0;
LNext 함수의 중간에 삽입된 문장 (plist->curPosition)++;
이렇듯 LFirst함수는 curPosition에 저장된 값을 0으로 재 설정 함으로써 데이터의 참조가 앞에서부터 다시 진행되도록 하는 역할을 한다. 반면 LNext함수는 이 값을 증가시켜서 순서대로 데이터를 참조할 수 있도록 한다. 그래서 이 두함수 모두 필요하다.
배열 기반의 리스트 구현 3. 삭제
LData LRemove(List *plist); //최근 조회가 이뤄진 데이터를 삭제한다.
이 함수의 정의를 위해서, 이 함수가 호출된 사례를 다시 보면
if(LFirst(&list, &data))
{
if(data ==22)
LRemove(&list); //앞서 LFirst 함수가 참조한 데이터 삭제!
while(LNext(&list, &data))
{
if(data ==22)
LRemove(&list); //앞서 LNext함수가 참조한 데이터 삭제!
}
}
이렇듯 LFirst 함수나 LNext 함수의 호출을 통해서 바로 직전에 참조가 이뤄진 데이터를 삭제하는 것이 LRemove함수이니 다음과 같은 형태로 삭제가 진행되어야 한다.
LRemove 함수가 호출되면 리스트의 멤버 curPosition을 확인해서, 조회가 이뤄진 데이터의 위치를 확인한 다음 그 데이터를 삭제한다.
이에 한가지 더해서 다음 사실을 기억하고 이를 반영해야 한다.
"앞에서부터 데이터를 채우는 것이 원칙이니 중간에 데이터가 삭제되면 ,뒤에 저장된 데이터들을 한칸씩 앞으로 이동시켜서 그 빈 공간을 채워야 한다"
위에서 언급한 두 가지 특성을 반영한 LRemove함수를 소개한다. 주목해서 볼것은 삭제할 때 데이터의 위치를 참조하는 방식과 삭제를 위한 데이터의 이동과정이다.
LData LRemove(List *plist)
{
int rpos = plist->curPosition; //삭제할 데이터의 인덱스 값 참조
int num = plist->numOfData;
int i;
LData rdata = plist ->arr[rpos]; //삭제할 데이터를 임시로 저장
//삭제를 위한 데이터의 이동을 진행하는 반복문
for(i=rpos; i<num-1; i++)
plist->arr[i] = plist ->arr[i+1];
(plist->numOfData)--; //데이터의 수 감소
(plist->curPosition)--; //참조위치를 하나 되돌린다.
return rdata; //삭제된 데이터의 반환
}
위의 함수에서 다음 문장이 삽입된 이유를 확인해야한다.
(plist->curPosition)--; //참조위치를 하나 앞으로 (배열 기준 왼쪽으로)옮긴다.
이렇듯 리스트의 참조 위치를 옮기는 이유는 curPosition은 최근에 참조가 이뤄진 데이터의 인덱스 정보를 담고 있어야 한다. 그런데 삭제로 인해 비는 공간을 메우려 데이터를 한 칸씩 앞으로 이동시키면 , 다음 그림에서 보이듯이 curPosition은 아직 참조가 이뤄지지않은 , 뒤에서 한 칸앞으로 이동한 데이터를 가리키게된다.
이후에 LNext함수가 호출되면 ,참조가 이뤄지지 않은 데이터를 참조할 수 있게된다.
'휴지통 > 자료구조-C' 카테고리의 다른 글
연결리스트2 (0) | 2021.02.13 |
---|---|
링크드리스트1 (0) | 2021.02.12 |
배열 기반의 리스트(List)2 (0) | 2021.02.09 |
재귀 함수 (0) | 2021.02.05 |
자료구조와 알고리즘 이해 (0) | 2021.02.03 |