/* Bai tap 3_67 - Quan ly hai STACK chi dung 1 day */
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

#define MAX 100

int stack[2*MAX];
int top1, top2;

void initstack()
{
top1 = -1;
top2 = 2*MAX;
}

void push(int value, int _stack)
{
if (_stack == 0)
{
if (top1<top2)
stack[++top1] = value;
}
else
{
if (top1<top2)
stack[--top2] = value;
}
}

int isempty(int _stack)
{
if (_stack == 0)
return top1 == -1;
else
return top2 == 2*MAX;
}

int pop(int _stack)
{
if (_stack == 0)
if (!isempty(_stack))
return(stack[top1--]);
if (!isempty(_stack))
return stack[top2++];
else
return -1;
}

void main()
{
int i, value, _stack;

initstack();
randomize();
for (i = 0; i<20; i++)
{
_stack = random(2);
value = random(10);
printf("\nPUSH %d vao stack %d", value, _stack);
push(value, _stack);
}
printf("\nLay nhung gia tri tu stack 0 : ");
while (!isempty(0))
printf("%3d", pop(0));
printf("\nLay nhung gia tri tu stack 1 : ");
while (!isempty(1))
printf("%3d", pop(1));
getch();
}

/* Bai tap 3_67 - Quan ly sinh vien */

#include <stdio.h>
#include <ctype.h>
#include <mem.h>
#include <string.h>

#define MAX 100
#define TOAN 0
#define LY 1
#define HOA 2

struct sinhvien {
char mslop[5];
char hoten[35];
float diem[3];
} danhsach[MAX];
int n = 0;

void nhapmoi()
{
char mslop[5], tmp[3];
int i;
float diem[3];
do {
printf("\nCho biet ma so lop : ");
gets(mslop);
if (strlen(mslop))
{
strcpy(danhsach[n].mslop, mslop);
printf("\nCho biet ho ten : ");
gets(danhsach[n].hoten);
printf("\nCho biet diem so : ");
for (i=0; i<3; i++)
{
scanf("%f", &diem);
danhsach[n].diem = diem;
}
gets(tmp);
n++;
}
} while (strlen(mslop));
}

void timkiem()
{
char mslop[5];
int i = 0, found = 0;
printf("\nCho biet ma so lop : ");
gets(mslop);
if (strlen(mslop))
while (i<n)
if (stricmp(danhsach.mslop, mslop) == 0)
{
printf("\nMa so lop : %s", danhsach.mslop);
printf("\nHo va ten : %s", danhsach.hoten);
printf("\nDiem Toan : %f", danhsach.diem[TOAN]);
printf("\nDiem Ly : %f", danhsach.diem[LY]);
printf("\nDiem Hoa : %f", danhsach.diem[HOA]);
found = 1;
break;
}
else
i++;
if (!found)
printf("\nKhong tim thay!!!");
}

void xoa()
{
char mslop[5], traloi;
int i = 0, j;
printf("\nCho biet ma so lop : ");
gets(mslop);
if (strlen(mslop))
while (i<n)
if (stricmp(danhsach.mslop, mslop) == 0)
{
printf("\nMa so lop : %s", danhsach.mslop);
printf("\nHo va ten : %s", danhsach.hoten);
printf("\nDiem Toan : %f", danhsach.diem[TOAN]);
printf("\nDiem Ly : %f", danhsach.diem[LY]);
printf("\nDiem Hoa : %f", danhsach.diem[HOA]);
printf("\nCo muon xoa khong (C/K)? ");
do {
traloi = toupper(getch());
} while (traloi != 'C' && traloi != 'K');
putc(traloi, stdout);
if (traloi == 'C')
{
n--;
memcpy(&danhsach, &danhsach[i+1], sizeof(struct sinhvien) * (n-i));
break;
}
}
else
i++;
}

void menu()
{
printf("\n***************");
printf("\n* 1. Them *");
printf("\n* 2. Xoa *");
printf("\n* 3. Tim kiem *");
printf("\n* 0. Thoat *");
printf("\n***************");
printf("\nChon lua ? ");
}

void main()
{
char traloi;
do {
menu();
do {
traloi = getch();
} while (traloi < '0' || traloi > '3');
putc(traloi, stdout);
switch (traloi)
{
case '1' : nhapmoi();
break;
case '2' : xoa();
break;
case '3' : timkiem();
break;
}
} while (traloi != '0');
}

/*Hang doi Queue*/

#include <stdio.h>

#define MAX 100

int queue[MAX + 1];
int front, rear, queue_size;

void khoi_tao_queue()
{
front = rear = 0;
queue_size = 0;
}

int is_empty()
{
return (queue_size == 0);
}

int is_full()
{
return (queue_size == MAX);
}

int push(int value)
{
if (queue_size < MAX)
{
queue_size++;
queue[rear++] = value;
if (rear == MAX)
rear = 0;
}
return rear;
}

int pop(int *value)
{
if (queue_size > 0)
{
*value = queue[front++];
if (front > MAX)
front = 0;
queue_size--;
}
return front;
}

void main()
{
int k;

khoi_tao_queue();
printf("\nNhap cac phan tu vao queue (-1 de ket thuc) : ");
do {
scanf("%d", &k);
if (k != -1)
push(k);
} while (k != -1 && !is_full());
printf("\n\nLay cac phan tu tu queue ra : ");
while (!is_empty())
{
pop(&k);
printf("%d ", k);
}
getch();
}

#include <stdio.h>

#define MAX 100

int stack[MAX + 1];
int top;

void khoi_tao_stack()
{
top = -1;
}

int is_empty()
{
return (top == -1);
}

int is_full()
{
return (top == MAX);
}

int push(int value)
{
if (top < MAX)
stack[++top] = value;
return top;
}

int pop(int *value)
{
*value = stack[top--];
return top;
}

void main()
{
int k;

khoi_tao_stack();
printf("\nNhap cac phan tu vao stack (-1 de ket thuc) : ");
do {
scanf("%d", &k);
if (k != -1)
push(k);
} while (k != -1 && !is_full());
printf("\n\nLay cac phan tu tu stack ra : ");
while (!is_empty())
{
pop(&k);
printf("%d ", k);
}
getch();
}

/* Chen nhi phan */
#include <stdio.h>
#include <stdlib.h>

#define MAX 10
int mang[MAX];

void in_mang(int *mang)
{
int i;
for (i=0; i<MAX; i++)
printf("%d ", mang);
}

void binarysort()
{
int i, j, x, l, r, m;
for (i=1; i<MAX; i++)
{
x = mang;
l = 0;
r = i-1;
while (l <= r)
{
m = (l + r) / 2;
if (x < mang[m])
r = m - 1;
else
l = m + 1;
}
if (x < mang[l])
{
for (j=i-1; j>=l; j--)
mang[j+1] = mang[j];
mang[l] = x;
}
}
}

void main()
{
int i;

randomize();
for (i=0; i<MAX; i++)
mang = random(100);
printf("\nTruoc khi sap : ");
in_mang(mang);
binarysort();
printf("\nSau khi sap : ");
in_mang(mang);
getch();
}

/* Bai tap 3_70 - Tim chieu cao cay */
#include <stdio.h>
#include <alloc.h>

typedef int element_type;
typedef struct node {
element_type element;
struct node *left, *right;
} NODE;

NODE *root;

#define max(a,b) ((a) > (b)? (a) : (b))

void khoi_tao_cay(NODE ** root)
{
*root = NULL;
}

void insert(NODE *tmp, NODE **root)
{

if (tmp->element < (*root)->element)
if ((*root)->left)
insert(tmp, &(*root)->left);
else
(*root)->left = tmp;
else
if ((*root)->right)
insert(tmp, &(*root)->right);
else
(*root)->right = tmp;
}

void insert_node(element_type e, NODE **root)
{
NODE *tmp;

tmp = (NODE *)malloc(sizeof(NODE));
tmp->element = e;
tmp->left = NULL;
tmp->right = NULL;
if (*root == NULL)
*root = tmp;
else
insert(tmp, root);
}

void nhap_cay(NODE **root)
{
element_type e;
do {
printf("\nNhap element (-1 de ket thuc) : ");
scanf("%d", &e);
if (e != -1)
insert_node(e, root);
} while (e != -1);
}

int chieucao(NODE *root, int start)
{
if (root == NULL)
return 0;
else
return max(chieucao(root->left, start + 1),
chieucao(root->right, start + 1)) + 1;
}

void main()
{
khoi_tao_cay(&root);
nhap_cay(&root);
printf("\nChieu cao cua cay = %d", chieucao(root, 1));
getch();
}

/* Bai tap 3_2 - Minh hoa giai thuat Boyer - Moore */
#include <stdio.h>
#include <conio.h>
#include <string.h>

#define MAX 256

int BoyerMoore(char *source, char *find);

void main()
{
char source[MAX], find[MAX];
int f;

printf("\nNhap vao chuoi nguon : ");
gets(source);
printf("Nhap vao chuoi tim kiem : ");
gets(find);

if ((f = BoyerMoore(source, find)) > 0)
printf("chuoi tim thay tai chi so %d", f);
else
printf("Khong tim thay chuoi da cho", f);
getch();
}

int BoyerMoore(char *source, char *find)
{
int skip[MAX], i = 0, len, j=-1, lensource;

len = strlen(find);
lensource = strlen(source);
for (i=0; i<MAX; i++)
skip = len-1;
for (i=0; i<len; i++)
if (skip[find] == len-1)
skip[find] = len-i-1;

i = j = len-1;
do {
if (source == find[j])
{
i--;
j--;
}
else
{
if (len-j+1 > skip[source])
i += len-j+1;
else
i += skip[source];
j = len-1;
}
} while (j>0 && i<lensource);

if (j<=0)
return i;
else
return -1;
}

/* Giai thuat tim kiem chuoi Brute-Force */
#include <stdio.h>

char *Brute_Force(char *source, char *substr, int *k)
{
int i = 0, j = 0, m, n;
n = strlen(source) - 1;
m = strlen(substr) - 1;
do {
if (source == substr[j])
{
i++;
j++;
}
else
{
i = i - j + 2;
j = 0;
}
} while (j <= m && i <= n);
if (j > m)
{
*k = i - m - 1;
return source + i - m - 1;
}
else
return NULL;
}

void main()
{
char source[255], substr[50], *found;
int k;

printf("\nNhap chuoi nguon : ");
gets(source);
printf("\nNhap chuoi tim kiem : ");
gets(substr);
found = Brute_Force(source, substr, &k);
if (found)
{
printf("\nTim thay tai vi tri : %d", k);
printf("\nChuoi tim thay : %s", found);
}
else
printf("\nKhong tim thay chuoi.");
getch();
}

/* Cai dat thuat toan Bubble Sort */
#include <stdio.h>
#include <stdlib.h>

#define MAX 10
int mang[MAX];

void in_mang(int *mang)
{
int i;
for (i=0; i<MAX; i++)
printf("%d ", mang);
}

void bubblesort()
{
int i, j, x;
for (i=1; i< MAX; i++)
for (j=MAX-1; j>=i; j--)
{
if (mang[j-1] > mang[j])
{
x = mang[j-1];
mang[j-1] = mang[j];
mang[j] = x;
}
}
}

void main()
{
int i;

randomize();
for (i=0; i<MAX; i++)
mang = random(100);
printf("\nTruoc khi sap : ");
in_mang(mang);
bubblesort();
printf("\nSau khi sap : ");
in_mang(mang);
getch();
}

#include <stdio.h>
#include <alloc.h>

typedef int element_type;
typedef struct node {
element_type element;
struct node *left, *right;
} NODE;

NODE *root;

void khoi_tao_cay(NODE ** root)
{
*root = NULL;
}

void insert(NODE *tmp, NODE **root)
{

if (tmp->element < (*root)->element)
if ((*root)->left)
insert(tmp, &(*root)->left);
else
(*root)->left = tmp;
else
if ((*root)->right)
insert(tmp, &(*root)->right);
else
(*root)->right = tmp;
}

void insert_node(element_type e, NODE **root)
{
NODE *tmp;

tmp = (NODE *)malloc(sizeof(NODE));
tmp->element = e;
tmp->left = NULL;
tmp->right = NULL;
if (*root == NULL)
*root = tmp;
else
insert(tmp, root);
}

void nhap_cay(NODE **root)
{
element_type e;
do {
printf("\nNhap element (-1 de ket thuc) : ");
scanf("%d", &e);
if (e != -1)
insert_node(e, root);
} while (e != -1);
}

int dem_nut_la(NODE *root)
{
if (root == NULL)
return 0;
else
if (root->left != NULL || root->right != NULL)
return dem_nut_la(root->left) + dem_nut_la(root->right);
else
return 1;
}

int dem_nut_day_du(NODE *root)
{
if (root == NULL)
return 0;
else
if (root->left != NULL && root->right != NULL)
return dem_nut_day_du(root->left) + dem_nut_day_du(root->right) + 1;
else
return dem_nut_day_du(root->left) + dem_nut_day_du(root->right);
}

void main()
{
int tong_nut_day_du, tong_nut_la;
khoi_tao_cay(&root);
nhap_cay(&root);
tong_nut_day_du = dem_nut_day_du(root);
tong_nut_la = dem_nut_la(root);
printf("\nTong so nut day du = %d", tong_nut_day_du);
printf("\nTong so nut la = %d", tong_nut_la);
getch();
}

#include <stdio.h>
#include <alloc.h>

typedef int element_type;
typedef struct node {
element_type element;
struct node *left, *right;
} NODE;

NODE *root;

void khoi_tao_cay(NODE ** root)
{
*root = NULL;
}

void insert(NODE *tmp, NODE **root)
{

if (tmp->element < (*root)->element)
if ((*root)->left)
insert(tmp, &(*root)->left);
else
(*root)->left = tmp;
else
if ((*root)->right)
insert(tmp, &(*root)->right);
else
(*root)->right = tmp;
}

void insert_node(element_type e, NODE **root)
{
NODE *tmp;

tmp = (NODE *)malloc(sizeof(NODE));
tmp->element = e;
tmp->left = NULL;
tmp->right = NULL;
if (*root == NULL)
*root = tmp;
else
insert(tmp, root);
}

void nhap_cay(NODE **root)
{
element_type e;
do {
printf("\nNhap element (-1 de ket thuc) : ");
scanf("%d", &e);
if (e != -1)
insert_node(e, root);
} while (e != -1);
}

int dem_nut(NODE *root)
{
if (root == NULL)
return 0;
else
return dem_nut(root->left) + dem_nut(root->right) + 1;
}

int dem_nut_rong(NODE *root)
{
if (root == NULL)
return 1;
else
return dem_nut_rong(root->left) + dem_nut_rong(root->right);
}
void main()
{
int tong_nut, tong_nut_rong;
khoi_tao_cay(&root);
nhap_cay(&root);
tong_nut = dem_nut(root);
tong_nut_rong = dem_nut_rong(root);
printf("\nTong so nut cua cay = %d", tong_nut);
printf("\nTong so nut rong = %d", tong_nut_rong);
getch();
}

/* Chen nut vao vi tri thu N trong DSLK */
#include <stdio.h>

typedef int element_type;
struct node {
element_type element;
struct node *next;
} *first = NULL, *last = NULL;

void insert(element_type e)
{
struct node *tmp;
tmp = (struct node*) malloc(sizeof(struct node));
tmp->element = e;
tmp->next = NULL;
if (first == NULL)
first = last = tmp;
else
{
last->next = tmp;
last = last->next;
}
}

struct node *insert_at_n(element_type e, int n)
{
long count = 0;
struct node *tmp, *t, *before = NULL;

tmp = first;

while (tmp != NULL && count <= n)
{
count++;
before = tmp;
tmp = tmp->next;
}
if (before != NULL)
{
t = (struct node*)malloc(sizeof(struct node));
t->element = e;
if (before == NULL)
{
t->next = first;
first = t;
}
else
{
before->next = t;
t->next = tmp;
}
}
else
{
printf("Vi tri khong tim thay! Thu tuc chen that bai");
return NULL;
}
return t;
}

void print_list()
{
struct node *tmp;

tmp = first;
while (tmp != NULL)
{
printf("%d ", tmp->element);
tmp = tmp->next;
}
}

void main()
{
element_type e;
int vitri;
struct node *tmp;

printf("\nNhap cac gia tri so (-1) de ket thuc : ");
do {
scanf("%d", &e);
if (e != -1)
insert(e);
} while (e != -1);

printf("Nhap gia tri can chen : ");
scanf("%d", &e);
printf("Nhap vi tri can chen : ");
scanf("%d", &vitri);

printf("\nTruoc khi chen, danh sach gom : \n");
print_list();
insert_at_n(e, vitri);
printf("\nSau khi chen, danh sach gom : \n");
print_list();

getch();

tmp = first;
while (tmp != NULL)
{
tmp = first->next;
free(first);
first = tmp;
}
}

#include <stdio.h>

typedef int element_type;
struct node {
element_type element;
struct node *next;
};

void khoi_tao_ds(struct node **first, struct node **last)
{
*first = *last = NULL;
}

void insert(element_type e, struct node **first, struct node **last)
{
struct node *tmp;
tmp = (struct node*) malloc(sizeof(struct node));
tmp->element = e;
tmp->next = NULL;
if (*first == NULL)
*first = *last = tmp;
else
{
(*last)->next = tmp;
(*last) = (*last)->next;
}
}

void xoa_ds(struct node **first, struct node **last)
{
struct node *tmp;
tmp = *first;
while (tmp != NULL)
{
tmp = (*first)->next;
free(*first);
*first = tmp;
}
*first = *last = NULL;
}

void nhap_ds(struct node **first, struct node **last)
{
element_type e;
printf("\nNhap cac gia tri so (-1) de ket thuc : ");
do {
scanf("%d", &e);
if (e != -1)
insert(e, first, last);
} while (e != -1);
}

void print_ds(struct node *first)
{
struct node *tmp;

tmp = first;
while (tmp != NULL)
{
printf("%d ", tmp->element);
tmp = tmp->next;
}
}

void daonguocds(struct node **first, struct node **last)
{
struct node *before = NULL, *after, *cursor ;

if (*first != NULL)
{
after = *first;
cursor = after->next;
*last = *first;
while (cursor != NULL)
{
after->next = before;
before = after;
after = cursor;
cursor = cursor->next;
}
after->next = before;
*first = after;
}
}

void main()
{
struct node *first, *last;

khoi_tao_ds(&first, &last);
nhap_ds(&first, &last);
printf("Danh sach ban dau : ");
print_ds(first);
daonguocds(&first, &last);
printf("\nSau khi dao nguoc : ");
print_ds(first);
xoa_ds(&first, &last);
getch();
}

/* Dem so nut trong mot danh sach lien ket */
#include <stdio.h>

typedef int element_type;
struct node {
element_type element;
struct node *next;
} *first = NULL, *last = NULL;

void insert(element_type e)
{
struct node *tmp;
tmp = (struct node*) malloc(sizeof(struct node));
tmp->element = e;
tmp->next = NULL;
if (first == NULL)
first = last = tmp;
else
{
last->next = tmp;
last = last->next;
}
}

void main()
{
element_type e;
int count = 0;
struct node *tmp;

printf("\nNhap cac gia tri so (-1) de ket thuc : ");
do {
scanf("%d", &e);
if (e != -1)
insert(e);
} while (e != -1);

tmp = first;
while (tmp != NULL)
{
count++;
tmp = tmp->next;
}

printf("\nSo node trong danh sach = %d", count);
getch();

tmp = first;
while (tmp != NULL)
{
tmp = first->next;
free(first);
first = tmp;
}
}

/* Bai tap 3_78 - Giai thuat DFS (Depth First Search) */
#include <dos.h>
#include <graphics.h>
#include <alloc.h>
#include "mouse.inc"

#pragma warn -sus

/* Toi da 100 nut */
#define MAX 100

int gr_drive=DETECT, gr_mode;
unsigned char lbutton, rbutton;
int xmouse, ymouse;

int sonut = 0;
typedef struct tagnode {
int x, y; /* Vi tri tren man hinh */
} NODE;

NODE nut[MAX];
int weight[MAX][MAX];
int themduoc = 1;

void DFS();

void initialize()
{
char s1[] = "Nhap nut phai chuot de them nut";
char s2[] = "Nhap nut trai chuot va re de them duong noi";
char s3[] = "Nhan phim Q de thoat - S de bat dau minh hoa giai thuat";
int i, j;

initgraph(&gr_drive, &gr_mode, "");
reset_mouse();
setcolor(YELLOW);
rectangle(0, 0, getmaxx(), getmaxy());
outtextxy((getmaxx()-textwidth(s1))/2, 5, s1);
outtextxy((getmaxx()-textwidth(s2))/2, 15, s2);
outtextxy((getmaxx()-textwidth(s3))/2, 25, s3);
line(0, 35, getmaxx(), 35);
set_mouse_hlimits(5, getmaxx()-6);
set_mouse_vlimits(40, getmaxy()-6);
for (i=0; i<MAX; i++)
for (j=0; j<MAX; j++)
weight[j] = -1;
show_mouse();
}

int index(int x, int y, int heso)
{
int i, OK = 0;
for (i=0; i<sonut; i++)
if (abs(nut.x - x) < 4*heso && abs(nut.y - y) < 4*heso)
{
OK = 1;
break;
}
if (OK)
return i;
else
return -1;
}

void get_mouse()
{
do {
get_mouse_button(&lbutton, &rbutton, &xmouse, &ymouse);
} while (lbutton == 0 && rbutton == 0 && !kbhit());
}

void clear_mouse()
{
do {
get_mouse_button(&lbutton, &rbutton, &xmouse, &ymouse);
} while (lbutton == 1 || rbutton == 1);
}

int input_weight(int start, int end)
{
int size, i;
void far *buf;
char c, s[]="Nhap trong so", s1[3]="";
size = imagesize(getmaxx()/2 - 70, getmaxy()/2 - 20,getmaxx()/2 + 70, getmaxy()/2 + 10);
buf = malloc(size);
getimage(getmaxx()/2 - 70, getmaxy()/2 - 20,getmaxx()/2 + 70, getmaxy()/2 + 10, buf);
setcolor(BLUE);
setfillstyle(SOLID_FILL, BLUE);
bar(getmaxx()/2 - 70, getmaxy()/2 - 20,getmaxx()/2 + 70, getmaxy()/2 + 10);
setcolor(WHITE);
rectangle(getmaxx()/2 - 70, getmaxy()/2 - 20,getmaxx()/2 + 70, getmaxy()/2 + 10);
line(getmaxx()/2 - 70, getmaxy()/2 - 5,getmaxx()/2 + 70, getmaxy()/2 - 5);
outtextxy((getmaxx()-textwidth(s))/2 - 4, getmaxy()/2 - 16, s);
i = 0;
do {
do {
c = getch();
} while ((c < '0' || c > '9') && c != 13 && c != 27 && c != 8);
if (c>='0' && c <= '9' && i<2)
{
s1 = c;
s1[i+1] = 0;
i++;
}
if (c == 8 && i>0)
{
i--;
s1 = 0;
}
setcolor(BLUE);
setfillstyle(SOLID_FILL, BLUE);
bar(getmaxx()/2 - 69, getmaxy()/2 - 3,getmaxx()/2 + 69, getmaxy()/2 + 9);
setcolor(YELLOW);
outtextxy((getmaxx()-textwidth(s))/2 - 4, getmaxy()/2 - 1, s1);
} while(c != 13 && c != 27);
putimage(getmaxx()/2 - 70, getmaxy()/2 - 20, buf, COPY_PUT);
free(buf);
if (c == 13)
{
i = atoi(s1);
weight[start][end] = i;
weight[end][start] = i;
return i;
}
else
return -1;
}

void get_weight()
{
int x, y, oldx, oldy, i, OK = 0, start, end;
char s[5];
setwritemode(XOR_PUT);
setcolor(GREEN);
for (i=0; i<sonut; i++)
if (abs(nut.x - xmouse) < 4 && abs(nut.y - ymouse) < 4)
{
start = i;
oldx = x = nut.x;
oldy = y = nut.y;
OK = 1;
break;
}
if (!OK)
return;
hide_mouse();
line(x, y, oldx, oldy);
clear_mouse();
show_mouse();
do {
get_mouse_button(&lbutton, &rbutton, &xmouse, &ymouse);
if (oldx != xmouse || oldy != ymouse)
{
hide_mouse();
line(x, y, oldx, oldy);
oldx = xmouse;
oldy = ymouse;
line(x, y, oldx, oldy);
show_mouse();
}
} while (lbutton == 0);
OK = 0;
hide_mouse();
line(x, y, oldx, oldy);
for (i=0; i<sonut; i++)
if (abs(nut.x - xmouse) < 4 && abs(nut.y - ymouse) < 4)
{
end = i;
OK = 1;
break;
}
if (OK && end != start)
{
if ((i = input_weight(start, end)) != -1)
{
setcolor(GREEN);
line(x, y, nut[end].x, nut[end].y);
itoa(i, s, 10);
setcolor(RED);
outtextxy(x + (nut[end].x - x) / 2 + 4, y + (nut[end].y - y) / 2 + 4, s);
}
}
setwritemode(COPY_PUT);
show_mouse();
}

void main()
{
int done = 0;
char c, s[4];

initialize();
do {
get_mouse();
if (kbhit())
{
c = toupper(getch());
switch(c)
{
case 'Q' : done = 1; break;
case 'S' : DFS(); break;
}
}
if (rbutton == 1 && index(xmouse, ymouse, 10) == -1)
{
hide_mouse();
if (themduoc)
{
setcolor(WHITE);
circle(xmouse, ymouse, 4);
itoa(sonut, s, 10);
setcolor(CYAN);
outtextxy(xmouse+6, ymouse-6, s);
nut[sonut].x = xmouse;
nut[sonut].y = ymouse;
sonut++;
if (sonut>=MAX)
themduoc = 0;
}
clear_mouse();
show_mouse();
}
if (lbutton == 1)
{
get_weight();
clear_mouse();
}
} while (!done);
closegraph();
}

void out(char *s)
{
setcolor(BLUE);
setfillstyle(SOLID_FILL, BLUE);
bar(1, 36, getmaxx()-1, 46);
setcolor(YELLOW);
outtextxy(4, 38, s);
}

int top, stack[MAX];
int visited[MAX];

void push(int value)
{
stack[++top] = value;
visited[value] = 1;
}

void pop(int *value)
{
*value = stack[top--];
}

int get()
{
if (!isempty())
return stack[top];
else
return -1;
}

int isempty(void)
{
return (top == -1);
}

int xpos = 1;

void visit(int nutxet)
{
int i, OK;
char s[3];

push(nutxet);
setcolor(YELLOW); itoa(nutxet, s, 10); outtextxy(xpos++*20, 38, s);
circle(nut[nutxet].x, nut[nutxet].y, 4); delay(1000);
visited[nutxet] = 1;
for (i=0; i<sonut; i++)
if (weight[nutxet] != -1 && visited == 0)
visit(i);
pop(&nutxet);
}

void DFS()
{
int start=-1, size, nutxet, i, OK;
void far *buf;
char *s = {"Dung nut trai de chon nut dau."};

size = imagesize(1, 36, getmaxx()-1, 46);
buf = malloc(size);
getimage(1, 36, getmaxx()-1, 46, buf);
out(s);
do {
get_mouse();
start = index(xmouse, ymouse, 1);
} while (rbutton == 0 && start == -1);
if (lbutton == 1)
{
clear_mouse();
hide_mouse();
setcolor(RED);
circle(nut[start].x, nut[start].y, 4);
setcolor(BLUE);
setfillstyle(SOLID_FILL, BLUE);
bar(1, 36, getmaxx()-1, 46);
/* Bat dau giai thuat */
top = -1;
for (i=0; i<sonut; i++)
visited = 0;
visit(start);
/* Ket thuc giai thuat */
show_mouse();
getch();
}
putimage(1, 36, buf, COPY_PUT);
free(buf);
clear_mouse();
hide_mouse();
setcolor(WHITE);
if (start != -1)
circle(nut[start].x, nut[start].y, 4);
show_mouse();
}

/* Bai tap 3_21 - Duyet cay theo muc */
#include <stdio.h>
#include <alloc.h>

#define MAX 100

typedef int element_type;
typedef struct node {
element_type element;
struct node *left, *right;
} NODE;

NODE *queue[MAX + 1];
int front, rear, queue_size;

void khoi_tao_queue()
{
front = rear = 0;
queue_size = 0;
}

int is_empty()
{
return (queue_size == 0);
}

int is_full()
{
return (queue_size == MAX);
}

int push(NODE *value)
{
if (queue_size < MAX)
{
queue_size++;
queue[rear++] = value;
if (rear == MAX)
rear = 0;
}
return rear;
}

int pop(NODE **value)
{
if (queue_size > 0)
{
*value = queue[front++];
if (front > MAX)
front = 0;
queue_size--;
}
return front;
}

NODE *root;

void khoi_tao_cay(NODE ** root)
{
*root = NULL;
}

void insert(NODE *tmp, NODE **root)
{

if (tmp->element < (*root)->element)
if ((*root)->left)
insert(tmp, &(*root)->left);
else
(*root)->left = tmp;
else
if ((*root)->right)
insert(tmp, &(*root)->right);
else
(*root)->right = tmp;
}

void insert_node(element_type e, NODE **root)
{
NODE *tmp;

tmp = (NODE *)malloc(sizeof(NODE));
tmp->element = e;
tmp->left = NULL;
tmp->right = NULL;
if (*root == NULL)
*root = tmp;
else
insert(tmp, root);
}

void nhap_cay(NODE **root)
{
element_type e;
do {
printf("\nNhap element (-1 de ket thuc) : ");
scanf("%d", &e);
if (e != -1)
insert_node(e, root);
} while (e != -1);
}

void duyet_cay_level(NODE *root)
{
NODE *p;
khoi_tao_queue();
if (root != NULL)
push(root);
while (!is_empty())
{
pop(&p);
printf("%d ", p->element);
if (p->left != NULL)
push(p->left);
if (p->right != NULL)
push(p->right);
}
}

void main()
{
khoi_tao_cay(&root);
nhap_cay(&root);
duyet_cay_level(root);
getch();
}

/* Bai tap 3_87 - Dem so nut trung gian trong mot cay */
#include <stdio.h>
#include <alloc.h>

typedef int element_type;
typedef struct node {
element_type element;
struct node *left, *right;
} NODE;

NODE *root;

#define max(a,b) ((a) > (b)? (a) : (b))

void khoi_tao_cay(NODE ** root)
{
*root = NULL;
}

void insert(NODE *tmp, NODE **root)
{

if (tmp->element < (*root)->element)
if ((*root)->left)
insert(tmp, &(*root)->left);
else
(*root)->left = tmp;
else
if ((*root)->right)
insert(tmp, &(*root)->right);
else
(*root)->right = tmp;
}

void insert_node(element_type e, NODE **root)
{
NODE *tmp;

tmp = (NODE *)malloc(sizeof(NODE));
tmp->element = e;
tmp->left = NULL;
tmp->right = NULL;
if (*root == NULL)
*root = tmp;
else
insert(tmp, root);
}

void nhap_cay(NODE **root)
{
element_type e;
do {
printf("\nNhap element (-1 de ket thuc) : ");
scanf("%d", &e);
if (e != -1)
insert_node(e, root);
} while (e != -1);
}

int dem_nut_tg(NODE *parent, NODE *root)
{
if (root == NULL)
return 0;
else
if (root->left == NULL && root->right == NULL)
return 0;
else
{
if (parent != NULL)
return dem_nut_tg(root, root->left) +
dem_nut_tg(root, root->right) + 1;
else
return dem_nut_tg(root, root->left) +
dem_nut_tg(root, root->right) ;
}
}

void main()
{
khoi_tao_cay(&root);
nhap_cay(&root);
printf("\nSo nut trung gian cua cay = %d", dem_nut_tg(NULL, root));
getch();
}

/* Bai tap 3_13 - Quan ly danh sach sinh vien bang danh sach da lien ket */
#include <stdio.h>
#include <conio.h>
#include <alloc.h>

typedef struct tagsinhvien {
char hoten[40];
char mslop[6];
struct tagsinhvien *nexthoten, *nextmslop;
} SINHVIEN;

SINHVIEN *headht, *headms;

void initialize()
{
headht = (SINHVIEN *)malloc(sizeof(SINHVIEN));
headht->nexthoten = NULL;
headms = (SINHVIEN *)malloc(sizeof(SINHVIEN));
headms->nextmslop = NULL;
}

void release(SINHVIEN *s)
{
if (s->nexthoten)
release(s->nexthoten);
free(s);
}

void cleanup()
{
if (headht->nexthoten)
release(headht->nexthoten);
free(headht);
free(headms);
}

void inds_ht(SINHVIEN *s)
{
if (s == NULL)
return;
printf("\n%-6s %-40s", s->mslop, s->hoten);
inds_ht(s->nexthoten);
}

void inds_ms(SINHVIEN *s)
{
if (s == NULL)
return;
printf("\n%-6s %-40s", s->mslop, s->hoten);
inds_ms(s->nextmslop);
}

void in_hoten()
{
if (headht->nexthoten)
inds_ht(headht->nexthoten);
}

void in_mslop()
{
if (headms->nextmslop)
inds_ms(headms->nextmslop);
}

void insert_hoten(SINHVIEN *s)
{
SINHVIEN *a, *b;
if (headht->nexthoten == NULL)
headht->nexthoten = s;
else
{
a = headht;
b = headht->nexthoten;
while (strcmp(b->hoten, s->hoten)<0 && b!= NULL)
{
a = a->nexthoten;
b = b->nexthoten;
}
a->nexthoten = s;
s->nexthoten = b;
}
}

void insert_mslop(SINHVIEN *s)
{
SINHVIEN *a, *b;
if (headms->nextmslop == NULL)
headms->nextmslop = s;
else
{
a = headms;
b = headms->nextmslop;
while (strcmp(b->mslop, s->mslop)<0 && b!= NULL)
{
a = a->nextmslop;
b = b->nextmslop;
}
a->nextmslop = s;
s->nextmslop = b;
}
}

void insert(char *hoten, char *mslop)
{
SINHVIEN *s;

s = (SINHVIEN *)malloc(sizeof(SINHVIEN));
strncpy(s->hoten, hoten, 40);
strncpy(s->mslop, mslop, 6);
s->nexthoten = s->nextmslop = NULL;
insert_hoten(s);
insert_mslop(s);
}

void nhapds()
{
int done = 0;
char hoten[40], mslop[6];
do {
printf("\nNhap ho ten (trong de thoat) : ");
gets(hoten);
if (strcmp(hoten, "") == 0)
done = 1;
else
{
printf("\nNhap ma so lop : ");
gets(mslop);
insert(hoten, mslop);
}
} while (!done);
}

void main()
{
initialize();
nhapds();
printf("\nDanh sach theo ho ten : ");
in_hoten();
printf("\nDanh sach theo ma so lop : ");
in_mslop();
getch();
cleanup();
}

/* Bai tap 3_79 - Tim chu trinh EULER cua mot do thi */
#include <dos.h>
#include <graphics.h>
#include <alloc.h>
#include "mouse.inc"

#pragma warn -sus

/* Toi da 100 nut */
#define MAX 100

int gr_drive=DETECT, gr_mode;
unsigned char lbutton, rbutton;
int xmouse, ymouse;

int sonut = 0, socanh = 0;
typedef struct tagnode {
int x, y; /* Vi tri tren man hinh */
} NODE;

NODE nut[MAX];
int themduoc = 1;
int weight[MAX][MAX];

void initialize()
{
char s1[] = "Nhap nut phai chuot de them nut";
char s2[] = "Nhap nut trai chuot va re de them duong noi";
char s3[] = "Nhan phim Q de thoat - S de bat dau tim chu trinh Euler";
int i, j;
initgraph(&gr_drive, &gr_mode, "");
reset_mouse();
setcolor(YELLOW);
rectangle(0, 0, getmaxx(), getmaxy());
outtextxy((getmaxx()-textwidth(s1))/2, 5, s1);
outtextxy((getmaxx()-textwidth(s2))/2, 15, s2);
outtextxy((getmaxx()-textwidth(s3))/2, 25, s3);
line(0, 35, getmaxx(), 35);
line(51, 35, 51, getmaxy()-1);
set_mouse_hlimits(56, getmaxx()-6);
set_mouse_vlimits(40, getmaxy()-6);
for (i=0; i<MAX; i++)
for (j=0; j<MAX; j++)
weight[j] = -1;
show_mouse();
}

int index(int x, int y, int heso)
{
int i, OK = 0;
for (i=0; i<sonut; i++)
if (abs(nut.x - x) < 4*heso && abs(nut.y - y) < 4*heso)
{
OK = 1;
break;
}
if (OK)
return i;
else
return -1;
}

void get_mouse()
{
do {
get_mouse_button(&lbutton, &rbutton, &xmouse, &ymouse);
} while (lbutton == 0 && rbutton == 0 && !kbhit());
}

void clear_mouse()
{
do {
get_mouse_button(&lbutton, &rbutton, &xmouse, &ymouse);
} while (lbutton == 1 || rbutton == 1);
}

void get_line()
{
int x, y, oldx, oldy, i, OK = 0, start, end;
setwritemode(XOR_PUT);
setcolor(GREEN);
for (i=0; i<sonut; i++)
if (abs(nut.x - xmouse) < 4 && abs(nut.y - ymouse) < 4)
{
start = i;
oldx = x = nut.x;
oldy = y = nut.y;
OK = 1;
break;
}
if (!OK)
return;
hide_mouse();
line(x, y, oldx, oldy);
clear_mouse();
show_mouse();
do {
get_mouse_button(&lbutton, &rbutton, &xmouse, &ymouse);
if (oldx != xmouse || oldy != ymouse)
{
hide_mouse();
line(x, y, oldx, oldy);
oldx = xmouse;
oldy = ymouse;
line(x, y, oldx, oldy);
show_mouse();
}
} while (lbutton == 0);
OK = 0;
hide_mouse();
line(x, y, oldx, oldy);
for (i=0; i<sonut; i++)
if (abs(nut.x - xmouse) < 4 && abs(nut.y - ymouse) < 4 )
{
end = i;
OK = 1;
break;
}
if (OK && end != start)
{
setcolor(GREEN);
line(x, y, nut[end].x, nut[end].y);
weight[start][end] = 1;
weight[end][start] = 1;
socanh++;
}
setwritemode(COPY_PUT);
show_mouse();
}

void main()
{
int done = 0;
char c, s[4];
void Euler();

initialize();
do {
get_mouse();
if (kbhit())
{
c = toupper(getch());
switch(c)
{
case 'Q' : done = 1; break;
case 'S' : Euler(); break;
}
}
if (rbutton == 1 && index(xmouse, ymouse, 10) == -1)
{
hide_mouse();
if (themduoc)
{
setcolor(WHITE);
circle(xmouse, ymouse, 4);
itoa(sonut, s, 10);
setcolor(CYAN);
outtextxy(xmouse+6, ymouse-6, s);
nut[sonut].x = xmouse;
nut[sonut].y = ymouse;
sonut++;
if (sonut>=MAX)
themduoc = 0;
}
clear_mouse();
show_mouse();
}
if (lbutton == 1)
{
get_line();
clear_mouse();
}
} while (!done);
closegraph();
}

int top;
struct {
int v1, v2;
} stack[MAX];

void push(int v1, int v2)
{
stack[++top].v1 = v1;
stack[top].v2 = v2;
}

void pop(int *v1, int *v2)
{
*v1 = stack[top].v1;
*v2 = stack[top--].v2;
}

int get(int *v1, int *v2)
{
if (!isempty())
{
*v1 = stack[top].v1;
*v2 = stack[top].v2;
return 1;
}
else
return 0;
}

int isempty(void)
{
return (top == -1);
}

int canh[MAX][MAX];

void Euler()
{
int size, visited = 0, v1 = 0, v2, i, j, iseuler = 0;
int y, OK = 1, oldv, n;
char s[10], *kq[2] = { "Do thi co chu trinh EULER","Do thi khong co chu trinh EULER"};

setcolor(BLUE);
setfillstyle(SOLID_FILL, BLUE);
bar(getmaxx()/2 - 150, 36, getmaxx()/2 + 150, 48);
setcolor(YELLOW);
for (n=0; n<sonut; n++)
{
y = 40;
top = -1;
for (i=0; i<sonut; i++)
for (j=0; j<sonut; j++)
{
canh[j] = 0; // Canh chua duoc tham
canh[j] = 0; // Canh chua duoc tham
}
v1 = n;
setcolor(YELLOW);
do {
oldv = v1;
for (i = 0; i<sonut; i++)
if (canh[v1] == 0 && weight[v1] != -1)
push(v1, i);
pop(&v2, &v1);
if (canh[v2][v1] == 0)
{
canh[v2][v1] = 1;
canh[v1][v2] = 1;
visited++;
sprintf(s, "{%d %d}", v2, v1);
outtextxy(5, y, s);
y += 10;
if (oldv != v2)
OK = 0;
}
} while ((!isempty() || v1 != 0) && visited != socanh);
outtextxy(5, getmaxy()-40, "EULER");
setcolor(RED);
if (v1 != 0 || OK == 0 || oldv != v2)
line(5, getmaxy()-36, 45, getmaxy()-36);
else
{
iseuler = 1;
setcolor(BLUE);
setfillstyle(SOLID_FILL, BLUE);
bar(getmaxx()/2 - 150, 36, getmaxx()/2 + 150, 48);
setcolor(YELLOW);
outtextxy((getmaxx()-textwidth(kq[0]))/2, 38, kq[0]);
getch();
break;
}
setcolor(BLACK);
setfillstyle(SOLID_FILL, BLACK);
getch();
bar(1, 36, 50, getmaxy()-1);
}
if (!iseuler)
{
setcolor(BLUE);
setfillstyle(SOLID_FILL, BLUE);
bar(getmaxx()/2 - 150, 36, getmaxx()/2 + 150, 48);
setcolor(YELLOW);
outtextxy((getmaxx()-textwidth(kq[1]))/2, 38, kq[1]);
}
setcolor(BLACK);
setfillstyle(SOLID_FILL, BLACK);
bar(1, 36, 50, getmaxy()-1);
}

/* Bai tap 3_32 - Tim phan giao cua hai danh sach lien ket */
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <alloc.h>

typedef struct tagsl {
int key;
struct tagsl *next;
} SL;

SL *L1, *L2, *L;

void initialize()
{
L1 = L2 = L = NULL;
clrscr();
randomize();
}

void cleanup()
{
SL *f;

while (L1 != NULL)
{
f = L1;
L1 = L1->next;
free(f);
}
while (L2 != NULL)
{
f = L2;
L2 = L2->next;
free(f);
}
while (L != NULL)
{
f = L;
L = L->next;
free(f);
}
L1 = L2 = L = NULL;
}

void insert(SL **l, int key)
{
SL *s, *a, *b;

s = (SL *)malloc(sizeof(SL));
s->key = key;
s->next = NULL;
if (*l==NULL)
*l = s;
else
{
a = NULL;
b = *l;
while (b!=NULL && b->key < key)
{
a = b;
b = b->next;
}
if (a == NULL)
{
s->next = *l;
*l = s;
}
else
{
a->next = s;
s->next = b;
}
}
}

void inds(SL *l)
{
SL *f;
printf("\nDanh sach : ");
if (l == NULL)
{
printf("rong");
return;
}
f = l;
while (f != NULL)
{
printf("%3d", f->key);
f = f->next;
}
}

void taods(SL **l)
{
int i, j, trung[50];
for (j=0; j<50; j++)
trung[j] = 0;
i = 0;
while(i<20)
{
do {
j = random(50);
} while(trung[j] == 1);
trung[j] = 1;
insert(l, j);
i++;
}
}

void giaosl(SL *l1, SL *l2, SL **l)
{
while (l1 != NULL && l2 != NULL)
{
if (l1->key < l2->key)
{
while (l1->key != l2->key && l1 != NULL)
l1 = l1->next;
if (l1 != NULL)
{
insert(l, l2->key);
l2 = l2->next;
l1 = l1->next;
}
}
else if(l1->key > l2->key)
{
while (l2->key != l1->key && l2 != NULL)
l2 = l2->next;
if (l2 != NULL)
{
insert(l, l1->key);
l2 = l2->next;
l1 = l1->next;
}
}
else if(l1->key == l2->key)
{
insert(l, l1->key);
l2 = l2->next;
l1 = l1->next;
}
}
}

void main()
{
initialize();
taods(&L1);
taods(&L2);
inds(L1);
inds(L2);
printf("\nGiao cua hai danh sach tren = ");
giaosl(L1, L2, &L);
inds(L);
cleanup();
getch();
}

/* Bai tap 3_81 - Tim chu trinh HAMILTON cua mot do thi */
#include <dos.h>
#include <graphics.h>
#include <alloc.h>
#include "mouse.inc"

#pragma warn -sus

/* Toi da 100 nut */
#define MAX 100

int gr_drive=DETECT, gr_mode;
unsigned char lbutton, rbutton;
int xmouse, ymouse;

int sonut = 0, socanh = 0;
typedef struct tagnode {
int x, y; /* Vi tri tren man hinh */
} NODE;

NODE nut[MAX];
int themduoc = 1;
int weight[MAX][MAX];

void initialize()
{
char s1[] = "Nhap nut phai chuot de them nut";
char s2[] = "Nhap nut trai chuot va re de them duong noi";
char s3[] = "Nhan phim Q de thoat - S de bat dau tim chu trinh Hamilton";
int i, j;
initgraph(&gr_drive, &gr_mode, "");
reset_mouse();
setcolor(YELLOW);
rectangle(0, 0, getmaxx(), getmaxy());
outtextxy((getmaxx()-textwidth(s1))/2, 5, s1);
outtextxy((getmaxx()-textwidth(s2))/2, 15, s2);
outtextxy((getmaxx()-textwidth(s3))/2, 25, s3);
line(0, 35, getmaxx(), 35);
line(51, 35, 51, getmaxy()-1);
set_mouse_hlimits(56, getmaxx()-6);
set_mouse_vlimits(40, getmaxy()-6);
for (i=0; i<MAX; i++)
for (j=0; j<MAX; j++)
weight[j] = -1;
show_mouse();
}

int index(int x, int y, int heso)
{
int i, OK = 0;
for (i=0; i<sonut; i++)
if (abs(nut.x - x) < 4*heso && abs(nut.y - y) < 4*heso)
{
OK = 1;
break;
}
if (OK)
return i;
else
return -1;
}

void get_mouse()
{
do {
get_mouse_button(&lbutton, &rbutton, &xmouse, &ymouse);
} while (lbutton == 0 && rbutton == 0 && !kbhit());
}

void clear_mouse()
{
do {
get_mouse_button(&lbutton, &rbutton, &xmouse, &ymouse);
} while (lbutton == 1 || rbutton == 1);
}

void get_line()
{
int x, y, oldx, oldy, i, OK = 0, start, end;
setwritemode(XOR_PUT);
setcolor(GREEN);
for (i=0; i<sonut; i++)
if (abs(nut.x - xmouse) < 4 && abs(nut.y - ymouse) < 4)
{
start = i;
oldx = x = nut.x;
oldy = y = nut.y;
OK = 1;
break;
}
if (!OK)
return;
hide_mouse();
line(x, y, oldx, oldy);
clear_mouse();
show_mouse();
do {
get_mouse_button(&lbutton, &rbutton, &xmouse, &ymouse);
if (oldx != xmouse || oldy != ymouse)
{
hide_mouse();
line(x, y, oldx, oldy);
oldx = xmouse;
oldy = ymouse;
line(x, y, oldx, oldy);
show_mouse();
}
} while (lbutton == 0);
OK = 0;
hide_mouse();
line(x, y, oldx, oldy);
for (i=0; i<sonut; i++)
if (abs(nut.x - xmouse) < 4 && abs(nut.y - ymouse) < 4 )
{
end = i;
OK = 1;
break;
}
if (OK && end != start)
{
setcolor(GREEN);
line(x, y, nut[end].x, nut[end].y);
weight[start][end] = 1;
weight[end][start] = 1;
socanh++;
}
setwritemode(COPY_PUT);
show_mouse();
}

void main()
{
int done = 0;
char c, s[4];
void Hamilton();

initialize();
do {
get_mouse();
if (kbhit())
{
c = toupper(getch());
switch(c)
{
case 'Q' : done = 1; break;
case 'S' : Hamilton(); break;
}
}
if (rbutton == 1 && index(xmouse, ymouse, 10) == -1)
{
hide_mouse();
if (themduoc)
{
setcolor(WHITE);
circle(xmouse, ymouse, 4);
itoa(sonut, s, 10);
setcolor(CYAN);
outtextxy(xmouse+6, ymouse-6, s);
nut[sonut].x = xmouse;
nut[sonut].y = ymouse;
sonut++;
if (sonut>=MAX)
themduoc = 0;
}
clear_mouse();
show_mouse();
}
if (lbutton == 1)
{
get_line();
clear_mouse();
}
} while (!done);
closegraph();
}

int top;
int stack[MAX];

void push(int v)
{
stack[++top] = v;
}

void pop(int *v)
{
*v = stack[top--];
}

int isempty(void)
{
return (top == -1);
}

int dinh[MAX];

void Hamilton()
{
int size, visited = 0, v1 = 0, v2, i, j, iseuler = 0;
int y, OK = 1, oldv, n;
char s[10], *kq[2] = { "Do thi co chu trinh HAMILTON","Do thi khong co chu trinh HAMILTON"};

hide_mouse();
setcolor(BLUE);
setfillstyle(SOLID_FILL, BLUE);
bar(getmaxx()/2 - 150, 36, getmaxx()/2 + 150, 48);
setcolor(YELLOW);
for (n=0; n<sonut; n++)
{
setcolor(WHITE);
for (i=0; i<sonut; i++)
for (j=0; j<sonut; j++)
if (weight[j] != -1)
line(nut.x, nut.y, nut[j].x, nut[j].y);
y = 40;
top = -1;
for (i=0; i<sonut; i++)
dinh = 0; // Dinh chua duoc tham
v1 = n;
setcolor(YELLOW);
push(v1);
dinh[v1] = 1;
visited = 1;
sprintf(s, "%d", v1);
outtextxy(5, y, s);
y+=10;
do {
oldv = v1;
pop(&v1);
if (dinh[v1] == 0 && weight[oldv][v1] != -1)
{
dinh[v1] = 1;
visited++;
sprintf(s, "%d", v1);
outtextxy(5, y, s);
line(nut[oldv].x, nut[oldv].y, nut[v1].x, nut[v1].y);
y += 10;
}
for (i = 0; i<sonut; i++)
if (dinh == 0 && weight[v1] != -1)
push(i);
} while ((!isempty() || v1 != n) && visited != sonut);
outtextxy(5, getmaxy()-40, "HAMIL");
setcolor(RED);
if (weight[n][v1] == -1)
line(5, getmaxy()-36, 45, getmaxy()-36);
else
{
setcolor(YELLOW);
line(nut[n].x, nut[n].y, nut[v1].x, nut[v1].y);
iseuler = 1;
setcolor(BLUE);
setfillstyle(SOLID_FILL, BLUE);
bar(getmaxx()/2 - 150, 36, getmaxx()/2 + 150, 48);
setcolor(YELLOW);
outtextxy((getmaxx()-textwidth(kq[0]))/2, 38, kq[0]);
getch();
break;
}
setcolor(BLACK);
setfillstyle(SOLID_FILL, BLACK);
getch();
bar(1, 36, 50, getmaxy()-1);
}
if (!iseuler)
{
setcolor(BLUE);
setfillstyle(SOLID_FILL, BLUE);
bar(getmaxx()/2 - 150, 36, getmaxx()/2 + 150, 48);
setcolor(YELLOW);
outtextxy((getmaxx()-textwidth(kq[1]))/2, 38, kq[1]);
}
setcolor(BLACK);
setfillstyle(SOLID_FILL, BLACK);
bar(1, 36, 50, getmaxy()-1);
show_mouse();
}

/* Bai tap 3_50 - Trinh bay cac buoc chuyen n dia tu coc A sang coc C
trong bai toan thap Hanoi dung ba dia */
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <dos.h>

#define A 0
#define B 1
#define C 2

void hanoi(int from, int to, int dia)
{
int trunggian;
if (dia == 1)
printf("\nChuyen 1 dia tu coc %c sang coc %c", 'A'+from, 'A'+to);
else
{
if ((from == A && to == C) || (from == C && to == A))
trunggian = B;
else if ((from == A && to == B) || (from == B && to == A))
trunggian = C;
else if ((from == C && to == B) || (from == B && to == C))
trunggian = A;
hanoi(from, trunggian, dia-1);
hanoi(from, to, 1);
hanoi(trunggian, to, dia-1);
}
}

void main()
{
int n;

printf("\nCho biet so dia ( 3 -> 6 ): ");
do {
scanf("%d", &n);
} while (n < 3 || n > 6);
hanoi(A, C, n);
getch();
}

/* Bai tap 3_51 - Trinh bay cac buoc chuyen n dia tu coc A sang coc D
trong bai toan thap Hanoi dung bon dia */
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <dos.h>

#define A 0
#define B 1
#define C 2
#define D 3

void hanoi(int from, int to, int dia)
{
int tg1, tg2, dia2;
if (dia <= 1)
printf("\nChuyen 1 dia tu coc %c sang coc %c", 'A'+from, 'A'+to);
else
{
if ((from == A && to == D) || (from == D && to == A))
{
tg1 = B;
tg2 = C;
}
else if ((from == A && to == B) || (from == B && to == A))
{
tg1 = C;
tg2 = D;
}
else if ((from == A && to == C) || (from == C && to == A))
{
tg1 = B;
tg2 = D;
}
else if ((from == B && to == C) || (from == C && to == B))
{
tg1 = A;
tg2 = D;
}
else if ((from == B && to == D) || (from == D && to == B))
{
tg1 = A;
tg2 = C;
}
else if ((from == C && to == D) || (from == D && to == C))
{
tg1 = A;
tg2 = B;
}
dia2 = dia / 2;
if (dia % 2 == 1)
{
hanoi(from, tg1, dia2);
hanoi(from, tg2, dia2);
hanoi(from, to, 1);
hanoi(tg2, to, dia2);
hanoi(tg1, to, dia2);
}
else
{
hanoi(from, tg1, dia2);
if (dia2 > 1)
{
hanoi(from, tg2, dia2-1);
hanoi(from, to, 1);
hanoi(tg2, to, dia2-1);
}
else
hanoi(from, to, 1);
hanoi(tg1, to, dia2);
}
}
}

void main()
{
int n;

printf("\nCho biet so dia ( 3 -> 6 ): ");
do {
scanf("%d", &n);
} while (n < 3 || n > 6);
hanoi(A, D, n);
getch();
}

/* Bai tap 3_88 - Cai dat HASH */
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define MAX 100

typedef struct tagitem {
int value;
char s[5];
} ITEM;

ITEM danhsach[MAX];
int HASH[MAX];

int hash(ITEM item)
{
long l;
l = (long)item.s[0] << 24 +
(long)item.s[1] << 16 +
(long)item.s[2] << 8 +
(long)item.s[3];

return (int)(l%MAX);
}

void insert_hash(ITEM item, int index)
{
int hfunc;

hfunc = hash(item);
while(HASH[hfunc] != -1)
{
hfunc += 26;
if (hfunc > MAX)
hfunc %= MAX;
}
HASH[hfunc] = index;
}

void initialize()
{
int i, j;
ITEM item;

clrscr();
randomize();
for (i=0; i<MAX; i++)
HASH = -1;
for (i=0; i<20; i++)
{
item.value = random(20);
for (j=0; j<4; j++)
item.s[j] = random(26) + 'a';
item.s[4] = 0;
danhsach = item;
insert_hash(item, i);
printf("\n%s %d", item.s, item.value);
}
}

void main()
{
int done = 0, hfunc, oldhfunc, error;
ITEM item;
initialize();
do {
printf("\nNhap chuoi tim kiem (toi da 4 ky tu) : ");
gets(item.s);
if (strlen(item.s)>0)
{
oldhfunc = hfunc = hash(item);
error = 0;
while (strcmp(item.s, danhsach[hfunc].s) != 0)
{
hfunc += 26;
hfunc %= MAX;
if (oldhfunc == hfunc || HASH[hfunc] == -1)
{
printf("Khong tim thay");
error = 1;
break;
}
}
if (!error)
{
printf("Tim thay tai %d : %s %d", HASH[hfunc], danhsach[HASH[hfunc]].s,
danhsach[HASH[hfunc]].value);
}
}
else
done = 1;
} while (!done);
}

/* Bai tap 3_52 - In bieu thuc dang hau to cua mot bieu thuc trung to */
#include <stdio.h>
#include <conio.h>

#define MAX 100

#define PLUS 0 /* Dau cong */
#define MINUS 1 /* Dau tru */
#define MULTIPLE 2 /* Dau nhan */
#define DIVIDE 3 /* Dau chia */
#define LPAREN 4 /* Dau mo ngoac don */
#define RPAREN 5 /* Dau dong ngoac don */

int top;

struct {
int toantu;
} stack[MAX];

void push (int tt)
{
if (top < MAX-1)
stack[++top].toantu = tt;
}

int isempty()
{
return top == -1;
}

int pop (int *tt)
{
if (!isempty())
{
*tt = stack[top--].toantu;
return 1;
}
return 0;
}

int get (int *tt)
{
if (!isempty())
{
*tt = stack[top].toantu;
return 1;
}
return 0;
}

void xet(int tt)
{
char chuoi[] = "+-*/";
int uutien[] = {0,0,1,1,-1,-1};
int toantu, done = 0, val;

if (isempty())
push(tt);
else
{
do {
if (get(&toantu))
{
if (uutien[tt] <= uutien[toantu])
{
pop(&toantu);
printf("%c ", chuoi[toantu]);
}
else
{
push(tt);
done = 1;
}
}
else
{
done = 1;
push(tt);
}
} while (!done);
}
}

void in_hauto(char *expr)
{
int len, i=0, ttu, done;
char c, chuoi[]="+-*/";
top = -1;
len = strlen(expr);
do {
c = expr[i++];
while (c == ' ' && i < len-1)
c = expr[i++];
switch (c)
{
case '0' :
case '1' :
case '2' :
case '3' :
case '4' :
case '5' :
case '6' :
case '7' :
case '8' :
case '9' : printf("%c ", c); break;
case '+' : xet(PLUS); break;
case '-' : xet(MINUS); break;
case '*' : xet(MULTIPLE); break;
case '/' : xet(DIVIDE); break;
case '(' : push(LPAREN); break;
case ')' : done = 0;
do {
if (isempty())
{
done = 1;
printf("\n\nError\n");
}
else
{
pop(&ttu);
if (ttu != LPAREN)
printf("%c ", chuoi[ttu]);
else
done = 1;
}
} while (!done);
break;
}
} while (i < len);
while (!isempty())
{
pop(&ttu);
printf("%c ", chuoi[ttu]);
}
}

void main()
{
char expr[50];
int done = 0;

printf("\nChuong trinh in bieu thuc hau to tuong ung voi mot bieu thuc"
"trung to hop le"
"\nChu y :"
"\nCac toan hang chi tu 0 den 9"
"\nCac toan tu chi gom + - * / ( )\n");
do {
printf("\nNhap mot bieu thuc trung to hop le (trong de thoat): ");
gets(expr);
if (strlen(expr) > 0)
in_hauto(expr);
else
done = 1;
} while (!done);
}

/* Bai tap 3_34 - Tim phan hieu cua hai danh sach lien ket */
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <alloc.h>

typedef struct tagsl {
int key;
struct tagsl *next;
} SL;

SL *L1, *L2, *L;

void initialize()
{
L1 = L2 = L = NULL;
clrscr();
randomize();
}

void cleanup()
{
SL *f;

while (L1 != NULL)
{
f = L1;
L1 = L1->next;
free(f);
}
while (L2 != NULL)
{
f = L2;
L2 = L2->next;
free(f);
}
while (L != NULL)
{
f = L;
L = L->next;
free(f);
}
L1 = L2 = L = NULL;
}

void insert(SL **l, int key)
{
SL *s, *a, *b;

s = (SL *)malloc(sizeof(SL));
s->key = key;
s->next = NULL;
if (*l==NULL)
*l = s;
else
{
a = NULL;
b = *l;
while (b!=NULL && b->key < key)
{
a = b;
b = b->next;
}
if (a == NULL)
{
s->next = *l;
*l = s;
}
else
{
a->next = s;
s->next = b;
}
}
}

void inds(SL *l)
{
SL *f;
printf("\nDanh sach : ");
f = l;
while (f != NULL)
{
printf("%3d", f->key);
f = f->next;
}
}

void taods(SL **l)
{
int i, j, trung[50];
for (j=0; j<50; j++)
trung[j] = 0;
i = 0;
while(i<10)
{
do {
j = random(50);
} while(trung[j] == 1);
trung[j] = 1;
insert(l, j);
i++;
}
}

void hieusl(SL *l1, SL *l2, SL **l)
{
while (l1 != NULL && l2 != NULL)
{
while (l2->key < l1->key && l2 != NULL)
l2 = l2->next;
if (l2 != NULL)
{
if (l1->key != l2->key)
{
insert(l, l1->key);
l1 = l1->next;
}
else
{
l1 = l1->next;
l2 = l2->next;
}
}
}
while (l1 != NULL)
{
insert(l, l1->key);
l1 = l1->next;
}
}
/*
if (l1->key < l2->key)
{
insert(l, l1->key);
l1 = l1->next;
}
else if(l1->key > l2->key)
{
insert(l, l2->key);
l2 = l2->next;
}
else if(l1->key == l2->key)
{
insert(l, l1->key);
l2 = l2->next;
l1 = l1->next;
}
}
if (l1 != NULL)
{
while (l1 != NULL)
{
insert(l, l1->key);
l1 = l1->next;
}
}
if (l2 != NULL)
{
while (l2 != NULL)
{
insert(l, l2->key);
l2 = l2->next;
}
*/
void main()
{
initialize();
taods(&L1);
taods(&L2);
inds(L1);
inds(L2);
printf("\nHieu cua danh sach L1 voi L2 = ");
hieusl(L1, L2, &L);
inds(L);
cleanup();
getch();
}

/* Bai tap 3_86 - Tim tat ca cac hoan vi cua mot mang 5 phan tu */
#include <stdio.h>

int mang[5];

void swap (int *x, int *y)
{
int tmp;
tmp = *x;
*x = *y;
*y = tmp;
}

void hoanvi(int k)
{
int j;

if (k==1)
{
printf("\n");
for (j=0; j<n; j++)
printf("%d ", mang[j]);
}
else
for (j=k-1; j>=0; j--)
{
swap(&mang[k-1], &mang[j]);
hoanvi(k-1);
swap(&mang[j], &mang[k-1]);
}
}

void main()
{
int i;

for (i=0; i<5; i++)
mang = i;
hoanvi(5);
getch();
}

/* Bai tap 3_33 - Tim phan hop cua hai danh sach lien ket */
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <alloc.h>

typedef struct tagsl {
int key;
struct tagsl *next;
} SL;

SL *L1, *L2, *L;

void initialize()
{
L1 = L2 = L = NULL;
clrscr();
randomize();
}

void cleanup()
{
SL *f;

while (L1 != NULL)
{
f = L1;
L1 = L1->next;
free(f);
}
while (L2 != NULL)
{
f = L2;
L2 = L2->next;
free(f);
}
while (L != NULL)
{
f = L;
L = L->next;
free(f);
}
L1 = L2 = L = NULL;
}

void insert(SL **l, int key)
{
SL *s, *a, *b;

s = (SL *)malloc(sizeof(SL));
s->key = key;
s->next = NULL;
if (*l==NULL)
*l = s;
else
{
a = NULL;
b = *l;
while (b!=NULL && b->key < key)
{
a = b;
b = b->next;
}
if (a == NULL)
{
s->next = *l;
*l = s;
}
else
{
a->next = s;
s->next = b;
}
}
}

void inds(SL *l)
{
SL *f;
printf("\nDanh sach : ");
f = l;
while (f != NULL)
{
printf("%3d", f->key);
f = f->next;
}
}

void taods(SL **l)
{
int i, j, trung[50];
for (j=0; j<50; j++)
trung[j] = 0;
i = 0;
while(i<10)
{
do {
j = random(50);
} while(trung[j] == 1);
trung[j] = 1;
insert(l, j);
i++;
}
}

void hopsl(SL *l1, SL *l2, SL **l)
{
while (l1 != NULL && l2 != NULL)
{
if (l1->key < l2->key)
{
insert(l, l1->key);
l1 = l1->next;
}
else if(l1->key > l2->key)
{
insert(l, l2->key);
l2 = l2->next;
}
else if(l1->key == l2->key)
{
insert(l, l1->key);
l2 = l2->next;
l1 = l1->next;
}
}
if (l1 != NULL)
{
while (l1 != NULL)
{
insert(l, l1->key);
l1 = l1->next;
}
}
if (l2 != NULL)
{
while (l2 != NULL)
{
insert(l, l2->key);
l2 = l2->next;
}
}
}

void main()
{
initialize();
taods(&L1);
taods(&L2);
inds(L1);
inds(L2);
printf("\nHop cua hai danh sach tren = ");
hopsl(L1, L2, &L);
inds(L);
cleanup();
getch();
}

/* Chen truc tiep */
#include <stdio.h>
#include <stdlib.h>

#define MAX 10
int mang[MAX];

void in_mang(int *mang)
{
int i;
for (i=0; i<MAX; i++)
printf("%d ", mang);
}

void straightinsertsort()
{
int i, j, x;
for (i=1; i<MAX; i++)
{
x = mang;
j = i-1;
while (x < mang[j] && j >= 0)
{
mang[j+1] = mang[j];
j--;
}
mang[j+1] = x;
}
}

void main()
{
int i;

randomize();
for (i=0; i<MAX; i++)
mang = random(100);
printf("\nTruoc khi sap : ");
in_mang(mang);
straightinsertsort();
printf("\nSau khi sap : ");
in_mang(mang);
getch();
}