. . Head Tail nil.
. Prev.
, , .
, . , , :
var p: Link;
...
p:= New(Link);
p^.Data:=...;
.
:
p^.Next:= nil;
if L = nil then
L:= p;
else begin
q:= L;
while q^.Next <> nil do
q:= q^.Next; {, !}
{ q }
q^.Next:= p;
p^.Next:= nil;
end;
( LTail ):
p^.Next:= nil;
if L = nil then begin
L:= p;
LTail:= L;
end
else begin
LTail^.Next:= p;
LTail:= p;
end;
:
if L = nil then
p^.Next:= p
else begin
{L , !}
p^.Next:= L^.Next;
L^.Next:= p;
end;
L:= p;
:
q:= L;
while q^.Next <> Link(@L) do
q:= q^.Next;
{ q }
p^.Next:= q^.Next;
q^.Next:= p;
{ }
( LTail ):
if L = nil then
L:= p
else
LTail^.Next:= p;
P^.Next:= nil;
p^.Prev:= LTail;
LTail:= p;
:
if L = nil then begin
p^.Next:= p;
p^.Prev:= p;
L:= p;
end
else begin
p^.Next:= L;
p^.Prev:= L^.Prev;
L^.Prev^.Next:= p;
L^.Prev:= p;
end;
, , :
- ( );
- ;
- ;
- ;
- ;
- .
, , .
. . .
|
|
|
, LIFO (Last in first out; ).
: .
TItem.
. :
Var Top: Integer; { , } Stack: array[1..MaxSize] of TItem; { }.
. Top. :
procedure ClearStack;begin Top:= 0;end;:
function IsEmpty: Boolean;begin IsEmpty:= Top=0;end;:
function Get: TItem;begin if Top=0 then RunError else Get:= Stack[Top];end;:
procedure Put(Item: TItem);begin if Top=0 then RunError else Stack[Top]:= Item;end;:
procedure Push(Item: TItem);begin if Top=MaxSize then RunError; Inc(Top); Stack[Top]:= Item;end;:
function Pop: TItem;begin if Top=0 then RunError; Item:= Stack[Top]; Dec(Top);end;. . ().
Type PElement = ^TElement; TElement = record Item: TItem; Next: PElement; end;Var TopPointer: PElement;.
. , :
procedure ClearStack;Var Temp: PElement;begin while TopPointer<>nil do begin Temp:= TopPointer; TopPointer:= TopPointer^.Next; Dispose(Temp); end;end;:
function IsEmpty: Boolean;begin IsEmpty:= TopPointer=nil;end;:
function Get: TItem;begin if TopPointer=nil then RunError else Get:= TopPointer^.Item;end;:
procedure Put(Item: TItem);begin if TopPointer=nil then RunError else TopPointer^.Item:= Item;end;. :
procedure Push(Item: TItem);Var Temp: PElement;begin Temp:= New(PElement); Temp^.Item:= Item; Temp^.Next:= TopPointer; TopPointer:= Temp;end;, :
function Pop: TItem;Var Temp: PElement;begin if TopPointer=nil then RunError; Item:= TopPointer^.Item; Temp:= TopPointer^.Next; Dispose(TopPointer); TopPointer:= Temp;end;,
ClearStack;Push(3); Push(7); Push(2); Push(1);, , . , .
|
|
|
.
1. :
- ;
- ;
- ;
-
- .
, ,
2. , .
3.
. . .
.
.
.
4
:
.
4 .
, .
;
.
.
. T. T-. . . . , . , .
, , . .
, .
.
, ( ), ( ). i- 2i-1 . , n , . =2i-1 .
T- 3 : , . :
1. ;
2. .
.
:
PTree = ^TTree;TTree = record Item: T; { } Left, Right: PTree; { }end;Left, Right nil, .
. , n . Value: array[1..N] of T, :
Value[1] ;
Value[2*i] Value[i];
Value[2*i+1] Value[i].
(, ). , ( ( ) ).
y[1]..y[n] , y[i+1] y[i] i. 0. . 3-.
|
|
|
. . , . :
T- , X : , , , X, , , , X.
: .
, .
// T-
, . Item Tree^.Item, , , ; , , :
function Exist(Item: T; Tree: PTree): Boolean;begin if Tree=nil then begin Exist:= False; Exit end; if Tree^.Item=Item then Exist:= True else if Tree^.Item>Item then Exist:= Exist(Item, Tree^.Left) else Exist:= Exist(Item, Tree^.Right);end;, . , . . Item Tree, . Item Tree.
, . , ( ), , Item ( , ):
procedure Add(Item: T; Tree: PTree);Var NewNode: PTree;begin { } while ((Item>Tree^.Item)and(Tree^.Right<>nil))or ((Item<Tree^.Item)and(Tree^.Left<>nil)) do if Item>Tree^.Item then Tree:= Tree^.Right else Tree:= Tree^.Left; { } NewNode:= New(PTree); NewNode^.Item:= Item; NewNode^.Left:= nil; NewNode^.Right:= nil; If Item>Tree^.Item then Tree^.Right:= NewNode else Tree^.Left:= NewNode;end;. , , . , . . , . , . , .
, , , . .
procedure Del(Item: T; Tree: PTree);Var Tree2, Father: PTree; Dir: (L, R); { (/)}begin { } Father:= nil; { } while ((Item>Tree^.Item)and(Tree^.Right<>nil))or ((Item<Tree^.Item)and(Tree^.Left<>nil)) do begin Father:= Tree; if Item>Tree^.Item then begin Tree:= Tree^.Right; Direction:= R; end else begin Tree:= Tree^.Left; Direction:= L; end; end; if (Tree^.Left<>nil)and(Tree^.Right<>nil then begin{ } Father:= Tree; Tree2:= Tree^.Right; While (Tree2^.Left<>nil) do begin Father:= Tree2; Tree2:= Tree2^.Left; end; Tree^.Item:= Tree2^.Item; Father^.Left:= Tree2^.Right; Dispose(Tree2); end else {} if (Tree^.Left=nil) then begin if Father<>nil then if Direction=L then Father^.Left:= Tree^.Right; else Father^.Right:= Tree^.Right; Dispose(Tree); end else begin if Father<>nil then if Direction=L then Father^.Left:= Tree^.Left; else Father^.Right:= Tree^.Left; Dispose(Tree); end;end;(, , , )? Tmax(log(n)). . , , . . T(n).
|
|
|
, . (//) , (
.
:
1. .
2. , F-
3. .
4.
1. , , ?
2. ?
3. .
4. ? .
5. ?
5
