Bài tập thực hành Cấu trúc dữ liệu và giải thuật

GVHD: Nguyễn Hữu Nhân Trang 1

THỰC HÀNH CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
CẤU TRÚC

// CauTrucNgay.cpp : Defines the entry point for the console
application.
//

#include "stdafx.h" #include <conio.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
// Khai bao kieu NGAY
struct ngay
{
int ngay;
int thang;
int nam;
};
typedef struct ngay NGAY;

// Nguyen mau ham
int KiemTraNamNhuan(int nam);
int TinhSoNgayTrongThang(int thang, int nam);
int KiemTraHopLe(NGAY ng);

printf("Ngay 1 la ngay thu %d trong nam %d\n",
TinhSTTNgayTrongNam(ng1), ng1.nam);
printf("Ngay 1 la ngay thu %d ke tu 1/1/1\n",
TinhSTTNgay(ng1));

Xuat(TinhNgayHomTruoc(ng1), "Ngay hom truoc cua
Ngay 1 la: ");
Xuat(TinhNgayHomSau(ng1), "Ngay hom sau cua Ngay 1
la: ");

int k;
printf("Nhap k: ");
scanf("%d", &k);

Xuat(TinhNgayTruoc(ng1, k), "Ngay truoc k ngay cua
Ngay 1 la: ");
Xuat(TinhNgaySau(ng1, k), "Ngay sau k ngay cua Ngay
1 la: ");

int n = TinhKhoangCach(ng1, ng2);
if (n < 0)
printf("Ngay 1 truoc ngay 2 %d ngay\n", -n);
else
printf("Ngay 1 sau ngay 2 %d ngay\n", n);
}
Bài tập thực hành Cấu trúc dữ liệu và giải thuật

GVHD: Nguyễn Hữu Nhân Trang 3
case 2:
if (KiemTraNamNhuan(nam) == 1)
songay = 29;
else
songay = 28;
break;
default:
songay = 0;
Bài tập thực hành Cấu trúc dữ liệu và giải thuật

GVHD: Nguyễn Hữu Nhân Trang 4

}

return songay;
} int KiemTraHopLe(NGAY ng)
{
int hople = 1;

if (ng.nam <= 0)
hople = 0;
else
if (ng.thang < 1 || ng.thang > 12)
hople = 0;
else
if (ng.ngay < 1 || ng.ngay >
TinhSoNgayTrongThang(ng.thang, ng.nam))


void Xuat(NGAY ng, char *thongbao)
{
printf("%s", thongbao);
printf("%d/%d/%d\n", ng.ngay, ng.thang, ng.nam);
}

int TinhSTTNgayTrongNam(NGAY ng)
{
int stt = 0;

// Tinh tong so ngay cac thang truoc do
for (int i=1; i<ng.thang; i++)
stt = stt + TinhSoNgayTrongThang(i, ng.nam);

stt = stt + ng.ngay;

return stt;
}

int TinhSTTNgay(NGAY ng)
{
int stt = 0;

// Tinh tong so ngay cac nam truoc do
for (int i=1; i<ng.nam; i++)
if (KiemTraNamNhuan(i) == 1)
stt = stt + 366;
else
stt = stt + 365;

}
else
{
kq.ngay = ng.ngay - 1;
kq.thang = ng.thang;
kq.nam = ng.nam;
}

return kq;
}

NGAY TinhNgayHomSau(NGAY ng)
{
NGAY kq;

int max = TinhSoNgayTrongThang(ng.thang, ng.nam);

Bài tập thực hành Cấu trúc dữ liệu và giải thuật

GVHD: Nguyễn Hữu Nhân Trang 7

if (ng.ngay == max) // Ngay cuoi cung cua thang
{
if (ng.thang == 12) // Thang cuoi cung cua nam
{
kq.nam = ng.nam + 1;
kq.thang = 1;
kq.ngay = 1;
}
else

Bài tập thực hành Cấu trúc dữ liệu và giải thuật

GVHD: Nguyễn Hữu Nhân Trang 8

for (int i=0; i<k; i++)
kq = TinhNgayHomSau(kq);

return kq;
}

int TinhKhoangCach(NGAY ng1, NGAY ng2)
{
return TinhSTTNgay(ng1) - TinhSTTNgay(ng2);
}

int SoSanh(NGAY ng1, NGAY ng2)
{
int kc = TinhKhoangCach(ng1, ng2);

if (kc > 0)
return 1;
else
if (kc < 0)
return -1;
else
return 0;
} Bài tập thực hành Cấu trúc dữ liệu và giải thuật

// Nguyen mau ham
void NhapDiem(DIEM &d);
void XuatDiem(DIEM d, char *thongbao);
float TinhKhoangCach(DIEM d1, DIEM d2);

int KiemTraHopLe(DIEM a, DIEM b, DIEM c);
void NhapTamGiac(TAMGIAC &tg);
void XuatTamGiac(TAMGIAC tg, char *thongbao);
float TinhChuVi(TAMGIAC tg);
float TinhDienTich(TAMGIAC tg);

void main()
Bài tập thực hành Cấu trúc dữ liệu và giải thuật

GVHD: Nguyễn Hữu Nhân Trang 10

{
TAMGIAC tg;

NhapTamGiac(tg);
XuatTamGiac(tg, "Toa do ba diem cua Tam giac:\n");

printf("Chu vi Tam giac = %.2f\n", TinhChuVi(tg));
printf("Dien tich Tam giac = %.2f\n", TinhDienTich(tg));
getch();
}

// Dinh nghia ham
void NhapDiem(DIEM &d)
{

float AB, AC, BC;

AB = TinhKhoangCach(tg.dA, tg.dB);
AC = TinhKhoangCach(tg.dA, tg.dC);
BC = TinhKhoangCach(tg.dB, tg.dC);

if (AB + AC > BC && AB + BC > AC && AC + BC > AB)
return 1;
else
return 0;
}

void NhapTamGiac(TAMGIAC &tg)
{
int hople = 1;

do
{
printf("Nhap toa do Diem A:\n");
NhapDiem(tg.dA);
printf("Nhap toa do Diem B:\n");
NhapDiem(tg.dB);
printf("Nhap toa do Diem C:\n");
NhapDiem(tg.dC);
hople = KiemTraHopLe(tg);
if (!hople)
printf("Tam giac khong hop le! Hay nhap
lai!");
}
while (!hople);

AB = TinhKhoangCach(tg.dA, tg.dB);
AC = TinhKhoangCach(tg.dA, tg.dC);
BC = TinhKhoangCach(tg.dB, tg.dC);

p = (AB + AC + BC) / 2;
S = sqrt(p * (p - AB) * (p - AC) * (p - BC));

return S;
}

Bài tập thực hành Cấu trúc dữ liệu và giải thuật

GVHD: Nguyễn Hữu Nhân Trang 13

// Diem.cpp : Defines the entry point for the console
application.
//

#include "stdafx.h" #include <stdio.h>
#include <math.h>
#include <conio.h>

// Khai bao kieu DIEM
struct diem
{
int x; // hoanh do
int y; // tung do

Xuat(TimDoiXungQuaOx(d1), "Toa do diem doi xung qua Ox
cua Diem 1: ");
Xuat(TimDoiXungQuaOy(d1), "Toa do diem doi xung qua Oy
cua Diem 1: ");
getch();
}

// Dinh nghia ham
void Nhap(DIEM &d)
{
printf("Nhap hoanh do x: ");
scanf("%d", &d.x);
printf("Nhap tung do y: ");
scanf("%d", &d.y);
}

void Xuat(DIEM d, char *thongbao)
{
printf("%s", thongbao);
printf("(%d, %d)\n", d.x, d.y);
}

float TinhKhoangCach(DIEM d1, DIEM d2)
{
float kq;

int dx = d1.x - d2.x;
int dy = d1.y - d2.y;

kq = sqrt((float)(dx*dx + dy*dy));

DIEM kq;

kq.x = -d.x;
kq.y = d.y;

return kq;
} Bài tập thực hành Cấu trúc dữ liệu và giải thuật

GVHD: Nguyễn Hữu Nhân Trang 16

// DaThuc.cpp : Defines the entry point for the console
application.
//

#include "stdafx.h" #include <stdio.h>
#include <math.h>
#include <conio.h>

#define MAX 100

// Khai bao kieu DATHUC
// anx^n + an-1x^n-1 + + a1x + a0
struct dathuc
{

Xuat(Tong(dt1, dt2), "Da thuc 1 + Da thuc 2 = ");
Xuat(Hieu(dt1, dt2), "Da thuc 1 - Da thuc 2 = ");
Xuat(Tich(dt1, dt2), "Da thuc 1 * Da thuc 2 = ");

Xuat(DaoHamCap1(dt1), "Dao ham cap 1 cua Da thuc 1 = ");

int k;
printf("Nhap k: ");
scanf("%d", &k);
Xuat(DaoHamCapk(dt1, k), "Dao ham cap k cua Da thuc 1 =
");

float x0;
printf("Nhap x0: ");
scanf("%f", &x0);
printf("Gia tri cua da thuc 1 tai x0 = %.2f la %.2f\n",
x0, TinhGiaTri(dt1, x0));
}

// Dinh nghia ham
void KhoiTaoDaThucRong(DATHUC &dt)
{
dt.n = 0;

for (int i=0; i<MAX; i++)
dt.a[i] = 0;
}

void Nhap(DATHUC &dt)
{

}

DATHUC Tong(DATHUC dt1, DATHUC dt2)
{
DATHUC kq;
KhoiTaoDaThucRong(kq);

if (dt1.n > dt2.n)
kq.n = dt1.n;
else
kq.n = dt2.n;

for (int i=0; i<=kq.n; i++)
kq.a[i] = dt1.a[i] + dt2.a[i];

while (kq.n>0 && kq.a[kq.n] == 0)
kq.n ;

Bài tập thực hành Cấu trúc dữ liệu và giải thuật

GVHD: Nguyễn Hữu Nhân Trang 19

return kq;
}

DATHUC Hieu(DATHUC dt1, DATHUC dt2)
{
DATHUC kq;
KhoiTaoDaThucRong(kq);


}
Bài tập thực hành Cấu trúc dữ liệu và giải thuật

GVHD: Nguyễn Hữu Nhân Trang 20 DATHUC DaoHamCap1(DATHUC dt)
{
DATHUC kq;
KhoiTaoDaThucRong(kq);

kq.n = dt.n - 1;

for (int i=kq.n; i>=0; i )
kq.a[i] = dt.a[i+1] * (i+1);

return kq;
}

DATHUC DaoHamCapk(DATHUC dt, int k)
{
DATHUC kq = dt;

for (int i=0; i<k; i++)
kq = DaoHamCap1(kq);

return kq;
}

float TinhGiaTri(DATHUC dt, float x0)

};
typedef struct data DATA;
struct node
{
DATA info;
struct node*pNext;
};
typedef struct node NODE;
struct list
{
NODE*pHead;
NODE*pTail;
};
typedef struct list LIST;

int CompareData(DATA info1, DATA info2);

void InitList(LIST &l);

bool IsEmptyList(LIST l);

void PrintList(LIST l, char *str);

NODE* CreateNode(DATA info);
Bài tập thực hành Cấu trúc dữ liệu và giải thuật

GVHD: Nguyễn Hữu Nhân Trang 22 NODE* GetNodePointer(LIST l, DATA info);


DATA RemoveAfter(LIST &l, NODE*q);

bool RemoveNode(LIST &l, DATA info);

void RemoveAll(LIST &l);

Bài tập thực hành Cấu trúc dữ liệu và giải thuật

GVHD: Nguyễn Hữu Nhân Trang 23

// 01. Hàm so sánh 2 biến kiểu cấu trúc cho trước
// Đầu vào: biến cấu trúc (info1) và biến cấu trúc (info2)
// Đầu ra: 0 (bằng nhau), -1 (info1 nhỏ hơn info2), 1 (info1
lớn hơn info2)
int CompareData(DATA info1, DATA info2)
{
if(info1.x<info2.x)
return -1;
if(info1.x>info2.x)
return 1;
return 0;
}
// 02. Hàm khởi tạo DSLK (rỗng)
// Đầu vào: tham chiếu đến DSLK cẩn khởi tạo (1)
// Đầu ra: Không có
void InitList(LIST &l)
{
l.pHead=NULL;
l.pTail=NULL;

// 05. Hàm tạo một node mới với dữ liệu cho trước
// Đầu vào: Dữ liệu của nút (info)
// Đầu ra: Con trỏ đến nút đó (trả về NULL nếu không tạo
được)
NODE*CreateNode(DATA info)
{
NODE*p=new NODE;
if(p!=NULL)
{
p->info=info;
p->pNext=NULL;
}
return p;
}
// 06. Hàm tìm nút đầu tiên trong DSLK cho trước có dữ liệu
cho trước
// Đầu vào: DSLK (l), dữ liệu của nút cần tìm (info)
// Đầu ra: Con trỏ đến nút tìm được (trả về NULL nếu
không tìm được)
NODE* GetNodePointer(LIST l, DATA info)
{
NODE *p = l.pHead;

while (p != NULL && CompareData(p->info, info) != 0)
p = p->pNext;

return p;
}
// 07. Hàm tìm nút có chỉ số (bắt đầu từ 0) cho trước
// Đầu vào: DSLK (l), chỉ số của nút cần lấy (index)

if (IsEmptyList(l))
return -1;

while (p != NULL && p != p)
{
pos++;
p = p->pNext;
}

if (p == p)
return pos;
else
return -1;
}
// 09. Hàm xác định con trỏ đến nút đứng trước của một nút
cho trước trong DSLK