Темы рефератов по c
Обновлено: 08.07.2024
Объектно-ориентированное программирование в С++. Контейнер как способ организации хранения данных. Алгоритмы сортировки, копирования, поиска и объединения. Списки и их методы. Вектор, его основные методы и преимущества. Контейнерные классы и итераторы.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 02.07.2014 |
| Размер файла | 961,7 K |
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Язык программирования С++
С++ - язык программирования, который поддерживает такие парадигмы программирования как процедурное программирование, объектно-ориентированное программирование, обобщенное программирование, обеспечивает модульность, раздельную компиляцию, обработку исключений, абстракцию данных, объявление типов (классов) объектов, виртуальные функции. Стандартная библиотека включает, в том числе, общеупотребительные контейнеры и алгоритмы. C++ сочетает свойства как высокоуровневых, так и низкоуровневых языков. В сравнении с его предшественником - языком C, - наибольшее внимание уделено поддержке объектно-ориентированного и обобщённого программирования.
Синтаксис C++ унаследован от языка C. Одним из принципов разработки было сохранение совместимости с C. Тем не менее, C++ не является в строгом смысле надмножеством C; множество программ, которые могут одинаково успешно транслироваться как компиляторами C, так и компиляторами C++, довольно велико, но не включает все возможные программы на C.
1. Общая характеристика работы
1.1 Актуальность темы
Язык программирования С++ является одним из самых употребляемых в настоящее время. Достаточно часто возникает задача ведения базы данных при минимальных затратах памяти. В этом случае применяется объектно-ориентированный подход с использованием стандартной библиотеки шаблонов (STL). В своей работе я использовала класс контейнера - вектор.
Целью данной работы является изучение стандартной библиотеки шаблонов (STL) языка С++ и создание собственной базы данных.
1.3 Задачи работы
Для достижения цели следует решить поставленные задачи:
1) создание собственной базы данных;
2) реализовать возможности добавления новых элементов;
3) реализовать возможность замены одного из элементов;
4) реализовать возможность поиска по заданным критериям;
5) реализовать возможность удаления одного из элементовж
6) реализовать возможность вывода всех данных;
2 Общая характеристика
2.1 Теоретическое введение
2.1.1 Введение в STL
В STL содержится несколько основных сущностей. Три наиболее важные из них -- это контейнеры, алгоритмы и итераторы. Контейнер -- это способ организации хранения данных (стек, связный список, очередь). Еще один контейнер -- это массив, но он настолько тривиален и популярен, что встроен в C++ и большинство других языков программирования. Контейнеры бывают самые разнообразные, и в STL включены наиболее полезные из них. Контейнеры STL подключаются к программе с помощью шаблонных классов, а значит, можно легко изменить тип хранимых в них данных. Под алгоритмами в STL подразумевают процедуры, применяемые к контейнерам для обработки их данных различными способами. Например, есть алгоритмы сортировки, копирования, поиска и объединения. Алгоритмы представлены в STL в виде шаблонных функций. Однако они не являются методами классов-контейнеров. Наоборот, это совершенно независимые функции. На самом деле, одной из самых привлекательных черт STL является универсальность ее алгоритмов. Их можно использовать не только в объектах классов-контейнеров, но и в обычных массивах и даже в собственных контейнерах. (Контейнеры, тем не менее, содержат методы для выполнения некоторых специфических задач.) Итераторы -- это обобщение концепции указателей: они ссылаются на элементы контейнера. Их можно инкрементировать, как обычные указатели, и они будут ссылаться последовательно на все элементы контейнера. Итераторы -- ключевая часть всего STL, поскольку они связывают алгоритмы с контейнерами. Их можно представить себе в виде кабеля, связывающего колонки вашей стереосистемы или компьютер с его периферией.
Контейнер -- это объект, который может содержать в себе другие объекты. Существует несколько разных типов контейнеров(см.рис.1). Например, класс vector определяет динамический массив, deque создает двунаправленную очередь, а list представляет связный список. Эти контейнеры называются последовательными контейнерами (sequence containers), потому что в терминологии STL последовательность -это линейный список. STL также определяет ассоциативные контейнеры (associative containers), которые обеспечивают эффективное извлечение значений на основе ключей.
Таким образом, ассоциативные контейнеры хранят пары “ключ/значение”. Примером может служить map. Этот контейнер хранит пары “ключ/значение”, в которых каждый ключ является уникальным. Это облегчает извлечение значения по заданному ключу.
Ассоциативный контейнер -- это уже несколько иная организация
2.1.3 Контейнерные классы
Каждый контейнер имеет определенный для него аллокатор (allocator). Аллокатор управляет выделением памяти для контейнера. Аллокатором по умолчанию является объект класса allocator, но вы можете определять свои собственные аллокаторы, если это необходимо для специализированных приложений. Для большинства применений аллокатора по умолчанию вполне достаточно.
Контейнеры реализованы посредством шаблонных классов. Например, ниже показа- на спецификация шаблона контейнера deque. Все контейнеры используют схожие спе- цификации: template > class deque Здесь обобщенный тип T специфицирует тип объектов, хранящихся в deque. Аллокатор, используемый deque, специфицирован Allocator; по умолчанию это стан- дартный класс для аллокаторов. Для подавляющего большинства приложений вы будете просто применять аллокатор по умолчанию, то же касается всего кода этой главы. Однако вы можете определять собственные типы аллокаторов, когда требуется специальная схема выделения памяти.
Итераторы -- это объекты, которые ведут себя более или менее подобно указателям. Они предоставляют возможность выполнять циклическую обработку элементов контейнера -- подобно тому, как вы используете указатель для организации цикла по массиву. Существует пять типов итераторов(см.рис.2)
Вообще итератор, имеющий более широкие возможности доступа, может применяться вместо итератора с меньшими возможностями. Например, прямой итератор может быть использован вместо входного итератора. Итераторы обрабатываются подобно указателям. Обратные итераторы либо двунаправлены, либо произвольного доступа, которые перемещаются по последовательности в обратном направлении. Таким образом, если обратный итератор указывает на конец последовательности, то увеличение этого итератора на единицу переместит его на элемент, предшествующий конечному.
Все итераторы должны поддерживать типы операций с указателями, допустимые для их категории. Например, класс входного итератора должен поддерживать операции ->, ++, *, == и !=. Более того, операция * не может использоваться для присваивания значения.
В отличие от входного, итератор произвольного доступа должен поддерживать операции ->, +, ++, -, --, *, , =, -=, +=, ==, != и [].
Вдобавок операция * должна позволять присваивание. Операции, поддерживаемые каждым типом итераторов, перечислены ниже(см.рис.3).
При ссылках на различные типы итераторов в описаниях шаблонов будут использованы следующие термины(см.рис.4).
Алгоритмы выполняют действия над контейнерами. Их возможности включают инициализацию, сортировку, поиск, слияние, замену и трансформацию содержимого контейнера. Многие алгоритмы оперируют диапазонами элементов в контейнере.
find ()- этот алгоритм ищет первый элемент в контейнере, значение которого равно указанному.
count()-подсчитывает, сколько элементов в контейнере имеют данное значение.
search()-ищет целую последовательность значений, заданную одним контейнером, в другом контейнере.
merge()-этот алгоритм работает с тремя контейнерами, объединяя элементы двух из них в третий, целевой контейнер.
for_each ()-этот алгоритм позволяет выполнять некое действие над каждым элементом в контейнере. Вы пишете собственную функцию, чтобы определить, какое именно действие следует выполнять. Эта ваша функция не имеет права модифицировать данные, но она может их выводить или использовать их значения в своей работе.
transform()-этот алгоритм тоже делает что-то с каждым элементом контейнера, но еще и помещает результат в другой контейнер (или в тот же). Опять же, пользовательcкая функция определяет, что именно делать с данными, причем тип возвращаемого ею результата должен соответствовать типу целевого контейнера.
2.1.6 Списки и их методы
Контейнер STL под названием список представляет собой дважды связный список, в котором каждый элемент хранит указатель на соседа слева и справа. Контейнер содержит адрес первого и последнего элементов, поэтому доступ к обоим концам списка осуществляется очень быстро.
push_front(), front() и pop_front() аналогичны методам pop_back() из векторов.
2.1.7 Вектор. Его методы и преимущества
Векторы -- это, так сказать, умные массивы. Они занимаются автоматическим размещением себя в памяти, расширением и сужением своего размера по мере вставки или удаления данных. Векторы можно использовать в какой-то мере как массивы, обращаясь к элементам с помощью привычного оператора []. Случайный доступ выполняется очень быстро в векторах. Также довольно быстро осуществляется добавление (или проталкивание) новых данных в конец вектора. Когда это происходит, размер вектора автоматически увеличивается для того, чтобы было, куда положить новое значение.
Так же существует достаточно большое количество полезных методов для вектора:
push_back() - вставляет значение своего аргумента в конец вектора
size() - возвращает текущее число элементов, содержащихся в контейнере.
swap() - обменивает данные одного вектора на данные другого, при этом порядок следования элементов не изменяется
back() - возвращает значение последнего элемента вектора
insert - имеет два параметра: будущее расположение нового элемента в контейнере и значение элемента.
erase() - удаляет элемент из указанной позиции
Благодаря описанным преимуществам, с помощью вектора можно достаточно просто создать базу данных, что и необходимо в моей курсовой работе. Поэтому из всех типов контейнеров в STL я выбрала именно вектор.
Важной вехой в развитии программирования явилось создание и широкое распространение языка С++. Этот язык, сохранив средства ставшего общепризнанным стандартом для написания системных и прикладных программ языка С (процедурно-ориентированный язык), ввел в практику программирования возможности нового технологического подхода к разработке программного обеспечения, получившего название “объектно-ориентированное программирование”. Внедрение в практику программирования объектно-ориентированной парадигмы дает развитие новых областей информатики, значительное повышение уровня технологичности создаваемых программных средств, сокращение затрат на разработку и сопровождение программ, их повторное использование, вовлечение в процесс расширения интеллектуальных возможностей ЭВМ. Объектный подход информационного моделирования предметных областей все более успешно применяется в качестве основы для структуризации их информационных отражений и, в частности, баз знаний.
1. История развития языков программирования
Первые компьютеры появились в конце Великой Отечественной Войны сначала в Соединенных Штатах Америки, а позже в СССР. Эти машины могли решать ограниченный класс задач.
Кодирование происходило на физическом уровне. Сначала программы хранились на перфокартах. Таким образом, процесс отладки программы занимал очень много времени. Позже появились магнитные ленты и магнитные диски, что облегчило задачу переносимости программ.
В конце 1950 – начале 1960 годов появились языки программирования Fortran(FORmulaTRANslation) и Cobol(COmmonBusinessOrientedLanguage)-язык, ориентированный на выполнение общих экономических расчетов.
В 1960-70 годах было написано множество языков программирования. Почти каждый программист придумывал свой язык, мечтая увековечить свое имя.
В конце 1970-х появились Паскаль, Модула, Си, которые широко применялись.
В начале 1980-х широкое распространение получили персональные компьютеры. Примерно в это же время появился язык C++.
Естественно, что C++ более всего близок к языку C. Язык С полностью включен в C++, оставлены все возможности С как языка низкого уровня для выполнения наиболее сложных и универсальных программ. Другим источником вдохновения был язык Simula67; оттуда заимствованы концепции классов и производных классов с виртуальными функциями.
Название языка C++ возникло летом 1983 года. Более ранние версии, известные под именем “C с Классами”, используются с 1980 года. Первоначально язык возник в процессе создания программы событийно-управляемой симуляции, для которой идеально подошел бы язык Simula67, если бы не соображения эффективности. “C с Классами” использовался для основных проектов по симуляции только в программах, критичных по времени выполнения и объему используемой памяти. C++ впервые возник вне группы автора в июле 1983года, однако он уже тогда практически не отличался от современной версии языка.
Название “C++ “ было предложено Риком Масцитти и символизирует эволюционные изменения, произошедшие с языком C(“++” – обозначение оператора инкрементации в языке C).
Таким образом, эволюцию языков можно показать на схеме:
Коды Ассемблеры Языки высокого Объектно-ориентированное и уровня модульное программирование
2. Основы объектно-ориентированного программирования:
Объектно-ориентированное программирование – это самый высокоуровневый вид программирования в настоящее время. Здесь поддерживаются достижения предыдущих поколений и добавлены новые свойства. Эти новые свойства реализуют парадигму объектно-ориентированного программирования.
Объектно-ориентированное программирование на C++ основывается на следующих основных этапах разработки программ.
Первый этап заключается в выделении абстракций. Выделение абстракций означает анализ предметной области, для которой составляется программа, с целью определения основных объектов предметной области, их свойств, отношений между объектами, а также возможных операций над объектами и их составляющими.
Второй этап состоит в типизации объектов и синтезе абстрактных типов данных.
Этап предполагает определение новых производных типов данных и наборов специфических функций или операций, применяемых к этим типам данных таким образом, чтобы исключить возможность смешивания или взаимозамены различных типов.
Третий этап заключается в объектной декомпозиции как выделении подтипов или подобъектов и их составляющих для каждого из типов объектов.
Четвертый этап представляет собой композиционную иерархизацию объектов как выделение родовидовых и композиционных отношений над объектами.
В результате объектно-ориентированного подхода к проектированию программ процесс разработки программы превращается в процесс эволюционного программирования, который для внесения каких-либо изменений и дополнений в программу не требует кардинального пересмотра составляющих ее алгоритмов. Эволюционный способ программирования опирается на сохранение целостности объектов программы, то есть внесение изменений в программу не должно затрагивать внутреннюю организацию существующих в ней объектов.
Важным свойством объектно-ориентированных языков является возможность разработки на них программ, работающих в системах со сложными параллельными вычислительными процессами, изначально присущими техническим средствам вычислительной техники. Это свойство опирается на концепцию активных и неактивных объектов в период функционирования программы. Одновременная активность различных объектов становится возможной за счет их строгой типизации и закрытости для изменений другими объектами.
Язык программирования C++ обладает всеми основными свойствами языков объектно-ориентированного программирования и существенно отличается по своей концепции от базового языка C.
Существует несколько принципов, лежащих в основе языка C++:
1. Инкапсуляция – это объединение производного типа данных с набором функций, используемых при работе с этим типом, в единый класс. При этом функции, включенные в класс, называются методами класса, данные – элементами данных, а конкретные представители класса – объектами класса. Закрытие данных и методов оперирования этими данными происходит таким образом, чтобы обращаться можно было бы только определенным объектам (в данном случае только объектам этих типов).
2. Наследование – это способность одних классов заимствовать основные свойства других классов, в частности – методы классов и элементы данных. Класс, наследующий свойства, называют производным, а класс, предоставляющий свои свойства для наследования, - базовым. Механизм наследования позволяет создавать иерархию классов, то есть многоуровневую систему классов, связанных между собой отношением наследования.
3. Полиморфизм – это возможность определения функции, работающей с различными по типу данных списками параметров в пределах какого-либо одного вида алгоритмов. Такие функции называются обычно виртуальными и проектируются как некоторое семейство одноименных функций, работающих с различными типами данных. Механизм, реализующий выбор какой-либо конкретной функции из определенного семейства, носит название механизма позднего связывания, поскольку может быть использован в процессе выполнения готовой программы.
Центральным понятием объектно-ориентированного программирования является понятие класса. Именно он реализует основные свойства: инкапсуляцию, наследование, полиморфизм.
Класс представляет собой тип, определяемый пользователем. Этот тип включает в себя совокупность полей данных и функций для работы с этими полями.
Отнесение переменной к какому-то типу данных определяет память, выделяемую для этой переменной и набор операций и функций, применяемых к таким переменным. Реализация этих принципов для типов, определяемых пользователем, осуществляется при помощи классов.
Существует ряд соображений, по которым было бы целесообразно ограничить доступ к элементам данных класса. К наиболее важным из них относятся следующие:
- ограничение доступа к данным класса рамками тех функций, которые включены программистом в этот класс, позволяет локализовать программные ошибки практически до начала работы программы;
- описание класса в этом случае позволяет пользователям классов более просто знакомиться с новыми библиотеками классов;
- при ограничении доступа упрощается корректировка программ, поскольку для их изменения достаточно скорректировать описание класса и функции, являющиеся его членами, не внося изменений в те места программы, где используются объекты класса;
- функциональное разграничение классов делает возможной разработку программ, использующих концепцию параллельных процессов.
Этим спецификатором помечается группа данных и функций, которые доступны другим функциям программы.
Помечаются защищенные данные и, возможно, функции, если есть необходимость. Эти элементы доступны только функциям - членам данного класса и производных от него классов, то есть тех классов, которые объявят себя приемниками данного.
Служит для задания данных и функций, доступных только функциям данного класса. Это частные данные.
По умолчанию элементы считаются частными (private) для класса и открытыми (public) для структуры (объединения также относят к классам).
Классы лучше определять в файле с расширением .h, а реализацию в файле с тем же именем, но с расширением .cpp или .c. Чаще всего класс по одиночке не определяется, а создаются библиотеки.
Для иллюстрации рассмотрим пример класса, который задает координату на экране:
Location (int _x, int _y); //конструктор
void setx(int nx);
void sety(int ny);
В данном примере, использовав спецификаторpublic, мы сделали открытыми для других функций методы, описанные в классе.
Определить функции – члены класса можно внутри описания класса или за его пределами. В первом случае функция считается встраиваемой. Встраиваемая функция характерна тем, что компилятор C++, обрабатывая вызовы этой функции в программе, заменяет их не на вызов функции как подпрограммы, а непосредственно на объектный код, соответствующий определению этой функции. Вследствие сказанного, программист должен принимать во внимание, что встраиваемые функции, как правило, имеют короткие определения. В качестве примера можно привести определение функций Getx() и Gety().
Для определения функции – члена класса за пределами описания класса необходимо определить ее где-либо в программе после определения класса, членом которого она является.
void Location :: setx(int nx)
void Location :: sety(int ny)
Location :: Location (int _x, int _y)
Операция разрешения контекста (::) позволяет указать компилятору, к какому из классов принадлежит определяемая функция.
Имя класса в определении пишется для того, чтобы компилятор однозначно определил к какому классу принадлежит данная функция, так как функции – члены различных классов могут иметь одинаковые имена.
При определении классов не происходит реального выделения памяти под объекты этого класса, а создаются лишь новые производные типы данных, для которых будут использоваться функции – члены класса.
Для того, чтобы начать работу с реальными объектами какого-либо класса, эти объекты необходимо сначала определить. При этом в программе необходимо указать имя класса, объект которого должен быть создан, а также имя самого объекта. У каждого из классов может быть произвольное число объектов.
4. Конструкторы и деструкторы
Конструктором называется функция-член класса, которая выделяет память под поля данных класса и производит их инициализацию, т.е. задает начальные значения в месте объявления переменных.
Имя конструктора совпадает с именем класса. Например, в классеLocation конструктор имеет следующий вид: Location (int _x, int _y).
Конструктор не возвращает никакого значения, даже void.
Одним из важных свойств конструктора является его автоматический вызов при описании любого объекта какого-либо класса, использующего конструктор, что снимает с программиста задачу своевременного отслеживания инициализации вновь вводимых объектов.
В общем случае конструкторы классов могут иметь списки параметров, которые могут потребоваться при инициализации. При этом программист будет обязан задать список инициализации при описании каждого нового объекта.
Конструкторов в классе может быть много. В этом случае реализуется механизм перегрузки функции.
Если конструкторы не объявлены, компилятор сам создает конструктор без параметров по умолчанию.
Объявление объектов можно проиллюстрировать следующим образом:
8. Перегрузка операций
На все операции языка C++, кроме операций объявления, new, delete, и других операций, связанных с определением производных типов данных, распространяется свойство полиморфизма, т.е. возможности использования в различных случаях для одной и той же операции операндов различных типов. Так, например, операция сложения позволяет “смешивать” типы int, double, float и другие в одном выражении. Такой полиморфизм обеспечен внутренними механизмами языка C++.
Таким образом, нельзя перегружать такие операции: . :: * ?:
Чтобы появилась возможность использовать стандартную для языка C++ операцию с необычными для нее данными, необходимо специальным образом определить ее новое поведение. Это возможно, если хотя бы один из операндов является объектом некоторого класса, т.е. введенного пользователем типа. В этом случае применяется механизм, во многом схожий с механизмом определения функций. Для распространения действия операции на новые пользовательские типы данных программист определяет специальную функцию, называемую “операция-функция” (operatorfunction). Формат определения операции-функции:
тип_возвращаемого_значения operator знак_операции (спецификация параметров операции-функции)
При необходимости может добавляться и прототип операции-функции с таким форматом:
тип_возвращаемого_значения operator знак_операции (спецификация параметров операции-функции);
И в прототипе, и в заголовке определения операции-функции используется ключевое слово operator, вслед за которым помещен знак операции. Если принять, что
конструкция operator знак_операцииесть имя некоторой функции,то определение и прототип операции-функции подобны определению и прототипу обычной функции языка C++. Например, для распространения действия бинарной операции * на объекты класса T может быть введена функция с заголовком Toperator *(Tx, Ty).
Определенная таким образом операция (в нашем примере операция “ звездочка”) называется перегруженной (по-английски - overload), а сам механизм – перегрузкой или расширением действия стандартных операций языка C++.
Количество параметров у операции-функции зависит от арности операции и от способа определения функции. Операция-функция определяет алгоритм выполнения перегруженной операции, когда эта операция применяется к объектам класса, для которого операция-функция введена. Чтобы явная связь с классом была обеспечена, операция-функция должна быть либо компонентом класса, либо она должна быть определена в классе как дружественная, либо у нее должен быть хотя бы один параметр типа класс (или ссылка на класс).
Если для класса T введена операция-функция с приведенным выше заголовком и определены два объекта A и B класса T,то выражение A*B интерпретируется как вызов функции operator * (A,B).
Рассмотрим пример. Реализуем перегрузку операции сложения для класса комплексных чисел.
comp(float i, float r)
comp operator +(comp X)
comp C1(1,1), C2(5,5),C3;
C3=C1.operator+(C2) // Прямой вызов операции-функции. Не используется.
C3=C1+C2 // Косвенный вызов операции-функции.
Компилятор по типам объектов С1 и С2 определяет, что необходимо реализовать не просто сложение двух скаляров, как это бывает в обычном использовании операции +, а вызвать перегруженную функцию operator +.Так как при определении класса поля im и real доступны функциям класса, есть необходимость определять только второй объект (X в нашем примере).
В языке C++ требуется, чтобы операции присваивания, индексации и косвенного обращения к полям класса (->) обязательно определялись как методы, т.е. как функции-члены класса.
Когда левый операнд операции является представителем класса, перегруженную операцию нужно определять как метод этого класса.
Для многих операций C++ существуют свои особенности при перегрузке (доопределении). Так, унарные операции переопределяются с описанием операции-функции без аргумента, например:
Соответственно доопределение бинарной операции использует описание операции-функции с одним аргументом, т.к. вторым является объект, для которого вызвана операция. Следует также помнить, что операция присваивания “=” может перегружаться только объявлением метода без описателя static. То же относится к операциям “()” и ”[]”.
Посмотрим, как будет выглядеть перегрузка операции присваивания для примера с комплексными числами.
comp & operator =([const] comp & X)
Если указываем const, то это показывает, что параметр не должен изменяться внутри функции, а кроме того, позволяет обрабатывать константные объекты.
Операция присваивания не наследуется.
Константные объекты и константные методы
constLocNK(0,0); //константный объект
После инициализации попытки изменения константного объекта отслеживаются и пресекаются компилятором.
Объявление константной функции в теле класса выглядит следующим образом:
1) не должны менять значения элементов класса;
2) не должны вызывать другие неконстантные методы класса.
Константные методы могут применяться как для константных, так и для неконстантных объектов.
1. М.Уэйт, С.Прата, Д.Мартин Язык Си: Пер с англ.-М.: Мир, 1988.-463 с.,ил.
2. Уинер Р. Язык Турбо Си: Пер с англ.-М.: Мир, 1991.-384 с.,ил.
3. Берри Р., Микинз Б. Язык Си: введение для программистов: Пер. с англ.-М.:Финансы и статистика, 1988.-с.,ил.
Читайте также: