Пример за обектно – ориентирана реализация на свързан списък
В примера се използва шаблон на класа List за обработка на списък от данни от цял тип и списък от данни с плаваща точка. Програма driver дава възможност да се използват 5 режима на работа. При първия режим има добавяне на елемент в началото на списъка, което става с помощта на функцията insertAtFront; втори режим – добавяне на елемент в началото на списъка, което става с функцията insertAtBack; трети режим – изключване на елемент от началото на списъка, което става с функцията removeFromFront; четвърти режим – изключване на елемент от края на списъка, което става с функцията removeFromBack; пети режим – завършване обработката на списъка. Програмата, която ще разгледаме включва 2 шаблона на класове – List и ListNode. Всеки обект от класа List е свързан списък от обект от класа ListNode.
// Деф. шаблона на класа ListNode във файла listnd.h
#ifndef LISTND_H
#define LISTND_H
template < class NODETYPE > class LIST;
template < class NODETYPE >
class ListNode
{
friend class List<NODETYPE>;
public:
ListNode( const NODETYPE& );
NODETYPE getData() const;
private:
NODETYPE data;
ListNode<NODETYPE> *nextPtr;
};
/* Шаблона на класа ListNode се състои от закритите член-данни data и *nextPtr. Данната data съдържа стойност от тип NODETYPE. Този параметър на тип се представя на шаблона на класа. Указателят nextPtr съдържа указател следващия обект на класа ListNode на свързания списък*/
template <class NODETYPE>
ListNode<NODETYPE>::ListNode(const NODETYPE &info):data(info), nextPtr(0)
{}
template <class NODETYPE>
NODETYPE ListNode<NODETYPE>::getData() const
{
return data;
}
#endif
//Деф. шаблона на класа List във файла list.h
#ifndef LIST_H
#define LIST_H
#include <iostream>
#include <cassert>
#include “listnd.h”
using std::cout;
template <class NODETYPE>
class List{
public:
List();
~List();
void insertAtFront(const NODETYPE&);
void insertAtBack(const NODETYPE&);
bool removeFromFront(NODETYPE&);
bool removeFromBack(NODETYPE&);
bool isEmpty() const;
void print() const;
private:
ListNode<NODETYPE> *firstPtr;
ListNode<NODETYPE> *lastPtr;
ListNode<NODETYPE> *getNewNode( const NODETYPE&);
};
/* Шаблона на класа List се състои от закр. член данни firstPtr – указател към първият обект на списъка с елементи от клас ListNode и lastPtr – указател към последния обект на списъка с елементи от клас ListNode. Констукторът с елементи по премълчаване инициализира и двата указателя с нулева стойност. Деструкторът осигурява унищожаването на всички обекти от клас ListNode, влизащи в обект на List, при унищожаване на обекта от клас List. Основни функции на на шаблона List са: insertAtFront, insertAtBack, removeFromFront, removeFromBack. Функцията isEmpty проверява дали списъка е празен, т.е. дали указателят към първият обект е 0. Ако е празен връща true, иначе връща false. Функцията print извежда на екрана съдържмото на списъка List. */
template<class NODETYPE>
List<NODETYPE>::List():firstPtr(0), lastPtr(0)
{}
template<class NODETYPE>
List<NODETYPE>::~List()
{
if(!isEmpty())
{
cout<<”изключване на обекти \n”;
ListNode<NODETYPE> *currentPtr = firstPtr, *tempPtr;
while(currentPtr != 0)
{
tempPtr = currentPtr;
cout<<tempPtr->data<<’\n’;
currentPtr = currentPtr->nextPtr;
delete tempPtr;
}
}
cout<<”Всички обекти са изключени\n\n”;
}
template<class NODETYPE>
void List<NODETYPE>::insertAtFront(const NODETYPE& value)
{
ListNode<NODETYPE> *newPtr = getNewNode(value);
if(isEmpty())
firstPtr = lastPtr = newPtr;
else{
newPtr->nextPtr = firstPtr;
firstPtr = newPtr;
}
}
/* Извиква се getNewNode(), на която се предава value – константен псевдоним на данната на добавения обект. Функцията getNewNode използва опер. new за създаване на нов обект от списъка и опер. new връща указател към този обект ptr. Ако този указател има стойност различна от 0, то функцията връща указател към добавения обект и го присвоява
на newPtr. Ако списъка е празен на указателите firstPtr и lastPtr се предава newPtr – това ще бъде единствения обект. Ако не е празен, то обекта към който сочи newPtr се добавя в началото на списъка чрез копиране на указ. firstPtr в полето newPtr->nextPtr, така че
този нов обект ще сочи към следващия, който преди беше първи в списъка; в резултат на копирането newPtr във firstPtr, новата стойност на firstPtr ще сочи към новия обект като първи в списъка.*/
template<class NODETYPE>
void List<NODETYPE>::insertAtBack(const NODETYPE& value)
{
ListNode<NODETYPE> *newPtr = getNewNode(value);
if(isEmpty())
firstPtr = lastPtr = newPtr;
else{
lastPtr->nextPtr = newPtr;
lastPtr = newPtr;
}
}
/* Ако има памет функцията getNewNode ще върне указател към добавения обект, който се присвоява на newPtr. Ако списъка е празен указатезателите firstPtr и lastPtr се правят равни на newPtr.
Ако списъка не е празен, тогава обекта към който сочи newPtr се добавя в края на списъка чрез копиране на указателя newPtr в полето lastPtr->nextPtr, така че този нов обект сега ще сочи като следващ обекта, който преди беше последен в списъка. Освен това в резултат на копирането на newPtr в lastPtr, новата стойност на lastPtr ще сочи към новия обект като последен в списъка*/
template<class NODETYPE>
bool List<NODETYPE>::removeFromFront(NODETYPE &value)
{
if(isEmpty())
return false;
else{
ListNode<NODETYPE> *tempPtr = firstPtr;
if(firstptr == lastPtr)
firstPtr = lastPtr = 0;
else
firstPtr = firstPtr->nextPtr;
value = tempPtr->data;
delete tempPtr;
return true;
}
}
/* Функцията връща false, ако е направен опит за изключване на обект от празен списък. Ако не е празен на tempPtr се присвоява стойността на firstPtr, указателят tempPtr се използва за освобождаване на паметта, заета от изключвания обект. Ако указателите firstPtr и lastPtr са равни, то в списъка има само 1 елемент. След изключването списъка става празен и затова на firstPtr и lastPtr се присвояват нулеви стойности. Ако в списъка има повече от 1 елемент, то указателят lastPtr остава непроменен, а на firstPtr се присвоява firstPtr->nextPtr, т.е. сега firstPtr ще сочи към втория елемент на списъка, който след изключването става първи. След като всички обработки на указатели са завършили в параметъра псевдоним value се копира данната data от изключения обект.
Операцията delete освобождава паметта, разпределена за елемента към който сочи tempPtr. Накрая функцията връща true, което е признак, че изключването е успешно. */
template<class NODETYPE>
bool List<NODETYPE>::removeFromBack(NODETYPE &value)
{
if(isEmpty())
return false;
else{
ListNode<NODETYPE> *tempPtr = lastPtr;
if(firstPtr == lastPtr)
firstPtr = lastPtr = 0;
else{
ListNode<NODETYPE> *currentPtr = firstPtr;
while(currentPtr->nextPtr != lastPtr)
currentPtr = currentPtr->nextPtr;
lastPtr = currentPtr;
currentPtr->nextPtr = 0;
}
value = tempPtr->data;
delete tempPtr;
return true;
}
}
/* Функцията връща false, ако е направен опит за изключване на обект от празен списък. На tempPtr се присвоява стойността на lastPtr. Указателят tempPtr ще се използва за освобождаване на паметта,
заета от изключения обект. Ако firstPtr и lastPtr са равни, то в списъка има само 1 елемент. След изключването му, списъкът остава празен и затова на firstPtr и lastPtr се присвояват нулеви стойностти.
Ако в списъка има повече от 1 елемент, то на указателя currentPtr се присвоява стойността на указателя firstPtr. След това се минава по списъка с помощта на указателя currentPtr, докато той не започне да сочи последния елемент. За да се изключи последния елемент на lastPtr се присвоява стойността на currentPtr. Полето nextPtr на новия последен елемент се анулира. След като всички обработки на указатели са завършили във value се копира данната data на изключения обект. Операцията delete освобождава областта от паметта, разпределена за елемента, към който tempPtr. Функцията връща true, което е признак че изключване е успешно.*/
template<class NODETYPE>
bool List::isEmpty() const
{
return firstPtr == 0;
}
template<class NODETYPE>
ListNode<NODETYPE>* List<NODETYPE>::getNewNode(const NODETYPE& value)
{
ListNode<NODETYPE>* ptr = new ListNode<NODETYPE>(value);
assert(ptr != 0);
return ptr;
}
template<class NODETYPE>
void List<NODETYPE>::print() const
{
if(isEmpty())
{
cout<<”Списъкът е празен.\n\n”;
return;
}
ListNode<NODETYPE>* currentPtr = firstPtr;
cout<<”Списък: “;
while(currentPtr != 0)
{
cout<<currentPtr->data<<’ ‘;
currentPtr = currentPtr->nextPtr;
}
cout<<”\n\n”;
}
#endif
/* Ще отбележим, че ако указ. към следващия елемент в последния елемент на списъка не е 0, то алгоритъма погрешно ще изведе данни след края на списъка. Алгоритъма за извеждане е един и същ за св. списъци, стекове, опашки. Добър стил на програмиране е анул. или инициализирането на указ. към следв. елемент в новосъздаден списък. */
// файл test.cpp
#include <iostream>
#include “list.h”
using std::cin;
using std::endl;
void instructions();
template <class T>
void testList(List<T>& listObject, const char* type)
{
cout<<”Тестване на списък със стойности от тип “<<type<<endl;
instructions();
int choice;
T value;
do{
cout<<”? “;
cin>>choice;
switch(choice)
{
case 1:
cout<<”Въведете “<<type<<”: “;
cin>>value;
listObject.insertAtFront(value);
listObject.print();
break;
case 2:
cout<<”Въведете “<<type<<”: “;
cin>>value;
listObject.insertAtBack(value);
listObject.print();
break;
case 3:
if(listObject.removeFromFront(value))
cout<<value<<” е изключена от списъка\n”;
listObject.print();
break;
case 4:
if(listObject.removeFromBack(value))
cout<<value<<” е изключена от списъка\n”;
listObject.print();
break;
}
}while(choice != 5);
cout<<”Край на тестването на списъка.\n\n”;
}
void instructions()
{
cout<<”Въведете номера на действието: \n”
<<”1 – за включване в началото на списъка.\n”
<<”2 – за включване в края на списъка.\n”
<<”3 – за изключване от началото на списъка.\n”
<<”4 – за изключване от края на списъка.\n”
<<”5 – за завършване обработката на списъка.\n”;
}
void main()
{
List<int> integerList;
testList(integerList, “цяло число”);
List<double> doubleList;
testList(doubleList, “число с плав. точка”);
Сходни статии:
- Пример за обектно ориентирана реализация на свързан стек Ще се възползваме от тясната връзка между св. списъци и стекове чрез повторно използване на класа на списъците. Ще приложим 2 разновидности на повторното използване. Отначало ще реализираме класа на...
- Търсене на нов елемент по ключ и добавяне на нов елемент в свързан списък void search ( student *first, unsigned key, float value ) // студент с ф. № key и с value се задава новия му успех { student *ptr = first; while...
- Свързан стек. Основни операции typedef int INFO_TYPE; struct stack_el{ INFO_TYPE info; stack_el *link; }; //Функция за добавяне на елемент void push(stack_el **t, INFO_TYPE x) //Указателят към върха на стека трябва да се промени, затова...
- СА Алгоритми Задание: Около кръгла маса са наредени n на брой човека, номерирани последователно с числата от 1 до n. След това започвайки от номер 1, всеки трети напуска масата, докато накрая...
- Обектно-ориентирано проектиране (ООП). Правила за обектно-ориентирано проектиране Проектиране на класове и обекти ПЪРВИ ЕТАП ОТДЕЛЯНЕ НА КЛАСОВЕТЕ И ОБЕКТИТЕ ОТ ПО НА ЗАДАЧАТА Класове и обекти могат да бъдат: реални неща от програмиране на обекти абстракции в...