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

Сортировка вставками двухсвязного списка

27.04.2013, 17:49. Просмотров 514. Ответов 0
Метки нет (Все метки)

По заданию требуется отсортировать список по возрастанию. Организовал структуру списка,функцию по добавлению и удалению элементов, но застрял на сортировке,пытался сделать по соответствующему алгоритму для массивов,вот что получилось:
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
struct List_t
{
    int mInfo; // значение,хранящееся в данном узле
 
    List_t* mpNext; //указатель на следующий узел списка
    List_t* mpPrev; //указатель на предыдущий узел списка
};
 
//...
 
//функция добавления нового элемента
void Insert(List_t* &n1,List_t* &n2,int value)
{
    if(!n1 || !n2)
        return;
 
    List_t* pNew = new List_t; //выделяем память
    pNew->mInfo = value;
 
    n1->mpNext = pNew;
    n2->mpPrev = pNew;
 
    pNew->mpNext = n2; //устанавливаем соседей нового узла 
    pNew->mpPrev = n1; 
}
 
//функция удаления узла списка
 
void Delete(List_t* &n)
{
    if(!n)
        return;
 
    n->mpPrev->mpNext = n->mpNext;
    n->mpNext->mpPrev = n->mpPrev;
 
    delete n;
}
 
//функция сортировки
 
void SortList(List_t* &head,List_t* &tail)
{
    //проверяем указатели
    if(!head || !tail)
    {
        return;
    }
 
    List_t* pCurr = head->mpNext->mpNext,*pTemp; 
    List_t* pPrev = pCurr->mpPrev,*pLast;
 
    while(pCurr != tail)
    {
        pTemp = pCurr->mpPrev;
 
        while((pCurr->mInfo > pTemp->mInfo) && (pTemp->mpPrev != head))
            pTemp = pTemp->mpPrev;
 
        pPrev = pTemp->mpPrev;
 
        if((pCurr->mInfo < pTemp->mInfo))
        {
            Insert(pPrev,pTemp,pCurr->mInfo); // вставляем перемещаемый узел в новое место
 
            pLast = pCurr->mpNext;
 
            Delete(pCurr); 
 
            pCurr = pLast;
        }
        else
            pCurr = pCurr->mpNext;
    }
}
Как правильно реализовать алгоритм данной сортировки,кто-нибудь опишите,пожалуйста.

Добавлено через 1 час 16 минут
Вроде разобрался,переписал код,может кому пригодится.
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
void SortList(List_t* &head,List_t* &tail)
{
    //проверяем указатели
    if(!head || !tail)
    {
        return;
    }
    
    List_t* pCurr = head->mpNext->mpNext; 
    List_t* pTemp = pCurr,*pLast;
 
    while(pCurr != tail)
    {
        pTemp = pCurr;
 
        while((pCurr->mInfo < pTemp->mpPrev->mInfo) && (pTemp->mpPrev != head))
            pTemp = pTemp->mpPrev;
 
        if(pCurr->mInfo <= pTemp->mInfo)
        {
            pLast = pTemp->mpPrev;
            Insert(pLast,pTemp,pCurr->mInfo);
 
            pLast = pCurr->mpNext;
            Delete(pCurr);
            
            pCurr = pLast;
        }
        else
            pCurr = pCurr->mpNext;
    }
}
Добавлено через 23 секунды
Тему можно закрывать
1
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
27.04.2013, 17:49
Ответы с готовыми решениями:

Сортировка списка бинарными вставками
Добрый день. Скажите в чем проблема. Вроде все правильно написано. код пересматривал несколько раз...

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

Сортировка списка прямыми включениями (вставками)
Ребята кто может помогите с курсовой. Пытаюсь написать класс двунаправленного списка. Проблема...

Создание двухсвязного списка
Есть задание: Реализовать двухсвязный список. Каждый элемент списка может содержать один объект....

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.04.2013, 17:49

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

Формирование символьного двухсвязного списка
нужна функция формирования символьного 2вусвязного списка!!! Хэлп!!!

Переписать с С# в С++. Реализация двухсвязного списка
Здраствуйте, помогите пожалуйста переписать код на С++ Вот сам код: using System; using...

Не работает метод удаления элементов двухсвязного списка
задание удалить все чётные эл двухсвязного списка. не работает функция удаления chek. помогите...

Добавление элементов в любое место двухсвязного списка
Есть двухсвязный список, В КОТОРОМ ЕЛЕМЕНТЫ ДОБАВЛЯЮТСЯ В КОНЕЦ. Как сделать что б можно было...


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

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

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