Bài tập Cấu trúc dữ liệu - Giải bằng Passcal

BÀI TẬP CẤU TRÚC DỮ LIỆU BÀI 1_3. {---------------TRON 2 DANH SACH ----------} Procedure MergerList(L1,L2:List;Var L:List); Var Q,P,T: List; Begin sapxep(L1); sapxep(L2); P:=first(L1); { CACH 1: while Pend_L(L1) do begin insert_L(retrieve(P,L1),End_L(L),L); P:=P^.next; end; Q:=L2; while Qend_L(L2) do begin T:=first(L); while (Tnil) and (retrieve(T,L)<retrieve(Q,L2)) do T:=T^.next; insert_L(retrieve(Q,L2),T,L); Q:=Q^.next; end; } P:=First(L1);q:=FIRST(L2); while (PEnd_L(L1)) and (QEnd_L(L2)) do if retrieve(P,L1)<Retrieve(Q,L2) then begin insert_L(retrieve(P,L1),End_L(L),L); P:=P^.next; end else begin insert_L(retrieve(Q,L2),End_L(L),L); Q:=Q^.next; end ; while Pend_L(L1) do begin insert_L(retrieve(P,L1),End_L(L),L); P:=P^.next; end; while Qend_L(L2) do begin insert_L(retrieve(Q,L2),End_L(L),L); Q:=Q^.next; end; End; {---------------TRON 2 DANH SACH ----------} Procedure MergerList(L2:List;Var L1:List); Var Q,P,T: List; Begin Q:=first(L2); while Qend_L(L2) do begin T:= L1^.next; while (Tnil) and (retrieve(T,L1)<retrieve(Q,L2)) do T:=T^.next; insert_L(retrieve(Q,L2),T,P); Q:=Q^.next; end; End; {--------TRON N DANH SACH ---------} Procedure Merger_nl(N_List:mang; m: integer; Var L:List); Var i:integer; Begin L:=N_List[1]; for i:=2 to m do mergerlist(N_List[i],L); End; {-------- NHAP N DANH SACH -------} Procedure READ_NL(Var N_List:mang); Var j:integer; Begin write('Co bao nhieu danh sach can tron: ');readln(m); for j:=1 to m do begin makenull(N_List[j]); writeln('------- DANH SACH THU ',j,' ------'); readlist(N_List[j]); sapxep(N_List[j]); WRITELN; end; End; BÀI 1_5: uses crt; Type Elementype=integer; Position=^List; List=record heso,somu:elementype; next:Position; end; Var A, B, C: position; {--------THEM PHAN TU VAO DA THUC --------------} Procedure Insert(c,e:elementype; Var A: position); Var Q,P:position; Begin new(P);p^.heso:=c;P^.somu:=e;P^.next:=nil; {tao nut tam} Q:=A; while (Q^.nextnil) and (Q^.next^.somu>e) do Q:=Q^.next; If Q^.next=nil then Q^.next:=P else if Q^.next^.somu=e then Q^.next^.heso:=Q^.next^.heso+C else begin P^.next:=Q^.next; Q^.next:=P; end; End; {---------- NHAN DA THUC -----------} Procedure Add(D1,D2: position; Var P:position); Var p1, p2: Position;x,y:elementype; Begin p1:=first(D1);p2:=first(D2); makenull(P); while (P1end_L(D1)) and (P2end_L(D2)) do if p1^.next^.somu>P2^.next^.somu then begin insert(P1^.next^.heso,P1^.next^.somu,P); P1:=P1^.next; end else if p1^.next^.somu<P2^.next^.somu then begin insert(P2^.next^.heso,P2^.next^.somu,P); P2:=P2^.next; end else begin x:=P1^.next^.heso+P2^.next^.heso; y:=P1^.next^.somu; insert(x,y,P); P1:=P1^.next;P2:=P2^.next; end; while P1end_L(D1) do begin insert(P1^.next^.heso,P1^.next^.somu,P); P1:=P1^.next; end; while P2end_L(D2) do begin insert(P2^.next^.heso,P2^.next^.somu,P); P2:=P2^.next; end; End ; {--------- TINH TONG HAI DA THUC ----------} Procedure SUM_DT(A, B: Position; Var C: Position); Var T, K : Position; Begin makenull(C); T:=A; while T^.nextnil do begin insert(T^.next^.heso,T^.next^.somu,C); T:=T^.next; end; K:=B; while K^.nextnil do begin insert(K^.next^.heso,K^.next^.somu,C); K:=K^.next; end; End; {---------- NHAN HAI DA THUC ------------} Procedure Nhan_DT(A: Position; B: Position; Var C: Position); Var T1,T2: Position; D:Position;mu,he:elementype; Begin T1:=first(A);makenull(C); While T1end_l(T1) do begin makenull(D); T2:=first(B); while T2end_l(T2) do begin he:=T1^.next^.heso*T2^.next^.heso ; mu:=T1^.next^.somu+T2^.next^.somu; insert(he,mu,D); T2:=T2^.next; end; add(D,C,C); T1:=T1^.next; end; End; {----------DAO HAM CUA DA THUC ----------} Function DaoHam(A: Position):Position; Var K, P, Q: Position; Begin makenull(K); P:=K; Q:=A; while Q^.nextnil do begin new(P^.next); P^.next^.heso:=Q^.next^.heso*Q^.next^.heso; P^.next^.somu:=Q^.next^.somu-1; Q:=Q^.next; P:=P^.next; end; daoham:=k; End; BÀI 1_6: THỰC HIỆN CỘNG 1 VÀO DÃY SỐ NHỊ PHÂN Type b=0..1; Position=^Cell; Cell=Record bit:0..1; next:Position; end; Procedure INCREMENT(Var Bnumber: Position; Q: Position); Var K,P: position; Begin P:=Bnumber; while P^.nextQ do P:=P^.next; if P=Bnumber then begin new(K); K^.bit:=1; K^.next:=bnumber^.next; Bnumber^.next:=k; end else if P^.bit=0 then P^.bit:=1 else begin P^.bit:=0; increment(Bnumber,P); end; End; BÀI 1_9 Const max_T=100; Type Elementype= char; Node=integer; Tree = Record label_T: array[1..max_t] of elementype; Parent: array[1..max_t] of Node; max_node:integer; end; Var T: Tree; {----- CHIEU CAO CUA CAY -------} Function Max(a,b:node):node; Begin if a>b then max:=a else max:=b; end; Function Height(n:node;T: Tree): integer; Var h:integer;m:node; Begin if empty(T) then writeln('Cay rong!') else begin h:=0; m:=LEFTMOST_CHILD(n,T); while m0 do begin h:=max(h,height(m,T)); m:=RIGHT_SIBLING(m,T); end; height:=h+1; end; end; BÀI 2_2 {----- DUYET DUONG DI CUA 1 NUT VE GOC ------} Procedure DD(m:node;VAR q: integer; Var A: mang;T:Tree); Var k: node;j:integer; Begin k:=T.parent[m]; j:=0; while kparent_T(Root(T),T) do begin a[j]:=k; k:=T.parent[k]; j:=j+1; end;q:=j-1; End; {------- KIEM TRA M CO O BEN ;TRAI N KHONG ----------} Function ON_LEFT(m,n: node; T:Tree):boolean; Var i,j,q,p:integer;kt:boolean;A,B:mang; Begin kt:=false; if T.parent[m] = T.parent[n] then if n<m then kt:=true else kt:=false else begin dd(m,p,A,t); dd(n,q,B,t); i:=0;j:=0; while a[i]b[j] do if a[i]>a[j] then i:=i+1 else j:=j+1; if a[i-1]<b[j-1] then kt:=true else kt:=false; end; ON_LEFT:=kt; End; {--------- KIEM TRA M CO O BEN PHAI N --------} Function ON_RIGHT(m,n: node; T:Tree):boolean; Var i,j,q,p:integer;kt:boolean;A,B:mang; Begin kt:=false; if T.parent[m] = T.parent[n] then if n<m then kt:=true else kt:=false else begin dd(m,p,A,t); dd(n,q,B,t); i:=0;j:=0; while a[i]b[j] do if a[i]<a[j] then i:=i+1 else j:=j+1; if a[i-1]>b[j-1] then kt:=true else kt:=false; end; ON_right:=kt; End; {--------- M LA TO TIEN CUA N ---------} Function P_ANCESTOR(m,n:node;T:Tree):boolean; Var i,j,p: integer; tim:boolean;A:mang; Begin dd(n,p,A,T);tim:=false; i:=0; while (i<p) and (tim=false) do if a[i]=m then tim:=true else i:=i+1; P_ANCESTOR :=tim; End; {---------- KIEM TRA M CO PHAI LA HAU DUE CUA N KHONG -------} Function P_Descendant(m,n:node;T:Tree):boolean; Var i,j,p: integer;A:mang; tim:boolean; Begin tim:=false; dd(m,p,A,T); i:=0; while (i<=p) and (tim=false) do if a[i]=n then tim:=true else i:=i+1; P_DESCENDANT:=tim; End; BÀI 2_3 {--------- TO TIEN GAN NHAT CUA M VA N --------} Procedure TOTIEN(m,n: node; Var TT: node; T: Tree); Var a,b: mang; i,j,q,p:integer;k:node; Begin if empty(T) then writeln('Cay rong!') else begin tt:=0; {---- duyet duong di cua m ve goc cay ----} k:=T.parent[m]; i:=0; while kparent_T(Root(T),T) do begin a[i]:=k; k:=T.parent[k]; i:=i+1; end; p:=i-1; if not kiemtra(n,p,A) then begin {---- duyet duong di cua n ve goc cay ----} k:=T.parent[n]; j:=0; while kparent_T(Root(T),T) do begin b[j]:=k; k:=T.parent[k]; j:=j+1; end; { --- Tim to tien ----} q:=j-1; i:=0; while i<=p do begin j:=0; while (a[i]a[j]) and (j<=q) do j:=j+1; if (a[i]=a[j]) and (j<=q) then begin tt:=a[i] ; i:=p+1; end else begin tt:=0; i:=i+1; end; end; end; end;end; BÀI 2_4 {-------- DUYET CAY THEO MUC -------} Procedure With_Order(n:integer; T: Tree); Var q: Queue; L: List; i,m: integer; Begin ENQUEUE(ROOT(T),Q); while not empty_Q(Q) do begin i:=front(Q); DEQUEUE(Q); insert_L(i,End_L(L),L); m:=LEFTMOST_CHILD(n,T); while m0 do begin ENQUEUE(m,Q); m:=RIGHT_SIBLING(m,T); end; end; End; BÀI 2_9 {---------- M LA TO TIEN CUA N ? -------} Function IS_ANCESTOR(m,n: node; L1, L2: List):boolean; Var p1, q1, p2,q2: node; Begin p1:=Locate(m,L1); ; q1:=Locate(n,L1); p2:=Locate(m,L2); q2:=Locate(n,L2); if (p1q2) then IS_ANCESTOR:=true else IS_ANCESTOR:=false; End;