ACM算法集5
|
十五、数据结构相关算法
1．链表的定位函数loc(I:integer):pointer; {寻找链表中的第I个结点的指针} procedure loc(L:linklist; I:integer):pointer; var p:pointer; j:integer; begin p:=L.head; j:=0; if (I>=1) and (I<=L.len) then while j<I do begin p:=p^.next; inc(j); end; loc:=p; end; 2．单链表的插入操作 procedure insert(L:linklist; I:integer; x:datatype); var p,q:pointer; begin p:=loc(L,I); new(q); q^.data:=x; q^.next:=p^.next; p^.next:=q; inc(L.len); end; 3．单链表的删除操作 procedure delete(L:linklist; I:integer); var p,q:pointer; begin p:=loc(L,I-1); q:=p^.next; p^.next:=q^.next; dispose(q); dec(L.len); end; 4．双链表的插入操作（插入新结点q） p:=loc(L,I); new(q); q^.data:=x; q^.pre:=p; q^.next:=p^.next; p^.next:=q; q^.next^.pre:=q; 5．双链表的删除操作 p:=loc(L,I); {p为要删除的结点} p^.pre^.next:=p^.next; p^.next^.pre:=p^.pre; dispose(p); 关键路径（最长路经）： var a,b:array [1..10,1..10] of integer; n,last,out:integer; q,c:array [1..10] of integer; o:set of 1..10; procedure init; var i,j:integer; begin readln(n); for i:=1 to n do for j:=1 to n do read(a[i,j]); last:=0; o:=[]; out:=0; b:=a; end; procedure sort; var i,j:integer; p:boolean; begin while out<>n do begin for i:=1 to n do if not (i in o) then begin p:=true; for j:=1 to n do if a[j,i]=1 then begin p:=false; break; end; if p then begin inc(last); q[last]:=i; inc(out); o:=o+[i]; fillchar(a[i],sizeof(a[i]),0); end; end; end; end; procedure work_1; var i,j,t,k:integer; begin a:=b; c[1]:=0; for i:=1 to n do begin k:=0; for j:=1 to i-1 do if (a[q[j],q[i]]>0) and (a[q[j],q[i]]+c[q[j]]>k) then k:=a[q[j],q[i]]+c[q[j]]; c[q[i]]:=k; end; end; procedure work_2; var i,j,k:integer; begin writeln(q[n]); for i:=n-1 downto 1 do begin k:=maxint; for j:=i+1 to n do if (a[q[i],q[j]]>0) and (c[q[j]]-a[q[i],q[j]]<k) then k:=c[q[j]]-a[q[i],q[j]]; if c[q[i]]=k then writeln(q[i],' '); c[q[i]]:=k; end; end; begin init; sort; work_1; work_2; end. |