Invert unidirectional list to C ++

Question

There was a problem with the implementation of the algorithm, which inverts the elements of the list between the maximum and minimum numbers. Simply put, if there is a list (2 1 4 5 12 5), then eventually it should be converted to (2 12 5 4 1 5), since the maximum element = 12, and the minimum = 1. Creating, filling and searching the maximum and the minimum element I implemented, but how to invert what is between them ... this is a problem for me. I would be very grateful for the help. Here is my code:

#include "stdafx.h" #include "iostream" #include "conio.h" #include "math.h" using namespace std; typedef float Tdata; struct Tnode { Tdata info; Tnode *next; }; typedef Tnode* Tlist; Tlist L=0; void output(Tlist L); void create_L(Tlist &L, int n); Tlist min(Tlist L); Tlist max(Tlist L); void change(Tlist &L); // Функция изменения порядка элементов между max и min int main () { setlocale(0,"Rus"); int n; cout<<"Введите количество узлов "; cin>>n; create_L(L,n); cout<<"Введённые числа: "; output(L); //Tlist L_min=min(L); //cout<<"Минимальное значение: "<<L_min->info<<endl; //Tlist L_max=max(L); //cout<<"Максимальное значение: "<<L_max->info<<endl; change(L); cout<<"Числа после сортировки: "; output(L); _getch(); return 0; } void output(Tlist L) // Вывод списка { Tlist q=L; while (q) { cout<<(q->info)<<" "; q=q->next; } cout<<endl; } void create_L(Tlist &L, int n) // Заполнение списка { L=new Tnode; cout<<"Введите число "; cin>>(L->info); L->next=0; Tnode *q1, *q2; q1=L; for(int i=1; i<n; i++) { q2 = new Tnode; cout<<"Введите число "; cin>>(q2->info); q2->next=0; q1->next=q2; q1=q2; } } Tlist min(Tlist L) { Tlist q=L; Tlist q_min; q_min=q; q=q->next; while (q) { if ((q_min->info)>(q->info)) q_min=q; q=q->next; } return q_min; // Возвращает указатель на минимальный узел списка } Tlist max(Tlist L) { Tlist q=L; Tlist q_max; q_max=q; q=q->next; while (q) { if ((q_max->info)<(q->info)) q_max=q; q=q->next; } return q_max; // Возвращает указатель на минимальный узел списка } void change(Tlist &L) { Tlist q=L; float temp1; float L_min=min(L)->info; // Вызов функции определения минимального числа float L_max=max(L)->info; // Вызов функции определения максимального числа while (q) { if ((q->info)==(L_min)) q->info=L_max; else if ((q->info)==(L_max)) q->info=L_min; q=q->next; } }

avp avp 37.4k 3 35 90 · Accepted Answer · 2012-12-13T12:42:30

It would be easier with a doubly linked list, but you have a simply connected ...

The idea of the algorithm is to split the list into 3 parts, the first from the head to the min, the second min ... max (it must be inverted) and the third tail for max.

After inverting, glue them one after the other. (Again, it is more convenient when the list is not represented by one pointer to the head, but by two - the structure of the head, the tail).

By the way, it will work if min precedes max in the list. If not, then the min and max pointers must be exchanged.

It is easy to tear off the tail (of course, this is a sketch, checks are needed everywhere)

 Tlist emax = max(L); Tlist emin = min(L); Tlist tailist = emax->next; emax->next = 0;

With a little worse head

 for (Tlist p = L; p->next != emin; p = p->next); p->next = 0;

now we invert

 Tlist t = 0, inv = 0, lastinv = emin; while (emin) { t = emin; emin = emin->next; t->next = inv; inv = t; }

left to glue (after cutting head p points to its last element)

 p->next = inv; lastinv->next = tailist;

Now L points to the first item in the modified list.

Probably some variables can be reduced, and more closely, do not trust much, stuffed right here, did not check at all.

VladD VladD 183k sixteen 228 434 · Answer 2 · 2012-12-13T12:23:22

How does inverting a sublist differ from inverting an entire list? Almost nothing, right?

So do this:

Calculate pointers to the largest and smallest list items
Temporarily "tear off" the sublist from the main list.
Invert the torn sublist and finally
Glue it to where it came from.
As a bonus, think about what to do if there are many maximum elements? For example, all elements of the list are equal.

1. Well, for this purpose, it seems to me that the functions min and max are created 2. Could you explain how to “tear off” the sublist?
That is, if my minimum element in the list is earlier than the maximum (for example), then I take a pointer to the minimum element (min function) and work with it?
First, you need to take a smaller index of two, this will be the beginning.
now, the one that is before the beginning indicates the beginning - set temporarily to NULL.

Invert unidirectional list to C ++

2 answers 2

More articles: