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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.82
Поночка
4 / 4 / 0
Регистрация: 04.10.2009
Сообщений: 22
#1

Быстрая сортировка связного списка - C++

18.10.2009, 15:00. Просмотров 2786. Ответов 3
Метки нет (Все метки)

Здравствуйте. не пойму как должна заканчиваться функция.что передавать в рекурсию и до каких пор.
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
Team *InsertBeforeHead(Team *&head, Team *n)//вставка n перед головой
{
    Team *k=head;
    Team *prevn=n->prev;
    Team *nextn=n->next;
    k->prev=n;
    n->next=k;
    n->prev=NULL;
    prevn->next=nextn;
    if(nextn)
        nextn->prev=prevn;
    head=n;
    return head;
}
 
bool InsertBehind( Team *n, Team *k)//вставляет n за k
{
if(k == NULL || n == NULL || k == n)
return false;
Team * nextk = k->next;
Team * prevn = n->prev;
Team * nextn = n->next;
k->next = n;
n->prev = k;
n->next = nextk;
if(nextk != NULL)
nextk->prev = n;
if(prevn != NULL)
prevn->next = nextn;
if(nextn != NULL)
nextn->prev = prevn;
return true;
}
 
Team *Quick (Team *&head,Team * s1,Team * p,Team * s2,Team * current)
{
    bool shift;
    Team *help;
    while(current)
    {
        if(p->Pay>current->Pay)
        {
            help=current->next;
            if(p==head) 
            {
                head=InsertBeforeHead(head, current);
            }
            else shift=InsertBehind(current, s1);
            s1=p->prev;
            current=help;
        }
        current=current->next;
    }
    ////////////////
 
}
p-элемент относительно которого сравнивают
s1-граница отсортированной части
s2-граница неотсортированной части
current-текущий элемент
 
int _tmain(int argc, _TCHAR* argv[])
{
Team *s1=head;
Team *p=head;
Team *s2=p->next;
    Team *current=p->next;
    Quick (head, s1, p, s2, current);
}
заранее спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.10.2009, 15:00     Быстрая сортировка связного списка
Посмотрите здесь:

Сортировка связного списка - C++
Привет всем! как правильно написать сортировку для связного циклического списка ? помогите пожалуйста... #include <iostream> using...

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

Сортировка пузырьком связного списка - C++
Доброго времени суток, надеюсь на вашу помощь в понимании проблемы при сортировке пузырьком связного списка (привожу только код сортировки,...

Создание и сортировка связного списка - C++
Задание: Написать программу, реализующую связный список с информацией о сотрудниках и отображающую список в порядке возрастания возраста...

Быстрая сортировка двусвязного списка - C++
что не так?? void newsort(Offender_Node*first,Offender_Node*last) { Offender_Node*cur=first,*Prev=cur; ...

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

Реализация связного списка - C++
Помогите решить задачу Нужно написать программу без использования библиотеки list я вот начал, только функция добавления не...

Конструктор-копирования связного списка - C++
Подскажите,как реализовать конструктор копирования для этого списка class part { public: ...

Возвращение элемента связного списка - C++
Здравствуйте. Есть связный список где в качестве элемента принимается структура DATA. Проблема возникает в методе get(int position),...

Обращение к члену связного списка - C++
Прошу помощи в решении Стоит задача обращения к члену связного списка(того списка что выводится на экран файлового менеджера),затем с...

Ошибка в реализации связного списка - C++
Здравствуйте. Делаю заголовочный файл связного списка. В результате компиляции выдает ошибку: "List is not a class template". Не понимаю в...

Вывод связного списка в файл - C++
Пишу программу для манипуляций со связным списком #include<iostream> #include<fstream> using namespace std; ...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nick Alte
Эксперт С++
1608 / 1000 / 118
Регистрация: 27.09.2009
Сообщений: 1,930
Завершенные тесты: 1
18.10.2009, 15:45     Быстрая сортировка связного списка #2
Смысл быстрой сортировки вкратце в следующем: необходимо разделить входной набор данных на две части, одна из которых меньше некоего произвольно выбранного элемента, а другая больше (ну и не забыть о равных). После чего надо применить операцию быстрой сортировки к каждой из частей, и результатом станет слияние данных двух частей.
В случае со списком операция достаточно проста. Ты получаешь некий список и выбираешь произвольный элемент p из списка(например, начальный или соседний с началом). Создаёшь два пустых списка - less и more. Проходишься по изначальным данным и элементы, меньшие p, заносишь в список less, а большие или равные - в список more. Из исходного массива ты эти элементы, естественно, просто убираешь (ну оно там само собой так и получается). Вызываешь ЭТУ ЖЕ САМУЮ функцию быстрой сортировки для списка less и для списка more (less = QuickSortList(less); more = QuickSortList(more); ). Объединяешь списки less и more так, чтобы next последнего элемента less указывал на первый элемент more и наоборот - prev первого элемента more указывал на последний элемент less. Затем остаётся возвратить из функции этот объединённый список (т.е., указатель на первый элемент less, т.е. сам less).
Поночка
4 / 4 / 0
Регистрация: 04.10.2009
Сообщений: 22
18.10.2009, 16:18  [ТС]     Быстрая сортировка связного списка #3
Ну вот я в Quick поделила первый раз список. Это я все понимаю. Но когда-то рекурсия должна кончиться.и я не понимаю как организовать цикл, который вызыват функцию для кусочков до тех пор, пока там не останется по 1 элементу, а потом соединяет их в один.ведь этих кусков будет становиться все больше и больше
Nick Alte
Эксперт С++
1608 / 1000 / 118
Регистрация: 27.09.2009
Сообщений: 1,930
Завершенные тесты: 1
18.10.2009, 17:15     Быстрая сортировка связного списка #4
Дело в том, что при каждом новом заходе в рекурсивную функцию для неё создаются новые копии её параметров и локальных переменных.
Пример:
C++
1
2
3
4
5
6
7
void PrintNum(int x) {
int y = x*x;
if(x<0)
    return;    // Прерывание рекурсии
printf("%d\n", x);
PrintNum(x-1);
}
Допустим, мы запустили PrintNum(3);. Стек вызова станет выглядеть так:
- PrintNum (x=3, y=9)
При вызове из самой PrintNum к нему добавится ещё один:
- PrintNum(x=3, y=9)
- PrintNum(x=2, y=4)
и так до упора, когда стек будет выглядеть так:
- PrintNum(x=3, y=9)
- PrintNum(x=2, y=4)
- PrintNum(x=1, y=1)
- PrintNum(x=0, y=0)
- PrintNum(x=-1, y=0) - здесь сработает проверка на прекращение рекурсии и дальнейшие PrintNum вызваны не будут.
После возврата из PrintNum(-1) её состояние будет убрано со стека:
- PrintNum(x=3, y=9)
- PrintNum(x=2, y=4)
- PrintNum(x=1, y=1)
- PrintNum(x=0, y=0)
затем будет возврат из (x=0) и так далее, в обратном порядке, с последовательным уничтожением отработавших состояний. Обрати внимание, что разные значения переменной y сосуществуют одновременно для разных вызовов функции.

При двукратном вызове QuickSort из неё самой размножение кусков будет происходить автоматически, так что беспокоиться тебе не о чем.
Yandex
Объявления
18.10.2009, 17:15     Быстрая сортировка связного списка
Ответ Создать тему
Опции темы

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