Переделать список

@cherc · Регистрация: 02.05.2018

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

Нужно сделать функцию сортировки слиянием(по возрастанию например).

Вот мой список

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
struct Node                             //Структура, являющаяся звеном списка
 {
     int x;                             //Значение x будет передаваться в список
     Node *Next, *Prev;                 //Указатели на адреса следующего и предыдущего элементов списка
 };
 
 class MyList                              //Создаем тип данных Список
 {
    public:
     Node *Head, *Tail;                 //Указатели на адреса начала списка и его конца
 
     MyList():Head(NULL),Tail(NULL){};    //Инициализируем адреса как пустые
     ~MyList();                           //Прототип деструктора
     void Show();                       //Прототип функции отображения списка на экране
     void Add(int x);                   //Прототип функции добавления элементов в список
     int GetSize();  // получаем размер списка
     void Remove(int index);  // удаление по индексу
     void Insert(int x, int index); // помещаем новый элемент по заданному индексу
     void Clear(); // ф-я для очищения списка, хотя детруктор и так долен очищать список после работы
     Node* GetBanner(int index);   // получаем элемент по индексу
 };
 
MyList::~MyList()                           //Деструктор
 {
     while (Head)                       //Пока по адресу на начало списка что-то есть
     {
         Tail = Head->Next;             //Резервная копия адреса следующего звена списка
         delete Head;                   //Очистка памяти от первого звена
         Head = Tail;                   //Смена адреса начала на адрес следующего элемента
     }
 }
 
 void MyList::Add(int x)
 {
   Node *temp = new Node;               //Выделение памяти под новый элемент структуры
   temp->Next = NULL;                   //Указываем, что изначально по следующему адресу пусто
   temp->x = x;
 
   if (Head != NULL)                    //Если список не пуст
   {
       temp->Prev = Tail;               //Указываем адрес на предыдущий элемент в соотв. поле
       Tail->Next = temp;               //Указываем адрес следующего за хвостом элемента
       Tail = temp;                     //Меняем адрес хвоста
   }
   else //Если список пустой
   {
       temp->Prev = NULL;               //Предыдущий элемент указывает в пустоту
       Head = Tail = temp;              //Голова=Хвост=тот элемент, что сейчас добавили
   }
 };
 
void MyList::Remove(int index)
{
    Node *temp = Head;
 
    for(int i(1); i < index; i++)
    {
        temp = temp->Next;
 
        if(temp == Head)  // если начало списка
        {
            temp->Prev;
            if(Head)
            {
                Head->Prev = NULL;
            }
            else
            {
                Tail = NULL;
            }
 
           delete temp;
        }
        if(temp == Tail) // если конец списка
        {
            Tail = Tail->Prev;
            if(Tail)
            {
                Tail->Next = NULL;
            }
 
            delete temp;
        }
        temp->Prev->Next = temp->Next;
        temp->Next->Prev = temp->Prev;
        delete temp;
    }
}
 
void MyList::Show()
{
    Node *temp = Head;
 
    if(temp == NULL)
    {
        cout << "Список пуст!" << endl;
    }
    else
    {
        while(temp)
        {
            cout << temp->x;
            temp = temp->Next;
        }
    }
}
 
void MyList::Clear()
{
    while(Head)
    {
        Tail = Head->Next;
        delete Head;
        Head = Tail;
    }
}
 
int MyList::GetSize()
{
    Node *temp = Head;
    int i(0);
 
    while(temp)
    {
        i++;
        temp = temp->Next;
    }
 
    return i;
}
 
Node* MyList::GetBanner(int index)
{
    Node *temp = Head;
    int i = 0;
    while(temp && i < index)
    {
        temp = temp->Next;
        i++;
    }
    return temp;
}

Я уже делал это по другому(сейчас хочу отделить сам список от класса который будет туда передаваться), код ниже:
Это сам список

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
struct Student
{
    int gender;   // Пол ученика
    string fio;    // Фамилия ученика
    double mass;   // Масса ученика
    double growth;  // Рост ученика
    Student *Prev = NULL;
    Student *Next = NULL;
};
typedef Student *student;
student Head = NULL;
student Tail = NULL;
 
student NewStudent(int gen, string f, double m, double g)
{
    student Node = new Student;
    Node->gender = gen;
    Node->fio = f;
    Node->mass = m;
    Node->growth = g;
    Node->Next = NULL;
    Node->Prev = NULL;
    return Node;
}

Это сортировка слиянием для него

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
student Remove(student stud)
{
    if ((Head == NULL) || (Tail == NULL)) return NULL;
 
    if (Head == Tail)
    {
        Head = NULL;
        Tail = NULL;
        stud->Next = NULL;
        stud->Prev = NULL;
        return stud;
    }
 
    if (stud == Head)
    {
        Head = stud->Next;
        Head->Prev = NULL;
        stud->Next = NULL;
        stud->Prev = NULL;
        return stud;
    }
 
    if (stud == Tail)
    {
        Tail = stud->Prev;
        Tail->Next = NULL;
        stud->Next = NULL;
        stud->Prev = NULL;
        return stud;
    }
 
    //Для остальных случаев
    stud->Prev->Next = stud->Next;
    stud->Next->Prev = stud->Prev;
    stud->Next = NULL;
    stud->Prev = NULL;
    return stud;
}
 
void InsertSort()
{
    student stud = Head;
    student a = NULL;
    student b = NULL;
    student c = NULL;
 
    if (Head == Tail || Head == NULL || Tail == NULL)  //Проверка на пустоту и на один элемент
    {
        return;
    }
    stud = stud->Next;
 
    while (stud != NULL)
    {
        a = stud->Prev;
 
        while (a != NULL && stud->growth < a->growth)
        {
            a = a->Prev;
        }
        b = a->Next;
        c = Remove(stud);
 
        if (a == NULL)
        {
            AddFirst(c);
        }
        else Add(c);
 
        stud = b;
        c = NULL;
    }
}

@ReDoX · 23.02.2019, 10:28

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

сортировка слиянием

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

InsertSort

Кто врет?

@cherc · 23.02.2019, 11:48 **[ТС]**

ReDoX, не то вставил
Вот сортировка слиянием

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
student Merge(student a, student b)
{
    student head = NULL;
    student tail = NULL;
 
    while (true)
    {
 
        if (a == NULL)
        {
            if (tail == NULL)
            {
                head = b;
                head->Prev = NULL;
 
                return head;
            }
            else
            {
                tail->Next = b;
                b->Prev = tail;
 
                return head;
            }
        }
        if (b == NULL)
        {
            if (tail == NULL)
            {
                head = a;
                a->Prev = NULL;
 
                return head;
            }
            else
            {
                tail->Next = a;
                a->Prev = tail;
 
                return head;
            }
        }
 
        if (a->growth > b->growth)
        {
            if (tail == NULL)
            {
                head = a;
                tail = a;
                head->Prev = NULL;
            }
            else
            {
                tail->Next = a;
                a->Prev = tail;
                tail = a;
            }
            a = a->Next;
            tail->Next = NULL;
        }
        else
        {
            if (tail == NULL)
            {
                head = b;
                tail = b;
                head->Prev = NULL;
            }
            else
            {
                tail->Next = b;
                b->Prev = tail;
                tail = b;
            }
 
            b = b->Next;
            tail->Next = NULL;
        }
    }
}
 
student GetMiddle(student c, student tail = NULL)  //поиск середины
{
    student a = c;
    student b = c;
    if (tail != NULL) tail = tail->Next;
    while (b->Next != tail && b->Next->Next != tail)
    {
        a = a->Next;
        b = b->Next->Next;
    }
    return a;
}
 
student MergeSort(student c)
{
    if (c->Next == NULL)
    {
        return c;
    }
 
    student middle = GetMiddle(c);
    student r = middle->Next;  //Начало второй части списка (после разделения)
 
    r->Prev = NULL;
    middle->Next = NULL;
 
    c = MergeSort(c);
    r = MergeSort(r);
 
    return Merge(c, r);
}

@zayats80888 · 23.02.2019, 12:07

я бы так сделал, а то в вашем алгоритме не разберешься:

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
student remove(student p)
{
    if (!p) return 0;
    if (!p->Next) Tail=p->Prev;
    else p->Next->Prev=p->Prev;
    if (!p->Prev) Head=p->Next;
    else p->Prev->Next=p->Next;
    p->Next=0;
    p->Prev=0;
    return p;
}
 
 
student min_growth(student p)
{
    if (!p) return 0;
    student min=p;
    while (p=p->Next) if (p->growth<min->growth) min=p;
    return min;
}
 
 
void InsertSort()//суть алгоритма-вытащить минимальный и вставить в начало
{
    localHead=Head;//проверки сами добавьте
 
    while (localHead->Next){
        add(remove(min_growth(localHead)));//при условии что add() добавляет во главу списка
        localHead=localHead->Next;
    }
}

@cherc · 23.02.2019, 12:19 **[ТС]**

zayats80888, я перепутал, это сортировка вставками, я в ответе ReDox прикрепил сортировку слиянием, который надо переделать, чтоб он работал здесь

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
struct Node                             //Структура, являющаяся звеном списка
 {
     int x;                             //Значение x будет передаваться в список
     Node *Next, *Prev;                 //Указатели на адреса следующего и предыдущего элементов списка
 };
 
 class MyList                              //Создаем тип данных Список
 {
    public:
     Node *Head, *Tail;                 //Указатели на адреса начала списка и его конца
 
     MyList():Head(NULL),Tail(NULL){};    //Инициализируем адреса как пустые
     ~MyList();                           //Прототип деструктора
     void Show();                       //Прототип функции отображения списка на экране
     void Add(int x);                   //Прототип функции добавления элементов в список
     int GetSize();  // получаем размер списка
     void Remove(int index);  // удаление по индексу
     void Insert(int x, int index); // помещаем новый элемент по заданному индексу
     void Clear(); // ф-я для очищения списка, хотя детруктор и так долен очищать список после работы
     Node* GetBanner(int index);   // получаем элемент по индексу
 };
 
MyList::~MyList()                           //Деструктор
 {
     while (Head)                       //Пока по адресу на начало списка что-то есть
     {
         Tail = Head->Next;             //Резервная копия адреса следующего звена списка
         delete Head;                   //Очистка памяти от первого звена
         Head = Tail;                   //Смена адреса начала на адрес следующего элемента
     }
 }
 
 void MyList::Add(int x)
 {
   Node *temp = new Node;               //Выделение памяти под новый элемент структуры
   temp->Next = NULL;                   //Указываем, что изначально по следующему адресу пусто
   temp->x = x;
 
   if (Head != NULL)                    //Если список не пуст
   {
       temp->Prev = Tail;               //Указываем адрес на предыдущий элемент в соотв. поле
       Tail->Next = temp;               //Указываем адрес следующего за хвостом элемента
       Tail = temp;                     //Меняем адрес хвоста
   }
   else //Если список пустой
   {
       temp->Prev = NULL;               //Предыдущий элемент указывает в пустоту
       Head = Tail = temp;              //Голова=Хвост=тот элемент, что сейчас добавили
   }
 };
 
void MyList::Remove(int index)
{
    Node *temp = Head;
 
    for(int i(1); i < index; i++)
    {
        temp = temp->Next;
 
        if(temp == Head)  // если начало списка
        {
            temp->Prev;
            if(Head)
            {
                Head->Prev = NULL;
            }
            else
            {
                Tail = NULL;
            }
 
           delete temp;
        }
        if(temp == Tail) // если конец списка
        {
            Tail = Tail->Prev;
            if(Tail)
            {
                Tail->Next = NULL;
            }
 
            delete temp;
        }
        temp->Prev->Next = temp->Next;
        temp->Next->Prev = temp->Prev;
        delete temp;
    }
}
 
void MyList::Show()
{
    Node *temp = Head;
 
    if(temp == NULL)
    {
        cout << "Список пуст!" << endl;
    }
    else
    {
        while(temp)
        {
            cout << temp->x;
            temp = temp->Next;
        }
    }
}
 
void MyList::Clear()
{
    while(Head)
    {
        Tail = Head->Next;
        delete Head;
        Head = Tail;
    }
}
 
int MyList::GetSize()
{
    Node *temp = Head;
    int i(0);
 
    while(temp)
    {
        i++;
        temp = temp->Next;
    }
 
    return i;
}
 
Node* MyList::GetBanner(int index)
{
    Node *temp = Head;
    int i = 0;
    while(temp && i < index)
    {
        temp = temp->Next;
        i++;
    }
    return temp;
}

@zayats80888 · 23.02.2019, 12:52

ну тогда можно сначала слить(соединить), а потом отсортировать по принципу что я выше описал

@cherc · 23.02.2019, 16:55 **[ТС]**

как написать ф-ю нахождения середины списка. А то у меня не получается.

Добавлено через 57 минут
up!

@zayats80888 · 23.02.2019, 17:07

C++
1
GetBanner(GetSize()/2)

, хотя судя по методам класса достаточно GetSize()/2

@cherc · 23.02.2019, 17:10 **[ТС]**

zayats80888, это не подойдет. Нахождение середины списка

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@zayats80888 6352 / 3523 / 1428 Регистрация: 07.02.2019 Сообщений: 8,995
	23.02.2019, 12:52
	ну тогда можно сначала слить(соединить), а потом отсортировать по принципу что я выше описал 0

@cherc 13 / 18 / 6 Регистрация: 02.05.2018 Сообщений: 545
	23.02.2019, 16:55 [ТС]
	как написать ф-ю нахождения середины списка. А то у меня не получается. Добавлено через 57 минут up! 0

@cherc 13 / 18 / 6 Регистрация: 02.05.2018 Сообщений: 545
	23.02.2019, 17:10 [ТС]
	zayats80888, это не подойдет. Нахождение середины списка 0

Переделать список

Решение