Wednesday, April 27, 2016

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.

Bài tập hướng đối tượng với Java (số 8)

//Họ Tên: Trần Văn Linh
//MaSV:581597
//Lớp:K58QLTT

Đề:
1. Hãy xây dựng lớp DaGiac gồm có các thuộc tính
- Số cạnh của đa giác
- Mảng các số nguyên chứa kích thước các cạnh của đa giác
Các phương thức:
- Tính chu vi
- In giá trị các cạnh của đa giác.
2. Xây dựng lớp TamGiac kế thừa từ lớp DaGiac, trong đó viết đè các hàm tính chu vi và xây dựng thêm
phương thức kiểm tra tính hợp lệ 3 cạnh của tam giác, tính diện tích tam giác
3. Xây dựng một ứng dụng Java để nhập vào một dãy gồm n tam giác rồi in ra màn hình các cạnh của các tam giác có diện tích lớn nhất.
--------------------------------------------------------------------------------------------------------------------------

Giải:
//Lớp DaGiac

public class DaGiac
{
    protected int soCanh;
    protected int a[];
 
    public DaGiac()
    {
     
    }
    public DaGiac(int soCanh,int a[])
    {
        this.soCanh=soCanh;
        this.a=a;
    }
    public int tinhChuVi()
    {
        int cv=0;
        for(int i=0;i<this.soCanh;i++)
            cv=cv+a[i];
        return cv;
    }
    public void inCanh()
    {
        for(int i=0;i<this.soCanh;i++)
        {
            System.out.println("Canh thu "+(i+1)+" : "+this.a[i]);
        }
    }
}
//Lớp TamGiac
import java.util.Scanner;
public class TamGiac extends DaGiac
{
    TamGiac()
    {
        this.a=new int[3];
        this.soCanh=3;
    }
    public int  tinhChuVi()
    {
        int cv=0;
        for(int i=0;i<3;i++)
             cv=+a[i];
           
        return cv;
    }
    public boolean ktHopLe()
    {
        int A=this.a[0];
        int B=this.a[1];
        int C=this.a[2];
        if(A+B>C && A+C>B && B+C>A)
            return true;
        return false;
    }
    public double tinhDT()
    {
        int A=this.a[0];
        int B=this.a[1];
        int C=this.a[2];
        int P=(A+B+C)/2;
        return (double) Math.sqrt(P*(P-A)*(P-B)*(P-C));
    }
    public void nhap()
    {
        Scanner sc=new Scanner(System.in);
        for(int i=0;i<3;i++)
        {
            System.out.print("Nhap canh thu "+(i+1)+": ");
            this.a[i]=sc.nextInt();
        }
    }
}
//Lop test
import java.util.ArrayList;
public class Test
{
    public static void main(String[] args)
    {
        ArrayList<TamGiac> ds=new ArrayList<TamGiac>();
        for(int i=0;i<4;i++)
        {
            System.out.println("Nhap tam giac thu "+(i+1)+" :");
            TamGiac tg=new TamGiac();
            tg.nhap();
            ds.add(tg);
        }
        double max=0;
        int Max=0;
        for(int i=0;i<ds.size();i++)
            if(ds.get(i).ktHopLe())
            {
               if(ds.get(i).tinhDT()>max)
               {
                    max=ds.get(i).tinhDT();
                    Max=i;
               }
           }
        System.out.println("Tam Giac Co Dien tich lon nhat la: "+max+", cac canh cua tam giac nay : ");
        ds.get(Max).inCanh();
    }
 

}




Bài tập trình hướng đối tượng với Java (Số 7)

//Họ Tên: Trần Văn Linh
//MaSV:581597
//Lớp:K58QLTT

Đề :
Một công ty được giao nhiệm vụ quản lý các phương tiện giao thông gồm các loại: ô tô, xe máy, xe tải.
+ mỗi loại phương tiện giao thông cần quản lý: Hãng sản xuất, năm sản xuất, giá bán và màu.
+ Các ô tô cần quản lý: số chỗ ngồi, kiểu động cơ
+ Xe máy cần quản lý: công suất
+ Xe tải cần quản lý: trọng tải.
2. Xây dựng các lớp XeTai, XeMay, OTo kế thừa từ lớp PTGT.
3. Xây dựng các hàm để truy nhập (get), thay đổi (set) và hiển thị các thuộc tính của các lớp.
4. Xây dựng lớp QLPTGT cài đặt các phương thức thực hiện các chức năng sau:
- Nhập đăng ký phương tiện
- Tìm phương tiện theo màu hoặc năm sản xuất

--------------------------------------------------------------------------------------------------------------------------

Giải:/
//Lop PTGT
import java.util.Date;
public class PTGT
{
    private String hangSX;
    private int namSX;
    private double gia;
    private String mau;
 
    public PTGT()
    {
    }
    public PTGT(String hangSX,int namSX,double gia,String mau)
    {
        this.hangSX=hangSX;
        this.namSX=namSX;
        this.gia=gia;
        this.mau=mau;
    }
 
    public void setHangSx(String hangSX)
    {
        this.hangSX=hangSX;
    }
    public void setNamSx(int namSX)
    {
        this.namSX=namSX;
    }
    public void setGia(double gia)
    {
        this.gia=gia;
    }
    public void setMau(String mau)
    {
        this.mau=mau;
    }
 
    public String getHangSX()
    {
        return this.hangSX;
    }
    public int getNamSX()
    {
        return this.namSX;
    }
    public double getGia()
    {
        return this.gia;
    }
    public String getMau()
    {
        return this.mau;
    }
 
    public void hienThongTin()
    {
        System.out.println("Hang san xuat: "+this.hangSX);
        System.out.println("Nam san xuat: "+this.namSX);
        System.out.println("Gia : "+this.gia);
        System.out.println("Mau: "+this.mau);
     
    }

}
//Lop XeTai

public class XeTai extends PTGT
{
    private double trongTai;
    
    public XeTai()
    {
    
    }
    public XeTai(String hangSX,int namSX,double gia,String mau,double trongTai)
    {
        super(hangSX,namSX,gia,mau);
        this.trongTai=trongTai;
    }
    
    public void setTrongTai(double trongTai)
    {
        this.trongTai=trongTai;
    }
    public double getTrongTai()
    {
        return this.trongTai;
    }
    
    public void hienThongTin()
    {
        super.hienThongTin();
        System.out.println("Trong tai cua xe la: "+this.trongTai);
    }
}
//Lop Oto

public class Oto extends PTGT
{
    private int soCho;
    private String kieuDongCo;
    
    public Oto()
    {
    }
    public Oto(String hangSX,int namSX,double gia,String mau,int soCho,String kieuDongCo)
    {
        super(hangSX,namSX,gia,mau);
        this.soCho=soCho;
        this.kieuDongCo=kieuDongCo;
    }
    
    public void setSoChoNgoi(int soCho)
    {
        this.soCho=soCho;
    }
    public void setKieuDongCo(String kieuDongCo)
    {
        this.kieuDongCo=kieuDongCo;
    }
    
    public void hienThongTin()
    {
        super.hienThongTin();
        System.out.println("So Cho ngoi: "+this.soCho);
        System.out.println("Kieu dong co: "+this.kieuDongCo);
    }
}
//Lop XeMay

public class XeMay extends PTGT
{
    private double congSuat; 
    
    public XeMay(String hangSX,int namSX,double gia,String mau,double congSuat)
    {
        super(hangSX,namSX,gia,mau);
        this.congSuat=congSuat;
    }
    
    public void setCongSuat(double congSuat)
    {
        this.congSuat=congSuat;
    }
    public double getCongSuat()
    {
        return this.congSuat;
    }
    
    public void hienThongTin()
    {
        super.hienThongTin();
        System.out.println("Cong Suat: "+this.congSuat);
    }
}
//lop QuanLyPhuongTienGT
import java.util.Date;
import java.util.ArrayList;
import java.util.Scanner;
import java.text.DateFormat;
import java.text.SimpleDateFormat;
public class QuanLyPhuongTienGT
{
    private ArrayList<PTGT> ds=new ArrayList<PTGT>();
    
    public PTGT nhapOto(Scanner sc) 
    {
        System.out.print("Nhap hang san xuat: ");
        String hangSx=sc.nextLine();
        
        System.out.print("Nhap nam san xuat:");
        int namSX=sc.nextInt();
        
        System.out.print("Nhap gia xe:");
        double gia=sc.nextDouble();
        sc.nextLine();
        
        System.out.print("Nhap mau xe:");
        String mau=sc.nextLine();
        
        System.out.print("Nhap so cho ngoi:");
        int soCho=sc.nextInt();
        sc.nextLine();
        
        System.out.print("Nhap kieu dong co:");
        String kdc=sc.nextLine();
        
        return new Oto(hangSx,namSX,gia,mau,soCho,kdc);
    }
    public PTGT nhapXeMay(Scanner sc) 
    {
        System.out.print("Nhap hang san xuat: ");
        String hangSx=sc.nextLine();
        
        System.out.print("Nhap nam san xuat:");
        int namSX=sc.nextInt();
        
        System.out.print("Nhap gia xe:");
        double gia=sc.nextDouble();
        sc.nextLine();
        
        System.out.print("Nhap mau xe:");
        String mau=sc.nextLine();
        
        System.out.print("Nhap Cong Suat:");
        double congSuat=sc.nextDouble();
        sc.nextLine();
        
        return new XeMay(hangSx,namSX,gia,mau,congSuat);
    }
    public PTGT nhapXeTai(Scanner sc) 
    {
        System.out.print("Nhap hang san xuat: ");
        String hangSx=sc.nextLine();
        
        System.out.print("Nhap nam san xuat:");
        int namSX=sc.nextInt();
        
        System.out.print("Nhap gia xe:");
        double gia=sc.nextDouble();
        sc.nextLine();
        
        System.out.print("Nhap mau xe:");
        String mau=sc.nextLine();
        
        System.out.print("Nhap trong tai cua xe:");
        double trongTai=sc.nextDouble();
        sc.nextLine();
        
        return new XeTai(hangSx,namSX,gia,mau,trongTai);
    }
    public void  nhapDangKiPhuongTien(Scanner sc)
    {
        char c;
        int chon=0;
        while(true)
        {
            System.out.print("Ban muon nhap loai xe nao (1-XeTai,2-Xemay,3-Oto):");
            chon=sc.nextInt();
            sc.nextLine();
            switch(chon)
            {
                case 1:{
                    ds.add(nhapXeTai(sc));
                    break;
                }
                case 2:{
                    ds.add(nhapXeMay(sc));
                    break;
                }
                case 3:{
                    ds.add(nhapOto(sc));
                    break;
                }
                default:
                {
                    ds.add(nhapXeTai(sc));
                    break;
                }
            }
            System.out.println("Ban co muon nhap nua khong: (Y/N)");
            c=sc.nextLine().charAt(0);
            if(c=='N'||c=='n')
                break;
        }
    }
    public void timKiemTheoMau(Scanner sc)
    {
        System.out.print("Nhap mau can tim kiem:");
        String mauTk=sc.nextLine();
        for(int i=0;i<ds.size();i++)
        {
            String mau=ds.get(i).getMau();
            if(mau.equalsIgnoreCase(mauTk))
                ds.get(i).hienThongTin();
        }
    }
    public void timKiemTheoNamSX(Scanner sc)
    {
        System.out.print("Nhap nam  de tim kiem:");
        int nam=sc.nextInt();
        int tg=0;
        for(int i=0;i<ds.size();i++)
        {
           tg=ds.get(i).getNamSX();
           if(tg==nam)
                ds.get(i).hienThongTin();
        }
    }
    public static void main(String[] args)
    {
        QuanLyPhuongTienGT PT=new QuanLyPhuongTienGT();
        Scanner sc=new Scanner(System.in);
        PT.nhapDangKiPhuongTien(sc);
        PT.timKiemTheoMau(sc);
        PT.timKiemTheoNamSX(sc);
    }
}