Указатели на константы и константные указатели

Константный указатель - адрес в памяти, где хранится это число. Адрес в памяти постоянен, и такой указатель указывает, всегда на одну и ту же ячейку памяти, а содержимое этой ячейки может меняться.

Указатель на константу - адрес в памяти, где хранится элемент. Адрес, где хранится этот элемент, может изменяться, а содержимое этой ячейки - нет.

char*p;
chars[] = 'Ci++';
const char* pc = s; //указатель на константу

pc[3] = 'g’;
// ошибка: рс указывает на константу

рс = р; // правильно

char *const cp = s; // констант-й указатель
ср[3] = 'а, //правильно
ср = р; //ошибка: ср - константа

const char *const cpc = s;
// константный указатель на константу

срс[3] = 'а'; ошибка: срс указывает на константу
срс=р; //ошибка: срс является константой

Указатели на функции.

Имя функции является адресом этой функции в памяти.

Язык программирования Си позволяет определять указатели на функции. Например, следующая инструкция
int (*fp)(int x, int y);

Пример
int add(int x, int y)
{ return x + y;}
int sub(int x, int y)
{ return x - y;}

void main()
{
int (*p)(int, int);
p = add;
/* вызываем функцию через указатель */
printf("1 + 2 = %d\n", (*p)(1, 2));
p = sub;
/* можно вызвать функцию и так */
printf("1 - 2 = %d\n", p(1, 2));
return 0;

}

12.9. Указатель на void
Существует указатель на объект любого типа: void* имя; Действия с указателем:
· переменной типа void* можно присвоить указатель на объект любого типа;

· void* нельзя разыменовывать.

· void* можно явно преобразовать в указатель на другой тип.

· один void* можно присвоить другому void*;
· пару void* можно сравнивать на равенство и неравенство;
· нельзя изменять void* (размер объекта неизвестен)

Основными применениями void* являются:
-передача указателей функциям, которым не позволено делать предположения о типе объектов
-возврат объектов «неуточненного типа» из функций.

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

Алгоритмы преобразование и перестановки .

void swaptmp(int *px, int *py) /* перестановка *px и *py */
{
// Обмен чисел
int temp;
temp = *px;
*px = *py;
*py = temp;
}

void swap(int *px, int *py)
/* перестановка *px и *py */
{
// Обмен чисел
*px ^= *py;
*py ^= *px;
*px ^= *py;
}

int* Revers(int *a, int n)
// Переворачивание элементов массива
{
int k;
for (int i=0;i<n/2;i++)
{
k=a[i];
a[i]=a[n-i-1];
a[n-i-1]=k;
}
return a;}

int* ReversP(int *a,int n)
{
int k;
for (int i=0;i<n/2;i++)
{
k=*(a+i);
*(a+i)=*(a+n-i-1);
*(a+n-i-1)=k;
}
return a;
}

int* ReversL(int *a,int n)
{
for (int i=0;i<n/2;i++)
{
*(a+i)^=*(a+n-i-1);
*(a+n-i-1)^=*(a+i);
*(a+i)^=*(a+n-i-1);
}
return a;
}

Алгоритмы расширение и сжатие массивов

При обработке массивов можно вставлять и удалять элементы
void MoveRight(int * a, int n, int num)
{ //сдвигает все элементы на одну позицию вправо до номера num
for (int i=n; i>=(num+1); i--)
a[i]=a[i-1];
}

void MoveLeft(int * a,int *n, int num)
{ //сдвигает все элементы на одну позицию влево c номера num
for (int i=num; i<*n-1; i++)
a[i]=a[i+1];
*n=*n-1;
}

int* DeleteCh(int *a,int *n, int item)

{

int i=0;

while (i<*n)

{

if (a[i]==item)

{

MoveLeft(a, n, i);

//Сдвигаем и удаляем элемент a=(int*)realloc(a,(*n)*sizeof(int));

i-- ;

}

i++;

}

return a;}

int* InsertCh(int *a,int *n)

{ int i=0;

while (i<*n)

{

if (a[i]%2==0)

{

a=(int *)realloc(a,(*n+1)*sizeof(int));

MoveRight(a,(*n)++,i+1); //Сдвигаем и добавляем элемент

a[i+1]=a[i];

i++ ;

}

i++;

}

return a;

}

Сортировка пузырьком

Мы будем просматривать весь массив "снизу вверх" и менять стоящие рядом элементы в том случае, если "нижний" элемент меньше, чем "верхний". Таким образом, мы вытолкнем наверх самый "легкий" элемент всего массива. Теперь повторим всю операцию для оставшихся неотсортироваными N-1 элементов (т.е. для тех, которые лежат "ниже" первого. Как видно, алгоритм достаточно прост, но, как иногда замечают, он является непревзойденным в своей неэффективности.

void sort( int *array, int size )

{

int temp;

for( i = size - 1; i > 0; i-- )

{

for( j = 0; j < i; j++ )

{

if( array[j] > array[j+1] )

{

temp = array[j];

array[j] = array[j+1];

array[j+1] = temp;

}

return; }

Сортировка Вставками

Будем разбирать алгоритм, рассматривая его действия на i-м шаге. Как говорилось выше, последовательность к этому моменту разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n].

На следующем, (i+1)-м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива.

Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним.

В зависимости от результата сравнения элемент либо остается на текущем месте(вставка завершена), либо они меняются местами и процесс повторяется.

void sort( int *array, int size )

{

int temp;

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

{

temp = array[i];

for ( j = i - 1; j >= 0; j--)

{

if( array[j] < temp )

break;

array[j+1] = array[j];

}

array[j+1] = temp; }}

Сортировка выбором

На этот раз при просмотре мaccива мы будем искать наименьший элемент, сравнивая его с первым. Если такой элемент

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

в первую позицию в таблице. Затем повторим эту операцию, но начнем не с первого элемента, а со второго. И будем продолжать

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

void sort( int *array, int size )

{

for( i = 0, k = 0; i < size - 1; i++, k++ )

{

temp = array[i];

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

{

if( temp > array[j] )

{

temp = array[j];

k = j;

}

temp = array[i];

array[i] = array[k];

array[k] = temp; }

return; }

Линейный поиск

Линейный, последовательный поиск — нахождения заданного

элемента в некотором массиве. Поиск значения осуществляется простым сравнением очередного значения и искомого, если значения совпадают, то поиск считается завершённым. Если у массива длина = N, найти решение можно за N шагов. Сложность алгоритма - O(n). В связи с малой эффективностью линейный поиск используют только

если N не большое.

1. Определяем начало интервала поиска и выбираем элемент для поиска.

2. Cравниваем образец с выбранным элементом.

Если элемент совпадает с образцом, то определяем его индекс и переходим к шагу 4.

3. Если элемент не совпадает с образцом, то выбираем следующий, если он есть и переходим к шагу 2.

4. Если индекс определен, то элемент найден, иначе - искомого элемента в массиве нет.

int LineSearch (int *a, int n, int x)

{
for (int i = 0;i<n; i++)

if (a[i] == x)

return i;

return -1; // элемент не найден