Программирование на Си: как отсортировать двунаправленный список?
=================================================================

Здравствуйте. Помогите, пожалуйста, с программированием.  
В программе есть двунаправленный список:  
struct l2  
{  
 char*name;  
 char*ext;  
 l2*next;  
 l2*prev;  
};  
Его нужно отсортировать по полю name. Как это сделать?  
Точнее, основной вопрос в том, как поменять местами два элемента списка. Если это получится, дальше справлюсь.  
Заранее спасибо за помощь.

Предполагаете ли Вы, что менять местами Вы всегда будете только соседние   
элементы списка? Если да, то как нам считать, что нам дан указатель на   
первый из этих двух элементов? Или на второй?   
  
Или Вы хотите уметь менять местами произвольные два элемента списка?   
Тогда задача усложняется. Тогда нам даны два указателя. Правильно я понимаю?   
Тогда нужно подумать, не следует ли соблюдать осторожность и учитывать, что   
случайно элементы могут всё-таки оказаться соседними — как бы тогда   
чего не затереть.   
  
При работе со списками вообще нужно соблюдать осторожность и,   
изменяя указатели, не потерять раньше времени нужный указатель.   
  
А идея простая:   
  
поля next и prev в первом элементе нужно сделать такими,   
какие они во втором элементе, и наоборот,   
  
левый сосед (prev-сосед) первого элемента должен теперь указывать   
не на первый, а на второй элемент (то есть нужно поменять в нём next),   
  
ну и аналогично с правым соседом, то есть с next-соседом (поменять в нём prev),   
и аналогично с соседями второго элемента.

Спасибо большое.  
Сортировать нужно методом выбора, т.е. менять местами минимальный и первый, следующий и второй и т. д.  
Получается, нужно поменять 8 указателей? А в чем отличие, если элементы соседние?

Итак, как я понял, менять местами нужно произвольные элементы списка.   
Но случайно они могут оказаться и соседними.   
И даже случайно может оказаться так, что минимальный элемент уже и так   
находится на первом месте. И как тогда? Менять его с самим собой?   
Желательно заранее продумать этот вопрос.   
  
Вам нужно написать функцию, давайте назовём её SWAP, которая принимает в   
качестве параметров два указателя и которая меняет местами элементы, на   
которые указывают эти указатели.   
Вы должны принять одно из двух решений:   
1) Функция SWAP всегда должна работать правильно,   
2) Функция SWAP должна работать правильно, если ей дают разные указатели,   
а если одинаковые — мы ничего не гарантируем. В этом во втором случае   
нужно следить, чтобы вызывающая функция никогда не вызывала функцию SWAP   
с указателями, равными друг другу.   
  
Возможно, что мои опасения излишни, и что при разумном подходе к написанию   
функции SWAP она и так получится универсальной и всегда будет работать   
правильно. Над этим надо подумать. Но просто такие тонкости нужно всегда   
иметь в виду.   
  
Возможно также, что при разумном подходе к написанию функции SWAP не нужно   
будет отдельно рассматривать случаи, когда элемнты соседние и когда не   
соседние. Об этом тоже нужно подумать.   
  
Давайте подсчитаем, количество указателей, которые нужно поменять.   
Пусть список такой:   
. . . ABC . . . . . . DEF . . .   
Допустим, что менять местами нужно B и E. Тогда надо:   
1) в элементе A изменить указатель next,   
2) в элементе B изменить указатель prev,   
3) в элементе B изменить указатель next,   
4) в элементе C изменить указатель prev,   
5) в элементе D изменить указатель next,   
6) в элементе E изменить указатель prev,   
7) в элементе E изменить указатель next,   
8) в элементе F изменить указатель prev.   
Действительно, поменять нужно 8 указателей.   
  
И даже если элементы C и D совпадают — всё равно 8.   
  
Но вот если совпадают B и D, а значит совпадают C и E,   
то есть B и E — соседние,   
то пункты 3 и 5 — это одно и то же   
и пункты 4 и 6 — это одно и то же.   
Получается, что поменять нужно 6 указателей.   
Это ответ на Ваш вопрос "в чем отличие, если элементы соседние?"   
  
И опять-таки, возможно, что при разумном написании программы   
в программе всегда будет выполняться 8 присваиваний, из которых   
иногда 2 будут дублирующими, но не будут приводить к плохим последствиям.   
  
И ещё. В этом примере элемент B левее элемента E, даже когда B и E — соседние.   
Вы должны принять одно из двух решений:   
1) Функция SWAP всегда должна работать правильно,   
2) Функция SWAP должна работать правильно, если элемент,   
на который указывает первый указатель,   
расположен левее элемента, на который указывает второй указатель.   
А если наоборот (да к тому же элементы соседние!) — мы ничего   
не гарантируем.   
  
И ещё. Элемент B может оказаться первым элементом в списке.   
Тогда действие 1 отпадает просто потому, что элемента A вообще не существует.   
Но эта-то проблема решается легко. Нужно просто проверить, не является ли   
нулевым указатель prev в элементе B.   
  
И ещё. Элемент E может оказаться последним элементом в списке . . .   
  
Попробуйте самостоятельно написать функцию SWAP (целиком или хотя бы фрагмент),   
а мы проверим, что у Вас получается и подскажем, если что-то не так.

Вот что получилось:  
void swap(l2*a,l2*b)  
{  
 if(a==b) return;  
 if(b==a->next)  
 {  
 l2*temp=a->prev->next;  
 a->prev->next=b->prev->next;  
 b->prev->next=temp;  
 temp=a->next->prev;  
 a->next->prev=b->next->prev;  
 b->next->prev=temp;  
 temp=a->next;  
 a->next=b->next;  
 b->next=temp;  
 temp=a->prev;  
 a->prev=b->prev;  
 b->prev=temp;  
 }  
  
 else  
 {  
 a->prev->next=b;  
 b->next->prev=a;  
 a->next->prev=b;  
 b->prev->next=a;  
 l2*temp=a->prev;  
 a->prev=b->prev;  
 b->prev=temp;  
 temp=a->next;  
 a->next=b->next;  
 b->next=temp;  
 }  
}  
Она вроде работает, но сортировка с ней не получается, ошибку пока не могу найти.  
  
>>И ещё. Элемент B может оказаться первым элементом в списке.   
>>И ещё. Элемент E может оказаться последним элементом в списке . . .  
у меня список с фиктивным первым и последним элементом, так что не окажутся.

Вот сортировка:  
void sortN(l2*beg,l2*end)//сортировка по имени  
{  
 for(l2*i=beg->next;i->next!=end->prev;i=i->next)  
 {  
 l2*min=i;  
 for(l2*j=i->next;j->next!=end;j=j->next)  
 if(strcmp(j->name,min->name)<0)  
 min=j;  
 swap(min,i);  
 }  
}  
Может, в ней что-то не так?

Поняла, что должно быть swap(i,min). Но сортировка всё равно не работает. :-(

Процитируйте инициализацию списка — посмотреть на B и E.

Честно говоря, не знаю, что такое инициализация. Список формируется вот так:  
  
l2*form(char*s)//формирование элемента списка  
{  
 l2*el=new l2;  
 char*t=new char[strlen(s)+1];  
 strcpy(t,s);  
 char*pnt=strrchr(t,'.');  
 el->name=t;  
 if(pnt!=0)  
 {  
 *pnt='\0';  
 code(el->name);  
 el->ext=pnt+1;  
 code(el->ext);  
 el->next=el->prev=0;  
 return el;  
 }  
 code(el->name);  
 el->ext=" ";  
 el->next=el->prev=0;  
 return el;   
}  
void form2(FILE*f,l2*beg,l2*end)//формирование списка  
{  
 beg->name=beg->ext=0;  
 end->name=end->ext=0;  
 beg->prev=end->next=0;  
 beg->next=end;  
 end->prev=beg;  
 l2*n=beg->next;  
 char t[4096];  
 while(fgets(t,4095,f)!=0)  
 {  
 l2*Nel=new l2;  
 Nel=form(t);  
 Nel->next=n;  
 Nel->prev=n->prev;  
 n->prev->next=Nel;  
 n->prev=Nel;  
 }  
}

Сделал список из 4-х элементов:  
B: предыдущий к нему он сам; следующий к нему — 1-й элемент.  
1-й элемент: предыдущий к нему B; следующий — 2-й.  
2-й элемент: предыдущий к нему 1-й; следующий — E.  
E: предыдущий к нему 2-й, следующий он сам.   
  
Поля name:  
у B и E пустые, у 1-го и 2-го в обратном алфавитном порядке.   
  
При вашей сортировке на таком массиве в цикл по i не входим: при инициализации i указывает на 1-й элемент, и условие i->next!=end->prev не выполнено. Ну, ок, заменяю его на i->next!=end.   
  
Теперь не входим в цикл по j: при инициализации j указывает на второй элемент, а для него j->next!=end не выполнено. Ну, не вопрос — меняю условие на j->next!=j.   
  
При таких раскладах сортировка двух элементов, кажется, произошла :) Во всяком случае   
listL2[0].next->name  
listL2[0].next->next->name  
оказались упорядочены. listL2 — массив структур l2:  
n=4;  
l2 *listL2;  
listL2 = new l2 [n];  
  
Дальше не смотрел.

j->next!=j — это как?

Уточните вопрос )  
  
У меня j->next равно j для последнего элемента E.

Да, прочитала внимательнее и поняла.  
Только с моим списком понятнее не становится, увы. :(

В 6-й строке (функция swap) у Вас написано:   
l2*temp=a->prev->next;  
  
Выражение a->prev->next равно a. Почему бы 6-ю строку не написать проще:   
l2*temp=a;  
   
В 7-й строке у Вас написано:   
a->prev->next=b->prev->next;   
  
Выражение b->prev->next равно b, 7-ю строку тоже можно написать проще:   
a->prev->next=b;   
Смысл 7-й строки таков: указатель next в элементе, предшествующем   
элементу a, раньше указывал на a, но теперь должен указывать на b. Логично.   
  
Смотрим 8-ю строку:   
b->prev->next=temp;  
В переменной temp у нас указатель a.   
b->prev — тоже указывает на a. Значит, в элементе a поле next мы делаем   
равным a, то есть элемент a будет указывать сам на себя. Это ли нам нужно?   
В этом, видимо, ошибка.   
   
Дальше я не смотрел.   
  
Про функцию swap Вы написали "Она вроде работает". А как Вы проверяли?   
У Вас написаны какие-нибудь вспомогательные функции, с помощью которых   
Вы могли бы создать список небольшой длины?   
Есть ли у Вас функция, которая вывела бы список на экран?   
Есть ли у Вас функция, с помощью которой можно было бы получить указатель   
на какой-нибудь желаемый элемент списка? Потом на другой элемент.   
Имея эти указатели, нужно вызвать функцию swap и ещё раз вывести список   
на экран — проверить, переставлены ли как надо элементы списка.   
Проделать такую проверку нужно многократно, проверяя разные случаи   
(соседние — не соседние, и т.п.).   
И нужна ещё одна вспомогательная функция — которая выводит список на экран   
задом наперёд. Дело в том, что при неправильной работе функции swap   
может оказаться неправильной структура, создаваемая указателями prev,   
а при выводе массива от начала к концу Вы этого не заметите.

>>У Вас написаны какие-нибудь вспомогательные функции, с помощью которых Вы могли бы создать список небольшой длины?  
Я просто из другого файла считываю список поменьше.  
  
Вывод на экран (в обе стороны) есть, получается одно и то же.  
Про функцию для получения указателей я не поняла.  
  
Со сменой указателей совсем затык:( Не могли бы вы написать, как их правильно менять?

Я постараюсь ещё раз объяснить то, о чём я уже писал.   
При серьёзном программировании значительная часть усилий тратится   
на написание вспомогательных, или отладочных, кусков программы.   
С этим нужно смириться и на этом экономить не нужно.   
  
Я бы начал с того, что создал бы какой-нибудь коротенький список,   
например из 6 элементов, а поля name заполнил бы указателями на   
какие-нибудь простенькие строки, например:   
"один", "два", "три", "четыре", "пять", "шесть".   
  
Вы умеете создавать такие списки?   
Вашу фразу про другой файл я не очень понял.   
Так всё-таки, можете создать такой список или с этим проблемы?   
Не так важно, каким способом. Я бы написал функцию   
void add\_to\_end(l2 *end, char *s),   
которая добавляла бы в конец списка новый элемент, в котором указатель   
name указывал бы на строку s. Затем я написал бы вызовы этой функции:   
add\_to\_end(end, "один");   
add\_to\_end(end, "два");   
add\_to\_end(end, "три");   
add\_to\_end(end, "четыре");   
add\_to\_end(end, "пять");   
add\_to\_end(end, "шесть");   
 — и список готов.   
Но если хотите — можно создавать список чтением данных из файла.   
  
Затем выводим список на экран. Должны получить:   
  
один два три четыре пять шесть   
  
Затем используем функцию вывода задом наперёд. Должны получить:   
  
шесть пять четыре три два один  
   
Вы получали такое? Привели бы пример того, что у Вас было на экране.   
(Заодно могли бы и сами функции вывода привести.)   
  
А дальше нужно проверить работоспособность функции swap.   
Вы пишете: "Про функцию для получения указателей я не поняла".   
А я не понял, как же Вы всё-таки проверяли функцию swap.   
Ведь Вы же написали "Она вроде работает".   
  
Я бы написал, например, функцию, которая по порядковому номеру   
элемента в списке возвращает указатель на этот элемент.   
Заголовок функции был бы таким:   
l2 *get\_pointer(l2 *beg, int n)   
(Хорошее для Вас упражнение: написать такую функцию, это совсем нетрудно.)   
А затем вызываем функцию swap, например так:   
swap(get\_pointer(beg,2), get\_pointer(beg,4)) — должны поменяться местами   
второй и четвёртый элементы списка.   
При выводе списка на экран должны увидеть:   
   
один четыре три два пять шесть   
  
При использовании вывода задом наперёд должны увидеть:   
   
шесть пять два три четыре один  
   
Вы такое видели? Хотелось бы, чтобы Вы разместили здесь, что Вы видели.   
Потому что мне непонятна Ваша фраза   
"Вывод на экран (в обе стороны) есть, получается одно и то же".

Да, кстати. Согласны ли Вы с моими замечаниями по поводу строк 6, 7, 8   
в функции swap? Или это я чего-то недопонял?

Юрий Анатольевич, большое спасибо за помощь, я уже со всем разобралась и сдала программу!