Понятии указателя

Указатели

Поиск в отсортированном массиве

В отсортированном массиве используется дихотомический (бинарный) поиск. При последовательном поиске требуется в среднем n/2 сравнений, где n – количество элементов в массиве. При дихотомическом поиске требуется не более m сравнений, если n- m-ая степень 2, если n не является степенью 2, то n<k=2^m.

Массив делится пополам S:=(L+R)/ 2+1 и определяется в какой части массива находится нужный элемент Х. Т.к. массив упорядочен, то если a[S]<X, то искомый элемент находится в правой части массива, иначе - находится в левой части. Выбранную часть массива снова надо разделить пополам и т. д., до тех пор, пока границы отрезка L и R не станут равны.

L S R

S=(L+R)/2=4

int b;

cout<<"\nB=?";cin>>b;

int l=0,r=n-1,s;

do

{

s=(l+r)/2;//средний элемент

if(a[s]<b)l=s+1;//перенести леую границу

else r=s;//перенести правую границу

}while(l!=r);

if(a[l]==b)return l;

else return -1;

Указатели являются специальными объектами в программах на Си++. Указатели предназначены для хранения адресов памяти.

Пример: Когда компилятор обрабатывает оператор определения переменной, например, int i=10;, то в памяти выделяется участок памяти в соответствии с типом переменной (int=> 4байта) и записывает в этот участок указанное значение. Все обращения к этой переменной компилятор заменит на адрес области памяти, в которой хранится эта переменная.

а

		&a

Программист может определить собственные переменные для хранения адресов областей памяти. Такие переменные называются указателями. Указатель не является самостоятельным типом, он всегда связан с каким-то другим типом.

Указатели делятся на две категории: указатели на объекты и указатели на функции. Рассмотрим указатели на объекты, которые хранят адрес области памяти, содержащей данные определенного типа.

В простейшем случае объявление указателя имеет вид:

тип *имя;

Тип может быть любым, кроме ссылки.

Примеры:

int *i;

double *f, *ff;

char *c;

Размер указателя зависит от модели памяти. Можно определить указатель на указатель: int**a;

Указатель может быть константой или переменной, а также указывать на константу или переменную.

Примеры:

1. int i; //целая переменная

const int ci=1; //целая константа

int *pi; //указатель на целую переменную

const int *pci;//указатель на целую константу

Указатель можно сразу проинициализировать:

int *pi=&i; //указатель на целую переменную

const int *pci=&ci;;//указатель на целую константу

2. int*const cpi=&i;//указатель-константа на целую переменную

const int* const cpc=&ci;//указатель-константа на целую константу

Если модификатор const относится к указателю (т. е. находится между именем указателя и *), то он запрещает изменение указателя, а если он находится слева от типа (т. е. слева от *), то он запрещает изменение значения, на которое указывает указатель.

Для инициализации указателя существуют следующие способы:

1)

a   *p     *r &a

Присваивание адреса существующего объекта:

1) с помощью операции получения адреса

int a=5;

int *p=&a; или int p(&a);

2) с помощью проинициализированного указателя

int *r=p;

3) адрес присваивается в явном виде

char*cp=(char*)0х В800 0000;

где 0х В800 0000 – шестнадцатеричная константа, (char*) – операция приведения типа.

4) присваивание пустого значения:

int*N=NULL;

int *R=0;

Дата добавления: 2014-01-04