Сортировка односвязного списка
От: ivanzh  
Дата: 05.04.07 08:24
Оценка:
Написал функцию сортировки списка, а BDS 2006 выдаёт ощибку, помогите, пожалуйста, найти:

void __fastcall TForm1::Button3Click(TObject *Sender)
{
    int temp;
    if (first == NULL)
            Memo1->Lines->Add("Ochered pusta");
    else    //sortirovka
            while (first!= NULL)
                {
                        if(first->a>first->next->a)
                        {
                            temp=first->a;
                            first->a=first->next->a;
                            first->next->a=temp;
                        }
                        first =first->next;
                }  //vivod
    while (first!= NULL)
                {
                        Memo1->Lines->Add(IntToStr(first->a)+' '+(first->ch));
                        first =first->next;
                }
}
Re: Сортировка односвязного списка
От: Alex Dav Россия  
Дата: 05.04.07 08:31
Оценка:
а какая ошибка?
Re[2]: Сортировка односвязного списка
От: vasmann  
Дата: 05.04.07 08:38
Оценка: +1
Здравствуйте, Alex Dav, Вы писали:

AD>а какая ошибка?

Не уверен что знаю о ошибке, но скорее всего что next == 0 а следовательно плохи дела
Re[2]: Сортировка односвязного списка
От: ivanzh  
Дата: 05.04.07 08:46
Оценка:
Здравствуйте, Alex Dav, Вы писали:

AD>а какая ошибка?


Я думаю, что ошибка в адресации
Re[3]: Сортировка односвязного списка
От: Alex Dav Россия  
Дата: 05.04.07 08:49
Оценка:
Здравствуйте, ivanzh, Вы писали:

I>Здравствуйте, Alex Dav, Вы писали:


AD>>а какая ошибка?


I>Я думаю, что ошибка в адресации


А где тут используется адресация?!
Re: Сортировка односвязного списка
От: e-garin Россия  
Дата: 05.04.07 08:51
Оценка:
Здравствуйте, ivanzh, Вы писали:

I>Написал функцию сортировки списка, а BDS 2006 выдаёт ощибку, помогите, пожалуйста, найти:


Согласен с vasmann, вот этот код упадёт на последнем элементе списка:
I>
I>    while (first!= NULL) //цикл до последнего элемента списка
I>    {
I>        if(first->a>first->next->a)//но у последнего элемента next==0 !
I>        { //...
I>
А мне нравится жить :).
Re[3]: Сортировка односвязного списка
От: Chorkov Россия  
Дата: 05.04.07 08:53
Оценка:
Здравствуйте, ivanzh, Вы писали:

I>Здравствуйте, Alex Dav, Вы писали:


AD>>а какая ошибка?


I>Я думаю, что ошибка в адресации


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


Возможно ошибка к том, что в циклах перебора элементов, в качестве итератора используется внешняя переменная.
Поэтому:
    while (first!= NULL) // на входев этот цикл  first всегда будет равен NULL
                {
                        Memo1->Lines->Add(IntToStr(first->a)+' '+(first->ch));
                        first =first->next;
                }
Re[2]: Сортировка односвязного списка
От: ivanzh  
Дата: 05.04.07 08:55
Оценка:
Здравствуйте, e-garin, Вы писали:

EG>Здравствуйте, ivanzh, Вы писали:


I>>Написал функцию сортировки списка, а BDS 2006 выдаёт ощибку, помогите, пожалуйста, найти:


EG>Согласен с vasmann, вот этот код упадёт на последнем элементе списка:


А как же это исправить?
Re[4]: Сортировка односвязного списка
От: ivanzh  
Дата: 05.04.07 09:00
Оценка:
Здравствуйте, Chorkov, Вы писали:


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


Когда нажимаю на кнопку Button3, выдаётся сообщение о ошибке в адресах

C>Возможно ошибка к том, что в циклах перебора элементов, в качестве итератора используется внешняя переменная.

C>Поэтому:
C>
C>    while (first!= NULL) // на входев этот цикл  first всегда будет равен NULL
C>                {
C>                        Memo1->Lines->Add(IntToStr(first->a)+' '+(first->ch));
C>                        first =first->next;
C>                }
C>


А как же иначе провести вывод очереди?
Re[3]: Сортировка односвязного списка
От: e-garin Россия  
Дата: 05.04.07 09:01
Оценка:
Здравствуйте, ivanzh, Вы писали:

I>Здравствуйте, e-garin, Вы писали:


EG>>Здравствуйте, ivanzh, Вы писали:


I>>>Написал функцию сортировки списка, а BDS 2006 выдаёт ощибку, помогите, пожалуйста, найти:


EG>>Согласен с vasmann, вот этот код упадёт на последнем элементе списка:


I>А как же это исправить?

например, так:

while ( first && first->next )
{
//...


(в логику самого алгоритма сортировки я не вникал, не могу сказать правильный он или нет)
А мне нравится жить :).
Re: Сортировка односвязного списка
От: e-garin Россия  
Дата: 05.04.07 09:14
Оценка: +1
Здравствуйте, ivanzh, Вы писали:

I>Написал функцию сортировки списка, а BDS 2006 выдаёт ощибку, помогите, пожалуйста, найти:


I>
I>void __fastcall TForm1::Button3Click(TObject *Sender)
I>{
I>    int temp;
I>    if (first == NULL)
I>            Memo1->Lines->Add("Ochered pusta");
I>    else    //sortirovka
I>            while (first!= NULL) //(1)
I>                {
I>                        if(first->a>first->next->a)//(*)
I>                        {
I>                            temp=first->a;
I>                            first->a=first->next->a;
I>                            first->next->a=temp;
I>                        }
I>                        first =first->next;
I>                }  //vivod //(2)
I>    while (first!= NULL)//(3)
I>                {
I>                        Memo1->Lines->Add(IntToStr(first->a)+' '+(first->ch));
I>                        first =first->next;
I>                }
I>}
I>

Подытоживая, здесь три проблемы:
1. Код между (1) и (2) не есть алгоритм сортировки (больше похоже на один проход сортировки пузырьком, но тогда надо бы до предпоследнего элемента).
Попробуйте проверить его руками на массиве из 4 элементов, например: [4, 1, 3, 2]
2. В (1) надо проверять first->next (тогда не будет падать в (*)).
3. В цикл (3) не попадём, поскольку first равен NULL после завершения цикла (2).

P.S. На самом деле ещё проблема в том, что внешняя переменная (скорее всего это член класса TForm1) после выполнения данного метода бесполезна, поскольку по-любому равна 0.
Подумайте ещё раз над тем, что Вы хотели написать.
А мне нравится жить :).
Re[5]: Сортировка односвязного списка
От: Chorkov Россия  
Дата: 05.04.07 09:15
Оценка:
Здравствуйте, ivanzh, Вы писали:


I>А как же иначе провести вывод очереди?


void __fastcall TForm1::Button3Click(TObject *Sender)
{
    int temp;
    if (first == NULL)
            Memo1->Lines->Add("Ochered pusta");
    else    //sortirovka
            //while (first!= NULL)
            for(T* i=first; i!=NULL && i->next!=NULL; i=i->next) // создаем временную переменную
                {
                        if(first->a>first->next->a)
                        {
                            temp=first->a;
                            first->a=first->next->a;
                            first->next->a=temp;
                        }
                        //first =first->next; переход на следующий элемент перенесен в for.
                }  //vivod
    for(T* i=first; i!=NULL && i->next!=NULL; i=i->next)
                {
                        Memo1->Lines->Add(IntToStr(first->a)+' '+(first->ch));
                        //first =first->next;
                }
}


P.S. не знаю какого типа переменная first. поэтому использовал T*
Re[6]: Сортировка односвязного списка
От: Chorkov Россия  
Дата: 05.04.07 09:19
Оценка:
Здравствуйте, Chorkov, Вы писали:

C>Здравствуйте, ivanzh, Вы писали:



I>>А как же иначе провести вывод очереди?


C>
C>void __fastcall TForm1::Button3Click(TObject *Sender)
C>{
C>    int temp;
C>    if (first == NULL)
C>            Memo1->Lines->Add("Ochered pusta");
C>    else    //sortirovka
C>            //while (first!= NULL)
C>            for(T* i=first; i!=NULL && i->next!=NULL; i=i->next) // создаем временную переменную
C>                {
C>                        if(first->a>first->next->a)
C>                        {
C>                            temp=first->a;
C>                            first->a=first->next->a;
C>                            first->next->a=temp;
C>                        }
C>                        //first =first->next; переход на следующий элемент перенесен в for.
C>                }  //vivod
C>    for(T* i=first; i!=NULL && i->next!=NULL; i=i->next)
C>                {
C>                        Memo1->Lines->Add(IntToStr(first->a)+' '+(first->ch));
C>                        //first =first->next;
C>                }
C>}
C>


C>P.S. не знаю какого типа переменная first. поэтому использовал T*



Внутри цикла нужно былдо также заменить first на i



void __fastcall TForm1::Button3Click(TObject *Sender)
{
    int temp;
    if (first == NULL)
            Memo1->Lines->Add("Ochered pusta");
    else    //sortirovka
            //while (first!= NULL)
            for(T* i=first; i!=NULL && i->next!=NULL; i=i->next) // создаем временную переменную
                {
                        if(i->a>i->next->a)
                        {
                            temp=i->a;
                            i->a=i->next->a;
                            i->next->a=temp;
                        }
                        //first =first->next; переход на следующий элемент перенесен в for.
                }  //vivod
    for(T* i=first; i!=NULL && i->next!=NULL; i=i->next)
                {
                        Memo1->Lines->Add(IntToStr(i->a)+' '+(i->ch));
                        //first =first->next;
                }
}
Re[6]: Сортировка односвязного списка
От: e-garin Россия  
Дата: 05.04.07 09:20
Оценка:
Здравствуйте, Chorkov, Вы писали:

C>Здравствуйте, ivanzh, Вы писали:



I>>А как же иначе провести вывод очереди?


C>
C>void __fastcall TForm1::Button3Click(TObject *Sender)
C>{
C>    int temp;
C>    if (first == NULL)
C>            Memo1->Lines->Add("Ochered pusta");
C>    else    //sortirovka
C>            //while (first!= NULL)
C>            for(T* i=first; i!=NULL && i->next!=NULL; i=i->next) // создаем временную переменную
C>                {
C>                        if(first->a>first->next->a)
C>                        {
C>                            temp=first->a;
C>                            first->a=first->next->a;
C>                            first->next->a=temp;
C>                        }
C>                        //first =first->next; переход на следующий элемент перенесен в for.
C>                }  //vivod
C>    for(T* i=first; i!=NULL && /*i->next!=NULL*/; i=i->next) //(3)
C>                {
C>                        Memo1->Lines->Add(IntToStr(first->a)+' '+(first->ch));
C>                        //first =first->next;
C>                }
C>}
C>


C>P.S. не знаю какого типа переменная first. поэтому использовал T*


В (3) всё-таки проверку i->next!=NULL не надо делать, автор здесь добавляет все элементы списка в качестве строк в Memo1.
А мне нравится жить :).
Re: Сортировка односвязного списка
От: Кодт Россия  
Дата: 05.04.07 09:55
Оценка:
Здравствуйте, ivanzh, Вы писали:

I>Написал функцию сортировки списка, а BDS 2006 выдаёт ощибку, помогите, пожалуйста, найти:


Тут ещё и в алгоритме ошибка. Он выполняет пробулькивание одного пузырька.
Кстати, сам по себе выбор сортировки с обменами значений над списком неоправдан. Почему бы не переупорядочивать узлы, т.е. сделать сортировку слияниями?
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re: Сортировка односвязного списка
От: Programador  
Дата: 05.04.07 11:08
Оценка:
Здравствуйте, ivanzh, Вы писали:

I>Написал функцию сортировки списка, а BDS 2006 выдаёт ощибку, помогите, пожалуйста, найти:


И я напмсал, наверно это слияние. там масив списков у каждого длинна 2^i потом в 1 собираются Вроде порядок равных менять не должен, но не проверял
http://rsdn.ru/Forum/Message.aspx?mid=2434255&amp;only=1
Автор: Programador
Дата: 05.04.07
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.