Лабораторная работа №1
.docСанкт-Петербургский Государственный Электротехнический Университет
Кафедра МОЭВМ
Объектно-ориентированное программирование
Отчет по лабораторной работе №1
«Реализация списочных структур»
Выполнила: Чярина Т.В.
Группа: 5342
Факультет: КТИ
Проверил: Чередниченко А.И.
Санкт-Петербург, 2008 г.
Формулировка задания
Разработать на языке C++ двунаправленный список. Реализовать операцию сортировки элементов списка.
Основная идея построения программы с использованием классов
При разработке объектно-ориентированной программы определяются сущности, которые будут использоваться, и на основе этих сущностей разрабатываются классы. При разработке программы с помощью классов, пользователю классов предоставляется определённый набор методов, с помощью которых он может изменять или просматривать данные объектов или классов, а реализация этих методов скрыта.
Каждый класс описывается и реализуется в отдельных файлах, что позволяет, имея эти файлы, повторно использовать эти классы.
В данной программе определены 2 сущности
- элемент двунаправленного списка
- двунаправленный список
Интерфейс класса элементов списка
class Elem {
friend List;
private:
int integer;
Elem *next;
Elem *prev;
void setNext(Elem *_next);
void setPrev(Elem *_prev);
public:
Elem(int _integer=0);
~Elem();
Elem* getNext();
Elem* getPrev();
void setInteger(int _integer);
int getInteger();
};
Методы класса
void setNext(Elem *_next) добавить связь со следующим элементом
void setPrev(Elem *_prev) добавить связь с предыдущим элементом
Elem* getNext() вернуть следующий элемент
Elem* getPrev() вернуть предыдущий элемент
void setInteger(int _integer) задать значение элемента
int getInteger() вернуть значение элемента
Текст файла реализации класса Elem.
Elem::Elem(int _integer) {
integer=_integer;
next = NULL;
prev = NULL;
};
Elem::~Elem() {
};
void Elem::setNext(Elem *_next) {
next = _next;
};
void Elem::setPrev(Elem *_prev) {
prev = _prev;
};
Elem* Elem::getNext() {
return next;
}
Elem* Elem::getPrev() {
return prev;
}
void Elem::setInteger(int _integer) {
integer=_integer;
}
int Elem::getInteger() {
return integer;
}
Интерфейс класса списка
class List {
private:
int Length;
Elem* current;
public:
List();
~List();
void add(int _integer=0);
void set(int _integer);
int getElem();
void del();
void view();
void goFirst();
void goLast();
void goNext();
void goPrev();
int isEmpty();
int Mediana();
int getLength();
int getIntegerAt(int index);
void sortByMax();
void sortByMin();
int getMax();
int getMin();
Elem* getElementAt(int index);
};
Методы класса
void add(int _integer=0) добавить новый элемент списка
void set(int _integer) задать значение текущего елемента
int getElem() вернуть значение текущего элемента
void del() удалить текущий элемент
void view() вывести на экран весь список
void goFirst() перейти к первому элементу списка
void goLast() перейти к последнему элементу списка
void goNext() перейти к следующему элементу списка
void goPrev() перейти к предыдущему элементу списка
int isEmpty() список пуст?
int Mediana() вернуть медиану списка
int getLength() вернуть длину списка
int getIntegerAt(int index) получить значение элемента по индексу
void sortByMax() сортировать по возрастанию
void sortByMin() сортировать по убыванию
int getMax() вернуть максимум списка
int getMin() вернуть минимум списка
Elem* getElementAt(int index) получить элемент по индексу
Текст файла реализации класса Spisok
List::List() {
Length = 0;
current = NULL;
};
List::~List() {
goLast();
while( current->getPrev() != NULL) {
Elem * temp = current;
goPrev();
delete temp;
}
if (current != NULL) delete current;
};
void List::add(int _integer) {
if(Length == 0) {
current = new Elem(_integer);
Length++;
}
else if (current->getPrev() == NULL) { // dobavlenie esli tekushiy perviy
Elem* temp = new Elem(_integer);
temp->setNext(current);
current->setPrev(temp);
current = temp;
Length++;
}
else {
Elem* temp = new Elem(_integer);
temp->setNext(current);
temp->setPrev((*current).getPrev());
current->setPrev(temp);
(temp->getPrev())->setNext(temp); // zlobnaya zapis' svyazivaet predidushiy element s temp
current = temp;
Length++;
}
};
void List::set(int _integer) {
current->setInteger(_integer);
};
int List::getElem() {
return current->getInteger();
};
void List::del() {
Elem * temp = current;
if (Length != 0) {
if(current->getPrev() == NULL && current->getNext() == NULL) {
delete current;
} else if(current->getPrev() != NULL && current->getNext() != NULL) {
Elem * next = current->getNext();
Elem * prev = current->getPrev();
prev->setNext(next);
next->setPrev(prev);
current = prev;
delete temp;
} else if (current->getPrev() == NULL && current->getNext() != NULL) {
Elem * next = current->getNext();
next->setPrev(NULL);
current = next;
delete temp;
} else if (current->getPrev() != NULL && current->getNext() == NULL) {
Elem * prev = current->getPrev();
prev->setNext(NULL);
current = prev;
delete temp;
}
Length--;
}
};
void List::view() {
if (Length != 0) {
Elem * temp = current;
goFirst();
for(int i=0;i<Length;i++) {
cout << " " << ((current==temp)?"<":"") << current->getInteger()
<< ((current==temp)?">":"") << "\n";
goNext();
}
current = temp;
} else cout << " <EMPTY> \n";
};
void List::goFirst() {
while(current->getPrev() != NULL) {
goPrev();
}
}
void List::goLast() {
while(current->getNext() != NULL) {
goNext();
}
}
void List::goNext() {
if (current->getNext() != NULL) current = current->getNext();
}
void List::goPrev() {
if (current->getPrev() != NULL) current = current->getPrev();
}
int List::isEmpty() {
return Length == 0;
}
int List::Mediana() {
return getIntegerAt( ((Length%2)==0) ? (Length/2) : (Length/2 + 1));
}
int List::getLength() {
return Length;
}
int List::getIntegerAt(int index) {
Elem * temp = current;
goFirst();
for(int i=1;i<index;i++) {
goNext(); }
int Integer = current->getInteger();
current = temp;
return Integer;
}
Elem* List::getElementAt(int index) {
Elem * temp = current;
Elem * toreturn;
goFirst();
for(int i=1;i<index;i++) {
goNext();
}
toreturn = current;
current = temp;
return toreturn;
}
void List::sortByMax() {
int hold;
for(int j=1;j<Length+1;j++) {
for(int i=0;i<Length;i++) {
if(getIntegerAt(i) > getIntegerAt(i+1)) {
hold = getElementAt(i)->getInteger();
getElementAt(i)->setInteger(getElementAt(i+1)->getInteger());
getElementAt(i+1)->setInteger(hold);
} } } }
void List::sortByMin() {
int hold;
for(int j=1;j<Length+1;j++) {
for(int i=0;i<Length;i++) {
if(getIntegerAt(i) < getIntegerAt(i+1)) {
hold = getElementAt(i+1)->getInteger();
getElementAt(i+1)->setInteger(getElementAt(i)->getInteger());
getElementAt(i)->setInteger(hold);
} } }}
int List::getMax() {
int max = -31000;
for(int i=0;i<Length;i++) if (getIntegerAt(i+1) > max) max = getIntegerAt(i+1);
return max;
}
int List::getMin() {
int min = 31000;
for(int i=0;i<Length;i++) if (getIntegerAt(i+1) < min) min = getIntegerAt(i+1);
return min;
}
Разработка тестирующей программы
Для тестирования классов была разработана тестирующая программа с удобным для пользовательским интерфейсом, возможностью вводить входные данные вручную.
Текст тестирующей программы на языке С++
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
#include "List.cpp"
void main()
{
char key='_';
clrscr();
List list;
int Integer;
while(key!='0')
{
clrscr();
cout << "Команды управления : \n"
<< "1 – Добавить элемент \n"
<< "2 – Удалить элемент \n"
// << "3 – Перейти в начало \n"
// << "4 – Перейти в конец \n"
// << "5 – Изменить значение элемента \n"
// << "6 – Показать значение элемента \n"
// << "7 – Показать длину списка \n"
<< "8 – Отсортировать список по убыванию \n"
<< "9 – Отсортировать список по возрастанию \n"
<< "< - Перейти назад \n"
<< "> - Перейти вперед \n"
<< "0 – Завершить работы программы \n\n";
cout << "---------СПИСОК--------- \n";
list.view();
cout << "------------------------ \n";
key=getch();
switch(key)
{
case '1':
cout << "Введите целое число: ";
cin >> Integer;
list.add(Integer);
break;
case '2':
list.del();
break;
/*case '3':
list.goFirst();
break;
case '4':
list.goLast();
break;
case '5':
cout << "Введите целое число: ";
cin >> Integer;
list.set(Integer);
break;
case '6':
if (list.getLength() == 0) cout << "Значение медианы не определено, так как список пуст ";
else cout << "Значение медианы равно " << list.Mediana();
getch();
break;
case '7':
cout << "Длина списка равна ";
cout << list.getLength();
getch();
break;*/
case ',':
list.goPrev();
break;
case '.':
list.goNext();
break;
case '8':
if(list.getLength() > 1) list.sortByMax();
break;
case '9':
if(list.getLength() > 1) list.sortByMin();
break;
}
clrscr();
}
}
Результаты тестирования функции формирования подсписков сведены в таблицу
-
Входные данные
Выходные данные
Основной список
Сортировка по возрастанию
Сортировка по убыванию
«отсутствуют»
пустой список
пустой список
пустой список
5
5
5
5
3 9 5 1 2
2 1 5 9 3
1 2 3 5 9
9 5 3 2 1
Отчёт по тестированию
В результате тестирования ошибок в программе не обнаружилось, поэтому разработанные классы можно использовать в других разработках. Можно сделать вывод, что разработанные классы программы соответствуют заданию.
Описание достоинств программы
Разработанная программа обладает удобным интерфейсом, позволяет вводить данные самостоятельно с клавиатуры, позволяет удалять конкретный элемент и множество дополнительных функций.
Описания недостатков программы
Не реализована проверка вводимых данных. Не реализован ввод данных с файла.
Количественные характеристики программы
Общая длина текста программы – 240 строк.
Общее количество классов, используемых в программе – 2
Количество новых (разработанных при выполнении работы) классов – 2:
Elem: длина текста описания – 16 строк; реализации – 25 строк
Spisok: длина текста описания – 26 строк; реализации – 166 строк
Общее количество заголовочных файлов – 2
Общее количество файлов-кодов – 3
Выводы по лабораторной работе
В результате выполнения лабораторной работы были закреплены знания в разработке объектно-ориентированных программ на языке С++. Были разработаны классы, которые можно будет использовать в других программах, а в частности в дальнейших лабораторных работах.