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

Linked List описание - C++

Восстановить пароль Регистрация
 
bekabot
1 / 1 / 0
Регистрация: 18.12.2013
Сообщений: 61
08.03.2014, 21:18     Linked List описание #1
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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
/*!Begin Snippet:filebegin*/
#ifndef _LINKEDLIST_H_
#define _LINKEDLIST_H_
 
using namespace std;
 
/*!Begin Snippet:fullnode*/
/*!Begin Snippet:private*/
template <typename T>
class LinkedList {
 
private:
    class Node {
        friend class LinkedList<T>;
 
    private:
        T data;
        Node* next;
 
    public:
        Node(T d, Node* n = NULL) : data(d), next(n) {}}
    ;
    /*!End Snippet:fullnode*/
 
    Node* head;  // Beginning of list
    Node* tail;  // End of list
    int count;    // Number of nodes in list
    /*!End Snippet:private*/
 
public:
 
    LinkedList(const LinkedList<T>& src);  // Copy constructor
    ~LinkedList(void);  // Destructor
 
    /*!Begin Snippet:simple*/
    // Default constructor
    LinkedList(void) : head(NULL), tail(NULL), count(0) {}
 
    // Returns a reference to first element
    T& front(void) {
        assert (head != NULL);
        return head->data;
    }
 
    // Returns a reference to last element
    T& back(void) {
        assert (tail != NULL);
        return tail->data;
    }
 
    // Returns count of elements of list
    int size(void) {
        return count;
    }
 
    // Returns whether or not list contains any elements
    bool empty(void) {
        return count == 0;
    }
    /*!End Snippet:simple*/
 
    void push_front(T);  // Insert element at beginning
    void push_back(T);   // Insert element at end
    void pop_front(void);  // Remove element from beginning
    void pop_back(void);  // Remove element from end
 
    void dump(void);  // Output contents of list
};
 
/*!Begin Snippet:copyconstructor*/
// Copy constructor
template <typename T>
LinkedList<T>::LinkedList(const LinkedList<T>& src) :
        head(NULL), tail(NULL), count(0) {
 
    Node* current = src.head;
    while (current != NULL) {
        this->push_back(current->data);
        current = current->next;
    }
 
}
/*!End Snippet:copyconstructor*/
 
/*!Begin Snippet:destructor*/
// Destructor
template <typename T>
LinkedList<T>::~LinkedList(void) {
 
    while (! this->empty()) {
        this->pop_front();
    }
}
/*!End Snippet:destructor*/
 
/*!Begin Snippet:pushfront*/
// Insert an element at the beginning
template <typename T>
void LinkedList<T>::push_front(T d) {
 
    Node* new_head = new Node(d, head);
 
    if (this->empty()) {
        head = new_head;
        tail = new_head;
    } else {
        head = new_head;
    }
    count++;
}
/*!End Snippet:pushfront*/
 
/*!Begin Snippet:pushback*/
// Insert an element at the end
template <typename T>
void LinkedList<T>::push_back(T d) {
 
    Node* new_tail = new Node(d, NULL);
 
    if (this->empty()) {
        head = new_tail;
    } else {
        tail->next = new_tail;
    }
 
    tail = new_tail;
    count++;
}
/*!End Snippet:pushback*/
 
/*!Begin Snippet:popfront*/
// Remove an element from the beginning
template <typename T>
void LinkedList<T>::pop_front(void) {
 
    assert(head != NULL);
 
    Node* old_head = head;
 
    if (this->size() == 1) {
        head = NULL;
        tail = NULL;
    } else {
        head = head->next;
    }
 
    delete old_head;
    count--;
}
/*!End Snippet:popfront*/
 
/*!Begin Snippet:popback*/
// Remove an element from the end
template <typename T>
void LinkedList<T>::pop_back(void) {
 
    assert(tail != NULL);
 
    Node* old_tail = tail;
 
    if (this->size() == 1) {
        head = NULL;
        tail = NULL;
    } else {
 
        // Traverse the list to node just before tail
        Node* current = head;
        while (current->next != tail) {
            current = current->next;
        }
 
        // Unlink and reposition
        current->next = NULL;
        tail = current;
    }
 
    delete old_tail;
    count--;
}
/*!End Snippet:popback*/
 
/*!Begin Snippet:printlist*/
// Display the contents of the list
template <typename T>
void LinkedList<T>::dump(void) {
 
    cout << "(";
 
    Node* current = head;
 
    if (current != NULL) {
 
        while (current->next != NULL) {
            cout << current->data << ", ";
            current = current->next;
        }
        cout << current->data;
    }
 
    cout << ")" << endl;
}
/*!End Snippet:printlist*/
 
/*!End Snippet:filebegin*/
#endif
в комментариях кода пишется, что head - начало списка, а tail - конец списка, но я так и не понял, где в коде указывается(описывается), что это именно так. Укажите строку, спасибо
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.03.2014, 21:18     Linked List описание
Посмотрите здесь:

linked error C++
Связанный список (Linked list). C++
Ошибка при компиляции undefined reference to `List<int>::List()'| C++
[Linked Error] Unresolved External C++
Проверить программу с linked list C++
Нужен совет - как сделать circular linked list? C++
C++ C-style Linked List
Linked List: error C2360: initialization of 'vp' is skipped by 'case' label C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
08.03.2014, 21:34     Linked List описание #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
конкретной строчки нет. весь код написан так.
например втыкание элемента в конец списка. для этого
нужно взять хвост и сделать так, чтобы старый tail->next указывал
на новый вставленный элемент и сделать хвостом этот новый элемент.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename T>
void LinkedList<T>::push_back(T d) {
 
    Node* new_tail = new Node(d, NULL);
 
    if (this->empty()) {
        head = new_tail;
    } else {
        tail->next = new_tail;
    }
 
    tail = new_tail;
    count++;
}
остальные функции тоже написаны так, чтобы хвост оставался хвостом а голова - головой после
модификации списка.
BigProgrammer
38 / 38 / 3
Регистрация: 20.07.2013
Сообщений: 105
08.03.2014, 21:42     Linked List описание #3
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Смотрите реализацию методов pop_front, pop_back, push_front, push_back. Они читают и изменяют поля head и tail.
Yandex
Объявления
08.03.2014, 21:42     Linked List описание
Ответ Создать тему
Опции темы

Текущее время: 06:21. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru