Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
HelloWrld
0 / 0 / 0
Регистрация: 22.04.2012
Сообщений: 16
22.04.2012, 12:19     Сортировка списка #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
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();
};
Может кто на русском объяснить что дальше мне делать? Каким образом сортировать список?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.04.2012, 12:19     Сортировка списка
Посмотрите здесь:

Сортировка списка C++
C++ Сортировка списка
Сортировка списка C++
C++ Сортировка списка
C++ Сортировка списка
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
IFree Host
Заблокирован
22.04.2012, 12:34     Сортировка списка #2
Дальше нужно написать наиболее оптимальный сортировочный алгоритм, и пропустить список через него.
Если с сортировочными алгоритмами еще не знаком, можешь позаимствовать здесь:
http://rosettacode.org/wiki/Sorting_algorithms
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 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;//и текущим элементом в отсортированной части
}
 
}
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;
}
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;
    }   
}
Я походу в чем-то очень сильно ошибаюсь
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 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 - бывший третий элемент
/////////////////////////разрываем его связь с четвёртым
/////////////////////////и связываем со вторым
HelloWrld
0 / 0 / 0
Регистрация: 22.04.2012
Сообщений: 16
22.04.2012, 16:16  [ТС]     Сортировка списка #7
Kuzia domovenok, не это не сортировка само собой Это я просто хочу поменять местами два элемента )

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

Всёёё, понял, спасибо) Дополнение твое помогло)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.04.2012, 16:32     Сортировка списка
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 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
что-то не удалась псевдографика, ладно, думаю и без неё понятно
Yandex
Объявления
22.04.2012, 16:32     Сортировка списка
Ответ Создать тему
Опции темы

Текущее время: 02:41. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru