awe的程設筆記

List ADT:

List.h

#ifndef LIST_H
#define LIST_H

template <typename E>
class List
{
private:
void operator = (const List&){}
List(const List&){}
public:
List(){}
virtual ~List(){}

//clear all the content of the List
virtual void clear() = 0;

//Insert an element to list at current location
//item : element to be insert
virtual void insert(const E& item) = 0;

//Append an element to the end of list
//item : element to be append
virtual void append(const E& item) = 0;

//Remove and return current element
//Retrun: element which removed
virtual E remove() = 0;

//Set the current element to the start of list
virtual void moveToStart() = 0;

//Move to end of the list
virtual void moveToEnd() = 0;

//Move to current position one step left
//and no change if at begin
virtual void prev() = 0;

//Move to current position one step right
//and no change if at end
virtual void next() = 0;

//Return : the number of elements in list
virtual int length() const = 0;

//Return : current position of the current element
virtual int currPos() const = 0;

//Set current position
//pos: The position to make current
virtual void moveToPos(int pos) = 0;

//Return : the current element
virtual const E& getValue() const = 0;
};

#endif

Array List 實作介面

AList.h

#include"List.h"
#include<iostream>

using namespace std;
const int defaultSize = 10;

template <typename E>
class AList : public List<E>
{
private:

int maxSize;
int listSize;
int curr;
E* listArray;

public:
AList( int size = defaultSize)
{
maxSize = size;
listSize = 0;
curr = 0;
listArray = new E[maxSize];
}

~AList()
{
delete [] listArray;
}

void clear()
{
delete [] listArray;
listSize = curr = 0;
listArray = new E[maxSize = defaultSize];
}

void insert(const E& it )
{
if(listSize == maxSize)
{
E* tempArray = new E [maxSize *2];
for(int i = 0 ; i < maxSize ; i++)
{
tempArray[i] = listArray[i];
}
delete [] listArray;
listArray = tempArray;
maxSize *= 2;
}
for(int i = listSize ; i > curr ; i--)
{
listArray[i] = listArray[i-1];
}

listArray[curr] = it;
listSize++;
}

void append(const E& it)
{
if(listSize == maxSize)
{
E* tempArray = new E [maxSize *2];
for(int i = 0 ; i < maxSize ; i++)
{
tempArray[i] = listArray[i];
}
delete [] listArray;
listArray = tempArray;
maxSize *= 2;
}
listArray[listSize++] = it;
}

E remove()
{
if(length() == 0 ) cerr<<"List is empty"<<endl;

E it = listArray[curr];
for(int i = curr ;i < listSize-1 ;i++)
{
listArray[i] = listArray[i+1];
}
listSize -- ;
return it;
}

void moveToStart()
{
curr = 0;
}

void moveToEnd()
{
curr = listSize ;
}

void prev()
{
if(curr != 0) curr = curr--;
}

void next()
{
if(curr < listSize) curr++;
}

int length() const
{
return listSize;
}

int currPos() const
{
return curr;
}

void moveToPos( int pos)
{
if(pos >= 0 && pos < listSize) curr = pos;
}

const E& getValue()const
{
return listArray[curr];
}

};