4) Trình bày giải thuật bổ sung 1 nút mới có chứa dữ liệu X vào trước nút trỏ bởi Q trong danh sách móc nối 2 chiều với: Pdau trỏ vào phần tử đầu, Pcuoi trỏ vào phần tử cuối, mỗi nút có các trường: Data, P_Trai, P_Phai.

Bài làm:

Procedure Insert (Pdau, Pcuoi, Q, X)

New(p); //Tạo nút mới

Data(p):= X;

If Pcuoi := Null then //Danh sách rỗng

P_trai(p) := P_Phai(p) := Null;

Pdau := Pcuoi := p;

Return

End ;

If Q = Pdau then begin //Q trỏ tới nút cực trái

P_Trai(p) := null;

P_Phai(p) := Q;

P_Trai(p) := p;

Pdau :=p;

Return

End ;

P_Trai(p) := P_Trai(Q); //Bổ sung vào giữa

P_Phai(p) := Q;

P_Trai(Q) := p;

P_Phai(P_Trai(p)) :=p;

Return.

5) Trình bày giải thuật loại bỏ nút trỏ bởi M trong danh sách móc nối 2 chiều với : Pdau trỏ vào phần tử đầu, Pcuoi trỏ vào phần tử cuối, mỗi nút có các trường: Data, P_Trai, P_Phai.

Bài làm:

Procedure Delete(Pdau, Pcuoi, M)

If Pcuoi = null then begin //Trường hợp danh sách rỗng

Write (“Danh sach rong”);

Return

End;

Case //Loại bỏ

Pdau := Pcuoi; //Danh sách chỉ có 1 nút và M trỏ tới nút đó

Pdau := Pcuoi := null

M: = Pdau //Phần tử đầu bị loại

Pdau := P_Phai(Pdau);

P_Trai(Pdau) := null;

M := Pcuoi //Phần tử cuối bị loại

Pcuoi := P_Trai(Pcuoi) ;

P_Phai(Pcuoi) := null ;

Else

P_Phai(P_Trai(M)) := P_Phai(M) ;

P_Trai(P_Phai(M)) := P_Trai(M) ;

End case;

Dispose(M) ;

Return.