Bài 9-Cài đặt cây tổng quát

#include <string.h> 

#include <string.h> 

#include <stdio.h>

#include <ctype.h>  

#include <conio.h>

#include <stdlib.h>

#define  MAX 5

typedef struct NODE{

               int  key ;

               char ht[30];// ho ten

               NODE *C[MAX+1]; // mang con tro 1..5 ( m+1) loai bo c0;

};

void menu();

void MakeNull(NODE **T);

NODE *TimCha(int x,NODE **T);

void DuyetTruoc(NODE *T);

void   Chen(int key,char ht[30],NODE **T);

 

void main()

{  NODE *T; // goc cay

   char ch;             int key; char ht[30];

   MakeNull(&T);

   do { clrscr();

               menu();

               ch=getch(); ch= toupper(ch);

               switch (ch)

               {

                case '1': printf("\nNhap gia tri KEY cua nut can chen:");

                                 scanf("%d",&key);

                                 printf("\tHo va ten :");fflush(stdin);

                                 gets(ht);

                                 Chen(key,ht,&T);

                                 break;

                case '2': DuyetTruoc(T);   getch();break;

               }

   }while(ch!=27);

}

 

void menu()

{

               printf("\n\t\t1.Them ");

               printf("\n\t\t2.Duyet");

               printf("\n\t\tESC. Thoat :");

               printf("\n\t\t  Chon cong viec:");

}

 

void MakeNull(NODE **T)

{

               *T = NULL;

}

 

NODE *TimCha(int x,NODE **T)

{

               NODE *q, *r, *h[100];// h: la hang doi | h: truoc...cuoi|

               int          truoc,cuoi,dem;

               truoc=cuoi=dem=1;

               /* truoc :dau hang doi

               cuoi        :cuoi hang doi

               dem        : dem so phan tu cua hang doi h */

               h[1]=(*T); // chi den goc cua cay

               while(dem >0)

               {  q  = h[truoc];// lay ra o dau hang doi

                  if (q!=NULL)

                                if (q->key==x) return q;

                                for(int i=1; i<=MAX; i++)

                                { r = q->C[i];//cac con cua nut q

                                if(r!=NULL)

                                              if(r->key==x) return r;

                              cuoi++;

                              h[cuoi]=r;

                              dem++;

                                }

               h[truoc]=NULL; // Loai bo phan tu o dau hang doi

               truoc++;      // chuyen den phan tu tiep theo tinh tu dau cua hang doi

               dem--;         // Giam so phan tu cua hang doi

               }

               return NULL;

}

 

void DuyetTruoc(NODE *T)

{

  if( T!=NULL)

               {

               printf("\n%5d.%s",T->key,T->ht);

               for(int i=1; i<=5; i++)

                              DuyetTruoc( T->C[i]);

               }

}

 

void   Chen(int key,char ht[30],NODE **T)

{

   NODE *q,*p; // con tro q la nut moi, p la con tro

   int khoacha, conthu;

   // Tao nut moi

               q= new NODE;

               q->key= key;

               strcpy(q->ht,ht);

               // Khoi tao cac con cua nut q la rong

               for( int i=1;i<=MAX;i++) q->C[i]=NULL;

               if((*T)==NULL){

                                             (*T)=q; return ;

                                    }

               else {

                      printf("\n\tNhap khoa nut cha:");

                      scanf("%d",&khoacha);

                      printf("\n\tDay la con thu may:");

                      scanf("%d",&conthu);

                      p=TimCha(khoacha,T);

                              /*Tim nut cha cua nut can them vao,

                              x la khoa cua nut can them vao,

                              p tro den nut cha cua nut co khoa la x moi nay*/

                      if(p==NULL) {

                                             printf("\n\tKhong tim thay nut cha cua nut nay");

                                             free (q);

                                             return ;

                                             }

                      else   printf("\n\tDa thay nut cha va chen xong roi!!!\n");

               p->C[conthu]=q;  // con thu cua nut cha

               }

}

Tham khảo: Bùi Thế Tâm, C/C++

Bình luận

Bài viết khác

Bài 16- Thuật toán Ford -Fulkerson

Thuật toán Ford - Fulkerson  Việc chứng minh định lý luồng cực đại - lát cắt cực tiểu cho ta một thuật toán tìm luồng cực đại (thuật toán Ford- Fulkerson)

Bài 15-Cài đặt thuật toán Dijkstra

Năm 1959, Edsger W. Dijkstra đưa ra một thuật toán rất hiệu quả để giải bài toán đường đi ngắn nhất. Thuật toán thực hiện việc gán và giảm giá trị của nhãn tại mỗi đỉnh của đồ thị.

Bài 14-Thuật toán Prim

Thuật toán Prim do Robert Prim đưa ra vào năm 1957, ý tưởng chính của nó là lần lượt ghép vào cây khung các cạnh có trọng số tối thiểu liên thuộc với một đỉnh của cây mà không tạo ra chu trình trong cây. Thuật toán sẽ dừng khi có được n - 1 cạnh vào cây. Dưới đây là mô tả các bước của thuật toán Prim.

Bài 13-Cài đặt thuật toán Kruskal tìm cây khung tối thiểu

File dữ liệu về đồ thị dạng text;

ĐỐI TÁC CỦA CHÚNG TÔI