Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
XChr
0 / 0 / 1
Регистрация: 13.11.2013
Сообщений: 84
Завершенные тесты: 1
1

Изменить последовательность указателей так, чтобы отрицательные числа находились в начале списка

24.04.2016, 17:58. Просмотров 360. Ответов 2
Метки нет (Все метки)

Проблема в методе Sort и Show.
Первый неверно сортирует, а второй зацикливается во время выполнения.
Скорее всего, причиной второй проблемы является первая проблема.
Помогите, пожалуйста, реализовать алгоритм сортировки указателей.

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
#include "stdafx.h"
#include <iostream>
 
using namespace std;
 
struct Node       //Структура являющаяся звеном списка
{
    int x;     //Значение x будет передаваться в список
    Node *Next, *Prev; //Указатели на адреса следующего и предыдущего элементов списка
};
 
class List   //Создаем тип данных Список
{
    Node *Head, *Tail; //Указатели на адреса начала списка и его конца
 
public:
    List() :Head(nullptr), Tail(nullptr) {}; //Инициализируем адреса как пустые
    ~List(); //Деструктор
    void Show(); //Функция отображения списка на экране
    void Add(int x); //Функция добавления элементов в список
    void Sort();
};
 
List::~List() //Деструктор
{
    while (Head) //Пока по адресу на начало списка что-то есть
    {
        Tail = Head->Next; //Резервная копия адреса следующего звена списка
        delete Head; //Очистка памяти от первого звена
        Head = Tail; //Смена адреса начала на адрес следующего элемента
    }
}
 
void List::Add(int x)
{
    Node *temp = new Node; //Выделение памяти под новый элемент структуры
    temp->Next = nullptr;  //Указываем, что изначально по следующему адресу пусто
    temp->x = x;//Записываем значение в структуру
 
    if (Head != nullptr) //Если список не пуст
    {
        temp->Prev = Tail; //Указываем адрес на предыдущий элемент в соотв. поле
        Tail->Next = temp; //Указываем адрес следующего за хвостом элемента
        Tail = temp; //Меняем адрес хвоста
    }
    else //Если список пустой
    {
        temp->Prev = nullptr; //Предыдущий элемент указывает в пустоту
        Head = Tail = temp; //Голова=Хвост=тот элемент, что сейчас добавили
    }
}
 
void List::Show()
{
    Node *temp=Head; //Временно указываем на адрес первого элемент
    while (temp!= nullptr) 
    {
    cout<<temp->x<<" ";
    temp=temp->Next; 
    }
    
    cout << "\n";
}
 
void List::Sort()
{
 
    struct Node *node, *lastnegative, *prev; 
 
    node = Head; 
    prev = nullptr; 
    lastnegative = nullptr;
 
    do
    {
        if (node->x<0)
        {           
            if (Head == node)
            
                             lastnegative = node;
            
            if (lastnegative == nullptr)
            {
                prev->Next = node->Next;
                node->Next = Head;
                Head = node;            
                lastnegative = node;
                lastnegative->Next = node;
                node = prev;
            }
            else
                if (lastnegative->Next == node)
                {
                    lastnegative = node;
                }
                else
                {
                    prev->Next = node->Next;
                    node->Next = lastnegative->Next;
                    lastnegative->Next = node;
                    lastnegative = node;
                    node = prev;
                }
        }
        else prev = node;
        node = node->Next;
    }
 
    while (node != nullptr);
}
 
int main()
{
    system("CLS");
    List lst; //Объявляем переменную, тип которой есть список
    lst.Add(1); //Добавляем в список элементы
    lst.Add(-2);
    lst.Add(3);
    lst.Add(4);
    lst.Add(5);
 
 
 
    lst.Show(); //Отображаем список на экране
    lst.Sort();
    lst.Show();
    cout << "\n";
 
    system("PAUSE");
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.04.2016, 17:58
Ответы с готовыми решениями:

Отсортировать массив, чтобы все положительные числа находились в начале, отрицательные - в конце
Помогите пожалуйста. Дан вещественный массив A( N ) . Отсортировать его таким образом , чтобы все...

Отсортировать массив из 0 и 1 так, чтобы все нули находились в начале, а все единицы - в конце массива
Тема: Функции 1. Дано одномерный массив, заполненный 0 и 1 в произвольном порядке. Отсортировать...

Быстрая сортировка, чтобы все отрицательные числа находились перед положительными
Отсортировать числа таким образом, чтобы все отрицательные числа находились перед положительными...

Переставить элементы массива так, чтобы отрицательные оказались в начале, положительные - в конце
дан массив целых чисел переставить его элементы так, чтобы отрицательные оказались в начале,...

Отсортировать массив таким образом, чтобы все нули находились в начале, а единицы — в конце массива
Здравствуйте, дано такое задание Элементами массива IM(N) являются числа 0 и 1. Отсортировать этот...

2
Геомеханик
798 / 602 / 939
Регистрация: 26.06.2015
Сообщений: 1,409
24.04.2016, 20:52 2
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
#include <iostream>
#include <cstdlib>
 
struct Node {
    int x;
    Node* Next, *Prev;
};
 
class List {
    Node* Head, *Tail;
public:
    List();
    ~List();
    void  Show(void);
    void  Add(int x);
    Node* Partition(bool (pcmp)(int));
    void  Clear(void);
    void  Swap(Node* p1, Node* p2);
};
 
List::List(void):Head(nullptr), Tail(nullptr){}
List::~List(){
    this->Clear();
}
 
void List::Show(void){
    for(auto p = Head; p != nullptr; p = p->Next)
        std::cout << p->x << ' ';
    std::cout << std::endl;
}
 
void List::Add(int x){
    Node* p;
    try {
        p = new Node();
    } catch(...){
        return;
    }
    p->x    = x;
    p->Next = p->Prev = nullptr;
 
    if(Head == nullptr)
        Head = Tail = p;
    else {
        p->Prev = Tail;
        Tail    = Tail->Next = p;
    }
}
    
//перестановка
Node* List::Partition(bool (pcmp)(int)){
    Node* p = Head;
    while((p != nullptr) && pcmp(p->x))
        p = p->Next;
    
    for(Node* i = p; i != nullptr; i = i->Next){
        if(pcmp(i->x)){
            if(i != p){
                this->Swap(i, p);
                std::swap(i, p);
            }
            p = p->Next;
        }
    }
    return p;
}
 
// обмен узлов
void List::Swap(Node* p1, Node* p2) {
    if((p1 == nullptr) || (p2 == nullptr))
        return;
 
    Node* prev1 = p1->Prev;
    Node* prev2 = p2->Prev;
 
    if(prev1 != nullptr)
        prev1->Next = p2;
    p2->Prev = prev1;
 
    if(prev2 != nullptr)
        prev2->Next = p1;
    p1->Prev = prev2;
 
    Node* t1 = p1->Next;
    Node* t2 = p2->Next;
 
    p1->Next = p2->Next;
    if(t2 != nullptr)
        t2->Prev = p1;
 
    p2->Next = t1;
    if(t1 != nullptr)
        t1->Prev = p2;
 
    if(Head == p1)
        Head = p2;
    else if(Head == p2)
        Head = p1;
 
    if(Tail == p1)
        Tail = p2;
    else if(Tail == p2)
        Tail = p1;
}
 
//удаление всех
void List::Clear(void){
    Node* tmp;
    while(Head != nullptr){
        tmp  = Head;
        Head = Head->Next;
        delete tmp;
    }
    Tail = nullptr;
}
 
 
int main(void){
    List lst;
    lst.Add(100);
    for(int i = 0; i < 10; ++i)
        lst.Add(-9 + std::rand() % 19);
        
    lst.Add(-200);
    lst.Show();
    lst.Partition([] (int x) { return (x < 0); });
    lst.Show();
    return 0;
}
Пример работы кода
1
XChr
0 / 0 / 1
Регистрация: 13.11.2013
Сообщений: 84
Завершенные тесты: 1
25.04.2016, 07:34  [ТС] 3
Свою программу я уже исправил, но за помощь спасибо!
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.04.2016, 07:34

Дан массив а1+ a2+…+an Переставить его элементы так чтобы в начале массива расположились все его неотрицательные элементы, а в конце - отрицательные
Дан массив а1+ a2+…+an помогите переставить его элементы так чтобы в начале массива расположились...

Дан массив а1,а2,,…,аn. Переставить его элементы так, чтобы в начале массива расположились все его неотрицательные элементы, а в конце – отрицательные
Помогите плиз написать программу: Дан массив а1,а2,,…,аn. Переставить его элементы так, чтобы в...

Изменить последовательность указателей так, чтобы отрицательные числа находились в начале списка
Массив целых чисел представлен в виде динамического списка. Изменить последовательность указателей...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru