![]() |
![]() ![]() |
![]() |
Altair |
![]() ![]()
Сообщение
#1
|
![]() Ищущий истину ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 824 Пол: Мужской Реальное имя: Олег Репутация: ![]() ![]() ![]() |
Содержание:
-------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
Altair |
![]()
Сообщение
#2
|
![]() Ищущий истину ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 824 Пол: Мужской Реальное имя: Олег Репутация: ![]() ![]() ![]() |
Указатель - это переменная, которая в качестве своего значения содержит адрес ячейки памяти.
Указатель связанный с некоторым типом данных, называется типизированным. Для объявления типизированного указателя используется значок ^, который помещается перед типом: var Также можно объявлять указатель, не связывая его при этом с конкретным типом данных. Для этого существует стандартный тип Pointer: var Указатели такого рода называют нетипизированными. Поскольку они не связаны с конкретным типом, то с их помощью удобно размещать динамические данные, структура и тип которых меняются в ходе работы программы: var Казалось бы, а стоило ли вводить ограничения (нельзя присваивать разнотипные указатели), и тут же давать средство для обхода этого ограничения (обмен значений через дополнительную НЕтипизированную переменную)? Стоило !!! Дело в том, что использование обмена через переменную типа Pointer придает языку дополнительную гибкость, но это также требует от программиста дополнительных усилий, и свидетельствует о вполне осознанном действии, а не случайной ошибке. Volvo Динамическая память - это оперативная память ПК, предоставляемая программе при ее работе, за вычетом сегмента данных (64КБ), стека, и тела программы. Вся ДП рассматривается как массив байтов, который называется кучей. Она располагается в старших адресах сразу же за областью памяти, которую занимает тело программы. HEAРORG — начало кучи хранится в этой переменной. HEAPEND — конец кучи. HEAPPTR — текущая граница незанятой динамической памяти. Память под любую динамически размещаемую переменную выделяется процедурой NEW. Параметром обращения к этой процедуре является типизированный указатель. В результате обращения указатель приобретает значение , соответствующее динамическому адресу, начиная с которого можно разместить данные: var После выполнения этого фрагмента указатель i приобретает значение, которое перед этим имел указатель кучи HEAPPTR, а сам HEAPPTR увеличивает свое значение на 2, так как внутреннее представление типа integer, с которым связан указатель i, составляет 2 байта. После того как указатель приобрел некоторое значение, т. е. стал указывать на конкретный физический адрес памяти, по этому адресу можно разместить любое значение соответствующего типа. Для этого сразу за указателем без пробелов ставится значок ^ (указатель разыменовывается), например: i^:=2;{в область памяти i помещено значение 2}. Значением любого указателя является адрес, а чтобы указать что речь идет не об адресе, а о тех данных, которые расположены по этому адресу, за указателем ставится ^. Чтобы вернуть байты обратно в кучу, используется процедура DISPOSE. DISPOSE(i) — возвращает в кучу 2 байта, которые ранее были выделены указателем i. Для работы с нетипизированными указателями используются процедуры: GETMEM(P,SIZE) — резервирование памяти. FREEMEM(P,SIZE) — освобождение памяти. Указательная переменная Р может быть в 3-х состояниях:
В неопределённом состоянии указатель бывает в начале работы программы до первого присвоения ему или конкретного адреса или пустого адреса nil , а также после освобождения области памяти на которую он указывает. Для организации связей между элементами динамических структур данных, требуется чтобы каждый элемента содержал кроме информационных значений, как минимум один указатель. Отсюда следует, что в качестве элементов таких структур необходимо использовать записи, которые могут объединять в одно целое разнородные элементы. Type |
Altair |
![]()
Сообщение
#3
|
![]() Ищущий истину ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 824 Пол: Мужской Реальное имя: Олег Репутация: ![]() ![]() ![]() |
Списки Указатели являются простым механизмом, позволяющим строить данные со сложной и меняющейся структурой. Используя указатели можно создавать и обрабатывать структуры данных, компоненты которых связаны явными ссылками. Самый простой способ связать множество элементов - это расположить их линейно в списке. В этом случае каждый элемент содержит только один указатель на следующий элемент списка. Пусть тип point описан следующим образом: Код Type point = ^item; item = record number: integer; next: point end; Каждая переменная типа point состоит из двух компонентов: индентифицирующего номера и указателя на следующий элемент. Из этих переменных, связав их указателями, можно создать линейный список. Способ построения линейного списка: начиная с пустого списка, последовательно добавлять элементы в его начало. Процесс формирования списка из n элементов: Код First: = nil; {начало с пустого списка} While n>0 do begin New(r); r^.Next:=first; r^.Number:=n; First:=r; n := n-1 end; Основные операции со списками Просмотр списка Процедура, которая выводит на экран значение поля number элементов списка. Код procedure Print (first: point); Var r: point Begin R: = first; While r<>nil do begin Writeln ('number = ' ,r^.Number); R:=r^.Next; end; Поиск в списке Очень частая операция - поиск в списке элементов с заданным значением ключевого поля X. Так же как в случае файлов, поиск ведется последовательно. Он заканчивается либо когда элемент найден, либо когда достигнут конец списка. Код Procedure Search (first: point; x: integer; var q: point); { q - возвращает указатель на найденный элемент; q - nil, если элемента с ключем X в списке нет } var r: point; ok: boolean; begin r: = first; ok: = true; while (r<>nil) and ok do if r^.Number=x then ok:=false else r:=r^.Next; q: = r end; Включить элемент в список Элемент нужно включить в середину списка после элемента, на который указывает ссылка q. Процедура включения записывается следующим образом. Код {включить элемент в середину списка перед q^} Procedure Insert (Var q: point; x: integer); { х - значение информационного поля включаемого элемента } Var r: point; Begin New (r); {размещаем элемент в памяти} R^.Number:=x; {меняем ссылку} r^.next:=q^.Next; q^.Next:=r; end; Если требуется включить перед элементом q^, а не после него, то кажется, что однонаправленная цепочка связей создает трудность, поскольку нет “прохода” к элементам, предшествующим данному. Однако эту проблему можно решить, используя простой прием, который состоит в том, что новый элемент вставляется после q^, но затем происходит обмен значениями между новым элементом и q^. Код {включить элемент в середину списка перед q^} Procedure insert_before (Var q: point; x: integer); Var r: point; Begin New(r); {размещаем элемент памяти} {включаем элемент после q^} r^.Next:=q^.Next; q^.Next:=r; {выполняем обмен значениями} r^.Number:=q^.Number; q^.Number:=x end; Удалить элемент из списка Предположим, что надо удалить элемент, расположенный после элемента, на который указывает ссылка q. Код {удаление элемента из середины списка после q^} Procedure Del (Var q: point); Var r: point; Begin r:=q^.Next; q^.Next:=q^.Next^.next; r^.Next:=nil End; Если следует удалить элемент на который указывается ссылка q, то следует в начале присвоить элементу q^ значение следующего за ним элемента, а затем этот элемент удалить. Код {удаление элемента q^} Procedure Delete(Var q: point); Var r: point; Begin r:=q^.next; q^:=r^; r^.Next:=nil; End; Обратите внимание на то, что удаляемый из списка элемент остается в памяти и к нему имеется доступ к указателю r, так что в дальнейшем этот элемент можно вставить, например, в другой список. Если требуется освободить занимаемую этим элементом память, то следует выполнить: Код { ... } Dispose(r); r:=nil; { ... } В присоединенном файле содержится RAR архив с модулем для работы со списками и инструкцией по использованию. В нем описанным все здесь перечисленные операции и еще некоторые. Поддержка списков с заглавным элементом и без него. Прикрепленные файлы ![]() -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
Altair |
![]()
Сообщение
#4
|
![]() Ищущий истину ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 824 Пол: Мужской Реальное имя: Олег Репутация: ![]() ![]() ![]() |
Стек Стек— это линейный список с определенной дисциплиной обслуживания, которая заключается в том, что элементы списка всегда включаются, выбираются и удаляются с одного конца, называемого вершиной стека. Доступ к элементам здесь происходит по принципу “последним пришел — первым ушел” (LIFO — last in first out), т.е. последний включенный в стек элемент первым из него удаляется. Стеки моделируются на основе линейного списка. Включение элемента вершины стека называется операцией проталкивания в стек, а удаление элемента из вершины стека называется операцией выталкивания из стека. Для работы со стеками необходимо иметь один основной указатель на вершину стека (Тор) и один дополнительный временный указатель (Р), который используется для выделения и освобождения памяти элементов стека. В присоединенном файле содержится текст модуля для работы со стекоми и инструкция по использованию модуля (все в архиве) Прикрепленные файлы ![]() -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
Altair |
![]()
Сообщение
#5
|
![]() Ищущий истину ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 824 Пол: Мужской Реальное имя: Олег Репутация: ![]() ![]() ![]() |
Очередь Очередь — это линейный список, в котором элементы включаются с одного конца, называемого хвостом, а выбираются и удаляются с другого конца, называемого вершиной. Дисциплина обслуживания очереди — “первым пришел — первым вышел” (FIFO — First In First Out), т.е. первый включенный в очередь элемент первым из нее и удаляется. Очередь — это частный случай линейного односвязного списка для которого разрешены только два действия: добавление элемента в конец очереди и удаление элемента из начала очереди. Для создания очереди и работы с ней необходимо иметь как минимум два указателя:
Прикрепленные файлы ![]() -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
volvo |
![]()
Сообщение
#6
|
Гость ![]() |
Дек
Еще один вариант структуры данных - очередь с двойным доступом, или, как ещё ее называют - двухконечная очередь (Double Ended Queue). Для дека добавление и удаление элементов возможны с обоих концов списка. С деком возможны следующие операции:
Пример использования модуля: Uses DeqUnit; Прикрепленные файлы ![]() |
volvo |
![]()
Сообщение
#7
|
Гость ![]() |
|
volvo |
![]()
Сообщение
#8
|
Гость ![]() |
Реализация сортировки стека
В приведенной ниже программе содержимое стека mainStack переносится в отсортированном виде в resStack с использованием дополнительного стека tmpStack): Исходный код Const maxStack = 100; Type TType = Integer; TStack = Record stArr: Array[1 .. maxStack] Of TType; currTop: Integer; End; Procedure Init(Var s: TStack); Begin s.currTop := 0 End; Procedure Push(Var s: TStack; x: TType); Begin If s.currTop <> maxStack Then Begin Inc(s.currTop); s.stArr[s.currTop] := x; End; End; Function Pop(Var s: TStack): TType; Begin If s.currTop <> 0 Then Begin Pop := s.stArr[s.currTop]; Dec(s.currTop); End; End; Function Top(Var s: TStack): TType; Begin Top := s.stArr[s.currTop]; End; Function IsEmpty(Var s: TStack): Boolean; Begin IsEmpty := (s.currTop = 0) End; Procedure Print(Var s: TStack); Var i: Integer; Begin For i := 1 To s.currTop Do Write(s.stArr[i]:4); WriteLn End; Const n = 10; arr: Array[1 .. n] Of TType = (1, 2, 4, 5, 2, 6, 7, 0, 9, 2); Var mainStack, resStack, tmpStack: TStack; i: integer; begin Init(mainStack); Init(resStack); Init(tmpStack); For i := 1 To n Do Push(mainStack, arr[i]); Print(mainStack); While not IsEmpty(mainStack) Do Begin If IsEmpty(resStack) or (Top(resStack) < Top(mainStack)) Then Push(resStack, Pop(mainStack)) Else Begin While (Top(resStack) > Top(mainStack)) and (not IsEmpty(resStack)) Do Push(tmpStack, Pop(resStack)); Push(resStack, Pop(mainStack)); While not IsEmpty(tmpStack) Do Push(resStack, Pop(tmpStack)) End End; Print(resStack) end. В присоединенном файле - программа сортировки стека ![]() Реализация сортировки очереди В примере реализуется сортировка очереди (реализованной в виде объекта) без применения дополнительных очередей. Исходный код type ttype = integer; ptitem = ^titem; titem = record data: ttype; next: ptitem; end; tqueue = object head, tail: ptitem; constructor init; destructor done; procedure put(x: ttype); function get: ttype; function empty: boolean; procedure print; function get_count: word; end; constructor tqueue.init; begin head := nil; tail := nil; end; destructor tqueue.done; begin while empty do get end; procedure tqueue.put(x: ttype); var p: ptitem; begin new(p); p^.data := x; p^.next := nil; if empty then head := p else tail^.next := p; tail := p end; function tqueue.get: ttype; var p: ptitem; begin if not empty then begin p := head; head := head^.next; get := p^.data; dispose(p); end else begin writeln('reading from empty queue'); halt(102) end; end; function tqueue.empty: boolean; begin empty := not assigned(head) end; procedure tqueue.print; var p: ptitem; begin p := head; write('(queue) <'); while assigned(p) do begin write(p^.data, ' '); p := p^.next end; writeln('>') end; function tqueue.get_count: word; var count: word; p: ptitem; begin p := head; count := 0; while assigned(p) do begin inc(count); p := p^.next end; get_count := count end; { А вот и сама сортировка очереди } procedure sort(var q: tqueue); var i, j, k, it, it_next: integer; len: word; begin len := q.get_count; for i := 1 to len do begin it := q.get; for j := 1 to len - i do begin it_next := q.get; if it > it_next then begin q.put(it); it := it_next; end else q.put(it_next) end; for k := 1 to pred(i) do q.put(q.get); q.put(it); end; end; const test: array[1 .. 10] of integer = (2, 5, 17, 7, 9, 3, 4, 6, 11, 71); var i: integer; qint: tqueue; begin qint.init; for i := 1 to 10 do qint.put(test[i]); qint.print; sort(qint); qint.print; qint.done; end. |
Altair |
![]()
Сообщение
#9
|
![]() Ищущий истину ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 824 Пол: Мужской Реальное имя: Олег Репутация: ![]() ![]() ![]() |
Демонстрационные программы без модулей.
Рассматриваются операции с ДСД. списки - ![]() деки - ![]() деревья - ![]() AVL деревья - ![]() -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
Altair |
![]()
Сообщение
#10
|
![]() Ищущий истину ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 824 Пол: Мужской Реальное имя: Олег Репутация: ![]() ![]() ![]() |
Двусвязный список.
Двусвязный список, отличается от односвязного только тем, что каждый узел списка имеет указатель не только на следующий элемент, но и на предыдущий. Некоторые учебники называют этот вид списка самым удобным, и широко используемым, но это не совсем так, ведь с каждым узлом уходит еще на 1 указатель памяти больше, чем у односвязного. Тем не менее, использовать двусвязный список удобнее - потерять начало списка просто невозможно! Все основные операции для двусвязных списков,похожи на операции с односвязными, но за счет добавления еще одного указателя, в код вносятся некоторые изменения. В присоединенном файле модуль DList для работы с двусвязными списками. А вот программа, тестирующая модуль и демонстрирующая его возможности. (одно из возможных расширений модуля - добавление функции поиска элемента, функции удаления элемента, добавленияв начало, и процедуры переворота...). uses crt, dlist; Модуль: ![]() -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
volvo |
![]()
Сообщение
#11
|
Гость ![]() |
Кольцевые (циклические) двухсвязные списки
Во многом эти списки похожи на обычные двухсвязные, за одним исключением: они закольцованы, т.е., последний элемент в таком списке ссылается на первый. Это вносит свои коррективы в алгоритм добавления элемента к кольцевому списку. Для описания элемента списка будем пользоваться следующей структурой: type Добавление элемента Добавляться новые элементы будут перед элементом, помеченным как first (то есть, перед "головой" списка) по следующему алгоритму:
procedure Append(var First: Ring; value: myType); Удаление элемента При удалении элемента из кольцевого списка также рассматриваем два случая:
{ Удалить из списка, начинающегося с First, элемент, на который указывает P } Продолжение следует... |
![]() ![]() |
![]() |
Текстовая версия | 21.08.2024 14:52 |