Thứ Ba, 10 tháng 5, 2016

HĂNG ĐỢI VỚI DANH SÁCH LIÊN KẾT KÉP.

Danh sách liên kết kép là danh sách tuyến tính khi sử dụng cấu trúc lưu trữ là phân tán. Mỗi nút trong danh sách liên kết kép gồm có  3 trường :
       

     +, Left: Con trỏ trái chứa địa chỉ nút đứng trước
      +,Right: Con trỏ phải chứa địa chỉ nú đứng sau.
      +, INFOR: thông tin của phần tử dữ liệu




Khi cài đặt hàng đợi bằng danh sách liên kết kép thì phép bổ sung sẽ thực hiện ở nút cuối danh sách và loại bỏ ở nút đầu danh sách.



A. Thủ tục bổ sung một phần tử dữ liệu vào hàng đợi

Procedure    QINSERT(F,R,X)

1,{tạo nút mới}
new <=AVAIL;//để biểu thị việc cấp phát bộ nhớ cho new
INFOR(new):=X;
Left(new):=null;
Right(new):=null;
2,{Bổ sung}
if F=null  then
 F:=R:=new;
else
  begin
      Right(R):=new;
      Left(new):=R;
       R:=new;
  end
3.Return;

B.Thủ tục bổ sung loại bỏ một phần tử dữ liệu khỏi hằng đợi

Fucntion QDELETE(F,R)

1.{ Kiểm tra hàng đợi rỗng}
   if F=null  then
   begin
          Write("Hàng đợi rỗng");
          Return;
   end
2.{Loại bỏ}
P:=F;
tg:=INFOR(F);
{Trường hợp chỉ còn một nút}
if F=R then
     F:=R:=null;
else
begin
       F:=Right(F);
       Left(F):=null;
end
3.{Xóa bỏ nút thu hồi bộ nhớ }
P=>AVAIL;
4.QDELETE=tg;
5,Return;

Lưu ý : P=>AVAIL, P<=AVAIL để biểu thị việc thu hổi và cấp phát bộ nhớ.!

0 nhận xét:

Đăng nhận xét