0 / 0 / 1
Регистрация: 24.10.2016
Сообщений: 43
1

Сортировку односвязного списка переделать для двусвязного

14.06.2017, 03:35. Показов 586. Ответов 1
Метки нет (Все метки)

Здравствуйте!
Есть проблема в реализации сортировки под двусвязный список.
Есть рабочая сортировка под односвязный. Как ее переделать в двусвязный?

Код прилагается
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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
#include <stdio.h>
#include <string.h>
#include <iostream> 
#include <locale.h> 
#include <ctime>
#include <conio.h> 
 
using namespace std;
 
typedef int new_type;
struct List//описание структуры
{
    new_type data;
    List *next; // указатель следующей записи
    List *pred;// указатель предыдущей записи 
} *start = NULL; // указатель на начало списка
 
 
 
void push(new_type val, int pos)//добавить узел в список в определённую позицию
{
    List *a = new List;
    a->data = val;
    if (start == NULL)//если это первый элемент в списке
    {
        a->next = a;
        a->pred = a;
        start = a;
    }
    else
    {
        List *t = start;
        for (int i = pos; i>1; i--, t = t->next);
        t->pred->next = a;
        a->pred = t->pred;
        a->next = t;//добавляем элемент перед t
        t->pred = a;
    }
}
 
new_type pop(int pos)//удалить узел по индексу из списка
{
    if (start == NULL)
        return (new_type)0;//список пуст
    new_type val;
    if (start == start->next)//если это последний элемент в списке
    {
        val = start->data;
        delete start;
        start = NULL;
    }
    else
    {
        List *t = start;
        for (int i = pos; i>1; i--, t = t->next);
        if (t == start)start = t->next;//если пытаемся удалить 1-ый элемент то голова указывает на 2-ой 
        t->pred->next = t->next;//удаляем t элемент
        t->next->pred = t->pred;
        val = t->data;
        delete t;
    }
 
    return val;
}
 
 
 
void view_pravo_levo()//просмотр элементов в списке c право на лево (н-1)
{
    if (start == NULL)return;
    List *a = start;
    int i = 0;
    do
    {
        a = a->next;
        cout << "Элемент #" << i + 1 << " : " << (int)a->data << endl;
        i++;
    } while (a != start);
 
}
 
void view_levo_pravo()//просмотр элементов в списке с лева на право  (1-н)
{
    if (start == NULL)return;
    List *a = start;
    int i = 0;
    do
    {
        cout << "Элемент #" << i + 1 << " : " << (int)a->data << endl;
        a = a->pred;
        i++;
    } while (a != start);
 
}
 
void bubble_sort_list(List * start) {  //сортировка по убыванию
    List * p = NULL;
 
    if (start != NULL) { 
        while (start->next != NULL) {
            p = start->next;
            start->pred;
            do {
                if (p->data > start->data) {    // переключатель
                    int tmp = p->data;
                    p->data = start->data;
                    start->data = tmp;
                    start->pred;
                }
 
                p = p->next;
            } while (p != NULL);
 
            start = start->next;
        }
    }
}
 
 
 
 
int main()
{
    setlocale(LC_ALL, "Russian");
 
 
    int znach;
    int n;// кол-во элементов
    cout << "Введите  кол-во элементов в списке: ";
    cin >> n;
 
    short a, b;
    cout << "Как заполнить список? " << endl;
    cout << "1) с клавиатуры " << endl;
    cout << "2) рандомно" << endl;
    cin >> a;
 
    switch (a)
    {
    case 1: {
        cout << "Заполните список числами с клавиатуры : " << endl;
        for (int i = 0; i < n; i++)
        {
            cout << "Введите  значение: ";
            cin >> znach;
 
            push(znach, i); //добавляем вторым
        }}break;
 
    case 2: {
        cout << "Список заполнится рандомно: " << endl;
        srand(time(NULL));
        for (int i = 0; i < n; i++)
        {
            znach = -100 + rand() % 200;
            push(znach, i);
        }
    }break;
    }
 
    while (1)
    {
 
        cout << "Что делаем?: " << endl;
 
        cout << "1)Просмотреть структуру " << endl;
        cout << "2)Вставить в любое место в списке " << endl;
        cout << "3)Удаляем любой элемент " << endl;
        cout << "4)Сортировать (sooon) " << endl;
        cout << "5)Выход" << endl;
 
        cin >> b;
 
        switch (b)
        {
        case 1: {
            short c;
            cout << "1)Вывести в прямом порядке- 1 до n " << endl;
            cout << "2)Вывести в обратном порядке- n до 1 " << endl;
            cin >> c;
            switch (c)
            {
            case 1: {view_levo_pravo(); } break;
            case 2: {view_pravo_levo(); } break;
            }
        }break;
        case 2: {
            int value, key;
            cout << "Введите значение: ";
            cin >> value;
            cout << "Введите место, в которое вставить: ";
            cin >> key;
            push(value, key);
        }break;
        case 3: {
            int key;
 
            cout << "Введите номер элемента, который удалить: ";
            cin >> key;
            pop(key);
        }break;
        case 4: {
            bubble_sort_list(start);
            cout << "Сортировка окончена. Просмотр найдите в меню ";
        }break;
        case 5: {
            exit(5); break;
        default: break;
        }
        }
    }
    _getch();
    return 0;
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.06.2017, 03:35
Ответы с готовыми решениями:

Написать сортировку односвязного списка
Здравствуйте. Написал программу для работы со списком. Программа работает, но не получается...

Переделать программу работы с базой заказчиков с помощью двусвязного списка
Задача сделана при помощи структур... Необходимо реализовать её при помощи Двусвязного списка на...

Переделать программу с использованием двусвязного списка (вместо односвязного)
Есть программа, которая содержит некоторые подпрограммы для работы с односвязным списком. Как...

Алгоритм нисходящей сортировки слиянием. Переделать для двусвязного списка (LinkedList)
Есть проблема с переписыванием алгоритма для двусвязного списка LinkedList, как это можно...

1
Форумчанин
Эксперт CЭксперт С++
8190 / 5040 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
14.06.2017, 12:09 2
tujh48, у вас код с двусвязным списком. У односвязного храниться только указатель на след. элемент, у вас же ещё и на предыдущий.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.06.2017, 12:09
Помогаю со студенческими работами здесь

Напишите для двусвязного списка процедуры вставки и удаления перед заданным элементом списка
Напишите для двусвязного списка процедуры вставки и удаления перед заданным элементом списка...

Cортировка вставкой для двусвязного списка
Добрый день, есть двусвязный рандомный список, никак не могу написать для него сортировку вставкой....

IComparable для сортировки двусвязного списка
Как отсортировать с помощью IComparable? using System; using System.Collections.Generic;...

Написать swap для двусвязного списка
Здраствуйте, имеються такие структуры: struct Node { uint count; string data; Node* next;...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru