Giai Thuat NC

1.
Đồ thị
#include <iostream>
#include <fstream>
using namespace std;
#define MAX 100
struct Graph{
int n;
int a[MAX][MAX]; };
void input(Graph &G){
ifstream fi(" ");
if (fi.is_open() == true){
fi >> G.n;
for (int i = 0; i < G.n; i++)
for (int j = 0; j < G.n; j++)
fi >> G.a[i][j];
}else{cout << "Doc file khong thanh cong!"; }
}
void output(Graph G){
cout << "Tong so canh la: " << G.n << endl;
for (int i = 0; i < G.n; i++){
for (int j = 0; j < G.n; j++)
cout << G.a[i][j] << " ";
cout << endl;
}}
// Tìm đường đi ngắn nhất
void dijkstra(Graph G, int bd, int kt){
int d[MAX], truoc[MAX], u;
int sau[MAX] = {0};
// khởi tạo
for (int v = 0; v < G.n; v++){
d[v] = G.a[bd][v];
truoc[v] = bd;
}
d[bd] = 0;
sau[bd] = 1;
for (int i = 0; i < G.n - 1; i++){
int min = 100;
for (int v = 0; v < G.n; v++){
if (sau[v] == 0 && d[v] < min) {
u = v;
min = d[v];
}}
sau[u] = 1;
for (int v = 0; v < G.n; v++){
if (sau[v] == 0 && d[v] > d[u] + G.a[u][v]) {
d[v] = d[u] + G.a[u][v];
truoc[v] = u;
}}}
// in đường đi
if (d[kt] == 100){cout << "Khong co duong di!" << endl;
}else{
u = kt;
while (u != bd){
cout << u << " <-- ";
u = truoc[u];}
cout << bd << endl;
cout << "Do dai duong di: " << d[kt] << endl;
}}
int main(){
Graph G;
input(G);
output(G);
int bd, kt;
do{
cout << "Nhap dinh bat dau: ";
cin >> bd;
} while (bd < 0 || bd >= G.n);
do{
cout << "Nhap dinh ket thuc: ";
cin >> kt;
} while (kt < 0 || kt >= G.n);
dijkstra(G, bd, kt);
return 0;
}
2. Mảng
#include <iostream>
#include <string.h>
#include <iomanip>
#define Max 100
struct Sinhvien{
int masv;
string tensv;
string lop;
float dtk;
};
typedef Sinhvien sv;
int solg(int n){

do{
cout << "Nhap tong so luong sinh vien: ";
cin >> n;
} while (n <= 0);}
void nhap(Sinhvien sv[], int n){

for (int i = 0; i < n; i++){
cout << "Nhap tt sv " << i + 1 << endl;
cout << "Nhap ma sinh vien: ";
cin >> sv[i].masv;
cout << "Nhap ten sinh vien: ";
cin >> sv[i].tensv;
cout << "Nhap lop sinh vien: ";
cin >> sv[i].lop;
do{
cout << "Nhap diem tong ket sinh vien: ";
cin >> sv[i].dtk;
} while (sv[i].dtk < 0 || sv[i].dtk > 10);
}}
void xuat(Sinhvien sv[], int n){
for (int i = 0; i < n; i++)
cout << i + 1 << setw(10) << sv[i].masv << setw(10) << sv[i].tensv <<
setw(10) << sv[i].lop << setw(10) << sv[i].dtk << endl;
}
void selectionsorf(Sinhvien sv[], int n){
int min = 0, i, j;
for (i = 0; i < n - 1; i++){
min = i;
for (j = i + 1; j < n; j++){
if (sv[j].dtk < sv[min].dtk)
min = j; }
swap(sv[min], sv[i]);
}}
void Bubblesoft(Sinhvien sv[], int n){
int i, j;
for (i = 0; i < n; i++){
for (j = n - 1; j > i; j--){
if (sv[j].dtk < sv[j - 1].dtk) {
swap(sv[j], sv[j - 1]);
}}}}
void insertionsort(Sinhvien sv[], int n){
int p, i;
Sinhvien x;
for (i = 1; i < n; i++){
x = sv[i];
p = i - 1;
while (p >= 0 && sv[p].dtk > x.dtk){
sv[p + 1] = sv[p];
p--;}
if (p != i - 1) {
sv[p + 1] = x;
}}}
void quicksort(Sinhvien sv[], int left, int right){
int i, j;
Sinhvien x = sv[(left + right) / 2];
i = left;
j = right;
while (i <= j){
while (sv[i].dtk < x.dtk)
i++;
while (sv[j].dtk > x.dtk)
j--;
if (i <= j){
swap(sv[i], sv[j]);
i++;
j--;
}}
if (left < j){ quicksort(sv, left, j);}
if (i < right) { quicksort(sv, i, right); }
}
int BnSearch(Sinhvien sv[], int n, float x){

int left = 0, right = n-1, mid;
do{
mid = (left+right)/2;
if (sv[mid].dtk==x)
return mid;
else if (sv[mid].dtk<x) left = mid + 1;
//tim o nua ben phai
else right = mid - 1;
}while(left<=right);
return -1;
}
int main(){
Sinhvien sv[Max];
int n = solg(n);
nhap(sv, n);
cout << "STT" << setw(10) << "Ma" << setw(10) << "Ten" << setw(10) <<
"Lop" << setw(10) << "DTK" << endl;
xuat(sv, n);
*selectionsorf(sv, n);
xuat(sv, n);
*Bubblesoft(sv, n);
xuat(sv, n);
*insertionsort(sv, n);
xuat(sv, n);
*int left = 0;
int right = n - 1;
quicksort(sv, 0, n - 1);
xuat(sv, n);
*int x;
cout << "\nNhap diem can tim: ";
cin >> x;
int pos = BnSearch(sv,n,x);
if (pos==-1)
cout << "Khong co diem can tim!";
else{
cout << "Vi tri tim duoc:\n";
//in cac vi tri ben trai cua pos neu co cung gia tri x
int t = pos;
while(t>=0 && sv[t].dtk==x){
cout << t << " ";
t--;
}
//in cac vi tri ben phai cua pos neu co cung gia tri x
int p = pos+1;
while(p<=n-1 && sv[p].dtk==x){
cout << p << " ";
p++;
}}}
3. Cây
#include <iostream>
#include <string.h>
#include <iomanip>
struct Node{
float data;
Node *left;
Node *right;
};
typedef Node *tree;
void khoitao (tree &root){
root = NULL; }
Node* TaoNut(float data){
Node *p = new Node;
if(p !=NULL){
p->data = data;
p->left=p->right=NULL;
}
return p;}
void ChenNut(tree &root,Node *p){
if(root != NULL){
if(root->data == p->data)
return;
if(root->data < p->data)
ChenNut(root->right,p);
else
ChenNut(root->left,p);
}
else root=p;}
void DuyetTruoc(tree root){
if(root !=NULL){
cout << root->data << "(dia chi: " << root << ")" << " " ;
DuyetTruoc(root->left);
DuyetTruoc(root->right);
}}
void DuyetGiua(tree root){
if(root !=NULL){
DuyetGiua(root->left);
DuyetGiua(root->right);
}}
void DuyetSau(tree root){
if(root !=NULL){
DuyetSau(root->left);
DuyetSau(root->right);
}}
(tkiemdequy)
Node* TKiem(tree root, float x) {
if (root == NULL || root->data == x) {return root;}
if (root->data > x) {return TKiem(root->left, x);}
return TKiem(root->right, x);}
(tkiemkhudequy)
Node* TimKiem(tree root, float y) {
Node *k = root;
while (k != NULL) {
if (y == k->data) {return k;}
else if (y < k->data) {return k = k->left;
}else {return k = k->right;}
} return NULL;
}
//Huy 1 nut la
//Huy 1 nut co 1 con trai hoac phai
//Huy 1 nut co du 2 con
void Timnutthaythe(tree &p, tree &q){
if(q->right != NULL)
Timnutthaythe(p, q->right);
else{
p->data = q->data;
p = q;
q = q->left;
}}
int xoanut(tree &root, float z){
if(root == NULL) return 0;
if(root->data > z) return xoanut(root->left, z);
if(root->data < z) return xoanut(root->right, z);
Node *p = root;
if(root->left == NULL)
root = root->right;
else
if(root->right == NULL)
root = root->left;
else
Timnutthaythe(p, root->left);
delete p;
}
int main(){
tree root;
khoitao(root);
//Tao cay
float data;
int n;
cout << "Nhap so so hang n = "; cin >> n;
for(int i=0;i<n;i++){
cout << "Nhap so data: "; cin >> data;
Node *p = TaoNut(data);
if(p!=NULL)
ChenNut(root,p);
}
cout << "----------------------------------------------------" << endl;
cout<<"\n Duyet cay thu tu truoc:\n";
DuyetTruoc(root);
cout<<"\n Duyet cay thu tu giua:\n";
DuyetGiua(root);
cout<<"\nDuyet cay thu tu sau:\n";
DuyetSau(root);
cout << "----------------------------------------------------" << endl;
float x;
cout << "\nThong tin so tim duoc:\n";
cout << "Nhap x = "; cin >> x;
Node* p = TKiem(root, x);
if (p != NULL) {
cout << p->data << "(dia chi: " << p << ")" << " " ;
} else {
cout << "Khong tim thay so " << x << endl;
}
cout << "----------------------------------------------------" << endl;
float y;
cout<<"\nThong tin so tim duoc:\n";
cout << "Nhap y: "; fflush(stdin); cin >> y;
Node* h = TimKiem(root, y);
if (h != NULL) {
cout << h->data << "(dia chi: " << h << ")" << " " ;
} else {
cout << "Khong tim thay so " << y << endl;
}
cout << "----------------------------------------------------" << endl;
cout << "\nXoa so can xoa" << endl;
float z;
cout << "Nhap so muon xoa: "; cin >> z;
z = xoanut(root, z);
DuyetTruoc(root);
DuyetGiua(root);
DuyetSau(root);
cout << "----------------------------------------------------" << endl;
cout << "----------------------------------------------------" << endl;
}
4. Cây np sp
#include <iostream>
#include <string.h>
#include <iomanip>
struct SanPham{
int ma;
string ten;
float gia;
};
typedef SanPham SP;
struct Node{
SP sp;
Node *left;
Node *right;
};
typedef Node *tree;
void khoitao (tree &root){ root = NULL;}
Node* TaoNut(SP sp){
Node *p = new Node;
if(p !=NULL){
p->sp = sp;
p->left=p->right=NULL;
} return p;}
void ChenNut(tree &root,Node *p){
if(root != NULL){
if(root->sp.ma == p->sp.ma)
return;
if(root->sp.ma < p->sp.ma)
ChenNut(root->right,p);
else
ChenNut(root->left,p);
} else root=p;}
void DuyetTruoc(tree root){
if(root !=NULL){
cout << root->sp.ma << setw(10) << "(dia chi: " << root << ")" <<
setw(10) << root->sp.ten << setw(10) << root->sp.gia << endl;
DuyetTruoc(root->left);
DuyetTruoc(root->right);
}}
void DuyetGiua(tree root){
if(root !=NULL){
DuyetGiua(root->left);
DuyetGiua(root->right);
}}
void DuyetSau(tree root){
if(root !=NULL){
DuyetSau(root->left);
DuyetSau(root->right);
}}
void Timnutthaythe(tree &p, tree &q){
if(q->right != NULL)
Timnutthaythe(p, q->right);
else{
p->sp = q->sp;
p = q;
q = q->left;
}}
int xoanut(tree &root, int x){
if(root == NULL) return 0;
if(root->sp.ma > x) return xoanut(root->left, x);
if(root->sp.ma < x) return xoanut(root->right, x);
Node *p = root;
if(root->left == NULL)
root = root->right;
else
if(root->right == NULL)
root = root->left;
else
Timnutthaythe(p, root->left);
delete p;
}
int main(){
tree root;
khoitao(root);
//Tao cay
SP sp;
int n;
cout << "Nhap so sp n = "; cin >> n;
cout << "Nhap ma sp thu " << i+1 << ": "; cin >> sp.ma;
cout << "Nhap ten sp thu " << i+1 << ": "; cin >> sp.ten;
cout << "Nhap gia sp thu " << i+1 << ": "; cin >> sp.gia;
Node *p = TaoNut(sp);
if(p!=NULL)
ChenNut(root,p);
}
cout << "----------------------------------------------------" << endl;
DuyetTruoc(root);
DuyetGiua(root);
DuyetSau(root);
cout << "----------------------------------------------------" << endl;
int x;
cout << "Nhap ma SP muon xoa: "; cin >> x;
x = xoanut(root, x);
DuyetTruoc(root);
DuyetGiua(root);
DuyetSau(root);
cout << "----------------------------------------------------" << endl;
cout << "----------------------------------------------------" << endl;
}
5. DFS và BFS
#include<iostream>
#include<fstream>
#include<stack>
#include<queue>
#define MAX 10
struct Graphlt{
int n;//so dinh
int A[MAX][MAX];
};
void input(Graphlt &G){
ifstream fi("C:\\Users\\DUONG HA\\Desktop\\cpp-codevsc\\cpp\\gt_nc\\
xtx\\Matran.txt");
if(fi.is_open()){
//doc dulieu
fi>>G.n;
for(int i=0;i<G.n;i++){
for(int j=0;j<G.n;j++){
fi>>G.A[i][j];
}}
fi.close();
}}
void xuat(Graphlt &G){

// hien thi do thi
cout<<"So dinh: "<<G.n << endl;
for(int j=0;j<G.n;j++){
cout<<G.A[i][j]<< " ";
}
cout<<"\n";
}}
bool IsFather(int u, int v, Graphlt G){// tra v la con u khong
if(G.A[u][v]==1){
return true;
}
return false;
}
void DFS(int start, int goal,Graphlt G){
//khai bao cac cau truc du lieu
stack<int> Open;
int close[G.n]={0};
int father[G.n];
bool kq=false;
//dua start vao open
Open.push(start);
//khoi tao mang father
father[i]=-1;
}
//lap
while (!Open.empty()){
//lay u la dinh o dau hang doi
int u=Open.top();
Open.pop();
// ktr neu u=goal thi ket thuc va tra ve loi giai
if(u==goal){
kq=true; break;
}
// danh dau u la dih da xet
close[u]=1;
//duyet cac trang thai v la con cua u
// for(int v=0; v<G.n;v++){
// if(IsFather(u,v,G)==true){
// if(father[v]==-1 && close[v]==0){
// Open.push(v);
// father[v]=u;
// }
for(int v=G.n-1; v>=0;v--){
if(IsFather(u,v,G)==true){
if(father[v]==-1 && close[v]==0){
Open.push(v);
father[v]=u;
}}}}
//in ra duong di
int u=goal;
if(kq==true){
//in duong di
while(u!=start){
cout<<u+1<<"<--";
u=father[u];
}
cout<<start+1;
}else{
cout<<"Khong tim thay duong di"<<endl;
}}
void BFS(int start, int goal,Graphlt G){
//khai bao cac cau truc du lieu
queue<int> Open;
int close[G.n]={0};
int father[G.n];
bool kq=false;
//dua start vao open
Open.push(start);
//khoi tao mang father
father[i]=-1;
}
//lap
while (!Open.empty()){
//lay u la dinh o dau hang doi
int u=Open.front();
Open.pop();
// ktr neu u=goal thi ket thuc va tra ve loi giai
if(u==goal){
kq=true; break;
}
// danh dau u la dih da xet
close[u]=1;
//duyet cac trang thai v la con cua u
for(int v=0; v<G.n;v++){
if(IsFather(u,v,G)==true){
if(father[v]==-1 && close[v]==0){
Open.push(v);
father[v]=u;
}}}}
//in ra duong di
int u=goal;
if(kq==true){
//in duong di
while(u!=start){
cout<<u+1<<"<--";
u=father[u];
}
cout<<start+1;
}else{
cout<<"Khong tim thay duong di"<<endl;
}}
int main(){
int start,goal;
Graphlt G;
input(G);
xuat(G);
*cout<<"Nhap dinh start,goal: ";

cin>>start>>goal;
DFS(start-1,goal-1,G);
*cout<<"\nNhap dinh start,goal: ";
cin>>start>>goal;
BFS(start-1,goal-1,G);
}
6
010110
101010
010011
100010
111000
001000
6. Đồ thị cạnh cung

#include<iostream>
#include<fstream>
#define MAX 100
typedef struct Edgetag{
int u;
int v;
} edge;
struct Graphlt{
edge e[MAX];
int m;
};
void input(Graphlt &G){
ifstream fi("D:\\danhsachcanhcung.txt");
if(fi.is_open()){
//doc dulieu
fi>>G.m;
for(int i=0;i<G.m;i++){
fi>>G.e[i].u>>G.e[i].v;
}
fi.close();
}}
string name(int i){
switch(i){
case 0:
return"v0";
case 1:
return"v1";
case 2:
return "v2";
case 3:
return "v3";
case 4:
return "v4";
case 5:
return "v5";
}}
void xuat(Graphlt &G){
// hien thi do thi
cout<<"So canh: "<<G.m << endl;
for(int i=0;i<G.m;i++){
cout<<"("<<name(G.e[i].u)<< ",
"<<name(G.e[i].v)<<")"<<endl;
cout<<"\n";
}}
int main(){
Graphlt G;
input(G);
xuat(G);}
9
0 1
0 2
0 3
1 3
1 4
2 3
3 4
3 5
4 5
7. ma trận kề
#include <iostream>
#include <list>
#include <fstream>
#define MAX 100
struct Graph
{
int n; // so dinh cua do thi
int A[MAX]; // Luu tap dinh ke cua tat ca cac dinh trong do thi
int I[MAX]; // Luu chi so dau cua doan dinh ke cua moi dinh i
};
bool Nhap(Graph &g){

// mo file
int k, d = 0;
ifstream fi("C:\\Users\\DUONG HA\\Desktop\\cpp-codevsc\\cpp\\gt_nc\\
xtx\\danhsachke.txt");
if (fi.is_open() == true){
fi >> g.n; // doc so dinh
for (int i = 0; i < g.n; i++){
g.I[i] = d;
fi >> k;
for (int j = 0; j < k; j++){
fi >> g.A[d];
d = d + 1;
}}
g.I[g.n] = d;
fi.close();
}}
void Xuat(Graph g){

cout << "So dinh = " << g.n << endl;
for (int i = 0; i < g.n; i++){
cout << g.I[i + 1] - g.I[i] << " "; // xuat so dinh ke cua dinh i
for (int j = g.I[i]; j < g.I[i + 1]; j++)
cout << g.A[j] << " ";
cout << "\n";
}}
int main(){
Graph g;
Nhap(g);
Xuat(g);}
5
212
3024
3014
14
3123
1. BFS
#include<iostream>
#include <fstream>
#include<conio.h>
#define MAX 100
#define TRUE 1
#define FALSE 0
/// Câu 2
struct Graph{
int N; //So đinh cua đo thi
int A[MAX][MAX];
};
void Nhap(Graph &g){
ifstream file("D:\\GIAITHUAT_NC\\OnThi\\BFS.txt");
file >> g.N;
for (int i = 1; i <= g.N; i++){
for (int j = 1; j <= g.N; j++){
file >> g.A[i][j];
}}
file.close();
}
void HienThi(Graph g){
cout << "Do thi vua nhap la:" << endl;
cout << "- So dinh cua do thi: " << g.N << endl;
cout << "- Ma tran ke cua do thi:" << endl;
for (int i = 1; i <= g.N; i++){
for (int j = 1; j <= g.N; j++){
cout << g.A[i][j] << " ";
}
cout << endl;
}}
struct BFS{
Graph g; //Đo thi G
int dinhdau; //Đinh đau (bat đau tim đuong đi)
int dinhcuoi; //Đinh cuoi (ket thúc đuong đi can tim)
int chuaxet[MAX];
int QUEUE[MAX];
int truoc[MAX];
};
void Init(BFS &bfs){
//Khoi tao
for (int i = 1; i <= bfs.g.N; i++){
bfs.chuaxet[i] = TRUE;
bfs.truoc[i] = 0; //Ban đau truoc mot đinh không là đinh nào
}}
bool TimDuongDi(BFS &bfs){

int u, dauQ, cuoiQ;
dauQ = 1;
cuoiQ = 1;
bfs.QUEUE[cuoiQ] = bfs.dinhdau;
bfs.chuaxet[bfs.dinhdau] = FALSE;
bool timduoc = FALSE;
while(dauQ <= cuoiQ){
u = bfs.QUEUE[dauQ];// lay đinh u ra khoi queue.
cout << "---> duyet qua dinh: " << (char(u + 'A' - 1)) << endl;
if (u == bfs.dinhcuoi){
timduoc = TRUE;
break; //Đa tim thay đuong đi, thoát khoi vong lap
}
dauQ = dauQ + 1; /* duyet đinh đau hàng đoi*/
for(int j = 1; j <= bfs.g.N; j++){
if(bfs.g.A[u][j] == 1 && bfs.chuaxet[j] ){
cuoiQ=cuoiQ + 1;
bfs.QUEUE[cuoiQ] = j;
bfs.chuaxet[j] = FALSE;
bfs.truoc[j] = u;
}}}
return timduoc;
}
void HienThiDuongDi(BFS bfs){
cout << "Duong di tu " << (char)(bfs.dinhdau + 'A' - 1) << " den " <<
(char)(bfs.dinhcuoi + 'A' - 1) << " la:" <<endl;
cout << (char)(bfs.dinhcuoi + 'A' - 1) << "<="; //in đinh cuoi dang
char
int i = bfs.truoc[bfs.dinhcuoi];
while (i != bfs.dinhdau){
cout << (char)(i + 'A' - 1) << "<=";//in ra ket qua duoi dang char
i = bfs.truoc[i];
}
cout << (char)(bfs.dinhdau + 'A' - 1) << endl;
}
int main(){
Graph g;
Nhap(g);
HienThi(g);
BFS bfs;
bfs.g = g;
Init(bfs);
cout << "- Nhap dinh dau: ";
cin >> bfs.dinhdau; //Thu tu các đinh bat đau tu 1
cout << "- Nhap dinh cuoi: ";
cin >> bfs.dinhcuoi; //Thu tu các đinh bat đau tu 1
TimDuongDi(bfs);
HienThiDuongDi(bfs);
}
2. DFS
#include<iostream>
#include <fstream>
#include<conio.h>
#define MAX 100
#define TRUE 1
#define FALSE 0
struct Graph{
int N; //So đinh cua đo thi
int A[MAX][MAX];
//Mang luu ma tran ke cua đo thi, chi so bat đau tu 1
};
void Nhap(Graph &g){
ifstream file("D:\\GIAITHUAT_NC\\OnThi\\DFS.txt");
file >> g.N;
for (int i = 0; i <= g.N; i++){
for (int j = 1; j <= g.N; j++){
file >> g.A[i][j];
}}
file.close();}
void HienThi(Graph g){
cout << "Do thi vua nhap la:" << endl;
cout << "- So dinh cua do thi: " << g.N << endl;
cout << "- Ma tran ke cua do thi:" << endl;
for (int i = 0; i <= g.N; i++){
for (int j = 1; j <= g.N; j++){
cout << g.A[i][j] << " ";
}
cout << endl;
}}
/// Depth First Search
struct DFS{
Graph g; //Đo thi G
int dinhdau; //Đinh đau (bat đau tim đuong đi)
int dinhcuoi; //Đinh cuoi (ket thúc đuong đi can tim)
int chuaxet[MAX];
int truoc[MAX];
};
void Init(DFS &dfs){
//Khoi tao
for (int i = 1; i <= dfs.g.N; i++){
dfs.chuaxet[i] = TRUE;
dfs.truoc[i] = 0; //Ban đau truoc mot đinh không là đinh nào
}}
void TimDuongDi(DFS &dfs, int v){
cout << "---> Duyet dinh : " << char(v + 'A' - 1) << endl;
dfs.chuaxet[v]=FALSE;
for(int u = 1; u <= dfs.g.N; u++){
if(dfs.g.A[v][u] == 1 && dfs.chuaxet[u]){
dfs.truoc[u] = v;
TimDuongDi(dfs, u);
}}}
void HienThiDuongDi(DFS dfs){
cout << "Duong di tu " << (char)(dfs.dinhdau + 'A' - 1) << " den " <<
(char)(dfs.dinhcuoi + 'A' - 1) << " la:" <<endl;
cout << (char)(dfs.dinhcuoi + 'A' - 1) << "<=";
int i = dfs.truoc[dfs.dinhcuoi];
while (i != dfs.dinhdau){
cout << (char)(i + 'A' - 1) << "<=";
i = dfs.truoc[i];
}
cout << (char)(dfs.dinhdau + 'A' - 1) << endl;
}
int main(){
Graph g;
Nhap(g);
HienThi(g);
DFS dfs;
dfs.g = g;
Init(dfs);
cout << "- Nhap dinh dau: ";
cin >> dfs.dinhdau; //Thu tu cac đinh bat đau tu 1
cout << "- Nhap dinh cuoi: ";
cin >> dfs.dinhcuoi; //Thu tu cac đinh bat đau tu 1
TimDuongDi(dfs, dfs.dinhdau);
HienThiDuongDi(dfs);
}
3. QL Mảng
#include<iostream>
#include<malloc.h>
#include<string.h>
struct SinhVien{
int maSV;
char tenSV[25];
char lop[15];
float diemTK;
};
void Nhap(SinhVien *s, int n){
printf("Nhap thong tin sinh vien thu %d: \n ",i);
printf("Nhap ma sinh vien: ");
scanf("%d", &s[i].maSV);
printf("Nhap ten sinh vien:");
fflush(stdin);
gets(s[i].tenSV);
printf("Nhap lop sinh vien:");
fflush(stdin);
gets(s[i].lop);
printf("Nhap diem tong ket:");
scanf("%f", &s[i].diemTK);
}}
void HienThi(SinhVien *s, int n){
printf("Ma sinh vien: %d || Ten sinh vien: %s || Lop: %s || Diem
tong ket: %f \n",s[i].maSV,s[i].tenSV,s[i].lop,s[i].diemTK);
}}
void InsertionSort(SinhVien *a,int n){//chen truc tiep
int pos;
SinhVien x
x = a[i];
pos = i-1;
while((pos >= 0) && (a[pos].diemTK > x.diemTK)){
a[pos+1] = a[pos];
pos--;
}
a[pos+1]=x;
}}
void BubbleSort(SinhVien *a, int n){//Noi bot
for(int j=n-1;j>i;j--){
if(a[j].diemTK < a[j-1].diemTK){
SinhVien x = a[j];
a[j] = a[j-1];
a[j-1] = x;
}}}}
void InterchangeSort(SinhVien *a,int n){//doi cho truc tiep
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if(a[j].diemTK < a[i].diemTK){
SinhVien x = a[j];
a[j] = a[i];
a[i] = x;
}} } }
void QuickSort(SinhVien *a, int left,int right){
SinhVien x = a[(left + right) / 2];
int i=left,j=right;
while (i<j){
while(a[i].diemTK < x.diemTK) i++;
while(a[j].diemTK > x.diemTK) j--;
if(i<=j){
SinhVien tmp = a[j];
a[j] = a[i];
a[i] = tmp;
i++;
j--;
}}
if(left<j) QuickSort(a,left,j);
if(i<right) QuickSort(a,i,right);
}
void SelectionSort(SinhVien *a,int n){
int min;
min = i;
for(int j = i+1;j<n;j++){
if(a[j].diemTK < a[min].diemTK)
min = j;
}
SinhVien x = a[min];
a[min]=a[i];
a[i]=x;
}}
//Cau5 Tim kiem mot phan tu trong danh sach
int BinarySearch(float diemTK,SinhVien *a,int N){
int m, bottom, top;
bottom = 0;
top = N-1;
while (bottom <= top){
m = (top+bottom)/2;
if(diemTK == a[m].diemTK){ return m; }
else if(diemTK<a[m].diemTK) return top = m-1;
else return bottom=m+1;
}
return -1;
}
void SearchALL(float diemTK,SinhVien *a,int N){
int found = BinarySearch(diemTK,a,N);
//Liet ke tat ca sinh vien co diem tong ket da tim duoc
if(found == -1) printf("Khong tim thay sinh vien co diem tong ket =
%f\n",diemTK);
else{
printf("Cac sinh vien co diem tong ket = %f la: \n",diemTK);
int i=found;
while (i<N && a[i].diemTK == diemTK){
printf("Ma sinh vien: %d || Ten sinh vien: %s || Lop: %s ||
Diem tong ket: %f\n",a[i].maSV,a[i].tenSV,a[i].lop,a[i].diemTK);
i++;
}
i = found -1;
while (i>=0 && a[i].diemTK == diemTK){
printf("Ma sinh vien: %d || Ten sinh vien: %s || Lop: %s ||
Diem tong ket: %f\n",a[i].maSV,a[i].tenSV,a[i].lop,a[i].diemTK);
i--;
}}}
//Cau6
int main(){
SinhVien *a;
int n;
///y thu nhat
printf("Nhap so luong sinh vien: ");
scanf("%d",&n);
a = (SinhVien*)malloc(n * sizeof(SinhVien));
//dsSV = new SinhVien[n];
Nhap(a,n);
printf("Danh sach sinh vien sau khi da nhap: \n");
HienThi(a,n);
///Het y thu nhat
///Y thu hai
printf("Sap xep sinh vien theo chieu tang cua diem tong ket: \n");
InterchangeSort(dsSV,n);
SelectionSort(dsSV,n);
BubbleSort(dsSV,n);
InsertionSort(a,n);
QuickSort(a,0,n-1);
HienThi(a,n);
///Het y thu hai
/// Y thu ba
float diemTK;
printf("Nhap diem tong ket can tim kiem: ");
scanf("%f",&diemTK);
SearchALL(diemTK,a,n);
///Het y thu ba
free(a);
}

Giai Thuat NC

Uploaded by

Copyright:

Available Formats

Giai Thuat NC

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Giai Thuat NC

Uploaded by

Copyright:

Available Formats

1.

int solg(int n){

void nhap(Sinhvien sv[], int n){

int BnSearch(Sinhvien sv[], int n, float x){

void xuat(Graphlt &G){

*cout<<"Nhap dinh start,goal: ";

6. Đồ thị cạnh cung

bool Nhap(Graph &g){

void Xuat(Graph g){

bool TimDuongDi(BFS &bfs){

You might also like