Сортировка методом простого включения (вставки)

       Элементы массива делятся на уже готовую последовательность и исходную. При каждом шаге, начиная с I=2, из исходной последовательности извлекается I-ый элемент и вставляется на нужное место готовой последовательности, затем I увеличивается на 1 и т. д.

44	55	12	42	94	18
готовая	исходная

 

В процессе поиска нужного места осуществляются пересылки элементов больше выбранного на одну позицию вправо, т. е. выбранный элемент сравнивают с очередным элементом отсортированной части, начиная с J:=I-1. Если выбранный элемент больше a[I], то его включают в отсортированную часть, в противном случае a[J] сдвигают на одну позицию, а выбранный элемент сравнивают со следующим элементом отсортированной последовательности. Процесс поиска подходящего места заканчивается при двух различных условиях:

- если найден элемент a[J]>a[I];

- достигнут левый конец готовой последовательности.

 

int i,j,x;

for(i=1;i<n;i++)

{

x=a[i];//запомнили элемент, который будем вставлять

j=i-1;

while(x<a[j]&&j>=0)//поиск подходящего места

{

a[j+1]=a[j];//сдвиг вправо

             j--;

}

a[j+1]=x;//вставка элемента

}

 

Сортировка методом простого выбора

Выбирается минимальный элемент массива и меняется местами с первым элементом массива. Затем процесс повторяется с оставшимися элементами и т. д.

44	55	12	42	94	18
1		мин

 

int i,min,n_min,j;

for(i=0;i<n-1;i++)

{

             min=a[i];n_min=i;//поиск минимального

             for(j=i+1;j<n;j++)

                        if(a[j]<min){min=a[j];n_min=j;}

                        a[n_min]=a[i];//обмен

                        a[i]=min;

}

 

Сортировка методом простого обмена

Сравниваются и меняются местами пары элементов, начиная с последнего. В результате самый маленький элемент массива оказывается самым левым элементом массива. Процесс повторяется с оставшимися элементами массива.

44	55	12	42	94	18

 

for(int i=1;i<n;i++)

for(int j=n-1;j>=i;j--)

if(a[j]<a[j-1])

{int r=a[j];a[j]=a[j-1];a[j-1]=r;}

}

 

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

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

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

1	3	8	10	11	15	19	21	23	37
0	1	2	3	4	5	6	7	8	9

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байта) и записывает в этот участок указанное значение. Все обращения к этой переменной компилятор заменит на адрес области памяти, в которой хранится эта переменная.

	10

а

			&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

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

5

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;

 

Динамические переменные

Все переменные, объявленные в программе размещаются в одной непрерывной области памяти, которую называют сегментом данных (64К). Такие переменные не меняют своего размера в ходе выполнения программы и называются статическими. Размера сегмента данных может быть недостаточно для размещения больших массивов информации. Выходом из этой ситуации является использование динамической памяти. Динамическая память – это память, выделяемая программе для ее работы за вычетом сегмента данных, стека, в котором размещаются локальные переменные подпрограмм и собственно тела программы.

Для работы с динамической памятью используют указатели. С их помощью осуществляется доступ к участкам динамической памяти, которые называются динамическими переменными. Динамические переменные создаются с помощью специальных функций и операций. Они существуют либо до конца работы программ, либо до тех пор, пока не будут уничтожены с помощью специальных функций или операций.

Для создания динамических переменных используют операцию new, определенную в СИ++:

указатель = new имя_типа[инициализатор];

где инициализатор – выражение в круглых скобках.

Операция new позволяет выделить и сделать доступным участок динамической памяти, который соответствует заданному типу данных. Если задан инициализатор, то в этот участок будет занесено значение, указанное в инициализаторе.

int*x=new int(5);

Для удаления динамических переменных используется операция delete, определенная в СИ++:

delete указатель;

где указатель содержит адрес участка памяти, ранее выделенный с помощью операции new.

delete x;

В языке Си определены библиотечные функции для работы с динамической памятью, они находятся в библиотеке <stdlib.h>:

1) void*malloc(unsigned s) – возвращает указатель на начало области динамической памяти длиной s байт, при неудачном завершении возвращает NULL;

2) void*calloc(unsigned n, unsigned m) – возвращает указатель на начало области динамической для размещения n элементов длиной m байт каждый, при неудачном завершении возвращает NULL;

3) void*realloc(void *p,unsigned s) –изменяет размер блока ранее выделенной динамической до размера s байт, р – адрес начала изменяемого блока, при неудачном завершении возвращает NULL;

4) void *free(void *p) – освобождает ранее выделенный участок динамической памяти, р- адрес начала участка.

Пример:

int *u=(int*)malloc(sizeof(int)); // в функцию передается количество требуемой памяти в байтах, т. к. функция возвращает значение типа void*, то его необходимо преобразовать к типу указателя (int*).

free(u); //освобождение выделенной памяти

 

 

Операции с указателями

С указателями можно выполнять следующие операции:

1) разыменование (*);

2) присваивание;

3) арифметические операции (сложение с константой, вычитание,
 инкремент ++, декремент --);

4) сравнение;

5) приведение типов.

1) Операция разыменования предназначена для получения значения переменной или константы, адрес которой хранится в указателе. Если указатель указывает на переменную, то это значение можно изменять, также используя операцию разыменования.

Примеры:

int a; //переменная типа int

int*pa=new int; //указатель и выделение памяти под динамическую переменную

*pa=10;//присвоили значение динамической переменной, на которую указывает указатель

a=*pa;//присвоили значение переменной а

Присваивать значение указателям-константам запрещено.

2) Приведение типов

На одну и ту же область памяти могут ссылаться указатели разного типа. Если применить к ним операцию разыменования, то получатся разные результаты.

int a=123;

int*pi=&a;

char*pc=(char*)&a;

float *pf=(float*)&a;

printf("\n%x\t%i",pi,*pi);

printf("\n%x\t%c",pc,*pc);

printf("\n%x\t%f",pf,*pf);

При выполнении этой программы получатся следующие результаты:

66fd9c 123

66fd9c {

66fd9c 0.000000

Т. е. адрес у трех указателей один и тот же, но при разыменовании получаются разные значения в зависимости от типа указателя.

В примере при инициализации указателя была использована операция приведения типов. При использовании в выражении указателей разных типов, явное преобразование требуется для всех типов, кроме void*. Указатель может неявно преобразовываться в значения типа bool, при этом ненулевой указатель преобразуется в true, а нулевой в false.

3) Арифметические операции применимы только к указателям одного типа.

- Инкремент увеличивает значение указателя на величину sizeof(тип).

Например:

char *pc;

int *pi;

float *pf;

.....

pc++;//значение увеличится на 1

pi++;//значение увеличится на 4

pf++;//значение увеличится на 4

-  Декремент уменьшает значение указателя на величину sizeof(тип).

- Разность двух указателей – это разность их значений, деленная на размер типа в байтах.

Например:

int a=123,b=456,c=789;

int*pi1=&a;

int *pi2=&b;

int*pi3=&c;

printf("\n%x",pi1-pi2);

printf("\n%x",pi1-pi3);

Результат

1

2

Суммирование двух указателей не допускается.

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

pi3=pi3+2;

pi2=pi2+1;

printf("\n%x\t%d",pi1,*pi1);

printf("\n%x\t%d",pi2,*pi2);

printf("\n%x\t%d",pi3,*pi3);

Результат выполнения программы:

66fd9c 123

66fd9c 123

66fd9c 123

При записи выражений с указателями требуется обращать внимание на приоритеты операций.

 

Ссылки

Понятие ссылки

Ссылка – это синоним имени объекта, указанного при инициализации ссылки.

Формат объявления ссылки

тип & имя =имя_объекта;

Примеры:

int x;// определение переменной

int& sx=x;// определение ссылки на переменную х

const char& CR=’\n’;//определение ссылки на константу

8.1. Правила работы со ссылками:

1) Переменная ссылка должна явно инициализироваться при ее описании, если она не является параметром функции, не описана как extern или не ссылается на поле класса.

2) После инициализации ссылке не может быть присвоено другое значение.

3) Не существует указателей на ссылки, массивов ссылок и ссылок на ссылки.

4) Операция над ссылкой приводит к изменению величины на которую она ссылается

Ссылка не занимает дополнительного пространства в памяти, она является просто другим именем объекта.

Пример1:

#include <iostream.h>

void main()

{

int I=123;

int &si=I;

cout<<”\ni=”<<I<<” si=”<<si;

I=456;

cout<<”\ni=”<<I<<” si=”<<si;

I=0; cout<<”\ni=”<<I<<” si=”<<si;

}

 

Выведется

I=123 si=123

I=456 si=456

I=0 si=0

Указатели и массивы