Нахождение середины списка

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

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

не работает

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
     Node* GetMiddle(MyList c)
     {
         MyList a = c;
         MyList b = c;
         MyList Tail = NULL;
 
         while(b->Next != Tail && b->Next->Next != Tail)
         {
             a = a->Next;
             b = b->Next->Next;
         }
         return a;
     }

Весь код. Ф-я в самом конце

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

@cherc · 23.02.2019, 22:28 **[ТС]**

zayats80888, Сортировка слиянием: Исходный список разбивается на 2 (через GetMiddle находится середина, 1 список правая часть, 2 список левая часть), потом эти 2 списка опять разбиваются и т д пока не получится списки по 1 элементу. Потом эти списки поочередно сравниваются(Merge) и список начинает обратно собираться(слияние).

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

@zayats80888 · 24.02.2019, 03:52

Вот так вроде работает:

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
template <class T>
struct Node
{
public:
    Node(T d):data(d),Next(0),Prev(0){}
    T data;
    Node<T> *Next, *Prev;
};
 
template <class T>
 class MyList
{
public:
    Node<T> *Head;
    Node<T> *Tail;
    int size;
    MyList():Head(0),Tail(0), size(0){}
    MyList(MyList& list):Head(0),Tail(0), size(0){for (int i=0; i<list.size; ++i) Add(list.GetData(i));}
    MyList& operator=(const MyList& list){
        while (size) Remove(size-1);
        for (int i=0; i<list.size; ++i) Add(list.GetData(i));
        return *this;
    }
    ~MyList(){
        while (size) Remove(size-1);
    }    
    void Show()
    {
        Node<T> *temp = Head;
        if(temp == 0)
        {
            cout << "Список пуст!" << endl;
        }
        else
        {
            while(temp)
            {
                cout << temp->data<<' ';
                temp = temp->Next;
            }
        }
    }
    void Add(T data)
    {
        Node<T> *temp = new Node<T>(data);
        if (Tail)
        {
            temp->Prev = Tail;
            Tail->Next = temp;
            Tail = temp;
        }
        else
        {
            Head = Tail = temp;
        }
        size++;
    }
 
    int GetSize(){return i;}
 
    Node<T>* GetNode(int i) const{
        if (i<0 || i>size-1) return 0;
        Node<T>* temp=Head;
        for (int j=0; j<i; ++j) temp=temp->Next;
        return temp;
    }
 
    T GetData(int i) const{
        if (GetNode(i)) return GetNode(i)->data;
        else return T();
    }
    
    void Remove(int index){
        Node<T> *temp=GetNode(index);
        if (!temp) return;
        if (temp->Next) temp->Next->Prev=temp->Prev;
        else Tail=temp->Prev;
        if (temp->Prev) temp->Prev->Next=temp->Next;
        else Head=temp->Next;
        delete temp;
        --size;
    }
 
    void Insert(class x, int index){};
 
};
template <typename T> void DivList(MyList<T>& list, MyList<T>& left, MyList<T>& right){
    left=list;
    right=list;
    for (int i=0; i<list.size/2; ++i){
        right.Remove(0);
        left.Remove(left.size-1);
    }
    if (list.size%2) right.Remove(0);
}
 
template<typename T> void MergeSort(MyList<T>& list){
    if (list.size>1){
        MyList<T> left;
        MyList<T> right;
        DivList(list,left,right);
 
        MergeSort(left);
        MergeSort(right);
        MyList<T> temp;
        while (0<left.size || 0<right.size){
            if(left.GetData(0)<right.GetData(0)){
                temp.Add(left.GetData(0));
                left.Remove(0);
            }
            else{
                temp.Add(right.GetData(0));
                right.Remove(0);
            }
            if (left.size==0){
                while (right.size){
                    temp.Add(right.GetData(0));
                    right.Remove(0);
                }
                break;
            }
            if (right.size==0){
                while (left.size){
                    temp.Add(left.GetData(0));
                    left.Remove(0);
                }
                break;
            }
        }
        list=temp;
    }
}

@cherc · 24.02.2019, 08:43 **[ТС]**

zayats80888, все работает. Спасибо большое

Новые блоги и статьи Все статьи Все блоги /
ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Nekobox - outbounds[0].transport: unknown transport type: raw damix 01.10.2026 Фикс ошибки Правым кликом по серверу -> отладочная информация -> edit Заменить "net": "raw", на "net": "tcp", Нажать кнопку reload.	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .

@cherc 13 / 18 / 6 Регистрация: 02.05.2018 Сообщений: 545
	23.02.2019, 22:28 [ТС]
	zayats80888, Сортировка слиянием: Исходный список разбивается на 2 (через GetMiddle находится середина, 1 список правая часть, 2 список левая часть), потом эти 2 списка опять разбиваются и т д пока не получится списки по 1 элементу. Потом эти списки поочередно сравниваются(Merge) и список начинает обратно собираться(слияние). Добавлено через 1 час 38 минут up! 0

@cherc 13 / 18 / 6 Регистрация: 02.05.2018 Сообщений: 545
	24.02.2019, 08:43 [ТС]
	zayats80888, все работает. Спасибо большое 0

Опции темы

Нахождение середины списка

Решение