anh chị ơi..ở ngoài đó ôn cấu trúc dữ liệu như thế nào? có thể chỉ cho em hướng đi với được không?
em cứ tự mò mẫm.. rồi tập cài đặt các thuật toán anh chị xem giúp em nhé
ah... có tài liệu ôn thi nào. ,, các đề năm ngoái về cấu trúc dữ liệu anh chị cho em với.
Đây là bài của em.. Lần đầu tham gia. có gì anh chị góp ý nhé.
≡≡≡≡≡- cai dat thuat toan tim duong di ngan nhat-≡
#include
#include

#define TOIDA 50
#define VOCUNG 30000
#define TRUE 1
#define FALSE 0

/* Khai bao ma tran trong so cua do thi
weight[i][j] = VOCUNG: neu tren do thi khong co cung
weight[i][j] != 0 : tren do thi co cung */
int weight[TOIDA][TOIDA];

int SoNut; // so nut thuc su co tren do thi

// Khoi dong ma tran trong so cua do thi
void initialize()
{
int i, j;
for(i = 0; i < TOIDA; i++)
for(j = 0; j < TOIDA; j++)
weight[i][j] = VOCUNG;
}

// Tac vu joinwt: them mot cung moi tu node1 den node2 co trong so wt
void joinwt(int node1, int node2, int wt)
{
weight[node1][node2] = wt;
}

// Tac vu remvwt: xoa mot cung tu node1 den node2
void remvwt(int node1, int node2)
{
weight[node1][node2] = VOCUNG;
}

/* Tac vu dijkstra: tim duong di ngan nhat tren do thi co trong so theo
giai thuat Dijkstra.
Du lieu nhap:
s: nut di, t: nut den
Du lieu xuat:
ngan1: chieu dai duong di ngan nhat tu s den t
duongdi[]: mang ghi nhan lo trinh ngan nhat tu s den t, luu y
duongdi[i] la nut truoc nut i tren lo trinh ngan nhat */
void dijkstra(int s, int t, int *ngan1, int duongdi[])
{
int i, k, kc, nuthientai, min, kcachmoi;
int tapcacnut[TOIDA]; // tap cac nut da xet
int kcach[TOIDA]; /* mang luu chieu dai duong di ngan nhat tu nut
s den cac nut khac */

// Buoc 0: khoi dong mang tapcacnut[] va kcach[]
for(i = 0; i < SoNut; i++)
{
tapcacnut[i] = FALSE;
kcach[i] = VOCUNG;
}

// dua nut s vao tap nut da xet
tapcacnut[s] = TRUE;
kcach[s] = 0;
nuthientai = s;

/* vong lap thuc hien cac buoc 1, 2, ... cho den khi dua duoc nut t vao
tap nut da xet */
while(nuthientai != t)
{
min = VOCUNG;
kc = kcach[nuthientai]; /* kc chieu dai duong di ngan nhat tu nut s
den nuthientai */
for(i = 0; i < SoNut; i++)
if(tapcacnut[i] == FALSE)
{
kcachmoi = kc + weight[nuthientai][i];
if(kcachmoi < kcach[i])
{
kcach[i] = kcachmoi;
duongdi[i] = nuthientai; /* gan nuthientai la nut truoc
nut i tren lo trinh */
}
if(kcach[i] < min)
{
min = kcach[i];
k = i;
}
}
// Dua nut k vao tap nut da xet
nuthientai = k;
tapcacnut[nuthientai] = TRUE;
}
*ngan1 = kcach[t];
}

// Chuong trinh chinh
void main()
{
int chon, x, y, i, j;
char c;
int wt, ngan1;
int duongdi[TOIDA];
int s, t;
clrscr();

initialize();
SoNut = 0;

do
{
printf("\n\n\tCHUONG TRINH TIM DUONG DI NGAN NHAT - GIAI THUAT DIJKSTRA");
printf("\n\nCac chuc nang cua chuong trinh:\n");
printf("\n1: Tao do thi moi");
printf("\n2: Them mot nut");
printf("\n3: Them mot cung");
printf("\n4: Xoa mot cung");
printf("\n5: Xoa toan bo do thi");
printf("\n6: Xac dinh so nut co tren do thi");
printf("\n7: Duyet cac cung");
printf("\n8: Tim cung");
printf("\n9: Tim duong di ngan nhat");
printf("\n0: Thoat");
printf("\nChon chuc nang: ");
scanf("%d", &chon);
switch(chon)
{
case 1:
{
initialize();
printf("\nDo thi moi co bao nhieu nut: ");
scanf("%d", &SoNut);
printf("\Hay nhap cac cung cua do thi (nhap %d %d de ket thuc):\n",
SoNut, SoNut);
x = 0;
y = 0;
while(x < SoNut && y < SoNut)
{
printf(" Nhap cung: ");
scanf("%d %d", &x, &y);
if(x < SoNut && y < SoNut)
{
printf(" Trong so cua cung %d %d: ", x, y);
scanf("%d", &wt);
weight[x][y] = wt;
}
};
break;
}
case 2:
{
if(SoNut < TOIDA)
{
SoNut++;
printf("So nut hien co la %d", SoNut);
}
else
printf("Khong the them nut moi");
break;
}
case 3:
{
printf("\nNhap cung can them: ");
scanf("%d %d", &x, &y);
if(x >= SoNut || y >= SoNut)
printf("Khong hop le");
else
{
printf("Trong so cua cung %d -> %d : ", x, y);
scanf("%d", &wt);
joinwt(x, y, wt);
}
break;
}
case 4:
{
printf("\nNhap cung can xoa: ");
scanf("%d %d", &x, &y);
remvwt(x, y);
break;
}
case 5:
{
printf("\nBan co chac khong (c/k): ");
c = getche();
if(c == 'c' || c == 'C')
{
initialize();
SoNut = 0;
}
break;
}
case 6:
{
printf("\nSo nut co tren do thi la %d", SoNut);
break;
}
case 7:
{
printf("\nCac cung co tren do thi:\n");
for(i = 0; i < SoNut; i++)
for(j = 0; j < SoNut; j++)
if(weight[i][j] < VOCUNG)
printf(" %d%s%d : %d\n", i, " -> ", j, weight[i][j]);
break;
}
case 8:
{
printf("\nNhap cung can tim: ");
scanf("%d %d", &x, &y);
if(x >= SoNut || y >= SoNut)
printf("Khong hop le");
else
if(weight[x][y] < VOCUNG)
printf("Co cung voi trong so %d", weight[x][y]);
else
printf("Khong co cung nay");
break;
}
case 9:
{
printf("\nNhap nut di: ");
scanf("%d", &s);
printf("\nNhap nut den: ");
scanf("%d", &t);
dijkstra(s, t, &ngan1, duongdi);
printf("\nDuong di ngan nhat tu %d->%d la: %d ", s, t, ngan1);
printf("\nLo trinh: ");
i = t;
while(i != s)
{
printf("%d <- ", i);
i = duongdi[i];
}
printf("%d", s);
break;
}
}
} while(chon !=