Bài tập C cấu trúc dữ liệu - SOXH.C

Một số bài tập thời còn đi học, dọn ổ backup lên blog :>>

----------------
#include <stdio.h>
#include <string.h>

void main()
{
  char source[250], substr[250], *found;
  int count = 0;

  printf("\nNhap chuoi nguon : ");
  gets(source);
  printf("\nNhap chuoi tim kiem : ");
  gets(substr);
  found = source;
  while ((found = strstr(found, substr)) != NULL)
  {
    count++;
    found++;
  }
  printf("\nSo lan xuat hien = %d", count);
  getch();
}
----------------

Bài tập C cấu trúc dữ liệu - RUN.C

Một số bài tập thời còn đi học, dọn ổ backup lên blog :>>

----------------
/* Bai tap 3_17 - Rut cac run tu nhien tu mot danh sach lien ket */
#include <conio.h>
#include <stdio.h>
#include <alloc.h>
#include <stdlib.h>

#define MAX 25

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

SL *first;

typedef struct tagds {
  SL *s;
  struct tagds *next;
} SL2;

SL2 *firstSL;

void tachrun()
{
  SL *a, *b;
  SL2 *fa, *fb;

  if (first != NULL)
  {
    a = first;
    do {
      fa = (SL2 *)malloc(sizeof(SL2));
      fa->next = NULL;
      fa->s    = a;
      b = a->next;
      while (b != NULL)
      {
        if (b->key < a->key)
          break;
        a = b;
        b = b->next;
      }
      a->next = NULL;
      a = b;
      if (firstSL == NULL)
      {
        firstSL = fa;
        fb = fa;
      }
      else
      {
        fb->next = fa;
        fb = fa;
      }
    } while (b != NULL);
  }
}

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

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

void initialize()
{
  int i;
  randomize();
  first = NULL;
  for (i=0; i<MAX; i++)
    insert(random(100));
  firstSL = NULL;
}

void release(SL *s)
{
  if (s->next != NULL)
    release(s->next);
  free(s);
}

void cleanup()
{
  release(first);
}

void in_ds(SL *first)
{
  SL *s;
  printf("\n");
  s = first;
  while (s != NULL)
  {
    printf("%3d", s->key);
    s = s->next;
  }
}

void inds(SL2 *f)
{
  in_ds(f->s);
}

void inrun()
{
  SL2 *f;
  if (firstSL != NULL)
  {
    f = firstSL;
    while (f != NULL)
    {
      inds(f);
      f = f->next;
    }
  }
}

void main()
{
  initialize();
  in_ds(first);
  tachrun();
  inrun();
  getch();
  cleanup();
}
----------------

Bài tập C cấu trúc dữ liệu - QSORT.C

Một số bài tập thời còn đi học, dọn ổ backup lên blog :>>

----------------
#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[i]);
}

void sort(int l, int r)
{
  int i, j, x, w;
  i = l;
  j = r;
  x = mang[(l+r)/2];
  do {
    while (mang[i] < x)
      i++;
    while (x < mang[j])
      j--;
    if (i <= j)
    {
      w = mang[i];
      mang[i] = mang[j];
      mang[j] = w;
      i++;
      j--;
    }
  } while (i<=j);
  if (l < j)
    sort(l, j);
  if (i < r)
    sort(i, r);
}

void quicksort()
{
  sort(0, MAX-1);
}

void main()
{
  int i;

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

Bài tập C cấu trúc dữ liệu - PLOST.C

Một số bài tập thời còn đi học, dọn ổ backup lên blog :>>

----------------
#include <stdio.h>

typedef struct node *node_ptr;
typedef int element_type;

struct node {
  element_type element;
  node_ptr next;
};

void initialize(node_ptr *list)
{
  *list = NULL;
}

node_ptr insert_before(element_type e, node_ptr *list)
{
  node_ptr p;
  p = (node_ptr)malloc(sizeof(struct node));
  p->element = e;
  p->next = *list;
  return p;
}

node_ptr insert_after(element_type e, node_ptr *list)
{
  node_ptr p, tmp_cell;
  if (*list == NULL)
    return (*list = insert_before(e, *list));
  else
  {
     tmp_cell = *list;
     while (tmp_cell->next)
       tmp_cell = tmp_cell->next;
     p = (node_ptr)malloc(sizeof(struct node));
     p->element = e;
     p->next = *list;
     p->next = NULL;
     tmp_cell->next = p;
     return p;
  }
}

void main()
{
   element_type e;
   node_ptr L, P, xp, xl;
   int i, n, k;

   initialize(&L);
   initialize(&P);
   printf("\nNhap vao cac phan tu cua danh sach (-1 de ket thuc) : ");
   do {
     scanf("%d", &e);
     if (e != -1)
       insert_after(e, &L);
   } while (e != -1);
   printf("\nNhap vao cac gia tri chi thu tu can lay trong danh sach L (-1 de ket thuc) : ");
   do {
     scanf("%d", &e);
     if (e != -1)
       insert_after(e, &P);
   } while (e != -1);
   n = 1;
   xl = L;
   xp = P;
   do {
     k = xp->element;
     for (i=0; i<k-n; i++)
       if (xl)
         xl = xl->next;
     if (xl)
       printf("\nPhan tu thu %d = %d", k, xl->element);
     xp = xp->next;
     n = k;
   } while ((xp != NULL) && (xl != NULL));
  getch();
}
----------------

Bài tập C cấu trúc dữ liệu - NUTLA.C

Một số bài tập thời còn đi học, dọn ổ backup lên blog :>>

----------------
#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;
}

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

Bài tập C cấu trúc dữ liệu - NUTCUOIS.C

Một số bài tập thời còn đi học, dọn ổ backup lên blog :>>

----------------
#include <stdio.h>

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

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

struct node *nutcuoi(struct node *first)
{
  struct node *tmp;
  tmp = first;
  while (tmp != NULL && tmp->next != NULL)
    tmp = tmp->next;
  return tmp;
}

void main()
{
  element_type e;
  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 = nutcuoi(first);
  if (tmp)
    printf("Nut cuoi co gia tri = %d", tmp->element);
  getch();

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

Bài tập C cấu trúc dữ liệu - NOIDS.C

Một số bài tập thời còn đi học, dọn ổ backup lên blog :>>

----------------
#include <stdio.h>

typedef int element_type;
struct node {
  element_type element;
  struct node *next;
} *first1 = NULL, *first2 = NULL, *first3 = NULL;

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

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

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

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

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

void noids(struct node *first1, struct node *first2, struct node **first3)
{
  struct node *tmp, *tmp1, *tmp2;

  tmp1 = first1;
  tmp2 = first2;
  if (first2 == NULL)
  {
    *first3 = first1;
    tmp = *first3;
    while (first1 != NULL)
    {
      first1 = first1->next;
      tmp->next = first1;
      tmp = tmp->next;
    }
  }
  else if (first1 == NULL)
  {
    *first3 = first1;
    tmp = *first3;
    while (first1 != NULL)
    {
      first1 = first1->next;
      tmp->next = first1;
      tmp = tmp->next;
    }
  }
  else
  {
    if (first1->element < first2->element)
    {
      *first3 = first1;
      tmp1 = first1->next;
    }
    else
    {
      *first3 = first2;
      tmp2 = first2->next;
    }
    tmp = *first3;
    while (tmp1 != NULL && tmp2 != NULL)
    {
      if (tmp1->element < tmp2->element)
      {
        tmp->next = tmp1->element;
        tmp1 = tmp1->next;
      }
      else
      {
        tmp->next = tmp2->element;
        tmp2 = tmp2->next;
      }
    }
    if (tmp1 == NULL)
    {

    }
    else
    {
    }
  }
}

void main()
{
  element_type e;

  printf("\nNhap cac gia tri tang dan cho danh sach 1 (-1 de ket thuc) : ");
  do {
    scanf("%d", &e);
    if (e != -1)
      insert(e, &first1);
  } while (e != -1);
  printf("\nNhap cac gia tri tang dan cho danh sach 2 (-1 de ket thuc) : ");
  do {
    scanf("%d", &e);
    if (e != -1)
      insert(e, &first2);
  } while (e != -1);
  printf("\nTruoc khi noi DS 1 co : ");
  print_list(first1);
  printf("\nTruoc khi noi DS 2 co : ");
  print_list(first2);
  noids(first1, first2, &first3);
  printf("\nSau khi noi DS 3 co : ");
  print_list(first3);

  xoads(&first1);
  xoads(&first2);
}
----------------

Bài tập C cấu trúc dữ liệu - MTKE.C

Một số bài tập thời còn đi học, dọn ổ backup lên blog :>>

----------------
/* Bai tap 3_76 - Cai dat cau truc do thi bang ma tran ke */
#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 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";
  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);
  show_mouse();
}

int index(int x, int y, int heso)
{
  int i, OK = 0;
  for (i=0; i<sonut; i++)
    if (abs(nut[i].x - x) < 4*heso && abs(nut[i].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[i] = c;
      s1[i+1] = 0;
      i++;
    }
    if (c == 8 && i>0)
    {
      i--;
      s1[i] = 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[i].x - xmouse) < 4 && abs(nut[i].y - ymouse) < 4)
    {
      start = i;
      oldx = x = nut[i].x;
      oldy = y = nut[i].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[i].x - xmouse) < 4 && abs(nut[i].y - ymouse) < 4)
    {
      end = i;
      OK = 1;
      break;
    }
  if (OK && end != start)
  {
    setcolor(GREEN);
    if ((i = input_weight(start, end)) != -1)
    {
      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());
      if (c == 'Q')
        done = 1;
    }
    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();
}
----------------

Bài tập C cấu trúc dữ liệu - MOUSE.INC

Một số bài tập thời còn đi học, dọn ổ backup lên blog :>>

----------------
#define MV_LBUTTON 1
#define MV_RBUTTON 2
#define MV_BBUTTON 3

int NUMBER_BUTTONS = 2;
int MOUSE_SIZE = 16;

unsigned char MOUSE_THERE;
unsigned char MOUSE_VISIBLE;

unsigned char LBUTTON_DOWN,
              RBUTTON_DOWN,
              BBUTTON_DOWN,
              LBUTTON_UP,
              RBUTTON_UP,
              BBUTTON_UP,
              CURSOR_MOVED;

int CMX = 0,
    CMY = 0;
int BSTATE = 0;

union REGS mregs;
struct SREGS msegregs;

unsigned char EGA_REG_READ = 1;
unsigned char lbutton, rbutton;
int xmouse, ymouse;

void reset_mouse()
{
  MOUSE_THERE = 0;
  MOUSE_SIZE = 16;
  MOUSE_VISIBLE = 0;
  if (getvect(0x33) != 0L)
  {
    mregs.x.ax = 0;
    int86(0x33, &mregs, &mregs);
    if (mregs.x.ax != 0)
    {
      MOUSE_THERE = 1;
      NUMBER_BUTTONS = mregs.x.bx;
      LBUTTON_DOWN = 0;
      RBUTTON_DOWN = 0;
      BBUTTON_DOWN = 0;
    }
  }
}

void show_mouse()
{
  if (MOUSE_THERE)
  {
    mregs.x.ax = 1;
    int86(0x33, &mregs, &mregs);
    MOUSE_VISIBLE = 1;
  }
}

void hide_mouse()
{
  if (MOUSE_THERE && MOUSE_VISIBLE)
  {
    mregs.x.ax = 2;
    int86(0x33, &mregs, &mregs);
    MOUSE_VISIBLE = 0;
  }
}

void get_mouse_button(unsigned char *lbutton, unsigned char *rbutton, int *x, int *y)
{
  if (MOUSE_THERE)
  {
    mregs.x.ax = 3;
    int86(0x33, &mregs, &mregs);
    *lbutton = (mregs.x.bx == 1) ? 1 : 0;
    *rbutton = (mregs.x.bx == 2) ? 1 : 0;
    if (mregs.x.bx == 3)
      *rbutton = *lbutton = 1;
    *x = mregs.x.cx;
    *y = mregs.x.dx;
  }
}

unsigned char get_button_rls_info(int butt_no, int *count, int *x, int *y)
{
  if (MOUSE_THERE)
  {
      mregs.x.ax = 6;
      mregs.x.bx = butt_no;
      int86(0x33, &mregs, &mregs);
      *count = mregs.x.bx;
      *x = mregs.x.cx;
      *y = mregs.x.dx;
    if (butt_no == 0)
      return (!(mregs.x.ax & 1));
    else
      return (!((mregs.x.ax & 2) >> 1));
  }
  return 0;
}

void set_event_handler(int call_mask, void (far *location)(void))
{
  if (MOUSE_THERE)
  {
      mregs.x.ax = 12;
      mregs.x.cx = call_mask;
      mregs.x.dx = FP_OFF(location);
      msegregs.es = FP_SEG(location);
      int86(0x33, &mregs, &mregs);
  }
}

void set_hide_bound(int x1, int y1, int x2, int y2)
{
  if (MOUSE_THERE)
  {
      mregs.x.ax = 16;
      mregs.x.cx = x1;
      mregs.x.dx = y1;
      mregs.x.si = x2;
      mregs.x.di = y2;
      int86(0x33, &mregs, &mregs);
  }
}

void set_mouse_position(int x,int y)
{
  if (MOUSE_THERE)
  {
      mregs.x.ax = 4;
      mregs.x.cx = x;
      mregs.x.dx = y;
      int86(0x33, &mregs, &mregs);
  }
}

void set_mouse_hlimits(int x1,int x2)
{
  if (MOUSE_THERE)
  {
      mregs.x.ax = 7;
      mregs.x.cx = x1;
      mregs.x.dx = x2;
      int86(0x33, &mregs, &mregs);
  }
}

void set_mouse_vlimits(int y1,int y2)
{
  if (MOUSE_THERE)
  {
      mregs.x.ax = 8;
      mregs.x.cx = y1;
      mregs.x.dx = y2;
      int86(0x33, &mregs, &mregs);
  }
}

void far event_handler(void);

void near event_processor(int event_status, int button_status, int x, int y)
{
  if ((CMX != x) || (CMY != y))
  {
    CURSOR_MOVED = 1;
    CMX = x;
    CMY = y;
  }

  BSTATE = button_status;

  if (event_status & 2)
    LBUTTON_DOWN = 1;
  if (event_status & 8)
    RBUTTON_DOWN = 1;
  if (((event_status & 2) || (event_status & 8)) && (button_status == 3))
    BBUTTON_DOWN = 1;
  if ((NUMBER_BUTTONS == 3) && (event_status & 32))
    BBUTTON_DOWN = 1;
  if (event_status & 4)
    LBUTTON_UP = 1;
  if (event_status & 16)
    RBUTTON_UP = 1;
  if (LBUTTON_UP & RBUTTON_UP)
    BBUTTON_UP = 1;
  if ((NUMBER_BUTTONS == 3) && (event_status & 64))
    BBUTTON_UP = 1;
}

void reset_event_handler(void)
{
  CURSOR_MOVED = 0;
  LBUTTON_DOWN = LBUTTON_UP = 0;
  RBUTTON_DOWN = RBUTTON_UP = 0;
  BBUTTON_DOWN = BBUTTON_UP = 0;
}

void install_event_handler(void)
{
  if (NUMBER_BUTTONS == 3)
    set_event_handler(127, event_handler);
  else
    set_event_handler(31, event_handler);
}
----------------

Bài tập C cấu trúc dữ liệu - MINSTREE.C

Một số bài tập thời còn đi học, dọn ổ backup lên blog :>>

----------------
/* Bai tap 3_77 - Tim cay bao trum toi tieu MST - Minimal Spanning Tree */
#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 MST();

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 MST";
  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[i][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[i].x - x) < 4*heso && abs(nut[i].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[i] = c;
      s1[i+1] = 0;
      i++;
    }
    if (c == 8 && i>0)
    {
      i--;
      s1[i] = 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[i].x - xmouse) < 4 && abs(nut[i].y - ymouse) < 4)
    {
      start = i;
      oldx = x = nut[i].x;
      oldy = y = nut[i].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[i].x - xmouse) < 4 && abs(nut[i].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' : MST(); 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();
}

int visited[MAX];

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

void MST()
{
  int size, i, j, min, vert1 = 0, vert2, numnut = 0;
  void far *buf;
  char s[] = "Nhan phim bat ky de ket thuc";
  hide_mouse();
  size = imagesize(1, 36, getmaxx()-1, 46);
  buf = malloc(size);
  getimage(1, 36, getmaxx()-1, 46, buf);
/* Bat dau giai thuat */
  for (i=0; i<sonut; i++)
    visited[i] = 0;
/* Bat dau tu dinh 0 */
  setcolor(RED);
  do {
    min = 100;
    visited[vert1] = 1; /* Danh dau no*/
    numnut++;
/* Tim canh nho nhat di qua 1 dinh da tham
   va 1 dinh chua tham */
    for (i=0; i<sonut; i++)
      for (j=0; j<sonut; j++)
        if (visited[i]==1 && weight[i][j] < min && weight[i][j]>-1 && visited[j]==0)
        {
          min = weight[i][j];
          vert2 = i;
          vert1 = j;
        }
    if (min < 100)
      line(nut[vert1].x, nut[vert1].y, nut[vert2].x, nut[vert2].y);
    delay(2000);
  } while (numnut < sonut);
/* Ket thuc giai thuat */
  show_mouse();
  out(s);
  getch();
  putimage(1, 36, buf, COPY_PUT);
  free(buf);
}

----------------