25 / 25 / 0
Регистрация: 21.11.2009
Сообщений: 159
|
||||||
1 | ||||||
Реализация алгоритма сортировки для любых типов данных08.12.2009, 22:49. Показов 12580. Ответов 38
Метки нет (Все метки)
Помогите пожалуйста переделать реализацию сортировки так, чтобы она могла работать с любыми типами данных(int, double, etc) Т.е. могла сортировать не только целые числа, но и строки, etc.. Начал делать через функцию обратного вызова и застрял..
вот header: sort.h typedef int (*cmp_fnx)(void*, void*) void sort(void *v, int c, int s, cmp_fnx); //указатель на массив, количество элементов, на размерность каждого элемента Сам алгоритм:
0
|
08.12.2009, 22:49 | |
Ответы с готовыми решениями:
38
Реализовать три любых алгоритма сортировки матрицы на выбор Реализация алгоритма сортировки Шелла Реализация алгоритма сортировки массива Реализация алгоритма сортировки слиянием |
2816 / 1407 / 107
Регистрация: 07.03.2009
Сообщений: 4,446
|
|
08.12.2009, 22:51 | 2 |
1
|
425 / 229 / 87
Регистрация: 25.03.2009
Сообщений: 744
|
|
08.12.2009, 23:01 | 3 |
Shim, Вандервуд , Джосаттис шаблоны С++ тебе этого на долго хватит)
1
|
25 / 25 / 0
Регистрация: 21.11.2009
Сообщений: 159
|
||||||
09.12.2009, 00:16 [ТС] | 4 | |||||
вот как-то так ?)) У меня не очень много времени, поэтому прошу отвечать по существу, если не сложно))
0
|
2816 / 1407 / 107
Регистрация: 07.03.2009
Сообщений: 4,446
|
|
09.12.2009, 01:28 | 5 |
Shim, да.
T - Это тип твоего массива
1
|
25 / 25 / 0
Регистрация: 21.11.2009
Сообщений: 159
|
|
09.12.2009, 03:08 [ТС] | 6 |
Просто запихнуть алгоритм в фигурные скобки я так думаю будет недостаточно)) А как это должно выглядеть в коде ? Черкани пожалуйста)
0
|
32 / 32 / 7
Регистрация: 26.10.2009
Сообщений: 98
|
|||||||||||
09.12.2009, 05:07 | 7 | ||||||||||
Вот код шаблонной функции для поиска значения в массиве и возврата его индекса (для примера) :
1
|
25 / 25 / 0
Регистрация: 21.11.2009
Сообщений: 159
|
||||||
10.12.2009, 21:43 [ТС] | 8 | |||||
через шаблон не годится, нужно делать через функцию обратного вызова...я не врубаюсь..
например для того чтобы поменять местами элементы(n1 и n2):
0
|
10.12.2009, 23:21 | 9 | |||||
Сделаем обобщённую функцию, которая в массиве произвольного типа переставляет местами два элемента. Для сортировки нужна будет аналогичная функция, которая сравнивает два элемента. Программу не запускал и не проверял - чисто чтобы объяснить, по какому принципу
В случае сортировки у тебя должен быть указатель на функцию, которая делает сравнение элементов и возвращает -1, 0 или 1 в зависимости от результата (меньше, равно, больше). Чтобы поменятть местами два элемента, такой мазохизм, как я привёл, не нужен. Можно просто в массиве побайтово поменять два куска от указателей на элементы. Куски размером elem_size байт
1
|
25 / 25 / 0
Регистрация: 21.11.2009
Сообщений: 159
|
||||||
11.12.2009, 01:05 [ТС] | 10 | |||||
Evg, спасибо, идею я вроде понял, но вот код аццкий)) Вот у меня библиотека состоит из header'а и cpp'шного файла xsort(я в 1м посте их написал), мне надо сделать, чтобы у меня вот в этом cpp'шном файле реализовалась функция которая может сортировать любые данные...а не просто менять 2 элемнта местами.. Я вот примерно функцию сравнения 2 чисел типа int попытался написать, но насколько это правильно не знаю, ибо не умею программировать, а задание сделать надо)) А как сделать для любых типов данных вообще не представляю(((
0
|
11.12.2009, 11:02 | 11 |
Не совсем правильно. Если одно число меньше другого, надо вернуть -1, если равны - 0, если больше, то +1. Я не сторонник того, чтобы выкладывать готовые решения. Пример привёл для того, потому что словами это не опишешь.
В моём примере было обмен местами двух элементов. А для сортировки надо, по сути дела сравнить и поменять
1
|
25 / 25 / 0
Регистрация: 21.11.2009
Сообщений: 159
|
|
11.12.2009, 14:34 [ТС] | 12 |
Evg, в вашем коде рассмотрены функции перестановки int'ов и double'в, а мне нужно для любых типов данных...
0
|
11.12.2009, 14:57 | 13 |
Перставлять - побайтный обмен местами от указателей p1 и p2 размером elem_size. Но функцию сравнения придётся писать для КАЖДОГО типа. Тут либо по одной функции для каждого типа, либо шаблон Си++ (что в конечном итоге так же родит по одной функции каждого типа)
1
|
25 / 25 / 0
Регистрация: 21.11.2009
Сообщений: 159
|
||||||
11.12.2009, 15:20 [ТС] | 14 | |||||
не, через шаблон не годится, ибо препод сказал что на лекц. нам про шаблоны не читал.
Добавлено через 16 минут Вот пример: поиск max в массиве (используем тип указателя viod* который может указывать на что угодно). Мне нужно по-аналогии сделать..
0
|
25 / 25 / 0
Регистрация: 21.11.2009
Сообщений: 159
|
||||||
13.12.2009, 01:10 [ТС] | 15 | |||||
не надо для каждого типа по функции делать..вот когда у нас целочисленные(инты) мы можем без проблем поменять элементы местами, вводим 3ю переменную, и сравниваем с ней, а когда мы не знаем тип, делаем так, вот есть 2 элемента, n1 и n2, каждый размером S байт, меняем побайтово, а я не могу это запихнуть в то место, ибо не знаю как написать, где у меня в алгоритме сортировки элементы меняются местами, думаю что вызову функцию из библиотеки, вот в библиотеку мне осталось записать функцию, которая должна сортировать любые типы данных, задание-то заключается в том, чтобы написать универсальную библиотеку. Помогите пожалуйста))
Добавлено через 18 минут что-то вот как-то так: (j - сдвиг на сколько-то байт)
0
|
13.12.2009, 17:38 | 16 |
Shim, из твоих рассуждений ничерта не понял. Одно могу сказать тебе точно - универсальную функцию нельзя написать ПО ОПРЕДЕЛЕНИЮ, т.к. неизвестно, как СРАВНИВАТЬ два куска памяти (в которых расположена переменная заранее неизвестного типа). Ибо сортировка основывается на сравнении. Универсальность в данном случае заключается в том, что ты заводишь новый тип (или берёшь существующий), пишешь для этого типа функцию сравнения и подаёшь указатель на неё в функцию сортировки. Сама функция сортировки при этом не меняется и сортировка работает для любого типа. А функция сравнения по сути является некоторым параметром сортировки, определяющим тип аргументов. Для самой функции сортировки этот параметр прозрачен, т.к. сортировка просто вызывает эту функцию и передаёт указатель на участки памяти. Что делается в этой функции (т.е. как конкретно идёт сравнение) - функции сортировки безразлично
По поводу твоего кода, я так же не пойму, что ты хочешь. Написать функцию или описать тип указателя на функцию. И почему она у тебя называется cmp (сравнить), в то время как функция занимается обменом двух участков памяти (swap)
1
|
25 / 25 / 0
Регистрация: 21.11.2009
Сообщений: 159
|
|
13.12.2009, 18:25 [ТС] | 17 |
эээм...нужно написать универсальную библиотеку, а не функцию, т.е. чтобы библиотеку потом можно было бы прикрутить куда нибудь, идею я написал как сам понял - когда в сортировке доходит до той части где меняются местами элементы, вызывается из моей библиотеки эта функция, которая вне зависимости от типа данных, меняет нам элементы побайтово(ex: если в одной аудитории 20 студентов и в другой 20, нам надо поменять их местами, мы же не можем взять их в охапку и перетащить...вот по одному и меняем).
0
|
25 / 25 / 0
Регистрация: 21.11.2009
Сообщений: 159
|
|
14.12.2009, 01:27 [ТС] | 19 |
тогда хз, я уже начинаю подозревать что задание невыполнимое...(по крайней мере для меня)
Добавлено через 16 минут сейчас уже ничего не соображаю, буду завтра на свежую голову думать..
0
|
20.12.2009, 23:44 | 20 |
Shim, я уже и позабыл, что было в первом посте...
Давай начнём со следующего. Для начала просто напиши сортировку int'ов без всяких дополнительных премудростей. То, что у тебя написано, в принципе верно (по крайней мере с ходу кажется, что верно), но несколько "некрасиво". Реализуй метод "сортировка пузырьком". В инете навалом мест, где это описано. Почему прошу сделать аккуратно? Потому что когда будем делать навороты над этой программой, то при аккуратной (классической) записи проще будет воспринимать и проще не наделать косяков. Хотя если ты готов работать со своей версией, то можно работать и на ней. Если готов рабоатть с текущей версией, то напиши полную программу, включая main и Change (правда по английски это называется не "change", а "swap") и добейся её работоспособности. Для порядку лучше иметь несколько массивов (хотя бы два). После чего поедем дальше
1
|
20.12.2009, 23:44 | |
20.12.2009, 23:44 | |
Помогаю со студенческими работами здесь
20
Реализация алгоритма сортировки пирамидой Реализация алгоритма сортировки слиянием Реализация алгоритма сортировки вставками Реализация алгоритма пузырьковой сортировки Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |