Новосибирский государственный технический университет
Кафедра вычислительной техники
 |
Лабораторная работа №1
по дисциплине «Структуры и Алгоритмы»
Вариант: 2 Преподаватель:
Группа: АМ-210
Студенты:
Новосибирск, 2004
1. Техническое задание.
Освоение технологии реализации позиционных, линейных коллекций на примере АТД «Список». Освоение методики тестирования трудоёмкости операций коллекций.
Задание:
Вар №2: Структура данных - надёжный массив.
2. Описание программы.
Шаблон массива:
В slist. h содержатся класс slist – список,
В iterator.h содержатся класс iterator который позволяет ходить по списку.
В MyEcx.h содержит класс MyExc – для обработки исключений.
3. Формат АТД.
slist. h:
АТД «НАДЁЖНЫЙ МАССИВ»
Массив элементов указанного типа Т с переменной размерностью. При создании массив имеет исходный размер size0. Массив может изменять свой размер. Операция индексирования массива выполняет проверку соответствия индекса текущему размеру массива size.
ДАННЫЕ:
Параметры:
Исходный размер массива size0
Количество элементов в списке cur_el
Текущий размер массива size
Структура данных:
Динамический массив элементов указанного типа Т – T array[size]
ОПЕРАЦИИ:
Конструктор:
Вход: исходный размер массива size0
Начальные значения: исходный размер массива size = size0
Процесс: выделение памяти с указанным размером size0
Постусловия: Создан массив с размером size = size0
Опрос размера массива:
Вход: нет
Предусловия: нет
Процесс: чтение текущего размера size
Выход: текущий размер size
Постусловия: нет
Тукущий размер
Вход: нет
Предусловия: cur_el≠0
Процесс: нет
Выход: текущий размер
Постусловия: нет
Очистка списка:
Вход: нет
Предусловия: нет
Процесс: очищаем список
Выход: нет
Постусловия: нет
Получение позиции в списке элемента с заданным значением:
Вход: значение, которое надо найти key
Предусловия: проверка на пустоту
Процесс: просматриваем весь список на наличие заданного элемента
Выход: возвращаем индекс найденного значения
Постусловия: генерация ошибки если не нашли заданный элемент
Опрос наличия элемента с заданным значением:
Вход: значение, которое надо найти key
Предусловия: проверка на пустоту
Процесс: просматриваем весь список на наличие заданного элемента
Выход: возвращаем FALSE, если не нашли элемент, TRUE если нашли
Постусловия: нет
Операция индексирования
Вход: значение индекса i
Предусловия: 0
i size-1
Процесс: вычисление адреса элемента массива array[i]
Выход: ссылка на элемент массива array[i]
Постусловия: генерация сообщения об ошибке при невыполнении предусловия
Изменение размера массива
Вход: новый размер массива sizen
Предусловия: sizen 
0,
Процесс: выделение памяти указанного размера sizen, копирование size или sizen значений из старого массива в новый массив
Выход: нет
Постусловия:
массив содержит size значений старого массива, если sizen> size,
массив содержит sizen значений старого массива, если sizen< size,
текущий размер массива size = sizen
Вставка элемента в массив по индексу:
Вход: Новый элемент, индекс вставки
Предусловия: Неверный индекс
Процесс: Если список пуст вставляем в начало.
Если вставка идет в середину, то раздвигаем массив в том месте куда надо вставлять и вставляем.
Выход: нет
Постусловия: Если количество элементов списка равно количеству элементов массива, то увеличиваем размерность массива на size0.
Удаление элемента списка по индексу:
Вход: индекс удаляемого элемента
Предусловия: Проверка на пустоту. Проверка на корректность индекса.
Процесс: Запоминаем удаленный элемент. Производим сдвижку списка с затиранием удаленного элемента.
Выход: Удаленный элемент
Постусловия: Если количество элементов списка меньше массива в 2 раза, то создаем новый массив размерностью size/2+size0
Распечатка списка:
Вход: Список
Предусловия: проверка на пустоту
Процесс: Выводим список на экран с разными характеристиками
Выход: нет
Постусловия: нет
КОНЕЦ АТД
Iterator.h:
АТД «Итератор»
Позволяет иметь последовательный доступ к элементам списка.
ДАННЫЕ:
Параметры:
Логический номер элемента ln
Ключ key
Структура данных:
Ссылка на список Slist<T> &l
ОПЕРАЦИИ:
Конструктор:
Вход: Указатели на список
Начальные значения: ln=0; key=0;
Процесс: нет
Переход к следующему элементу списка:
Вход: нет
Предусловия: проверка на пустоту
Процесс: Выводим на экран элемент списка
Выход: Возвращаем указатель
Постусловия: нет
Переход к предыдущему элементу списка:
Вход: нет
Предусловия: проверка на пустоту
Процесс: Выводим на экран элемент списка
Выход: Возвращаем указатель
Постусловия: нет
Переход к началу списка:
Вход: нет
Предусловия: проверка на пустоту
Процесс: Выводим на экран 1-ый элемент списка
Выход: нет
Постусловия: нет
Переход к концу списка:
Вход: нет
Предусловия: проверка на пустоту
Процесс: Выводим на экран последний элемент списка
Выход: нет
Постусловия: нет
КОНЕЦ АТД
4. Описание пользовательского интерфейса.
В программе имеется удобное меню для пользователя и для лучшего представления операций класса.
Print_List – просмотр списка,
Insert –добавить элемент по логическому номеру;
Insert N elements – добавление N элементов в список
Find value – найти элемент в списке
Element with given index – найти элемент в списке по индексу
Removing an Element with given index – удаление элемента по индексу
Is_empty – проверка списка на пустоту
Test – тестирование общей трудоёмкости
Clear – Очистка списка
Iterator - имеет следующие варианты:
а) Iterator_next – переход к следующему элементу списка;
б) Iterator_pred – переход к предыдущему элементу списка;
в) First – переход к началу списка;
г) Last – переход к концу списка;
Exit – выход.
Statistic – Статистика трудоемкости при вставке , удаление, просмотре
5. Описание методики тестирования трудоёмкости операций
Тестирование производилось 4-х операций: вставки N элементов, вставки одного, удаления и нахождения элемента списка.
Это производится очень просто, например при вставке N элементов подсчитывалось число раздвижек и вставок. При удаление – число сдвижек и удалений. При нахождение элемента списка - число просмотренных элементов списка.
6. Анализ теоретических показателей трудоемкости и их сопоставление с практическими результатами:
Структура данных | Извлечение по ЛН | Включение/искл. | Ускоренный поиск | Поиск в неупоряд. |
Массив | 1 | N/2 | Log N | N/2 |
Экспериментальные показатели трудоёмкости при вставке, удаление и поиске M элементов в массив размера N. Рис 1.
Объём массива | Вставка | Удаление | Поиск |
100 | 50 | 48 | 83 |
200 | 100 | 99 | 155 |
300 | 146 | 150 | 242 |
400 | 194 | 198 | 316 |
500 | 242 | 251 | 399 |
1000 | 506 | 514 | 790 |
5000 | 2597 | 2609 | 3926 |
Графики
Рис. 1
Анализ графических результатов
Перед началом сопоставления мы привели таблицу теоретических показателей трудоёмкости базовых операций вставки, удаления и поиска. Затем, исследуя экспериментальные показатели и сопоставляя их с теоретическими, мы пришли к выводу, что показатели вставки и удаления практически совпадают. Поиск также линейно зависит от размера структуры данных. В данном случае наблюдается превосходство по трудоемкости над операциями удаления и вставки. Это обусловлено тем, что происходят многочисленные промашки. Анализ проводился при среднем состоянии АТД (как было указано в методических указаниях к лабораторной работе). Для большей наглядности приведен график: в виде диаграмм
7. Выводы.
В процессе лабораторной работы:
1) Освоили технологию реализации позиционных, линейных коллекций на примере АТД «Список - надёжный массив».
2) Освоение методики тестирования трудоёмкости операций для данного вида коллекции.
3) Повысили навыки программирования шаблонных классов.
8. Список используемой литературы.
1) Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с английского/Роберт Сеждвик. – СПб. : , 2002. – 688 с.
2) Глушаков С. В.
Язык программирования С++ /Худож. – оформитель . – Харьков: Фолио, 2002 – 500.
3) Подбельский С. С.
Программирование на языке Си : Учебное пособие. 2 – е доп.
Изд. – М.: Финансы и статистика, 2002 – 600 с.
4) С++ язык программирования “И. В.К.-СОФТ” Москва 1991
9. Описание работы программы на контрольных примерах
Шаблон массива может хранить указатели на объекты типа lond, int, double, а также при небольшом изменение кода программы в списке могут хранится указатели на строчка (char *) но это будет доработано позже…
10. Тексты программных модулей (приложение).
slist. h:
#include "stdafx. h"
#include "MyExc. h"
#include "Iterator. h"
template<class T> class Iterator;
template <class T> //Класс список
class slist
{
private:
int size; //текущий размер массива
int cur_el; //количество элементов в списке
int size0; //начальный размер массива
T* array; //динамический массив
long ch_vst; //Трудоемкость при вставке элемента по лог. номеру
long ch_del; //Трудоемкость при удаление элемента по лог. номеру
long ch_val; //Трудоемкость при поиске элемента по значению
long ch_vstx; //Число вставленных элементов
T operator [] (int index) //Возвращение элемента по индексу
{ if(is_empty()) throw MyExc(-3);
if (index<0 && index>cur_el-1) throw MyExc(-1);
else
return array[index];}
//
void change_sz (int sz) //изменяет размер списка
{T* tmp=new T[sz];
if (sz<=size) //Если надо уменьшить размер массива
{for (int i=0; i<cur_el; i++)
tmp[i]=array[i];
delete []array;
array=tmp;
size=sz; } else //Если надо увеличить размер массива
{for (int i=0; i<cur_el; i++)
{ tmp[i]=array[i];
ch_vst++;}
delete []array; //Удаляем старый массив
array=tmp;
size=sz;}}
public:
slist(int sz=10):size0(sz), size(sz)
{array=new T[sz];
cur_el=ch_vst=ch_del=ch_val=ch_vstx=0; }
~slist()
{if (cur_el==0) delete []array;}
int ask_sz() //возащает текущий размер
{if(is_empty()) throw MyExc(-3);
return cur_el-1; }
int ask_sz1() //возащает текущий размер
{return cur_el; }
void report() //отчет
{ cout<<"Insert: "<<ch_vst<<endl;
cout<<"Delete: "<<ch_del<<endl;
cout<<"Searching values: "<<ch_val<<endl; }
bool is_empty() //проверка на пустоту
{ if(cur_el==0) return true;
else return false; }
T return_ind (int index) //возвращает элемент по индексу
{ if(is_empty()) throw MyExc(-3);
if (index<0 || index>cur_el-1) throw MyExc(-1);
return array[index];}
//операции:
void clear_lst() //очистка списка
{ size=size0;
cur_el=ch_vst=ch_del=ch_vstx=0; }
int find_val(T key) //получение позиции в списке элемента с //заданным значением
{ if(is_empty()) throw MyExc(-3);
for (int i=0;i<cur_el;i++)
{ ch_val++;
if(array[i]==key) return i; }
throw MyExc(-2);} //Если не нашли
bool is_val (T key) //опрос наличия элемента с //заданным значением
{for (int i=0;i<cur_el;i++)
{if(array[i]==key) return true;}
return false;}
//Вставка элемента в массив по индексу
void insert (T new_el, int index)
{if (index<0 || index>size) throw MyExc(-1); //Неверный индекс
//empty slist
if (cur_el==0) //Список пуст
{ cur_el++;
ch_vst++;
array[0]=new_el;
cout<<"Chislo vstavlennux el: "<<ch_vstx++<<"\r";
return; }
//full slist:
if (cur_el==size) //Увеличиваем размерность массива на //начальный размер массива
{change_sz(size+size0); }
//not empty:
if (index>=0 && index<=cur_el) //Вставка в середину
{ for (int i=cur_el; i>index; i--)
{ array[i]=array[i-1];
ch_vst++; }
array[index]=new_el;
cur_el++;
cout<<"Chislo vstavlennux el: "<<ch_vstx++<<"\r";
}
else if (index>cur_el && index<size)
{ array[++cur_el]=new_el;
ch_vst++;
cout<<"Chislo vstavlennux el: "<<ch_vstx++<<"\r";
return;}}
T delete_el (int index) //Удаление элемента массива по //индексу
{ T del=array[index];
if(is_empty()) throw MyExc(-3);
if (index<0 || index>cur_el-1) throw MyExc(-1);
for (int i=index; i<cur_el; i++)
{ array[i]=array[i+1];
ch_del++;}
--cur_el;
//TODO: check here the size of slist and the amount of its elements!
if (cur_el==size/2 && size>size0)
{change_sz(size/2+size0); }
return del;}
//----Распечатываем список------
friend ostream& operator<<(ostream& os, slist<T> &s)
{ int n=0;
if(s. is_empty()) throw MyExc(-3);
cout<<"There are all elements of slist:"<<endl;
for(int i=0;i<s. cur_el;i++,n++)
{ os<<s. array[i]<<" ";
if(n==4)
{ cout<<endl;
n=-1;}}
cout<<endl;
os<<"\nThe current amount elements of slist is:"<<s. cur_el<<endl;
os<<"The current size of array is:"<<s. size<<endl;
os<<"The initial size of array is:"<<s. size0<<endl;
return os;}
friend class Iterator<T>; // классу iterator разрешаем доступ к классу Elem.
};
iterator. h:
#include "stdafx. h"
template<class T> class slist;
template<class T> //Класс итератор
class Iterator
{ slist<T> &l; //указатель на список
int ln; //логический номер элемента
bool key; //ключ
public:
Iterator(slist<T> &L):l(L){ln=0;key=0;}
Iterator& operator++() //Переходим к след. элементу массива
{ if(key==1)
{ln++;key=0;}
if(l. ask_sz()==0)
{cout<<"Array empty!!!"<<endl;
return *this;}
if(ln==l. ask_sz()) ln=0;
cout<<l[ln++]<<"("<<ln<<")"<<endl;
return *this;}
Iterator& operator--() //Переходим к пред. элементу массива
{ if(key==0)
{ln--;key=1;}
if(l. ask_sz()==0)
{
cout<<"Array empty!!!"<<endl;
return *this;
}
if(ln==-1) {ln=l. ask_sz()-1; }
cout<<l[ln--]<<"("<<ln<<")"<<endl;
return *this;
}
void First_el() //Переходим на начало списка
{
if(l. ask_sz()==0)
{
cout<<"Array empty!!!"<<endl;
return ;
}
ln=0;
cout<<l[ln]<<"("<<ln<<")"<<endl;
return;
}
void Last_el() //Переходим на конец списка
{
if(l. ask_sz()==0)
{
cout<<"Array empty!!!"<<endl;
return ;
}
ln=l. ask_sz()-1;
cout<<l[ln]<<"("<<ln<<")"<<endl;
return;
}
friend class slist<T>; // классу Iterator разрешаем доступ к классу slist.
};
MyExc. h:
#include "stdafx. h"
class MyExc //класс исключений
{
int temp;
public:
MyExc(int t):temp(t){}
int GetMeExc(){return temp;}
};
