Поиск по близости к заданному значению ключа.
Нужно реализовать алгоритм поиска по близости к заданному значению ключа в таблице, одно из полей которой ключевое. Что вообще означает это понятие "по близости к заданному значению ключа". Просмотрел несколько книг по алгоритмам - нигде не могу найти. Если Вам нетрудно - поясните, а если уж совсем легко :) - кусочек кода с реализацией. И еще - в задании конкретно не указано - отсортирована таблица или нет. Есть ли одинаковые ключевые поля. Если можно - мысли по этому вопросу.
Заранее благодарен.
Заранее благодарен.
формулировка меня поставила в тупик, но поскольку вы просили еще и мысли...
И еще - в задании конкретно не указано - отсортирована таблица или нет. Есть ли одинаковые ключевые поля. Если можно - мысли по этому вопрос
Цитата:
И еще - в задании конкретно не указано - отсортирована таблица или нет. Есть ли одинаковые ключевые поля. Если можно - мысли по этому вопрос
я так понимаю имеется ввиду реляционная таблица. так вот в реляционном исчислении - порядок строк таблицы и столбцов значения не имеет. это по поводу сортировки. ключевое поле всегда уникально. это насчет одинаковых кл. полей
если нетрудно - запостите задание дословно.
А отчего такая задача возникла?
Я по своему понял насчет "поблизости": как-то мне надо было сделать ссылки на ближайшие публикации к текущей. Т.е. например известно, что ID текущей (открытой) публикации скажем 15, нужно вывести ссылки на 2 предшествующие ей по дате публикации в том же разделе и 2 ссылки на публикации после текущей. Таблица публикаций отсортирована по дате публикации. ID'ы могут идти не по порядку, некоторых номером может вовсе не быть. 1ым запросом выбирал ..WHERE id<15 LIMIT 2, вторым соответственно ..WHERE id>15 LIMIT 2. Более красивого способа придумать не удалось.
Я по своему понял насчет "поблизости": как-то мне надо было сделать ссылки на ближайшие публикации к текущей. Т.е. например известно, что ID текущей (открытой) публикации скажем 15, нужно вывести ссылки на 2 предшествующие ей по дате публикации в том же разделе и 2 ссылки на публикации после текущей. Таблица публикаций отсортирована по дате публикации. ID'ы могут идти не по порядку, некоторых номером может вовсе не быть. 1ым запросом выбирал ..WHERE id<15 LIMIT 2, вторым соответственно ..WHERE id>15 LIMIT 2. Более красивого способа придумать не удалось.
Это задание по контрольной в институте.
Мой вариант - 20
Не могу найти информацию относительно "поиска по близости к заданному значению ключа".
Курс: “ Структуры и организация данных в ЭВМ ”
Контрольная работа № 1
Тема: ” Методы сортировки и поиска в таблице по заданному ключу”.
Варианты заданий
1.Сравнительный анализ линейного выбора с подсчетом и метода Шелла. Поиск с барьером.
.....................................
20.По близости к заданному значению ключа. Сортировка методом «пузырька» и двухпутевого слияния.
...................................
40. Сортировка таблицы комбинированием методов “быстрой сортировки” и вставки (метод вставка рекомендуется использовать для таблиц длиной<=9). Поиск по совпадению ключа при наличии нескольких элементов с одинаковым значением ключа.
Пояснения к выполнению контрольной работы
1.Выбор предметной области. Для заданной предметной области создать таблицу с исходными данными. Таблица должна иметь не менее трех полей (одно поле - ключевое) и содержать не мение 15 записей.
2.Формирование данных таблицы. Ввод исходных данных должен быть реализован как с клавиатуры, так из файла.
3.Сортировка таблицы. Используя теоретические данные по заданному методу сортировки, согласно варианта, разработать программу и выполнить упорядочение данных. Экспериментальные данные по методам сортировки должны быть полученные по исходным данным, которые должны быть подготовленные в трех вариантах:
- исходные данные находятся в произвольном виде (не упорядоченные);
- исходные данные упорядоченные;
- исходные данные упорядоченные в обратном порядке;
4.Сравнительный анализ. Теоретические и экспериментальные данные и результаты сравнения различных методов сортировки должны быть представлены в виде таблицы по следующей форме:
- метод сортировки;
- количество сравнений;
- количество обменов;
- резерв памяти.
Выходная таблица формируется в файл и на печать.
5. Поиск в таблице. Разработать программу поиска для заданного ключевого поля.
Отчет должен содержать
1.Задание по контрольной работе.
2.Теоретические данные по заданным методам.
3.Ручной просчет.
4.Экспериментальные данные.
5.Листинг программы. Выделить процедуры сортировки и поиска.
6.Результаты:
- исходные данные;
- отсортированные данные;
- выходная таблица.
7. Выводы.
Реализация на любом языке. В-принципе все сделаю сам. В тупик поставил лишь метод поиска.
Мой вариант - 20
Не могу найти информацию относительно "поиска по близости к заданному значению ключа".
Курс: “ Структуры и организация данных в ЭВМ ”
Контрольная работа № 1
Тема: ” Методы сортировки и поиска в таблице по заданному ключу”.
Варианты заданий
1.Сравнительный анализ линейного выбора с подсчетом и метода Шелла. Поиск с барьером.
.....................................
20.По близости к заданному значению ключа. Сортировка методом «пузырька» и двухпутевого слияния.
...................................
40. Сортировка таблицы комбинированием методов “быстрой сортировки” и вставки (метод вставка рекомендуется использовать для таблиц длиной<=9). Поиск по совпадению ключа при наличии нескольких элементов с одинаковым значением ключа.
Пояснения к выполнению контрольной работы
1.Выбор предметной области. Для заданной предметной области создать таблицу с исходными данными. Таблица должна иметь не менее трех полей (одно поле - ключевое) и содержать не мение 15 записей.
2.Формирование данных таблицы. Ввод исходных данных должен быть реализован как с клавиатуры, так из файла.
3.Сортировка таблицы. Используя теоретические данные по заданному методу сортировки, согласно варианта, разработать программу и выполнить упорядочение данных. Экспериментальные данные по методам сортировки должны быть полученные по исходным данным, которые должны быть подготовленные в трех вариантах:
- исходные данные находятся в произвольном виде (не упорядоченные);
- исходные данные упорядоченные;
- исходные данные упорядоченные в обратном порядке;
4.Сравнительный анализ. Теоретические и экспериментальные данные и результаты сравнения различных методов сортировки должны быть представлены в виде таблицы по следующей форме:
- метод сортировки;
- количество сравнений;
- количество обменов;
- резерв памяти.
Выходная таблица формируется в файл и на печать.
5. Поиск в таблице. Разработать программу поиска для заданного ключевого поля.
Отчет должен содержать
1.Задание по контрольной работе.
2.Теоретические данные по заданным методам.
3.Ручной просчет.
4.Экспериментальные данные.
5.Листинг программы. Выделить процедуры сортировки и поиска.
6.Результаты:
- исходные данные;
- отсортированные данные;
- выходная таблица.
7. Выводы.
Реализация на любом языке. В-принципе все сделаю сам. В тупик поставил лишь метод поиска.