Новосибирский государственный технический университет
Кафедра вычислительной техники
 |
Лабораторная работа №1
по дисциплине «Структуры и алгоритмы обработки данных»
«Линейные коллекции данных»
Вариант: 5
Группа: АМ-016
Бригада:
Студенты:
Преподаватель:
Романенко
Новосибирск 2002
Цель работы: Реализация типовых коллекций данных в виде Абстрактных Типов Данных (АТД) на языке высокого уровня С++. Оценка и анализ эффективности алгоритмов реализации АТД. Формирование библиотеки разработанных АТД.
Задание: Спроектировать, реализовать и провести тестовые испытания АТД для линейной коллекции «Список» и её модификации. Список базируется на структуре данных «Надежный массив», модификация АТД «Циклическая очередь».
АТД – формат.
АТД Massiv
Данные:
Указатель на память, выделенную под массив, положительное целое число, которое указывает на минимальную (начальную) память, выделенную под массив, положительное целое число, которое указывает на размерность памяти при её расширении и уменьшение, положительное целое число, которое указывает на текущее количество памяти занятой списком (количество элементов в списке), а также имеются 3 переменные счётчики для подсчёта производительности 3-х операций.
Операции:
Конструктор:
Начальные значения: размер минимальной памяти выделяемой под массив (по умолчанию размер минимальной памяти равен 50).
Процесс: установление размера списка в 0, выделение памяти под массив начальной (минимальной) размерности.
ListSize:
Вход:
нет.
Предусловие:
нет.
Процесс:
чтение размерности списка.
Выход:
размерность списка.
Постусловие:
нет.
ListEmpty:
Вход:
нет.
Предусловие:
нет.
Процесс:
чтение размерности списка и проверка равенства её на 0.
Выход:
если размерность списка равна 0, то вернуть 1, иначе вернуть 0.
Постусловие:
нет.
Find:
Вход:
значение, которое ищется в списке.
Предусловие:
нет.
Процесс:
перебираются элементы списка, пока не встретится элемент равный по значению тому, который ищется или пока не дойдём до конца списка и увеличение счетчика при переходе каждому следующему элементу.
Выход:
если нашелся элемент, который мы искали, то вернуть 1, иначе вернуть 0.
Постусловие:
нет.
GetData:
Вход:
позиция получаемого элемента.
Предусловие:
значение позиции не больше количества элементов в списке.
Процесс:
нет.
Выход:
если значение позиции больше количества элементов в списке, то выбросить исключение, иначе вернуть значение элемента в массиве с заданной позицией.
Постусловие:
нет.
GetPos:
Вход:
значение, позиция которого ищется.
Предусловие:
нет.
Процесс:
последовательно перебирается весь список, пока не встретится элемент по значению равный искомому или пока не дойдем до конца списка.
Выход:
если список пуст или мы пробежали по всему списку и не нашли искомый элемент, то вернуть –1, иначе вернуть позицию найденного элемента в списке.
Постусловие:
нет.
ClearList:
Вход:
нет.
Предусловие:
нет.
Процесс:
обнуляется количество элементов в списке уменьшается память, выделенная под массив до минимальной.
Выход:
нет.
Постусловие:
уменьшается память, выделенная под массив.
Insert:
Вход:
позиция, в которую помещается элемент и помещаемый элемент.
Предусловие:
позиция включаемого элемента не должна превышать количество элементов в списке.
Процесс:
если количество элементов списка равно размеру выделенной памяти, то производится увеличение размерности массива, а затем раздвижка элементов и вставка в освобождённое место, при раздвижке увеличивается количество перестановок.
Выход:
нет.
Постусловие:
если позиция включаемого элемента больше количества элементов в списке, то выбрасывается исключение, при отсутствии свободного места в массиве производится увеличение памяти выделяемой под массив.
Delete
Вход:
позиция, с которой надо удалить.
Предусловие:
позиция удаляемого элемента не должна превышать количество элементов в списке.
Процесс:
производится сдвижка элементов списка с конца, если количество выделенной памяти, возможно, уменьшить на минимально допустимую память, то она уменьшается, а также при перестановке элементов производится увеличение счётчика.
Выход:
нет.
Постусловие:
при возможности уменьшения памяти она уменьшается, если позиция исключаемого элемента больше количества элементов в списке, то выбрасывается исключение.
operator[]
Вход:
индекс.
Предусловие:
значение индекса не должно превышать количества элементов в списке.
Процесс:
нет.
Выход:
значение элемента в данной позиции.
Постусловие:
если индекс больше размера списка, то выбрасывается исключение.
ReInputSize:
Вход:
размерность новой памяти.
Предусловие:
размерность выделяемой памяти не должна быть меньше минимальной размерности памяти.
Процесс:
Выделяется новая память, туда переписывается содержимое старой памяти, а затем старая память удаляется.
Выход:
нет.
Постусловие:
если размер новой памяти меньше минимальной, то не производится никаких действий.
RezultTesting:
Вход:
по ссылке три переменные типа long.
Предусловие:
нет.
Процесс:
в эти переменные записывается значения счётчиков, а затем счётчики обнуляются.
Выход:
нет.
Постусловие:
нет.
operator<<:
Вход:
ссылка на объект класса ostream и ссылка на выводимый список.
Предусловие:
нет.
Процесс:
пробегаем по списку и загоняем в поток значения элементов списка.
Выход:
Ссылка на объект класса ostream.
Постусловие:
нет.
~Massiv:
Вход:
нет.
Предусловие:
нет.
Процесс:
освобождаем память, выделенную под массив.
Выход:
нет.
Постусловие:
нет.
Описание иерархии классов: Шаблонный класс Циклическая очередь (template<class T> class Lifo<T>) наследует от шаблонного класса надёжный массив (template<class T> class Massiv<T>).
Определение классов на языке программирования С++ с комментариями о назначение данных и методов:
Описание класса «надежный массив»:
template<class T>
class Massiv
{
protected:
T* Pointer;//Указатель на память выделеную под массив.
int Size0;//Размер минимальной памяти.
int Size;//Размерность массива.
int SizeList;//Размер списка.
long InsertCX;//СЧЁТЧИКИ.
long DeleteCX;
long FindCX;
public:
Massiv(int=50);//Конструктор.
Massiv(Massiv&);//Конструктор копирования.
int ListSize();// Опрос размера списка.
BOOL ListEmpty();//Проверка пустого списка.
BOOL Find(T);//Опрос наличия элемента в списке.
T GetData(int);//Получения элемента в заданной позиции.
int GetPos(T&);//Получение позиции для заданного значения.
void ClearList();//Очистка списка.
void Insert(int, T);//Вставка по заданной позиции.
void Delete(int);//Удаление по заданной позиции.
void ReInputSize(int);//Изменение размера.
T& operator[](int);//Переопределение операции индексирование.
void RezultTesting(long&,long&,long&);//Метод обнуления счётчиков.
friend ostream& operator<<(ostream&,Massiv<T>&);//Перопределение вывода.
~Massiv();//Деструктор.
};
Описание класса «циклическая очередь»:
template<class T>
class Lifo : public Massiv<T>
{
T* first;//Первый в очереди.
T* last;//Последний в очереди.
public:
Lifo(int=50);//Конструктор.
Lifo(Lifo<T>&);//Конструктор копирования.
int ListSize();//Опрос размера очереди.
BOOL ListEmpty();//Проверка на пустоту.
BOOL Find(T);//Запрещение метода базового класса.
T GetData(int);//Запрещение метода базового класса.
int GetPos(T&);//Запрещение метода базового класса.
void Insert(T);//Поместить в очередь.
T Delete();//Вытолктнуть из очереди.
void ReInputSize(int);//Перераспределение памяти выделенной под очередь
void ClearList();//Очистка очереди.
T& operator[](int);//Запрещение метода базового класса.
friend ostream& operator<<(ostream&,Lifo<T>&);//Переопределение операции вывода.
};
Реализация методов классов на языке программирования С++:
Описание методов класса «надёжный массив»:
template<class T>
Massiv<T>::Massiv(int size)
{
Pointer=new T[size];
Size=Size0=size;
SizeList=0;
InsertCX=0;
DeleteCX=0;
FindCX=0;
}
template<class T>
Massiv<T>::Massiv(Massiv& data)
{
delete []Pointer;
Pointer=new T[data. Size];
int i=0;
while(i!=Size)
Pointer[i]=data. Pointer[i++];
Size=data. Size;
}
template<class T>
int Massiv<T>::ListSize()
{
return SizeList;
}
template<class T>
BOOL Massiv<T>::ListEmpty()
{
if(SizeList==0)
return 1;
return 0;
}
template<class T>
BOOL Massiv<T>::Find(T a)
{
int i=0;
while(i<SizeList)
{
FindCX++;
if(Pointer[i]==a)
return 1;
i++;
}
return 0;
}
template<class T>
void Massiv<T>::ClearList()
{
SizeList=0;
ReInputSize(Size0);
}
template<class T>
int Massiv<T>::GetPos(T&a)
{
if(SizeList==0)
return -1;
int i=0;
while(i<SizeList)
if(Pointer[i]==a)
return i;
else
i++;
return -1;
}
template<class T>
T Massiv<T>::GetData(int pos)
{
if(pos>ListSize)
throw "Нет столько элементов";
return Pointer[pos];
}
template<class T>
void Massiv<T>::Insert(int pos, T val)
{
if(pos<0)
throw "Позиция отрицательная!!!";
if(pos>SizeList+1)
throw "Немогу включить на заданую позицию!!!";
if(SizeList==Size)
ReInputSize(Size+Size0);
int i=SizeList;
while(i!=pos)
{Pointer[i]=Pointer[i-1];i--;InsertCX++;}
Pointer[pos]=val;
SizeList++;
}
template<class T>
void Massiv<T>::Delete(int pos)
{
if(pos<0)
throw "Позиция отрицательная!!!";
if(SizeList<pos)
throw "Нет такого элемента!!!";
int i=pos;
while(i<SizeList)
{Pointer[i]=Pointer[i+1],i++;DeleteCX++;}
if(SizeList!=0)
SizeList--;
if(SizeList+Size0==Size&&Size-Size0>=Size0)
ReInputSize(Size-Size0);
}
template<class T>
void Massiv<T>::ReInputSize(int size)
{
if(size<Size0)
return;
T *p=new T[size];
int i=0;
while(i<SizeList)
p[i]=Pointer[i++];
delete []Pointer;
Pointer=p;
Size=size;
}
template<class T>
T& Massiv<T>::operator[](int index)
{
if(index>SizeList||index<0)
throw"Не могу взять этот элемент";
return Pointer[index];
}
template<class T>
Massiv<T>::~Massiv()
{
delete []Pointer;
}
template<class T>
void Massiv<T>::RezultTesting(long& a, long& b, long& c)
{
a=InsertCX,
b=DeleteCX,
c=FindCX;
InsertCX=DeleteCX=FindCX=0;
}
template<class T>
ostream& operator<<(ostream&s, Massiv<T> &data)
{
int i=0;
while(i<data. ListSize())
{
s<<data. Pointer[i];
i++;
if(i!=data. SizeList)
s<<',';
}
s<<endl;
return s;
}
Описание методов класса «циклическая очередь»:
template<class T>
Lifo<T>::Lifo(int size):Massiv<T>(size)
{
first=NULL;
last=NULL;//Очередь пуста.
}
template<class T>
BOOL Lifo<T>::ListEmpty()
{
if(first==NULL)
return 1;
return 0;
}
template<class T>
int Lifo<T>::ListSize()
{
char bufer[200];
CharToOem("Память под очередь : ",bufer);
cout<<bufer<<Size<<endl;
if(first==last)
return 0;
if(first<last)
return last-first;
else
{
int a=Size-(first-Pointer);
int b=last-Pointer;
return a+b;
}
}
template<class T>
void Lifo<T>::Insert(T val)
{
if(first==last && first==NULL)
{
if(Size==1)
ReInputSize(Size+Size0);
else
{first=Pointer;last=Pointer+1;}
*first=val;
return;
}
if(first==Pointer && abs(last-Pointer)==Size-1)
{
ReInputSize(Size+Size0);
*last=val;
last++;
return;
}
if(last+1==first)
{
ReInputSize(Size+Size0);
*last=val;
last++;
return;
}
*last=val;
if(last-Pointer==Size-1)
last=Pointer;
else
last++;
}
template<class T>
T Lifo<T>::Delete()
{
T val;
if(first==NULL)
throw "Очередь пуста!!!";
if(first+1==last||(last==Pointer&&first-Pointer==Size-1))
{
val=*first;
first=last=NULL;
return val;
}
val=*first;
if(first-Pointer==Size-1)
first=Pointer;
else
first++;
if(Size-Size0>ListSize()&&Size-Size0>=Size0)
ReInputSize(Size-Size0);
return val;
}
template<class T>
void Lifo<T>::ReInputSize(int size)
{
if(size<Size&&size<Size0)
{
delete []Pointer;
Pointer=new T[size];
Size=size;
return;
}
if(size<Size0)
return;
T *p;
p=new T[size];
int i=0;
if(!ListEmpty())
{
while(first!=last&&first-Pointer!=Size)
p[i++]=*(first)++;
if(first!=last)
first=Pointer;
if(first!=last)
while(first!=last)
p[i++]=*(first)++;
}
if(i==0) i++;
delete []Pointer;
Size=size;
Pointer=p;
first=Pointer;
last=&p[i];
}
template<class T>
void Lifo<T>::ClearList()
{
if(Size>Size0)
{
delete []Pointer;
Pointer=new T[Size0];
Size=Size0;
}
first=last=NULL;
}
template<class T>
BOOL Lifo<T>::Find(T a)
{
return 0;
}
template<class T>
int Lifo<T>::GetPos(T&a)
{
return -1;
}
template<class T>
T Lifo<T>::GetData(int pos)
{
throw "Нельзя меня вызывать";
}
template<class T>
T& Lifo<T>::operator[](int index)
{
throw"Не могу это делать для очереди!!!";
}
template<class T>
ostream &operator<<(ostream& s, Lifo<T>& data)
{
char bufer[200];
if(data. last==NULL)
{
CharToOem("Очередь пуста!!!",bufer);
s<<bufer<<endl;
return s;
}
CharToOem("Содержимоё очереди: ",bufer);
s<<bufer;
T *p;
int k=1;
p=data. first;
while(p!=data. first-1&&p!=data. last)
{
s<<*p;
if(abs(p-data. Pointer)==data. Size-1)
p=data. Pointer;
else
p++;
if(p!=data. first-1&&p!=data. last)
s<<',';
}
s<<endl;
return s;
}
График для усреднённой производительности операций вставка, удаление, поиск:
Таблица.
N | Вставка | Удаление | Поиск |
100 | 41 | 42 | 57 |
200 | 92 | 97 | 126 |
300 | 138 | 142 | 186 |
400 | 185 | 196 | 250 |
500 | 244 | 239 | 317 |
600 | 283 | 285 | 371 |
700 | 346 | 366 | 454 |
800 | 390 | 394 | 529 |
900 | 429 | 454 | 600 |
Сравнительный анализ: Теоретически зависимости для списков линейны, на графиках мы наблюдаем практически линейную зависимость. Т. е. подтверждаем теоретическую зависимость.
Вывод: практически мы получили линейную зависимость, но с небольшой погрешностью, которая обусловлена «промахами».
Список литературы: литература не использовалась.
