Задача - Форум на исходниках

WWW.ИСХОДНИКИ.РУ cpp.sources.ru

java.sources.ru web.sources.ru soft.sources.ru

jdbc.sources.ru asp.sources.ru api.sources.ru

  Форум на исходниках
  C / C++ / Visual C++
  Задача
СПРОСИТЬ  ОТВЕТИТЬ
профайл | регистрация | faq

Автор Тема:   Задача

One опубликован 25-12-2001 17:05 MSK
Вот какая задача: допустим есть три - много линейных массивов, элементы которых зависят друг от друга, т.е. первый элемент первого массива "привязан" к первому элементу второго массива и т.д (по-строчно). Нужен алгоритм сортировки любого массива таким образом, чтобы привязки во всех остальных массивах остались (строки совпадали).
Вопрос чисто теоретический, т.к. как сам решить вполне в сотоянии, просто интересно, какие будут идеи. Сейчас сам решу, тоже скажу.
One опубликован 25-12-2001 17:29 MSK
Самое простое - понятно, выясняем, какой массив нужно отсортировать, пузырем его и в соответсвии меняем строки в остальных массивах.
проблемма в том, что заранее не известно, по какому массиву сортировать, и получается куча if, особенно если массивов много.
Flex Ferrum опубликован 25-12-2001 17:35 MSK
А массивы однотипные? Может быть их проще в матрицу запихнуть, после чего выбирать нужный массив по индексу?
mishootka опубликован 25-12-2001 17:40 MSK
Конкретезируй задачу, можно ли обойтись не несколькими массивами, а массивом структур? Тогда при перестановках будут изменяться сразу все поля.
Если так необходимо оставить несколько массивов, то заведи для сортируемого массива таблицу перестановок. Сначала сортируешь основной массив, корректируя таблицу перестановок, а потом по полученным индексам меняешь все остальные массивы. Таким образом и производительность повысишь.
One опубликован 25-12-2001 17:44 MSK
Нет, массивы не однотипные да и их количество заранее не известно (вообще задача чисто теоретическая), поэтому с матрицей как-то не очень
One опубликован 25-12-2001 17:45 MSK
А с массивом структур я как то не очень понял - поясни пожалуйста.
mishootka опубликован 25-12-2001 17:59 MSK
Допустим, тебе надо работать со списком файлов. У файла есть имя, размер, дата создания. Можно завести три массива - строковый для имен, интовый для размера и файлтаймовый для времени. А можно создать структуру, включающую имя, размер, время и завести всего один массив этих структур. При сортировке сравниваешь только нужные поля, а копируешь целиком всю структуру.
Flex Ferrum опубликован 25-12-2001 18:07 MSK
А массивы у тебя содержат только примитивные типы (int, double и иже с ними), или могут содержать классы? Мне тут такая идея в голову пришла:
class vector_base
{
public:
virtual bool less(int idx1, int idx2) = 0;
virtual void swap(int idx1, int idx2) = 0;
virtual int size() = 0;
};
template<typename T> vector_tpl : public vector_base
{
protected:
vector<T> array;
public:
virtual bool less(int idx1, int idx2) {return array[idx1] < array[idx2];}
virtual bool swap(int idx1, int idx2)
{::swap(array[idx1], array[idx2]);}
virtual int size() {return array.size();}
};
Твой функция сортировки:
void sort(int idx, vector<vector_base*> arrays)
{
int size = arrays[idx] -> size();
int narrays = arrays.size();
vector_base* array = arrays[idx];
for (int i = 0;i < size - 1;i ++)
for (int j = i;j < size;j ++)
if (!array -> less(i, j)
for (int n = 0;n < narrays;n ++)
arrays[n] -> swap(i,j);
}
One опубликован 25-12-2001 18:11 MSK
Теперь понял - записи короче. Нет, тут задача именно с массивами, теоретическая. Ведь допустим, сегодня мне надо описать файлы (с тремя полями), а завтра информацию о пользователе (с десятью полями). Хотелось бы иметь универсальный алгоритм для этого дела.
One опубликован 25-12-2001 18:12 MSK
2FelxFerrum: да только примитивные. Сейчас попробую :)
Flex Ferrum опубликован 25-12-2001 18:16 MSK
А еще один универсальный агоритм - функция sort из библиотеки stl. На вход она получает два итератора - начала и конец контейера и метод сравнивания элементов этих контейнеров. Контейнер может содержать что угодно - от простых чисел до сложных классов. Главное - определить для него метод сравнения. Сравниваещь по одному полю - получаешь один результат. По другому - другой.
One опубликован 25-12-2001 18:18 MSK
Ага, вроде разобрался.
Ну пускай топик повисит, может, кто еще идей подкинет либо потребуется кому. А может сам еще чего придумаю, поделюсь.
СПРОСИТЬ  ОТВЕТИТЬ
Перейти:

E-mail | WWW.ИСХОДНИКИ.RU

Powered by: Ultimate Bulletin Board, Freeware Version 5.10a
Purchase our Licensed Version- which adds many more features!
© Infopop Corporation (formerly Madrona Park, Inc.), 1998 - 2000.

Автор	Тема: Задача
One	опубликован 25-12-2001 17:05 MSK Вот какая задача: допустим есть три - много линейных массивов, элементы которых зависят друг от друга, т.е. первый элемент первого массива "привязан" к первому элементу второго массива и т.д (по-строчно). Нужен алгоритм сортировки любого массива таким образом, чтобы привязки во всех остальных массивах остались (строки совпадали). Вопрос чисто теоретический, т.к. как сам решить вполне в сотоянии, просто интересно, какие будут идеи. Сейчас сам решу, тоже скажу.
One	опубликован 25-12-2001 17:29 MSK Самое простое - понятно, выясняем, какой массив нужно отсортировать, пузырем его и в соответсвии меняем строки в остальных массивах. проблемма в том, что заранее не известно, по какому массиву сортировать, и получается куча if, особенно если массивов много.
Flex Ferrum	опубликован 25-12-2001 17:35 MSK А массивы однотипные? Может быть их проще в матрицу запихнуть, после чего выбирать нужный массив по индексу?
mishootka	опубликован 25-12-2001 17:40 MSK Конкретезируй задачу, можно ли обойтись не несколькими массивами, а массивом структур? Тогда при перестановках будут изменяться сразу все поля. Если так необходимо оставить несколько массивов, то заведи для сортируемого массива таблицу перестановок. Сначала сортируешь основной массив, корректируя таблицу перестановок, а потом по полученным индексам меняешь все остальные массивы. Таким образом и производительность повысишь.
One	опубликован 25-12-2001 17:44 MSK Нет, массивы не однотипные да и их количество заранее не известно (вообще задача чисто теоретическая), поэтому с матрицей как-то не очень
One	опубликован 25-12-2001 17:45 MSK А с массивом структур я как то не очень понял - поясни пожалуйста.
mishootka	опубликован 25-12-2001 17:59 MSK Допустим, тебе надо работать со списком файлов. У файла есть имя, размер, дата создания. Можно завести три массива - строковый для имен, интовый для размера и файлтаймовый для времени. А можно создать структуру, включающую имя, размер, время и завести всего один массив этих структур. При сортировке сравниваешь только нужные поля, а копируешь целиком всю структуру.
Flex Ferrum	опубликован 25-12-2001 18:07 MSK А массивы у тебя содержат только примитивные типы (int, double и иже с ними), или могут содержать классы? Мне тут такая идея в голову пришла: class vector_base { public: virtual bool less(int idx1, int idx2) = 0; virtual void swap(int idx1, int idx2) = 0; virtual int size() = 0; }; template<typename T> vector_tpl : public vector_base { protected: vector<T> array; public: virtual bool less(int idx1, int idx2) {return array[idx1] < array[idx2];} virtual bool swap(int idx1, int idx2) {::swap(array[idx1], array[idx2]);} virtual int size() {return array.size();} }; Твой функция сортировки: void sort(int idx, vector<vector_base> arrays) { int size = arrays[idx] -> size(); int narrays = arrays.size(); vector_base array = arrays[idx]; for (int i = 0;i < size - 1;i ++) for (int j = i;j < size;j ++) if (!array -> less(i, j) for (int n = 0;n < narrays;n ++) arrays[n] -> swap(i,j); }
One	опубликован 25-12-2001 18:11 MSK Теперь понял - записи короче. Нет, тут задача именно с массивами, теоретическая. Ведь допустим, сегодня мне надо описать файлы (с тремя полями), а завтра информацию о пользователе (с десятью полями). Хотелось бы иметь универсальный алгоритм для этого дела.
One	опубликован 25-12-2001 18:12 MSK 2FelxFerrum: да только примитивные. Сейчас попробую :)
Flex Ferrum	опубликован 25-12-2001 18:16 MSK А еще один универсальный агоритм - функция sort из библиотеки stl. На вход она получает два итератора - начала и конец контейера и метод сравнивания элементов этих контейнеров. Контейнер может содержать что угодно - от простых чисел до сложных классов. Главное - определить для него метод сравнения. Сравниваещь по одному полю - получаешь один результат. По другому - другой.
One	опубликован 25-12-2001 18:18 MSK Ага, вроде разобрался. Ну пускай топик повисит, может, кто еще идей подкинет либо потребуется кому. А может сам еще чего придумаю, поделюсь.