VPF::Сорт списк - Форум программистов

apook

Дата 2.7.2007, 04:51 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 794
Регистрация: 12.7.2006

Репутация: 9
Всего: 23

Не могу догнать устройство сортировки списка
Если с массивом все ясно

Код


char *tmp;
    ...
    tmp=array[ i ];
    array[ i ]=array[ i+1 ];
    array[ i+1 ]=tmp;

а со списком какая-то муть, если делать

Код


List *tmp;
    ...
    tmp=List[ i ]; //допустим квадратные скобки перегружены
    List[ i ]=List[ i+1 ];
    List[ i+1 ]=tmp;

нифига неправильно, там вроде какая то путанница с List[ i ]->next;
Даже если этот код проходит то ничего не меняет?
уже бошка заклинила...

--------------------

Мои руки из дуба, голова из свинца ну и пусть ...

zkv

Дата 2.7.2007, 05:33 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Участник Клуба
Сообщений: 2133
Регистрация: 23.7.2006
Где: Санкт-Петербург

Репутация: 26
Всего: 92

Цитата(apook @ 2.7.2007, 04:51

)

нифига неправильно, там вроде какая то путанница с List[ i ]->next;

технически все правильно будет (если перегруженный оператор [] дает ссылку на данные, а для типа данных перегружен оператор =).

Но когда речь идет о списке обычно перемещение осуществляется перенацеливанием указателей.
Хотя обмен данными может работать быстрее в некоторых случаях.
Несомненное преимущество в быстродействии перед контейнерами в которых данные идут "сплошняком" список имеет при частых вставках(удалениях) данных в(из) середину(ы).
В случае сортировки, список должен давать преимущество, если размер данных достаточно велик, и дешевле перекинуть указатели, чем обменивать данные (но это мои догадки).

Что я подразумевал под перенацеливанием указателей:

Код


NODE
{
  char data[1000];
  NODE *next;
  NODE *prev;
};
//...
Swap( NODE *node1, NODE *node2 )//не рассмотрены крайние варианты (начало, конец списка)
{
  NODE *tmp;
  tmp->next = node1->next;
  tmp->prev = node1->prev;

  node1->next = node2->next;
  node1->prev = node2->prev;
  node1->prev->next = node1;
  node1->next->prev = node1;

  node2->next = tmp->next;
  node2->prev = tmp->prev;
  node2->prev->next = node2;
  node2->next->prev = node2;
}

apook

Дата 2.7.2007, 06:17 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 794
Регистрация: 12.7.2006

Репутация: 9
Всего: 23

У меня структура такая

Код


NODE
{
  char data[1000];
  NODE *next;
};

указатели на начало и конец отдельно

Код


NODE *start;
NODE *end;
NODE *current;

допустим вот даже поменять местами start и end? У меня даже не получается даные поменять
прога доходит до этого меса и ошибка.
Я сравниваю:

Код


if( start->data[ 0 ]>end->data[ 0 ] )
{
    //????
    //первое что приходит в голову
    tmp=end;
    start=end;
    end=tmp
    }

ну а что же с указателем внутри структуры допустим end->next теперь указывает на второй
элемент списка , пробовал их там тоже менять но запутался че-то

--------------------

Мои руки из дуба, голова из свинца ну и пусть ...

Sartorius

Дата 2.7.2007, 07:06 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

Репутация: 8
Всего: 37

Цитата

У меня даже не получается даные поменять
прога доходит до этого меса и ошибка.

Код


NODE *start;
NODE *end;

Код


    tmp=end; // меняешь местами указатели. а не данные (*tmp = * end;)
    start=end;

ЗЫ что за ошибка?

PPS списки сортируют слиянием(по Нейману)

Это сообщение отредактировал(а) Sartorius - 2.7.2007, 07:07

apook

Дата 2.7.2007, 07:38 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 794
Регистрация: 12.7.2006

Репутация: 9
Всего: 23

Ну что нетак?

Код


void Swap( List *node1, List *node2 )
{
List *next_1, *next_2, *tmp;

next_1=node1->next;
next_2=node2->next;

tmp = node1;
node1 = node2;
node2 = tmp;

node1->next=next_1;
node2->next=next_2;
}

Туплю конкретно

--------------------

Мои руки из дуба, голова из свинца ну и пусть ...

zkv

Дата 2.7.2007, 08:19 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Участник Клуба
Сообщений: 2133
Регистрация: 23.7.2006
Где: Санкт-Петербург

Репутация: 26
Всего: 92

на компиляторе не проверял, вроде должно работать, если в конце ничего не затупил (что возможно)

Код


NODE
{
  char data[1000];
  NODE *next;
};
/*Проверяет, принадлежат ли элементы node1, node2 списку с началом root, если нет возвращает false, если да, то меняет их местами и возвращает true*/
bool Swap( NODE *root, NODE *node1, NODE *node2 )
{
  if( root == 0 || node1 == 0 || node2 == 0 )
    return false; //тут понятно

  NODE *prNode1 = NULL;
  if( root != node1 )
  {
    for( prNode1 = root; prNode1->next != node1 || prNode1 != 0; prNode1 = prNode1->next )
      ; 
    if( prNode1 == 0 )
      return false;//node1 не в списке
  }

  NODE *prNode2 = NULL;
  if( root != node2 )
  {
    for( prNode2 = root; prNode2->next != node2 || prNode2 != 0; prNode2 = prNode2->next )
      ; 
    if( prNode2 == 0 )
      return false;//node2 не в списке
  }
  
  if( node1 == node2 )
    return true; //показывают на один и тот же элемент в списке

  NODE *tmp;
  tmp = node1->next;

  if( prNode1 )
    prNode1->next = node2;
  if( prNode2 )
    prNode2->next = node1;
  node1->next = node2->next;
  node2->next = tmp;

  return true; //все Ок
}

apook

Дата 2.7.2007, 09:14 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 794
Регистрация: 12.7.2006

Репутация: 9
Всего: 23

zkv сейчас проверю твой код но я выяснил что в теле функции меняет
а на самом деле все остается на своих местах

--------------------

Мои руки из дуба, голова из свинца ну и пусть ...

zkv

Дата 2.7.2007, 09:26 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Участник Клуба
Сообщений: 2133
Регистрация: 23.7.2006
Где: Санкт-Петербург

Репутация: 26
Всего: 92

Цитата(apook @ 2.7.2007, 09:14

)

zkv сейчас проверю твой код но я выяснил что в теле функции меняет
а на самом деле все остается на своих местах

фишка списка в том, что данные всегда остаются на местах, только указатели перекидываются. Ты это имел ввиду? Или у меня не правильно работает код?

apook

Дата 2.7.2007, 09:43 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 794
Регистрация: 12.7.2006

Репутация: 9
Всего: 23

2zkv твоя функция приводит к точно такому же исключению что и моя
Вот весь листинг тестирующий список набросал, все хорошл если бы не сорт

Код


#include<iostream.h>
#include<fstream.h>
#include<stdlib.h>


#include<conio.h>



struct List
    {
        char value;
        List *next;
        };

int size=0;

List *start=NULL, *end=NULL, *current=NULL;



List *index( int index )
{
int i;
List *tmp=NULL;

tmp=start;
for( i=0; tmp; i++ )
{
    if( i==index )
        break;
    tmp=tmp->next;
    }
return tmp;
}



void add( char sub_value )
{
current=new List;

current->value=sub_value;

if( start==NULL && end==NULL )
    start=current;
else
    end->next=current;

    end=current;
    end->next=NULL;
++size;
return;
}



void Swap( List *node1, List *node2 )
{
List *next_1, *next_2, *tmp;

next_1=node1->next;
next_2=node2->next;

tmp = node1;
node1 = node2;
node2 = tmp;

node1->next=next_1;
node2->next=next_2;
}




void sort()
{
int i, j;
List *tmpd, *tmp;


for( i=0; i<size; i++ )
{

    for( j=0; j<size-1; j++ )
    {
       current=index( j );
       tmpd=index( j+1 );

       if( current->value > tmpd->value )
       {
            
            Swap( current, tmpd );

            }
        }
    }
}


void fload( char *fname )
{
char ch;
fstream f( fname, ios::in );

if( !f )
{
    cout << "Can`t open file " << fname;
    exit( 1 );
    }

f.seekp( 0, ios::beg );

for( ;!f.eof(); )
{
    f >> ch;
    if( !f.eof() )
    {

        if( ch!=' ' && ch!='\n' && ch!='\t' && ch!='\0' )
            add( ch );

        //cout << ch << endl;
        }

    }
}


void out()
{
int i;

for( i=0; i<size; i++ )
    cout << index( i )->value;
return;
}



int main()
{
int i, j;

//randomize();
/*
for( i='a'; i<'a'+10; i++ )
{
    first_list.add( a, i+random( 10 ) );
    }
*/

fload( "a.txt" );

sort();
out();

return 0;
}

Ошибка однако в функции Swap на разных компиляторах пробовал что то точно не то
ну на tсс разве что прога доходит до конца но толку тож нету.

--------------------

Мои руки из дуба, голова из свинца ну и пусть ...

apook

Дата 3.7.2007, 02:15 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 794
Регистрация: 12.7.2006

Репутация: 9
Всего: 23

В функции Swap перенацеливанием указателей происходит, но после выхода из нее выясняется что все осталось на своих местах, неохото memcpy использовать ведь так должно работать по идее...

--------------------

Мои руки из дуба, голова из свинца ну и пусть ...

KelTron

Дата 3.7.2007, 07:02 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 745
Регистрация: 8.10.2006
Где: Красноярск

Репутация: нет
Всего: 38

Тебе же Sartorius написал:

Цитата(Sartorius @ 2.7.2007, 07:06

)

tmp=end; // меняешь местами указатели. а не данные (*tmp = * end;)
start=end;

Поэтому надо делать так:

Код


if( start->data[ 0 ]>end->data[ 0 ] )
{
    //????
    //первое что приходит в голову
    *tmp=*end;
    *start=*end;
    *end=*tmp
}

Но для этого конечно же надо перегрузить оператор =.

--------------------

Тысячами незримых нитей обвивает тебя Закон. Разрубишь одну - преступник. Десять - смертник. Все - Бог.
Эвенгар Салладорский, основатель Школы Тьмы.

apook

Дата 3.7.2007, 07:26 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 794
Регистрация: 12.7.2006

Репутация: 9
Всего: 23

Нее данные менять неинтересно, а перенацеливание указателей что-то не получается
в данном случае можно менять данные так попроще серавно при перегрузка придется то-же делать:
[code=cpp]
char tmp;
tmp=end->data;
end->data=start->data;
start->data=tmp;
[/code=cpp]
Я хотел именно перенацеливанием указателей... ну тогда отложим пока

--------------------

Мои руки из дуба, голова из свинца ну и пусть ...

Delite

Дата 4.7.2007, 01:02 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 10
Регистрация: 29.1.2007

Репутация: нет
Всего: нет

Если требования разрешают и лень разбираться с кучей вариантов, то можно сделать, например, так:

Код


class Data;
struct Node {
  Data* data_;
  Node* next_;
  Node* prev_;
};

void Swap(Node* n1, Node* n2) {
  Data* t = n1->data_; n1->data_ = n2->data_; n2->data_ = t;
}

apook

Дата 4.7.2007, 01:31 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 794
Регистрация: 12.7.2006

Репутация: 9
Всего: 23

Это замена данных, а не перенацеливание указателей smile

--------------------

Мои руки из дуба, голова из свинца ну и пусть ...

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »