Функция

@xexew · Регистрация: 22.02.2011

Author24 — интернет-сервис помощи студентам

C++

// binary_search_with_fun.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
 
using namespace std;
 
int *Bin_Srch(int *first, int *last, int key)
{
    int l=first;
    int u=last-1;   
while (l <= u) 
    {
        int m = (l + u) / 2;
        if (*(first+m) == key) return m;
            if (*(first+m) < key) l = m + 1;
                if (*(first+m) > key) u = m - 1;
    }
    
}
 
int _tmain(int argc, _TCHAR* argv[])
{   setlocale(0,"");
    int arr[5]={1, 2, 3, 4, 5};
    int key;
    cout << "Число: \n";
    cin >> key;
    
    cout << endl << Bin_Srch(arr,arr+5,2);
    return 0;
}

Будьте добры, помогите понять принцип функций в целом, в каком случае требуется ставить указатель "*", а в каком нет.
Программа на двоичный поиск, как правильно осуществить функцию этого поиска?

Можете подкинуть статьи по функциям и указателям, ато в нете куча этих статей?)

@Dani · 15.10.2011, 00:40

можете посмотреть стандартную реализацию в библиотеке algorithm.

@talis · 15.10.2011, 01:26

Сообщение от xexew

Можете подкинуть статьи по функциям и указателям, ато в нете куча этих статей?)

xexew, почитайте лучше книжки. На форуме была прикреплённая тема со списком хорошей литературы.

Сообщение от xexew

Будьте добры, помогите понять принцип функций в целом, в каком случае требуется ставить указатель "*", а в каком нет.

Функция - это, грубо говоря, программа в программе. Подпрограмма. Часто выполняемые действия обычно выносят в функции, чтобы не писать по десять раз. Функция может принимать аргументы (параметры по-другому) и возвращать значение. Синтаксис такой:

тип_возвращаемого_значения имя ( тип_параметра_1 параметр_1, тип_параметра_2 параметр_2, ... )
{

тело_функции

}

Пример:

int add( int a, int b )
{

return a + b;

}

Функция add принимает два параметра типа int и возвращающая значение типа int, которое является суммой её параметров. То есть, когда я пишу

int c = add( 5, 8 );

Вызывается функция add, в первый параметр попадает число 5, во второй - 8. Значение, которое вернёт функция, 13, запишется в int c.

Указатель - переменная, хранящая адрес начала чего-либо. Синтаксис объявления указателя на объект:

тип_объекта * имя_указателя;

Пример:

char * alpha;

Указатель alpha на начало объекта (или последовательности объектов) типа char.

Если указатель указывает на элемент массива, то для перехода к следующему элементу нужно выполнить инкремент указателя, а для перехода к предыдущему элементу - декремент указателя:

alpha++;
alpha--;

Так же можно производить доступ через operator[]:

alpha[5];

Чтобы взять значение, на которое указывает указатель, нужно его разименовать:

C

char * alpha = "Hello"; // alpha указывает на начало массива char
char c = *alpha; // c == 'H'
alpha++;
c = *alpha; // c == 'e'

Или получить доступ по индексу:

C

1 2	char * alpha = "Hello"; // alpha указывает на начало массива char char c = alpha[4]; // c == 'o'

Для взятия адреса объекта используется операция взятия адреса объекта:

C

1
2
3

int a = 18;
int * ptr = &a; // взятие адреса a и запись его в указатель ptr
int b = *ptr; // разыменовывание указателя ptr и запись значения по указателю в b; b == 18

При создании указателя на массив операция взятия адреса не требуется, так как идентификатор (имя) массива эквивалентно указателю на начало массива:

C

1 2	int a[16]; int * ptr = a;

При передачи больших объектов и массивов в функцию предпочтительна передача по указателю, так как в этом случае функция примет 4 байта указателя вместо огромного объекта или массива:

C

int lng( char * str ); // функция принимает указатель на char
 
//...
 
printf( "%d", lng( "hello" ) ); // передача указателя на начало строки hello в функцию lng;
                          // значение, возвращённое функцией lng передаётся в функцию printf

Есть ещё указатели на функцию. Будет интересно подробнее узнать про всё это - найдёте книжки и почитаете.

silent_1991 · 15.10.2011, 14:46

Не по теме:

Сообщение от talis

аргументы (параметры по-другому)

Небольшое исправление:
Обычно то, что стоит в прототипе функции называют параметрами, а то, что фактически передаётся при вызове функции - аргументами.

@xexew · 15.10.2011, 20:38 **[ТС]**

C++

int *Bin_Srch(int *first, int *last, int key)
{
    int l=*first;
    int u=*last-1;  
while (l <= u) 
    {
        int m = (l + u) / 2;
        if (*(first+m) == key) return m;
            if (*(first+m) < key) l = m + 1;
                if (*(first+m) > key) u = m - 1;
    }
    return -1;
}
 
int _tmain(int argc, _TCHAR* argv[])
{   setlocale(0,"");
    int arr[5]={1, 2, 3, 4, 5};
    int key;
    cout << "Число: \n";
    cin >> key;
    int *p=Bin_Srch(arr,arr+5,key);
    cout << p <<" "; 
    return 0;
}

подскажите, почему функция не может вернуть значение -1?

@Net_Wanderer · 15.10.2011, 20:47

Сообщение от xexew

подскажите, почему функция не может вернуть значение -1?

C++

1	int u=*last-1;

Оператор разыменования имеет больший приоритет чем оператор -
иными словами, этот код эквивалентен следующему:

C++

1	int u=(*last)-1;

по этому что бы получить ожидаемый результат нужно написать так:

C

1	int u = *(last - 1);

@xexew · 15.10.2011, 20:55 **[ТС]**

спасибо, но он все равно пишет что не может конвертировать из 'int' в 'int *', ссылаясь на строку, где написано

C++

return -1

@Net_Wanderer · 15.10.2011, 20:58

Сообщение от xexew

спасибо, но он все равно пишет что не может конвертировать из 'int' в 'int *', ссылаясь на строку, где написано

C++

return -1

Да, потому что функция объявлена, как возвращающая указатель, а вы пытаетесь вернуть просто число (int)
Возвращайте тогда нулевой указатель, чтобы сигнализировать о том что элемент не найден:

C++

1	return NULL;

@xexew · 15.10.2011, 21:37 **[ТС]**

C++

int *Bin_Srch(int *first, int *last, int key)
{
    int l=*first;
    int u=*(last-1);    
while (l <= u) 
    {
        int m = (l + u) / 2;
        if (*(first+m) == key) key=*(first+m);
            if (*(first+m) < key) l = m + 1;
                if (*(first+m) > key) u = m - 1;
    }
    return NULL;
}
 
int _tmain(int argc, _TCHAR* argv[])
{   setlocale(0,"");
    int arr[5]={1, 2, 3, 4, 5};
    int key;
    cout << "Число: \n";
    cin >> key;
    int *p=Bin_Srch(arr,arr+5,key);
    cout << p <<" "; 
    return 0;
}

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

@Net_Wanderer · 15.10.2011, 21:46

Сообщение от xexew

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

А где у вас оператор return на тот случай если элемент найден?

@aeshes · 15.10.2011, 21:47

А она у вас всегда NULL возвращает, других-то return-ов нет

@Net_Wanderer · 15.10.2011, 21:48

вот написал:

C

int *binsearch(int *first, int *last, int key)
{
    int *mid;
 
    while (first < last) {
        mid = first + (last-first) / 2;
        if (*mid > key)
            last = mid;
        else if (*mid < key)
            first = mid + 1;
        else
            return mid;
    }
    return NULL;
}

изучайте...

@xexew · 15.10.2011, 21:51 **[ТС]**

ох..большое спасибо за решение)

@xexew · 17.10.2011, 23:48 **[ТС]**

C++

// binary_search_with_fun.cpp : Defines the entry point for the console application.
//
 
int *binsearch(int *first, int *last, int key)
{
        int* mid;
        int* p=last; 
        while (first < last) {
                mid = first + (last-first) / 2;
                if (*mid == key) return mid;        
                if (*mid < key) last = mid + 1;
                if (*mid > key) first = mid - 1;
                        return mid;
        }
        return p;
}
 
int _tmain(int argc, _TCHAR* argv[])
{   setlocale(0,"");
    int arr[5]={1,5,4,3,2};
    int* q=binsearch(arr,arr+5,2);
    cout << "\nИндекс: " << q-arr << endl; 
    return 0;
}

посмотрите пожалуйста "свежим" взглядом, где ошибка? не правильно возвращает значение, может в цикле что-то не то?

@talis · 18.10.2011, 00:46

Сообщение от xexew

int arr[5]={1,5,4,3,2};

xexew, условие для бинарного поиска - отсортированный массив. Иначе будет работать с ошибками. Сами подумайте:

Код

берём середину интервала
если ключ меньше значения
   ищем в левой части
если ключ больше значения
   ищем в правой части
если ключ равен значению
   возвращаем адрес найденного элемента
если границы поиска стоят впритык друг к другу или вообще пересеклись
   возвращаем, что значения нет в массиве

повторить

@Dani 1405 / 647 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	15.10.2011, 00:40	2
	можете посмотреть стандартную реализацию в библиотеке algorithm. 0

silent_1991
	15.10.2011, 14:46 #4
	Не по теме: Сообщение от talis аргументы (параметры по-другому) Небольшое исправление: Обычно то, что стоит в прототипе функции называют параметрами, а то, что фактически передаётся при вызове функции - аргументами. 1

@Net_Wanderer 237 / 210 / 29 Регистрация: 08.06.2011 Сообщений: 467
	15.10.2011, 21:46	10
	Сообщение от xexew Программа запускается, но после прочтения числа просто бездействует, что может быть не так? А где у вас оператор return на тот случай если элемент найден? 0

@aeshes 448 / 211 / 21 Регистрация: 07.10.2011 Сообщений: 462
	15.10.2011, 21:47	11
	А она у вас всегда NULL возвращает, других-то return-ов нет 0

@xexew 0 / 0 / 2 Регистрация: 22.02.2011 Сообщений: 76
	15.10.2011, 21:51 [ТС]	13
	ох..большое спасибо за решение) 0

Функция

Решение