Chương trình ứng ngăn xếp với danh sách liên kết đơn bằng C

#include<stdio.h>
#include<stdlib.h>

//Khai báo cấu trúc 1 nút
struct node
{
int infor;
struct node *link;
}*T=NULL; //Khởi tạo T

// Khai báo hàm
void Push(int X);
int Pop();
int Empty();

// ===Chuong Trinh Chinh===
int main()
{
     // Bổ sung vào ngăn xếp
        Push(1);
        Push(2);
        Push(3);
        Push(4);
        Push(5);

//Hiện thị thông tin của ngăn xếp
printf("Cac so trong danh sach la: \n");
while(!Empty())
printf("%d\t\t",Pop());
return 0;
}
// ==Định nghĩa hàm
// Hàm bổ sung một phần tử vào ngăn xếp
void Push(int X)
{
struct node *N;
// Cấp phát bộ nhớ
N=(struct node*)malloc(sizeof(struct node));
N->infor=X;
N->link=NULL;

// Bổ sung
N->link=T;
T=N;

}
//Hàm loại bỏ một 1 nút khỏi ngăn xếp và trả về thông tin ở nút đó
int Pop()
{
int tg;
struct node *P;

if(T==NULL){
printf("Ngan xep rong! ");
return 0;
}

tg=T->infor;
P=T;
T=T->link;
free(P); //Thu hồi bộ nhớ ,hủy nút

return tg;
}
//Hàm kiểm tra danh sách rỗng
int Empty()
{
if(T==NULL)
return 1;
return 0;

}

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

Ngăn xếp cài đặt bằng danh sách liên kết đơn

Ngăn xếp là danh sách tuyến tính , mà phép bổ sung và loại bỏ thực hiện theo nguyên tắc vào sau ra trước. Khi cài đặt ngăn xếp bằng danh sách liên kết đơn phần tử đỉnh của ngăn xếp chính là nút đầu tiên của danh sách liên kết. Phép bổ sung và loại bỏ được thực hiện ở vị trí này.

1, Giải thuật bổ sung một phần tử vào ngăn xếp:

Procedure    Push(var T,X)
1,{Tạo một node mới có infor là X}
new <= AVAIL;
infor(new):=x;
link(new):=x;
2,{Bổ sung}
link(new):=T;
T:=new;
return.
// Chuyển sang hàm trong C;
Ban đầu ta có cấu trúc của node là:

typedef struct node NODE;
struct node
{
         int  infor;
        NODE *link;
};
// -------------------
void Push(NODE *T,int x)
{
       //tạo một nút mới
        NODE *N;
        N=(NODE*) malloc(sizeof(NODE));
        N->infor=x;
        N->link=NULL;
        //bổ sung
        N->link=T;
        T=N;
}

2, Giải thuật loại bỏ 1 phần tử khỏi ngăn xếp

Function   POP(var T)
1,{Kiểm tra ngăn xếp rỗng }
   if T=NULL then
   begin
       write('Ngan xep rong');
        return ;
   end
2,{Loại bỏ}
P:=T;
tg:==infor(T);
T:=link(T);
P=>AVAIL;
POP:=tg;
Return.

//Chuyen sang hàm trong c
//Ban đầu ta cũng có cấu trúc một nút như bên trên 
int POP(NODE *T)
{
       NODE *P:
       P=T;
       int tg=0;
      //Kiểm tra ngăn xếp rỗng

       if(T==NULL)
       {
                printf("Ngăn xếp rỗng.!");
                return 0;
       }
     
       tg=T->infor;//lấy thông tin của nút đỉnh 
       T=T->link;//cho T trỏ tới nút tiếp theo
       free(P);//xóa  bỏ nút đỉnh
       return tg;//trả về thông tin của nút bị loại bỏ
}
P=>AVAIL, P<=AVAIL để biểu thị việc thu hổi và cấp phát bộ nhớ.!
Lưu ý: với cách cài đặt này T phải là biến toàn cục vì trong ngôn ngữ C không có kiểu tham chiếu mà chỉ có tham trị. Khi truyền theo giá trị thì biến sẽ không bị thay đổi khi.

Read More