Проектирование и реализация абстракций типов данных
Содержание
Введение
Текст программы
Результаты выполнения программы
Описание программы
Заключение
Список использованных источников
Введение
Денис Ричи
разработал и первым реализовал язык программирования C на DEC PDP-11 с
операционной системой UNIX. Язык является результатом разработки старого языка
BCPL. Мартин Ричард разработал BCPL под влиянием созданного Кеном Томсоном
языка B, который привел к разработке C в 1980 году.
В течение
многих лет стандартом C де-факто была версия, поставляемая для операционной
системы UNIX System V. Растущая популярность компьютеров привела к созданию
множества приложений для C.
C часто называют языком среднего уровня. Это определение означает, что он
объединяет элементы языков высокого уровня с функциональностью ассемблера.
Известно, какое значение приобретает сегодня объектно-ориентированное
программирование, учитывая возрастающие требования к качеству, надежности и
пользовательскому интерфейсу приложений. Сложность и объем программ все время
растут. В свете этого объектно-ориентированные языки, и прежде всего C++,
становятся едва ли не единственным средством решения встающих перед
программистом задач.
Наиболее важным понятием в объектно-ориентированном программировании
является понятие объекта. Объект-это логическая единица, которая содержит
данные и правила (методы) обработки этих данных. В языке С++ в качестве таких
правил обработки выступают функции.
Чтобы определить объект в С++ , надо сначала определить его форму с
помощью ключевого слова class.
Описание класса производится следующим образом:
сlass: <имя>
{
[< спецификатор видимости>]
< член класса>
…
};
Спецификатор видимости определяет степень доступности членов класса и
может принимать значения:(закрытый) - доступный только внутри методов и друзей
этого класса;(защищенный) - доступный только внутри методов, друзей этого
класса и производных от него классов;(открытый) - доступный из произвольной
программной среды.
Членами класса могут быть:
●Информационные поля ,которые определяются как поля структуры;
●Операции- функции члена класса, которые определяются как прототипы
функций.
Очевидно, что функции члены класса должны компилироваться всегда, когда
вносится какое-либо изменение в описание класса. В идеале такое изменение никак
не должно отражаться на пользователях класса. К сожалению, это не так. Для
размещения переменной классового типа компилятор должен знать размер объекта
класса. Если размер этих объектов меняется, то файлы, в которых класс
используется, нужно компилировать заново.
Этой сложности можно избежать, представив каждый объект класса как
указатель на «настоящий» объект. Так как все эти указатели будут иметь
одинаковый размер, а размещение «настоящих» объектов можно определить в файле,
где доступна закрытая часть, то это может решить проблему. Однако решение
подразумевает дополнительные ссылки по памяти при обращении к членам класса,
(т.е включает по меньшей мере один вызов программ выделения и освобождения
свободной памяти).
Но почему же пользователям класса не разрешается обращаться к закрытым членам,
почему их описания должны приводиться в заголовочных файлах, которые, как
предполагается, пользователь читает? Ответ - эффективность. Во многих системах
и процесс компиляции, и последовательность операций, реализующих вызов функции,
проще, когда размер автоматических объектов известен во время компиляции.
Подобно функциям, классы также могут быть параметризованы одним или
несколькими типами. Типичным примером такой возможности могут служить классы с
неизвестными заранее типами элементов, которые реализуются с помощью шаблонов
классов. В качестве примера рассмотрим шаблон класса, реализующий очередь.
Файл UnQLimSz.h
Содержит стандартные и пользовательские включаемые файлы и определение
шаблонного класса для работы с универсальной очередью ограниченного размера на
базе массива. В шаблоне классов реализованы следующие операции с очередью:
* инициализация очереди (конструктор);
* разрушение очереди с освобождением занятой динамической памяти
(деструктор);
* занесение элемента с левого конца;
* занесение элемента с правого конца;
* извлечение элемента с левого конца;
* извлечение элемента с правого конца;
* печать состояния очереди с использованием указателя на левый конец
очереди;
* печать состояния очереди с использованием указателя на правый конец
очереди.
Добавление элемента в правый конец очереди< class T
>UnQueueLimSize< T > :: AddRight(
// false - элемент не добавленT
&add ) // Данное для добавляемог элемента
{
// Очередь заполнена?( Size>=MaxSize )
{false;
}
// Добавляем элемент в очередь= ( Right+1 ) % MaxSize; pQueue[ Right ] =
add;++;true;
}
// Добавление элемента в левый конец очереди< class T
>UnQueueLimSize< T > :: AddLeft(
// false - элемент не добавленT
&add ) // Данное для добавляемого элемента
{
// Очередь заполнена?( Size>=MaxSize )
{false;
}
// Добавляем элемент в очередь[ Left ] = add;= ( Left+MaxSize-1 ) %
MaxSize; Size++;true;
}
// Извлечение элемента из левого конца очереди< class T
>UnQueueLimSize< T > :: OutLeft(
// false - извлечение не выполнено&out ) // Значение, которое
извлекли
{
// Очередь пуста?( Size==0 )
{false;
}
// Извлекаем элемент из очереди= ( Left+1 ) % MaxSize; out = pQueue[ Left
];-;true;
}
// Извлечение элемента из правого конца очереди< class T
>UnQueueLimSize< T > :: OutRight(
// false - извлечение не выполнено&out ) // Значение, которое
извлекли
{
// Очередь пуста?( Size==0 )
{false;
}
// Извлекаем элемент из очереди= pQueue[ Right ];= ( Right+MaxSize-1 ) %
MaxSize; -;true;
}
#include "stdio.h"
#include "conio.h"
#include <iostream>
#include <cstdlib>
#include <iostream>
#include <cstdlib>namespace std;<class T>Queue // класс
очередь
{strucelem // встроенный класс
{:data;// информационное поле* next;// адресное поле* prev;() { next =
0;prev = 0;}// конструктор
};* BeginQ;// указатель на первый элемент* LastQ;// указатель на
предыдущий элемент:();// коструктор
~Queue();// деструкторPrintQueue();// печать очередиAddQueue(T data);//
добавление элементов в очередьCheckQueue();// проверка состояния
очередиDelQueue();// удаление из очередиDeleteQueue();// удаление очереди
};
// Конструктор.<class T><T> :: Queue() {= 0;= 0;
}
// Деструктор - освобождаем очередь и память выделенную под
объекты.<class T><T> :: ~Queue() {*work;(BeginQ) {=
BeginQ->next;BeginQ;= work;
}= NULL;= NULL;
}
//Печать очереди<class T> void Queue<T>::PrintQueue()
{*p = BeginQ;<< endl << "Очередь: ";(p)
{<<p->data<<' ';= p->next;
}<< endl;
}
// Положить в очередь.<class T>Queue <T> :: AddQueue(T data)
{* link = new strucelem;
(BeginQ == NULL) {>data = data;= link;= link;
}{>data = data;>next = link;= LastQ->next;
}
}
// Проверить состояние очереди.<class T>Queue <T> ::
CheckQueue() {(BeginQ) return true;return false;
}
// Изъять из очереди.<class T>Queue <T> :: DelQueue()
{*link;p;(BeginQ != NULL) {= BeginQ;= BeginQ->next;(BeginQ == NULL) = 0;=
link->data;link;
// return p;
}
//else return 0;
}
// Очистить очередь.<class T>Queue <T> :: DeleteQueue() {*
link;(BeginQ) {= BeginQ;= BeginQ->next;(!BeginQ) LastQ = 0;link;
}
}main(){(LC_ALL,"Russian");
// Формирование
очереди<int> d;iCount = 1;<<"Введите количество элементов (по
умолчанию 1):"; >>iCount;(iCount <= 0) = 1; n = 0;(int i=0;
i<iCount; i++){<<"\nВведите число =";>>n;.AddQueue(n);
}.PrintQueue();
//data_int.CheckQueue();
//data_int.PrintQueue();
//Добавление элементов
<<"Введите кол-во элементов на добавление:"; >>
iCount;(int i=0; i<iCount; i++){<<"\nВведите число
=";>>n;.AddQueue(n);
}.PrintQueue();
// Удаление
элементов<<"Введите кол-во элементов на удаление:"; >>
iCount;(int i=0; i<iCount; i++).DelQueue();.PrintQueue();<<"
удаление очереди:"; .DeleteQueue();.PrintQueue();("pause");0;
}
Результаты
3 Описание
программы
Программа предназначена для работы с универсальной очередью при
использовании шаблона класса. В шаблоне класса необходимо предусмотреть методы,
выполняющие создание очереди установленного типа, добавление и удаление
элементов, вывод содержимого очереди на экран, а также инициализацию и удаление
очереди.
Спроектируем шаблон класса Queue с типом T.
Определим интерфейс шаблона класса Queue:
Конструктор Queue ()
Назначение: создает объект класса Queue, т. е. создает очередь,
выделяет динамическую память для хранения объекта.
Деструктор ~ Queue ()
Назначение: удаляет выделенную для объекта-очереди память.
Методы:
Добавление элемента n в очередь PutQueue(T data)
Удаление элемента из очереди T GetQueue()
Вывод очереди на экран PrintQueue()
Удаление очереди ClearQueue();
Проверка состояния очереди СheckQueue()
Свойства:
T data - информационное поле объекта-очереди;* next- указатель
на следующий элемент(адресное поле)* prev - указатель на предыдущий элемент*
BeginQ - указатель на первый элемент;* LastQ - указатель на предыдущий элемент;
Заключение
объектное ориентированное программирование очередь
При выполнении курсового проекта был спроектирован шаблон класса для
работы с универсальной очередью с методами создания очереди установленного
типа, добавления и удаления элементов очереди, вывода содержимого очереди на
экран, а также инициализацию и удаление очереди.
В процессе курсового проектирования была разработана программа на языке
C++, реализующая выполнение описанных выше функций.
Список
использованных источников
1. Герберт Шилдт «Справочник программиста по C/C++, второе
издание» - Москва - Санкт-Петербург - Киев 2001 г.
2. Т.А. Павловская «C/C++ программирование на языке
высокого уровня» - Москва - Санкт-Петербург 2005 г.
. Р. Лафоре « Объектно- ориентированное
программирование в С++, четвертое издание» - Москва - Санкт-Петербург - Минск
2004 г.