Не типизированные указатели.

Пусть имеем описание:

var
p1: ^Char;
p2: ^Boolean;
pp: Pointer; {нетипизированный указатель}
Присваивание значения одного указателя другому возможно только между указателями объектов идентичного типа. Например, нельзя записать:
p1:= p2; {ошибка!}

Нетипизированный указатель совместим по присваиванию с указателем любого типа. Поэтому можно сделать присваивание между p1 и p2 опосредованно:

pp:= p2;
p1:= pp;

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

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

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

§ Определение адреса указателя: &p, где p – указатель (&p – адрес ячейки, в которой находится указатель).

§ Присваивание. Указателю можно присвоить адрес переменной p=&q, где p – указатель, q – идентификатор переменной.

§ Определение значения, на которое ссылается указатель: *p (операция косвенной адресации).

§ Увеличение (уменьшение) указателя. Увеличение выполняется как с помощью операции сложения (+), так и с помощью операции инкремента (++). Уменьшение – с помощью операции вычитания (–) либо декремента (––).

Например, пусть p1 – указатель, тогда р1++ перемещает указатель на:

o 1 байт, если *p1 имеет тип char;

o 4 байта, если *p1 имеет тип int (в 32 разрядной операционной системе) или 2 байта (в 16 разрядной операционной системе);

o 4 байта, если *p1 имеет тип float.

§ Разность двух указателей. Пусть р1 и р2 – указатели одного и того же типа. Можно определить разность р1 и р2, чтобы найти, на каком расстоянии друг от друга находятся элементы массива.

Пример программы.

Даны адреса переменных &a=63384,&b=64390,&c=64404. Что напечатает ЭВМ?

#include<stdio.h>

intmain()

{

floata,*p1;

intb,*p2;

charc,*p3;

a=2.5;b=3;c='A';

p1=&a;p2=&b; p3=&c;

p1++;p2++;p3++;

printf("\np1=%u,p2=%u,p3=%u",p1,p2,p3);

return0;

}

Ответ: р1=63388,р2=64392,р3=64405.

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

Применительно к указателям на объект типа char операции адресной арифметики выполняются как обычные арифметические операции, потому что длина объекта char всегда равна 1.

Операции адресной арифметики не ограничены увеличением (инкрементом) и уменьшением (декрементом). К указателям, например, можно добавлять или вычитать из них целые числа.

При операции вычитания двух указателей можно определить количество объектов, расположенных между адресами, на которые указывают эти два указателя. При этом необходимо, чтобы указатели имели один и тот же тип. Кроме того, стандартом C допускается сравнение двух указателей. Как правило, сравнение указателей может оказаться полезным только тогда, когда два указателя ссылаются на общий объект, например, на массив.

Все остальные операции над указателями запрещены.

Выделение и освобождение динамической памяти. ПроцедурыNew, Dispose, Mark, Release

New(p)

p – типизированный указатель

работа:

1) Указатель р получает конкретное значение адреса

2) В куче по указанному адресу указывается размер памяти, размер которой определяется типом памяти

Наиболее типичная ошибка – задание значения ссылочной переменной без предварительного выделения памяти

При выделении памяти указатель heapptrможет переместиться, а может и остаться на месте.

Выделения памяти происходит так: просматривается память с начала кучи, в ней ищется фрагмент памяти подходящего размера. Если он найден, то он и выделяется, если нет – память выделяется на heapptr

Dispose(p)

p – типиз. Указатель

disposeиспользуется для возврата памяти в кучу. При этом значение соответствующего фрагмента памяти не меняется; этот фрагмент помещается в список свободных, которые можно распределять.

Повторное применение процедуры к “свободному” указателю приводит к ошибке при исполнении.

Mark(p)

p – нетипизированный указатель

Процедура markиспользуется чтобы отметить значение переменной указателя p.

С помощью markпамять не выделяется, heapptrне меняет своего значения.

Release(p)

p – нетипиз.указатель.

releaseосвобождает место памяти от адреса р до конца кучи.

Механизмыработыdispose, markиrelease– различны. В одной проге следует использовать их с осторожностью.

Процедуры для работы с нетипизированными указателями Getmem, Freemem.

Getmem(p,size) – выделение памяти размера sizeв байтах начиная с адреса р.

Freemem(p,size)– освобождает память от адреса р размером size.

Освобождать следует столько сколько было выделено и с ножного адреса, иначе возможны трудно обнаруживаемые ошибки.

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

1) Метод прямого включения

Дан массив a[1..n], x-буферная переменная. Во время сортировки массив делится на 2 части – упорядоченную и неупорядоченную. При каждом шаге с i=2 (Iувеличивается на 1 при каждом проходе цикла) из исходной последовательности (неупорядоченной) извлекается i-тый элемент и перекладывается в нужное место готовой части (упорядоченной). Алгоритм:
для i=2 до nвыполнить
x:=a[i]
включить xна соответствующее место среди a[1]..a[i]

В процессе включения xна нужное место представляет собой цикл из сравнений и обменов соседних элементов. Окончание цикла, если найдено число в массиве, меньшее x, либо xпопал на первое место в массиве. Возможные варианты: 1-внутренний цикл с заданным числом повторений, следовательно, возможны лишние сравнения, можно при этом поставить дополнительную проверку. 2-внутренний цикл с предусловием, которое объединяет оба условия (усложнение процесса). 3-установка барьера a[0]:=x. В этом случае проверяется только одно условие окончания цикла.
2) Метод прямого выбора

Действия:

- выбирается элемент с наименьшим ключом

- обменивается местами с первым элементом

- процесс повторяется с n-1 элементом, потом с n-2 и т.д., пока не останется 1 самый большой элемент.

Алгоритм:

Для i=1 до n-1 выполнить

Присвоить k– индекс наименьшего из a[i]..a[n]

Поменять местами a[i] и a[k].

Данный метод в среднем показывает число перестановок M=O*(n*ln(n)). Данный метод быстрее метода прямого включения.

3) Метод прямого обмена (метод пузырька)

Алгоритм основан на смене мест для пары соседних элементов до упорядочивания.

Алгоритм:

Для i:=2 до n выполнить

Для i:=nдо I (шаг -1) выполнить

Еслиa[j-1]>a[j] то

x:=a[j-1];

a[j-1]:=a[i]
a[j]:=x;

все если

все для

все для

Поиски

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

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

Алгоритм:
a:[0..N-1]

i:=0;

while (i<N) and (a[i]<>x) do i:=i+1;

Возможно улучшение алгоритма установкой барьера.

a:[0..N]
a[N]:=x;

i:=0;

while a[i]<>x do i:=i+1;

2) Двоичный поиск (поиск деления пополам)

Если нет дополнительных сведений о данных, то линейный поиск – единственный вариант. Если данные упорядочить, то поиск можно сделать более эффективным. Поэтому операциям поиска часто предшествует сортировке.

Пусть массив упорядочен по возрастанию, выберем некоторый элемент a_mи сравним с x. Если a_m=x, то поиск заканчивается, если a_m<x, то все элементы с индексами больше mможно исключить, если a_m>x, то все элементы с индексами меньше mможно исключить.

Алгоритм:

L,R

Found: boolean;

L:=0;

R:=N-1;
found:=false;

While (L<=R) and not(found) do

Begin

m:=любое значение между Lи R (желательно средний элемент)

if a[m]:=x then found:=true else

if a[m]<x then L:=m+1 else

R:=m-1;

end;

Для ускорения алгоритма можно отказаться от проверки на совпадение

L,R

L:=0;

R:=N;
While L<R do

Begin

m:= (L+R) div 2;

if a[m]<x then L:=m+1 else

R:=m;

end;

В данном случае условие окончания – L>=R. При L=Rцикл заканчивается, но это не свидетельствует о совпадении. При R=Nсовпадений нет. В других случаях a[R] не участвует в проверке, следовательно, необходимо дополнительно проверить a[R]=x.

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: