/* Tim mot phan tu trong mot DSLK khong de quy */
#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;
printf("Cac gia tri cua danh sach : ");
while (tmp != NULL)
{
printf("%d ", tmp->element);
tmp = tmp->next;
}
}

struct node *tim(struct node *first, element_type e)
{
if (first == NULL)
return NULL;
else
{
while (first->element != e && first != NULL)
first = first->next;
return first;
}
}

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

khoi_tao_ds(&first, &last);
nhap_ds(&first, &last);
print_ds(first);
printf("\nNhap gia tri can tim : ");
scanf("%d", &e);
tmp = tim(first, e);
if (tmp)
printf("Tim thay");
else
printf("Khong tim thay");
getch();
}

/* Tim mot phan tu trong mot DSLK */
#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;
printf("Cac gia tri cua danh sach (tang dan) : ");
while (tmp != NULL)
{
printf("%d ", tmp->element);
tmp = tmp->next;
}
}

int tim(struct node *first, int x)
{
int n = 0;
while (first != NULL && first->element < x)
{
n++;
first = first->next;
}
if (first->x != x)
return -1;
return n;
}

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

khoi_tao_ds(&first, &last);
nhap_ds(&first, &last);
print_ds(first);
printf("\nNhap vao gia tri can tim : ");
scanf("%d", &x);
n = tim(first, x);
if (n!=-1)
printf("\nGia tri %d tim thay tai nut thu %d", x, n);
else
printf("\nKhong tim thay gia tri %d", x);
getch();
}

/* Bai tap 3_94 - Bai toan tron tim */
#include <graphics.h>
#include <stdlib.h>
#include <dos.h>
#include <ctype.h>

#define RADIUS 3
#define DELAY 10

int gr_drive=DETECT, gr_mode;
int xvat, yvat, xnguoi, ynguoi;
int dx, dy, left, right, top, bottom;

void initialize()
{
char s1[] = "Nhan phim bat ky de bat dau";
char s2[] = "Nhan phim ESCAPE de ket thuc";

initgraph(&gr_drive, &gr_mode, "");
setcolor(YELLOW);
rectangle(0, 0, getmaxx(), getmaxy());
outtextxy((getmaxx()-textwidth(s1))/2, 4, s1);
line(0, 16, getmaxx(), 16);
getch();
setcolor(BLACK);
setfillstyle(SOLID_FILL, BLACK);
bar(1, 1, getmaxx(), 15);
setcolor(YELLOW);
outtextxy((getmaxx()-textwidth(s1))/2, 4, s2);
setviewport(1, 17, getmaxx()-1, getmaxy()-1, 1);
left = top = 0;
right = getmaxx() - 2;
bottom = getmaxy() - 18;
randomize();
xvat = random(getmaxx()/2);
xnguoi = random(getmaxx()/2)+getmaxx()/2;
yvat = random(getmaxy()/2);
ynguoi = random(getmaxy()/2)+getmaxy()/2;
}

void drawvat(int color)
{
setcolor(color);
circle(xvat, yvat, RADIUS);
}

void drawnguoi(int color)
{
setcolor(color);
rectangle(xnguoi-3, ynguoi-2, xnguoi+3, ynguoi+2);
}

void tinhvat()
{
if (xnguoi >= xvat)
xvat += 2;
if (xnguoi < xvat)
xvat -= 2;
/*
if (xvat < 2)
xvat += 2;
if (xvat > right-2)
xvat = right-2;
*/
if (ynguoi >= yvat)
yvat += 2;
if (ynguoi < yvat)
yvat -= 2;
/*
if (yvat < 2)
yvat += 2;
if (yvat >bottom - 2)
yvat = bottom - 2;
*/
}

void tinhnguoi()
{
xnguoi += dx;
ynguoi += dy;
if (xnguoi < left)
xnguoi = left;
if (xnguoi > right)
xnguoi = right;
if (ynguoi < top)
ynguoi = top;
if (ynguoi > bottom)
ynguoi = bottom;
}

void main()
{
char c, s[] = "Oh! Ban da thua roi";
initialize();
drawvat(YELLOW);
drawnguoi(WHITE);
dx = dy = 0;
do {
if (kbhit())
{
c = toupper(getch());
if (c == 0)
c = getch();
switch(c)
{
case 'A' : dx = 0; break;
case 'S' : dy = 0; break;
case 75 : dx = -2; break;
case 77 : dx = 2; break;
case 72 : dy = -2; break;
case 80 : dy = 2; break;
}
}
delay(DELAY);
drawvat(BLACK);
drawnguoi(BLACK);
tinhnguoi();
tinhvat();
drawvat(YELLOW);
drawnguoi(WHITE);
if (abs(xnguoi-xvat) < 4 && abs(ynguoi-yvat) < 4)
{
setviewport(0, 0, getmaxx(), getmaxy(), 1);
setcolor(BLACK);
setfillstyle(SOLID_FILL, BLACK);
bar(1, 1, getmaxx(), 15);
setcolor(YELLOW);
outtextxy((getmaxx()-textwidth(s))/2, 4, s);
getch();
c = 27;
}
} while (c != 27);
closegraph();
}

/* Kiem tra xem hai cay co dang cau nhau khong */
#include <stdio.h>
#include <alloc.h>

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

NODE *root1, *root2;

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%*c", &e);
if (e != -1)
insert_node(e, root);
} while (e != -1);
}

int kiemtra(NODE *root1, NODE *root2)
{
if (root1 != NULL && root2 != NULL)
if (kiemtra(root1->left, root2->right) &&
kiemtra(root1->right, root2->left))
return 1;
else
return 0;
else
if (root1 == NULL && root2 == NULL)
return 1;
else
return 0;
}

void main()
{
khoi_tao_cay(&root1);
nhap_cay(&root1);
khoi_tao_cay(&root2);
nhap_cay(&root2);
if (kiemtra(root1, root2))
printf("\nHai cay da cho tuong tu cau truc");
else
printf("\nHai cay da cho khac cau truc");
getch();
}

/* Kiem tra xem hai cay co tuong tu ve cau truc nhau khong */
#include <stdio.h>
#include <alloc.h>

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

NODE *root1, *root2;

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%*c", &e);
if (e != -1)
insert_node(e, root);
} while (e != -1);
}

int kiemtra(NODE *root1, NODE *root2)
{
if (root1 != NULL && root2 != NULL)
if (kiemtra(root1->left, root2->left) &&
kiemtra(root1->right, root2->right))
return 1;
else
return 0;
else
if (root1 == NULL && root2 == NULL)
return 1;
else
return 0;
}

void main()
{
khoi_tao_cay(&root1);
nhap_cay(&root1);
khoi_tao_cay(&root2);
nhap_cay(&root2);
if (kiemtra(root1, root2))
printf("\nHai cay da cho tuong tu cau truc");
else
printf("\nHai cay da cho khac cau truc");
getch();
}

/* Thay the chuoi con trong mot chuoi bang mot chuoi con khac */
#include <stdio.h>
#include <string.h>
#include <alloc.h>

char *tim_thay(char *source, char *substr, char *replace)
{
char *found, *temp, *stemp;
int pos = 0;

stemp = strdup(source);
found = strstr(stemp + pos, substr);
while (found)
{
pos = found - stemp + strlen(replace) - strlen(substr) + 1;
temp = (char *) malloc(sizeof(stemp) + strlen(replace) - strlen(substr) + 1);
strncpy(temp, stemp, found - stemp);
temp[found-stemp] = 0;
strcat(temp, replace);
strcat(temp, found + strlen(substr));
free(stemp);
stemp = (char *)malloc(sizeof(temp) + 1);
strcpy(stemp, temp);
free(temp);
found = strstr(stemp + pos, substr);
}
return stemp;
}

void main()
{
char source[255], substr[50], replace[50], *result;

printf("\nNhap chuoi nguon : ");
gets(source);
printf("\nNhap chuoi tim kiem : ");
gets(substr);
printf("\nNhap chuoi thay the : ");
gets(replace);
result = tim_thay(source, substr, replace);
printf("\nKet qua = %s", result);
getch();
}

/* Bai tap 3_94 - Bai toan tron tim */
#include <graphics.h>
#include <stdlib.h>
#include <dos.h>
#include <ctype.h>

#define RADIUS 3
#define DELAY 10

int gr_drive=DETECT, gr_mode;
int xvat, yvat, xnguoi, ynguoi;
int dx, dy, left, right, top, bottom;

void initialize()
{
char s1[] = "Nhan phim bat ky de bat dau";
char s2[] = "Nhan phim ESCAPE de ket thuc";

initgraph(&gr_drive, &gr_mode, "");
setcolor(YELLOW);
rectangle(0, 0, getmaxx(), getmaxy());
outtextxy((getmaxx()-textwidth(s1))/2, 4, s1);
line(0, 16, getmaxx(), 16);
getch();
setcolor(BLACK);
setfillstyle(SOLID_FILL, BLACK);
bar(1, 1, getmaxx(), 15);
setcolor(YELLOW);
outtextxy((getmaxx()-textwidth(s1))/2, 4, s2);
setviewport(1, 17, getmaxx()-1, getmaxy()-1, 1);
left = top = 0;
right = getmaxx() - 2;
bottom = getmaxy() - 18;
randomize();
xvat = random(getmaxx()/2);
xnguoi = random(getmaxx()/2)+getmaxx()/2;
yvat = random(getmaxy()/2);
ynguoi = random(getmaxy()/2)+getmaxy()/2;
}

void drawvat(int color)
{
setcolor(color);
circle(xvat, yvat, RADIUS);
}

void drawnguoi(int color)
{
setcolor(color);
rectangle(xnguoi-3, ynguoi-2, xnguoi+3, ynguoi+2);
}

void tinhvat()
{
if (xnguoi >= xvat)
xvat -= 2;
if (xnguoi < xvat)
xvat += 2;
if (xvat < 2)
xvat += 2;
if (xvat > right-2)
xvat = right-2;
if (ynguoi >= yvat)
yvat -= 2;
if (ynguoi < yvat)
yvat += 2;
if (yvat < 2)
yvat += 2;
if (yvat >bottom - 2)
yvat = bottom - 2;
}

void tinhnguoi()
{
xnguoi += dx;
ynguoi += dy;
if (xnguoi < left)
xnguoi = left;
if (xnguoi > right)
xnguoi = right;
if (ynguoi < top)
ynguoi = top;
if (ynguoi > bottom)
ynguoi = bottom;
}

void main()
{
char c, s[] = "Hoan ho! Ban da chien thang";
initialize();
drawvat(YELLOW);
drawnguoi(WHITE);
dx = dy = 0;
do {
if (kbhit())
{
c = toupper(getch());
if (c == 0)
c = getch();
switch(c)
{
case 'A' : dx = 0; break;
case 'S' : dy = 0; break;
case 75 : dx = -2; break;
case 77 : dx = 2; break;
case 72 : dy = -2; break;
case 80 : dy = 2; break;
}
}
delay(DELAY);
drawvat(BLACK);
drawnguoi(BLACK);
tinhnguoi();
tinhvat();
drawvat(YELLOW);
drawnguoi(WHITE);
if (abs(xnguoi-xvat) < 4 && abs(ynguoi-yvat) < 4)
{
setviewport(0, 0, getmaxx(), getmaxy(), 1);
setcolor(BLACK);
setfillstyle(SOLID_FILL, BLACK);
bar(1, 1, getmaxx(), 15);
setcolor(YELLOW);
outtextxy((getmaxx()-textwidth(s))/2, 4, s);
getch();
c = 27;
}
} while (c != 27);
closegraph();
}

/* Bai tap 3_89 - Tim bao dong chuyen tiep (Transitive Closure) 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;
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;
int ypos = 10;

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

push(nutxet);
setcolor(YELLOW); itoa(nutxet, s, 10); outtextxy(xpos++*20, 38+ypos, 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);
xpos = 1;
ypos += 10;
}

void DFS()
{
unsigned size, i, n;
void far *buf;
char s[] = "Nhan phim bat ky de tiep tuc";

hide_mouse();
size = imagesize(1, 36, 150, 300);
buf = malloc(size);
getimage(1, 36, 150, 300, buf);
/* Bat dau giai thuat */
for (n=0; n<sonut; n++)
{
top = -1;
for (i=0; i<sonut; i++)
visited = 0;
visit(n);
}
out(s);
getch();
setcolor(BLACK);
setfillstyle(SOLID_FILL, BLACK);
bar(1, 36, getmaxx()-1, 46);
/* Ket thuc giai thuat */
putimage(1, 36, buf, COPY_PUT);
free(buf);
show_mouse();
}