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ớ.!

Read More

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ớ.!

Read More

Cài đặt hàng đợi sử dụng danh sách liên kết đơn .

Khi cài đặt hàng đợi bằng danh sách liên kết đơn mỗi một phần tử của hằng đợi sẽ được lưu trữ trong một nút có cấu trúc như trong danh sách liên kết đơn. Khi bổ sung vào hàng đợi ta bổ sung vào cuối danh sách, khi loại bỏ ta loại bỏ ở đầ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;
     infor(new):=x;
     link(new):=null;
2.{Bổ sung}
if F=null then
       begin
             F:=new;
             R:=new;
       end;
else
begin
    link(R):=new;
    R:=new;
end
3.Return

Cài đặt hàm trong ngôn ngữ lập trình C
//--------------------------------------
Đầu tiên ta có cấu trúc nút
typedef struct node NODE;
struct node
{
     typeDaTa infor;
     NODE *link;
}
//--------------------------------------------------
void  QINSERT(NODE *F,NODE *R,typeDaTa X)
{
      // tạo nút mới
      NODE *N;
      N=(NODE*)malloc(sizeof(NODE);
      N->infor=X;
      N->link=NULL;
   
      //Bổ sung
      if (F==NULL)
      {
           F=N;
           R=N;
      }
      else
       {
             R->link=N;
             R=N;
        }
}
B.Thủ tục loại bỏ một nút khỏi hàng đợi và trả về thông tin của nút đó.

Procedure   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ỏ}
    tg=infor(F);
    P:=F;
 
     if F=R then
                F:=R:=null;
     else
           F:=link(F);
3,{Thu hoi bo nho}
     P=>AVAIL;
4.QDELETE:=tg;
5.Return

Cài đặt hàm trong ngôn ngữ lập trình C

typeDaTa  QDELETE(NODE *F,NODE *R)
{
      NODE *P;
      typeDaTa  tg;
     //kiểm tra danh sách rỗng.
      if(F==NULL)
      {
             printf("Danh sách rỗng .!");
             return NULL;
      }
     P=F;
     tg=F->infor;
     F=F->link;
    free(P);//hủy nút
    return tg;//trả về giá trị thông tin của nút bị xóa
}

Read More