Объединение двух связанных списков (нужен совет)

@svadum · Регистрация: 04.06.2016

Студворк — интернет-сервис помощи студентам

шаблон ListNode

C++

#pragma once
 
// оголошення, щоб зробити другом 
template< typename NODETYPE >
class List;
 
// шаблон класу
template < typename NODETYPE >
class ListNode
{
    friend List< NODETYPE >;
public:
    ListNode(const NODETYPE &);
    NODETYPE getData() const { return data; };
private:
    NODETYPE data;
    ListNode *nextPtr;
};
 
// constructor
template<typename NODETYPE>
inline ListNode<NODETYPE>::ListNode(const NODETYPE &inData)
    : data(inData),nextPtr(0)
{
}

шаблон List

C++

#pragma once
 
#include <iostream>
#include "ListNode.h"
 
using namespace std;
 
template< typename NODETYPE >
class List
{
public:
    List();
    ~List();
    // service
    void addInFront(const NODETYPE &);
    void addInBack(const NODETYPE &);
    bool removeFromFront(NODETYPE &);
    bool removeFromBack(NODETYPE &);
    bool isEmpty() const;
    void print() const;
    List< NODETYPE> merge(List< NODETYPE > &, List< NODETYPE > &);
private:
    ListNode< NODETYPE > *firstPtr, *lastPtr;
    ListNode< NODETYPE > *getNewListNode(const NODETYPE &); // service fun.
};
 
 
 
template<typename NODETYPE>
inline List<NODETYPE>::List()
    : firstPtr(0),lastPtr(0)
{
}
 
template<typename NODETYPE>
inline List<NODETYPE>::~List()
{
    if (!isEmpty())
    {
        cout << "Destroying nodes...\n";
 
        ListNode< NODETYPE > *currentPtr = firstPtr;
        ListNode< NODETYPE > *tempPtr;
 
        while (currentPtr != 0)
        {
            tempPtr = currentPtr;
            cout << tempPtr->data << endl;
            currentPtr = currentPtr->nextPtr;
            delete tempPtr;
        }
    }
    cout << "All nodes destroyd." << endl;
    system("pause");
}
 
template<typename NODETYPE>
inline void List<NODETYPE>::addInFront(const NODETYPE &value)
{
    ListNode< NODETYPE > *newPtr = getNewListNode(value);
 
    if (isEmpty())
        firstPtr = lastPtr = newPtr;
    else
    {
        newPtr->nextPtr = firstPtr;
        firstPtr = newPtr;
    }
}
 
template<typename NODETYPE>
inline void List<NODETYPE>::addInBack(const NODETYPE &value)
{
    ListNode< NODETYPE > *newPtr = getNewListNode(value);
 
    if (isEmpty())
        firstPtr = lastPtr = newPtr;
    else
    {
        lastPtr->nextPtr = newPtr;
        lastPtr = newPtr;
    }
}
 
template<typename NODETYPE>
inline bool List<NODETYPE>::removeFromFront(NODETYPE &value)
{
    ListNode< NODETYPE > *tempPtr = firstPtr;
 
    if (isEmpty())
        return false;
    else
    {
        if (firstPtr == lastPtr)
            firstPtr = lastPtr = 0;
        else        
            firstPtr = firstPtr->nextPtr;
            
        value = tempPtr->data;
        delete tempPtr;
    }
}
 
template<typename NODETYPE>
inline bool List<NODETYPE>::removeFromBack(NODETYPE &value)
{
    if (isEmpty())
        return false;
    else
        if (firstPtr == lastPtr)
            firstPtr = lastPtr = 0;
        else
        {
            ListNode< NODETYPE > *tempPtr = lastPtr;
            ListNode< NODETYPE > *currentPtr = firstPtr;
 
            while (currentPtr != lastPtr)
                currentPtr = currentPtr->nextPtr;
 
            lastPtr = currentPtr;
            lastPtr->nextPtr = 0;
        }
}
 
template<typename NODETYPE>
inline bool List<NODETYPE>::isEmpty() const
{
    return firstPtr == 0;
}
 
template<typename NODETYPE>
inline List<NODETYPE> List<NODETYPE>::merge(List<NODETYPE> &firstList, List<NODETYPE> &secondList)
{
    firstList.lastPtr->nextPtr = secondList.firstPtr;
    
    ListNode<NODETYPE> *temp = firstList.lastPtr;
    ListNode<NODETYPE> *currentPtr = secondList.firstPtr;
    
    while (currentPtr != secondList.lastPtr)
    {
        currentPtr = currentPtr->nextPtr;
    }
    firstList.lastPtr = currentPtr;
 
    // обращени
    currentPtr = firstList.firstPtr;
    cout << temp->nextPtr->nextPtr->data << endl;
 
    return firstList;
}
 
template<typename NODETYPE>
inline void List<NODETYPE>::print() const
{
    if (isEmpty())
    {
        cout << "List is empty.\n";
        return;
    }
 
    ListNode< NODETYPE > *currentPtr = firstPtr;
    
    while (currentPtr != 0)
    {
        cout << currentPtr->data << ' ';
        currentPtr = currentPtr->nextPtr;
    }
    cout << endl;
}
 
template<typename NODETYPE>
inline ListNode<NODETYPE> *List<NODETYPE>::getNewListNode(const NODETYPE &data)
{
    return new ListNode< NODETYPE >(data);

main.cpp

C++

#include<iostream>
#include"ListNode.h"
#include"List.h"
 
using namespace std;
 
int main()
{
    List< int >integers, nextIntegers;
 
    integers.addInFront(1);
    integers.addInBack(2);
    nextIntegers.addInFront(3);
    nextIntegers.addInBack(4);
 
    integers.merge(integers, nextIntegers);
 
    nextIntegers.print();
    integers.print();
 
    system("pause");
    return 0;
}

трудности с функцией merge:
пример обращения к присоединенного объекта второго "списка" через указатель первого списка (выделено на скриншоте с функцией), свидетельствует, шо присоединение было успешным(вивод показан на скриншоте), но после написания функции "merge" выдает исключение в фукнции "print" (показано на скриншоте), но суть в функции "merge" потому что к ее написанию все работало, думаю где-то есть проблема с адресами, но не могу понять до конца месте.
буду рад любым советам

(преждевременно извиняюсь, что код без комментариев)

@nmcf · 14.08.2016, 14:47

Твоя merge() новых узлов не создает, а возвращает копию.Там деструктор будет вызываться.
В общем сделай так, чтобы присоединялось к списку, для которого функция вызвана.

C++

1	void merge(List<NODETYPE> &secondList)

@svadum · 14.08.2016, 15:22 **[ТС]**

спасибо, это так, перемудрил немного с функцией, а на счет "не создает новых узлов" все же надо чтоб создавались новые узлы в первом списке можно чтоб конец первого списка отметил начало второго, а конец первого стал на место конца второго.

Добавлено через 15 минут
nmcf, к теме с узлами, эти же узлы уже существуют во втором списке, нельзя указать на них, чтобы не создавать лишние копии, а просто взять то, что есть?

@nmcf · 14.08.2016, 18:26

Надо либо делать копии узлов, либо передавать от одного объекта другому. А если несколько объектов будет владеть одним и тем же, то будет путаница.

@svadum · 14.08.2016, 19:56 **[ТС]**

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

nmcf

Добавлено через 42 минуты

C++

template<typename NODETYPE>
inline void List<NODETYPE>::merge(List<NODETYPE> &secondList)
{
    ListNode<NODETYPE> *currentPtr = secondList.firstPtr;
    
    while (currentPtr != 0)
    {
        addInBack(currentPtr->data);
        currentPtr = currentPtr->nextPtr;
    }
}

вот рабочая версия по первому варианту + утилизация

C++

1	addInBack(currentPtr->data);

Объединение двух связанных списков (нужен совет)

Решение

Решение

@svadum 0 / 0 / 0 Регистрация: 04.06.2016 Сообщений: 24
	14.08.2016, 15:22 [ТС]	3
	спасибо, это так, перемудрил немного с функцией, а на счет "не создает новых узлов" все же надо чтоб создавались новые узлы в первом списке можно чтоб конец первого списка отметил начало второго, а конец первого стал на место конца второго. Добавлено через 15 минут nmcf, к теме с узлами, эти же узлы уже существуют во втором списке, нельзя указать на них, чтобы не создавать лишние копии, а просто взять то, что есть? 0

@nmcf 7651 / 6456 / 2944 Регистрация: 14.04.2014 Сообщений: 28,147
	14.08.2016, 18:26	4
	Сообщение было отмечено svadum как решение Решение Надо либо делать копии узлов, либо передавать от одного объекта другому. А если несколько объектов будет владеть одним и тем же, то будет путаница. 1

	14.08.2016, 19:56

Опции темы