Указатели на константы и константные указатели
Константный указатель - адрес в памяти, где хранится это число. Адрес в памяти постоянен, и такой указатель указывает, всегда на одну и ту же ячейку памяти, а содержимое этой ячейки может меняться.
Указатель на константу - адрес в памяти, где хранится элемент. Адрес, где хранится этот элемент, может изменяться, а содержимое этой ячейки - нет.
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 )
{
register int i, j;
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 )
{
register int i, j;
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 )
{
register int i, j, k; int temp;
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; // элемент не найден