0 / 0 / 0
Регистрация: 04.06.2016
Сообщений: 24
1

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

14.08.2016, 13:55. Показов 1629. Ответов 4
Метки нет (Все метки)

шаблон ListNode
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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" потому что к ее написанию все работало, думаю где-то есть проблема с адресами, но не могу понять до конца месте.
буду рад любым советам
(преждевременно извиняюсь, что код без комментариев)
Миниатюры
Объединение двух связанных списков (нужен совет)   Объединение двух связанных списков (нужен совет)   Объединение двух связанных списков (нужен совет)  

__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.08.2016, 13:55
Ответы с готовыми решениями:

Объединение двух списков
Помогите пожалуйста с решением следующей задачи. Нужно добавить функцию для объединения двух...

Найти объединение двух списков
Помогите мне решить задачку, я в принципе не понимаю как её решать, вот её условие. Найти...

Объединение (конкатенация) двух односвязных списков
Задача: Построить стек (односвязный список). Показать реализацию стека на следующем примере:...

Объединение двух списков в один без повтора элементов (С++)
нужно дописать функцию, которая делает из двух списков один (новый), в котором все элементы разные,...

4
7167 / 6142 / 2802
Регистрация: 14.04.2014
Сообщений: 26,462
14.08.2016, 14:47 2
Лучший ответ Сообщение было отмечено svadum как решение

Решение

Твоя merge() новых узлов не создает, а возвращает копию.Там деструктор будет вызываться.
В общем сделай так, чтобы присоединялось к списку, для которого функция вызвана.
C++
1
void merge(List<NODETYPE> &secondList)
1
0 / 0 / 0
Регистрация: 04.06.2016
Сообщений: 24
14.08.2016, 15:22  [ТС] 3
спасибо, это так, перемудрил немного с функцией, а на счет "не создает новых узлов" все же надо чтоб создавались новые узлы в первом списке можно чтоб конец первого списка отметил начало второго, а конец первого стал на место конца второго.

Добавлено через 15 минут
nmcf, к теме с узлами, эти же узлы уже существуют во втором списке, нельзя указать на них, чтобы не создавать лишние копии, а просто взять то, что есть?
0
7167 / 6142 / 2802
Регистрация: 14.04.2014
Сообщений: 26,462
14.08.2016, 18:26 4
Лучший ответ Сообщение было отмечено svadum как решение

Решение

Надо либо делать копии узлов, либо передавать от одного объекта другому. А если несколько объектов будет владеть одним и тем же, то будет путаница.
1
0 / 0 / 0
Регистрация: 04.06.2016
Сообщений: 24
14.08.2016, 19:56  [ТС] 5
если честно, я с самого начала так и хотел реализовать, через копии узлов, функцию getNewListNode(...), поочередно вставляя в зад новые узлы, но потом стало интересно можно реализовать через манипуляции с указателями (все же так и кода меньше и быстрее , но все же первый вариант предпочтительнее и надежнее + более понятен.
спасибо тебе за помощь и советы nmcf

Добавлено через 42 минуты
C++
1
2
3
4
5
6
7
8
9
10
11
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);
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.08.2016, 19:56
Помогаю со студенческими работами здесь

Объединение двух связных списков с объектами одного типа
Здравствуйте. При изучении связных списков, написал шаблон для связного списка, с функциями...

Нужен совет по решению - из двух натуральных чисел составить одно наименьшее.
Минимальное число Требуется написать программу, которая из цифр двух натуральных чисел создает...

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

Создать модель файловой системы на основе связанных списков
доброго времени суток, форумчане!!! В сентябре получил задание на курсовой проект по СПО: ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru