Подсчет узлов в связанном списке

[Sverest]

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

Исключительные ситуации:

Используется синтаксис C++

//***************************************************
//       ListIndexOutOfRangeException
//
//***************************************************
#include <stdexcept>
#include <string>
using namespace std;
class ListIndexOutOfRangeException: public out_of_range
{
public:
        ListIndexOutOfRangeException(const string & message = "")
        :out_of_range(message.c_str())
        { }
}; //конец определения класса end ListIndexOutOfRangeException

//***************************************************
//       ListException
//
//***************************************************

#include <exception>
#include <string>
using namespace std;

class ListException: public exception
{
public:
        ListException(const string & message = "")
        :exception(message.c_str())
        { }
}; //конец определения класса ListException

 

Заголовочный файл ListP.h для реализации абстрактного списка:

Используется синтаксис C++

//**************************************************************
//Заголовочный файл ListP.h для реализации абстрактного списка,
//основанной на указателях
//**************************************************************
#include "ListException.h"
#include "ListIndexOutOfRangeException.h"
typedef тип_элемента_списка ListItemType;

class List
{
public:
        //Конструкторы и деструкторы
        List(); //Конструктор по умолчанию
        List(const List& aList); //Конструктор копирования
        ~List(); //Деструктор

        //Операции над списком:
        bool isEmpty() const;
        int getLength() const;
        void insert (int index,ListItemType newItem)
                throw (ListIndexOutOfRangeException, ListException);
        void remove(int index)
                throw (ListIndexOutOfRangeException);
        void retrieve (int index, ListItemType& dataItem) const
                throw(ListIndexOutOfRangeException);
        //Конструктор копирования и деструктор необходимы 
        //Для реализации абстрактного списка на основе указателей
private:
        struct ListNode //Узел списка
        {
                ListItemType item; //Данные, хранящиеся в узле
                ListNode *next; //Указатель на следующий узел
        }; //Конец структуры

        int size;            //Количество элементов списка
        ListNode *head;      //Указатель на связанный список
        ListNode *find(int index) const;
        //Возвращает указатель на узел с номером index
}; //Конец описания класса
//Конец заголовочного файла
 

Файл реализации ListP.cpp для абстрактного списка

Используется синтаксис C++

//**************************************************************
//Файл реализации ListP.cpp для абстрактного списка
//Реализация на основе указателей 
//**************************************************************
#include "ListP.h" //Заголовочный файл
#include "cstddef" //Определение константы NULL
#include "cassert" //Определение макроса assert()

//Определение функций-членов

//Конструктор по умолчанию
List::List(): size (0), head(NULL)
{
} //Конец конструктора по умолчанию

//Конструктор копирования
//List(const List& aList);
List::List(const List& aList): size(aList.size)
{
        if (aList.head == NULL)
                head = NULL; //Исходный список пуст
        else
        {
                //Копирование первого узла
                head = new ListNode;
                assert(head != NULL); //Проверка оператора new
                head -> item = aList.head -> item;

                //Копирование остальной части списка
                ListNode *newPtr = head; //new list pointer
                //Указатель newPtr ссылается на последний узел нового списка
                for (ListNode *origPtr = aList.head -> next;
                        origPtr != NULL;
                        origPtr = origPtr -> next)
                {
                        newPtr -> next = new ListNode;
                        assert (newPtr -> next != NULL);
                        newPtr = newPtr -> next;
                        newPtr -> item = origPtr -> item;
                } //конец цикла for

                newPtr -> next = NULL;
        } // конец цикла if
} //конец конструктора копирования


List::~List()
{
        while (!isEmpty())
                remove(1);
} //Конец деструктора


bool List::isEmpty() const 
{
        return bool (size == 0)
} //Конец фунции isEmpty

int List::getLength() const
{
        return size;
} //Конец функции getLength

List::ListNode *List::find(int index) const
//-------------------------------------------------------
//Обнаруживает указанный узел в связанном списке
//Предусловие: переменная index задает номер искомого узла
//Постусловие: возвращает указатель на искомый узел.
//Если index < 1 или index больше количества узлов списка,
//возвращается константа NULL
//-------------------------------------------------------
{
        if ((index < 1) || (index > getLength()))
                return NULL;
        else //Отчет от начала списка
                {
                        ListNode *cur = head;
                        for (int skip = 1; skip < index; ++skip)
                                cur= cur -> next;
                        return cur;
                } // конец if
} //конец find


void List::retrieve(int index, 
        ListItemType& dataItem) const
        {
                if ((index < 1) || (index > getLength()))
                        throw ListIndexOutOfRangeException()
                else
                {
                        //Вычислить указатель на узел, а затем 
                        //извлечь из него данные
                        ListNode *cur = find(index);
                        dataItem = cur -> item;
                } //конец if 
        } // конец retrieve

        void List::insert (int index, ListItemType newItem)
        {
                int newLength = getLength() + 1;
                if ((index < 1) || (index > newLength))
                        throw ListIndexOutOfRangeException(
                                "ListIndexOutOfRangeException: неверный индекс");
                else
                {
                        //Создаем новый узел и помещаем в него объект newItem
                        ListNode *newPtr = new ListNode;
                        if (newPtr == NULL)
                                throw ListException (
                                        "ListException: выделить память невозможно");
                        else
                        {
                                size = newLength;
                                newPtr -> item = newItem;

                                //присоединяем к списку новый элемент
                                if (index == 1)
                                {
                                        //Вставляем новый узел в начало списка
                                        newPtr -> next = head;
                                        head = newPtr;
                                }
                                else
                                {
                                        ListNode *prev = find(index-1);
                                        //вставляем новый узел после узла
                                        //на который ссылается указатель prev
                                        newPtr -> next = prev -> next;
                                        prev -> next = newPtr;
                                } //конец if
                        } //конец if
                } //конец if
        } //конец insert

        void List::remove(int index)
        {
                ListNode *cur;
                if ((index < 1) || (index > getLength()))
                        throw ListIndexOutOfRangeException(
                                "ListIndexOutOfRangeException: неверный индекс");
                else
                {
                        --size;
                        if (index == 1)
                        {
                                //Удаляем первый элемент списка
                                cur = head; //сохраняем указатель на узел
                                head = head -> next;
                        }
                        else 
                        {
                                ListNode *prev = find (index-1);
                                //Удаляем узел, находящийся после узла,
                                //на который ссылаетсяуказатель prev
                                cur = prev -> next; //Сохраняем указатель на узел
                                prev -> next = cur -> next;
                        } конец if

                        //освобождаем память, занятую узлом
                        cur -> next = NULL;
                        delete cur;
                        cur = NULL;
                } //конец if
        } // конец remove
 

Функция для итеративного подсчета количества узлов:

Используется синтаксис C++

int kolvo_yzlov()
{
int t=0;
for (int i=0 ; getLength(); i++ );
    {if (retrieve (i, dataItem))
     t=t+1;}
retrieve t;
}
 

Я правильно сделал функцию kolvo_yzlov()?

[Toucan]

И что? Предмет обсуждения-то какой?

[Sverest]

Toucan в сообщении #606556 писал(а):

И что? Предмет обсуждения-то какой?

Я правильно сделал функцию kolvo_yzlov()?

[lim0n]

Нет, не правильно. А разве компилятор не матерился на каждой строке?
1. Метод retrieve() возвращает void, а вы его в условный оператор.
2. Второе выражение в операторе цикла — при непустом списке гарантирован бесконечный цикл.
3. Начальное значение i=0 не имеет смысла, т.к. элементы списка нумеруются от единицы (см. определение класса).
3. retrieve() и getLength() — это не функции, а методы объекта класса List. Какого объекта, где его определение/имя?
4. Где определение переменной dataItem?
5. Оператор возврата пишется по другому — return.

И вообще, зачем нужна ваша функция, есть уже готовый метод getLength() для получения размера списка.