Предположим, что массив х и искомый объект t принадлежат к одному типу — DataType. Тип этот можно будет определить оператором typedef:
typedef int DataType
Таким образом можно определить и длинное целое вещественное число с плавающей точкой и любой другой тип. Массив реализуется с помощью двух глобальных переменных:
1 nt п .
DataType х[МАХ N]
Несмотря на то что это «дурной тон» программирования для языка С, он соответствует способу доступа к данным в классах C++; кроме того, глобальные переменные позволяют уменьшить объем тестовой программы. Итак, мы должны получить функцию на языке С, отвечающую следующим требованиям;
1nt biпаrysearch(DataType t)
/* precondition x[0]<=x[1]<= ,<=x[n-l] postcondition
result == -1 => элемент t в пассиве x отсутствует
0 <= result < n => x[resul] == t*/
Большая часть операторов на псевдокоде (см., например, листинг 4.3) непосредственно переводятся на язык С строчка за строчкой (как и на большинство других языков). Когда программа на псевдокоде помещает значение в переменную р, функция на С будет возвращать это значение оператором return. Оператор loop па псевдокоде заменяется бесконечным циклом на С. В результате получаем следующий код:
for (..) {
if (1 > u)
return -1.
/* и так далее */}
Мы можем переделать это в цикл «пока» (while), изменив условие проверки:
wh11е (1< = и ) {
/* тело цикла */}
В итоге получим законченный вариант нашей функции двоичного поиска на языке С (листинг 5.1).
Листинг 5.1. Функция двоичного поиска на языке С
mt biпаrysearch(DataType t)
/* возвращает любое вхождение t в отсортированный массив х[0 п-1]
либо -1 в случае отсутствия вхождений */
{ 1nt 1. u. m.
1 = 0.
u = п -1 ,
while П <= u) { m - (1 + u)/2, if (x[m]<t)
1= m+1; else if ( х[т]=^) return m. else /* x[m]>t */ u = m-1,}
return -1,
Опубликовал vovan666
April 16 2013 23:58:27 ·
0 Комментариев ·
4853 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
