Bài giảng Giải thuật

Ví dụ Đa thức được bd dưới dạng ds nối đơn Coef: chứa hệ số khác 0 của số hạng đa thức Exp: chứa số mũ tương ứng Link: liên kết tới nút tiếp theo A(x)=4x10 – 2x3 + 6 B(x)=-6x10 + 8x6 + 2x3 + 5x Giải thuật Exp(p)=Exp(q): cộng 2 giá trị Coef ở 2 nút đó, nếu khác 0 tạo ra nút mới. Exp(p)>Exp(q) và ngược lại: sao chép nút tại p Nếu 1 trong 2 ds kết thúc trước: copy toàn bộ phần còn lại Procedure Attach(H, M, d) Begin New(Temp) Temp^.Coef:=H; Temp^.Exp:=M; d^.link:=Temp; d:=temp; end Procedure PADD(A, B, C) Begin p:=A; q:=B; New(C); d:=c; While (pnil) and (qnil) do if (p^.Exp=q^.Exp) then begin x:=p^.Coef + q^.Coef; if x0 then Attach(x, p^.Exp, d) p:=p^.Link; q:=q^.Link; end else if p^.Data>q^.Data then begin Attach(p^.Coef, p^.Exp, d); p:=p^.Link; end else begin Attach(q^.Coef, q^.Exp, d); p:=p^.Link; end While p nil do Begin Attach(p^.Coef, p^.Exp, d); p:=p^.Link; End While q nil do Begin Attach(q^.Coef, q^.Exp, d); q:=q^.Link; End d^.link:=nil; T:=c; c:=c^.link; dispose(T); End {of procedure} 3. Danh sách nối kép LPTR: con trỏ trái, trỏ tới nút đứng trước RPTR: con trỏ phải, trỏ tới nút đứng sau INFO: dữ liệu Nút cực trái, nút cực phải Procedure DOUBIN(L, R, M, X) {Bổ sung 1 nút mới chứa dl X vào trước nút trỏ bởi M} Begin {tạo nút mới} New(T); T^.info:=X; {ds rỗng} if R=nil then begin T^.Lptr:=nil; T^.Rptr:=nil L:=R:=T; end; {M trỏ tới nút cực trái} If (M=L) then begin T^.Lptr:=nil; T^.Rptr:=M; M^.Lptr:=T; L:=T; end; {Bổ sung vào giữa} T^.Lptr:=M^.Lptr; T^.Rptr:=M; M^.Lptr:=T; M^.Lptr.Rptr:=T; End Procedure Double(L, R, M) {Loại bỏ nút M khỏi danh sách trỏ bởi L và R} Begin {Trường hợp ds rỗng} If R = nil then Begin write(‘ds rỗng’); halt; end; {Loại bỏ} Case L=R: {ds chỉ có 1 nút và M trỏ tới nút đó} L:=R:=nil; M=L: {nút cực trái bị loại} L:=L^.Rptr; L^.Lptr:=nil; M=R: {nút cực phải bị loại} R:=R^.Lptr; R^.rptr:=nil; else M^.Lptr.Rptr:=M^.Rptr; M^.Rptr.Lptr:=M^.Lptr; End case Dispose(M); End.