03-1. 추상 자료형: Abstract Data Type
추상 자료형(Abstract Data Type)
추상 자료형은 간단히 ADT라고도 한다.
객체지향 언어(C++이나, JAVA, Python 등)에서 공부하면 더 깊이 이해할 수 있기 때문에 여기서는 자료구조의 관점에서 ADT를 배워볼 것이다.
추상 자료형(ADT)이란 구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지 나열하는 것을 말한다.
예를 들어 아래와 같이 Wallet이라는 구조체를 기반으로 하는 자료형을 정의했다고 하자.
typedef struct _wallet
{
int coin100Num; // 100원짜리 동전의 수
int bill500Num; // 5000원짜리 지폐의 수
} Wallet;단순히 구조체 정의만으로 Wallet이라는 자료형의 정의가 완성되는 것이 아니라 Wallet을 기반으로 하는 연산의 종류를 결정하는 것도 자료형 정의의 일부로 봐야하고, 연산의 종류가 결정되었을 때 자료형의 정의는 완성된다.
예를 들면 돈을 꺼내는 연산과 돈을 넣는 연산에 대한 것을 아래와 같이 정의하면 Wallet에 대한 자료형의 정의는 완성된다. (연산이 이 두개가 다라면)
int TakeOutMoney(Wallet * pw, int coinNum, int billNum); // 돈을 꺼내는 연산
void PutMoney(Wallet * pw, int coinNum, int bilNum); // 돈을 넣는 연산추상 자료형 정의
정의한 자료형 Wallet에 대한 추상 자료형을 정의해보자.
위에서 언급한 연산 2가지에 대해서 명시해야 할 정보인 기능을 묘사하면 된다.
✅Operations:
- int TakeOutMoney(Wallet * pw, int coinNum, int billNum)
- 첫 번째 인자로 전달된 주소의 지갑에서 돈을 꺼낸다.
- 두 번째 인자로 꺼낼 동전의 수, 세 번째 인자로 꺼낼 지폐의 수를 전달한다.
- 꺼내고자 하는 돈의 총액이 반환된다. 그리고 그만큼 돈은 차감된다.
- void PutMoney(Wallet * pw, int coinNum, int billNum)
- 첫 번째 인자로 전달된 주소의 지갑에 돈을 넣는다.
- 두 번째 인자로 넣을 동전의 수, 세 번째 인자로 넣을 지폐의 수를 전달한다.
- 넣은 만큼 동전과 지폐의 수가 증가한다.
구조체 Wallet의 정의는 ADT에 포함되어야 하는 것일까?
main 함수를 통해 필요한지 알아보자.
int main(void)
{
Wallet myWallet;
....
PutMoney(&myWallet, 5, 10);
....
ret = TakeOutMoney(&myWallet, 2, 5);
}보다시피 Wallet의 정의는 돈을 넣고 꺼내는데 필요한 정보가 아니다.
따라서 Wallte의 정의를 ADT에 넣는 것은 바람직하지 못하다.
생각해보면 우리는 FILE 구조체의 내부를 잘 몰라도 잘 사용해왔다. 따라서 필요한 구조체를 우리가 만들었다고 해서 그 내부 멤버들까지 추상 자료형에 추가해 알 필요는 없는 것이다.
리스트 자료구조 ADT
이제 리스트 자료구조라는 것을 배울 것인데 학습 순서는 다음과 같다.
- 리스트 자료구조의 ADT를 정의.
- ADT를 근거로 리스트 자료구조를 활용하는 main 함수를 정의.
- ADT를 근거로 리스트 구현.
2, 3번의 순서가 저렇게 된 것은 리스트 사용자에게 사용방법 이외 불필요한 부분까지 알려주지 않아도 되기 때문이다.
따라서 앞으로 구현할 자료구조는 그 내부 구현을 알지 못해도 활용할 수 있도록 ADT를 정의하여 구현할 것이다.
03-2. 배열을 이용한 리스트의 구현
리스트의 이해
리스트는 구현 방법에 따라 크게 두 가지로 나뉜다.
(리스트 = 연결 리스트란 오해에서 벗어나보자.)
- 순차 리스트: 배열을 기반으로 구현된 리스트
- 연결 리스트: 메모리의 동적 할당을 기반으로 구현된 리스트
그렇 순차 리스트와 연결 리스트 ADT는 무조건 다른가? 아니다. 구현방법의 차이에서 비롯된 것이기 때문에 이 둘의 ADT가 동일할 수도 있다.
리스트의 기본 특성을 가진 ADT는 표준을 가지고 있다. 리스트의 ADT 정의를 위해서 리스트 자료구조의 가장 기본적이고도 중요한 특성은 다음과 같다.
"리스트 자료구조는 데이터를 나란히 저장한다. 그리고 중복된 데이터의 저장을 허락한다."
자료구조 중에서 중복된 데이터의 저장을 허용하지 않는 경우도 있다. 하지만 리스트는 이를 허용한다. (집합은 중복을 허락하지 않는다.)
리스트의 ADT
리스트의 특성에 대해 알았으니 리스트의 특성을 기반으로 제공해야 할 기능들을 정의해보자.
✅리스트 자료구조의 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);
- 리스트에 저장되어 있는 데이터의 수 반환.
LData는 리스트에 저장할 데이터의 자료형에 제한을 두지 않기 위한 typedef 선언의 결과로 헤더파일로 따로 관리한다.
우리는 리스트 자료구조의 ADT를 정의했고 ADT를 근거로 리스트 자료구조를 활용하는 main 함수를 정의할 것이다.
리스트의 ADT를 기반으로 정의된 main 함수
아래 main함수를 기반으로 리스트 ADT에서 소개하는 함수들의 기능을 완전히 이해해보자.
// 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("Number of Current Data: %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("Now Number of Data: %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"가 정의되지 않았기 때문에 실행을 하면 오류가 발생할 수 밖에 없다.
하지만 우리가 설정한 리스트이 ADT의 기능을 main 함수에 구현한 것이 중점이기 때문에 이를 찬찬히 먼저 살펴보자.
우선 위의 main 함수에서 제일 먼저 등장하는 리스트의 생성 및 초기화 관련된 문장은 아래와 같다.
int main()
{
List list; // 리스트의 생성
....
ListInit(&list); // 리스트의 초기화
....
}List를 기반으로 변수 list를 선언하고 있고 이걸 리스트라고 부를 것이다.
모든 자료구조는 단순히 데이터만 담는 것이 아니라 데이터를 효율적으로 저장 및 참조하기 위한 정보들도 담아야한다. 따라서 이와 관련된 변수들의 초기화 해야하면 이를 담당하는 함수가 ListInit이다.
이 후 데이터를 5번 저장했는데 LInsert 함수를 호출하면서 리스트의 주소 값을 첫 번째 인자로, 리스트에 담을 데이터를 두 번째 인자로 전달하고 있다.
이 후 데이터를 저장된 순서대로 데이터를 참조하여 출력을 진행하고, 마지막 데이터까지 참조하여 출력을 진행한다.
순서대로 참조하려면 먼저 LFirst를 호출해서 첫 번째 데이터를 얻고 두 번째 이후의 데이터는 LNext를 호출해서 얻으면 된다.
그리고 LFirst 함수와 LNext 함수는 더이상 참조할 데이터가 없다면 FALSE를 반환한다.
마지막으로 데이터 삭제관련 코드다.
삭제를 위해서는 데이터 탐색이 먼저 되어야하기 때문에 코드를 LFirst로 탐색한 후 삭제하고 싶은 데이터 값(22)과 동일하다면 LRemove 함수가 실행된다. 이 코드 진행은 출력과 동일하게 LFirst 이후 LNext로 이루어지게 된다.
배열기반 리스트 구현하기 1: 헤더파일의 정의
우리는 어떤 자료구조던 간에 '자료구조의 구현'과 '구현된 자료구조의 활용'이 완전히 구분되도록 ADT를 정의해야한다.
리스트 구현방법 중 하나인 배열을 이용해 구현하는 방법(순차 리스트)을 사용할 것이다.
그 첫 번째 순서로 배열 기반의 리스트 구현을 위해 정의된 헤더파일은 다음과 같다.
// ArrayList.h
#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__
#define TRUE 1 // 참을 표현하기 위한 메크로 정의
#define FALSE 0 // 거짓을 표현하기 위한 메크로 정의
#define LIST_LEN 100
typedef int LData; // LData에 대한 typedef 선언
typedef struct __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에는 데이터의 저장공간이 배열로 선언되었고,
저장된 데이터의 수를 기록하기 위한 멤버(numOfData)와
LFirst, LNext, LRemove 함수에서 참조의 위치를 기록하기 위한 멤버(curPosition)멤버가 있다.
다양한 종류의 데이터를 저장할 수 있게 하기 위한 typedef 선언도 다음과 같이 존재한다.
typedef int LData; // 리스트에 int형 데이터의 저장을 위한 선언
typedef ArrayList List; // List는 배열 기반 리스트ArrayList라는 이름에도 typedef 선언을 하면 연결리스트로 리스트 종류를 바꿀 수 있다.
typedef LinkedList List;
배열기반 리스트 구현하기 2: 함수 정의
이제 헤더파일에 선언된 함수들을 정의해보자.
1. 초기화 함수 - ListInit
이 함수를 정의하기 위해서는 먼저 앞서 정의한 구조체 ArrayList에서 초기화할 대상이 어떤 것인지 알아야한다.
void ListInit(List * plist)
{
(plist->numOfData) = 0; // 현재 리트스에 저장된 데이터 수 0
(plist->curPosition) = -1; // 현재 아무 위치도 가리키지 않음
}curPosition에는 배열의 인덱스 값이 저장된다.
LFirst 함수와 LNext 함수에서 참조해야할 배열의 위치를 이 변수에 저장된 값을 통해 알 수 있게 한다.
2. 삽입 함수 - LInsert
이 함수는 단순하게 우선 데이터의 수가 배열의 길이를 초과했는지 검사하고 초과하지 않았다면 일반적인 데이터의 저장과정을 진행한다. 저장할 때는 배열의 앞부분부터 채워나간다.
void LInsert(List * plist, LData data)
{
if(plist->numOfData >= LIST_LEN) // 데이터의 수 > 배열의 길이
{
puts("저장이 불가능합니다.");
return;
}
plist->arr[plist->numOfData] = data; // 데이터 저장
(plist->numOfData)++; // 저장된 데이터의 수 증가
}다음은 LFirst와 LNext 함수를 정의해보자.
3. 첫 번째 데이터 조회 - LFirst
int LFirst(List * plist, LData * pdata)
{
if(plist->numOfData == 0) // 저장된 데이터가 하나도 없다면
return FALSE;
(plist->numOfData) = 0; // 참조 위치 초기화. 첫 번째 데이터의 참조
*pdata = plist->arr[0]; // pdata가 가리키는 공간에 데이터 저장
return TRUE;
}4. 두 번째 이후의 데이터 조회 - LNext
int LNext(List * plist, LData * pdata)
{
if(plist->curPosition >= (plist->numOfData)-1) // 더 이상 참조할 데이터가 없다면
return FALSE;
(plist->curPosition)++;
*pdata = plist->arr[plist->curPosition];
return TRUE;
}LFirst 함수와 LNext 함수의 차이점은 다음 문장에 있다.
(plist->numOfData) = 0; (LFirst)와 (plist->numOfData)++; (LNext)이다.
LFirst에서는 curPosition에 저장된 값을 0으로 재설정함으로써 데이터의 참조가 앞에서부터 다시 진행할 수 있도록 한다.
반면, LNext에서는 이 값을 증가시켜 순서대로 데이터를 참조할 수 있도록 한다.
5. 삭제 - LRemove
마지막으로 데이터의 삭제를 담당하는 함수를 완성해보자.
LFirst 함수나 LNext 함수의 호출을 통해서 바로 직전에 참조가 이뤄진 데이터를 삭제하는 것이 LRemove 함수다보니 LRemove 함수가 호출되면 리스트의 멤버 curPosition을 확인해서 조회가 이뤄진 데이터의 위치를 확인한 다음 그 데이터를 삭제한다.
앞에서부터 데이터를 채우는 것이 원칙이니 중간에 데이터가 삭제되면, 뒤에 저장된 데이터들을 한 칸씩 앞으로 이동시켜서 그 빈 공간을 메워야 한다.
따라서 주의해야할 점은 삭제할 데이터의 위치를 참조하는 방식과 삭제를 위한 데이터의 이동과정이다.
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; // 삭제된 데이터의 반환
}참조위치를 하나 되돌리는 이유는 C가 삭제된 이후에 curPosition에 최근 참조가 이뤄진 데이터의 인덱스 정보를 담고 있어야하기 때문에 B를 가리켜야하는데 하나 되돌리지 않을 경우 D를 가리키고 있어 아직 참조가 이루어지지 않은 인덱스를 가리키기 때문이다.
따라서 삭제 이후 LNext 함수가 호출되면 아직 참조되지 않은 D를 가리킬 수 있게 된다.
6. 데이터 갯수 조회 - LCount
데이터 수를 조회하는 LCount 함수 정의는 간단하다.
int LCount(List * plist)
{
return plist->numOfData;
}배열기반 리스트 구현하기 3: 정리
위에서 설명한 함수 5가지를 하나의 파일로 정리해보자.
#include <stdio.h>
#include "ArrayList.h"
void ListInit(List * plist)
{
(plist->numOfData) = 0; // 현재 리트스에 저장된 데이터 수 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]; // 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;
}
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;
}이제 다시 한번 ListMain.c 파일을 컴파일해서 실행해보자.
> gcc .\ListMain.c .\ArrayList.c
> .\a.exe
> 출력
Number of Current Data: 5
11 11 22 22 33
Now Number of Data: 3
11 11 33리스트에 구조체 변수 저장하기 1: 구조체 Point와 관련 함수들의 정의
이전에 구현한 리스트에는 단순히 정수를 저장했다.
하지만 실제로 구조체 변수를 비롯해서 각종 데이터들이 저장된다.
따라서 우리가 정의한 리스트에 구조체 변수의 주소값을 저장해 보자.
이를 위해서 다음과 같은 구조체를 정의했다.
typedef struct _point
{
int xpos; // x좌표 정보
int ypos; // y좌표 정보
} Point;정수가 아닌 다른 데이터를 리스트에 저장한다는데 의미가 있으므로, 구조체는 가급적 간단히 정의했다.
위의 구조체와 관련 있는 다른 함수들도 함께 정의해준다.
void SetPointPos(Point * ppos, int xpos, int ypos);: 구조체 변수에 값을 저장void ShowPointPos(Point * ppos);: 저장된 정보 출력int PointComp(Point * pos1, Point * pos2);: 두 구조체 변수에 저장된 값 비교
위 함수가 반환하는 값은 다음과 같다고 정의한다.
- 두 Point 변수의 멤버 xpos만 같으면 1 반환
- 두 Point 변수의 멤버 ypos만 같으면 2 반환
- 두 Point 변수의 멤버가 모두 같으면 0 반환
- 두 Point 변수의 멤버가 모두 다르면 -1 반환
이렇게 해서 구조체 Point와 구조체 Point 관련 함수들의 선언 및 정의를 다음 헤더파일과 소스파일에 나누어 저장했다.
// Point.h
리스트에 구조체 변수 저장하기 2: 구조체 Point와 관련함수들의 정의
배열 기반 리스트 코드에서 Point 구조체 변수의 주소 값을 저장할 수 있도록 Point 구조체 관련하여 약간의 수정을 해줘야한다.
#include "Point.h"추가typedef int LData;👉typedef Point * LData;변경
그리고 Point 구조체 변수에 대해 실행할 main 함수를 구현하면 아래와 같다.
//PointListMain.c
#include <stdio.h>
#include <stdlib.h>
#include "ArrayList.h"
#include "Point.h"
int main()
{
List list;
Point compPos;
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("Now number of data: %d \n", LCount(&list));
if(LFirst(&list, &ppos))
{
ShowPointPos(ppos);
while(LNext(&list, &ppos))
ShowPointPos(ppos);
}
printf("\n\n");
// xpos가 2인 모든 데이터 삭제 ///////
compPos.xpos = 2;
compPos.ypos = 0;
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("Now number of data: %d \n", LCount(&list));
if(LFirst(&list, &ppos))
{
ShowPointPos(ppos);
while(LNext(&list, &ppos))
ShowPointPos(ppos);
}
printf("\n");
return 0;
}
> gcc .\PointListMain.c .\ArrayList.c .\Point.c
> .\a.exe
> 출력
Now number of data: 4
[2, 1]
[2, 2]
[3, 1]
[3, 2]
Now number of data: 2
[3, 1]
[3, 2]위 main 함수에서 LRemove 함수가 삭제된 데이터를 반환하도록 한 이유는 리스트에 저장한 데이터가 'Point 구조체 변수의 주소 값'이기 때문이다. 이 주소 값은 Point 구조체를 동적으로 할당한 결과이기 때문에, 반드시 free 함수를 통한 메로리의 해체과정을 거쳐야한다.
때문에 LRemove 함수처럼 데이터를 소멸하는 함수는 소멸된 데이터를 반환하도록 정의해야 한다.
배열 기반 리스트이 장점과 단점
- 장점 (배열의 일반적인 장점)
- 데이터 참조가 쉽다. 인덱스 값 기준으로 어디든 한 번에 참조가 가능하다.
- 단점 (배열의 일반적인 단점)
- 배열의 길이가 초기에 결정되어야 한다. 변경이 불가능하다.
- 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어난다.
<Review>
드디어 처음으로 C언어로 자료구조를 구현해봤다.
생각보다 Django에서 기능하나를 만들 때 어떤 기능인지 먼저 설정하고 이 기능에 필요한 것들을 model, serializer 등 하나하나 세워서 만드는 느낌과 비슷하다 생각이 들었다.
파이썬에서 문장은 이해하는데 머리 속으로 한번에 들어오지 않았는데 이걸 배우고 다시 본다면 다시 이해하기 쉬울지도...!
연결 리스트는 아직 안배웠으니 쉬운 걸 수도 있다 하핫
트리랑 그래프까지 할 수 있도록 화이팅이다~!
(Point 구조체 사용할 때 기존 ArrayList.h를 수정하는 과정에서 typedef Point * LData에서 *를 빼먹어서 오류를 계속 찾는데 시간을 쏟았다.
앞으로 코드를 작성할 때 더 신중하고 꼼꼼하게 봐야겠다.)
