Sunday, May 15, 2016

Giải thuật thêm,xóa ,tim kiếm một nút vào danh sách liên kết đơn

  12:07:00 AM    1 comment
//Họ và tên :Trần Văn Linh
//MSV:581597
//Lớp:K58QLTT

 ---------------------------------------------------------------------------------
A.Giải thuật thêm một nút vào danh sách liên đơn
Bài này mình sẽ giới thiệu 3 trường hợp bổ sung trong danh sách liên kết đơn.
Mình sẽ dùng 2 biến con trỏ F, R là nút đầu tiên, nút cuối cùng của danh sách.

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

 TH1. Giải thuật bổ sung vào nút đầu tiên
 - Vào :Phần tử dữ liệu x
 -  Ra: Không có

procedure Insert(F,X)
1,{Tạo nút mới}
      new <=AVAIL;
    infor(new):=X;
    Link(new):=null;
2,{Bổ sung}
   Link(new):=F;
   F:=new;
3,{Kết thúc}
Return.

 TH2. Giải thuật bổ sung vào sau nút M
  -Vào :M,X
  -Ra: Không có

procedure Insert(F,M,X)
1,{Tạo nút mới}
      new <=AVAIL;
    infor(new):=X;
    Link(new):=null;
2,{Bổ sung}
 {Trường hợp danh sách rỗng}
  if F=null then
      F:=new;
  else
  begin
        Link(new):=Link(M);
        Link(M):=new;
  end
3,{Kết thúc}
Return.

 TH3. Giải thuật bổ sung vào nút cuối cùng

procedure Insert(F,R,M,X)
1,{Tạo nút mới}
      new <=AVAIL;
    infor(new):=X;
    Link(new):=null;
2,{Bổ sung}
 {Trường hợp danh sách rỗng}
  if F=null then
                    begin
                          F:=new;
                          R:=new;
  else
  begin
        Link(R):=new;
        R:=new;
  end
3,{Kết thúc}
Return. 

 B. Giải thuật tiềm kiếm một nút trong danh sách liên đơn khi biết trường thông tin.

 Vào :F,thông tin nút cần tìm kiếm 
 Ra: Nút cần tìm kiếm

  Function Search(F,X)
 1{Kiểm tra danh sách rỗng}
   if F=null
   begin
        write('Danh sách rỗng');
        return;{kết thúc}
   end
 2,{Tìm kiếm}
   P:=F;
   while P#null Do
   begin
        if infor(P)=X
         begin
              Q:=P;{nút tìm thấy}
              return;{Dừng vòng lặp,thay cho lệnh break trong C}
        end;
         P=Link(P);
   end
3,{Kiểm tra xem có tồn tại nút cần tìm không?}
 if Q=null
 begin
      write('Không tồn tại nút cần tìm kiếm.!');
      return;{Kết thúc}
 end
else
    Search:=Q;{Trả về nút được tìm thấy}
4,{Kết thúc}
Return.

C. Giải thuật xóa một nút có trường thông tin là x trong danh sách liên kết đơn.
Vào:F,X
Ra: Không có

 Procedure    Delete(F,X)
1{Kiểm tra danh sách rỗng}
   if F=null
   begin
        write('Danh sách rỗng');
        return;{kết thúc}
  end
2,{Tìm nút cần xóa}
 P:=F;
 while P# null Do
 begin
       if infor(P)=X then
            return;{Dừng vòng lặp,thay cho lệnh break trong C}
      Q:=P;
      P:=Link(P);{nút cần xóa}
 end
3,{xóa bỏ}
if P # null
begin
     if P=F then
           F=Link(F);
     else
     begin
          Link(Q):=Link(P);
     end
  P=>AVAIL;{Thu hồi bộ nhớ}
end
4,{Kết thúc}
Return.

Read More

Saturday, May 14, 2016

Chương trình chuyển một số nguyên dương thành xâu nhị phân sử dụng danh sách liên kết kép

  7:35:00 AM    No comments
//Họ Tên: Trần Văn Linh
//MaSV:581597
//Lớp:K58QLTT

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

//khai bao cau truc
struct node
{
int infor;
struct node *left;
struct node *right;
} *L=NULL,*R=NULL;

//khai bao ham
void Insert(int x);// chen mot nut
int Delete();//xoa mot nut
int empty();//kiem tra danh sach rong

//==chuong trinh chinh==
int main()
{
int n,thuong;
printf("Nhap so nguyen can chuyen sang dang nhi phan:");
do
{
scanf("%d",&n);
if(n<0)
printf("\nSo nguyen nhap phai duong,nhap lai: ");
}while(n<0);
thuong=n;
while(thuong)
{
Insert(thuong%2);
thuong/=2;
}
printf("\n%d chuyen sang dang nhi phan la:",n);
while(!empty())
printf("%d",Delete());
return 0;
}
//==Dinh nghia ham==
void Insert(int x)
{
struct node *N;
N=(struct node*)malloc(sizeof(struct node));
N->infor=x;
N->left=NULL;
N->right=NULL;
//bo sung vao dinh ngan xep
if(L==NULL)
{
L=N;
R=N;
}
else
{
N->right=L;
L->left=N;
L=N;
}
}
//-------------
int Delete()
{
int tg;
struct node *P;
if(L==NULL)
{
printf("Danh sach rong.!");
return 0;
}
tg=L->infor;
P=L;
if(L->right==NULL)
{
L=NULL;
}
else
{
L=L->right;
L->left=NULL;
}
free(P);
return tg;
}
//-------------
int empty()
{
if(L==NULL)
return 1;
return 0;
}
//-------------
Read More

Chương trình chuyển một số nguyên thành xâu nhị phân sử dụng danh sách liên kết đơn (ngăn xếp)

  5:36:00 AM    No comments
//Họ Tên: Trần Văn Linh
     //MaSV:581597
     //Lớp:K58QLTT

-------------------------------------------------------------------------------------------------------------------------
xaunhiphan.c
#include<stdio.h>
#include<stdlib.h>

    //khai bao cau truc
typedef struct node node;
struct node
{
int infor;
node *link;
} *T=NULL;

 //Khai bao ham
void push(int x);//Hàm bổ sung 
int pop();//Hàm xóa một nút
int empty();//Hàm kiểm tra danh sách rỗng

 //==Chuong trinh chinh==
int main()
{
int n,thuong;
printf("Nhap so nguyen can chuyen sang dang nhi phan:");
do
{
scanf("%d",&n);
if(n<0)
printf("\nSo nguyen nhap phai duong,nhap lai: ");
}while(n<0);
thuong=n;
while(thuong)
{
push(thuong%2);
thuong/=2;
}
printf("\n%d chuyen sang dang nhi phan la:",n);
while(!empty())
printf("%d",pop());
return 0;
}
//==Dinh nghia ham==
void push(int x)
{
node *N;
N=(node*)malloc(sizeof(node));
N->infor=x;
N->link=NULL;
//bo sung vao dinh ngan xep
N->link=T;
T=N;
}
//-------------
int pop()
{
int tg;
node *P;
if(T==NULL)
{
printf("Danh sach rong.!");
return 0;
}
P=T;
tg=T->infor;
T=T->link;
free(P);
return tg;
}
//-------------
int empty()
{
if(T==NULL)
return 1;
return 0;
}
Read More