자료구조 구현 (2), Sorted list

Sorted list 구현

 

C++을 통해서 Sorted list를 구현했다. Unsorted list와 마찬가지로 ItemType, Sorted list, Application을 세 파트로 나누어 코드를 구현했다. ItemType과 Application은 Unsorted list와 크게 다른 부분이 없기에 이는 이전 포스팅을 참고하면 좋을 것 같다.

2022.05.11 - [강의 내용 정리/자료구조] - 자료구조 구현 (1), Unsorted list

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

 

 

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

 

1. ArrayList(Sorted 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	item을 찾아서 해당 item을 반환한다.
	*	@pre	인수 data에 있는 id가 list 내에 존재하는 값이어야 한다.
	*	@post	list 내에서 찾은 item이 data에 입력된다.
	*	@param	data	찾고자 하는 id가 입력된 ItemType값. 발견한 item이 리턴된다.
	*	@return	성공(발견)시 1, 실패시 0을 리턴한다.
	*/
	int Get(ItemType& data);

	/**
	*	@brief	id가 일치하는 item을 찾아서 해당 item을 제거한다.
	*	@pre	인수 data에 있는 id가 list 내에 존재하는 값이어야 한다.
	*	@post	list 내에 해당 item이 제거된다.
	*	@param	data	제거하고자 하는 id가 입력된 ItemType값. 
	*	@return	성공시 1, 실패시 0을 리턴한다.
	*/
	int Delete(ItemType data);

	/**
	*	@brief	id가 일치하는 list내 item을 찾아서 변경한다.
	*	@pre	인수 data에 있는 id가 list 내에 존재하는 값이어야 한다.
	*	@post	배열 내에 넘겨받은 item과 id가 일치하는 값이 넘겨받은 item의 내용으로 변경된다.
	*	@param	data	교체하고자 하는 id와 레코드를 가진 ItemType값.
	*	@return	성공시 1, 실패시 0을 리턴한다.
	*/
	int Replace(ItemType data);

	/**
	*	@brief	이진탐색을 통해 id가 일치하는 list내 item을 찾아서 반환한다.
	*	@pre	없음.
	*	@post	배열 내에 넘겨받은 item과 id가 일치하는 값을 찾아서 data로 반환된다.
	*	@param	data	찾고자 하는 id가 입력된 ItemType값.
	*	@return	성공(발견)시 1, 실패시 0을 리턴한다.
	*/
	int GetBinarySearch(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())
	{
		ResetList();
		ItemType dummy = inData;
		GetBinarySearch(dummy);
		for (int i = m_Length++; i > m_CurPointer+1; i--) {
			m_Array[i] = m_Array[i - 1];
		}
		m_Array[m_CurPointer+1] = inData;
		return 1;
	}
	return 0;
}


// 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];
			m_CurPointer = location;
		}
	}
	return found?1:0;
}

int ArrayList::Delete(ItemType data) {
	if (GetBinarySearch(data)) {
		for (int i = m_CurPointer; i < m_Length-1; i++) {
			m_Array[i] = m_Array[i + 1];
		}
		m_Length--;
		return 1;
	}
	return 0;
}

int ArrayList::Replace(ItemType data) {
	ItemType dummy = data;
	if (GetBinarySearch(dummy)) {
		m_Array[m_CurPointer] = data;
		return 1;
	}
	return 0;
}

int ArrayList::GetBinarySearch(ItemType& data) {
	int start = 0, end = m_Length-1;
	bool found = false;
	ResetList();
	while (start <= end && !found) {
		int mid = (start + end) / 2;
		switch (data.CompareByID(m_Array[mid])) {
		case LESS: 
			end--; 
			m_CurPointer = m_CurPointer > mid ? mid : m_CurPointer;
			break;
		case GREATER: 
			start++; 
			m_CurPointer = m_CurPointer < mid ? mid : m_CurPointer;
			break;
		case EQUAL:
			found = true;
			data = m_Array[mid];
			m_CurPointer = mid;
		}
	}
	return found ? 1 : 0;
}

- Sorted list이지만 이를 array list로 구현했기에 데이터 삽입, 삭제 시에 유의해야한다. 특히 데이터를 삽입할 때마다 GetBinarySearch를 사용해 m_CurPointer를 찾고, 이에 맞춰 데이터를 뒤로 하나씩 옮겨주었다. 따라서 오버헤드가 있을 수 밖에 없지만 이는 array list로 sorted list를 구현했기 때문에 어쩔 수 없다.

- Sorted list이기에 내부 자료를 검색하거나 삽입, 삭제할 때는 이진탐색을 사용했다. 실습에서 요구한 사항은 아니지만 효율성을 고려해 이와 같이 코드를 작성했다. 

- 자료의 대소관계는 enum 타입을 사용해 swich문으로 case를 분리했다.