첫번째 자료구조 소개 전 '추상 자료형' 이라는 용어 소개→이해 필수
03-1 '추상 자료형'(Abstract Data Type) 이란?
- 자료구조의 관점에서보면, 구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것'
그럼 위의 설명을 왜 추상 자료형이라고 부르는가?
- 컴퓨터 공학적 측면에서 연산의 종류를 결정하는 것도 자료형 정의의 일부로 보아야 하고, 연산의 ****종류가 결정되었을 때 자료형의 정의는 완성이 된다.
- 이 때 말하는 연산은 특정 언어(ex) c++, python) 에서 제공하는 기본 연산을 의미하는 것이 아니라, 제공할 수 있는 기능관련연산(함수)
ex) 아래와 같이 구조체를 기반으로 지갑을 의미하는 Wallet이라는 자료형을 정의
typedef struct _wallet
{
int coin100Num; // 100원짜리 동전의 수
int bill5000Num;// 5000원짜리 지폐의 수
} Wallet;
Wallet을 기반으로 제공할 수 있는 기능 관련 연산이 포함되어야 자료형의 정의가 완성됨
int TakeOutMoney(Wallet *pw, int coinNum, int billNum); //돈을 꺼내는 연산
int PutMoney(Wallet *pw, int coinNum, int billNum); //돈을 넣는 연산
결론
'자료형'의 정의에 '기능' 혹은 '연산'과 관련된 내용을 명시할 수 있다는 것
구조체 Wallet의 추상 자료형 정의
추상자료형(ADT) 에 대해 다시 설명하면,
구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것
결국 Wallet의 ADT를 아래처럼 정의할 수 있음
Operations:
int TakeOutMoney(Wallet *pw, int coinNum, int billNum)
**첫번째 인자로 전달된 주소의 지갑에서 돈을 꺼낸다
두번째 인자는 꺼낼 동전의 수, 세번째 인자는 꺼낼 지폐의 수를 전달한다.
꺼내고자 하는 돈의 총액을 반환된다. 그리고 그만큼 돈은 차감된다.**
void PutMoney(Wallet *pw, int coinNum, int billNum)
**첫번째 인자로 전달된 주소의 지갑에 돈을 넣는다.**
**두번째 인자는 꺼낼 동전의 수, 세번째 인자는 꺼낼 지폐의 수를 전달한다.
넣은 만큼 동전과 지폐의 수가 증가한다.**
위에서는 추상 자료형을 명시하는데 있어 특정 언어에 의존적(C or C++)이게 표기했지만, 특정 언어에 의존적이지 않게 별도의 표기법을 활용하는 것도 가능
Q. 최소한 구조체 Wallet의 정의는 ADT에 포함시켜야 하는 것 아닌가?
- 필요하다면 가능, 제한은 없음
- Q.Wallet의 정의는 필요한 정보인가? →이를 판단하기 위해 아래 main 함수를 보면,
int main()
{
Wallet myWallet; //지갑 하나
PutMoney(&myWallet, 5, 10); //돈을 넣음
ret = TakeOutMoney(&myWallet, 2, 5); //돈을 꺼냄
}
- 구조체 Wallet의 멤버가 어떻게 구성이 되어있는지 몰라도 Wallet을 기반으로 돈을 넣고 뺄 수 있음 →Wallet의 멤버 구성을 알 필요 없음 → Wallet의 정의를 ADT에 포함시키지 않는 것이 바람직
Q. 동전이나 지폐가 몇개씩 있는지 확인해야하는 경우에는? 이런 경우를 위해 Wallet의 멤버에 대해 알아야 하지 않나?
→ 동전이나 지폐의 수를 확인해야 한다면, 그에 관련된 연산을 위의 ADT에 추가하는 것이 더 바람직
→ 구초제 멤버에 직접 접근하는 것에 훨씬 익숙하지만 이것이 늘 옳은 것인지는 고민해봐야 함
자료구조의 학습에 ADT의 정의를 포함합니다.
이후의 자료구조에 대해서 아래와 같은 학습 순서를 요함.
- 자료구조의 ADT를 정의
- ADT를 근거로 리스트 자료구조를 활용하는 main 함수를 정의
- ADT를 근거로 리스트를 구현
위의 학습 순서는 "사용자에게 사용방법 이외에 불필요한 부분까지 알도록 부담주지 않기 위해"이고, 내부 구현을 알지 못해서 활용할 수 있도록 자료구조를 구현할 것
03-2 배열을 이용한 리스트의 구현
리스트의 이해
- 리스트라는 자료구조는 구현방법에 따라 크게 2가지로 나뉨
- 순차 리스트(Array list) : 배열을 기반으로 구현된 리스트
- 연결 리스트(linked list) : 메모리의 동적 할당을 기반으로 구현된 리스트
- 구현방법에 따라 나뉘기 때문에 둘의 ADT가 동일하다고 해서 문제될 것은 없음
- 각종 자료구조들의 ADT는 표준이 있는게 아니라, 필요에 따라 달라짐
- 리스트의 ADT 정의를 위해 리스트 자료 구조의 가장 기본적이고도 중요한 특성
- 데이터를 나란히 저장
- 중복된 데이터의 저장을 허용
리스트의 ADT
- 특성에 대해(ex) 데이터를 어떻게 나란히 저장할지) 고민하는 게 아니라, 나란히 저장된다는 특성을 기반으로 제공해야 할 기능들을 정의해야 하는 것
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);
**- 리스트에 저장되어 있는 데이터의 수를 반환한다.**
리스트의 ADT를 기반으로 정의된 main 함수
- 정의된 ADT를 기반으로 main 함수 작성
- 아래의 main 함수를 보면서, 어떤 라이브러리에 포함되어 있는 리스트의 사용방법을 파악하는 상황이라고 생각
//main.cpp
#include "ArrayList.h"
using namespace std;
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);
//저장된 데이터의 수 출력
cout << "현재 데이터의 수 : " << LCount(&list) << endl;
if (LFirst(&list, &data)) //첫 번째 데이터 조회
{
cout << data << " ";
while (LNext(&list, &data)) //두번째 이후 데이터 조회
cout << data << " ";
}
cout << endl;
cout << endl;
//숫자 22를 탐색하여 모두 삭제
if (LFirst(&list, &data))
{
if (data == 22)
LRemove(&list);
while (LNext(&list, &data))
{
if (data == 22)
LRemove(&list);
}
}
//삭제 후 남은 데이터 전체 수 출력
cout << "현재 데이터의 수 : " << LCount(&list) << endl;
if (LFirst(&list, &data))
{
cout << data << " ";
while (LNext(&list, &data))
cout << data << " ";
}
cout << endl;
cout << endl;
return 0;
}
//#ifndef __ARRAY_LIST_H__
//#define __ARRAY_LIST_H__
#pragma once
#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.cpp
#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;
}
현재 데이터의 수 : 5
11 11 22 22 33
현재 데이터의 수 : 3
11 11 33
리스트! 배열을 기반으로 구현하기1: 헤더파일의 정의
앞서 보인 main 함수에 리스트의 구현과 관련된 어떠한 코드도 등장하지 않았음
→ '자료구조의 구현'과 '구현된 자료구조의 활용'은 완전히 구분되도록 ADT를 정의해야 함
#pragma once
#include <iostream>
#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);
리스트! 배열을 기반으로 구현하기2: 삽입과 조회
- 헤더파일에 선언된 함수들을 정의해야 함
- 먼저 아래의 두 함수
void ListInit(List *plist); //초기화
void LInsert(List *plist, LData data); //데이터 저장
#include "ArrayList.h"
void ListInit(List * plist)
{
plist->numOfData = 0; //리스트에 저장된 데이터의 수는 0
plist->curPosition = -1; //배열의 index값. 현재 아무 위치도 가리키지 않음!
}
void LInsert(List * plist, LData data)
{
//더이상 저장할 공간이 없는 경우
if (plist->numOfData >= LIST_LEN)
{
std::cout << "더 이상 데이터 저장 불가" << std::endl;
}
plist->arr[plist->numOfData] = data; //데이터 저장
plist->numOfData++; //저장된 데이터 수 증가
}
다음 세 함수
int LFirst(List *plist, LData *pdata);
int LNext(List *plist, LData *pdata);
int LCount(List *plist);
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 += 1;
*pdata = plist->arr[plist->curPosition];
return TRUE;
}
int LCount(List * plist)
{
return plist->numOfData;
}
리스트! 배열을 기반으로 구현하기3 : 삭제
- LRemove 함수가 호출되면 리스트의 멤버 cur_pos를 확인해서 조회가 이뤄진 데이터의 위치를 확인한 다음 그 데이터를 삭제
- 앞에서부터 데이터를 채우는 것이 원칙이니 중간에 데이터가 삭제되면, 뒤에 저장된 데이터들을 한칸씩 앞으로 이동시켜서 그 빈 공간을 메워야 함
LData LRemove(List * plist)
{
// curposition 데이터 삭제하고
// 뒤에 데이터들 한칸씩 앞으로 이동
// 그리고 참조 데이터는 이전 데이터
// 삭제된 값 return
LData rdata = plist->arr[plist->curPosition];
for (int i = plist->curPosition; i < plist->numOfData; i++)
{
plist->arr[i] = plist->arr[i + 1];
}
plist->curPosition--;
plist->numOfData--;
return plist->curPosition;
}
Q. 아래코드가 삽입된 이유?
plist->curPosition--; //참조위치를 하나 앞으로(배열 기준 왼쪽으로) 옮긴다.
- curPosition 변수는 최근에 참조가 이뤄진 데이터의 인덱스 정보를 담아야 함
- 삭제로 인해 비는 공간을 메우려 데이터를 한 칸씩 왼쪽으로 이동시키면, 참조가 이뤄지지 않는 데이터를 가리키게 되므로, cur_pos 변수가 가리키는 인덱스를 한칸 왼쪽으로 옮겨야 한다.
배열 기반의 리스트 구현 하나로 묶기
#include "ArrayList.h"
void ListInit(List * plist)
{
plist->numOfData = 0; //리스트에 저장된 데이터의 수는 0
plist->curPosition = -1; //배열의 index값. 현재 아무 위치도 가리키지 않음!
}
void LInsert(List * plist, LData data)
{
//더이상 저장할 공간이 없는 경우
if (plist->numOfData >= LIST_LEN)
{
std::cout << "더 이상 데이터 저장 불가" << std::endl;
}
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 += 1;
*pdata = plist->arr[plist->curPosition];
return TRUE;
}
LData LRemove(List * plist)
{
// curposition 데이터 삭제하고
// 뒤에 데이터들 한칸씩 앞으로 이동
// 그리고 참조 데이터는 이전 데이터
// 삭제된 값 return
LData rdata = plist->arr[plist->curPosition];
for (int i = plist->curPosition; i < plist->numOfData; i++)
{
plist->arr[i] = plist->arr[i + 1];
}
plist->curPosition--;
plist->numOfData--;
return plist->curPosition;
}
int LCount(List * plist)
{
return plist->numOfData;
}
- 만든 리스트를 사용하기 위해서는 헤더에 선언된 함수의 기능을 숙지하면 됨
- 실제 리스트가 어떻게 구현되어 있는지 확인할 필요는 없음
리스트에 구조체 변수 저장하기1: 구조체 Point와 관련 함수들의 정의
- 앞의 예에서는 리스트에 간단한 정수만 저장하였지만 구조체 변수를 비롯하여 각종 데이터 저장 가능
- 리스트에 '구조체 변수의 주소 값'을 저장해보고자 함
typedef struct _point
{
int xpos;
int ypos;
}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.h
#pragma once
#include <iostream>
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);
//Point.cpp
#include "Point.h"
void setPointPos(Point * ppos, int xpos, int ypos)
{
ppos->xpos = xpos;
ppos->ypos = ypos;
}
void ShowPointPos(Point * ppos)
{
std::cout << ppos->xpos << " " << ppos->ypos << std::endl;
}
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;
}
리스트에 구조체 변수 저장하기2: 구조체 Point와 관련함수들의 정의
- Point 구조체 변수의 주소 값을 저장할 수 있도록 변경
- 헤더파일(ArrayList.h)은 일부 변경해야하지만, 소스파일(ArrayList.cpp)은 변경하지 않아도 됨
//ArrayList.h
typedef int LData; **//(typedef 선언변경) -> typedef Point *LData;**
- List가 int형 data를 담는 것에서 Point 구조체의 포인터를 담는 것으로 변경되었기 때문에 main 내용은 변경됨
- ArrayList.h에 Point 변수를 사용하므로 Point.h 파일 include 필요
//main.cpp
#include "ArrayList.h"
#include "Point.h"
using namespace std;
int main()
{
//ArrayList의 생성 및 초기화
List list;
Point comPos;
Point *ppos;
ListInit(&list);
// 4개의 데이터 저장
ppos = new Point;
SetPointPos(ppos, 2, 1);
LInsert(&list, ppos);
ppos = new Point;
SetPointPos(ppos, 2, 2);
LInsert(&list, ppos);
ppos = new Point;
SetPointPos(ppos, 3, 1);
LInsert(&list, ppos);
ppos = new Point;
SetPointPos(ppos, 3, 2);
LInsert(&list, ppos);
//저장된 데이터의 수 출력
cout << "현재 데이터의 수 : " << LCount(&list) << endl;
if (LFirst(&list, &ppos)) //첫 번째 데이터 조회
{
ShowPointPos(ppos);
while (LNext(&list, &ppos)) //두번째 이후 데이터 조회
ShowPointPos(ppos);
}
cout << endl;
cout << endl;
//xpos가 2인 모든 데이터 삭제
if (LFirst(&list, &ppos))
{
if (ppos->xpos==2)
{
ppos=LRemove(&list);
delete ppos;
}
while (LNext(&list, &ppos))
{
if (ppos->xpos == 2)
{
ppos = LRemove(&list);
delete ppos;
}
}
}
//삭제 후 남은 데이터 전체 수 출력
cout << "현재 데이터의 수 : " << LCount(&list) << endl;
if (LFirst(&list, &ppos)) //첫 번째 데이터 조회
{
ShowPointPos(ppos);
while (LNext(&list, &ppos)) //두번째 이후 데이터 조회
ShowPointPos(ppos);
}
cout << endl;
cout << endl;
return 0;
}
- LRemove 함수에서 왜 삭제된 데이터를 반환하도록 디자인했는지 알 수 있음
- 리스트에 저장한 데이터는 Point 구조체 변수의 주소값으로 동적 할당한 메모리의 해제 과정을 거쳐야 메모리 누수를 막을 수 있다
문제 3-2 [리스트의 활용]
//NameCard.h
#pragma once
#define NAME_LEN 30
#define PHONE_LEN 30
typedef struct __namecard
{
char name[NAME_LEN];
char phone[PHONE_LEN];
}NameCard;
//NameCard 구조체 변수의 동적 할당 및 초기화 후 주소 값 반환
NameCard* MakeNameCard(const char *name, const char *phone);
//NameCard 구조체 변수의 정보출력
void ShowNameCardInfo(NameCard *pcard);
//이름이 같으면 0, 다르면 0이 아닌 값 반환
int NameCompare(NameCard *pcard, const char *name);
//전화번호 정보를 변경
void ChangePhoneNum(NameCard *pcard, const char *phone);
//NameCard.cpp
#include "NameCard.h"
#include <iostream>
NameCard * MakeNameCard(const char * name, const char * phone)
{
NameCard *name_card = new NameCard;
strcpy(name_card->name, name);
strcpy(name_card->phone, phone);
return name_card;
}
void ShowNameCardInfo(NameCard * pcard)
{
std::cout << pcard->name << " " << pcard->phone << std::endl;
}
int NameCompare(NameCard * pcard, const char * name)
{
return strcmp(pcard->name, name);
}
void ChangePhoneNum(NameCard * pcard, const char * phone)
{
strcpy(pcard->phone, phone);
}
//main.cpp
#include <iostream>
#include "ArrayList.h"
using namespace std;
int main()
{
List list;
ListInit(&list);
NameCard *p_namecard;
p_namecard = MakeNameCard("최우성", "111");
LInsert(&list, p_namecard);
p_namecard = MakeNameCard("임은지", "222");
LInsert(&list, p_namecard);
p_namecard = MakeNameCard("최우승", "333");
LInsert(&list, p_namecard);
LCount(&list);
//특정이름을 대상으로 탐색 후 그 사람의 정보 출력
if (LFirst(&list, &p_namecard))
{
//같으면 0 return
if (NameCompare(p_namecard, "최우성")==0)
ShowNameCardInfo(p_namecard);
else
{
while(LNext(&list, &p_namecard))
{
if (NameCompare(p_namecard, "최우성") == 0)
{
ShowNameCardInfo(p_namecard);
break;
}
}
}
}
//특정이름을 대상으로 탐색 후 그 사람의 전화번호 변경
if (LFirst(&list, &p_namecard))
{
//같으면 0 return
if (NameCompare(p_namecard, "임은지") == 0)
{
ChangePhoneNum(p_namecard, "444");
ShowNameCardInfo(p_namecard);
}
while (LNext(&list, &p_namecard))
{
if (NameCompare(p_namecard, "임은지") == 0)
{
ChangePhoneNum(p_namecard, "444");
ShowNameCardInfo(p_namecard);
break;
}
}
}
//특정이름 대상으로 탐색 후 그 사람의 정보 삭제
if (LFirst(&list, &p_namecard))
{
if (NameCompare(p_namecard, "최우승") == 0)
{
LRemove(&list);
delete p_namecard;
}
while(LNext(&list, &p_namecard))
{
if (NameCompare(p_namecard, "최우승") == 0)
{
LRemove(&list);
delete p_namecard;
break;
}
}
}
if (LFirst(&list, &p_namecard))
{
ShowNameCardInfo(p_namecard);
while (LNext(&list, &p_namecard))
{
ShowNameCardInfo(p_namecard);
}
}
return 0;
}
배열의 장점과 단점! 그리고 연결 기반 리스트
- 배열 기반 리스트의 장점
- 데이터의 참조가 쉽다. 인덱스 값을 기준으로 어디든 한 번에 참조가 가능
- 배열 기반 리스트의 단점
- 배열의 길이가 초기에 결정되어야 함→ 변경 불가
- 삭제의 과정에서 데이터의 이동(복사)이 매우 빈번히 일어남
