Реализация концепции контейнеров и итераторов на примере однонаправленного связанного списка

 















Реализация концепции контейнеров и итераторов на примере однонаправленного связанного списка




ОГЛАВЛЕНИЕ


ВВЕДЕНИЕ

Глава 1. Проектирование классов

.1Формализация задачи

1.2Проектирование абстракции данных

.3Определение семантики классов

.4Определение отношений между классами

Глава 2. Реализация

2.1 Реализация класса TList

.2 Реализация класса TBasicIterator

.3 Реализация класса TArrayIterator

.4 Реализация класса TLineIterator

.5 Реализация класса TReverseIterator

.6 Реализация класса TListException

Глава 3. Результаты

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ



ВВЕДЕНИЕ


Объектно-ориентированная парадигма программирования не нова. Её истоки восходят к Симуле-67, хотя первая впервые она была полностью реализована в Smalltalk-80. ООП (Объектно-ориентированное программирование) приобрело популярность во второй половине 80-х вместе с такими языками, как С++, Objective C (другое расширение C), Object Pascal и Turbo Pascal, CLOS (обектно-ориентированное расширение Lisp'a), Eiffel, Ada (в её последних воплощениях) и недавно - в Java. В этой статье внимание сосредоточена на C++, Object Pascal и Java, иногда упоминаются и другие языки.

Ключевые черты ООП хорошо известны:

Первая - инкапсуляция - это определение классов - пользовательских типов данных, объединяющих своё содержимое в единый тип и реализующих некоторые операции или методы над ним. Классы обычно являются основой модульности, инкапсуляции и абстракции данных в языках ООП.

Вторая ключевая черта, - наследование - способ определения нового типа, когда новый тип наследует элементы (свойства и методы) существующего, модифицируя или расширяя их. Это способствует выражению специализации и генерализации.

Третья черта, известная как полиморфизм, позволяет единообразно ссылаться на объекты различных классов (обычно внутри некоторой иерархии). Это делает классы ещё удобнее и облегчает расширение и поддержку программ, основанных на них.

Инкапсуляция, наследование и полиморфизм - фундаментальные свойства, которыми должен обладать язык, претендующий называться объектно-ориентированным (языки, не имеющие наследования и полиморфизма, но имеющие только классы, обычно называются основанными на классах). Различные ОО языки используют совершенно разные подходы. Мы можем различать ОО языки, сравнивая механизм контроля типов, способность поддерживать различные программные модели и то, какие объектные модели они поддерживают.

Алан Кей в свое время вывел пять основных черт языка Smalltalk - первого удачного ОО языка:

Все является объектом. Объект как хранит информацию, так и способен ее преобразовывать. В принципе любой элемент решаемой задачи (дом, собака, услуга, химическая реакция, город, космический корабль и т.д.) может представлять собой объект. Объект можно представить себе как швейцарский нож: он является набором различных ножей и «открывашек» (хранение), но в то же самое время им мы можем резать или открывать что-либо (преобразование).

Каждый объект имеет свою собственную «память» состоящую из других объектов. Таким образом, программист может скрыть сложность программы за довольно простыми объектами. К примеру, дом (достаточно сложный объект) состоит из дверей, комнат, окон, проводки и отопления. Дверь, в свою очередь, может состоять из собственно двери, ручки, замка и петель. Проводка тоже состоит из проводов, розеток и, к примеру, щитка.

У каждого объекта есть тип. Иногда тип называют еще и классом. Класс (тип) определяет какие сообщения объекты могут посылать друг другу. Например, аккумуляторная батарея может передавать электролампе ток, а вот момент или физическое усилие - нет.

Все объекты одного типа могут получать одинаковые сообщения. К примеру, у нас есть 2 объекта: синяя и красная кружки. Обе разные по форме и материалу. Но из обеих мы можем пить (или не пить, если они пустые). В данном случае кружка - это тип объекта.

Самое лаконичное описание объекта предложил Буч: «Объект обладает состоянием, поведением и индивидуальностью».



Глава 1. Проектирование классов


1.1Формализация задачи


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

Все итераторы будут представлены классами-наследниками базового итератора, обеспечивающего взаимодействие с контейнером.

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


.2 Проектирование абстракции данных


В задаче удобно определить 6 объектов - классов. Пусть класс контейнера списка именуется TList, класс базового итератора - TListBasicIterator, классы-наследники базового итератора - TArrayIterator, TLineIterator, TReverseIterator, а класс исключений - TListException. Кроме того реализуется структура Elem, представляющая конкретный элемент списка и имеющая поле row, которое носит смысловой характер, и поле next, которое является указателем на следующий элемент.

Класс TList имеет поля first и cur, которые являются указателями на начальный и текущий элементы списка соответственно, поскольку список характеризуется головным элементом и указателем, перемещающимся по списку.

Класс TListBasicIterator содержит поля basic_cur и basic_first, являющиеся указателями на текущий и начальный элементы соответственно. Данный класс позволяет работать с элементами контейнера, не влияя на элементы и указатели контейнера.

Класс TArrayIterator не имеет полей, а только методы, реализующие индексирование элементов и подсчета длины списка.

Класс TLineIterator имеет поля first и cur, которые являются указателями на начальный и текущий элементы списка соответственно. Этот класс реализует операции для работы с контейнером как со списком.

Класс TReverseIterator имеет поля first и cur, которые являются указателями на начальный и текущий элементы списка соответственно. Данный итератор работает со списком в обратном порядке, т.е. поле first указывает на последний элемент контейнера, а движение указателя происходит в сторону начального элемента контейнера.

Класс TListException имеет поля errmsg и errnum типа char* и int соответственно, носящими информацию о текущей исключительной ситуации (текст и код ошибки).


1.3 Определение семантики классов


Класс TList (контейнер для списка)

TList содержит поля first и cur, являющиеся указателями на первый и текущий элементы соответственно.

Данный класс содержит также приватный метод CreateFirst, создающий первый элемент списка. Также класс имеет методы для работы со списком: isEmpty (проверка списка на пустоту), isEnd (проверка достижения указателем конца списка), Rewind (установление указателя в исходное положение), Set (установка нового значения текущего элемента списка), Get (получение значения текущего элемента списка), Next (смещение указателя на следующий элемент), InsertAfterCurrent (вставка элемента после текущего), AddLast (вставка элемента в конец) и DeleteCurrent (удаление элемента из текущей позиции).

Кроме того, реализуются операторы вывода списка в поток и присваивания, деструктора и конструкторов.

Класс TBasicIterator (базовый итератор)

Данный класс имеет единственный конструктор, получающий на вход константную ссылку на контейнер списка, и виртуальную функцию nothing, показывающую, что данный класс является абстрактным и не должен иметь созданных объектов в программе.

Также класс имеет поля basic_cur и basic_first, указывающие на текущий и последний элементы списка соответственно. Поле basic_first указывает на тот же элемент, что и поле first класса TList, однако basic_cur не совпадает с указателем cur класса TList, что показывает независимость итератора от контейнера.

Класс TArrayIterator (итератор массива)

Данный класс имеет единственный конструктор, получающий на вход константную ссылку на контейнер списка и реализованную функцию nothing, что показывает возможность создания объектов данного класса.

Кроме того, реализуется оператор индексирования элементов и метод Count для подсчета числа элементов списка. Данные методы позволяют работать со списком как с массивом.

Класс TLineIterator (итератор прямого обхода)

Данный класс имеет единственный конструктор, получающий на вход константную ссылку на контейнер списка и реализованную функцию nothing, что показывает возможность создания объектов данного класса.

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

Еще список имеет поля cur и first, указывающие на текущий и головной элементы списка.


Класс TReverseIterator (итератор обратного обхода)

Данный класс имеет единственный конструктор, получающий на вход константную ссылку на контейнер списка и реализованную функцию nothing, что показывает возможность создания объектов данного класса.

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

Еще список имеет поля cur и first, указывающие на текущий и головной элементы списка.

Особенность данного итератора состоит в том, что он позволяет работать со списком в обратном порядке: головным элементом становится последний элемент списка, а движение происходит в направлении от последнего к начальному элементу контейнера.

Класс TListException (класс исключений)

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

Класс имеет поля errmsg и errnum типа char* и int соответственно, носящими информацию о текущей исключительной ситуации (текст и код ошибки), и методы GetMessage и GetCode для дальнейшей обработки ошибки в зависимости от ситуации. Еще в классе реализована операция вывода информации об ошибке в поток.


.4 Определение отношений между классами


Класс TBasicIterator является базовым для классов TLineIterator, TReverseIterator и TArrayIterator, поскольку каждый производный класс является конкретным частным случаем базового итератора.

Также класс TBasicIterator является дружественным для класса TList, так как он должен иметь доступ к элементам контейнера. Здесь будет применяться агрегация с классом TList, поскольку оба класса самостоятельны, но TBasicIterator содержит поле типа TList.

Между классами TList и TListException используется отношения использования: класс TList использует класс TListException для работы с исключительными ситуациями.

На рисунке 1 приведена диаграмма классов.


Рисунок 1 - Диаграмма классов




Глава 2. Реализация


Для решения поставленной задачи я использовал язык программирования C++. Программа разработана в среде Microsoft Visual Studio 2012, консольное приложение Win32. Операционная система Windows 7.

Программа представляет собой совокупность объектных модулей, заголовочных файлов и файлов с ихсодным кодом самой программы.

Каждый класс состоит из двух файлов: интерфейсной части - «ClassName.h» и реализационной - «ClassName.cpp».


2.1 Реализация класса TList


template<typename T>TList

{TListBasicIterator<T>;:<T>* first;<T>* cur;<T>& CreateFirst(T val);:operator=(const TList<T>&);(const TList<T>&);isEmpty();isEnd();& Rewind();& Set(T val);Get();& Next();& InsertAfterCurrent(T val);& AddLast(T val);& DeleteCurrent();(void);

~TList(void);ostream& operator<<(ostream& os, TList<T>& li)

{(li.isEmpty())

{<< "Empty";os;

}.Rewind();(!li.isEnd())

{<< li.Get() << " ";.Next();

}.Rewind();os;

}

};


2.2 Реализация класса TBasicIterator


class TListBasicIterator

{:void nothing() = 0;:<T> *basic_cur, *basic_first;:();(const TList<T>& l);

~TListBasicIterator(void);

};


2.3 Реализация класса TArrayIterator


template<typename T>TArrayIterator :TListBasicIterator<T>

{:void nothing() {};:(void);

~TArrayIterator(void);(const TList<T>& l);Count();& operator[](int pos);

};


2.4 Реализация класса TLineIterator


template<typename T>TLineIterator : public TListBasicIterator<T>

{:<T> *cur, *first;void nothing() {}:();(const TList<T>& l);<T>& operator++();& operator*();<T>& operator~();operator!();

~TLineIterator(void);

};


2.5 Реализация класса TReverseIterator


template<typename T>TReverseIterator :TListBasicIterator<T>

{:<T> *cur, *first;void nothing() {}:(void);(const TList<T>& l);

~TReverseIterator(void);<T>& operator++();& operator*();<T>& operator~();operator!();

};


2.6 Реализация класса TListException


class TListException

{:* errmsg;errnum;:();(char* m, int c);* GetMessage() const;GetCode() const;

~TListException();ostream& operator<<(ostream& os, const TListException& ex)

{<< endl << "\tCaught exception: " << ex.GetMessage() << " (" << .GetCode() << ")" << endl;os;

}

};

Полный исходный код программы приведен в Приложении А.

семантика класс контейнер итератор


Глава 3. Результаты


Для демонстрации работы программы был создан список l типа TList<int>, куда были добавлены 3 элемента. Затем был создан итератор прямого обхода, с помощью которого элементы были выведены на экран. После этого, итератором обратного обхода, значение каждого элемента списка было увеличено на единицу. В заключение итератором массива элементы были выведены на экран. Для проверки на экран выводится сам список, что показывает, что итераторы могут изменять значения элементов списка, обходить список, но не изменять положения внутреннего указателя в самом контейнере.

Результаты работы приведены на рисунке 2:


Рисунок 2 - Результаты работы


В ходе работы программы был создан контейнер для списка, наполнен элементами, после чего были созданы три итератора для работы с этим контейнером, что и требовалось при постановке задачи.




ЗАКЛЮЧЕНИЕ


В результате выполнения курсовой работы поставленная задача была решена. Были созданы контейнер для списка и три итератора для работы с этим контейнером.

При выполнении работы я познакомился и изучил основы объектно-ориентированного программирования, познакомился с таким понятием объекта как - класс. Изучил типы взаимодействия между ними, выбрал необходимые для решения поставленной задачи.

Применил полученные знания на практике. Результат - работающая программа, которая решает поставленную задачу.




СПИСОК ЛИТЕРАТУРЫ


1.Лафоре, Р Объектно-ориентированное программирование в C++. - 4-е изд. - М.: СПб.: Питер, 2010. - 923 с.

2.Лекция №3: Диаграмма классов: крупным планом // INTUI.ru

.Кораблев, В Самоучитель Visual C ++. NET / В. Кораблев. - СПб.: Питер: BHV, 2009. - 527 с.

.Павловская, Т.А. C++. Объектно-ориентированное программирование: практикум: учеб. пособие для вузов по спец. "Информатика и вычисл. техника" / Т.А. Павловская, Ю.А. Щупак. - СПб.: Питер, 2010. - 264 с.

.Объектное программирование // C++ для начинающих




ПРИЛОЖЕНИЕ (обязательное)


Полный код программы


Файл TList.h. Интерфейсная часть

#include <iostream>namespace std;<typename T>Elem

{row;<T>* next;

};<typename T>TListBasicIterator;<typename T>TList

{TListBasicIterator<T>;:<T>* first;<T>* cur;<T>& CreateFirst(T val);:operator=(const TList<T>&);(const TList<T>&);isEmpty();isEnd();& Rewind();& Set(T val);Get();& Next();& InsertAfterCurrent(T val);& AddLast(T val);& DeleteCurrent();(void);

~TList(void);ostream& operator<<(ostream& os, TList<T>& li)

{(li.isEmpty())

{<< "Empty";os;

}.Rewind();(!li.isEnd())

{<< li.Get() << " ";.Next();

}.Rewind();os;

}

};


Файл TList.cpp. Реализационная часть

#include "stdafx.h"

#include "TList.h"<typename T><T>& TList<T>::CreateFirst(T val)

{>first = new Elem<T>;>first->row = val;>first->next = nullptr;>cur = this->first;(*this);

}<typename T>TList<T>::operator=(const TList<T>&)

{TListException("=: forbidden operator.", 3);

}<typename T><T>::TList(const TList<T>&)

{TListException("copying list: forbidden act.", 3);

}<typename T>TList<T>::isEmpty()

{(this->first == nullptr);

}<typename T>TList<T>::isEnd()

{(this->cur == nullptr);

}<typename T><T>& TList<T>::Rewind()

{>cur = this->first;(*this);

}<typename T><T>& TList<T>::Set(T val)

{(this->isEnd())TListException("Set(): Out of List", 1);>cur->row = val;(*this);

}<typename T>TList<T>::Get()

{(this->isEnd())TListException("Get(): Out of List", 1);this->cur->row;

}<typename T><T>& TList<T>::Next()

{(this->isEnd())TListException("Next(): Out of List", 1);>cur = this->cur->next;(*this);

}<typename T><T>& TList<T>::InsertAfterCurrent(T val)

{(this->isEmpty())this->CreateFirst(val);<T>* temp = this->cur->next;>cur->next = new Elem<T>;>cur->next->next = temp;>cur->next->row = val;(*this);

}<typename T><T>& TList<T>::AddLast(T val)

{>Rewind();(this->isEmpty())this->CreateFirst(val);(this->cur->next != nullptr)

{>cur = this->cur->next;

}this->InsertAfterCurrent(val);

}<typename T><T>& TList<T>::DeleteCurrent()

{(this->isEnd())TListException("Delete(): Out of List", 1);(this->cur == this->first)

{>first = this->cur->next;this->cur;>cur = this->first;(*this);

}* ToDelete = this->cur;* Nex = this->cur->next;>cur = this->first;(this->cur->next != ToDelete)>cur = this->cur->next;* Prev = this->cur;>next = Nex;ToDelete;>cur = this->first;(*this);

}<typename T><T>::TList(void)

{>first = nullptr;>cur = this->first;

}<typename T><T>::~TList(void)

{>Rewind();(this->cur != nullptr)

{<T>* temp = this->cur->next;this->cur;>cur = temp;

}

}


Файл TLineIterator.h. Интерфейсная часть

#pragma once

#include "TListBasicIterator.h"<typename T>TLineIterator : public TListBasicIterator<T>

{:<T> *cur, *first;void nothing() {}:();(const TList<T>& l);<T>& operator++();& operator*();<T>& operator~();operator!();

~TLineIterator(void);

};


Файл TLineIterator. cpp. Реализационная часть

#include "stdafx.h"

#include "TLineIterator.h"<typename T><T>::TLineIterator()

{

}<typename T><T>::TLineIterator(const TList<T>& l) : TListBasicIterator(l)

{>first = basic_first;>cur = this->first;

}<typename T><T>& TLineIterator<T>::operator++()

{>cur = this->cur->next;(*this);

}<typename T>& TLineIterator<T>::operator*()

{this->cur->row;

}<typename T><T>& TLineIterator<T>::operator~()

{>cur = this->first;(*this);

}<typename T>TLineIterator<T>::operator!()

{(this->cur == nullptr);

}<typename T><T>::~TLineIterator(void)

{

}



Файл TArrayIterator.h. Интерфейсная часть

#pragma once

#include "tlistbasiciterator.h"<typename T>TArrayIterator :TListBasicIterator<T>

{:void nothing() {};:(void);

~TArrayIterator(void);(const TList<T>& l);Count();& operator[](int pos);

};


Файл TArrayIterator. cpp. Реализационная часть

#include "stdafx.h"

#include "TArrayIterator.h"<typename T><T>::TArrayIterator(void)

{

}<typename T><T>::~TArrayIterator(void)

{

}<typename T><T>::TArrayIterator(const TList<T>& l): (l)

{

}<typename T>TArrayIterator<T>::Count()

{_cur = basic_first;c = 0;(basic_cur != nullptr)

{_cur = basic_cur->next;++;

}c;

}<typename T>& TArrayIterator<T>::operator[](int pos)

{_cur = basic_first;(int i = 1; i <= pos - 1; i++)

{_cur = basic_cur->next;

}basic_cur->row;

}


Файл TReverseIterator.h. Интерфейсная часть

#pragma once

#include "tlistbasiciterator.h"<typename T>TReverseIterator :TListBasicIterator<T>

{:<T> *cur, *first;void nothing() {}:(void);(const TList<T>& l);

~TReverseIterator(void);<T>& operator++();& operator*();<T>& operator~();operator!();

};


Файл TReverseIterator. cpp. Реализационная часть

#include "stdafx.h"

#include "TReverseIterator.h"<typename T><T>::TReverseIterator(void)

{

}<typename T><T>::TReverseIterator(const TList<T>& l): (l)

{(basic_cur->next != nullptr)

{_cur = basic_cur->next;

}>first = basic_cur;>cur = this->first;

}<typename T><T>::~TReverseIterator(void)

{

}<typename T><T>& TReverseIterator<T>::operator++()

{(this->cur == nullptr)

{TListException("Out of List in Reverse Iterator", 2);

}(this->cur == basic_first)

{>cur = nullptr;(*this);

}_cur = basic_first;(basic_cur->next != this->cur)

{_cur = basic_cur->next;

}>cur = basic_cur;(*this);

}<typename T>& TReverseIterator<T>::operator*()

{this->cur->row;

}<typename T><T>& TReverseIterator<T>::operator~()

{>cur = this->first;(*this);

}<typename T>TReverseIterator<T>::operator!()

{(this->cur == nullptr);

}


Файл TListBasicIterator.h. Интерфейсная часть

#pragma once

#include "TList.h"<typename T>TListBasicIterator

{:void nothing() = 0;:<T>* basic_cur;<T>* basic_first;:();(const TList<T>& l);

~TListBasicIterator(void);

};


Файл TListBasicIterator.cpp. Реализационная часть

#include "stdafx.h"

#include "TListBasicIterator.h"<typename T><T>::TListBasicIterator()

{

}<typename T><T>::TListBasicIterator(const TList<T>& l)

{>basic_first = l.first;>basic_cur = this->basic_first;

}<typename T><T>::~TListBasicIterator(void)

{

}


Файл TListException.h. Интерфейсная часть

#pragma once

#include <iostream>namespace std;TListException

{:* errmsg;errnum;:();(char* m, int c);* GetMessage() const;GetCode() const;

~TListException();ostream& operator<<(ostream& os, const TListException& ex)

{<< endl << "\tCaught exception: " << ex.GetMessage() << " (" << .GetCode() << ")" << endl;os;

}

};


Файл TListException. cpp. Реализационная часть

#include "stdafx.h"

#include "TListException.h"

#include <iostream>namespace std;::TListException()

{>errmsg = "";>errnum = 0;

}::TListException(char* m, int c)

{>errmsg = m;>errnum = c;

}* TListException::GetMessage() const

{this->errmsg;

}TListException::GetCode() const

{this->errnum;

}::~TListException()

{

}


Файл Main.cpp (основная программа)

// Effective.cpp: определяет точку входа для консольного приложения.

//

#include "stdafx.h"

#include <iostream>namespace std;

#include "TListBasicIterator.h"

#include "TArrayIterator.h"

#include "TLineIterator.h"

#include "TReverseIterator.h"

#include "TListException.h"_tmain(int argc, _TCHAR* argv[])

{<int> l;.AddLast(1).AddLast(2).AddLast(3);<int> iter(l);<< "List contains: ";(~iter; !!iter; ++iter)

{<< *iter << " ";

}

//cout << endl << "Reversive: ";<int> rev(l);(~rev; !!rev; ++rev)

{

*rev = *rev + 1;

}<< endl << "Like an Array: ";<int> arr(l);c = arr.Count();(int i = 1; i <= c; i++)

{<< arr[i] << " ";

}<< endl;<< "Through <cout>: " << l << endl;_s("%d");0;

}


Реализация концепции контейнеров и итераторов на примере однонаправленного связанного списка

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ