Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
straus
0 / 0 / 0
Регистрация: 18.10.2010
Сообщений: 45
#1

три двунаправленных списка - C++

27.11.2010, 01:22. Просмотров 723. Ответов 17
Метки нет (Все метки)

помогите решить задачу на зачет....
даны два файла, содержащие числовые данные
1.создать два двунаправленных упорядоченных списка, заполненный данными из файла
2. создать новый двунаправленный список, содержащий данные из двух существующих с сохранением упорядоченности
3.записать содержимое нового списка в третьем файле
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.11.2010, 01:22     три двунаправленных списка
Посмотрите здесь:

Использование двунаправленных списков - C++
Здравствуйте. Помогите решить задачу. Задание: Переместить во второй список все элементы, находящиеся после элемента с максимальным...

Кольцевые списки на базе двунаправленных списков - C++
Всем привет! Помогите решить задачу: Пусть L обозначает кольцевой двунаправленный список с включенным заглавным звеном. Написать функцию...

С помощью списка определить три наиболее распространенных среди студентов имен - C++
Помогите, пожалуйста с задачей Сформуваты двунаправленный список строк, каждая из которых состоит из фамилии и имени студента. С...

Написать программу, расщепляющую упорядоченный линейный список целых чисел на три упорядоченных списка - имеющих остаток от деления на 3, ра - C++
Написать программу, расщепляющую упорядоченный линейный список целых чисел на три упорядоченных списка - имеющих остаток от деления...

В интервале от 1 до 100, вывести все числа, кроме делящихся на три или имеющих в записи цифру три - C++
вывести цикл от 1 до 100, так чтобы числа имеющие 3 или которые можно разделить на 3 не выводились. пробовал через массивы, но нужно по...

Даны три стороны одного и три стороны другого треугольника. Я, чайник нужно в С++ - C++
Даны три стороны одного и три стороны другого треугольника. Эти треугольники равновеликие, т.е. имеют равные площади

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
NightmareZ
1339 / 562 / 37
Регистрация: 31.03.2009
Сообщений: 1,918
27.11.2010, 03:47     три двунаправленных списка #2
Цитата Сообщение от straus Посмотреть сообщение
помогите решить задачу на зачет....
даны два файла, содержащие числовые данные
1.создать два двунаправленных упорядоченных списка, заполненный данными из файла
2. создать новый двунаправленный список, содержащий данные из двух существующих с сохранением упорядоченности
3.записать содержимое нового списка в третьем файле
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
#include <algorithm>
#include <iterator>
#include <fstream>
#include <list>
 
int main()
{
    std::list<int> lst1(
        std::istream_iterator<int>(std::ifstream("1.txt")),
        std::istream_iterator<int>()
    );
 
    std::list<int> lst2(
        std::istream_iterator<int>(std::ifstream("2.txt")),
        std::istream_iterator<int>()
    );
 
    lst1.sort();
    lst2.sort();
 
    std::list<int> result;
    std::merge(lst1.begin(), lst1.end(), lst2.begin(), lst2.end(), std::back_inserter(result));
 
    std::ofstream out("result.txt");
    std::copy(result.begin(), result.end(), std::ostream_iterator<int>(out, " "));
 
    return 0;
}
straus
0 / 0 / 0
Регистрация: 18.10.2010
Сообщений: 45
27.11.2010, 11:08  [ТС]     три двунаправленных списка #3
нет , не так надо... через first->next , curr, curr->next и так далее
NightmareZ
1339 / 562 / 37
Регистрация: 31.03.2009
Сообщений: 1,918
27.11.2010, 15:24     три двунаправленных списка #4
Цитата Сообщение от straus Посмотреть сообщение
нет , не так надо... через first->next , curr, curr->next и так далее
Ну так бы сразу и написал, что нужно сделать через анальный проход.
silent_1991
Эксперт С++
4960 / 3036 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
27.11.2010, 15:30     три двунаправленных списка #5
NightmareZ, неужели вы, когда учились, сами никогда не писали связные списки, стеки и т.д. вручную?
NightmareZ
1339 / 562 / 37
Регистрация: 31.03.2009
Сообщений: 1,918
27.11.2010, 15:36     три двунаправленных списка #6
Цитата Сообщение от silent_1991 Посмотреть сообщение
NightmareZ, неужели вы, когда учились, сами никогда не писали связные списки, стеки и т.д. вручную?
Писал конечно. Но где в ТЗ указано, что нужно сделать вручную?
silent_1991
Эксперт С++
4960 / 3036 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
27.11.2010, 15:41     три двунаправленных списка #7
Цитата Сообщение от NightmareZ
Но где в ТЗ указано, что нужно сделать вручную?
С этим согласен. Но ИМХО по заданию видно, что зачёт у них вряд-ли по STL
NightmareZ
1339 / 562 / 37
Регистрация: 31.03.2009
Сообщений: 1,918
27.11.2010, 17:04     три двунаправленных списка #8
Цитата Сообщение от silent_1991 Посмотреть сообщение
NightmareZ, неужели вы, когда учились, сами никогда не писали связные списки, стеки и т.д. вручную?
Ок, вот вариант "вручную":

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
#include <fstream>
#include <iterator>
 
template <class T>
class Node
{
private:
    Node *_prev, *_next;
    T _value;
public:
    Node(T value, Node *prev, Node *next)
        : _value(value), _prev(prev), _next(next)
    { 
        _prev->next = this;
        _next->_prev = this;
    }
 
    Node(T value, Node *prev)
        : _value(value), _prev(prev), _next(0)
    { 
        _prev->_next = this;
    }
 
    Node(T value)
        : _value(value), _prev(0), _next(0)
    { }
 
    Node* getPrev() const { return _prev; }
    Node* getNext() const { return _next; }
    T getValue() const { return _value; }
    void setValue(T value) { _value = value; }
};
 
template <class T>
class List
{
private:
    Node<T> *_head, *_tail;
public:
    List()
        : _head(0), _tail(0)
    { }
 
    ~List();
    void Add(T value);
    void Foreach(void (*f)(T value));
    void ForeachBack(void (*f)(T value));
    void Sort(bool (*comparer)(T a, T b));
    void Merge(List<T>& lst1, List<T>& lst2, bool (*comparer)(T a, T b));
};
 
template <class T>
List<T>::~List()
{
    Node<T> *curr = _head, *tmp;
 
    while (curr)
    {
        tmp = curr;
        curr = tmp->getNext();
        delete tmp;
    }
}
 
template <class T>
void List<T>::Add(T value)
{
    if (!_head)
        _head = _tail = new Node<T>(value);
    else
        _tail = new Node<T>(value, _tail);
}
 
template <class T>
void List<T>::Foreach(void (*f)(T value))
{
    for (Node<T> *curr = _head; curr; curr = curr->getNext())
        f(curr->getValue());
}
 
template <class T>
void List<T>::ForeachBack(void (*f)(T value))
{
    for (Node<T> *curr = _tail; curr; curr = curr->getPrev())
        f(curr->getValue());
}
 
template <class T>
void List<T>::Sort(bool (*comparer)(T a, T b))
{
    bool e = true;
 
    while (e)
    {
        e = false;
        for (Node<T> *curr = _head; curr; curr = curr->getNext())
        {
            if (curr->getNext() && !comparer(curr->getValue(), curr->getNext()->getValue()))
            {
                T tmp = curr->getValue();
                curr->setValue(curr->getNext()->getValue());
                curr->getNext()->setValue(tmp);
                e = true;
            }
        }
    }
}
 
template <class T>
void List<T>::Merge(List<T>& lst1, List<T>& lst2, bool (*comparer)(T a, T b))
{
    Node<T> *curr1 = lst1._head, *curr2 = lst2._head;
 
    while (curr1 && curr2)
    {
        if (comparer(curr1->getValue(), curr2->getValue()))
        {
            Add(curr1->getValue());
            curr1 = curr1->getNext();
        }
        else
        {
            Add(curr2->getValue());
            curr2 = curr2->getNext();
        }
    }
 
    while (curr1)
    {
        Add(curr1->getValue());
        curr1 = curr1->getNext();
    }
 
    while (curr2)
    {
        Add(curr2->getValue());
        curr2 = curr2->getNext();
    }
}
 
template <class T>
bool Comparer(T a, T b)
{
    return a < b;
}
 
std::ofstream outfile("result.txt");
 
template <class T>
void Output(T value)
{
    outfile << value << " ";
}
 
int main()
{
    std::ifstream file1("1.txt"), file2("2.txt");
    List<int> lst1, lst2, result;
 
    for (std::istream_iterator<int> it(file1); it != std::istream_iterator<int>(); it++)
        lst1.Add(*it);
 
    for (std::istream_iterator<int> it(file2); it != std::istream_iterator<int>(); it++)
        lst2.Add(*it);
 
    lst1.Sort(Comparer);
    lst2.Sort(Comparer);
    result.Merge(lst1, lst2, Comparer);
    result.Foreach(Output);
}
straus
0 / 0 / 0
Регистрация: 18.10.2010
Сообщений: 45
27.11.2010, 22:44  [ТС]     три двунаправленных списка #9
огого... это конечно ближе...первый раз вижу записи типа-template <class T> или <......> это типа определения класса что ли? public тоже неговори в списках! во муть то.... у нас видимо проще надо
NightmareZ
1339 / 562 / 37
Регистрация: 31.03.2009
Сообщений: 1,918
27.11.2010, 23:07     три двунаправленных списка #10
Цитата Сообщение от straus Посмотреть сообщение
первый раз вижу записи типа-template <class T> или <......> это типа определения класса что ли?
Это шаблоны. Чтобы списки можно было безболезненно разных типов делать.

Цитата Сообщение от straus Посмотреть сообщение
у нас видимо проще надо
Тебе язык то какой нужен? C++ или C?
straus
0 / 0 / 0
Регистрация: 18.10.2010
Сообщений: 45
27.11.2010, 23:13  [ТС]     три двунаправленных списка #11
с++
нам сказали исп iostream, fstream-без всяких примбамбасов видимо и стандартную библиотеку
функции упорядочивания и тд! видимо так...
NightmareZ
1339 / 562 / 37
Регистрация: 31.03.2009
Сообщений: 1,918
27.11.2010, 23:45     три двунаправленных списка #12
Цитата Сообщение от straus Посмотреть сообщение
с++
нам сказали исп iostream, fstream-без всяких примбамбасов видимо и стандартную библиотеку
функции упорядочивания и тд! видимо так...
Ну так самый первый мой ответ - это и есть без прибамбасов и только со стандартной библиотекой.

Добавлено через 29 минут
Ну на вот, ещё проще сделал:

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
#include <fstream>
#include <iterator>
 
class Node
{
private:
    Node *_prev, *_next;
    int _value;
public:
    Node(int value, Node *prev, Node *next)
        : _value(value), _prev(prev), _next(next)
    { 
        _prev->_next = this;
        _next->_prev = this;
    }
 
    Node(int value, Node *prev)
        : _value(value), _prev(prev), _next(0)
    { 
        _prev->_next = this;
    }
 
    Node(int value)
        : _value(value), _prev(0), _next(0)
    { }
 
    Node* getPrev() const { return _prev; }
    Node* getNext() const { return _next; }
    int getValue() const { return _value; }
    void setValue(int value) { _value = value; }
};
 
class List
{
private:
    Node *_head, *_tail;
public:
    List()
        : _head(0), _tail(0)
    { }
 
    ~List();
    void Add(int value);
    void Foreach(void (*f)(int value));
    void ForeachBack(void (*f)(int value));
    void Sort(bool (*comparer)(int a, int b));
    void Merge(List& lst1, List& lst2, bool (*comparer)(int a, int b));
};
 
List::~List()
{
    Node *curr = _head, *tmp;
 
    while (curr)
    {
        tmp = curr;
        curr = tmp->getNext();
        delete tmp;
    }
}
 
void List::Add(int value)
{
    if (!_head)
        _head = _tail = new Node(value);
    else
        _tail = new Node(value, _tail);
}
 
void List::Foreach(void (*f)(int value))
{
    for (Node *curr = _head; curr; curr = curr->getNext())
        f(curr->getValue());
}
 
void List::ForeachBack(void (*f)(int value))
{
    for (Node *curr = _tail; curr; curr = curr->getPrev())
        f(curr->getValue());
}
 
void List::Sort(bool (*comparer)(int a, int b))
{
    bool e = true;
 
    while (e)
    {
        e = false;
        for (Node *curr = _head; curr; curr = curr->getNext())
        {
            if (curr->getNext() && !comparer(curr->getValue(), curr->getNext()->getValue()))
            {
                int tmp = curr->getValue();
                curr->setValue(curr->getNext()->getValue());
                curr->getNext()->setValue(tmp);
                e = true;
            }
        }
    }
}
 
void List::Merge(List& lst1, List& lst2, bool (*comparer)(int a, int b))
{
    Node *curr1 = lst1._head, *curr2 = lst2._head;
 
    while (curr1 && curr2)
    {
        if (comparer(curr1->getValue(), curr2->getValue()))
        {
            Add(curr1->getValue());
            curr1 = curr1->getNext();
        }
        else
        {
            Add(curr2->getValue());
            curr2 = curr2->getNext();
        }
    }
 
    while (curr1)
    {
        Add(curr1->getValue());
        curr1 = curr1->getNext();
    }
 
    while (curr2)
    {
        Add(curr2->getValue());
        curr2 = curr2->getNext();
    }
}
 
bool Comparer(int a, int b)
{
    return a < b;
}
 
std::ofstream outfile("result.txt");
 
void Output(int value)
{
    outfile << value << " ";
}
 
int main()
{
    std::ifstream file1("1.txt"), file2("2.txt");
    List lst1, lst2, result;
 
    for (std::istream_iterator<int> it(file1); it != std::istream_iterator<int>(); it++)
        lst1.Add(*it);
 
    for (std::istream_iterator<int> it(file2); it != std::istream_iterator<int>(); it++)
        lst2.Add(*it);
 
    lst1.Sort(Comparer);
    lst2.Sort(Comparer);
    result.Merge(lst1, lst2, Comparer);
    result.Foreach(Output);
}
straus
0 / 0 / 0
Регистрация: 18.10.2010
Сообщений: 45
28.11.2010, 00:19  [ТС]     три двунаправленных списка #13
ну спасибо... не знаю это можно нет, кое какие комменты...
например зачем вначале privat? public?

lst1.Sort(Comparer) что значит точка
_prev->_next = this;
_next->_prev = this; почему this

struct Node{
double val;
Node * next;
Node * prev;
};

Node * first;
Node * last;


ну это я написал как мы заполняли

Добавлено через 2 минуты
так можно переправить приват и паблик?
NightmareZ
1339 / 562 / 37
Регистрация: 31.03.2009
Сообщений: 1,918
28.11.2010, 00:36     три двунаправленных списка #14
Цитата Сообщение от straus Посмотреть сообщение
ну спасибо... не знаю это можно нет, кое какие комменты...
например зачем вначале privat? public?
Области видимости. То, что в private, видно только изнутри класса, а то, что в public, видно всем. В private нужно помещать реализацию, а в public интерфейс.

Цитата Сообщение от straus Посмотреть сообщение
lst1.Sort(Comparer) что значит точка
Значит, что обращаемся к функции-члену класса через объект. Если бы обращались через указатель на объект, то вместо точки использовали бы оператор ->

Цитата Сообщение от straus Посмотреть сообщение
_next->_prev = this; почему this
Потому что устанавливаем указателю на следующую ноду предыдущей ноды адрес текущей ноды. Ключевое слово this позволяет получать указатель на текущий объект.

Цитата Сообщение от straus Посмотреть сообщение
так можно переправить приват и паблик?
Можно. Помести всё в public. Но это очень плохая практика и в реальных проектах за такое нужно анально карать.

Цитата Сообщение от straus Посмотреть сообщение
это я написал как мы заполняли
Всё дело в том, что вы изучаете не C++. Вы изучаете C, и зачем-то к этому привязываете небольшие фрагмены из C++. Потому что система образования у нас убогая и преподы (в большинстве своём) тоже.

Написал решение на C, может тебе оно будет понятнее:

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
175
176
177
178
179
180
181
182
183
184
185
#include <stdlib.h>
#include <stdio.h>
 
typedef struct Node
{
    struct Node *prev, *next;
    int value;
} Node;
 
 
typedef struct List
{
    Node *head, *tail;
} List;
 
List* createList()
{
    List* lst = (List*)malloc(sizeof(List));
    lst->head = 0;
    lst->tail = 0;
    return lst;
}
 
void deleteList(List* const lst)
{
    Node *curr = lst->head, *tmp;
 
    while (curr)
    {
        tmp = curr;
        curr = tmp->next;
        free(tmp);
    }
 
    free(lst);
}
 
void addToList(List* const lst, int value)
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->value = value;
 
    if (!lst->head)
    {
        newNode->prev = 0;
        newNode->next = 0;
        lst->head = lst->tail = newNode;
    }
    else
    {
        newNode->prev = lst->tail;
        newNode->next = 0;
        lst->tail->next = newNode;
        lst->tail = newNode;
    }
}
 
void foreach(const List* const lst, void (*f)(int value))
{
    Node *curr;
 
    for (curr = lst->head; curr; curr = curr->next)
        f(curr->value);
}
 
void foreachBack(const List* const lst, void (*f)(int value))
{
    Node *curr;
 
    for (curr = lst->tail; curr; curr->prev)
        f(curr->value);
}
 
void sort(List* const lst, int (*comparer)(int a, int b))
{
    Node *curr;
    int e = 1, tmp;
 
    while (e)
    {
        e = 0;
        for (curr = lst->head; curr; curr = curr->next)
        {
            if (curr->next && !comparer(curr->value, curr->next->value))
            {
                tmp = curr->value;
                curr->value = curr->next->value;
                curr->next->value = tmp;
                e = 1;
            }
        }
    }
}
 
void merge(List* const result, 
    const List* const lst1, const List* const lst2, int (*comparer)(int a, int b))
{
    Node *curr1, *curr2;
    
    curr1 = lst1->head;
    curr2 = lst2->head;
 
    while (curr1 && curr2)
    {
        if (comparer(curr1->value, curr2->value))
        {
            addToList(result, curr1->value);
            curr1 = curr1->next;
        }
        else
        {
            addToList(result, curr2->value);
            curr2 = curr2->next;
        }
    }
 
    while (curr1)
    {
        addToList(result, curr1->value);
        curr1 = curr1->next;
    }
 
    while (curr2)
    {
        addToList(result, curr2->value);
        curr2 = curr2->next;
    }
}
 
int comparer(int a, int b)
{
    return a < b;
}
 
void readFile(List* lst, FILE* file)
{
    int value;
 
    while (!feof(file))
    {
        fscanf(file, "%d", &value);
        addToList(lst, value);
    }
}
 
FILE *outfile;
 
void writeFile(int value)
{
    fprintf(outfile, "%d ", value);
}
 
int main(void)
{
    FILE *file1, *file2;
    List *lst1, *lst2, *result;
 
    lst1 = createList();
    lst2 = createList();
 
    file1 = fopen("1.txt", "r");
    file2 = fopen("2.txt", "r");
 
    readFile(lst1, file1);
    readFile(lst2, file2);
 
    fclose(file2);
    fclose(file1);
 
    sort(lst1, comparer);
    sort(lst2, comparer);
 
    result = createList();
    merge(result, lst1, lst2, comparer);
    
    deleteList(lst2);
    deleteList(lst1);
 
    outfile = fopen("result.txt", "w");
    foreach(result, writeFile);
    fclose(outfile);
    deleteList(result);
 
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.11.2010, 00:42     три двунаправленных списка
Еще ссылки по теме:

Проверка, пуст ли список, очистка списка, печать списка в направлении от верха к низу - C++
Доброго вечера. Пожалуйста помогите разобраться с заданием на структуры, и подскажите с чего здесь начинать? 1) Кольцевой...

Списки. К каждому элементу списка прибавить значение следующего элемента списка. Последний элемент не менять - C++
Данные списка должен ввести пользователь. Результат нужно сформировать в начальном списке, никаких новых списков создавать нельзя. Спасибо!

Три массива - C++
Всем привет! Помогите пожалуйста - очень прошу всех! Есть код на Паскале только с процедурами, помогите пожалуйста переделать с...

Три числа - C++
Среди трех чисел (а = 7/5 * ch (x); b = 1 + | x |; c = (1 + x) / x) найти два максимальных, вывести их произведение и расположить в порядке...


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

Или воспользуйтесь поиском по форуму:
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
28.11.2010, 00:42     три двунаправленных списка #15
NightmareZ, Прошу прощения... Но как же правила хорошего тона, которые призывают НЕ писать такие названия для переменных?

Код
    Node *_prev, *_next;
    T _value;
Yandex
Объявления
28.11.2010, 00:42     три двунаправленных списка
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru