Проектирование и реализация абстракций типов данных

1 Текст программы

2 Результаты выполнения программы

3 Описание программы

Заключение

Список использованных источников

Денис Ричи разработал и первым реализовал язык программирования C на DEC PDP-11 с операционной системой UNIX. Язык является результатом разработки старого языка BCPL. Мартин Ричард разработал BCPL под влиянием созданного Кеном Томсоном языка B, который привел к разработке C в 1980 году.

В течение многих лет стандартом C де-факто была версия, поставляемая для операционной системы UNIX System V. Растущая популярность компьютеров привела к созданию множества приложений для C.

C часто называют языком среднего уровня. Это определение означает, что он объединяет элементы языков высокого уровня с функциональностью ассемблера.

Известно, какое значение приобретает сегодня объектно-ориентированное программирование, учитывая возрастающие требования к качеству, надежности и пользовательскому интерфейсу приложений. Сложность и объем программ все время растут. В свете этого объектно-ориентированные языки, и прежде всего C++, становятся едва ли не единственным средством решения встающих перед программистом задач.

Наиболее важным понятием в объектно-ориентированном программировании является понятие объекта. Объект-это логическая единица, которая содержит данные и правила (методы) обработки этих данных. В языке С++ в качестве таких правил обработки выступают функции.

Чтобы определить объект в С++, надо сначала определить его форму с помощью ключевого слова class.

Описание класса производится следующим образом:

сlass: <�имя>

{

[< спецификатор видимости>]

< член класса>

…

};

Спецификатор видимости определяет степень доступности членов класса и может принимать значения:

private (закрытый) — доступный только внутри методов и друзей этого класса;

protected (защищенный) — доступный только внутри методов, друзей этого класса и производных от него классов;

public (открытый) — доступный из произвольной программной среды.

Членами класса могут быть:

?Информационные поля, которые определяются как поля структуры;

?Операциифункции члена класса, которые определяются как прототипы функций.

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

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

Но почему же пользователям класса не разрешается обращаться к закрытым членам, почему их описания должны приводиться в заголовочных файлах, которые, как предполагается, пользователь читает? Ответ — эффективность. Во многих системах и процесс компиляции, и последовательность операций, реализующих вызов функции, проще, когда размер автоматических объектов известен во время компиляции.

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

Файл UnQLimSz. h

Содержит стандартные и пользовательские включаемые файлы и определение шаблонного класса для работы с универсальной очередью ограниченного размера на базе массива. В шаблоне классов реализованы следующие операции с очередью:

* инициализация очереди (конструктор);

* разрушение очереди с освобождением занятой динамической памяти (деструктор);

* занесение элемента с левого конца;

* занесение элемента с правого конца;

* извлечение элемента с левого конца;

* извлечение элемента с правого конца;

* печать состояния очереди с использованием указателя на левый конец очереди;

* печать состояния очереди с использованием указателя на правый конец очереди.

Добавление элемента в правый конец очереди

template< class T >

bool UnQueueLimSize< T >: AddRight (

// false — элемент не добавлен

const T

&add) // Данное для добавляемог элемента

{

// Очередь заполнена?

if (Size>=MaxSize)

{

return false;

}

// Добавляем элемент в очередь

Right = (Right+1) % MaxSize; pQueue[ Right ] = add;

Size++;

return true;

}

// Добавление элемента в левый конец очереди

template< class T >

bool UnQueueLimSize< T >: AddLeft (

// false — элемент не добавлен

const T

&add) // Данное для добавляемого элемента

{

// Очередь заполнена?

if (Size>=MaxSize)

{

return false;

}

// Добавляем элемент в очередь

pQueue[ Left ] = add;

Left = (Left+MaxSize-1) % MaxSize; Size++;

return true;

}

// Извлечение элемента из левого конца очереди

template< class T >

bool UnQueueLimSize< T >: OutLeft (

// false — извлечение не выполнено

T &out) // Значение, которое извлекли

{

// Очередь пуста?

if (Size==0)

{

return false;

}

// Извлекаем элемент из очереди

Left = (Left+1) % MaxSize; out = pQueue[ Left ];

Size—;

return true;

}

// Извлечение элемента из правого конца очереди

template< class T >

bool UnQueueLimSize< T >: OutRight (

// false — извлечение не выполнено

T &out) // Значение, которое извлекли

{

// Очередь пуста?

if (Size==0)

{

return false;

}

// Извлекаем элемент из очереди

out = pQueue[ Right ];

Right = (Right+MaxSize-1) % MaxSize;

Size—;

return true;

}

1 Текст программы

#include «stdio.h»

#include «conio.h»

#include

#include

#include

#include

using namespace std;

template

class Queue // класс очередь

{

class strucelem // встроенный класс

{

public:

T data;// информационное поле

strucelem * next;// адресное поле

strucelem * prev;

strucelem () { next = 0;prev = 0;}// конструктор

};

strucelem * BeginQ;// указатель на первый элемент

strucelem * LastQ;// указатель на предыдущий элемент

public:

Queue ();// коструктор

~Queue ();// деструктор

void PrintQueue ();// печать очереди

void AddQueue (T data);// добавление элементов в очередь

bool CheckQueue ();// проверка состояния очереди

void DelQueue ();// удаление из очереди

void DeleteQueue ();// удаление очереди

};

// Конструктор.

template

Queue: Queue () {

BeginQ = 0;

LastQ = 0;

}

// Деструктор — освобождаем очередь и память выделенную под объекты.

template

Queue: ~Queue () {

strucelem *work;

while (BeginQ) {

work = BeginQ->next;

delete BeginQ;

BeginQ = work;

}

BeginQ = NULL;

LastQ = NULL;

}

//Печать очереди

template void Queue: PrintQueue ()

{

strucelem *p = BeginQ;

cout << endl << «Очередь: «;

while (p)

{

cout <data<<' ';

p = p->next;

}

cout << endl;

}

// Положить в очередь.

template

void Queue: AddQueue (T data) {

strucelem * link = new strucelem;

if (BeginQ == NULL) {

link->data = data;

BeginQ = link;

LastQ = link;

}

else {

link->data = data;

LastQ->next = link;

LastQ = LastQ->next;

}

}

// Проверить состояние очереди.

template

bool Queue: CheckQueue () {

if (BeginQ) return true;

else return false;

}

// Изъять из очереди.

template

void Queue: DelQueue () {

strucelem *link;

T p;

if (BeginQ ≠ NULL) {

link = BeginQ;

BeginQ = BeginQ->next;

if (BeginQ == NULL)

LastQ = 0;

p = link->data;

delete link;

// return p;

}

//else return 0;

}

// Очистить очередь.

template

void Queue: DeleteQueue () {

strucelem * link;

while (BeginQ) {

link = BeginQ;

BeginQ = BeginQ->next;

if (!BeginQ) LastQ = 0;

delete link;

}

}

int main (){

setlocale (LC_ALL," Russian");

// Формирование очереди

Queue d;

int iCount = 1;

cout<<" Введите количество элементов (по умолчанию 1):" ;

cin>>iCount;

if (iCount <= 0)

iCount = 1;

int n = 0;

for (int i=0; i

cout<<" nВведите число =";

cin>>n;

d.AddQueue (n);

}

d.PrintQueue ();

//data_int.CheckQueue ();

//data_int.PrintQueue ();

//Добавление элементов

cout<<" Введите кол-во элементов на добавление:" ;

cin>> iCount;

for (int i=0; i

cout<<" nВведите число =";

cin>>n;

d.AddQueue (n);

}

d.PrintQueue ();

// Удаление элементов

cout<<" Введите кол-во элементов на удаление:" ;

cin>> iCount;

for (int i=0; i

d.DelQueue ();

d.PrintQueue ();

cout<<" удаление очереди:" ;

d.DeleteQueue ();

d.PrintQueue ();

system («pause»);

return 0;

}

Результаты

3 Описание программы

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

Спроектируем шаблон класса Queue с типом T.

Определим интерфейс шаблона класса Queue:

Конструктор Queue ()

Назначение: создает объект класса Queue, т. е. создает очередь, выделяет динамическую память для хранения объекта.

Деструктор ~ Queue ()

Назначение: удаляет выделенную для объекта-очереди память.

Методы:

Добавление элемента n в очередь PutQueue (T data)

Удаление элемента из очереди T GetQueue ()

Вывод очереди на экран PrintQueue ()

Удаление очереди ClearQueue ();

Проверка состояния очереди СheckQueue ()

Свойства:

T data — информационное поле объекта-очереди;

strucelem * nextуказатель на следующий элемент (адресное поле)

strucelem * prev — указатель на предыдущий элемент

strucelem * BeginQ — указатель на первый элемент;

strucelem * LastQ — указатель на предыдущий элемент;

Заключение

объектное ориентированное программирование очередь

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

В процессе курсового проектирования была разработана программа на языке C++, реализующая выполнение описанных выше функций.

Список использованных источников

1. Герберт Шилдт «Справочник программиста по C/C++, второе издание» — Москва — Санкт-Петербург — Киев 2001 г.

2. Т. А. Павловская «C/C++ программирование на языке высокого уровня» — Москва — Санкт-Петербург 2005 г.

3. Р. Лафоре «Объектноориентированное программирование в С++, четвертое издание» — Москва — Санкт-Петербург — Минск 2004 г.