Lập Trình C - kiến thức và bài tập ví dụ về FILE


- Trong ngôn ngữ C , một tập tin là một khái niệm logic, được áp dụng không những đối với các tập tin trên đĩa mà cả với các terminal ( bàn phím, màn hình, máy in...).
- File có 2 loại : 

Text file ( file văn bản ).
+ Binary ( nhị phân : dbf, doc, bitmap,...).
- File văn bản chỉ khác binary khi xử lý ký tự chuyển dòng (LF) ( mã 10 ) được chuyển thành 2 ký tự CR (mã 13) và LF ( mã 10) và khi đọc 2 ký tự liên tiếp CR và LF trên file cho ta một ký tự LF.
- Các thao tác trên file thực hiện thông qua con trỏ kiểu FILE. Mỗi biến FILE có 1 con trỏ lúc đầu sẽ trỏ vào phần tử đầu tiên của file. Sau mỗi thao tác đọc hay ghi dữ liệu con trỏ tự động dời xuống mẫu tin kế tiếp. Làm việc trên kiểu File thường có 3 công đoạn : mở file, nhập xuất thông trên file và đóng file.
* Một số hàm thông dụng thao tác trên file ( tập tin/tệp tin ) :
+ Mở file : FILE *fopen ( char *filename, char *mode);
. Nếu có lỗi fp sẽ trỏ đến NULL.
+ Các mode chế độ mở file :
" r" " rt " / " rb " : mở file để đọc theo kiểu văn bản / nhị phân - file phải tồn tại trước nếu không sẽ có lỗi.
"w" "wt" / " wb " : mở ( tạo ) file mới để ghi theo kiểu văn bản/nhị phân - nếu file đã có nó sẽ bị xóa(ghi đè )( luôn luôn tạo mới ).
"a" "at"/ "ab" : mở file để ghi bổ sung (append) thêm theo kiểu văn bản hoặc nhị phân( chưa có thì tạo mới ).
+ Ðóng file : int fclose ( file + biến file ) ;
Ví dụ : Void main ( )
 { FILE *fp ;
    fp = fopen ("c:\\THUCTAP\\Data.txt", "wt" );
     if (fp = NULL )
        printf ( " không mở được file c/Thuctap\data.txt");
     else {< xử lý file > }
     fclose (fp) ; /* đóng file */
}
+ Làm đóng tất cả các tập đang mở : int fclose all(void) ; nếu thành công trả về số nguyên bằng tổng số các file đóng được, ngược lại trả về EOF.
+ Hàm xóa tập : remove (const + char*ten tập ) ; nếu thành công cho giá trị 0, ngược lại EOF.
+ Hàm kiểm tra cuối tập : int feof(FILE*fp) : !=0 : nếu cuối tập= 0 : chưa cuối tập.
+ Hàm int putc ( int ch, FILE*fp);
Hàm int fputc( int ch, FILE*fp);
Công dụng của hai hàm này :ghi một ký tự lên tập fp theo khuôn dạng được xác định trong chuỗi điều khiển dk. Chuỗi dk và danh sách đối tương tự hàm printf( ).
+ Hàm int fscanf ( FILE *fp, const char *dk, ...);
Công dụng : đọc dữ liệu từ tập tin fp theo khuôn dạng ( đặc tả) làm việc giống scanf( ).


*Ví dụ : giả sử có file c/data.txt lưu 10 số nguyên 1 5 7 9 8 0 4 3 15 20 . Hãy đọc các số nguyên thêm vào một mãng sau đó sắp xếp tăng dần rồi ghi vào file datasx.txt
Giải :
#include <stdio.h>
#include<conio.h>
#include<stdlib.h>
#define n 10
void main ( )
   { FILE *fp ; int i, j, t, a[n]
      clrscr ( ) ;
     fp = fopen (" c :\\data.txt ", "rt" ); /* mở file để đọc vào mãng */
     if (fp = NULL)
        { printf ("không mở được file ");
          exit (1);
        }
/* Sắp xếp mãng */
      for ( i=0 ; i<n-1 ; i++)
      for (j=i+1; j<n ; j++)
          if (a[i]<a[j] )
              { t = a[i] ; a[i]=a[j] ; a[j] = t ; }
      fclose (fp);
/* mở file datasx.txt để ghi sau khi sắp xếp */
     fp = fopen ("c:\\datasx.txt ", "wt");
     for ( i=0 ; i<n;i++)
     printf (fp,"%2d", a[i] );
      fclose (fp);
/* đọc dữ liệu từ file cách 2 ( tổng quát hơn ) không phụ thuộc vào n */
    i = 0 ;
while (1)
{ fscanf (fp,"%d",&a[i] ;
   i++;
   if (foef(fp) ) break ;
}
- Hàm int fputs ( const char *s, file *fp );
Công dụng : ghi chuỗi s lên tập tin fp ( dấu "\0" ghi lên tập) nếu có lỗi hàm cho eof.
- Hàm char fgets ( char *s, int n , FILE *fp);
Công dụng : đọc 1 chuỗi ký tự từ tập tin fp chứa vào vùng nhớ s. Việc đọc kết thúc khi : hoặc đã đọc n-1 ký tự hoặc gặp dấu xuống DÒNG( CẮPMÃ 13 10). KHI ÐÓ MÃ 10 ÐƯỢC ÐƯA VÀO CHUỖI KẾT QUẢ.
 CáC HàM ÐọC GHI FILE KIểU CấU TRúC

- Hàm int fwrite (void *p, int size , int n , FILE*fp);
Ðối : p : là con trỏ trỏ tới vùng nhớ chứa dữ liệu cần ghi.
size : là kích thước của mẫu tin theo byte.
n số mẫu tin cần ghi.
fp là con trỏ tập.
- Ví dụ : fwrite(&tam) size of(tam),1,fv); /* tam là 1 mẫu tin(record) nào đó*/
Công dụng : ghi một mẫu tin (record) kích thước sizebyte ( size of (tam)) từ vùng nhớ p(&tam) lên tập fp. Hàm sẽ trả về một giá trị = số mẫu tin thực sự ghi được.


+ Hàm int fread (void*p), int size , int n, FILE *fp);
Ðối : p : là con trỏ trỏ tới vùng nhớ chứa dữ liệu đọc được.
size là kích thước của mẫu tin theo byte
n : là số mẫu tin cần đọc, fp là con trỏ tập tin.
Ví dụ : fread (&tam, size of(KIEUHS) , 1, 4 )>0)
Công dụng : đọc n(1) mẫu tin kích thước sizebyte (size of(tam)) từ tập tin fp chứa vào vùng nhớ p(&tam). Hàm trả về một giá trị bằng số mẫu tin thực sự đọc được.
* Ví dụ áp dụng : Nhập vào danh sách lớp gồm n học viên ("nhập vào). Thông tin về mỗi học viên gồm Họ tên, phái , điểm, kết quả. Xét kết quả theo điều kiện sau : nếu Ðiểm>= 5 ( đậu ), điểm <5 : rớt. Sau đó sắp xếp theo điểm và ghi vào tập tin c:\lop.txt. Ðọc lại tập tin c:\lop.txt và xét lại kết quả nếu điểm =4 và phái là nữ sẽ đậu và chép sang tập tin c:\ketqua.txt.
Giải : 

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
typedef struct
{ char ten[20] ; char phai[4] ; int diem ; char kq[4] ; } KieuHV;
KieuHV *lop ,*p, tam;
/* Hàm nhập danh sách n học viên */
void nhapds ( int n, KieuHV lop[ ] )
{ int i , diem ; p = lop ;
for ( i=0; i<n ; i++ )
{ printf (" nhập họ và tên người thứ %d : " , i + 1) ; gets ( pă ten);
printf ("phái (nam/nữ ) : ") ; gets (pă phai );
printf ("nhập điểm = ") ; scanf ("%d%c*c", &diem); pă diem=diem;
if (diem>5)strcpy (p--> kq,"Ðậu");
else strcpy (pă kq, "rớt " ) ; p++;
}
/* Hàm sắp xếp */
void sapxep ( int n , KieuHV lop[ ] )
{ int i , j ;
for ( i=0 ; i<n-1; i++)
for ( j=i+1 ; j<0; j++)
if (lop[i].diem< lop[j]diem )
{ tam = lop[i] ; lop[i] = lop[j] ; lop [i] = tam ;}
}
/* Hàm in danh sách */
void inds ( int n, KieuHS lop[ ] )
{ int i ;
for ( i=0 ; i<n ; i++)
printf ("\n %20s %5s%5d%5s, lop[i].ten, lop[i].phai, lop[i].diem, LOP[I].KQ );
/* CHƯƠNG TRìNH CHíNH */

void main ( )
{ int i , j, n, t, diem ; FILE *fp, *fr ;
   printf ("\n nhập sĩ số : ") ; scanf("%d%*c",&n);
   lop = (KieuHV*) malloc (n*size of (KieuHV));
   nhapds(n, lop) ; sapxep ( n, lop ); inds( n, lop); getch( );
   fp = fopen ( "c :\\lop.txt ", "wb");
   for ( i = 0; i<n ; i++)
   fwrite (&lop[ i], size of (KieuHV), 1, fp);
   fclose(fp);
    printf ("\n ghi dữ liệu xong ");
    printf("\n in file sau khi sắp xếp và xét kết quả lại ");
    fr = fopen ("c:\\ketqua.txt", "wb");
    while ( fread (&tam, size of ( KieuHV), 1, fp ) > 0)
         { printf ("\n %s %s%d%s", tam.ten, tam.phai, tam.diem, tam.kq);
             if (tam.diem = = 4 &&strcmp(tam.phai,"nữ")= =0 )
                  strcmp(&tam.kq, "đậu");
                  fwrite(&tam,size of(tam),1, fr);
        }
     fclose (fp); fclose(fr);
    printf ("\n in file ketqua.txt sau khi xét lại kết qủa ");
    fp = fopen ("c:\\ketqua.txt", "rb");
     while (fread(&tam, size of (KieuHV) , 1, fp) > 0)
         printf("\n %s%s%d%s",tam.ten,tam.phai, tam.diem,tam.kq);
          fclose (fp); getch( );
&NBSP; }


CáC HàM XUấT NHậP NGẫU NHI
Và DI CHUYểN CON TRỏ CHỉ Vị (File position locator )
- Khi mở tệp tin để đọc hay ghi, con trỏ chỉ vị luôn luôn ở đầu tập tin (byte 0) nếu mở mode "a" (append) => con trỏ chỉ vị ở cuối tập tin.
+ Hàm void rewind (FILE*fp) : chuyển con trỏ chỉ vị của tập fp về đầu tập tin.
+ Hàm int fseek (FILE*fp, long số byte, int xp)
Ðối : fp : là con trỏ tập tin; số byte : là số byte cần di chuyển.
xp " cho biết vị trí xuất phát mà việc dịch chuyển được bắt đầu từ đó.
xp = SEEK - SET hay 0 xuất phát từ đầu tập.
xp = SEEK - CUR hay 1 : xuất phát từ vị trí hiện tại của con trỏ.
xp= SEEK - END HAY 2 : xuất phát từ vị trí cuối tập của con trỏ.
+ Công dụng : hàm di chuyển con trỏ chỉ vị của tập fp từ vị trí xác định bởi xp qua một số byte bằng giá trị tuyệt đối của số byte. Nếu số byte > 0 : chuyển về hướng cuối tập ngược lại chuyển về hướng đầu tập. Nếu thành công trả về trị 0. Nếu có lỗi trả khác 0.
+ Chú ý : không nên dùng fseep trên kiểu văn bản, vì sự chuyển đổi ký tự( mã 10) sẽ làm cho việc định vị thiếu chính xác.
+ Hàm long ftell(FILE*fp) ; : cho biết vị trí hiện tại của con trỏ chỉ vị (byte thứ mấy trên tập fp) nếu không thành công trả về trị -1L.
+ Ví dụ 1: giả sử tập fp có 3 ký tự .
fseek (fp,0,SEEK-END) => ftell(fp) = 3
fseek(fp,0,2) => ftell(fp) = 3
fseek (fp,-2, SEEK-END) => ftell(fp) = 1
fseek(fp,0,SEEK -SET) => ftell(fp) = 0
fseek(fp,0, 0) =>ftell(fp) = 0


+ Ví dụ 2 : giả sử ta có tập tin c:\lop.txt chứa danh sách các học viên. Hãy đọc danh sách và sắp xếp giảm dần theo điểm sau đó ghi lại file c:\lop.txt ( nối điểm)
#include <stdio.h>
#include<conio.h>
#include<string.h>
#define N 100
typedef struct
{ char ten[20] ; int tuoi; float diem ; } KieuHV ;
void main( )
{ KieuHV hv[N] ; t;
FILE*fp ; int i, , n ;
fp = fopen ("c:\\lop.txt ", "rat");
if (fp = =NULL)
   { printf ("không mở được file "); exit(1); }
       n = 0 ; i = 0 ;
     while (!feof (fp))
         { fread (&hv[i], size of (KieuHV), 1,fp);
             i++; n++ ;
  /* sắp xếp giảm dần theo điểm */
       for (i=0, i <n-1, i++)
       for (j=i+1; j<n, j++)
            if (hv[i].diem <hv[j].diem)
                { t =hv[i] ; hv[i] = hv[j] ; hv[j] = t }
/* ghi lên đĩa */
fseek (fp, 0, SEEK-END);
for ( i=0; i<n ; i++)
fwrite(&hv[i], size of (KieuHV), 1, fp);

Các Thuật Toán Sắp Xếp Cơ Bản - Qick Sort

Qick Sort chia làm 2 phần: 
PHẦN 1: Phân hoạch dãy ban đầu thành 3 dãy:
B1:
- Chọn 1 phần tử ngẫu nhiên x; thông thường ta lấy x là phần tử giữa (x=a[(l+r)/2] );
- Gán i = l, j = r
B2: Hoán đỗi những phần tử sai vị trí:
2.1 Nếu a<x thì i++
2.2 Nếu a[j]>x thì j--
2.3 Nếu i<=j thì hoán vị a,a[j] và tăng i, j lên ( i++; j--)
B3:
3.1 Nếu i>=j dừng dãy đã được sắp xếp
3.2 Nếu i<j tới B2
PHẦN 2: Thuật Toán
B1: Phân hoạch dãy đã cho thành 3 dãy: ( dùng thuật toán bên trên )
- Dãy 1: các phần tử nhỏ hơn x
- Dãy 2: x
- Dãy 3: Các phần tử lớn hơn x
B2: Gọi đệ qui
2.1 Nếu (l<j) phân hoạch dãy 1 ( l->j)
2.1 Nếu (i<r) phân hoạch dãy 3 (i->r)
Code tham khảo thuật toán ( chương trinh chạy bằng phần mềm codeblock )

#include<conio.h>
#include<stdio.h>
void qicksort(int a[],int l,int r)
{
    int i,j,t,x;
    x=a[(l+r)/2];
    i=l; j=r;
    do
    {
        while(a[i]<x) i++;
        while(a[j]>x) j--;
        if (i<=j) {t=a[i];a[i]=a[j];a[j]=t; i++;j--;}
 
    }while(i<j);
    if(l<j)
    qicksort(a,l,j);
    if(i<r)
    qicksort(a,i,r);
}
void main()
{
    int a[10];
    int n,i,j;
    for (i=1;i<7;i++)
    {
        printf("a[%d]= ",i);
        scanf("%d",&a[i]);
    }
    qicksort(a,1,6);
    for(i=1;i<7;i++)
    printf("%3d",a[i]);
    getch();

Sử dụng danh sách liên kết đơn cho bài tập Danh Sách Sinh Viên

Dùng mảng một chiều để lưu trữ một lớp học có N sinh viên. Biết rằng mỗi sinh viên bao gồm các thông tin sau: Tên (chuỗi ký tự), Mã số sinh viên (chuỗi ký tự), Điểm trung bình. Hãy viết hàm thực hiện các yêu cầu sau:
a. In danh sách sinh viên ra màn hình
b. Liệt kê những sinh viên có điểm trung bình cao nhất trong lớp học.
c. Cho biết số sinh viên có điểm trung bình >=5. Nếu không có thì thông báo không có.
d. Tìm một sinh viên có tên X trong lớp học (X nhập từ bàn phím)
e. Xoá một sinh viên có mã số cho trước trong lớp học. Nếu không có thì thông báo không có.
f. Sắp xếp danh sách sinh viên tăng theo điểm trung bình bằng thuật toán sắp xếp mà các bạn đã học (Selection Sort, Interchange Sort, Binary Sort)
g. Chèn một sinh viên vào lớp học, biết ràng sau khi chèn danh sách sinh viên vẫn tăng dần theo điểm trung bình.

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
struct sv
{
    char ten[20];
    char MSSV[10];
    int dtb;
};
struct NODE
{
    sv info;
    struct NODE* next;
};
struct LIST
{
    NODE *head;
    NODE *tail;
};
NODE* CreateNode (sv x)
{
    NODE *p;
    p=new NODE;
    if(p==NULL)  exit(1);
    p->info=x;
    p->next=NULL;
    return p;
}
void CreateList (LIST &L)
{
    L.head=L.tail=NULL;
}
void input (sv &x)
{
    printf("\nNhap MSSV: ");  fflush(stdin); gets(x.MSSV);
    printf("\nNhap ten: ");  fflush(stdin); gets(x.ten);   
    printf("\nNhap dtb: "); scanf("%d", &x.dtb);
}
void AddLast (LIST &L, NODE *p)
{
    if(L.head==NULL)  L.head=L.tail=p;
    else
    {
        L.tail->next=p;
        L.tail=p;
    }
}
void nhap (LIST &L)
{
    sv x;
    char kt;   
    printf("\nNhan phim bat ki de tiep tuc nhap.");
    printf("\nNhan 0 de dung nhap.");
    do
    {
        kt=getch();
        if(kt=='0')  break;
        input(x);
        NODE *p=CreateNode(x);
        AddLast(L,p);
    } while (1);
}
void output (sv x)
{
    printf("\n%s    %s      %d",x.MSSV,x.ten,x.dtb);
}
void xuat (LIST L)
{
    NODE *p;
    p=L.head;
    while(p!=NULL)
    {
        output(p->info);
        p=p->next;
    }
}
void maxdtb (LIST L)
{
    NODE *p,*max;
    int dem;
    p=L.head;
    max=p;
    while (p!=NULL)
    {
        if(p->info.dtb>max->info.dtb)  { max=p; dem=0; }
        if(p->info.dtb==max->info.dtb) { max=p; dem++; }
        p=p->next;
    }
    printf("\nSV co dtb cao nhat la: \n");
    if(dem==0)  output(max->info);
    else
    {
        NODE *q=L.head;
        while (q!=NULL)
        {
            if(q->info.dtb==max->info.dtb) output(q->info);
            q=q->next;
        }
    }
}
void thongkedtb (LIST L)
{
    NODE *p;
    int dem=0;
    p=L.head;
    while (p!=NULL)
    {       
        if(p->info.dtb>=5)  dem++;
        p=p->next;
    }
    if(dem==0)  printf("\nKo co sv co dtb>=5.");
    else printf("\nCo %d sv co dtb >=5.",dem);
}
void tim (LIST L)
{
    NODE *p;
    int dem=0;
    char k[20];
    printf("\nNhap ten sv can tim: ");
    fflush(stdin);
    gets(k);
    p=L.head;
    while (p!=NULL)
    {
        if(strcmp(k,p->info.ten)==0)      dem++;
        p=p->next;
    }
    if(dem!=0)
    {
            printf("\nTim thay sv: "); output(p->info);
    }
    else printf("\nKo tim thay.");
}
void xoa (LIST &L)
{
    NODE *p, *q;
    char a[10];
    p=L.head;
    q=NULL;
    printf("\nNhap MSSV can xoa: ");
    fflush(stdin);
    gets(a);
    while (p!=NULL)
    {
        if(strcmp(a, p->info.MSSV)==0)    break;
        else printf("\nKo co sv can xoa.");
        q=p;
        p=p->next;
    }
    if(q!=NULL)
    {
        if(p!=NULL)
        {
            q->next=p->next;
            delete (p);
            if(p==L.tail)  L.tail=q;
            delete(p);
        }
    }
    else
    {
        L.head=p->next;
        delete(p);
        if(L.head==NULL)  L.tail=NULL;
    }
}
void selectionsort (LIST &L)
{
    NODE *p,*q,*min;
    p=L.head;
    sv temp;
    while (p!=L.tail)
    {
        min=p;
        q=p->next;
        while (q!=NULL)
        {
            if(q->info.dtb<min->info.dtb)  min=q;
            q=q->next;
        }
        temp=p->info;
        p->info=min->info;
        min->info=temp;
        p=p->next;
    }
}
void menu()
{
    LIST L;
    NODE *p,*q,*moi;
    sv x;
    char chon;
    CreateList(L);
    do
    {
        printf("\n\t\t\tMENU");
        printf("\n\t1. Nhap ds");
        printf("\n\t2. In ds");
        printf("\n\t3. Ds sv co dtb cao nhat");
        printf("\n\t4. Ds sv co dtb >=5");
        printf("\n\t5. Tim sv");
        printf("\n\t6. Xoa sv");
        printf("\n\t7. Sap xep ds");
        printf("\n\t8. Chen sv");
        printf("\n\tNhap 0 de thoat");
        chon=getch();
        switch(chon)
        {
            case '1': { nhap(L); break;}
            case '2': { xuat(L); break;}
            case '3': { maxdtb(L); break;}
            case '4': { thongkedtb(L); break;}
            case '5': { tim(L); break;}
            case '6': { xoa(L); printf("\nDs sau khi xoa: "); xuat(L); break;}
            case '7': { selectionsort(L);printf("\nDs sau khi sap xep: "); xuat(L); break;}
            case '8':
                    {
                        sv them;
                        printf("\nNhap thong tin sv can them: ");
                        input(them);
                        NODE *t= CreateNode(them);
                        AddLast(L,t);
                        selectionsort(L);
                        printf("\nDs sau khi them :");
                        xuat(L);
                        break;
                    }
            case '0': exit(1);
            default: printf("\nNhap lai.");
        }
    } while (chon!='0');
}
int main()
{
    while(1)
    {
        menu();
        getch();
    }
}

Các code cơ bản trong cây nhị phân Binary Tree


I/Định nghĩa :
Cây là cấu trúc dữ liệu dùng để lưu trữ một tập các dữ liệu có cùng kiểu và các dữ liệu này được lưu trữ không liên tiếp trong bộ nhớ . Mỗi nút (phần tử) trên cây sẽ giữ địa chỉ của nút con bên trái và địa chỉ của nút con bên phải , khi đó chỉ cần biết địa chỉ nút gốc (nút không là con của bất kỳ nút nào ) là có thể truy xuất đến tất cả các nút .

Danh sách liên kết đơn là trường hợp đặc biệt của cây nhị phân mà tất cả các nút chỉ con trái hoặc tất cả các nút chỉ con phải .
II/Các loại cây nhị phân :
II.1/Cây nhị phân tìm kiếm (Binary Search Tree-Hình 1)

İmage
Với mọi nút p , dữ liệu của các nút trên cây con trái của p <= dữ liệu nút p <= dữ liệu của các nút trên cây con phải của p .
II.2/Cây nhị phân đúng (Strictly Binary Tree-Hình 2)
İmage
Tất cả các nút đều có 2 con , ngoại trừ nút lá .
II.3/Cây nhị phân đầy (Complete Binary Tree-Hình 3)
İmage
Là cây nhị phân đúng và tất cả các nút lá ở cùng mức .
Nếu cây có chiều cao h thì số nút của cây là N = 2^(h+1) - 1 ==> h = log2(N+1) -1 . Vậy chiều cao của cây nhỏ hơn rất nhiều so với tổng số nút ==> Tìm kiếm nhanh .
Cây nhị phân đầy sẽ có đầy đủ các nút ở mỗi mức .
II.4/Cây nhị phân gần đầy(Almost Complete Binary Tree)
Tất cả các mức <=h-1 (h là chiều cao của cây) có đầy đủ các nút , còn ở mức h , các nút đầy từ trái sang phải .
III/Ưu khuyết điểm cây nhị phân tìm kiếm :
III.1/Ưu điểm :

Có được ưu điểm của danh sách liên kết như là : Thao tác hủy hoặc chèn rất nhanh , có thể cấp phát thêm nút hoặc thu hồi bộ nhớ đã cấp phát cho nút và kích thước cây không bị giới hạn bởi 64 KB .
Có thêm ưu điểm khác là tìm kiếm nhanh (trong khi danh sách liên kết tìm kiếm chậm).
III.2/Khuyết điểm :
Tốn thêm bộ nhớ để lưu trữ địa chỉ nút con trái , con phải .
IV/Các hàm xử lý cây nhị phân tìm kiếm :
IV.1/Khai báo cấu trúc một nút :

Mã:
struct node
{
   int data;//Noi dung cua nut
   node *letf , *right;//Dia chi nut trai , nut phai
};
typedef node *nodeptr;
IV.2/Hàm khởi tạo cây :
Khởi tạo cây là làm cho cây rỗng bằng cách gán root = NULL
Mã:
void init_tree(nodeptr &root)
{
   root = NUll;
}
IV.3/Hàm kiểm tra cây rỗng :
Nếu root = NULL thì cây rỗng , và hàm trả về giá trị 1 , ngược lại trả về 0
Mã:
int empty_tree(nodeptr root)
{
   if(root == NULL)   return 1;
   else return 0;
}
IV.4/Hàm tạo một nút :
Cấp phát bộ nhớ cho một nút , cất dữ liệu vào nút , gán left , right == NULL , trả về địa chỉ nút.
Mã:
nodeptr make_node(int x)
{
   noteptr p = new node; 
   p->data = x;
   p->left = p->right = NULL;
   return p;
}
IV.5/Hàm chèn một nút :
Chèn nút chứa dữ liệu x vào cây có gốc là root và trả về địa chỉ nút mới chèn.
Mã:
nodeptr insert_node(nodeptr &root , int x)
{
   nodeptr p =make_node(x) ;
   nodeptr q,f;
   if(root == NULL)
   {
      root = p;
   }
   else
   {
      root = q;
      f=NULL;
      while(q!=NULL)
      {
         f = q;
         if(x < q ->data)
         {
            q = q->left;
         }
         else
         {
            q = q->right;
         }
      }
      if(x < f->data)
      {
         f->left = p;
      }
      else
      {
         f->right = p;
      }
   }
   return p;
}
IV.6/ Hàm tìm nút :
Tìm nút chứa x trên cây có gốc là root , nếu tìm thấy trả về địa chỉ nút chứa x , ngược lại trả về NULL.
Mã:
nodeptr search_node(nodeptr root , int x)
{
   nodeptr p = root;
   while(p!=NULL)
   {
      if(p->data == x)          return p;
      else if(x < p->data)           p = p->left;
               else          p = p->right;
   }
   return NULL;
}
IV.7/ Hàm hủy nút :
Gọi p là nút cần hủy , có ba trường hợp :
a/ p không có con :
delete p;
b/ p có một con :
Gọi f là cha p , q là con p .
Cho q là con của f .
delete p ;
c/ p có 2 con : đưa về trường hợp hủy nút có không con hoặc một con bằng cách :
+) Tìm nút thế mạng q
q là nút cực trái của cây con phải của p hoặc q là nút cực phải của của cây con trái của p .
q sẽ có không con hoặc một con .
+) Chép dữ liệu q vào p .
+) Hủy q .
Mã:
int del_node(nodeptr &root , int x)
{
   nodeptr p , q , f;
   p = root;
   f = NULL;
   while(p!=NULL)
   {
      if(p->data == x)     break;
      else
      {
         f = p;
         if(x<p->data)          p = p->left;
         else          p = p->right;
      }
   }
   if(p==NULL)         return 0;
   else
   {
      if(p->left !=NULL && p->right!=NULL)
      {
         q = p->right;
         f = p;
         while(q->left!=NULL)
         {
            f = q;
            q = q->left;
         }
         p->data = q->data;
         p = q;
      }
      if(p->left!=NULL)          q = p->left;
      else          q = p->right;
      if(p==root)         root = q;
      else
      {
          if(p=f->left)         f->left = q;
         else          f->right = q;
      }
      delete p;
      return 1;
   }
}
IV.8/ Hàm tạo cây :
Nhập vào n số nguyên , lưu vào cây nhị phân tìm kiếm .
Mã:
void input_tree(nodeptr &root)
{
   int n,x;
   root = NULL;
   printf("\nSo phan tu : ");
   scanf("%d" , &n);
   for(int i=1; i<=n; i++)
   {
      printf("Phan tu thu %d : ",i);
      scanf("%d" , &x);
      insert_node(root , x);
   }
}
IV.9/ Hàm duyệt cây :
Có 6 phương pháp duyệt cây : NLR , LNR ; LRN ; NRL ; RNL ; RLN . Ba phương pháp sau tương tự với 3 phương pháp đầu nên ta chỉ xét 3 phương pháp đầu .
a/ Node - Left - Right :
Duyệt nút gốc - Duyệt cây con trái - Duyệt cây con phải .
Mã:
void NLR(nodeptr root)
{
   if(root!=NULL)
   {
      printf("%d" , root->data);
      NLR(root->left);
      NLR(root->right);
   }
}
b/ Left - Node - Right :
Duyệt cây con trái - Duyệt nút gốc - Duyệt cây con phải .
Phương pháp duyệt này sẽ cho dãy tăng .(RNL sẽ cho dãy giảm)
Mã:
void LRN(nodeptr root)
{
   if(root!=NULL)
   {
      LNR(root->left);
      printf("%d" , root->data);
      LNR(root->right);
   }
}
c/ Left - Right - Node :
Duyệt cây con trái - Duyệt cây con phải - Duyệt nút gốc .
Mã:
void LRN(nodeptr root)
{
   if(root!=NULL)
   {
      LRN(root->left);
      LRN(root->right);
      printf("%d" , root->data);
   }
}
IV.10/ Hàm hủy cây :
Thu hồi bộ nhớ đã cấp phát cho tất cả các nút trên cây , làm cho cây rỗng .
Mã:
void del_tree(nodeptr &root)
{
   if(root!=NULL)
   {
      del_tree(root->left);
      del_tree(root->right);
      delete root;
      root = NULL;
   }
}

Bài tập ôn tập danh sách liên kết đơn

Bài 1: Một danh sách sinh viên được tổ chức lưu trữ bằng cấu trúc Danh sách liên kết đơn (DSLKD). Mỗi sinh viên có những thông tin sau:
 Masv( kieu nguyên), họ tên (kiểu char[30]), diem toan(dt ; kiểu int), điểm lý (dl ; kiểu int), điểm hóa (dh; kiểu int) ()
 1. Viết chương trình nhập vào n sinh viên(n nhập từ bàn phím)
 2. In ra tất cả sinh viên thi lại ít nhất 1 môn 
3. In ra tất cả sinh viên thi lại cả 3 môn 
4. In ra tất cả sinh viên là sinh viên giỏi (diem trung binh 3 môn >=8 và không có môn nào thi lại)
 5. In ra tất cả sinh viên là sinh viên khá (8>diem trung binh 3 môn >=7; và không có môn nào thi lại) 6. In ra tất cả sinh viên là sinh viên trung bình và không có môn nào thi lại)
 7. In ra tất cả sinh viên là sinh viên có điểm trung bình cao nhất
 8. In ra tất cả sinh viên là sinh viên có điểm trung bình thấp nhất
 9.Nhập vào Masv nào đó, cho phép tìm kiếm tuần tự theo Masv 
10. Xóa bỏ tất cả những sinh viên có điểm trung bình (dtb) =8

 Bài 2: Viết chương trình nhập vào n số nguyên dương lẻ, các số này được lưu dưới dạng danh sách liên kết đơn. TÍnh tổng các phần tử là số chính phương

Bài 3: Giả sử ma trận vuông thưa được lưu trữ dạng DSLK đơn. 
1. Tính tổng các phần tử trên đường chéo chính của ma trận trên 
2. Tính tổng các phần tử trên đường chéo phụ của ma trận trên 

Bài 4: Sử dụng Danh sách liên kết đơn để lưu trữ n số nguyên nhập từ bàn phím. 
1. Loại bỏ tất cả các phân tử bị lặp trong danh sách nói trên
 2. Loại bỏ tất cả các phân tử âm trong danh sách nói trên 
3. Sắp xếp các số đó theo chiều tăng dần 

Bài 5: Viết chương trình cho phép nhập 2 đa thức (đa thức được tổ chức dạng DSLK đơn) 
1.Tính tổng 2 đa thức
 2. Tính hiệu 2 đa thức 

Bài 6: Viết chương trình cho phép nhập 2 đa thức (đa thức được tổ chức dạng DSLK kép) 
1.Tính tổng 2 đa thức
 2. Tính hiệu 2 đa thức

Tìm kiếm trong cây nhị phân - Binary Search Tree


#include<stdio.h>
#include<stdlib.h>


struct searchtree
{
 int element;
 struct searchtree *left,*right;
}*root;
typedef struct searchtree *node;
typedef int ElementType;

node insert(ElementType, node);
node delet(ElementType, node);
void makeempty();
node findmin(node);
node findmax(node);
node find(ElementType, node);
void display(node, int);

void main()
{
 int ch;
 ElementType a;
 node temp;
 makeempty();
 while(1)
 {
  printf("\n1. Insert\n2. Delete\n3. Find \n4. Find min\n5. Find max\n6. Display\n7. Exit\nEnter Your Choice : ");
  scanf("%d",&ch);
  switch(ch)
  {
   case 1:
    printf("Enter an element : ");
    scanf("%d", &a);
    root = insert(a, root);
    break;
   case 2:
    printf("\nEnter the element to delete : ");
    scanf("%d",&a);
    root = delet(a, root);
    break;
   case 3:
    printf("\nEnter the element to search : ");
    scanf("%d",&a);
    temp = find(a, root);
    if (temp != NULL)
     printf("Element found");
    else
     printf("Element not found");
    break;
   case 4:
    temp = findmin(root);
    if(temp==NULL)
     printf("\nEmpty tree");
    else
     printf("\nMinimum element : %d", temp->element);
    break;
   case 5:
    temp = findmax(root);
    if(temp==NULL)
     printf("\nEmpty tree");
    else
     printf("\nMaximum element : %d", temp->element);
    break;
   case 6:
    if(root==NULL)
     printf("\nEmpty tree");
    else
     display(root, 1);
    break;
   case 7:
    exit(0);
   default:
    printf("Invalid Choice");
  }
 }
}

node insert(ElementType x,node t)
{
 if(t==NULL)
 {
  t = (node)malloc(sizeof(node));
  t->element = x;
  t->left = t->right = NULL;
 }
 else
 {
  if(x < t->element)
   t->left = insert(x, t->left);
  else if(x > t->element)
   t->right = insert(x, t->right);
 }
 return t;
}

node delet(ElementType x,node t)
{
 node temp;
 if(t == NULL)
  printf("\nElement not found");
 else
 {
  if(x < t->element)
   t->left = delet(x, t->left);
  else if(x > t->element)
   t->right = delet(x, t->right);
  else
  {
   if(t->left && t->right)
   {
    temp = findmin(t->right);
    t->element = temp->element;
    t->right = delet(t->element,t->right);
   }
   else if(t->left == NULL)
    t=t->right;
   else
    t=t->left;
  }
 }
 return t;
}
void makeempty()
{
 root = NULL;
}

node findmin(node temp)
{
 if(temp == NULL || temp->left == NULL)
  return temp;
 return findmin(temp->left);
}

node findmax(node temp)
{
 if(temp==NULL || temp->right==NULL)
  return temp;
 return findmax(temp->right);
}

node find(ElementType x, node t)
{
 if(t==NULL) return NULL;
 if(x<t->element) return find(x,t->left);
 if(x>t->element) return find(x,t->right);
 return t;
}

void display(node t,int level)
{
 int i;
 if(t)
 {
  display(t->right, level+1);
  printf("\n");
  for(i=0;i<level;i++)
   printf(" ");
  printf("%d", t->element);
  display(t->left, level+1);
 }
}



Sample Output:

1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 1
Enter an element : 10

1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 1
Enter an element : 20

1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 1
Enter an element : 5

1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 4
The smallest Number is 5

1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 3
Enter an element : 100
Element not Found

1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 2
Enter an element : 20

1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 6
20
10

1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 7




Duyệt cây nhị phân - Binary Search Tree Traversal


#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

struct TreeNode;
typedef struct TreeNode *node;
typedef int ElementType;

struct TreeNode
{
 int element;
 node left, right;
}*root;

node insert(ElementType x,node t)
{
 if(t==NULL)
 {
  t = malloc(sizeof(node));
  t->element = x;
  t->left = t->right = NULL;
 }
 else
 {
  if(x < t->element)
   t->left = insert(x, t->left);
  else if(x > t->element)
   t->right = insert(x, t->right);
 }
 return t;
}

void printpreorder(node T)
{
 if(T != NULL)
 {
  printf("%d ", T->element);
  printpreorder(T->left);
  printpreorder(T->right);
 }
}

void printinorder(node T)
{
 if(T != NULL)
 {
  printinorder(T->left);
  printf("%d ", T->element);
  printinorder(T->right);
 }
}

void printpostorder(node T)
{
 if(T != NULL)
 {
  printpostorder(T->left);
  printpostorder(T->right);
  printf("%d ", T->element);
 }
}

void main()
{
 int ch;
 ElementType a;
 root = NULL;
 while(1)
 {
  clrscr();
  printf("\n1. Insert\n2. Print Pre Order\n3. Print In Order\n4. Print Post Order\n5. Exit\nEnter Your Choice : ");
  scanf("%d",&ch);
  switch(ch)
  {
   case 1:
    printf("Enter an element : ");
    scanf("%d", &a);
    root = insert(a, root);
    break;
   case 2:
    printpreorder(root);
    break;
   case 3:
    printinorder(root);
    break;
   case 4:
    printpostorder(root);
    break;
   case 5:
    exit(0);
   default:
    printf("Invalid Choice");
  }
  getch();
 }
}

Sample Output:

1. Insert
2. Print Pre Order
3. Print In Order
4. Print Post Order
5. Exit
Enter Your Choice : 1
Enter an Element : 1
1. Insert
2. Print Pre Order
3. Print In Order
4. Print Post Order
5. Exit
Enter Your Choice : 1
Enter an Element : 5
1. Insert
2. Print Pre Order
3. Print In Order
4. Print Post Order
5. Exit
Enter Your Choice : 1
Enter an Element : 2
1. Insert
2. Print Pre Order
3. Print In Order
4. Print Post Order
5. Exit
Enter Your Choice : 1
Enter an Element : 7
1. Insert
2. Print Pre Order
3. Print In Order
4. Print Post Order
5. Exit
Enter Your Choice : 2
1 2 5 7
1. Insert
2. Print Pre Order
3. Print In Order
4. Print Post Order
5. Exit
Enter Your Choice : 3
1 5 2 7
1. Insert
2. Print Pre Order
3. Print In Order
4. Print Post Order
5. Exit
Enter Your Choice : 4
2 7 5 1
1. Insert
2. Print Pre Order
3. Print In Order
4. Print Post Order
5. Exit
Enter Your Choice : 5