Пример за обектно ориентирана реализация на свързан списък.

17. Пример за обектно ориентирана реализация на свързан списък.

Програмата, която разглеждаме включва два шаблона на класовете ListNode и List. Всеки обект от класа List е свързан списък от обекти на класа ListNode. Шаблонът на класа ListNode се състои от закритите член данни data, nextPtr от тип NODETYPE. Този параметър на тип се предава на шаблона на класа. Указателят nextPtr е указател към следващия обект в свързания списък.

Файл listnd.h

#ifndef _LISTND_H_
#define _LISTND_H_
 
template <class NODETYPE>
class ListNode
{
    friend class List<NODETYPE>
 
    public:
        ListNode( const  NODETYPE& );
        NODETYPE getData() const;
 
    private:
        NODETYPE data;
        ListNode<NODETYPE> *nextPtr;
};
 
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 се състои от закритите член-данни firstPtr ( указател към първия обект от списък с ел. с клас ListNode ), lastPtr ( указател към последния обект ). Конструкторът с аргументи по премълчаване инициализира и двата с нулева стойност. Деструкторът осигурява унищожаване на всички обекти от ListNode, влизащи в обект от клас List. Основните член-функции на шаблонния клас List: insertAtFront( const NODETYPE& ), insertAtBack( const NODETYPE& ), removeFromFront( NODETYPE& ), removeFromBack( NODETYPE& ), isEmpty() const -> проверява дали списъкът е празен ( first == NULL ), ako e wry]a true, а иначе false, print () const -> извежда на екрана съдъжанието на списъка List.

Файл list.h

#ifndef _LIST_H_
#define _LIST_H_
 
#include <iostream>
#include <assert>
#inclue "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& );
};
 
template <class NODETYPE>
List<NODETYPE>::List(): firstPtr(0), lastPtr(0)
{}
 
template <class NODETYPE>
List<NODETYPE>::~List()
{
    if ( !isEmpty() )
    {
        cout << " \n Изключване на обекти.. \n ";
        ListNode<NODETYPE> * curPtr = firstPtr, *temoPtr;
 
        while( curPtr != 0 )
        {
            tempPtr = curPtr;
            cout << tempPtr->data << "\n";
            cur->Ptr = curPtr->next;
            delete tempPtr;
        }
    }
    cout << " \n Всички обекти са изключени \n ";
}
 
/* Предикатна функция, не изменя списъка, само проверява дали е празен.. */
template <class NODETYPE>
bool List<NODETYPE> :: 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> :: insertAtFront( const NODETYPE& value )
{
    ListNode<NODETYPE> *newPtr = getNewNode(value);
 
    if ( isEmpty() )
        firstPtr = lastPtr = newPtr;
    else
    {
        newPtr->next = firstPtr;
        first = newPtr;
    }
}
 
template <class NODETYPE>
void List<NODETYPE>::insertAtBack( const NODETYPE& value )
{
    ListNode<NODETYPE> *newPtr = getNewNode( value );
    if ( isEmpty() )
        firstPtr = lastPtr = newPtr;
    else
    {
        lastPtr->next = newPtr;
        lastPtr = newPtr;
    }
}
 
template <class NODETYPE>
bool List<NODETYPE> :: removeFromFront( NODETYPE& value )
{
    if ( isEmpty() )
        return false;
    else
    {
        ListNode<NODETYPE> *tempPtr = firstptr;
        if ( fisrtPtr == lastPtr )
            firstPtr = lastPtr = 0;
        else
            firstPtr = firstPtr->next;
 
        value = tempPtr->data;
        delete tempPtr;
        return true; 
    }    //изключването е успешно..
}
 
template <class NODETYPE>
bool List<NODETYPE>:: removeFromBack( const NODETYPE& value )
{
    if ( isEmpty() )
        return false;
    else
    {
        ListNode<NODETYPE> *tempPtr = lastPtr;
        if ( fisrtPtr == lastPtr )
            firstPtr = lastPtr = 0;
        else
        {
            ListNode<NODETYPE> *curPtr = firstPtr;
            while( curPtr->nextPtr != lastPtr )
                curPtr = curPtr->next;
            lastPtr = curPtr;
            curPtr->next = 0;
        }
        value = tempPtr->data;
        delete tempPtr;
        return true;
    }
}
 
template <class NODETYPE>
void List<NODETYPE>::print() const
{
    if ( isEmpty() )
    {
        cout << " \n Списъкът е празен.. \n ";
        return;
    }
 
    ListNode<NODETYPE> *curPtr = firstPtr;
    cout << " Списък: ";
    while( curPtr != 0 )
    {
        cout << curPtr->data << " ";
        curPtr = curPtr->next;
    }
    cout << "\n";
}
 
#endif

print() проверява дали списъкът е празен, ако е съобщение, че е празен и return, ако ли не - обхожда списъка и извежда полетата с данни. Ако указателят към следващия елемент на последния елемент не е нула, то алгоритъмът погрешно ще изведе данни след края на спиисъка (алгоритъмът е общ за стек, опашка, списък.. ) Добър стил е анулиране или инициализиране на указател към следващия елемент с нов елемент.
#include "list.h"
 
using std::cin;
using std::cout;
using std:endl;
 
template <class T>
void testList( List<T> &listObject, const char* type )
{
    cout << " Тестване на списък със стойности от тип " << type << endl;
 
    int choice; // 1 - insertAtFront, 2 - insertAtBack, 3 - removeFromFront, 4 - removeFromBack, 5 - End
 
    T value;
 
    do
    {
        cout << " ?  ";
        cin >> choice;
 
        switch( choice )
        {
            case 1:
                cout << " Въведете " << type << " : ";
                cin >> value;
                listObject.insertAtFront( value );
                break;
            case 2:
                cout << " Въведете " << type << " : ";
                cin >> value;
                listObject.insertAtBack( value );
                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 ";
}
 
void main()
{
    List<int> integerList;
    testList( integerList, " цяло число " );
 
    List<double> doubleList;
    testList( doubleList, " число с плаваща точка " );
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License