, . , - . :
:
;
( ).
nil , .
, , nil . () .
, - .
""
rel2=^elem2;
elem2=record
next:rel1;
prev:rel2;
data:< >
end;
list2=rel2;
var
l2:list2;
procedure insert2(pred:rel2; info:<>);
var
q:rel2;
begin
new(q); { }
q^.data:=info;
q^.next:=pred^.next;
q^.prev:=pred^.next^.prev;
pred^.next.prev:=q;
pred^.next:=q
end;
procedure delete2(del:rel2);
begin
del^.next^.prev:=del^.prev;
del^.prev^.next:=del^.next;
dispose(del);
end;
function search2(list:rel2; info:<>; var point:rel2):boolean;
var
p,q:rel2;
b:boolean;
begin
b:=false;
point:=nil;
p:=list;
q:=p^.next;
while (p<>q) and (not b) do
begin
if q^.data=info then
begin
b:=true;
point:=q
end;
q:=q^.next
end;
search2:=b
end;
...
...
...
var
l2:list2;
r:rel2;
begin { }
new(r);
r^.next:=r;
r^.pred:=r;
l2:=r;
...
...
...
end.
:
, , , l2, - .
:
- ( ), - .
, .
- , .
: , , ( ). ( ) pred , (l2).
(), , .
|
|
|
: 1- N-, N- 1-, 1- N- , . , .
, 1- N-, . :
var a,l1:list1;
begin
...
new(l1);
l1^.next:=nil;
a:=l1;
...
, .
. , . : , , . , N
a: array[0..N1] of Item
Item , . , x. i, [i].key = x, . , , , , Item .
: , (- ), , .
, , .
- .
.
- for while.
1/2*N , - 1 , - N .
- .
, .
""
var
nums:array[0..N] of real;
function search_s1(item:^real; n:integer; key:real):integer;
var
i:integer;
begin
for i:=0 to N do
if key=item[i] then
begin
search_s1:=i;
break
end
else
search_s1:=-1
end;
function search_s2(item:^real; n:integer; key:real):integer;
var
i:integer;
begin
i:=0;
search_s2:=-1;
while (key<>item[i]) or (i<n) do
begin
if key=item[i] then
search_s2:=i;
i:=i+1
end
end;
.
( 2): 1/2, 1/4, 1/8 .., . , . , , , .
|
|
|
, , ().
log2(N)+E ( E<0.0861) , " ". "".
""
function search_b(item:^real; n:integer; key:real):integer;
var
low,high,mid:integer;
begin
search_b:=-1;
low:=0;
high:=n-1;
while low<=high do
begin
mid:=(low+high)/2;
if key<item[mid] then
hig:=mid-1
else
if key>item[mid] then
low:=mid+1
else
search_b:=mid
end
end;
:
low, high, mid (, ) - . ;
.
. . . , , . N+1=Fk.
. , k kl kh, (l-k)(k-kl)/(kh-ki) li. .
, n/2 sqr(ni) log2(log2(N)) , .
: . log2(log2(N)) log2(N) N, () .
.
, , , .
, ( ) .
, , .
:
();
();
;
;
;
;
.
, - (); , ; - .
:
( , );
;
;
()?
, ;
.
. N.
|
|
|
, . .
: , (0). , .
. . , . "" .
""
var
str:array[0..M] of char;
procedure bubble(item:^char; n:integer);
var
a,b:integer;
t:char;
begin
for a:=1 to n-1 do
for b:=n-1 downto a do
if item[b-1]>item[b] then
begin
{}
t:=item[b-1];
item[b-1]:=item[b];
item[b]:=t
end
end;
procedure bubble1(item:^char; n:integer);
var
a,ssign,pass:integer;
t:char;
begin
ssign:=1;
pass:=0;
while ssign<>0 do
begin
ssign:=0;
pass:=pass+1;
for a:=0 to n-pass-1 do
if item[a]>item[a+1] then
begin
t:=item[a-1];
item[a-1]:=item[a];
item[a]:=t;
ssign:=1
end
end
end;
.
:
. N-1 , , .
d, c, a, b.
:
d, c, a, b
a, d, c, b
a, b, d, c
a, b, c, d
1/2*(N*N-N) . N-1 , N/2.
:
( );
3*N*(N-1)/4 ;
( ) 3*N*(N-1)/2 .
- N*N, N- . N, .
, . - - - - . , :
d, c, a, b
a, d, c, b
a, b, d, c
a, b, c, d.
. ( ), - . ., .
(, )
""
procedure insert(item:^char; n:integer);
var
a,b:integer; t:char;
begin
for a:=1 to n-1 do
begin
t:=item[a];
b:=a-1;
while (b>=0) and (t begin
item[b+1]:=item[b];
b:=b-1
end;
item[b+1]:=t
end
end;
d c a b
|
|
|
, . , N-1 , , 1/2*(N*N+N).
:
, :
: , , , , . .
. , .
:
, .
: , .
