[Nhật ký] Cấu trúc dữ liệu!

Lý thuyết:
2. Xử lý xung đột trong bảng băm (tiếp):

• Phương pháp dò tuyến tính
• Phương pháp dò bậc 2
• Phương pháp băm kép

Lý thuyết:
1. Bảng băm và xung đột bảng băm
2. Xử lý xung đột trong bảng băm:

• Phương pháp nối kết trực tiếp
• Phương pháp nối kết hợp nhất

a) Lý thuyết:
3. Cây tìm kiếm nhị phân (tiếp): các phép toán: tìm kiếm | thêm nút | xóa nút | duyệt cây

Code:

/* Chuong trinh minh hoa cay nhi phan tim kiem */
#include "conio.h"
#include "stdio.h"
#include "stdlib.h"

//Cau truc cua Node
typedef struct
{
  char tenhs[10];
  int cmt;
  float dtoan,dly,dhoa,dtb;
}Data;
typedef struct Node
{
  Data infor;
  Node *Left,*Right;
}Node,*Tree;

//Khoi tao Node
Node *MakeNode(Data x)
{
  Node *p;
  p=(Node *)malloc(sizeof(Node));
  p->infor = x;
  p->Left = NULL;
  p->Right = NULL;
  return p;
}

//Ham nhap thong tin mot Node
void nhap(Data *x)
{
  float tam;
  printf("\nTen:");fflush(stdin);gets(x->tenhs);
  printf("CMT:");scanf("%d",&x->cmt);
  printf("Diem Toan:");scanf("%f",&tam);x->dtoan=tam;
  printf("Diem Ly:");scanf("%f",&tam);x->dly=tam; 
  printf("Diem Hoa:");scanf("%f",&tam);x->dhoa=tam; 
  x->dtb=(x->dtoan+x->dly+x->dhoa)/3;
}

//Ham in thong tin mot Node
void hien(Data x)
{
  printf("\nTen:%-10sCMT:%7dToan:%6.2fLy:%6.2fHoa:%6.2fDTB:%6.2f",x.tenhs,x.cmt,x.dtoan,x.dly,x.dhoa,x.dtb);
}

//Khoi tao cay ban dau
void init(Tree *Root)
{
    *Root=NULL;
}

//Them 1 node vao cay tim kiem nhi phan
void InsertNode(Tree *k,Node *p)
{
  if (p->infor.cmt < (*k)->infor.cmt )
  {
      if((*k)->Left)
        InsertNode(&(*k)->Left,p);
      else
        (*k)->Left = p;
  }
  else
  if (p->infor.cmt > (*k)->infor.cmt)
  {
      if((*k)->Right)
        InsertNode(&(*k)->Right,p);
      else
        (*k)->Right = p;
  }
}

//Thu tuc them node cho cay ban dau
void PushNode(Tree *k,Data x)
{
  Tree p = MakeNode(x);
  if (*k == NULL)
      *k = p;
  else
      InsertNode(&*k,p);
}

//Nhap cac Node vao cay
void InputTree(Tree *k)
{
  Data x;
  printf("Nhap vao cac phan tu trong cay nhi phan tim kiem.\n");
  char ch;
  do
  {
      printf("Co tiep khong (Y/N):");ch=getch();
      if (ch=='Y'||ch=='y')
      {
        nhap(&x);
        PushNode(&(*k),x);
      }
  }
  while(ch=='Y'||ch=='y');
}

//Duyet tien to
void NLR(Tree k)
{
  if(k != NULL)
  {
      printf("\nTen:%-10sCMT:%7dToan:%6.2fLy:%6.2fHoa:%6.2fDTB:%6.2f",k->infor.tenhs,k->infor.cmt,k->infor.dtoan,k->infor.dly,k->infor.dhoa,k->infor.dtb);
      NLR(k->Left);
      NLR(k->Right);
  }
}

//Duyet trung to
void LNR(Tree k)
{
  if(k != NULL)
  {
      LNR(k->Left);
      printf("\nTen:%-10sCMT:%7dToan:%6.2fLy:%6.2fHoa:%6.2fDTB:%6.2f",k->infor.tenhs,k->infor.cmt,k->infor.dtoan,k->infor.dly,k->infor.dhoa,k->infor.dtb);
      LNR(k->Right);
  }
}

//Duyet hau to
void LRN(Tree k)
{
  if(k != NULL)
  {
      LRN(k->Left);
      LRN(k->Right);
      printf("\nTen:%-10sCMT:%7dToan:%6.2fLy:%6.2fHoa:%6.2fDTB:%6.2f",k->infor.tenhs,k->infor.cmt,k->infor.dtoan,k->infor.dly,k->infor.dhoa,k->infor.dtb);
  }
}

//Ham tim kiem nhi phan neu tim thay tra ve 1 nguoc lai 0
char Search(Tree k,int x)
{
  Tree tam = k;
  while (tam != NULL )
  {
      if (tam -> infor.cmt == x)
        return 1;
      else
      {
        if (tam -> infor.cmt > x)
            tam = tam -> Left;
        else
            tam = tam -> Right;
      }
  }
  return 0;
}

//Chuong trinh chinh
int main()
{
  Tree Root;
  int n;

  init(&Root);
  InputTree(&Root);

  printf("\nGia tri cua cay khi duyet NLR.\n");
  NLR(Root);

  printf("\nGia tri cua cay khi duyet LNR.\n");
  LNR(Root);

  printf("\nGia tri cua cay khi duyet LRN.\n");
  LRN(Root);

  printf("\nBan muon tim phan tu gi trong cay? ");
  scanf("%d",&n);
  if ( Search(Root,n) == 0 )
      printf("\nPhan tu %d khong co trong cay nhi phan tim kiem.\n",n);
  else
      printf("\nPhan tu %d co trong cay nhi phan tim kiem.\n",n);

  getch();
  return 0;
}


4. Chuyển cây tổng quát thành cây nhị phân: (hình như phần này thầy Phúc ko cho code, mà nghĩ cũng chưa chắc ra)

• Nút gốc của cây tổng quát là nút gốc của cây nhị phân
• Con trái thứ nhất là con trái của cây nhị phân, đem liền kề là con phải của cây nhị phân

b) Bài tập về nhà:

1. Viết hàm in thông tin gồm tên và mã của sinh viên trong bài 18 - phần bài tập
   

   Code:

   void hien(Data x)
{
  printf("\nTen:%-10sCMT:%7dToan:%6.2fLy:%6.2fHoa:%6.2fDTB:%6.2f",x.tenhs,x.cmt,x.dtoan,x.dly,x.dhoa,x.dtb);
}

2. Tính tổng thuế nếu mỗi nút là 1 mặt hàng (tên mặt hàng, mã mặt hàng, thuế)
   

   Code:

   /* Tinh tong thue cac mat hang */
#include "conio.h"
#include "stdio.h"
#include "stdlib.h"

//Cau truc cua Node
typedef struct
{
  char tenmh[10];
  int mamh;
  float thue;
}Data;
typedef struct Node
{
  Data infor;
  Node *Left,*Right;
}Node,*Tree;

//Khoi tao Node
Node *MakeNode(Data x)
{
  Node *p;
  p=(Node *)malloc(sizeof(Node));
  p->infor = x;
  p->Left = NULL;
  p->Right = NULL;
  return p;
}

//Ham nhap thong tin mot Node
void nhap(Data *x)
{
  float tam;
  printf("\nTen mat hang:");fflush(stdin);gets(x->tenmh);
  printf("Ma mat hang:");scanf("%d",&x->mamh);
  printf("Thue:");scanf("%f",&tam);x->thue=tam;
}

//Ham in thong tin mot Node
void hien(Data x)
{
  printf("\nTen:%-10sMa:%7dThue:%6.2f",x.tenmh,x.mamh,x.thue);
}

//Khoi tao cay ban dau
void init(Tree *Root)
{
    *Root=NULL;
}

//Them 1 node vao cay tim kiem nhi phan
void InsertNode(Tree *k,Node *p)
{
  if (p->infor.mamh < (*k)->infor.mamh )
  {
      if((*k)->Left)
        InsertNode(&(*k)->Left,p);
      else
        (*k)->Left = p;
  }
  else
  if (p->infor.mamh > (*k)->infor.mamh)
  {
      if((*k)->Right)
        InsertNode(&(*k)->Right,p);
      else
        (*k)->Right = p;
  }
}

//Thu tuc them node cho cay ban dau
void PushNode(Tree *k,Data x)
{
  Tree p = MakeNode(x);
  if (*k == NULL)
      *k = p;
  else
      InsertNode(&*k,p);
}

//Nhap cac Node vao cay
void InputTree(Tree *k)
{
  Data x;
  printf("Nhap vao cac mat hang.\n");
  char ch;
  do
  {
      printf("Co tiep khong (Y/N):");ch=getch();
      if (ch=='Y'||ch=='y')
      {
        nhap(&x);
        PushNode(&(*k),x);
      }
  }
  while(ch=='Y'||ch=='y');
}

//Duyet tien to
void NLR(Tree k)
{
  if(k != NULL)
  {
      printf("\nTen:%-10sMa:%7dThue:%6.2f",k->infor.tenmh,k->infor.mamh,k->infor.thue);
      NLR(k->Left);
      NLR(k->Right);
  }
}

//Ham tinh tong thue cac mat hang
float tongthue(Tree k)
{
    Tree tam=k;
    float t;
    if (tam==NULL) return 0;
    else
          t=tongthue(k->Left)+tongthue(k->Right)+k->infor.thue;
    return t;
}

//Chuong trinh chinh
int main()
{
  Tree Root;
  int n;

  init(&Root);
  InputTree(&Root);

  printf("\nDuyet NLR.\n");
  NLR(Root);

  printf("Tong thue la:%6.2f",tongthue(Root));
 
  getch();
  return 0;
}

3. Thống kê sinh viên đạt học bổng (d1,d2,d3>=5,dtb>=7) trong cây gồm các nút là các sinh viên (họ tên, mã sinh viên, điểm môn 1, điểm môn 2, điểm môn 3, điểm trung bình)
   

   Code:

   /* Chuong trinh hoc bong sinh vien */
#include "conio.h"
#include "stdio.h"
#include "stdlib.h"

//Cau truc cua Node
typedef struct
{
  char tensv[10];
  int msv;
  float dm1,dm2,dm3,dtb;
}Data;
typedef struct Node
{
  Data infor;
  Node *Left,*Right;
}Node,*Tree;

//Khoi tao Node
Node *MakeNode(Data x)
{
  Node *p;
  p=(Node *)malloc(sizeof(Node));
  p->infor = x;
  p->Left = NULL;
  p->Right = NULL;
  return p;
}

//Ham nhap thong tin mot Node
void nhap(Data *x)
{
  float tam;
  printf("\nTen:");fflush(stdin);gets(x->tensv);
  printf("Ma sinh vien:");scanf("%d",&x->msv);
  printf("Diem mon 1:");scanf("%f",&tam);x->dm1=tam;
  printf("Diem mon 2:");scanf("%f",&tam);x->dm2=tam; 
  printf("Diem mon 3:");scanf("%f",&tam);x->dm3=tam; 
  x->dtb=(x->dm1+x->dm2+x->dm3)/3;
}

//Ham in thong tin mot Node
void hien(Data x)
{
  printf("\nTen:%-10sCMT:%7dToan:%6.2fLy:%6.2fHoa:%6.2fDTB:%6.2f",x.tensv,x.msv,x.dm1,x.dm2,x.dm3,x.dtb);
}

//Khoi tao cay ban dau
void init(Tree *Root)
{
    *Root=NULL;
}

//Them 1 node vao cay tim kiem nhi phan
void InsertNode(Tree *k,Node *p)
{
  if (p->infor.msv < (*k)->infor.msv )
  {
      if((*k)->Left)
        InsertNode(&(*k)->Left,p);
      else
        (*k)->Left = p;
  }
  else
  if (p->infor.msv > (*k)->infor.msv)
  {
      if((*k)->Right)
        InsertNode(&(*k)->Right,p);
      else
        (*k)->Right = p;
  }
}

//Thu tuc them node cho cay ban dau
void PushNode(Tree *k,Data x)
{
  Tree p = MakeNode(x);
  if (*k == NULL)
      *k = p;
  else
      InsertNode(&*k,p);
}

//Nhap cac Node vao cay
void InputTree(Tree *k)
{
  Data x;
  printf("Nhap thong tin sinh vien.\n");
  char ch;
  do
  {
      printf("Co tiep khong (Y/N):");ch=getch();
      if (ch=='Y'||ch=='y')
      {
        nhap(&x);
        PushNode(&(*k),x);
      }
  }
  while(ch=='Y'||ch=='y');
}

//Duyet tien to
void NLR(Tree k)
{
  if(k != NULL)
  {
      printf("\nTen:%-10sCMT:%7dToan:%6.2fLy:%6.2fHoa:%6.2fDTB:%6.2f",k->infor.tensv,k->infor.msv,k->infor.dm1,k->infor.dm2,k->infor.dm3,k->infor.dtb);
      NLR(k->Left);
      NLR(k->Right);
  }
}

int thongke(Tree k)
{
  int dem=0;
  Tree tam=k;
  if(tam==NULL) return 0;
  else
  {
      if (tam->infor.dm1>=5&&tam->infor.dm2>=5&&tam->infor.dm3>=5&&tam->infor.dtb>=7)
      {
          dem++;
          hien(tam->infor);
      }
      dem=dem+thongke(k->Left)+thongke(k->Right);
  }
  return dem;
}

//Chuong trinh chinh
int main()
{
  Tree Root;
  int x;

  init(&Root);
  InputTree(&Root);

  printf("\nDanh sach sinh vien vua nhap.\n");
  NLR(Root);

  printf("\n\nTrong do:\n");
  x=thongke(Root);
  if (x==0) printf("\nKhong co sinh vien nao dat hoc bong...");
    else
        printf("\nCo %d sinh vien dat hoc bong...",x);

  getch();
  return 0;
}


Gợi ý: Wordpress Blog

a) Lý thuyết:
Hàng đợi (Queue) và các phép toán: createQ | emptyQ | fullQ | addQ | delQ
b) Bài tập về nhà:

1. Viết hàm size cho biết số phần tử trong hàng đợi
   
2. Viết hàm backQ lấy được giá trị phần tử cuối cùng trong hàng đợi
   
3. Viết hàm frontQ lấy giá trị phần tử đầu tiên trong hàng đợi
   
4. Giả sử cấu trúc Queue gồm những phép toán trên, có hàng đợi Q1 chứa các phần tử có giá trị nhị phân. Viết chương trình dùng các phép toán trên in ra giá trị thập phân tương ứng của hàng đợi.
   
5. Đổi cơ số từ nhị phân sang cơ số bất kì sử dụng Queue

Gợi ý: Wordpress Blog

a) Lý thuyết:
Ngăn xếp (Stack) và các phép toán: createS | emptyS | fullS | pushS | popS
b) Bài tập về nhà:

1. Đổi cơ số thập phân sang nhị phân (sử dụng Stack và các phép toán trên)
   
2. Lấy ra phần tử thứ k trong Stack, các phần tử khác vẫn giữ nguyên
   
3. Tính trung bình cộng các phần tử chẵn trong Stack
   
4. So sánh 2 Stack
   
5. Chuyển đổi cơ số từ nhị phân sang thập phân
   
6. Chuyển đổi cơ số từ thập phân sang hệ cơ số bất kì

Gợi ý:

Code:

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <string.h>
typedef struct
{
        int num;
}Data;
typedef struct tagNode
{
        Data infor;
        struct tagNode *link;
}Node,*Stack;
void nhap(Data *x)
{
    printf("Nhap so nguyen:");
    scanf("%d",&(x->num));
}
void createS(Stack *s)
{
    *s=NULL;
}
int emptyS(Stack s)
{
    return(s==NULL);
}
int fullS(Stack s)
{
    return 0;
}
void pushS(Data x,Stack *s)
{
    Node *p=new Node;
    p->infor=x;
    p->link=*s;
    *s=p;
}
void popS(Stack *s,Data *x)
{
    Node *p=*s;
    if (emptyS(*s)) return;
      else
      {
          *s=p->link;
          *x=p->infor;
          free(p);
      }         
}
void doi10to2(int N)
{
    int du;
    Data x;
    Stack s;
    createS(&s);
    while (N!=0)
    {
          du=N%2;
          x.num=du;
          pushS(x,&s);
          N=N/2;
    }
    while (!emptyS(s))
    {
          popS(&s,&x);
          printf("%d",x.num);
    }
}
void pullS(Stack *s,int k)
{
    int dem=0,i;
    Stack p;
    Data x;
    char ch;
    Stack s1;
    createS(&s1);
    do
    {
          printf("Nhap tiep khong?(Y/N):");
          ch=toupper(getch());
          if (ch=='Y')
          {
            nhap(&x);
            pushS(x,s);
          }
    }
    while (ch=='Y');
    p=*s;
    while (p!=NULL)
    {
          dem++;
          p=p->link;
    }
    if ((k>dem)||(k<=0)) printf("\nDo dai Stack k thoa man nhu cau");
      else
      {
          for (i=0;i<=k-2;i++)
              {
                  popS(s,&x);
                  pushS(x,&s1);
              }
          popS(s,&x);
          while (!emptyS(s1)&&k>=2)
                  {
                    popS(&s1,&x);
                    pushS(x,s);
                  }
      }
    printf("Thu lai:");
    p=*s;
    while (p!=NULL)
    {
          printf("\np->infor.num=%d",p->infor.num);
          p=p->link;
    }
    printf("Done");
}
void average(Stack s)
{
    Data x;
    char ch;
    int dem=0,sum=0;
    do
    {
          printf("Nhap tiep khong?(Y/N):");
          ch=toupper(getch());
          if (ch=='Y')
          {
            nhap(&x);
            pushS(x,&s);
          }
    }
    while (ch=='Y');
    while (!emptyS(s))
    {
          popS(&s,&x);
          if (x.num%2==0)
          {
              sum+=x.num;
              dem++;
          }         
    }
    printf("\nAVERAGE=%7.2f",(float)(sum/dem));
}
void sosanh(Stack s1,Stack s2)
{
    char ch;
    Data x1,x2;
    int dem=0,size1=0,size2=0;
    printf("\nNhap Stack 1:\n");
    do
    {
          printf("Nhap tiep khong?(Y/N):");
          ch=toupper(getch());
          if (ch=='Y')
          {
            nhap(&x1);
            pushS(x1,&s1);
            size1++;
          }
    }
    while (ch=='Y');
    printf("\nNhap Stack 2:\n");
    do
    {
          printf("Nhap tiep khong?(Y/N):");
          ch=toupper(getch());
          if (ch=='Y')
          {
            nhap(&x2);
            pushS(x2,&s2);
            size2++;
          }
    }
    while (ch=='Y');
    if (size1==0||size2==0)
    {
        printf("\nMot trong hai Stack rong, so sanh khong duoc thuc hien...");
        return;
    }
    if (size1!=size2) printf("...\nHai Stack khong bang nhau!");
      else
        {
          while (!emptyS(s1)||!emptyS(s2))
          {
                popS(&s1,&x1);
                popS(&s2,&x2);
                if (x1.num==x2.num) dem++;
          }
          if (dem==size1) printf("...\nHai Stack bang nhau!");
            else printf("...\nHai Stack khong bang nhau!");
        }
}
float doics2to10(char ch[30])
{
    float sum=0;
    int i,j=0,d=strlen(ch)-1;
    for (i=d;i>=0;i--)
    {
        if (ch[i]=='1') sum=sum+pow(2,j);
        j++;
    }
    getch();
    return sum;
}
void doi10to8(int N)
{
    int du;
    Data x;
    Stack s;
    createS(&s);
    while (N!=0)
    {
          du=N%8;
          x.num=du;
          pushS(x,&s);
          N=N/8;
    }
    while (!emptyS(s))
    {
          popS(&s,&x);
          printf("%d",x.num);
    }
}
void doi10to16(int N)
{
    int du;
    Data x;
    Stack s;
    createS(&s);
    while (N!=0)
    {
          du=N%16;
          x.num=du;
          pushS(x,&s);
          N=N/16;
    }
    while (!emptyS(s))
    {
          popS(&s,&x);
          if (x.num<9) printf("%d",x.num);
            else
              switch(x.num)
                {
                    case 10:printf("A");break;
                    case 11:printf("B");break;                   
                    case 12:printf("C");break;                   
                    case 13:printf("D");break;                   
                    case 14:printf("E");break;                   
                    case 15:printf("F");break;                   
                    default: printf("");
                }
    }
}
int main()
{
    int n,k;
    Stack s,s1=NULL,s2=NULL;
    char ch[30];
    printf("1. Doi co so thap phan sang nhi phan...\n");
    printf("Nhap so can doi (n>0):");scanf("%d",&n);
    printf("%d=(",n);
    doi10to2(n);
    printf(")");
    createS(&s);
    printf("\n2. Trung binh cong phan tu chan trong Stack...\n");
    average(s);
    printf("\n3. Lay phan tu o vi tri thu may:");scanf("%d",&n);
    printf("Lay phan tu thu %d ha? Uk thi lay!\n",n);
    pullS(&s,n);
    printf("\n4. So sanh 2 Stack:");
    sosanh(s1,s2);
    printf("\n5. Doi co so nhi phan sang thap phan:");fflush(stdin);gets(ch);
    printf("(%s)=%d",ch,int(doics2to10(ch)));
    printf("\n6. Doi co so thap phan sang he bat ki (2,8,16):");scanf("%d",&n);
    printf("Nhap so can doi:");scanf("%d",&k);
    switch(n)
    {
      case 2:
            {
                printf("Xac nhan doi %d tu he %d sang he %d...Done\n",k,10,n);
                printf("%d=(",k);
                doi10to2(k);
                printf(")");
                break;
            }
      case 8:
            {
                printf("Xac nhan doi %d tu he %d sang he %d...Done\n",k,10,n);
                printf("%d=(",k);
                doi10to8(k);
                printf(")");
                break;
            }
      case 10:
            {
                printf("Xac nhan doi %d tu he %d sang he %d...Done\n",k,10,n);
                printf("%d=(%d)",k,k);
                break;
            }
      case 16:
            {
                printf("Xac nhan doi %d tu he %d sang he %d...Done\n",k,10,n);
                printf("%d=(",k);
                doi10to16(k);
                printf(")");
                break;
            }
      defaut:
                printf("\nKhong co he dem co so nay!");getch();
    }
    getch();
    return 0;
}


a) Lý thuyết:

1. Tìm kiếm sinh viên có mã được nhập từ bàn phím (tìm sinh viên đầu tiên gặp được)
   Gợi ý:Wordpress Blog
2. Sắp xếp danh sách theo điểm trung bình giảm dần
   Gợi ý:Wordpress Blog
3. Thêm phần tử đầu danh sách (xa NULL nhất)
   

   Code:

   Name changed: "last"->"head"

   Gợi ý:Wordpress Blog
4. Thêm phần tử cuối danh sách (gần NULL nhất)

b) Bài tập về nhà:

1. Viết hàm thống kê in tất cả các sinh viên có tên được nhập vào (không phân biệt chữ hoa chữ thường)
   Gợi ý: sử dụng hàm strstr thuộc thư viện string.h hoặc ctype.h
2. Thêm phần tử x vào vị trí bất kì (sau phần tử nào đó) của danh sách
   Gợi ý:Wordpress Blog