Создайте шаблонный класс односвязного списка. C++

@Arbuz228 · Регистрация: 22.04.2020

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

Требуется создать реализации для типичных операций над элементами:
- AddToHead – добавление элемента в голову;
- AddToTail – добавление элемента в хвост;
- DeleteFromHead – удаление элемента из головы;
- DeleteFromTail – удаление элемента из хвоста;
- DeleteAll – удаление всех элементов;
- Show – отображение всех элементов списка на экран.

Вот что я написал.
Я запутался, head слева или справа ?
Функция Добавления добавляет в tail или в head ?

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
#include <iostream>
#include <time.h>
using namespace std;
template <typename T>
struct Element
{
    T data;
    Element<T>* next;
};
 
template <typename T>
class MyList
{
private:
    Element<T>* head;
    Element<T>* tail;
    int count;
public:
    MyList()
    {
        head = tail = NULL;
        count = 0;
    }
 
    ~MyList()
    {
        DeleteAll();
    }
    void AddToHead(T value)
    {
        Element<T>* temp = new Element<T>;
        temp->data = value;
        temp->next = NULL;
 
        if (head == NULL)
        {
            head = tail = temp;
        }
        else
        {
            tail->next = temp;
            tail = temp;
        }
        count++;
    }
    void DeleteFromTail()
    {
        if (head == nullptr)
        {
            return;
        }
        else {
            Element<T>* temp = head->next;
            delete head;
            head = temp;
            count--;
        }
    }
 
    void DeleteAll()
    {
        while (head != NULL)
        {
            DeleteFromTail();
        }
    }
 
    void Print()
    {
        Element<T>* temp = head;
 
        while (temp != NULL)
        {
            cout << temp->data << ' ';
            temp = temp->next;
        }
        cout << endl;
    }
 
    int GetCount()
    {
        return count;
    }
};
int main()
{
    srand(time(NULL));
    MyList<int> List1;
    int count = 5;
 
    for (int i = 0; i < count; i++)
    {
        List1.AddToHead(i);
    }
 
    cout << "count = " << List1.GetCount() << endl;
 
    List1.Print();
}

Добавлено через 10 минут
Еще , функция удаления удаляет с tail или head ?

@_stanislav · 29.11.2020, 11:43

Сообщение от Arbuz228

head

это начало списка (голова)

Сообщение от Arbuz228

tail

это конец списка (хвост)

справа или с лева они у тебя будут хз.

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

Сообщение от Arbuz228

tail или head

не важно

@Arbuz228 · 29.11.2020, 11:48 **[ТС]**

Сообщение от _stanislav

tail или head

А как реализовать функцию добавления в начало ?

@_stanislav · 29.11.2020, 12:01

Сообщение от Arbuz228

А как реализовать функцию добавления в начало ?

определяешь новый узел, записываешь в указатель next нового узла текущий head

@Jason · 29.11.2020, 12:02

Создать новый элемент, от него next будет head и заменить head на новый.

@Arbuz228 · 29.11.2020, 12:08 **[ТС]**

Сообщение от Jason

Создать новый элемент, от него next будет head и заменить head на новый.

Не получается

void AddToHead(T value)// В начало списка.
{
Element<T>* temp = new Element<T>;
temp->data = value;
temp->next = NULL;

if (head == NULL)
{
head = tail = temp;
}
else
{
head->next = head;
head = temp;
}
count++;
}

Добавлено через 28 секунд
Выводит только последний элемент

@Jason · 29.11.2020, 12:10

C++
1
2
3
4
5
6
7
8
9
        if (head == NULL)
        {
            head = tail = temp;
        }
        else
        {
            temp->next = head;
            head = temp;
        }

@Arbuz228 · 29.11.2020, 12:10 **[ТС]**

Сообщение от Arbuz228

head->next = head;

Я увидел, надо head первый заменить на next
Спасибо !!!

@Jason · 29.11.2020, 12:10

Arbuz228, так ты посмотри внимательно, что написал...

@Arbuz228 · 29.11.2020, 12:21 **[ТС]**

Где тут ошибка ? не могу понять

C++
1
2
3
4
5
6
7
8
9
10
11
void DeleteFromTail()
    {
        if (head == nullptr)
        {
            return;
        }
        else {
            delete tail;
            count--;
        }
    }

@Jason · 29.11.2020, 14:04

Arbuz228, нужно хранить prev, либо бежать по списку, искать предпоследний элемент и уничтожать его next и в tail записать этот предпоследний элемент.

Добавлено через 1 час 34 минуты
Arbuz228, как-то так, но добавь проверки на удаление элементов (pop_head / pop_tail):

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
#include <iostream>
 
using namespace std;
 
template <typename type>
struct Element {
    type data;
    Element<type> *next;
    Element<type> *prev;
};
 
template <typename type>
class List {
    Element<type> *head;
    Element<type> *tail;
    unsigned int count;
    
public:
    List() {
        head = tail = nullptr;
        count = 0;
    }
    
    void push_head(type value) {
        Element<type>* tmp = new Element<type>;
        tmp->data = value;
        tmp->next = nullptr;
        if (!head)
            head = tail = tmp;
        else {
            head->prev = tmp;
            tmp->next = head;
            head = tmp;
        }
        count++;
    }
    
    void push_tail(type value) {
        Element<type>* tmp = new Element<type>;
        tmp->data = value;
        tmp->next = nullptr;
        if (!head)
            head = tail = tmp;
        else {
            tail->next = tmp;
            tmp->prev = tail;
            tail = tmp;
        }
        count++;
    }
    
    void pop_head() {
        Element<type>* tmp = head->next;
        tmp->prev = nullptr;
        delete head;
        head = tmp;
    }
    
    void pop_teil() {
        Element<type>* tmp = tail->prev;
        tmp->next = nullptr;
        delete tail;
        tail = tmp;
    }
    
    void print() {
        Element<type>* tmp = head;
        while (tmp) {
            cout << tmp->data << " ";
            tmp = tmp->next;
        }
        cout << endl;
    }
}; 
 
int main()
{
    List<int> list;
 
    for (int i = 1; i < 6; i++)
        list.push_head(i);
    list.print();
 
    list.push_head(0);
    list.push_tail(0);
    list.print();
 
    list.pop_head();
    list.print();
 
    list.pop_teil();
    list.print();
}

@Arbuz228 · 29.11.2020, 14:20 **[ТС]**

Сообщение от Jason

Arbuz228, нужно хранить prev, либо бежать по списку, искать предпоследний элемент и уничтожать его next и в tail записать этот предпоследний элемент.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void DeleteFromTail()
    {
        if (head == nullptr)
        {
            return;
        }
        else {
            Element<T>* temp = head;
            int count1 = 0;
            while (head != nullptr)
            {
                if (count == count)
                {
                    delete temp;
                    count--;
                    break;
                }
                temp = temp->next;
                count1++;
            }
        }
    }

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

Сообщение от Jason

как-то так, но добавь проверки на удаление элементов (pop_head / pop_tail):

Разве это не двухсвязный список?

@Jason · 29.11.2020, 14:25

Arbuz228, что-то не понятное по названию функции уделяешь хвост, а используешь голову и не верное условие:

C++
1
if (count == count)

Должен быть наверное count1, а лучше for использовать для этой цели.

Добавлено через 3 минуты
Arbuz228, не посмотрел на название темы... Тогда используй for...

@Arbuz228 · 29.11.2020, 14:35 **[ТС]**

Почему nullptr tail ? Не вдупляю

C++
1
2
3
4
5
6
7
8
9
10
11
12
void DeleteFromTail()
    {
        Element<T>* temp = tail;
        for (int i=0;i<count-1;i++)
        {
            temp = temp->next;
        }
        Element<T>* tmp = temp;
        tmp->next = nullptr;
        delete tail;
        tail = tmp;
    }

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
void DeleteFromTail()
    {
        Element<T>* temp = head;
        for (int i=0;i<count-2;i++)
        {
            temp = temp->next;
        }
        Element<T>* tmp = temp;
        tmp->next = nullptr;
        delete tail;
        tail = tmp;
    }

@Jason · 29.11.2020, 14:41

C++
1
2
3
4
5
6
7
    void pop_teil() {
        Element<type>* tmp = head;
        for (int i = 1; i < count - 1; i++)
            tmp = tmp->next;
        delete tmp->next;
        tmp->next = nullptr;
    }

@Arbuz228 · 29.11.2020, 14:57 **[ТС]**

Лутший Брат !!!!!

@Jason · 29.11.2020, 15:01

Arbuz228, вот полный код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    void pop_tail() {
        if (head) {
            if (count == 1) {
                head = tail = nullptr;
                count = 0;
            }
            else {  
                Element<type>* tmp = head;
                for (int i = 1; i < count - 1; i++)
                    tmp = tmp->next;
                delete tmp->next;
                tmp->next = nullptr;
                tail = tmp;
                count--;
            }
        }
    }

@Arbuz228 · 29.11.2020, 15:30 **[ТС]**

Вот полный Класс
Может кому нужно:

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
template <typename T>
struct Element
{
    T data;
    Element<T>* next;
};
template <typename T>
class MyList
{
private:
    Element<T>* head;
    Element<T>* tail;
    int count;
public:
    MyList()
    {
        head = tail = NULL;
        count = 0;
    }
 
    ~MyList()
    {
        DeleteAll();
    }
    void AddToTail(T value)// В конец списка.
    {
        Element<T>* temp = new Element<T>;
        temp->data = value;
        temp->next = NULL;
 
        if (head == NULL)
        {
            head = tail = temp;
        }
        else
        {
            tail->next = temp;
            tail = temp;
        }
        count++;
    }
    void AddToHead(T value)// В начало списка.
    {
        Element<T>* temp = new Element<T>;
        temp->data = value;
        temp->next = NULL;
 
        if (head == NULL)
        {
            head = tail = temp;
        }
        else
        {
            temp->next = head;
            head = temp;
        }
        count++;
    }
    void DeleteFromHead()
    {
        if (head == nullptr)
        {
            return;
        }
        else {
            Element<T>* temp = head->next;
            delete head;
            head = temp;
            count--;
        }
    }
    void DeleteFromTail()
    {
        Element<T>* tmp = head;
        for (int i = 1; i < count - 1; i++)
            tmp = tmp->next;
        delete tmp->next;
        tmp->next = nullptr;
        count--;
    }
 
 
    void DeleteAll()
    {
        while (head != NULL)
        {
            DeleteFromHead();
        }
    }
 
    void Print()
    {
        Element<T>* temp = head;
 
        while (temp != NULL)
        {
            cout << temp->data << ' ';
            temp = temp->next;
        }
        cout << endl;
    }
 
    int GetCount()
    {
        return count;
    }
};

@Jason · 29.11.2020, 15:55

Arbuz228, этим методом не удалить последний элемент (голову):

C++
1
2
3
4
5
6
7
8
9
    void DeleteFromTail()
    {
        Element<T>* tmp = head;
        for (int i = 1; i < count - 1; i++)
            tmp = tmp->next;
        delete tmp->next;
        tmp->next = nullptr;
        count--;
    }

@Arbuz228 · 29.11.2020, 17:26 **[ТС]**

Сообщение от Jason

Arbuz228, этим методом не удалить последний элемент (голову):

А почему он работает как надо ?
Ваш метод оставляет только последний элемент
Вот:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void pop_tail() {
        if (head) {
            if (count == 1) {
                head = tail = nullptr;
                count = 0;
            }
            else {  
                Element<type>* tmp = head;
                for (int i = 1; i < count - 1; i++)
                    tmp = tmp->next;
                delete tmp->next;
                tmp->next = nullptr;
                tail = tmp;
                count--;
            }
        }
    }

Новые блоги и статьи Все статьи Все блоги /
Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .
Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .

Создайте шаблонный класс односвязного списка. C++

Решение

Решение

Решение

@Jason 525 / 487 / 99 Регистрация: 25.12.2011 Сообщений: 1,176
	29.11.2020, 12:02
	Сообщение было отмечено Arbuz228 как решение Решение Создать новый элемент, от него next будет head и заменить head на новый. 0

@Jason 525 / 487 / 99 Регистрация: 25.12.2011 Сообщений: 1,176
	29.11.2020, 12:10
	Сообщение было отмечено Arbuz228 как решение Решение Arbuz228, так ты посмотри внимательно, что написал... 0

@Arbuz228 0 / 0 / 0 Регистрация: 22.04.2020 Сообщений: 24
	29.11.2020, 14:57 [ТС]
	Лутший Брат !!!!! 0