Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Динамические списковые структурыИзучить: ü Линейные списки. ü Описание элемента односвязного списка. ü Типовые действия со списком. Действия со стеком(создание списка, добавление, удаление, печать элементов списка) type pitem=^item; item=record { элемент стека } data: integer; { значение элемента } prev: pitem; { адрес предыдущего элемента } end; var top,p:pitem; n,k:integer; procedure add(x:integer); { добавляет элемент на вершину стека } begin new(p); { создаем произвольный элемент р } p^.data:=x; p^.prev:=top; top:=p; { устанавливаем р вершиной стека } end; procedure deltop; { удаляет узел с вершины стека } begin if top<>nil then begin { если стек не пустой } p:=top^.prev; { запоминаем предшествующий вершине элемент } dispose(top); top:=p; { устанавливаем р вершиной стека } end; end; procedure writestack; { выводит стек на экран } begin writeln('Содержимое стека (начиная с вершины): '); p:=top; while p<>nil do begin write(p^.data,' '); p:=p^.prev; end; writeln; end; BEGIN { начало программы } top:=nil; for k:=l to 10 do add(k); { заполняем стек числами от 1 до 10 } writestack; writeln('Введите значение элемента для добавления в стек:'); readln(n); add(n); writestack; writeln('Сколько элементов стека нужно удалить?'); readln(n); for k:=l to n do deltop; writestack; readln END. { Комментарии} В примере реализованы две основные операции со стеком: добавление и удаление элементов. Для решения задачи потребовалось всего два указателя типа pitem. Один из них (top) всегда указывает на вершину стека, второй (р) — рабочий указатель, предназначенный для временного хранения адресов различных элементов. Обратите внимание на типовую процедуру вывода списка при помощи цикла while. Стандартное действие p:=p^.prev; означает переход к следующему элементу стека (для стека правильнее назвать этот элемент не следующим, а предыдущим, т. к. он был помещен в стек раньше). Поэтому элементы стека можно вывести только в порядке, обратном тому, в котором они вводились. В следующем примере при формировании списка указующие поля заполняются таким образом, что каждый элемент списка действительно указывает на следующий за ним элемент, т. е. элемент, помещенный в список позже. Таким образом, при выводе списка его элементы появятся на экране именно в том порядке, в котором заполнялся список. Такой способ формирования списка используется при реализации очередей. Но в данном примере рассматривается общий случай списка и приводятся процедуры вставки и удаления элементов в произвольную позицию списка. Листинг 2. Вставка и удаление элементов в произвольной позиции type pitem=^item; item=record data:integer; next:pitem; end; var head,p,p1:pitem; n,k,l:integer; procedure add(x,i:integer); var j:integer; begin if (i>0) and (i<=n+l) then begin new(p); p^.data:=x; if i=l then begin p^.next:=head; head:=p; end else begin p1:=head; for j:=2 to i-1 do (находим i-1-й элемент } pl:=pl^.next; p^.next:=р1^.next; pl^.next:=p; end; n:=n+l; end; end; procedure delitem(i:integer); var k:integer; begin if (i>=l) and (i<=n) and (head<>nil) then if i=l then begin { если нужно удалить первый элемент } р:=head^.next; dispose(head); head:=p; end else begin p:=head; for к:=2 to i-1 do { находим i-1-й элемент } p:=p^.next; pl:=p^.next; { pl-i-й элемент } р^.next:=р1^.next; { p^.next ссылается на i+1-й элемент } dispose(pi); end; end; procedure writelist; begin p1:=head; writeln('Содержимое списка'); while p1<>nil do begin write(р1^.data,' '); pl:=pl^.next; end; writeln; end; BEGIN n:=0; head:=nil; for k:=l to 10 do add(k,k); { заполняем список числами от 1 до 10 } writelist; write('Введите значение добавляемого элемента:'); readln(k); write('Введите позицию добавляемого элемента'); readln(l); add(k,l); writelist; write('Введите номер удаляемого элемента:'); readln(k); delitem(k); writelist; readln END. {Комментарии} Проанализировав процедуры вставки и удаления элементов в произвольное место списка, можно прийти к выводу, что сама операция добавления и удаления выполняется на удивление просто — достаточно лишь переставить указатели. Гораздо больше времени уходит на то, чтобы найти элемент с заданным номером в списке. Список — это не массив, и обратиться по индексу к элементу нельзя. Остается только один вариант — двигаться по цепочке от одного элемента к другому, начиная от самого первого элемента. 2. Работа с массивом ссылок Type ssilka=^real; vector=array [1..100] of ssilka; Считая, что все элементы вектора Х отличны от nil, описать функцию Negat(x), значением которой является первый из элементов вектора Х, ссылающихся на отрицательные числа или nil, если таких элементов нет. var v:vector; function Negat(var x:vector):ssilka; var i:byte; begin negat:=nil; for I:=1 to 100 do if x[i]^<0 then {если элемент массива отрицателен} begin negat:=x[i] exit {досрочный выход из функции} end; end; BEGIN {тело основной программы} randomize; writeln(' исходный массив'); for i:=1 to 100 do {создание массива ссылок в куче заполнение случайными числами и печать массива} begin new(v[i]); v[i]^:=random*10-0.2; write(v[i]^:5:1) end; writeln; if negat(v)=nil then writeln(' ссылок на отрицательные числа нет в массиве') else writeln(' первое отрицательное число= ',negat(v):5:1); for i:=1 to 100 do {высвобождение памяти в куче} dispose(v[i]) END.
|