С++: cортировка односвязного списка перестановкой указателей

Сортировка односвязного списка - одна из самых дурацких головоломных задач для начинающих.

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

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

По-моему, вся беда этих и подобных кодов в том, что аффтары пытались применить любимый "пузырёк" к списку по аналогии с массивом, а в списке из-за перестановок указателей начиналась путаница...

Метод вставок рулит, что б там не писали на форумах. Остальные комменты в исходнике:

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 30

typedef struct student {
 unsigned char f[MAX]; //Фамилия
 int ekz[4]; //4 оценки
 student *next; //Указатель на следующего студента
};

int show (student *head) {
 //Показать список, начиная с эл. head и вернуть кол-во записей
 int count=0;
 while (1) {
  printf ("\n%s",head->f);
  for (int i=0; i<4; i++) printf (" %d",head->ekz[i]);
  count++;
  if (!head->next) break;
  head=head->next;
 }
 return count;
}

student *sort (student *ph) {
 //Сортируем список по алфавиту (фамилии, полю f) и возвращаем
 //указатель на начало измененного списка
 student *q,*out=NULL,*p,*pr; //out - выход - сначала пуст
 while (ph !=NULL) { //пока не конец входного списка
  q = ph; ph = ph->next; //исключить очередной элемент
  for (p=out,pr=NULL; p!=NULL && strcmp(q->f,p->f)>0; pr=p,p=p->next);
   //ищем, куда включить очередной элемент - тут strcmp
   //задает критерий сравнения элементов, в вашей задаче м.б. другой
  if (pr==NULL) { q->next=out; out=q; } //включение в начало
  else { q->next=p; pr->next=q; } //или после предыдущего
 }
 return out;
}

void main () {
 student group[] = { //В начале фамилии в списке расставлены как в массиве -
  //предыдущий элемент показывает на следующий
  {"Popov",{4,4,3,3},&group[1]},
  {"Belugin",{4,5,3,5},&group[2]},
  {"Ivanov",{4,4,5,5},&group[3]},
  {"Yakovlev",{5,4,3,2},&group[4]},
  {"Petrov",{5,5,5,5},NULL}
 };
 printf ("\nИсходный список:");
 int count=show (&group[0]);
 printf ("\nВсего записей: %d",count);
 //Сортируем список структур по алфавиту
 student *ptr=sort (group);
 printf ("\nОтсортированный список:");
 show (ptr);
 getchar();
}

Проверил в консольном Borland C++ 3.1, работает, завершается без Null pointer assignment, значит, есть надежда, что нормально... хотя вырожденные случаи не смотрел, а писал в спешке, мож чего и не так, тогда жду поправок.

Более новые коды по действиям с подобной структурой есть в этой статье.

12.02.2013, 00:14 [17127 просмотров]