추상 자료형(ADT, Abstract Data Type)
지갑을 ADT로 정리하면?
코드 구현
typedef struct _wallet
{
int coin100Num; // 100원짜리 동전의 수
int bill5000Num; // 5,000원짜리 지폐의 수
}
int TakeOutMoney(Wallet * pw, int coinNum, int billNum); // 돈을 꺼내는 연산
void PutMoney(Wallet * pw, int coinNum, int billNum); // 돈을 넣는 연산구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것을 가리켜 '추상 자료형' 또는 간단히 ADT라 한다.
리스트의 이해
리스트는 곧 연결리스트인가? X
리스트는 배열 기반의 순차리스트와 동적 할당 기반의 연결리스트로 나뉜다.
리스트 자료구조는 데이터를 나란히 저장하고 중복된 데이터의 저장을 막지 않는다.
리스트 자료구조의 ADT
void ListInit(List* plist)
: 초기화할 리스트의 주소 값을 인자로 저장한다.
: 리스트 생성 후 제일 먼저 호출되어야 하는 함수이다.
void LInsert(List* plist, LData data)
: 리스트에 데이터를 저장한다. 매개변수 data에 전달된 값을 저장한다.
void LFirst(List* plist, LData pdata)
: 첫 번째 데이터가 pdata가 가리키는 메모리에 저장된다.
: 데이터의 참조를 위한 초기화가 진행된다.
: 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환
void LNext(List* plist, LData pdata)
: 참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장된다.
: 순차적인 참조를 위해서 반복 호출이 가능하다.
: 참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야 한다.
: 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환
LData LRemove(List* plist)
: LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다.
: 삭제된 데이터는 반환된다.
: 마지막 반환 데이터를 삭제하므로 연이은 반복 호출은 허용하지 않는다.
int LCount(List* plist)
: 리스트에 저장되어 있는 데이터의 수를 반환한다.
리스트의 ADT를 기반으로 정의된 main 함수
#include <stdio.h>
#include "ArrayList.h"
int main(void)
{
//1. 리스트를 생성 및 초기화 한 다음, 정수 1부터 9까지 리스트에 저장한다.
List list;
int data;
int sum = 0;
ListInit(&list);
for(int i=1; i<10; i++)
LInsert(&list, i);
printf("현재 데이터의 수: %d \n", LCount(&list));
if(LFirst(&list, &data))
{
printf("%d ", data);
while(LNext(&list, &data))
{
printf("%d ", data);
}
}
printf("\n\n");
//2. 리스트에 저장된 값을 순차적으로 참조하여 그 합을 계산하여 출력한다.
if(LFirst(&list, &data))
{
sum = sum + data;
while(LNext(&list, &data))
{
sum = sum + data;
}
printf("데이터의 총 합: %d \n\n", sum);
}
//3. 리스트에 저장된 값들 중 2의 배수와 3의 배수에 해당하는 값을 모두 삭제한다.
if(LFirst(&list, &data))
{
if(data%2 == 0 || data%3 == 0)
LRemove(&list);
while(LNext(&list, &data))
{
if(data%2 == 0 || data%3 == 0)
LRemove(&list);
}
}
//4. 마지막으로 리스트에 저장된 데이터를 순서대로 출력한다.
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 헤더파일
// ArrayList.h
#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__
#define TRUE 1
#define FALSE 0
#define LIST_LEN 100
typedef int LData;
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.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)++;
}
inf 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-i; i++)
plist->arr[i] = plist->arr[i+1];
(plist->numOfData)--;
(plist->curPosition)--;
return rdata;
}
int LCount(List * plist)
{
return plist->numOfData;
}구조체 변수의 주소 값을 저장하기 위해 다음 구조체 함수들을 선언 및 정의
// Point.h
#ifndef __POINT_H_
#define __POINT_H_
typedef struct _point
{
int xpos;
int ypos;
} Point;
// Point 변수의 xpos, ypos 값 설정
void SetPointPos(Point * ppos, int xpos, int ypos);
// Point 변수의 xpos, ypos 정보 출력
void ShowPointPos(Point * ppos);
// 두 Point 변수의 비교
int PointComp(Point * pos1, Point * pos2);
#endif// Point.c
#include <stdio.h>
#include "Point.h"
// Point 변수의 xpos, ypos 값 설정
void SetPointPos(Point * ppos, int xpos, int ypos)
{
ppos->xpos = xpos;
ppos->ypos = ypos;
}
// Point 변수의 xpos, ypos 정보 출력
void ShowPointPos(Point * ppos)
{
printf("{%d, %d} \n", ppos->xpos, ppos->ypos);
}
// 두 Point 변수의 비교
int PointComp(Point * pos1, Point * pos2)
{
if(pos1->xpos == pos2->xpos && pos1->ypos == pos2->ypos)
return 0;
else if(pos1->xpos == pos2->xpos)
return 1;
else if(pos1->ypos == pos2->ypos)
return 2;
else
return -1;
}위 Point 구조체를 기존 리스트 소스에 적용하려면
ArrayList.h에서 typedef int LData; 선언을 typedef Point * LData; 로 변경이 필요하다.
#include "Point.h" 헤더파일 선언도 당연히 필요
그리고 아래는 main 함수
main 함수 코드 구현
#include <stdio.h>
#include <stdlib.h>
#include "ArrayList.h"
#include "Point.h"
int main(void)
{
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("현재 데이터의 수: %d \n", LCount(&list));
if(LFirst(&list, &ppos))
{
ShowPointPos(ppos);
while(LNext(&list, &ppos))
ShowPointPos(ppos);
}
printf("\n");
// xpos가 2인 모든 데이터 삭제
compPos.xpos=2;
compPos.ypos=0;
if(LFirst(&list, &ppos))
{
if(PointComp(ppos, &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");
return 0;
}
댓글 없음:
댓글 쓰기