Размещено на http://www.allbest.ru/

Федеральное агентство по образованию Российской Федерации

САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМЕНИ Н.Г. ЧЕРНЫШЕВСКОГО

Кафедра математической кибернетики и компьютерных наук

КУРСОВАЯ РАБОТА

ОБЪЕКТНАЯ РЕАЛИЗАЦИЯ СПИСКА

Саратов 2009

Содержание

• Введение
• 1. Что такое объект
• 2. Реализация списка на C++
• 3. Результаты работы программы
• Заключение
• Список использованных источников
• Приложение

Введение

Структуры данных делятся на статические и динамические. К статическим структурам данных относятся, например, массивы. Они имеют фиксированный размер, который не может быть изменён. Динамические же структуры данных могут менять свой размер во время выполнения программы. Динамическими структурами данных являются списки, стеки, очереди, деревья и т.д.

Список -- это динамическая структура данных, каждый элемент которой связывается со следующим посредством указателя. Каждый элемент списка содержит как минимум одно поле данных и поле ссылки на следующий элемент. Списки имеют ряд преимуществ перед массивами: легче выполнять вставку и удаление элементов, не нужно заранее задавать максимально возможный размер списка. Поэтому списки часто используются в приложениях.

Существует множество способов реализации списка. В данной работе будет рассмотрена его объектная реализация на C++.

1. Что такое объект

Дадим определение объекта согласно [1]: "Объект обладает состоянием, поведением и индивидуальностью; структура и поведение схожих объектов определяют общий для них класс; термины "экземпляр класса" и "объект" взаимозаменяемы.

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

Понятие объекта тесно связано с понятием класса. Согласно определению из [1], класс -- множество объектов, связанных общностью структуры и поведения. Каждый объект является экземпляром класса.

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

У класса существует интерфейсная часть, в которой перечисляются действия, переменные, константы. Она может быть разделена на общедоступную (public), защищённую (protected) и обособленную (private) части.

2. Реализация списка на C++

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

Так как реализация этих функций не зависит от того, какой тип имеют элементы списка (целый, вещественный, символьный, строковый или какой-то другой), то при создании класса удобнее всего использовать шаблоны C++ (templates). Это позволит объявить параметризованный класс списков. Затем для каждого экземпляра списка можно указать тип его элементов.

Опишем вспомогательную структуру El -- элемент списка. Она будет содержать два поля: собственно значение элемента inf и указатель на следующий элемент next:

template <class T>

struct El

{

El *next; T inf;

};

Здесь в роли параметра выступает T. Этот параметр задаёт тип данных, который будет храниться в структуре.

Теперь объявим класс List -- список. Он будет иметь два поля: a -- первый элемент списка; size -- размер списка. Так как они используются только внутри самого класса, то они будут в области видимости private. Также класс List будет иметь следующие методы:

· List и ~List -- конструктор и деструктор соответственно;

· At -- возвращает значение элемента в позиции с номером z;

· Insert -- добавляет элемент со значением val в позицию z;

· Delete -- удаляет элемент из позиции z;

· Length -- возвращает длину списка;

· First -- возвращает первый элемент списка;

· Last -- возвращает последний элемент списка.

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

Алгоритмы вставки и удаления элемента списка взяты из [2].

Полный листинг приведён в приложении.

список интерфейсный класс программа

3. Результаты работы программы

a.in
5 1 2 3 4 5 5 4
a.out
1 2 3 4 5 5-й элемент списка: 5 4-й элемент списка удалён; теперь в списке 4 элементов: 1 2 3 4 Первый элемент: 1; последний: 4
a.in
6 benz 670 qwerty crunk == $$$ 0 5
a.out
benz 670 qwerty crunk == $$$ 0-й элемент списка: benz 5-й элемент списка удалён; теперь в списке 5 элементов: benz 670 qwerty crunk == Первый элемент: benz; последний: ==
a.in
5 ok 312 asdfg ';' 0 4 2
a.out
ok 312 asdfg ';' 0 4-й элемент списка: 0 2-й элемент списка удалён; теперь в списке 4 элементов: ok 312 ';' 0 Первый элемент: ok; последний: 0
a.in
5 ok 312 asdfg ';' 0 4 0
a.out
ok 312 asdfg ';' 0 4-й элемент списка: 0 0-й элемент списка удалён; теперь в списке 4 элементов: 312 asdfg ';' 0 Первый элемент: 312; последний: 0

Заключение

Рассмотрена такая структура данных, как список. Показано, как можно реализовать её с использованием объектно-ориентированного подхода. Также дано определение объекта и класса. Приведены результаты работы программы и её листинг.

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

1. Буч Г. Объектно-ориентированное проектирование с примерами применения/Пер. с англ. -- М.: Конкорд, 1992.

2. Окулов С.М. Основы программирования /С. М. Окулов. -- 3-е изд. -- М.: БИНОМ. Лаборатория знаний, 2006.

Приложение

Реализация списка:

#include<iostream>

#include<fstream>

#include<string>

#define INF 1000000000

#define Type string

using namespace std;

// Входной и выходной файлы.

ifstream in("a.in"); ofstream out("a.out");

template <class T>

struct El

{

El *next; T inf;

};

template <class T>

class List

{

El<T> *a;

int size;

public:

List();

~List();

T At(int z);

void Insert(int z,T val);

void Delete(int z);

int Length();

T First();

T Last();

};

template <class T>

List<T>::List()

{

size=0; a=NULL;

// Вначале список имеет нулевой размер; первый элемент - пустое значение.

}

template <class T>

List<T>::~List()

{

for (int i=size-1; i>=0; --i) Delete(i);

}

template <class T>

T List<T>::At(int z)

{

if (z>=size) z=size-1;

El<T> *t;

t=a;

for (int i=0; i<z; ++i) t=t->next;

return t->inf;

}

template <class T>

void List<T>::Insert(int z,T val)

{

if (z>size) return;

El<T> *t=a;

if (z==0)

{

t=new El<T>; t->next=a; t->inf=val; a=t; size=1; return;

}

if (z==size)

{

for (int i=0; i<z-1; ++i) t=t->next;

t->next=new El<T>;

t=t->next;

t->inf=val;

t->next=NULL;

}

else

{

for (int i=0; i<z; ++i) t=t->next;

El<T> *m=t->next; m->inf=val; t->next=m;

}

++size;

}

template <class T>

void List<T>::Delete(int z)

{

if (z>=size) return;

El<T> *t=a,*d=new El<T>;

for (int i=0; i<z; ++i)

{

d=t; t=t->next;

}

if (t==a)

{

El<T> *x=a;

a=a->next; delete x; t=a;

}

else

{

El<T> *x=t;

t=t->next; d->next=t; delete x;

}

--size;

}

template <class T>

int List<T>::Length()

{

return size;

}

template <class T>

T List<T>::First()

{

return At(0);

}

template <class T>

T List<T>::Last()

{

return At(size-1);

}

int main()

{

List<Type> *l;

l=new List<Type>();

int f;

in>>f;

for (int i=0; i<f; ++i)

{

Type n;

in>>n; out<<n<<' ';

l->Insert(i,n);

}

out<<endl;

in>>f;

out<<f<<"-й элемент списка: "<<l->At(f)<<endl;

in>>f;

l->Delete(f);

out<<f<<"-й элемент списка удалён; теперь в списке "<<l->Length()<<" элементов:"<<endl;

for (int i=0; i<l->Length(); ++i) out<<l->At(i)<<' ';

out<<endl<<"Первый элемент: "<<l->First()<<"; "<<"последний: "<<l->Last()<<endl;

l->~List(); in.close(); out.close();

return 0;

}

Размещено на Allbest.ru