Удаление элемента из списка

ДИНАМИКА

(ЛАБОРАТОНАЯ РАБОТА №1)

Выполнила:

студентка 141 группы

математического факультета

Пухова Ю.И.

Проверила:

Швалева О. В.

Пермь

ГЛАВА 1 Короткая ТЕОРИЯ

СПИСКИ

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

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

Только на самый 1-ый элемент перечня (голову) имеется отдельный Удаление элемента из списка указатель. Последний элемент перечня никуда не показывает.

Описание перечня

Пример описания перечня

Type ukazat= ^ S;

S= record

Inf: integer;

Next: ukazat;

End;

В Паскале существует основное правило: перед внедрением какого-нибудь объекта он должен быть описан. Исключение изготовлено только для указателей, которые могут ссылаться на еще не объявленный тип.

Формирование перечня

Чтоб перечень Удаление элемента из списка существовал, нужно найти указатель на его начало.

Пример описания перечня

Type ukazat= ^S;

S= record

Inf: integer;

Next: ukazat;

End;

Сделаем 1-ый элемент перечня:

New (u); {выделяем место в памяти}

u^. Next:= nil; {указатель пуст}

u^. Inf:=3;

Продолжим формирование перечня. Для этого необходимо добавить элемент или в конец перечня, или Удаление элемента из списка в голову.

А) Добавим элемент в голову перечня. Для этого нужно выполнить последовательность действий:

получить память для нового элемента; поместить туда информацию; присоединить элемент к голове перечня.

New(x);

Readln(x^.Inf);

x^. Next:= u;

u:= x;

Б)Добавление элемента в конец перечня. Для этого введем вспомогательную переменную, которая будет Удаление элемента из списка хранить адресок последнего элемента. Пусть это будет указатель с именованием hv (хвост).

x:= hv;

New( x^. next); {выделяем память для последующего элемента}

x:= x^.next;

x^.next:= nil;

x^. inf:= 5;

hv:=x;

Просмотр перечня

While u nil do

Begin

Writeln (u^.inf);

u:= u^.next;>

end;

Удаление элемента из перечня

А)Удаление первого Удаление элемента из списка элемента. Для этого во вспомогательном указателе запомним 1-ый элемент, указатель на голову перечня переключим на последующий элемент перечня и освободим область динамической памяти, на которую показывает вспомогательный указатель.

x:= u;

u:= u^.next;

dispose(x);

Б) Удаление элемента из середины перечня. Для этого необходимо знать адреса удаляемого элемента и Удаление элемента из списка элемента, стоящего перед ним. Допустим, что digit – это значение удаляемого элемента.

x:= u;

while ( x nil) and ( x^. inf digit) do

begin

dx:= x;

x:= x^.next;

end;

dx:= x^.next:

dispose(x);

В)Удаление из конца перечня. Для этого необходимо отыскать предпоследний элемент.

x:= u; dx:= u;

while x^.next nil Удаление элемента из списка do

begin

dx:= x; x:= x^.next;

end;

dx^.next:= nil;

dispose(x);

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

summa:= 0;

x:= u;

while x nil do

begin

summa:= summa+ x^.inf;

x:= x^.next;

ДВОИЧНОЕ ДЕРЕВО

Дерево — это совокупа частей, именуемых узлами Удаление элемента из списка (при всем этом какой-то из них определен как корень), и отношений (родительский–дочерний), образующих иерархическую структуру узлов. Узлы могут являться величинами хоть какого обычного либо структурированного типа, кроме файлового. Узлы, которые не имеют ни 1-го следующего узла, именуются листьями.

В двоичном (бинарном) дереве каждый узел может Удаление элемента из списка быть связан менее чем 2-мя другими узлами. Рекурсивно двоичное дерево определяется так: двоичное дерево бывает или пустым (не содержит ни 1-го узла), или содержит узел, именуемый корнем, также два независящих поддерева — левое поддерево и правое поддерево.

Двоичное дерево поиска может быть или пустым, или оно обладает таким свойством, что корневой Удаление элемента из списка элемент имеет большее значение узла, чем хоть какой элемент в левом поддереве, и наименьшее либо равное, чем элементы в правом поддереве. Обозначенное свойство именуется характеристическим свойством двоичного дерева поиска и производится для хоть какого узла такового дерева, включая корень.

Представим для себя генеалогическое дерево, корень которого - имя человека Удаление элемента из списка, на последующем уровне - имена его родителей, еще на последующем - имена родителей и их родителей и т.д. Такая структура именуется двоичным деревом, рис. 1.36.

Рис. 1.36. Структура типа «двоичное дерево»;
пара ближайших по горизонтали кружков -мужское и женское имя.

Выделим типовые операции над двоичными деревьями поиска:

Так как определение двоичного дерева рекурсивно, то все обозначенные типовые операции могут быть реализованы в виде рекурсивных подпрограмм (на практике конкретно таковой вариант в большинстве случаев и применяется). Отметим только, что внедрение рекурсии замедляет работу Удаление элемента из списка программки и расходует лишнюю память при её выполнении.

Покажем два варианта прибавления элемента в дерево: итеративный и рекурсивный.

{Итеративный вариант прибавления элемента в дерево, Turbo Pascal}

Procedure InsIteration(Var T : U; X : BT);

Var vsp, A : U;

Begin

New(A); A^.Inf := X; A^.L:=Nil; A^.R := Nil;

If T=Nil Then Удаление элемента из списка T:=A

Else Begin vsp := T;

While vsp Nil Do

If A^.Inf < vsp^.Inf

Then

If vsp^.L=Nil Then Begin vsp^.L:=A; vsp:=A^.L End Else vsp:=vsp^.L

Else

If vsp^.R = Nil Then Begin vsp^.R := A; vsp:=A^.R End Else vsp := vsp^.R;

End

End;

{Рекурсивный Удаление элемента из списка вариант прибавления элемента в дерево, Turbo Pascal}

Procedure InsRec(Var Tree : U; x : BT);

Begin

If Tree = Nil

Then Begin

New(Tree);

Tree^.L := Nil;

Tree^.R := Nil;

Tree^.Inf := x

End

Else If x < Tree^.inf

Then InsRec(Tree^.L, x)

Else InsRec(Tree^.R, x)

End;

Существует несколько методов обхода (прохождения) всех узлов Удаление элемента из списка дерева. Три более нередко применяемых из их именуются обход в прямом (префиксном) порядке, обход в оборотном (постфиксном) порядке и обход во внутреннем порядке (либо симметричный обход). Любой из обходов реализуется с внедрением рекурсии.

ГЛАВА 2. Задачка 4

Кольцевой перечень из частей с ключами.

Обозначения: D – данные, next – указатель на последующий элемент, P Удаление элемента из списка – указатель на предшествующий элемент, K – ключ, begin – указатель на начало перечня.

ЛИСТИНГ Программки

Program Kolzevoy_Spisok;

type

ptr=^R;

R=Record

A:real;

K:integer;

next:ptr;

end;

var

nach:ptr;

nb,a,i,n:integer;

inf:real;

Procedure Init(var nach:ptr);

begin

nach:=nil;

end;

Procedure Print_Spisok(nach:ptr Удаление элемента из списка);

var q:ptr; i:integer;

begin

writeln('spisok:');

writeln;

i:=0;

if nachnil then

begin

q:=nach;

repeat

i:=i+1;

writeln(i:3,' ',q^.A:8:2,' ',q^.K);

q:=q^.next;

until q=nach;

writeln;

end;

if (nach=nil) then writeln('spisok pust');

end;

Procedure Clear_Spisok(var nach:ptr);

var q,r:ptr;

begin

if nachnil then

begin

q:=nach;

repeat

r Удаление элемента из списка:=q;

q:=r^.next;

Dispose(r);

until q=nach;

end;

nach:=nil;

end;

Procedure Dobavit_nach(var nach:ptr; inf:real);

var q,r:ptr;

begin

New(q);

if nach=nil then begin

nach:=q;

q^.next:=nach;

end

else begin

r:=nach;

while r^.nextnach do r:=r^.next;

q^.next Удаление элемента из списка:=nach;

nach:=q;

r^.next:=q;

end;

q^.A:=inf;

q^.K:=nb;

nb:=nb+1;

end;

Procedure Dobavit_kon(var nach:ptr; inf:real);

var q,r:ptr;

begin

New(q);

r:=nach;

if nachnil then while r^.nextnach do r:=r^.next;

if nach=nil then begin

nach:=q;

q Удаление элемента из списка^.next:=nach;

end

else begin

r^.next:=q;

q^.next:=nach;

end;

q^.A:=inf;

q^.K:=nb;

nb:=nb+1;

end;

Procedure Dobavit_nom(var nach:ptr; a:integer; inf:real);

var q,r:ptr; i:integer;

begin

q:=nach; i:=1;

if a1 then repeat

i:=i+1;

q:=q^.next;

until (i Удаление элемента из списка=a) or (q=nach);

if (ia) then writeln('nevernyi nomer')

else begin

New(r);

r^.A:=inf;

r^.K:=nb;

nb:=nb+1;

r^.next:=q^.next;

q^.next:=r;

end;

end;

Procedure Dobavit_kl(var nach:ptr; a:integer; inf:real);

var q,r:ptr;

begin

q:=nach;

if q^.Ka Удаление элемента из списка then repeat

q:=q^.next;

until (q^.K=a) or (q=nach);

if (q^.Ka) then writeln('nevernyi kluch')

else begin

New(r);

r^.A:=inf;

r^.K:=nb;

nb:=nb+1;

r^.next:=q^.next;

q^.next:=r;

end;

end;

Procedure Udalit_nach(var nach:ptr);

var q,r:ptr Удаление элемента из списка;

begin

if nachnil then begin

if nach^.nextnach then

begin

r:=nach;

while r^.nextnach do r:=r^.next;

q:=nach;

nach:=q^.next;

r^.next:=nach;

Dispose(q);

end

else

begin

q:=nach;

nach:=nil;

Dispose(q);

end;

end;

end;

Procedure Udalit_kon(var nach:ptr);

var q,r:ptr;

begin

r:=nach;

if nachnil then

begin

if nach Удаление элемента из списка^.next=nach then

begin

q:=nach;

nach:=nil;

Dispose(q);

end

else

begin

while r^.next^.nextnach do r:=r^.next;

q:=r^.next;

r^.next:=nach;

Dispose(q);

end;

end;

end;

Procedure Udalit_nom(var nach:ptr; a3:integer);

var q,r:ptr; i:integer;

begin

if a3=1 then

Udalit_nach(nach)

else

begin

r:=nach; i Удаление элемента из списка:=1;

while (ia3-1) do

begin

i:=i+1;

r:=r^.next;

end;

q:=r^.next;

r^.next:=q^.next;

Dispose(q);

end;

end;

Procedure Udalit_kl(var nach:ptr; a3:integer);

var q,r:ptr;

begin

r:=nach;

if r^.K=a3 then

Udalit_nach(nach)

else

begin

while (r^.next^.Ka3) do

r:=r^.next;

q:=r Удаление элемента из списка^.next;

r^.next:=q^.next;

Dispose(q);

end;

end;

Procedure Dobav_Element(var nach:ptr);

var a2,a3:byte; i:integer;

b:boolean;

begin

repeat

writeln('1 - v nachalo');

writeln('2 - v konec');

writeln('3 - posle elementa');

writeln('4 - posle klucha');

readln(a2);

if (a21) and (a22) and (a23) and (a24) then b:=false else b Удаление элемента из списка:=true;

until b;

if a2=3 then

begin

write('nomer:');

readln(a3);

end;

if a2=4 then

begin

write('kluch:');

readln(a3);

end;

write('element:');

readln(inf);

if (a2=1) then

Dobavit_nach(nach,inf);

if (a2=2) then

Dobavit_kon(nach,inf);

if (a2=3) then

Dobavit_nom(nach,a3,inf);

if (a2=4) then

Dobavit_kl(nach,a3,inf Удаление элемента из списка);

end;

Procedure Udal_Element(var nach:ptr);

var a2,a3:byte; i:integer;

b:boolean;

begin

repeat

writeln('1 - iz nachala');

writeln('2 - iz konca');

writeln('3 - ukazannyi element');

writeln('4 - ukazannyi kluch');

readln(a2);

if (a21) and (a22) and (a23) and (a24) then b:=false else b:=true;

until b;

if a2=3 then

begin

write('nomer:');

readln Удаление элемента из списка(a3);

end;

if a2=4 then

begin

write('kluch:');

readln(a3);

end;

if (a2=1) then

Udalit_nach(nach);

if (a2=2) then

Udalit_kon(nach);

if (a2=3) then

Udalit_nom(nach,a3);

if (a2=4) then

Udalit_kl(nach,a3);

end;

begin

nb:=1;

Init(nach);

write('chislo dobavlennyh elementov spiska:');

readln(n);

for i:=1 to n do begin

Dobav_Element Удаление элемента из списка(nach);

Print_Spisok(nach);

readln;

end;

write('chislo udalennyh elementov spiska:');

readln(n);

for i:=1 to n do begin

Udal_Element(nach);

Print_Spisok(nach);

readln;

end;

Clear_Spisok(nach);

end.

НАБОР ТЕСТОВ

2.2.1

При добавлении элемента в начало, подходящий элемент занимает место перед предшествующим. Если перечень пуст, перечень заполняется одним Удаление элемента из списка элементом.

Сейчас в перечне находится элемент 6. Вставим в начало элемент 3. Перечень будет смотреться последующим образом:

При добавлении элемента в конец, подходящий элемент занимает место после последнего элемента. Вставим в конец нашего перечня элемент 28. Тогда перечень будет смотреться последующим образом:

Когда уже есть несколько частей, то можно добавить элемент после хоть Удаление элемента из списка какого элемента с каким или номером. Вставим после элемента с номером два элемент 111.

Элементу 111 присваивается номер 3. И выходит перечень:

Добавим элемент 609 после элемента с ключом 1.

При нажатии кнопки «удалить из начала» получим: 6, 609, 111, 28.

Удалим элемент из конца перечня, получим: 6, 609, 111.

Можно удалить элемент с хоть каким номером, который есть в этом Удаление элемента из списка перечне, к примеру с номером 2. Получим перечень: 6,111.

Удалим элемент с ключом 3. Получим перечень, состоящий из 1-го элемента: 6.

2.2.2

Проверим работу программки вторым вариантом тестов: пусть число вводимых частей равно 6. Вставим 1-ый элемент 123. Получим перечень, состоящий только из элемента 123.

Вставим в начало элемент 8. Ему присваивается номер 1, ключ 2.

Вставим элемент 333333 после элемента Удаление элемента из списка с ключом 2. Получим последующий перечень:

При добавлении элемента в конец, подходящий элемент занимает место после последнего элемента. Вставим элемент 2 в конец перечня:

Вставим элемент 8 после элемента с номером 1:

Вставим в начало перечня элемент 3. Вышел перечень, состоящий из 6 частей: 3, 8, 8, 333333, 123, 2.

Удалим из перечня элемент под номером 4. Перечень состоит из 5 частей: 3, 8, 8, 123, 2.

ГЛАВА Удаление элемента из списка 3. Задачка II 5 e


uchrezhdeniya-visshego-professionalnogo-obrazovaniya.html
uchrezhdeniya-zdravoohraneniya-telefoni-ekstrennogo-vizova.html
uchrezhdeniyah-ugolovno-ispolnitelnoj-sistemi.html