Комбинаторные алгоритмы для программистов



             

Связанные списки - часть 2


Программа написана на языке программирования Turbo-Pascal}

uses crt; type TLink=^Link; Link=record v : integer; p, n : TLink end;

var i : integer; p, q, w : TLink; s1,s2,rs : TLink;

procedure Sort( sp : TLink; t : integer ); var temp : integer; begin q:=sp; while q^.n<>nil do begin q:=q^.n; p:=sp; while p^.n<>nil do begin if (p^.v-p^.n^.v)*t>0 then begin temp:=p^.v; p^.v:=p^.n^.v; p^.n^.v:=temp; end; p:=p^.n; end; end; end;

function CreatRndSpis(deep : integer):TLink; begin new(q); for i:=1 to deep do begin if i=1 then begin p:=q;q^.p:=nil; end; q^.v:=random(9999); new(q^.n); q^.n^.p:=q; q:=q^.n; end; q^.p^.n:=nil; dispose(q); CreatRndSpis:=p; end;

function CreatSortDawnSpis(deep : integer):TLink; begin if deep<9999 then begin new(q); for i:=1 to deep do begin if i=1 then begin q^.p:=nil;p:=q; end; q^.v:=random(round(9999/deep))+round(9999*(1-i/deep)); new(q^.n); q^.n^.p:=q; q:=q^.n; end; q^.p^.n:=nil; dispose(q); end else p:=nil; CreatSortDawnSpis:=p; end;

procedure Show( s : TLink; sp: integer ); var i : integer; begin p:=s; i:=1; while p<>nil do begin gotoxy(sp,i);write(' ' : 5); gotoxy(sp,i);writeln(p^.v); p:=p^.n; inc(i); end; end;

function min( c1, c2 : integer) : integer; begin case c1<c2 of true : min:=c1; false: min:=c2; end; end;

function CreatConcSortUpSpis( sp1, sp2 : TLink ) : TLink; begin q:=sp1;while q^.n<>nil do q:=q^.n; w:=sp2;while w^.n<>nil do w:=w^.n; new(p);

CreatConcSortUpSpis:=p; p^.p:=nil; while(w<>nil)and(q<>nil)do begin if(w<>nil)and(q<>nil)then begin p^.v:=min(q^.v,w^.v); case p^.v=q^.v of true : q:=q^.p; false: w:=w^.p; end; new(p^.n); p^.n^.p:=p; p^.n^.n:=nil; p:=p^.n; end; if(w=nil)and(q<>nil)then begin while q<>nil do begin p^.v:=q^.v;q:=q^.p; new(p^.n); p^.n^.p:=p; p^.n^.n:=nil; p:=p^.n; end; end; if(w<>nil)and(q=nil)then begin while w<>nil do begin p^.v:=w^.v;w:=w^.p; new(p^.n); p^.n^.p:=p; p^.n^.n:=nil; p:=p^.n; end; end; end; p^.p^.n:=nil; dispose(p); end;

begin clrscr; randomize; s1:=CreatRndSpis(15);Sort(s1,-1); s2:=CreatRndSpis( 5);Sort(s2,-1); rs:=CreatConcSortUpSpis(s1,s2); Show(s1,10); Show(s2,20); Show(rs,30); Sort(rs,-1); Show(rs,40); readln; end.




Содержание  Назад  Вперед