Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 28.01.2010, 19:56
гость

 
Сообщений: n/a

Сортировка слиянием
http://algolist.ru/sort/merge_sort.php

Как сделать такую сортировку в двухсвязном списке?:

struct titem
{
char dvd[50]; //Название DVD-плеера
char mark[50]; //Марка
float cena; //Цена
char data[50]; //Дата выпуска
char color_p[50]; //Цвет
char razmer[50]; //Размер
char ves[50]; //Вес
char moshnost[50]; //Мощность
titem * next; //cледующая запись
titem * prev; //предыдущая запись
};
  #2  
Старый 28.01.2010, 20:39
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Как сделать такую сортировку в двухсвязном списке?:
Ключевое слово - двусвязный? Считай, что он односвязный (т.е. игнорируй поле prev), сортируй как обычно, потом дополнительным проходом по списку расставляй правильные значения prev.
  #3  
Старый 28.01.2010, 20:47
гость

 
Сообщений: n/a

Ну вот я вписал код подпрограммы сортировки, а как его вызвать, если я хочу сортировать по полю char dvd[50] ?
  #4  
Старый 28.01.2010, 21:18
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Ну вот я вписал код подпрограммы сортировки, а как его вызвать, если я хочу сортировать по полю char dvd[50] ?
код - в студию!
  #5  
Старый 28.01.2010, 21:26
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
код - в студию!
template<class T>
void MergeSort(T *const A, int const n)
{
if( n < 2 ) return; //Сортировка не нужна

if( n == 2 ) //Два элемента проще поменять местами,
{ // если нужно, чем делать слияние
if( A[0] > A[1] ) { T const t(A[0]); A[0]=A[1]; A[1]=t; }
return;
}

MergeSort(A , n/2 ); //Сортируем первую половину
MergeSort(A+n/2, n-n/2); //Сортируем вторую половину

T *const B( new T[n] ); //Сюда запишем результат слияния

Merge(A,n/2, A+n/2,n-n/2, B); //Слияние половин

//Копирование результата слияния в исходный массив:
for(int i(0); i<n; ++i) A[i]=B[i];

delete[n] B; //Удаляем временный буфер
}
  #6  
Старый 28.01.2010, 21:47
гость

 
Сообщений: n/a

Я так думаю, через это нужно сравнивать?:
int lcmp(titem * p1, titem * p2)
{
return strcmp(p1->dvd,p2->dvd);
}
  #7  
Старый 28.01.2010, 23:04
гость

 
Сообщений: n/a

Вы не тот код привели. Это же у вас сортировка массива, а не связанного списка.
Сообщение от гость Посмотреть сообщение
template<class T>
void MergeSort(T *const A, int const n)
{
if( n < 2 ) return; //Сортировка не нужна

if( n == 2 ) //Два элемента проще поменять местами,
{ // если нужно, чем делать слияние
if( A[0] > A[1] ) { T const t(A[0]); A[0]=A[1]; A[1]=t; }
return;
}

MergeSort(A , n/2 ); //Сортируем первую половину
MergeSort(A+n/2, n-n/2); //Сортируем вторую половину

T *const B( new T[n] ); //Сюда запишем результат слияния

Merge(A,n/2, A+n/2,n-n/2, B); //Слияние половин

//Копирование результата слияния в исходный массив:
for(int i(0); i<n; ++i) A[i]=B[i];

delete[n] B; //Удаляем временный буфер
}
  #8  
Старый 29.01.2010, 04:29
гость

 
Сообщений: n/a

Да, я понял. Мне нужно эту функцию подстроить под мой список, но никак не получается.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Повторная сортировка (или сортировка после изменений) motz-art Сортировка и поиск 3 17.08.2009 00:49
Внешняя сортировка прямым слиянием OKSI55 Сортировка и поиск 0 22.03.2009 13:31
Помогите реализовать сортировку естественным двухпутевым слиянием на С++ Witcher Сортировка и поиск 9 19.06.2008 14:38