자료구조 구현 (1), Unsorted list

Unsorted list 구현

 

C++을 통해서 Unsorted list를 구현했다. 특히 ItemType, Unsorted list, Application을 세 파트로 나누어 코드를 구현했다. Unsorted list는 각 요소로서 ItemType을 포함하고 있고, Application에서 Unsorted list를 객체로 사용했다. 또한 각각의 파트는 헤더와 cpp 파일을 구분해 각각 구현했다.

 

해당 실습에서의 특징적인 점은 Unsorted list를 Linked list가 아닌 Array list로 구현했다. 이에 따라 데이터 삽입, 삭제하는 방법이 다르니 이를 고려하여 코드를 확인하면 좋을 것 같다.

 

1. ItemType

1) ItemType h

#ifndef _ITEMTYPE_H
#define _ITEMTYPE_H

#include <iostream>
#include <fstream>
#include <string>

using namespace std;


/**
*	Relation between two items.
*/
enum RelationType {LESS, GREATER, EQUAL};


/**
*	item information class.
*/
class ItemType
{
public:
	/**
	*	default constructor.
	*/
	ItemType()
	{
		m_Id = -1;
		m_sName = "";
		m_sAddress = "";
	}

	/**
	*	destructor.
	*/
	~ItemType()	{}

	/**
	*	@brief	Get student id.
	*	@pre	student id is set.
	*	@post	none.
	*	@return	student id.
	*/
	int GetId()
	{
		return m_Id;
	}

	/**
	*	@brief	Get student name.
	*	@pre	student name is set.
	*	@post	none.
	*	@return	student name.
	*/
	string GetName()
	{
		return m_sName;
	}

	/**
	*	@brief	Get student address
	*	@pre	student address is set.
	*	@post	none.
	*	@return	student address.
	*/
	string GetAddress()
	{
		return m_sAddress;
	}

	/**
	*	@brief	Set student id.
	*	@pre	none.
	*	@post	student id is set.
	*	@param	inId	student id.
	*/
	void SetId(int inId)
	{
		m_Id = inId;
	}
	
	/**
	*	@brief	Set student name.
	*	@pre	none.
	*	@post	student name is set.
	*	@param	inName	student name.
	*/
	void SetName(string inName)
	{
		m_sName = inName;
	}
	
	/**
	*	@brief	Set student address.
	*	@pre	none.
	*	@post	student address is set.
	*	@param	inAddress	student address.
	*/
	void SetAddress(string inAddress)
	{
		m_sAddress = inAddress;
	}
	
	/**
	*	@brief	Set student record.
	*	@pre	none.
	*	@post	student record is set.
	*	@param	inId	student id.
	*	@param	inName	student name.
	*	@param	inAddress	student address.
	*/
	void SetRecord(int inId, string inName, string inAddress)
	{
		SetId(inId);
		SetName(inName);
		SetAddress(inAddress);
	}

	/**
	*	@brief	Display student id on screen.
	*	@pre	student id is set.
	*	@post	student id is on screen.
	*/
	void DisplayIdOnScreen() 
	{
		cout << "\tID   : " << m_Id << endl; 
	};

	/**
	*	@brief	Display student name on screen.
	*	@pre	student name is set.
	*	@post	student name is on screen.
	*/
	void DisplayNameOnScreen() 
	{
		cout << "\tName : " << m_sName << endl; 
	};

	/**
	*	@brief	Display student address on screen.
	*	@pre	student address is set.
	*	@post	student address is on screen.
	*/
	void DisplayAddressOnScreen() 
	{
		cout << "\tAddress : " << m_sAddress << endl; 
	};

	/**
	*	@brief	Display an student record on screen.
	*	@pre	student record is set.
	*	@post	student record is on screen.
	*/
	void DisplayRecordOnScreen()
	{
		DisplayIdOnScreen();
		DisplayNameOnScreen();
		DisplayAddressOnScreen();
	};

	/**
	*	@brief	Set student id from keyboard.
	*	@pre	none.
	*	@post	student id is set.
	*/
	void SetIdFromKB();

	/**
	*	@brief	Set student name from keyboard.
	*	@pre	none.
	*	@post	student name is set.
	*/
	void SetNameFromKB();

	/**
	*	@brief	Set student address from keyboard.
	*	@pre	none.
	*	@post	student address is set.
	*/
	void SetAddressFromKB();
	
	/**
	*	@brief	Set student record from keyboard.
	*	@pre	none.
	*	@post	student record is set.
	*/
	void SetRecordFromKB();

	/**
	*	@brief	Read a record from file.
	*	@pre	the target file is opened.
	*	@post	student record is set.
	*	@param	fin	file descriptor.
	*	@return	return 1 if this function works well, otherwise 0.
	*/
	int ReadDataFromFile(ifstream& fin);

	/**
	*	@brief	Write a record into file.
	*	@pre	the target file is opened. And the list should be initialized.
	*	@post	the target file is included the new student record.
	*	@param	fout	file descriptor.
	*	@return	return 1 if this function works well, otherwise 0.
	*/
	int WriteDataToFile(ofstream& fout);
	
	/**
	*	Compare two itemtypes.
	*	@brief	Compare two item types by item id.
	*	@pre	two item types should be initialized.
	*	@post	the target file is included the new item record.
	*	@param	data	target item for comparing.
	*	@return	return LESS if this.id < data.id, 
	*			return GREATER if this.id > data.id then,
	*			otherwise return EQUAL.
	*/
	RelationType CompareByID(const ItemType &data);

protected:
	int m_Id;			///< student ID.
	string m_sName;		///< student name.
	string m_sAddress;	///< student address.
};

#endif	// _ITEMTYPE_H

 

 

 

2) ItemType cpp

#include "ItemType.h"


// Set student id from keyboard.
void ItemType::SetIdFromKB()
{
	cout << "\tID : ";
	cin >> m_Id;
}


// Set student name from keyboard.
void ItemType::SetNameFromKB()
{
	cout << "\tName : ";
	cin >> m_sName;
}


// Set student address from keyboard.
void ItemType::SetAddressFromKB()
{
	cout << "\tAddress : ";
	cin >> m_sAddress;
}


// Set student record from keyboard.
void ItemType::SetRecordFromKB()
{
	SetIdFromKB();
	SetNameFromKB();
	SetAddressFromKB();
}


// Read a record from file.
int ItemType::ReadDataFromFile(ifstream& fin)
{
	fin >> m_Id;
	fin >> m_sName;
	fin >> m_sAddress;

	return 1;
};


// Write a record into file.
int ItemType::WriteDataToFile(ofstream& fout)
{
	fout << endl;
	fout << m_Id << " ";
	fout << m_sName << " ";
	fout << m_sAddress;

	return 1;
}


// Compare two itemtypes.
RelationType ItemType::CompareByID(const ItemType &data)
{
	if(this->m_Id > data.m_Id)
		return GREATER;
	else if(this->m_Id < data.m_Id)
		return LESS;
	else
		return EQUAL;
}

- ItemType은 ID, Name, Address 값을 가지고 있다. linked list가 아니기에 별도의 pointer는 가지고 있지 않다.

- Unsorted list의 자료형은 각 요소의 데이터 타입과는 독립적으로 구현하고자 ItemType에서 Display하는 메소드를 구현했다.

- Sorted list에서도 해당 ItemType을 사용하기 위해 ID 값을 기준으로 대소관계를 파악하여 열거형으로 값을 반환하는 메소드를 작성했다. 

- Application 파트에서 파일 입출력하는 기능이 있어 이를 ItemType에서 받아올 수 있도록 했다.

 

2. ArrayList (Unsorted list)

1) ArrayList h

#ifndef _UNSORTEDLIST_H
#define _UNSORTEDLIST_H

#include <iostream>
#include <fstream>	
#include <string>
using namespace std;

#include "ItemType.h"

#define MAXSIZE 5

/**
*	array based simple unsorted list.
*/
class ArrayList
{
public:
	/**
	*	default constructor.
	*/
	ArrayList()
	{
		m_Length = 0;
		ResetList();
	}

	/**
	*	destructor.
	*/
	~ArrayList()	{}

	/**
	*	@brief	Make list empty.
	*	@pre	none.
	*	@post	clear list.
	*/
	void MakeEmpty();

	/**
	*	@brief	Get a number of records in current list.
	*	@pre	none.
	*	@post	none.
	*	@return	number of records in current list.
	*/
	int GetLength();

	/**
	*	@brief	Check capacity of list is full.
	*	@pre	none.
	*	@post	none.
	*	@return	return true if list capacity reached to the upper bound, otherwise return false.
	*/
	bool IsFull();

	/**
	*	@brief	add a new data into list.
	*	@pre	list should be initialized.
	*	@post	added the new record into the list.
	*	@param	data	new data.
	*	@return	return 1 if this function works well, otherwise 0.
	*/
	int Add(ItemType data);

	/**
	*	@brief	Initialize list iterator.
	*	@pre	list should be initialized.
	*	@post	iterator is reset.
	*/
	void ResetList();

	/**
	*	@brief	move list iterator to the next item in list and get that item.
	*	@pre	list and list iterator should not be initialized. 
	*	@post	iterator is moved to next item.
	*	@param	data	get current iterator's item. it does not need to be initialized.
	*	@return	index of current iterator's item if is not end of list, oterwise return -1.
	*/
	int GetNextItem(ItemType& data);

	/** [작성]
	*	@brief	전달받은 학생 학번에 대한 정보를 찾음
	*	@pre	아이템 타입이 초기화되어야한다.
	*	@post	전달받은 학생 정보를 찾으면 데이터에 값을 저장하고, 그렇지 않으면 값을 바꾸지 않는다.
	*	@param  데이터    찾고자하는 학생의 학번이 있는 아이템 타입의 데이터
	*	@return 찾았을 경우 1을, 못찾았을 경우 0을 리턴한다.
	*/
	int Get(ItemType& data);

	/** [작성]
	*	@brief 전달받은 학생 학번에 대한 정보를 삭제
	*	@pre   아이템 타입이 초기화되어야한다.
	*	@post  전달받은 학생 학번에 대한 정보를 지운다.
	*	@param 데이터    삭제하고자하는 학생의 학번이 있는 아이템 타입의 데이터
	*	@return 없음
	*/
	void Delete(ItemType data);

	/** [작성]
	*	@brief 전달받은 학생 학번에 대한 정보를 변경
	*	@pre   아이템 타입이 초기화되어야한다.
	*	@post  전달받은 학생 학번에 대한 정보를 변경한다.
	*	@param 데이터    변경하고자하는 학생의 학번이 있는 아이템 타입의 데이터
	*	@return 없음
	*/
	void Replace(ItemType data);

private:
	ItemType m_Array[MAXSIZE];  ///< list array.
	int m_Length;				///< number of elements in list.
	int m_CurPointer;			///< iterator pointer.
};

#endif	// _UNSORTEDLIST_H

 

2) ArrayList cpp

#include "ArrayList.h"


// Make list empty.
void ArrayList::MakeEmpty()
{
	m_Length = 0;
}


// Get a number of records in current list.
int ArrayList::GetLength()
{
	return m_Length;
}


// Check capacity of list is full.
bool ArrayList::IsFull()
{
	if(m_Length > MAXSIZE - 1)
		return true;
	else
		return false;
}


// add a new data into list.
int ArrayList::Add(ItemType inData)
{
	if(!IsFull())
	{
		m_Array[m_Length] = inData;
		m_Length++;
	}
	else
		return 0;

	return 1;
}


// Initialize list iterator.
void ArrayList::ResetList()
{
	m_CurPointer = -1;
}


// move list iterator to the next item in list and get that item.
int ArrayList::GetNextItem(ItemType& data)
{
	m_CurPointer++;	// list pointer 증가
	if(m_CurPointer == MAXSIZE)	// end of list이면 -1을 리턴
		return -1;
	data = m_Array[m_CurPointer];	// 현재 list pointer의 레코드를 복사

	return m_CurPointer;
}

int ArrayList::Get(ItemType& data) {
	int location = 0;
	bool found = false;
	while ((location < m_Length) && !found) {
		switch (data.CompareByID(m_Array[location])) {
		case LESS:
		case GREATER: location++;  break;
		case EQUAL:
			found = true;
			data = m_Array[location];
		}
	}
	return found?1:0;
}

void ArrayList::Delete(ItemType data) {
	int location = 0;
	while (location < m_Length && data.CompareByID(m_Array[location]) != EQUAL)
		location++;
	if (location < m_Length)
		m_Array[location] = m_Array[--m_Length];
}

void ArrayList::Replace(ItemType data) {
	int location = 0;
	while (location < m_Length && data.CompareByID(m_Array[location]) != EQUAL)
		location++;
	if (location < m_Length) 
		m_Array[location] = data;
}

- Unsorted list이기에 데이터 삽입 삭제 시 크게 고려해야할 부분은 없다.

- Array list로 구현했기에 컴파일 타임에 자료형의 크기를 전달받는다.

- ItemType의 CompareByID를 탐색에 활용해 데이터의 삽입, 삭제를 돕는다.

 

3. Application

1) Application h

#ifndef _APPLICATION_H
#define _APPLICATION_H

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

#include "ArrayList.h"

#define FILENAMESIZE 1024

/**
*	아이템을 관리하기위한 어플리케이션 클래스
*/
class Application
{
public:
	/**
	*	디폴트 생성자
	*/
	Application()
	{
		m_Command = 0;
	}
	
	/**
	*	소멸자
	*/
	~Application()	{}

	/**
	*	@brief	Program driver.
	*	@pre	program is started.
	*	@post	program is finished.
	*/
	void Run();

	/**
	*	@brief	Display command on screen and get a input from keyboard.
	*	@pre	none.
	*	@post	none.
	*	@return	user's command.
	*/
	int GetCommand();

	/**
	*	@brief	Add new record into list.
	*	@pre	list should be initialized.
	*	@post	new record is added into the list.
	*	@return	return 1 if this function works well, otherwise 0.
	*/
	int AddItem();

	/**
	*	@brief	Display all records in the list on screen.
	*	@pre	none.
	*	@post	none.
	*/
	void DisplayAllItem();

	/**
	*	@brief	Open a file by file descriptor as an input file.
	*	@pre	a file for reading is exist.
	*	@post	open the file for reading.
	*	@param	fileName	a filename to open for reading.
	*	@return	return 1 if this function works well, otherwise 0.
	*/
	int OpenInFile(char *fileName);

	/**
	*	@brief	Open a file by file descriptor as an output file.
	*	@pre	list should be initialized.
	*	@post	open the file for writing.
	*	@param	fileName	a filename to open for writing.
	*	@return	return 1 if this function works well, otherwise 0.
	*/
	int OpenOutFile(char *fileName);

	/**
	*	@brief	Open a file as a read mode, read all data on the file, and set list by the data.
	*	@pre	The file is not opened.
	*	@post	list holds all records from the file.
	*	@return	return 1 if this function works well, otherwise 0.
	*/
	int ReadDataFromFile();

	/**
	*	@brief	Open a file as a write mode, and write all data into the file,
	*	@pre	The file is not opened.
	*	@post	the list is stored in the output file.
	*	@return	return 1 if this function works well, otherwise 0.
	*/
	int WriteDataToFile();

	/** [작성]
	*	@brief  주어진 학생 학번을 토대로 리스트에 저장되었는지 확인하여 출력
	*	@pre    리스트가 초기화되어있어야함
	*	@post   학생을 찾으면 학생 정보를 출력하고, 학생을 찾지 못하면 학생을 찾지 못했다는 문구를 출력한다.
	*	@return 학생을 찾았을 경우 1을 리턴하고, 학생을 찾지 못하면 0을 리턴한다.
	*/
	int SearchData();

	/** [작성]
	*	@brief  주어진 학생 학번을 토대로 리스트에 저장된 학생 정보를 삭제
	*	@pre    리스트가 초기화되어있어야함
	*	@post   학생을 찾으면 학생 정보를 삭제하고, 학생을 찾지 못하면 리스트를 그대로 놔둔다.
	*	@return 학생 정보를 삭제했을 경우 1을 리턴하고, 학생 정보를 삭제하지 못하면 0을 리턴한다.
	*/
	int DeleteItem();

	/** [작성]
	*	@brief	주어진 학생 학번을 토대로 리스트에 저장된 학생 정보를 변경
	*	@pre    리스트가 초기화되어있어야함
	*	@post	학생을 찾으면 학생 정보를 변경하고, 학생을 찾지 못하면 리스트를 그대로 놔둔다.
	*	@return	학생 정보를 변경했을 경우 1을 리턴하고, 학생 정보를 변경하지 못하면 0을 리턴한다.
	*/
	int UpdateItem();

	
private:
	ifstream m_InFile;		///< input file descriptor.
	ofstream m_OutFile;		///< output file descriptor.
	ArrayList m_List;		///< item list.
	int m_Command;			///< current command number.
};

#endif	// _APPLICATION_H

 

2) Application cpp

#include "Application.h"


// Program driver.
void Application::Run()
{
	while(1)
	{
		m_Command = GetCommand();

		switch(m_Command)
		{
		case 1:		// read a record and add to list.
			AddItem();
			break;
		case 2:		// display all the records in list on screen.
			DisplayAllItem();
			break;
		case 3:		// make empty list.
			m_List.MakeEmpty();
			break;
		case 4:		// [작성] search item from list.
			SearchData();
			break;
		case 5:		// [작성] delete item from list
			DeleteItem();
			break;
		case 6:		// [작성] update item in list
			UpdateItem();
			break;
		case 7:		// load list data from a file.
			ReadDataFromFile();
			break;
		case 8:		// save list data into a file.
			WriteDataToFile();
			break;
		case 0:
			return;
		default:
			cout << "\tIllegal selection...\n";
			break;
		}
	}
}


// Display command on screen and get a input from keyboard.
int Application::GetCommand()
{
	int command;
	cout << endl << endl;
	cout << "\t---ID -- Command ----- " << endl;
	cout << "\t   1 : Add new item" << endl;
	cout << "\t   2 : Print all on screen" << endl;
	cout << "\t   3 : Make empty list" << endl;
	cout << "\t   4 : Search item" << endl;
	cout << "\t   5 : Delete item" << endl;
	cout << "\t   6 : Update item" << endl;
	cout << "\t   7 : Get from file" << endl; 
	cout << "\t   8 : Put to file " << endl; 
	cout << "\t   0 : Quit" << endl; 

	cout << endl << "\t Choose a Command--> ";
	cin >> command;
	cout << endl;

	return command;
}


// Add new record into list.
int Application::AddItem()
{
	// [작성] 입력받은 레코드를 리스트에 add, 리스트가 full일 경우는 add하지 않고 0을 리턴
	ItemType data;
	data.SetRecordFromKB();
	int isAdd = m_List.Add(data);
	if (!isAdd) return 0;

	// [작성] 현재 list 출력
	DisplayAllItem();
	return 1;
}


// Display all records in the list on screen.
void Application::DisplayAllItem()
{
	ItemType data;

	cout << "\n\tCurrent list" << endl;


	// [작성] list의 모든 데이터를 화면에 출력
	m_List.ResetList();
	int location = m_List.GetNextItem(data);
	while (location != -1 && location < m_List.GetLength()) {
		data.DisplayRecordOnScreen();
		cout << '\n';
		location = m_List.GetNextItem(data);
	}
	
}


// Open a file by file descriptor as an input file.
int Application::OpenInFile(char *fileName)
{
	m_InFile.open(fileName);	// file open for reading.
	
	// [작성] 파일 오픈에 성공하면 1, 그렇지 않다면 0을 리턴.
	return m_InFile.is_open();
}


// Open a file by file descriptor as an output file.
int Application::OpenOutFile(char *fileName)
{
	m_OutFile.open(fileName);	// file open for writing.

	// [작성] 파일 오픈에 성공하면 1, 그렇지 않다면 0을 리턴.
	return m_OutFile.is_open();
}


// Open a file as a read mode, read all data on the file, and set list by the data.
int Application::ReadDataFromFile()
{
	int index = 0;
	ItemType data;	// 읽기용 임시 변수
	
	char filename[FILENAMESIZE];
	cout << "\n\tEnter Input file Name : ";
	cin >> filename;

	// [작성] file open, open error가 발생하면 0을 리턴
	if (!OpenInFile(filename)) return 0;

	// [작성] 파일의 모든 내용을 읽어 list에 추가
	m_List.MakeEmpty();
	while (!m_InFile.eof()) {
		data.ReadDataFromFile(m_InFile);
		if (data.GetId() != -1) m_List.Add(data);
	}
	
	m_InFile.close();	// file close

	// [작성] 현재 list 출력
	DisplayAllItem();

	return 1;
}


// Open a file as a write mode, and write all data into the file,
int Application::WriteDataToFile()
{
	ItemType data;	// 쓰기용 임시 변수

	char filename[FILENAMESIZE];
	cout << "\n\tEnter Output file Name : ";
	cin >> filename;

	// [작성] file open, open error가 발생하면 0을 리턴
	if (!OpenOutFile(filename)) return 0;

	// [작성] list 포인터를 초기화
	m_List.ResetList();

	// [작성] list의 모든 데이터를 파일에 쓰기
	int location = m_List.GetNextItem(data);
	while (location != -1 && location < m_List.GetLength()) {
		data.WriteDataToFile(m_OutFile);
		location = m_List.GetNextItem(data);
	}

	m_OutFile.close();	// file close

	return 1;
}


int Application::SearchData() {
	int inId;
	ItemType data;
	cout << "찾고자 하는 학생 학번을 입력하세요.";
	cin >> inId;
	data.SetId(inId);
	if (!m_List.Get(data)) {
		cout << "주어진 학생 정보가 없습니다." << endl;
		return 0;
	}

	data.DisplayRecordOnScreen();
	return 1;
}


int Application::DeleteItem() {
	int inId;
	ItemType data;
	cout << "삭제하고자 하는 학생 학번을 입력하세요.";
	cin >> inId;
	data.SetId(inId);
	if (!m_List.Get(data)) return 0;
	m_List.Delete(data);
	return 1;
}


int Application::UpdateItem() {
	ItemType data;
	data.SetRecordFromKB();
	m_List.Replace(data);
	return m_List.Get(data);
}

- run을 통해 어플리케이션을 실행한다.

- 사용자로부터 숫자를 입력받아 원하는 기능을 동작하도록 한다.

- 자료형에 값을 저장하여 데이터 추가, 삭제, 파일 입출력 등의 기능을 수행할 수 있다.