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.

Источник — «http://it.mmcs.sfedu.ru/_wiki/index.php?title=Xyz&oldid=2362»