Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
HelloWrld
0 / 0 / 0
Регистрация: 22.04.2012
Сообщений: 16
#1

Сортировка списка - C++

22.04.2012, 12:19. Просмотров 1331. Ответов 7
Метки нет (Все метки)

Здравствуйте,
не совсем понимаю как должна быть реализована сортировка вставками в деке.
Что имеется на данный момент:
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
class List {
private:
    struct ListItem {
        int item;
        ListItem *next;
 
        ListItem (int i, ListItem *n = NULL){
            item = i;
            next = n;       
        }
    };
 
    int itemsCount;
    ListItem *first;
    ListItem *last;
 
public:
    List(){
        itemsCount = 0;
        first = last = NULL;
    }
 
    ~List();
        int Head() {
        return first->item;
    }
        int Tail() {
        return last->item;
    }
 
    void AddFirst (int item);
    void AddLast (int item);
    void DeleteFirst();
    void DeleteLast();
 
    void ShowList();
};
Может кто на русском объяснить что дальше мне делать? Каким образом сортировать список?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.04.2012, 12:19
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировка списка (C++):

"Сортировка двусвязного списка путем исключения элемента с минимальным значением и включения его в начало нового списка - C++
Здравствуйте! Возникла проблема с программой. Тема: "Сортировка двусвязного списка путем исключения элемента с минимальным значением и...

Сортировка списка - C++
Привет, всем.. Ребята помогите у подруги зачет по программированию ей надо решить задачку.. Информационное поле элемента...

Сортировка списка - C++
Народ нужна помощь :) Элементы списка представлены следующим образом: class Node { public: char *name; Node *next; ...

Сортировка списка - C++
Приветствую всех! Есть небольшая проблема: не могу понять, как создать сортировку в алфавитном порядке. Вот код: void SortList() { ...

Сортировка списка - C++
Помогите пожалуйста, нужна сортировка методом вставок односвязанного кольцевого списка, не пойму как делать. Со списками ток начал...

Сортировка списка - C++
Дан список сел и расстояния до них от города. Нужно вывести села в порядке удаленности от города. Городов до 10^8. Расстояния - целые...

7
IFree Host
Заблокирован
22.04.2012, 12:34 #2
Дальше нужно написать наиболее оптимальный сортировочный алгоритм, и пропустить список через него.
Если с сортировочными алгоритмами еще не знаком, можешь позаимствовать здесь:
http://rosettacode.org/wiki/Sorting_algorithms
0
Kuzia domovenok
1957 / 1810 / 142
Регистрация: 25.03.2012
Сообщений: 6,278
Записей в блоге: 1
22.04.2012, 14:48 #3
Цитата Сообщение от IFree Host Посмотреть сообщение
Если с сортировочными алгоритмами еще не знаком, можешь позаимствовать здесь:
он же решил уже сортировать вставками. для списков как раз подходящий вариант.

Добавлено через 14 минут
как-то так. Писал в блокноте, могут быть ошибки.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void List::sort(){
Listitem* unsortedlist=first->next;
ListItem* ins_item, counter, pre;
first->next=NULL;//начинаем создавать новый список, перемещая в него элементы из несортированной части по очереди
while(unsortedlist){
  ins_item=unsortedlist;//элемент для вставки - первый в неотсортированной части
  unsortedlist=unsortedlist->next;// удаляем его из неё
  counter=first; //counter \указатель на место, куда вставить в отсортированную часть
  pre=NULL;
  while(counter){//ищем это место пока отсорт. часть не закончится...
   if (ins_item->item>counter->item){
     pre=counter;                             //при этом перемещаем указатель по отсортированной части
     counter=counter->next;              // запоминая, текущее и предыдущее место
     }
     else{
      break;//...или не найдём место, куда вставить элемент.
     }
  }
  if(pre) pre->next=ins_item;// вставляем элемент между предыдущим
  ins_item->next=counter;//и текущим элементом в отсортированной части
}
 
}
1
IFree Host
Заблокирован
22.04.2012, 15:11 #4
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
он же решил уже сортировать вставками. для списков как раз подходящий вариант.
Извеняюсь, что невнимательно прочел. Могу тогда до кучи еще кинуть пример на С

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stddef.h>
 
static void insertion_sort(int *a, const size_t n) {
    size_t i, j;
    int value;
    for (i = 1; i < n; i++) {
        value = a[i];
        for (j = i; j > 0 && value < a[j - 1]; j--) {
            a[j] = a[j - 1];
        }
        a[j] = value;
    }
}
 
int main(void) {
    int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1};
    insertion_sort(a, sizeof a / sizeof a[0]);
    return 0;
}
1
HelloWrld
0 / 0 / 0
Регистрация: 22.04.2012
Сообщений: 16
22.04.2012, 15:43  [ТС] #5
IFree Host, массивы я понимаю как сортировать, видимо у меня проблемы с пониманием списка...
Kuzia domovenok, так я вроде с этим разобрался, пробую сейчас пузырек сделать
Для начала я просто решил попробовать как вообще происходит процесс обмена местами элементов. Т.к. у нас запись состоит из двух полей: само значение и указатель на след элемент, то значит если мы указатели поменяем местами, то и элементы получается тоже меняются.
Вот я написал обмен адресов, но после этого у меня программа не хочет выводить список (точнее бесконечно выводит). Не пойму в чем ошибка
C++
1
2
3
4
5
6
7
8
9
10
11
12
void List::Sort()
{
    ListItem *current = first;
    ListItem *temp;
    current = current->next; //просто чтоб с головой не заморачиваться, сравниваю 2 и 3 эл-т
 
    if (current->item > current->next->item){
        temp = current->next;
        current->next = current;
        current = temp;
    }   
}
Я походу в чем-то очень сильно ошибаюсь
0
Kuzia domovenok
1957 / 1810 / 142
Регистрация: 25.03.2012
Сообщений: 6,278
Записей в блоге: 1
22.04.2012, 16:15 #6
Цитата Сообщение от HelloWrld Посмотреть сообщение
void List::Sort()
{
* * ListItem *current = first;
* * ListItem *temp;
* * current = current->next; //просто чтоб с головой не заморачиваться, сравниваю 2 и 3 эл-т
if (current->item > current->next->item){
* * * * temp = current->next;
* * * * current->next = current;
* * * * current = temp;
* * } *
}
ну, настоящую сортировку надо в цикле делать, ну ладно будем считать это наброском алгоритма,

во-вторых, у тебя тут не происходит ничего current->next = current;
эта операция превратит этот список
C++
1
2
current-----v       |--------v      |----
            |item|next|   |item|next|
в такой
C++
1
2
3
                                      тут связь потеряна
current-----v      |------|                 |----
           |item|next|<---|       |item|next|
Добавлено через 12 минут
перестановку делать надо так(меняем второй и третий местами)
C++
1
2
3
4
5
6
7
8
(pre-первый элемент, current второй, current->next третий, current->next->next четвёртый)
pre->next=current->next;//разрываем связь первого со вторым,
///////////////////////// связываем первый с третьим 
current->next=current->next->next;//разрываем связь 2го и 3го, 
////////////////////////////////////связываем второй с четвёртым
pre->next->next=current;//pre->next - бывший третий элемент
/////////////////////////разрываем его связь с четвёртым
/////////////////////////и связываем со вторым
1
HelloWrld
0 / 0 / 0
Регистрация: 22.04.2012
Сообщений: 16
22.04.2012, 16:16  [ТС] #7
Kuzia domovenok, не это не сортировка само собой Это я просто хочу поменять местами два элемента )

Эм.. почему ничего не происходит? Я думал раньше у меня у меня cerrent->next указывал, к примеру, на начало области памяти: 004C46A0. А теперь указывается на: 004C46E8, т.е. поэтому адресу у нас же другое значение хранится? Вот так я думал обмен осуществить..

Всёёё, понял, спасибо) Дополнение твое помогло)
0
Kuzia domovenok
1957 / 1810 / 142
Регистрация: 25.03.2012
Сообщений: 6,278
Записей в блоге: 1
22.04.2012, 16:32 #8
pre->next=current->next;
current->next=current->next->next;
pre->next->next=current;


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
...............pre......................current......
.................|.......................|
.................v......|----------v.....v.....|----v......|-------v......
.............|item1|next|....|item2|next|....|item3|next|....|item4|next|
 
pre->next=current->next;
...............pre.............current......
.................|...................|
.................v...................v........|-------v........|-------v......
.............|item1|next|....|item2|next|....|item3|next|....|item4|next|
..........................|----------------------^
 
current->next=current->next->next;
 
...............pre.............current......
.................|...................|.........----------------------------|
.................v...................v.......|......................|-------v.....v...
.............|item1|next|....|item2|next|....|item3|next|....|item4|next|
.........................|----------------------^
 
pre->next->next=current;
 
...............pre.............current......
.................|...................|........-------------------------|
.................v...................v......|.............................v...
............|item1|next|....|item2|next|....|item3|next|....|item4|next|
.......................|-------------------------^...|
.....................................^------------------|
 
и того 
item1->next=item3
item3->next=item2
item2->next=item4
что-то не удалась псевдографика, ладно, думаю и без неё понятно
1
22.04.2012, 16:32
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.04.2012, 16:32
Привет! Вот еще темы с ответами:

Сортировка списка - C++
Всем привет задание такое Разработать программу работы со связным списком сеансов в кинотеатре. Для каждого сеанса должна храниться...

Сортировка списка - C++
Здравствуйте!!! Прошу помочь мне написать алгоритм сортировки односвязного списка. Задание такое: необходимо из элементов трёх списков...

Сортировка списка - C++
Люди помогите плиз я уже не могу!! надо сортировать список!!! Останьные недоработки тоже можете указать. Вот код Жду ответов) ...

Сортировка списка - C++
Всем привет) Нужно реализовать сортировку списка, линейного однонаправленного. Написал, но что-то как-то не правильно... void...


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

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

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