Xyz
Материал из Вики ИТ мехмата ЮФУ
type
Node<T> = class
data: T;
prev, next: Node<T>;
constructor (d: T; p, n: Node<T>);
begin
data := d;
prev := p;
next := n;
end;
end;
DoubleLinkedList<T> = class
head, tail: Node<T>;
constructor;
begin
head := nil;
tail := nil;
end;
procedure AddFirst(d: T);
begin
head := new Node<T>(d, nil, head);
if head.next <> nil then
head.next.prev := head
else // если список был пуст
tail := head;
end;
procedure AddLast(d: T);
begin
tail := new Node<T>(d, tail, nil);
if tail.prev <> nil then
tail.prev.next := tail
else // если список был пуст
head := tail;
end;
procedure DeleteFirst;
begin
head := head.next;
if head = nil then
tail := nil
else
head.prev := nil;
end;
procedure DeleteLast;
begin
tail := tail.prev;
if tail = nil then
head := nil
else
tail.next := nil;
end;
procedure InsertBefore(cur: Node<T>; d: T);
begin
if cur = head then
AddFirst(d)
else
begin
cur.prev := new Node<T>(d, cur.prev, cur);
cur.prev.prev.next := cur.prev;
end;
end;
procedure InsertAfter(cur: Node<T>; d: T);
begin
if cur = tail then
AddLast(d)
else
begin
cur.next := new Node<T>(d, cur, cur.next);
cur.next.next.prev := cur.next;
end;
end;
function RemoveAt(cur: Node<T>): Node<T>;
begin
if cur = head then
begin
DeleteFirst;
Result:=head;
end
else if cur = tail then
begin
DeleteLast;
Result:=nil;
end
else if cur = tail then
begin
DeleteLast;
result := nil;
end
else
begin
cur.prev.next := cur.next;
cur.next.prev := cur.prev;
result := cur.next;
end;
end;
procedure Print;
begin
var cur := head;
while cur <> nil do
begin
write(cur.data, ' ');
cur := cur.next;
end;
end;
procedure PrintReverse;
begin
var cur := tail;
while cur <> nil do
begin
write(cur.data, ' ');
cur := cur.prev;
end;
end;
end;
procedure FillNodeFromFile(name: string; var list: DoubleLinkedList<integer>); begin
list := new DoubleLinkedList<integer>; var f: text; assign(f, name); reset(f); var a: integer; read(f, a); list.head := new Node<integer>(a, nil, nil); var cur := list.head; while not eof(f) do begin read(f, a); cur.next := new Node<integer>(a, cur, nil); list.tail := cur.next; cur := cur.next; end; Close(f);
end;
begin
var name: string := '1.txt'; var list: DoubleLinkedList<integer>; FillNodeFromFile(name, list); list.Print
end.
type
Node<T> = class
data: T;
prev, next: Node<T>;
constructor (d: T; p, n: Node<T>);
begin
data := d;
prev := p;
next := n;
end;
end;
DoubleLinkedList<T> = class
head, tail: Node<T>;
constructor;
begin
head := nil;
tail := nil;
end;
procedure AddFirst(d: T);
begin
head := new Node<T>(d, nil, head);
if head.next <> nil then
head.next.prev := head
else // если список был пуст
tail := head;
end;
procedure AddLast(d: T);
begin
tail := new Node<T>(d, tail, nil);
if tail.prev <> nil then
tail.prev.next := tail
else // если список был пуст
head := tail;
end;
procedure DeleteFirst;
begin
head := head.next;
if head = nil then
tail := nil
else
head.prev := nil;
end;
procedure DeleteLast;
begin
tail := tail.prev;
if tail = nil then
head := nil
else
tail.next := nil;
end;
procedure InsertBefore(cur: Node<T>; d: T);
begin
if cur = head then
AddFirst(d)
else
begin
cur.prev := new Node<T>(d, cur.prev, cur);
cur.prev.prev.next := cur.prev;
end;
end;
procedure InsertAfter(cur: Node<T>; d: T);
begin
if cur = tail then
AddLast(d)
else
begin
cur.next := new Node<T>(d, cur, cur.next);
cur.next.next.prev := cur.next;
end;
end;
function RemoveAt(cur: Node<T>): Node<T>;
begin
if cur = head then
begin
DeleteFirst;
Result:=head;
end
else if cur = tail then
begin
DeleteLast;
Result:=nil;
end
else if cur = tail then
begin
DeleteLast;
result := nil;
end
else
begin
cur.prev.next := cur.next;
cur.next.prev := cur.prev;
result := cur.next;
end;
end;
procedure Print;
begin
var cur := head;
while cur <> nil do
begin
write(cur.data, ' ');
cur := cur.next;
end;
end;
procedure PrintReverse;
begin
var cur := tail;
while cur <> nil do
begin
write(cur.data, ' ');
cur := cur.prev;
end;
end;
end;
procedure CreateRandom(var list: DoubleLinkedList<integer>; n: integer); begin
list := new DoubleLinkedList<integer>; list.head := new Node<integer>(Random(1, 9), nil, nil); var cur := list.head; for var i := 1 to n-1 do begin cur.next := new Node<integer>(Random(1, 9), cur, nil); list.tail := cur.next; cur := cur.next; end;
end;
procedure InsertZeroAfterEvenElem(var list: DoubleLinkedList<integer>); begin
var cur := list.head;
while cur <> nil do
begin
if (cur.data mod 2 = 0) then
begin
list.InsertAfter(cur, 0);
cur := cur.next
end;
cur := cur.next;
end;
end;
begin
var list: DoubleLinkedList<integer>; CreateRandom(list, 5); list.Print; writeln; InsertZeroAfterEvenElem(list); list.Print;
end.
type
Node<T> = class
data: T;
prev, next: Node<T>;
constructor (d: T; p, n: Node<T>);
begin
data := d;
prev := p;
next := n;
end;
end;
DoubleLinkedList<T> = class
head, tail: Node<T>;
constructor;
begin
head := nil;
tail := nil;
end;
procedure AddFirst(d: T);
begin
head := new Node<T>(d, nil, head);
if head.next <> nil then
head.next.prev := head
else // если список был пуст
tail := head;
end;
procedure AddLast(d: T);
begin
tail := new Node<T>(d, tail, nil);
if tail.prev <> nil then
tail.prev.next := tail
else // если список был пуст
head := tail;
end;
procedure DeleteFirst;
begin
head := head.next;
if head = nil then
tail := nil
else
head.prev := nil;
end;
procedure DeleteLast;
begin
tail := tail.prev;
if tail = nil then
head := nil
else
tail.next := nil;
end;
procedure InsertBefore(cur: Node<T>; d: T);
begin
if cur = head then
AddFirst(d)
else
begin
cur.prev := new Node<T>(d, cur.prev, cur);
cur.prev.prev.next := cur.prev;
end;
end;
procedure InsertAfter(cur: Node<T>; d: T);
begin
if cur = tail then
AddLast(d)
else
begin
cur.next := new Node<T>(d, cur, cur.next);
cur.next.next.prev := cur.next;
end;
end;
function RemoveAt(cur: Node<T>): Node<T>;
begin
if cur = head then
begin
DeleteFirst;
Result:=head;
end
else if cur = tail then
begin
DeleteLast;
Result:=nil;
end
else if cur = tail then
begin
DeleteLast;
result := nil;
end
else
begin
cur.prev.next := cur.next;
cur.next.prev := cur.prev;
result := cur.next;
end;
end;
procedure Print;
begin
var cur := head;
while cur <> nil do
begin
write(cur.data, ' ');
cur := cur.next;
end;
end;
procedure PrintReverse;
begin
var cur := tail;
while cur <> nil do
begin
write(cur.data, ' ');
cur := cur.prev;
end;
end;
end;
procedure CreateRandom(var list: DoubleLinkedList<integer>; n: integer); begin
list := new DoubleLinkedList<integer>; list.head := new Node<integer>(Random(-9, 9), nil, nil); var cur := list.head; for var i := 1 to n-1 do begin cur.next := new Node<integer>(Random(-9, 9), cur, nil); list.tail := cur.next; cur := cur.next; end;
end;
procedure DeletePositiveElems(var list: DoubleLinkedList<integer>); begin
var cur := list.head;
var i: integer;
while cur <> nil do
begin
if cur.data > 0 then
cur := list.RemoveAt(cur)
else
cur := cur.next;
end;
end;
begin
var list: DoubleLinkedList<integer>; CreateRandom(list, 5); list.Print; writeln; DeletePositiveElems(list); list.Print;
end.
