Thứ Ba, 10 tháng 5, 2016

NGĂN XẾP VỚI DANH SÁCH LIÊN KẾT KÉP

Khi cài đặt ngăn xếp bằng danh sách liên kết kép , mỗi phần tử của ngăn xếp sẽ được lưu trữ trong một nút có cấu trúc nút trong danh sách liên kết kép.
        
       +,Left: Con trỏ trái chứa địa chỉ nút đứng trước
      +, Right: Con trỏ phải chứa địa chỉ nút đứng sau.
      +, INFOR: thông tin của phần tử dữ liệu

Với cách lưu trữ này nút đỉnh ngăn xếp chính là nút đầu tiên của danh sách. Do đó phép loại bỏ, bổ sung sẽ thực hiện ở nút đầu danh sách .







A. Thủ tục bổ sung một phần tử vào ngăn xếp.

Procedure   PUSH(T,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 T=null  then
    T:=new;
else
  begin
       Right(new):=T;
       Left(T):=new;
       T:=new;
  end
3.Return;

B. Thủ tục loại bỏ một phần tử khỏi ngăn xếp

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