It is necessary to form a queue containing integers and arrange them in ascending order. In the process of ordering, the elements of the queue do not have to be moved. Found the code that finds the maximum element of the queue and takes it to the beginning. But how can I not figure out what needs to be changed so that the whole queue is sorted. Here is the code:
#include"stdafx.h" #include <iostream> #include <stdlib.h> #include <conio.h> using namespace std; struct qitem { struct qitem *next, *prev; int data; }; struct queue { struct qitem *first, *last; }; struct qitem *add_head(struct queue *q, struct qitem *e) { if (e) { e->prev = 0; if (e->next = q->first) q->first->prev = e; else q->last = e; q->first = e; } return e; } struct qitem *add_tail(struct queue *q, struct qitem *e) { if (e) { e->next = 0; if (e->prev = q->last) q->last->next = e; else q->first = e; q->last = e; } return e; } struct qitem *remove(struct queue *q, struct qitem *e) { if (e) { if (e->next) e->next->prev = e->prev; else q->last = e->prev; if (e->prev) e->prev->next = e->next; else q->first = e->next; } return e; } struct qitem *find_max(struct queue *q) { struct qitem *cur = q->first, *pmax = cur; while (cur) { if (cur->data < pmax->data) pmax = cur; cout <<"re "<< cur; cur = cur->next; } return pmax; } struct qitem *make_item(int n) { struct qitem *p = new struct qitem; p->data = n; return p; } void print_list(struct queue *q) { cout << "queue " << q->first << " : " << q->last << '\n'; for (struct qitem *cur = q->first; cur; cur = cur->next) cout << cur->data << " [ " << cur << ": next " << cur->next << " prev " << cur->prev << "]\n"; } struct queue randlist(int n) { struct queue my_q = { 0, 0 }; for (int i = 0; i < n; i++) add_tail(&my_q, make_item((rand() % 100) + 1)); return my_q; } int main() { int N; cout << "Enter N: "; cin >> N; struct queue my_q = randlist(N); print_list(&my_q); cout << "---- find max and move it to head ----\n"; add_head(&my_q, remove(&my_q, find_max(&my_q))); print_list(&my_q); cout << "---- free memory (remove all queue items and delete them) ----\n"; struct qitem *p; int n = 0; while (p = remove(&my_q, my_q.first)) { delete p; n++; } cout << "remove " << n << " items\n"; print_list(&my_q); if (n == N) cout << "OK!\n"; else cout << "FAIL...\n"; _getch(); return N != n; } 