Отчет по лабораторной работе №




Скачать 92.15 Kb.
НазваниеОтчет по лабораторной работе №
Дата публикации04.04.2013
Размер92.15 Kb.
ТипОтчет
litcey.ru > Военное дело > Отчет
Национальный исследовательский

Томский Политехнический университет


Институт – Кибернетический Центр

Направление – Информатика и вычислительная техника

Кафедра – Оптимизации систем управления

«ОСВОЕНИЕ ТЕХНОЛОГИИ РЕАЛИЗАЦИИ ПОЗИЦИОННЫХ, ЛИНЕЙНЫХ КОЛЛЕКЦИЙ НА ПРИМЕРЕ АТД "СПИСОК"»

Отчет по лабораторной работе № 4

Вариант 12
по дисциплине Структуры и алгоритмы обработки данных

Выполнил

Студент группы 8В83 __________Г.В. Кобызь

Проверил __________А.В. Черний

ЦЕЛИ РАБОТЫ


Освоение технологии реализации позиционных, линейных коллекций на примере АТД "Список". Освоение методики тестирования трудоёмкости реализации коллекций.
^

ЗАДАНИЕ К ЛАБОРАТОРНОЙ РАБОТЕ


1. Спроектировать, реализовать и провести тестовые испытания АТД "Список" для коллекции, содержащей данные произвольного типа. Тип данных выбирается самостоятельно. Структура данных выбирается по номеру студента (шаг3) в журнале:

1. Структура данных - двусвязная, на базе адресных указателей.

2. Структура данных - кольцевая, односвязная, на базе адресных указателей.

3. Структура данных - кольцевая, двусвязная, на базе адресных указателей.
Интерфейс АТД "Список" включает следующие операции:

опрос размера списка,

очистка списка,

проверка списка на пустоту,

опрос наличия элемента с заданным значением,

доступ к значению элемента с заданным номером в списке,

получение позиции в списке элемента с заданным значением,

включение нового элемента в позицию с заданным номером,

удаление элемента из позиции с заданным номером,
1. Для тестирования эффективности операций интерфейс АТД "Список" включить дополнительную операцию:

опрос числа элементов списка, просмотренных операцией.
2. Выполнить отладку и тестирование всех операций АТД "Список" с помощью меню операций.

3. Выполнить тестирование средней трудоёмкости операций поиска, вставки и удаления элементов.

4. Провести анализ экспериментальных показателей трудоёмкости операций.

Составить отчёт по лабораторной работе. Отчёт должен содержать следующие пункты:

a) общее задание и вариант задания,

b) формат АТД,

c) определение шаблонного класса для коллекции "Список", предназначенное для клиентской программы,

d) описание методики тестирования трудоёмкости операций,

e) таблицы и графики с полученными оценками трудоёмкости операций для среднего случая функционирования АТД. Должны быть приведены графики среднего числа просмотренных элементов для операций поиска, вставки и удаления (графики совмещены в одной системе координат),

f) сравнительный анализ теоретических и экспериментальных оценок эффективности алгоритмов АТД,

g) приложение с текстами программ:

h) полное определение класса и текстов методов класса,

i) текст программы тестирования трудоёмкости операций.
^

ФОРМАТ АТД


Кольцевая, двусвязная, на базе адресных указателей.

ШАБЛОННЫЙ КЛАСС ДЛЯ КОЛЛЕКЦИИ "СПИСОК", ПРЕДНАЗНАЧЕННЫЙ ДЛЯ КЛИЕНТСКОЙ ПРОГРАММЫ:


struct List {

char name[20]; //Имя студента

double runtime; //Время бега

int jumplength; //Длина прыжка

int n; //Позиция элемента в списке

List* next; //Ссылка на следущий элемент списка

List* prev; //Ссылка на предыдущий элемент списка

};
^

ОПИСАНИЕ МЕТОДИКИ ТЕСТИРОВАНИЯ ТРУДОЁМКОСТИ ОПЕРАЦИЙ


Трудоемкость операции зависит от количества проходов по элементам списка. Таким образом, чем дальше элемент от конца списка, тем больше трудоемкость его поиска, замены, вставки.

^

ТАБЛИЦЫ И ГРАФИКИ С ПОЛУЧЕННЫМИ ОЦЕНКАМИ ТРУДОЁМКОСТИ ОПЕРАЦИЙ


Сложность алгоритмов поиска, вставки и удаления элементов, имеет сложность T(n) = O(n), если мы производим данные операции над первым или последним элементами в списке, то их сложность T(n) = O(1).
Таким образом, показания графика подтверждают теоритическую оценку эффективности работы алгоритма T(n) = O(n).

^

ПОЛНОЕ ОПРЕДЕЛЕНИЕ КЛАССА И ТЕКСТОВ МЕТОДОВ КЛАССА


//---------------------------------------------------------------------------

#include

#pragma hdrstop

#include

#include

#include

#include

//---------------------------------------------------------------------------
#pragma argsused

double runstandart = 13.0; //Норматив по бегу

int jumpstandart = 250; //Норматив по прыжкам

int num = 0; //Количество элементов в списке
struct List {

char name[20]; //Имя студента

double runtime; //Время бега

int jumplength; //Длина прыжка

int n; //Позиция элемента в списке

List* next; //Ссылка на следущий элемент списка

List* prev; //Ссылка на предыдущий элемент списка

};
//-----Создание головы и хвоста списка

struct DynList {

List* head; //Первый элемент (голова) списка

List* tail; //Последний элемент (хвост) списка

};
//-----Создание пустого списка

void constrList(DynList &list) {

list.head = NULL;

list.tail = NULL;

}
//-----Проверка списка на пустоту

bool chekEmpty(DynList list) {

return (list.head==NULL);

}
//-----Опрос размера списка

int getListNum() {

return num;

}
//-----Перенумерация элементов

void reNumList (DynList list) {

for (int i = 0; i < getListNum(); i++) {

list.head->n = num-i;

list.head=list.head->next;

}

}

//-----Добавить новый элемент в голову списка

void addListHead (DynList &list, char* n, double r, int j) {

List* c = new List();

strcpy_s(c->name, 15, n);

c->runtime = r;

c->jumplength = j;

c->n = num + 1;

if (chekEmpty(list)) {

num++;

c->prev = c;

c->next = c;

list.head = list.tail = c;

}

else {

c->next = list.head;

c->prev = list.head->prev;

list.head->prev = c;
list.head = c;

list.tail->next = list.head;

num++;

}

reNumList(list); //Перенумерация элементов

}
//-----Добавить новый элемент в хвост списка

void addListTail (DynList &list, char* n, double r, int j) {

List* c = new List();

strcpy_s(c->name, 15, n);

c->runtime = r;

c->jumplength = j;

c->n = num + 1;

if (chekEmpty(list)) {

num++;

c->prev = c;

c->next = c;

list.head = list.tail = c;

}

else {

c->next = list.head;

c->prev = list.tail;

list.tail->next = c;

list.tail = c;

num++;

}

reNumList(list); //Перенумерация элементов

}
//-----Вывод элементов списка в прямой и обратной последовательности

List* printList(DynList list) {

if (chekEmpty(list) || num == 0) cout << "List is empty!\n";

else {

List* elem = list.head;
for (int i = 0; i < getListNum(); i++) {

cout << elem->name << " " <n<<

endl;

elem = elem->next;

}
cout << endl;
elem = list.tail;

for (int i = 0; i < getListNum(); i++) {

cout << elem->name << " " <n<
elem = elem->prev;

}

}

}
//-----Удаление элемента из позиции с заданным номером

void delElem (DynList &list, int n) {

if(n < 1 || n > num) {

cout << "Incorrect position!\n";

return;

}

int i = 0;

List* del = list.head;

while(i < n) { //Доходим до элемента, который удаляется

del = del->prev;

i++;

}

cout << "\nItem deleted:" << del->name << " Operations number: "<< i << endl << endl;
List* prev_del = del->prev; //Элемент, который предшествует удаляемому

List* after_del = del->next; //Элемент, который следует за удаляемым
if(prev_del != NULL && num != 1)

prev_del->next = after_del;

if(after_del != NULL && num != 1)

after_del->prev = prev_del;

if(n == num)

list.head = after_del;

if(n == 1)

list.tail = prev_del;

delete del;

num--;

reNumList(list); //Перенумерация элементов

}
//-----Очистка списка

delAll(DynList &list) { //Удаляет все элементы списка

while(num != 0)

delElem(list, 1);

}
//-----Опрос наличия элемента с заданным значением

void ifElem (DynList &list, double str) {

List* elem = list.head;

bool flag = false;

for (int i = 0; i < getListNum(); i++) {

if (elem->runtime == str) {

flag = true;

cout << "\nItem found, this is: " << elem->name <<" runtime: "<< elem->runtime << " Operations number: "<< i+1 << endl;

}

elem = elem->next;

}

if (!flag) cout << "Item not found!";

}
//-----Получение позиции в списке элемента с заданным значением

void getElemPosition (DynList &list, double str) {

List* elem = list.tail;

bool flag = false;

for (int i = 0; i < getListNum(); i++) {

if (elem->runtime == str) {

flag = true;

cout << "\nItem found. It has position: " << elem->n << " Operations number: "<< i+1 << endl;

}

elem = elem->prev;

}

if (!flag) cout << "Item not found!";

}
//-----Доступ к значению элемента с заданным номером в списке

void getElemValue (DynList &list, int n) {

if(n < 1 || n > num) {

cout << "Incorrect position!\n";

return;

}

int i = 1;

List* elem = list.tail;

while(i < n) { // Доходим до элемент

elem = elem->prev;

i++;

}

cout << "\nValue of the item number " << n << ": " << elem->name << " Operations number: "<< i << endl;

}
//-----Включение нового элемента в позицию с заданным номером

Insert(DynList &list) {
char temp_name[20]; //Имя студента

double temp_runtime; //Время бега

int temp_jumplength; //Длина прыжка

int pos = 0;

cout << "\nInput position: ";

cin >> pos;

if(pos < 1 || pos > num + 1) { // Позиция от 1 до num+1

cout << "Incorrect insert position !\n"; // Неверная позиция

return -1;

}
if(pos == 1) { //Вставка в конец списка

//-----Вводимые данные

cout << "Input name: ";

cin >> temp_name;

cout << "Input runtime: ";

cin >> temp_runtime;

cout << "Input jumplength: ";;

cin >> temp_jumplength;
//-----Добавление в конец списка

addListTail(list, temp_name, temp_runtime, temp_jumplength);

return -1;

}
else if(pos == num+1) { //Вставка в начало списка

//-----Вводимые данные

cout << "Input name: ";

cin >> temp_name;

cout << "Input runtime: ";

cin >> temp_runtime;

cout << "Input jumplength: ";;

cin >> temp_jumplength;
addListHead(list, temp_name, temp_runtime, temp_jumplength);
return -1;

} else {

int i = 1; //Счетчик

List* ins = list.head;

while(i < pos) {

ins = ins->prev; //Доходим до элемента, перед которым вставка

i++;

}
List* prev_ins = ins->prev; //Предшествующий элемент
List* temp = new List;
//-----Ввод данных

cout << "Input name: ";

cin >> temp_name;

cout << "Input runtime: ";

cin >> temp_runtime;

cout << "Input jumplength: ";;

cin >> temp_jumplength;
strcpy_s(temp->name, 15, temp_name);

temp->runtime = temp_runtime;

temp->jumplength = temp_jumplength;
//-----Настройка связей

if(prev_ins != 0 && num != 1)

prev_ins->next = temp;
temp->next = ins;

temp->prev = prev_ins;

ins->prev = temp;
cout << "Insert operations number: " << i << endl;

}

num++;

reNumList(list); //Перенумерация элементов

}
int _tmain(int argc, _TCHAR* argv[]) {

DynList students; //Создание динамического списка

constrList (students); //Создание пустого списка
//-----Внесение студентов в список

addListHead (students, "Vas9", 10.5, 270);

addListHead (students, "Gen9", 12.5, 230);

addListHead (students, "Slava", 12.7, 250);

addListHead (students, "Petr", 11.5, 215);

addListHead (students, "Maxim", 14.5, 150);

addListHead (students, "Sasha", 11.7, 198);

addListHead (students, "Andrey", 10.8, 234);

addListHead (students, "Kolya", 12.1, 227);

addListHead (students, "Dima", 13.4, 205);

addListHead (students, "Kirill", 11.5, 179);

addListHead (students, "Vova", 12.8, 218);

addListHead (students, "Misha", 12.3, 250);
printList(students);

cout << endl << endl <<"number of items: "<< getListNum() << endl << endl;
delElem(students,6); //Удаление элемента из позиции с заданным номером
printList(students);

cout << endl << endl <<"number of items: "<< getListNum() << endl << endl;
//delAll(students); //Очистка списка
ifElem(students, 10.8); //Опрос наличия элемента с заданным значением

getElemValue(students, 4); //Доступ к значению элемента с заданным номером в списке

getElemPosition(students, 10.8); //Получение позиции в списке элемента с заданным значением

Insert(students); //Включение нового элемента в позицию с заданным номером

cout << endl;

printList(students);

cout << endl << endl <<"Number of items: "<< getListNum() << endl << endl;

getch();

return 0;

}
//---------------------------------------------------------------------------


ТЕКСТ ПРОГРАММЫ ТЕСТИРОВАНИЯ ТРУДОЁМКОСТИ ОПЕРАЦИЙ


int i = 1;

while(i < pos) {

ins = ins->prev; //Доходим до элемента, перед которым вставка

i++;

}

Доходим до элемента, с заданным значение или номером, для осуществления необходимых операций. Счетчик считает количество операций прохождений по элементам списка.



Томск 2010

Похожие:

Отчет по лабораторной работе № iconОтчет по лабораторной работе №2 «Исследование диодных схем» по дисциплине «Электроника»
Подготовиться к лабораторной работе, т е знать и понимать процессы, происходящие в исследуемых схемах
Отчет по лабораторной работе № iconОтчет по лабораторной работе 6 Контрольные вопросы 6
Целью лабораторной работы является ознакомление с методами работы с динамическими элементами с использованием структур
Отчет по лабораторной работе № iconОтчет по лабораторной работе №15 по дисциплине "Программирование...
Отчет по лабораторной работе №15 по дисциплине "Программирование на языке высокого уровня"
Отчет по лабораторной работе № iconОтчет по лабораторной работе №1 По дисциплине «Название дисциплины»

Отчет по лабораторной работе № iconОтчет по лабораторной работе должен содержать номер, название, цель...
Основным носителем информации является файл. Файлы организованы в системе не хаотическим образом, а виде определенной структуры,...
Отчет по лабораторной работе № iconОтчёт По лабораторной работе м-04 «Изучение законов равноускоренного движения»
Цель работы: Изучение динамики поступательного движения связанной системы тел с учётом силы трения: оценка силы трения как источника...
Отчет по лабораторной работе № iconОтчет по лабораторной работе №4 по дисциплине электроника “
Что должно быть получено в результате его выполнения (прогнозируемый результат)?
Отчет по лабораторной работе № iconОтчет по лабораторной работе №2 по курсу «Электроника»
Овладеть методикой снятия вольт-амперных характеристик (вах) нелинейных элементов
Отчет по лабораторной работе № iconОтчет о лабораторной работе №2 «одноиндексные задачи линейного программирования»
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
Отчет по лабораторной работе № iconОтчет по лабораторной работе №1 по дисциплине
Расчет основной заработной платы, выплачиваемой исполнителям всего проекта, ведется по следующей формуле
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
litcey.ru
Главная страница