[자료구조] [샤니]3장 연습문제 풀이

소개글

샤니의 자료구조론 연습문제풀이입니다.

목차

없음

본문내용

14. Suppose that we are to represent a linear list the formula

location(i)=(location(1)+i-1) % MaxSize

where MaxSize is the size of the array in which the elements are stored. Rather than storing the list size explicitly, we keep variables first and last that give the locations of the first and last elements of the list.

(a) Develop a class similar to LinearList for this representation.

template<class T>
class LinearList {
public:
LinearList(int MaxListSize = 10); // constructor
~LinearList() {delete [] element;} // destructor
bool IsEmpty() const {return first == -1;}

int Length() const // Length 함수를 정의함으로써 length 변수의 역할을 대신한다.
{if (first == -1) return 0;
else return (MaxSize+last-first) % MaxSize + 1;}

bool Find(int k, T& x) const;
// return the k'th element of list in x
int Search(const T& x) const;
// return position of x
LinearList<T>& Delete(int k, T& x);
// delete k'th element and return in x
LinearList<T>& Insert(int k, const T& x);
// insert x just after k'th element
void Output(ostream& out) const;

private:
int first; // location of first element
int last; // location of last element
int MaxSize;
T *element; // dynamic 1D array
};

참고 자료

샤니의 자료구조론 3장 연습문제 풀이입니다.