Сортировка списка(Нет ничего проще)

[Nomlpppp]

Нет ничего проще чем отсортировать список.
Отсортировать список. Задача хоть не очень сложная, но легко может возникнуть путанница с
указателями. Список представляет из себя структуру кот-я содержит указатель на следующую
структуру этого-же типа. При сортировке придется менять местами элементы списка.
Допустим мы поменяли второй с пятым элементы списка. Теперь на месте второго бывший пятый,
а на месте пятого бывший второй. Так как элемент списка содержит указатель на следуюший элемент,
то имеем указатель на шестой вместо третьего(во втором) и на третий вместо шестого(в пятом). Если
элеметов списка фактически 6 то их станет практически 3. Получется надо менять и указатель на
следующий элемент в каждом из меняемых элементов:

LIST *tmp1, *tmp2, *next_ptr1, *next_ptr2;

// здвигаемся ко второму элементу 
... 
tmp1 = List; // запоминаем
next_ptr1 = List-next; // запоминаем куда указывает

// здвигаемся к пятому элементу 
... 
tmp2 = List;
next_ptr2 = List-next; // запоминаем куда указывает

// меняем местами
List = tmp1;
tmp1 = tmp2;

// восстонавливаем указатели
List->next = next_ptr1;
tmp1->next = next_ptr2;

Теоретически так, но на практике это работать не будет . Потому-что надо учитывать еще и указатели на следующий элемент у предыдущих, орносительно мсеняемых, элементах списка!
В поисках решения данного вопроса, иные умы наворачмвают программу так что потом сами не могут
разобрать свой код.

[Nomlpppp]

Между тем есть простой способ сортировки и работы со списками. Идея такая:
В примере выше была попытка перенацеливания указателей на элементы списка, что в случае со списками
плохой способ. В примере рассмотренном ниже список останется неизменным(порядок
элементов не меняется), будет меняться только указатель на тип SOMETHING(т.е на сами данные).

Например имеется структура даных

typedef _SOMETHING_
 {
 // Здесь любые данные
 ...
 } SOMETHING;

Создать список структур типа SOMETHING:

struct LIST
 {
 SOMETHING some, *some_ptr;

 LIST *next; // Указатель на следующий элемент списка
 };

Обращаю внимание на указатель *some_ptr, так как по ходу программы, и функция сортировки в частности,
будет работать с ним.
Вот ПРИМЕР:

#include<stdio.h>
#include<string.h>
#include<conio.h>
#include<malloc.h>

typedef struct _SOMETHING_
 {
 char name[ 20 ];
 int price; 
 } SOMETHING;


struct LIST
 {
 SOMETHING something, *some_ptr;  

 LIST *next;
 };

LIST *first = NULL;
LIST *end = NULL;

/**
 Добавляет элемент в конец списка
**/
void add_to_list( LIST *List, SOMETHING *some )
 {
 if( !first )
  {
  first = ( LIST * ) malloc ( sizeof(LIST) ); // выделяем память для первого элемента списка
  List = end = first;

  memcpy( &List->something, some, sizeof(SOMETHING) );
  }
 else
  {
  List = end;
  List->next = ( LIST * ) malloc ( sizeof(LIST) );

  List = List->next;
  memcpy( &List->something, some, sizeof(SOMETHING) );

  end = List;
  }

 List->some_ptr = &List->something; // нацеливаем указатель на данные
 }

/**
 Врзвращает указатель на элемент списка с заданным порядковым номером
**/
LIST *list_elm_ptr( LIST *List, int num )
 {
 int sign=0, i=0;

 List = first;

 do
  {
  if( i==num ) break;
  List = List->next;
  if( sign ) break;
  i++;
  if( List==end )
   {
   sign = 1;
   continue;
   }
  } while( 1 );



 return List;
 } 

void change_list( LIST *List, int elm_a, int elm_b )
 {
 LIST *tmp, *change, *to;

 tmp = list_elm_ptr( List, elm_a );      // находим в памяти elm_a  
 change = tmp;
 to = list_elm_ptr( List, elm_b );       // находим в памяти elm_b 

 // перненацеливаем указатель на данные
 change->some_ptr = &to->something;
 to->some_ptr = &tmp->something;   
 }

void show_list( LIST *List )
 {
 int sign=0;
 List = first;

 do
  {
  printf( "%s", List->some_ptr->name );
  printf( "    [ %d ]\n", List->some_ptr->price );
 
  List = List->next;
  if( sign ) break;
  if( List==end )
   {
   sign = 1;
   continue;
   }
  } while( 1 );
 }

/**
 разрушает List
**/
void destroy_list( LIST *List )
 {
 int sign;
 LIST *current;

 List = first;
 do
  {
  if( List==end ) 
   {
   free( List );
   }  
  else if( List->next==end )
   {
   free( List->next );
   end = List;
   continue;
   }

  List = List->next;
  if( List->next==end )
   {
   free( List->next );
   end = List;
   List = first;
   }
  } while( 1 );
 }

int main()
 {
 int i, j, c;

 SOMETHING some;
 LIST *List;


 // TEST 
 for( i=0; i<6; i++ )
  {
  memset( &some, 0, sizeof(SOMETHING) );

  sprintf( some.name, "NAME_%d", i+1 );
  some.price = i+1;
  add_to_list( List, &some );
  }

 show_list( List );
 printf( "-= change List ( 2 to 5 )=-\n" );

 change_list( List, 2, 4 );

 show_list( List );
 getch();



 return 0;
 }

[Nomlpppp]

Подробнее о функции change_list

1: void change_list( LIST *List, int elm_a, int elm_b )
2: {
3: LIST *tmp, *change, *to;
4:
5: tmp = list_elm_ptr( List, elm_a ); // находим в памяти elm_a
6: change = tmp;
7: to = list_elm_ptr( List, elm_b ); // находим в памяти elm_b
8:
9: // перненацеливаем указатель на данные
10: change->some_ptr = &to->something;
11: to->some_ptr = &tmp->something;
12: }

В строке 10 и 11 происходит весь прикол. Элемент списка(все данные) остался на месте, но указатtель some_ptr стал указывать на другие места.

Вот как ывглядит эта-же функция опботающаяя по принципу перенацеливания указателей на элементы списка

void change_list( LIST *List, int elm_a, int elm_b )
 {
 LIST *tmp, *change, *to, *change_next, *to_next;

 change = list_elm_ptr( List, elm_a );      // находим в памяти elm_a  
 to = list_elm_ptr( List, elm_b );          // находим в памяти elm_b 

 change_next = change->next;
 to_next = to->next;


 if( change==first ) first = to;
 else if( to==first ) first=change;


 tmp = change;
 change = to;
 to = tmp;


 tmp = change->next;
 change->next = to->next;
 to->next = tmp;


 if( elm_a )
  {
  tmp = list_elm_ptr( List, elm_a-1 );
  tmp->next = change;
  }

 if( elm_b )
  {
  tmp = list_elm_ptr( List, elm_b-1 );
  tmp->next = to;
  }
 }