Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > Сорт списк


Автор: apook 2.7.2007, 04:51
Не могу догнать устройство сортировки списка
Если с массивом все ясно
Код

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
Цитата(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
У меня структура такая
Код

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
Цитата

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

Код

NODE *start;
NODE *end;


Код

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


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


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

Автор: apook 2.7.2007, 07:38
Ну что нетак? 
Код

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
на компиляторе не проверял, вроде должно работать, если в конце ничего не затупил (что возможно)
Код

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
zkv  сейчас проверю твой код но я выяснил что в теле функции меняет
а на самом деле все остается на своих местах

Автор: zkv 2.7.2007, 09:26
Цитата(apook @  2.7.2007,  09:14 Найти цитируемый пост)
zkv  сейчас проверю твой код но я выяснил что в теле функции меняет
а на самом деле все остается на своих местах 

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

Автор: apook 2.7.2007, 09:43
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
В функции Swap перенацеливанием указателей происходит, но после выхода из нее выясняется что все осталось на своих местах, неохото memcpy использовать ведь так должно работать по идее...

Автор: KelTron 3.7.2007, 07:02
Тебе же 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
Нее данные менять неинтересно, а перенацеливание указателей что-то не получается
в данном случае можно менять данные так попроще серавно при перегрузка придется то-же делать:
[code=cpp]
char tmp;
tmp=end->data;
end->data=start->data;
start->data=tmp;
[/code=cpp]
Я хотел именно перенацеливанием указателей... ну тогда отложим пока

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

Код

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;
}


smile

Автор: apook 4.7.2007, 01:31
Это замена данных, а не перенацеливание указателей  smile 

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)