Một số bài tập lớn môn cấu trúc dữ liệu và giải thuật

// Heapsort.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <conio.h>

void thaydoi(int *a,int i,int n)
{ int t,j,key;
 
  key=a[i];
  j=2*i;
  while(j<=n)
  {
    // so sanh hai nhanh con cua nut thu i.
   if(((j+1)<=n)&(a[j]<a[j+1])) j=j+1;
   t=j/2;
   // sap xep tung nhanh.
   if(key>a[j])
   {
     a[t]=key;
     return;
   }
     a[t]=a[j];
     j=j*2;
  }
    a[j/2]=key;
}
main()
{ int tg,i,n,a[100];
   
    printf("\n n="); scanf("%d",&n);
   for(i=1;i<=n;i++)
   {
      printf("\n a[%d]=",i); scanf("%d",&a[i]);
   }
    // tao dong.
   for(i=n/2;i>=1;i--) thaydoi(a,i,n);
   for(i=n-1;i>=1;i--)
   { tg=a[1];
     a[1]=a[i+1];
     a[i+1]=tg;
     thaydoi(a,1,i);
   }
   printf("\n");
    for(i=1;i<=n;i++) printf("%4d",a[i]);
   
   getch();
   return 0;
}

// Chuong tring tinh toan bieu thuc toan hoc ung dung cay nhi phan

#include "StdAfx.h"
#include <conio.h>
#include <malloc.h>
#include <string.h>
#include <math.h>

typedef struct Node
{ char  cToantu;
  char  bt[200];
  double dToanHang;
  struct Node *Left;
  struct Node *Right;
}NODEE;

// Cac ham su dung
void  CreateNode(Node *nNode,char *b1,char *b2);
void  Analyst(Node *nNode);
void  Duyet(Node *Goc);
double Eval(Node *nNode);
void  CopyString(char *cBufffer,char *b,int iBegin, int iEnd);
void  ChuanSau(char *cS);
int    iCheckToanTu(char ch);

/*--------------------------------------------------*/
void  CreateNode(Node *nNode,char *b1,char *b2)
{
      // Nhanh trai
     nNode->Left=(Node*)malloc(sizeof(Node));
     nNode->Left->Left=NULL;
     nNode->Left->Right=NULL;
     strcpy(nNode->Left->bt,b1);
      // Nhanh phai
     nNode->Right=(Node*)malloc(sizeof(Node));
     nNode->Right->Left=NULL;
     nNode->Right->Right=NULL;
     strcpy(nNode->Right->bt,b2);
}
/*--------------------------------------------------*/
void  Analyst(Node *nNode)
{ char  Buffer[200],b1[200],b2[200];
  int    i,j,n,iMoNgoac;
  bool  check=true,bDoiNgoi=false;

  strcpy(Buffer,nNode->bt);
  n=strlen(Buffer);
  i=0;
  j=0;
  iMoNgoac=0;
  while((check==true)&&(i<=n))
  {
    if((Buffer[0]=='-')&&(i==0)) i++;
   
   //Khi duyet bo qua phan bieu thuc trong ngoac
   if(Buffer[i]=='(')
   { 
      iMoNgoac++;
      i++;
      while(iMoNgoac!=0)
      {  if(Buffer[i]=='(') iMoNgoac++;
         if(Buffer[i]==')') iMoNgoac--;
         i++;
      }
      
      if((i==n)&&(Buffer[i-1]==')')&&(Buffer[0]=='('))
      {
        ChuanSau(Buffer);
        i=0;
      }
   }

   //Phan tich bieu thuc thanh
   //Tong cac bieu thuc, roi thanh tich cac bieu thuc
    if(iCheckToanTu(Buffer[i])!=1)
   {
     if((Buffer[i]=='*')||(Buffer[i]=='/')) j=i;   
     i++;
     continue;
    }
   if(iCheckToanTu(Buffer[i])==1)
   { 
     j=i;
     check=false;
     if(Buffer[i]=='-')
     {
      if(Buffer[i+1]=='(')
      {
        bDoiNgoi=true;
          CopyString(Buffer,b1,0,i-1);
         CopyString(Buffer,b2,i+1,n);
        }
      else
      {
        CopyString(Buffer,b1,0,i-1);
         CopyString(Buffer,b2,i,n);
      }
     }
     else
     {
          CopyString(Buffer,b1,0,i-1);
         CopyString(Buffer,b2,i+1,n);
     }
   }
 }
 
  // Bieu thuc khong co dau cong.
if((j==0)&&(i==n+1))
{ 
    nNode->dToanHang=atof(Buffer);
} 
if(j!=0)
{
  // Phan tich bieu thuc thanh tich hoac thuong hai bieu thuc.
  if((i==n+1)&&(check==true))
  { 
 
     nNode->cToantu=Buffer[j];
     CopyString(Buffer,b1,0,j-1);
     CopyString(Buffer,b2,j+1,n);
   
     // Tao hai nhanh trai phai
     CreateNode(nNode,b1,b2);
     
     Analyst(nNode->Left);
     Analyst(nNode->Right);
  }
  // Phan tich thanh tong hoac hieu hai bieu thuc
  if(check==false)
  { 
     if(bDoiNgoi==true) nNode->cToantu='-';
     else nNode->cToantu='+';
    
      // Tao hai nhanh trai phai
     CreateNode(nNode,b1,b2);
     
     Analyst(nNode->Left);
     Analyst(nNode->Right);
  }
}

}

/*--------------------------------------------------*/
void Duyet(Node *Goc)
{
   if(Goc!=NULL)
   {
      if((Goc->Left!=NULL)&&(Goc->Right!=NULL)) printf("\n%c",Goc->cToantu);
      else printf("\n%f",Goc->dToanHang);
      Duyet(Goc->Left);
      Duyet(Goc->Right);
   }
}
/*--------------------------------------------------*/
double Eval(Node *nNode)
{ double var;
  if((nNode->Left==NULL)&&(nNode->Right==NULL))
  {
      var=nNode->dToanHang;
     free(nNode);
     return var;
  }
  else
  {
     if(nNode->cToantu=='+') nNode->dToanHang=Eval(nNode->Left)+Eval(nNode->Right);
     if(nNode->cToantu=='-') nNode->dToanHang=Eval(nNode->Left)-Eval(nNode->Right);
     if(nNode->cToantu=='*') nNode->dToanHang=Eval(nNode->Left)*Eval(nNode->Right);
     if(nNode->cToantu=='/') nNode->dToanHang=Eval(nNode->Left)/Eval(nNode->Right);
     return nNode->dToanHang;
  }
}
/*--------------------------------------------------*/
int iCheckToanTu(char ch)
{
  if((ch=='+')||(ch=='-')) return 1;
  else if((ch=='*')||(ch=='/')) return 2;
  else return 0;
}

/*---------------------------------------------------*/
void CopyString(char *cBufffer,char *b,int iBegin, int iEnd)
{
   int i,j;
   i=0;
   j=0;
   for(i=iBegin;i<=iEnd;i++)
   {
      b[j]=cBufffer[i];
      j++;
   }
       b[j]='\0';
}
/*---------------------------------------------------*/
void ChuanSau(char *cS)
{
   char cS2[200];
   int  i,j,n;
   
   n=strlen(cS);
   j=0;
   for(i=1;i<n-1;i++)
   {
      cS2[j]=cS[i];
     j++;
   }
     cS2[j]='\0';
   strcpy(cS,cS2);
}
/*---------------------------------------------------*/
void main()
{ char bt[200];
  Node *Goc; 
  double var;

  printf("\n--------------------------------------------------------------------------------");
  printf("\n      Phan mem mo ta thuat toan tinh bieu thuc toan hoc bang cay nhi phan");
  printf("\n          Le Minh Nghia Lop Cong Nghe Phan Mem K51 Dai Hoc Bach Khoa ");
  printf("\n--------------------------------------------------------------------------------");
 
  printf("\n nhap bieu thuc:");
  gets(bt);
  fflush(stdin);

  Goc=(Node*)malloc(sizeof(Node));
  strcpy(Goc->bt,bt);
  Goc->Left=NULL;
  Goc->Right=NULL;
 
  Analyst(Goc);
  printf("\n Cay nhi phan:");
  Duyet(Goc);
 
  printf("\n Ket qua");
  var=Eval(Goc);
  printf("\n%f",var);
  getch();
}

// Cay Tu Dien.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <conio.h>
#include <malloc.h>
#include <string.h>

typedef struct Node
{
   char label;
   char meaning[100];
   struct Node *left;
   struct Node *right;
}NODE;

// Cac ham su dung.
Node* CreateNode(char Label);
void InsertNode(Node *Root, char *Word, char *Meaning);
void WalkTree(Node *Root);
bool SearchingWord(Node *Root, char *Word);

/*-----------------------------------------------------------*/

Node *CreateNode(char Label)
{
   Node *p;
   
   p=(Node*)malloc(sizeof(Node));
   p->left=NULL;
   p->right=NULL;
   p->label=Label;
   strcpy(p->meaning,"Khong co nghia!");
   return p;
}

/*------------------------------------------------------------*/

void InsertNode(Node *Root, char *Word, char *Meaning)
{
   int i, n;
   Node *p=Root;
   
   n=strlen(Word);
   i=0;
   
   while(i<n)
   {
      while((p->right!=NULL)&&(p->label!=Word[i]))
         p=p->right;
      if(p->label==Word[i])
      {
         if(i==n-1)
         {
            strcpy(p->meaning,Meaning);
            return;
         }
         
         i++;

         if(p->left==NULL)
         {
            while(i<=n-1)
            {
               p->left=CreateNode(Word[i]);
               i++;
               p=p->left;
            }
            strcpy(p->meaning,Meaning);
            return;
         }
         if(p->left!=NULL)
            p=p->left;
      }
      if(p->label!=Word[i])
      {
         p->right=CreateNode(Word[i]);
         p=p->right;
         i++;
         while(i<=n-1)
         {
            p->left=CreateNode(Word[i]);
            i++;
            p=p->left;
         }
         strcpy(p->meaning,Meaning);
           return;   
      }
   }
}

/*------------------------------------------------------------*/

void WalkTree(Node *Root)
{
   if(Root->left!=NULL)
      WalkTree(Root->left);
   
   printf("\n %c:%s",Root->label,Root->meaning);

   if(Root->right!=NULL)
      WalkTree(Root->right);
}

/*-------------------------------------------------------------*/

bool SearchingWord(Node *Root, char *Word)
{
   Node *p=Root;
   int i=0;
   int n=strlen(Word);

   while(i<=n-1)
   {
      while((p->right!=NULL)&&(p->label!=Word[i]))
         p=p->right;
      if(p->label==Word[i])
      {
         if(i==n-1)
         {
            printf("\n %s",p->meaning);
            return true;
         }
         else
         {
            i++;
            if(p->left==NULL)
            {
               printf("\n %c:Khong co nghia",p->label);
               return false;
            }
            else
            {
               p=p->left;
               continue;
            }
         }
      }
      if(p->label!=Word[i])
      {
         printf("\nKhong co nghia",p->label);
         return false;
      }
   }
   return true;
}

/*-------------------------------------------------------------*/

void main()
{
   Node *Root=NULL;
   char  Word[100];
   if(Root==NULL)
   {
      Root=(Node*)malloc(sizeof(Node));
      Root->label='A';
      strcpy(Root->meaning,"Khong co nghia");
      Root->left=NULL;
      Root->right=NULL;
   }
   // Khoi tao mot vai tu
   InsertNode(Root,"Hello","Xin Chao");
   InsertNode(Root,"Good","tot");
   InsertNode(Root,"Bad","xau");
   InsertNode(Root,"Bear","Con Gau");
   InsertNode(Root,"Hell","Dia Nguc");
   InsertNode(Root,"Dog","Con Cho");
   InsertNode(Root,"Harm","Lam Hai");
   InsertNode(Root,"Good Bye","Tam biet");
   InsertNode(Root,"Love","Yeu thuong");
   
   WalkTree(Root);
   
   printf("\n");
   printf("\n Searching\n");
   printf("Nhap tu muon tra:");
   gets(Word);
   SearchingWord(Root,Word);

   getch();
   return ;
}

#include <stdio.h>
#include <stdlib.h>
#include
<conio.h>
struct dnode
{
int data;
struct dnode *left,
*right;
};
struct dnode *insert(struct dnode *p, struct dnode **q, int
n)
{
struct dnode *temp;
if(p==NULL)
{
p=(struct dnode
*)malloc(sizeof(struct dnode));
if(p==NULL)
{
printf("Khong du bo
nho\n");
exit(0);
}
p->data = n;
p-> left = p->right
=NULL;
*q =p;
}
else
{
temp = (struct dnode
*)malloc(sizeof(struct dnode));
if(temp == NULL)
{
printf("Khong du bo
nho\n");
exit(0);
}
temp->data = n;
temp->left =
(*q);
temp->right = NULL;
(*q)->right = temp;
(*q) =
temp;
}
return (p);
}
void printfor( struct dnode *p
)
{
printf("Duyen theo chieu tien:\n");
while (p!=
NULL)
{
printf("%d\t",p-> data);
p = p->right;
}
}
void
printrev( struct dnode *p )
{
printf("Duyet theo chieu
nguoc:\n");
while (p!= NULL)
{
printf("%d\t",p->data);
p =
p->left;
}
}
void main()
{
int n;
int x;
struct dnode
*start = NULL ;
struct dnode *end = NULL;
printf("Nhap so phan tu cho danh
sach \n");
scanf("%d",&n);
while ( n-- > 0 )
{
printf( "Nhap
gia tri cho phan tu\n");
scanf("%d",&x);
start = insert ( start,
&end,x );
}
printf("Danh sach da tao\n");
printfor ( start
);
printrev(end);
getch();
}

#include <stdio.h>
#include <stdlib.h>
#include
<conio.h>
struct node
{
int data;
struct node
*link;
};
struct node *insert(struct node *p, int n)
{
struct node
*temp;
/* Neu list rong, them node moi */
if(p==NULL)
{
p=(struct
node *)malloc(sizeof(struct node));
/* cap phat o nho moi
*/
if(p==NULL)
{
printf("Khong co bo
nho!\n");
exit(0);
}
p-> data = n;
p-> link = p;
/* Tao
lien ket tro toi chinh no */
}
else
{
temp = p;
/* duyet qua tat
ca cac phan tu cua danh sach, den khi khac p */
while (temp-> link !=
p)
temp = temp-> link;
temp-> link = (struct node
*)malloc(sizeof(struct node));
/* cap phat o nho va gan cac gia tri, lien
ket tuong ung cho node moi*/
if(temp -> link ==
NULL)
{
printf("Thieu bo nho\n");
exit(0);
}
temp = temp->
link;
temp-> data = n;
temp-> link = p;
}
return
(p);
}
void printlist ( struct node *p )
{
struct node
*temp;
temp = p;
printf("Cac phan tu trong danh sach:\n");
if(p!=
NULL)
{
do
{
printf("%d\t",temp->data);
temp=temp->link;
}
while (temp!= p);
}
else
printf("Danh sach rong\n");
}

void
main()
{
int n;
int x;
struct node *start = NULL ;
printf("Nhap
do node can tao \n");
scanf("%d",&n);
while ( n-- > 0
)
{
printf( "Nhap gia tri cho node\n");
scanf("%d",&x);
start =
insert ( start, x );
}
printf("Danh sach da dua vao\n");
printlist (
start );
getch();
}

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

#define TRUE 1
#define
FALSE 0
#define M 10

struct nodes
{
int key;
struct nodes
*next;
};
typedef struct nodes *NODEPTR;

NODEPTR bucket[M]; // mang
cac con tro chi nut dau cua cac bucket

// Tac vu getnode: cap phat mot
nut cho bang bam
NODEPTR getnode(void)
{
NODEPTR p;
p =
(NODEPTR)malloc(sizeof(struct nodes));
return(p);
}

// Tac vu
freenode: huy nut da cap phat
void freenode(NODEPTR
p)
{
free(p);
}

// Ham bam
int hashfunc(int
key)
{
return(key % M);
}

// Khoi dong cac bucket
void
initbucket()
{
int b;
for(b = 0; b < M; b++)
bucket[b] =
NULL;
}

// Tac vu emptybucket: kiem tra bucket b co rong khong
int
emptybucket(int b)
{
return(bucket[b] == NULL ? TRUE :
FALSE);
}

// Tac vu empty: kiem tra bang bam co rong khong
int
empty()
{
int b;
for(b = 0; b < M; b++)
if(bucket[b] !=
NULL)
return(FALSE);
return(TRUE);
}

// Tac vu push: them nut
moi vao dau bucket b
void push(int b, int x)
{
NODEPTR p;
p =
getnode();
p->key = x;
p->next = bucket[b];
bucket[b] =
p;
}

// Tac vu pop: xoa nut o dau bucket b
int pop(int
b)
{
NODEPTR p;
int k;
if(emptybucket(b))
{
printf("\nBucket
%d rong, khong xoa nut duoc", b);
return(0);
}
p = bucket[b]; // nut
can xoa la nut dau Bucket b
k = p->key; // k la noi dung nut bi
xoa
bucket[b] = p->next;
freenode(p);
return(k);
}

// Tac
vu insafter: them nut moi vao bucket sau nut p
void insafter(NODEPTR p, int
k)
{
NODEPTR q;
if(p == NULL)
printf("khong them nut moi
duoc");
else
{
q = getnode();
q->key = k;
q->next =
p->next;
p->next = q;
}
}

// Tac vu delafter: xoa nut
trong bucket sau nut p
int delafter(NODEPTR p)
{
NODEPTR q;
int
k;

if(p == NULL || p->next == NULL)
{
printf("khong xoa nut
duoc");
return(0);
}
q = p->next; // q chi nut can xoa
k =
q->key; // k la noi dung nut bi xoa
p->next =
q->next;
freenode(q);
return(k);
}

// Tac vu place: tac vu
nay chi su dung khi them nut vao bucket da co thu tu
void place(int b, int
k)
{
NODEPTR p, q; // q la nut truoc, p la nut sau
q = NULL;
for(p =
bucket[b]; p != NULL && k > p->key; p = p->next)
q =
p;
if(q == NULL) // them nut vao dau bucket
push(b, k);
else // them
nut vao sau nut q
insafter(q, k);
}

// Tac vu insert: them nut co
khoa k vao bang bam
void insert(int k)
{
int b;
b =
hashfunc(k);
place(b, k); // tac vu place cua danh sach lien
ket
}

// Tac vu remove: xoa nut co khoa k trong bang bam
void
remove(int k)
{
int b;
NODEPTR p, q;
b = hashfunc(k);
p =
bucket[b];
q = p;
while(p != NULL && p->key != k)
{
q =
p;
p = p->next;
}
if(p == NULL)
printf("\n Khong co nut co khoa
%d", k);
else
if(p == bucket[b])
pop(b); // tac vu pop cua danh sach
lien ket
else
delafter(q); // tac vu delafter cua danh sach lien
ket
}

// Tac vu clearbucket: xoa tat ca cac nut trong bucket b
void
clearbucket(int b)
{
NODEPTR p, q; // q la nut truoc, p la nut sau
q =
NULL;
p = bucket[b];
while(p != NULL)
{
q = p;
p =
p->next;
freenode(q);
}
bucket[b] = NULL; // khoi dong lai bucket
b
}

// Tac vu clear: xoa tat ca cac nut trong bang bam
void
clear()
{
int b;
for(b = 0; b < M;
b++)
clearbucket(b);
}

// Tac vu traversebucket: duyet bucket
b
void traversebucket(int b)
{
NODEPTR p;
p = bucket[b];
while(p
!= NULL)
{
printf("%3d ", p->key);
p =
p->next;
}
}

// Tac vu traverse: duyet bang bam
void
traverse()
{
int b;
for(b = 0; b < M; b++)
{
printf("\nBucket
%d:", b);
traversebucket(b);
}
}

/* Tac vu search: tim kiem mot
nut trong bang bam, neu khong tim thay ham nay
tra ve tri -1, neu tim thay
ham nay tra ve bucket co chua nut */
int search(int k)
{
NODEPTR
p;
int b;
b = hashfunc(k);
p = bucket[b];
while(k > p->key
&& p != NULL)
p = p->next;
if(p == NULL || k != p->key) //
khong tim thay
return(-1);
else // tim thay
return(b);
}

//
chuong trinh chinh
void main()
{
int b, key, i, n, chucnang;
char
c;

clrscr();

// khoi dong M bucket cua bang
bam
initbucket();

do
{
// menu chinh cua chuong
trinh
printf("\n\nCac chuc nang cua chuong trinh:\n");
printf(" 1: Them
mot nut vao bang bam\n");
printf(" 2: Them ngau nhien nhieu nut vao bang
bam\n");
printf(" 3: Xoa nut trong bang bam\n");
printf(" 4: Xoa toan bo
bang bam\n");
printf(" 5: Duyet bang bam\n");
printf(" 6: Tim kiem tren
bang bam\n");
printf(" 0: Ket thuc chuong trinh\n");
printf("\nChuc nang
ban chon: ");
scanf("%d", &chucnang);
switch(chucnang)
{
case
1:
{
printf("\nTHEM MOT NUT VAO BANG BAM");
printf("\n Khoa cua nut
moi: ");
scanf("%d", &key);
insert(key);
break;
}
case
2:
{
printf("\nTHEM NGAU NHIEN NHIEU NUT VAO BANG BAM");
printf("\n Ban
muon them bao nhieu nut: ");
scanf("%d", &n);
for(i = 0; i < n;
i++)
{
key = random(100);
insert(key);
}
break;
}
case
3:
{
printf("\nXOA NUT TREN BANG BAM");
printf("\n Khoa cua nut can
xoa: ");
scanf("%d", &key);
remove(key);
break;
}
case
4:
{
printf("\nXOA TOAN BO BANG BAM");
printf("\n Ban co chac khong
(c/k): ");
c = getche();
if(c == 'c' || c ==
'C')
clear();
break;
}
case 5:
{
printf("\nDUYET BANG
BAM");
traverse();
break;
}
case 6:
{
printf("\nTIM KIEM TREN
BANG BAM");
printf("\n Khoa can tim: ");
scanf("%d", &key);
b =
search(key);
if(b == -1)
printf(" Khong thay");
else
printf(" Tim
thay trong bucket %d", b);
break;
}
}
} while(chucnang !=
0);

// Xoa tat ca cac nut tren bang bam
clear();
}

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

#define MAXLIST 200
#define TRUE 1
#define FALSE
0

int nodes[MAXLIST];

void mergesort(int nodes[], int
n)
{
int i, j, k, low1, up1, low2, up2, size;
int
dstam[MAXLIST];
size = 1;
while(size < n)
{
low1 = 0;
k =
0;
while(low1+size < n)
{
low2 = low1+size;
up1 = low2-1;
up2
= (low2+size-1 < n) ? low2+size-1 : n-1;
for(i = low1, j = low2; i <=
up1 && j <= up2; k++)
if(nodes[i] <= nodes[j])
dstam[k] =
nodes[i++];
else
dstam[k] = nodes[j++];
for(; i <= up1;
k++)
dstam[k] = nodes[i++];
for(; j <= up2; k++)
dstam[k] =
nodes[j++];
low1 = up2+1;
}
for(i = low1; k < n; i++)
dstam[k++]
= nodes[i];
for(i = 0; i < n; i++)
nodes[i] = dstam[i];
size *=
2;
}
}

// Chuong trinh chinh
void main()
{
int
chucnang;
char c;

clrscr();

do
{
// menu chinh cua chuong
trinh
printf("\n\n\tMERGE SORT");
printf("\n\nCac chuc nang cua chuong
trinh:\n");
printf(" 1: Tao danh sach voi %d so ngau nhien\n",
MAXLIST);
printf(" 2: Merge Sort\n");
printf(" 3: Duyet danh
sach\n");
printf(" 0: Ket thuc chuong trinh\n");
printf("Chuc nang ban
chon: ");
scanf("%d", &chucnang);
switch(chucnang)
{
case
1:
{
for(int i = 0; i < MAXLIST; i++)
nodes[i] =
random(1000);
printf("\nDa tao xong danh sach voi %d so ngau nhien",
MAXLIST);
break;
}
case 2:
{
mergesort(nodes,
MAXLIST);
printf("\nDa sap xep xong danh sach theo giai thuat Merge
Sort");
break;
}
case 3:
{
printf("\nDUYET DANH
SACH:\n");
for(int i = 0; i < MAXLIST; i++)
printf("%4d",
nodes[i]);
break;
}
}
} while(chucnang != 0);
}

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

#define MAXLIST 200
#define TRUE 1
#define FALSE
0

int nodes[MAXLIST];

void heapsort(int nodes[], int
n)
{
int k, x, s, f, ivalue;

// chuyen danh sach nodes[] thanh
heap
for(k = 1; k < n; k++)
{
x = nodes[k]; // Nut can them vao
heap

// tac vu insert(nodes[], k, x)
s = k; // s la nut con
f =
(s-1)/2; // f la nut cha
while(s > 0 && nodes[f] <
x)
{
nodes[s] = nodes[f]; // keo nut < x xuong mot muc
s = f;
f =
(s-1)/2;
}
nodes[s] = x; // dien nut x vao vi tri phu hop
}

//
lan luot xoa nodes[0] tren heap, copy no ve vi tri thich hop tren ds
for(k =
n-1; k > 0; k--)
{
// tac vu removeroot(nodes[], k+1)
ivalue =
nodes[k]; // ivalue la nut hien tai o vi tri k
nodes[k] = nodes[0]; // chuyen
nut goc xuong vi tri k

f = 0; // f la nut cha, s la nut con lon hon
//
s = largeson(0, k-1)
if(k == 1)
s = -1;
else
s = 1;
if(k > 2
&& nodes[2] > nodes[1])
s = 2;
while(s >= 0 &&
ivalue < nodes[s])
{
nodes[f] = nodes[s]; // doi nut con lon hon len 1
muc
f = s;

// s = largeson(f, k-1)
s = 2*f+1;
if(s+1 <= k-1
&& nodes[s] < nodes[s+1])
s = s+1;
if(s > k-1)
s =
-1;
}
nodes[f] = ivalue;
}
}

// Chuong trinh chinh
void
main()
{
int i, chucnang;
char c;

clrscr();

do
{
//
menu chinh cua chuong trinh
printf("\n\n\tHEAPSORT");
printf("\n\nCac chuc
nang cua chuong trinh:\n");
printf(" 1: Tao danh sach voi %d so ngau
nhien\n", MAXLIST);
printf(" 2: Heap Sort\n");
printf(" 3: Duyet danh
sach\n");
printf(" 0: Ket thuc chuong trinh\n");
printf("Chuc nang ban
chon: ");
scanf("%d", &chucnang);
switch(chucnang)
{
case
1:
{
for(i = 0; i < MAXLIST; i++)
nodes[i] =
random(1000);
printf("\nDa tao xong danh sach voi %d so ngau nhien",
MAXLIST);
break;
}
case 2:
{
heapsort(nodes,
MAXLIST);
printf("\nDa sap xep xong danh sach theo giai thuat Heap
Sort");
break;
}
case 3:
{
printf("\nDUYET DANH
SACH:\n");
for(i = 0; i < MAXLIST; i++)
printf("%4d",
nodes[i]);
break;
}
}
} while(chucnang != 0);
}

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

#define MAXLIST 20000
#define TRUE 1
#define FALSE
0

// Khai bao danh sach ke chua cac nut can sap xep
int
nodes[MAXLIST];

void partition(int nodes[], int low, int up, int
*pivot)
{
int nuttruc, l, u, temp;
nuttruc = nodes[low]; // Chon phan
tu dau lam truc
l = low;
u = up;
while(l < u)
{
// quyet
len
while(nodes[l] <= nuttruc && l < up)
l++;

//
quyet xuong
while(nodes[u] > nuttruc)
u--;

if(l <
u)
{
// Doi cho hai phan tu tai hai vi tri down va up
temp =
nodes[l];
nodes[l] = nodes[u];
nodes[u] = temp;
}
}
// Doi cho
phan tu truc va phan tu tai vi tri up
nodes[low] = nodes[u];
nodes[u] =
nuttruc;
*pivot = u;
}

void quicksort(int nodes[], int low, int
up)
{
int pivot;
if(low >= up) // dieu kien
dung
return;
if(low < up) // buoc de qui
{
partition(nodes, low,
up, &pivot);
quicksort(nodes, low, pivot-1);
quicksort(nodes, pivot+1,
up);
}
}

// Chuong trinh chinh
void main()
{
int
chucnang;
char c;

clrscr();

do
{
// menu chinh cua chuong
trinh
printf("\n\n\tQUICKSORT");
printf("\n\nCac chuc nang cua chuong
trinh:\n");
printf(" 1: Tao danh sach voi %d so ngau nhien\n",
MAXLIST);
printf(" 2: Quick Sort\n");
printf(" 3: Duyet danh
sach\n");
printf(" 0: Ket thuc chuong trinh\n");
printf("Chuc nang ban
chon: ");
scanf("%d", &chucnang);
switch(chucnang)
{
case
1:
{
for(int i = 0; i < MAXLIST; i++)
nodes[i] =
random(1000);
printf("\nDa tao xong danh sach voi %d so ngau nhien",
MAXLIST);
break;
}
case 2:
{
quicksort(nodes, 0,
MAXLIST-1);
printf("\nDa sap xep xong danh sach theo giai thuat Quick
Sort");
break;
}
case 3:
{
printf("\nDUYET DANH
SACH:\n");
for(int i = 0; i < MAXLIST; i++)
printf("%4d",
nodes[i]);
break;
}
}
} while(chucnang != 0);
}

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

#define TRUE 1
#define FALSE 0
#define NUMNODES
500

struct nodetype
{
int info;
int left;
int
right;
};
struct nodetype nodes[NUMNODES];

int avail; // avail duoc
khai bao la bien toan cuc

// Tac vu getnode: cap phat mot phan tu cua
mang cho cay nhi phan
int getnode(void)
{
int p;
if(avail == -1) //
het tap nut danh san
printf("Het tap nut danh san, khong cap phat
duoc\n");

// cap phat nut avail trong tap nut danh san, avail chi nut cap
phat tiep
else
{
p = avail;
avail =
nodes[avail].left;
return(p);
}
}

// Tac vu freenode: huy phan
tu da cap phat
void freenode(int p)
{
// chen nut bi huy vao dau tap
nut danh san
nodes[p].left = avail;
avail = p;
}

// Tac vu
initialize: khoi dong cay nhi phan
void initialize(int *ptree)
{
*ptree
= -1;
}

// Tac vu empty: kiem tra cay nhi phan co bi rong khong
int
empty(int *ptree)
{
return(*ptree == -1 ? TRUE : FALSE);
}

/*
Tac vu makenode: tao mot nut (nut la) cho cay nhi phan, noi dung nut nay
la x
*/
int makenode(int x)
{
int p;
p = getnode();
nodes[p].info =
x;
nodes[p].left = -1;
nodes[p].right = -1;
return(p);
}

//
Tac vu setleft: tao nut co khoa x la nut con ben trai cua nut p
void
setleft(int p, int x)
{
if(p == -1)
printf("Nut p khong hien
huu\n");
else
if(nodes[p].left != -1)
printf("Nut p da co nut con ben
trai\n");
else
nodes[p].left = makenode(x);
}

// Tac vu
setright: tao nut co khoa x la nut con ben phai cua nut p
void setright(int
p, int x)
{
if(p == -1)
printf("Nut p khong hien
huu\n");
else
if(nodes[p].right != -1)
printf("Nut p da co nut con ben
phai\n");
else
nodes[p].right = makenode(x);
}

// Tac vu
delleft: xoa nut con ben trai (nut la) cua nut p
int delleft(int
p)
{
int q;
int x;
if(p == -1)
printf("Nut p khong hien
huu\n");
else
{
q = nodes[p].left;
x = nodes[q].info;
if(q ==
-1)
printf("Nut p khong co nut con ben trai\n");
else
if(nodes[q].left
!= -1 || nodes[q].right != -1)
printf("Nut q khong la nut la, khong xoa nut
duoc\n");
else
{
nodes[p].left =
-1;
freenode(q);
return(x);
}
}
}

// Tac vu delright: xoa
nut con ben phai (nut la) cua nut p
int delright(int p)
{
int q;
int
x;
if(p == -1)
printf("Nut p khong hien huu\n");
else
{
q =
nodes[p].right;
x = nodes[q].info;
if(q == -1)
printf("Nut p khong co
nut con ben phai\n");
else
if(nodes[q].left != -1 || nodes[q].right !=
-1)
printf("Nut q khong la nut la, khong xoa nut
duoc\n");
else
{
nodes[p].right =
-1;
freenode(q);
return(x);
}
}
}

// Tac vu pretrav: duyet
cay theo thu tu truoc (NLR)
void pretrav(int proot)
{
if(proot !=
-1)
{
printf("%d ",
nodes[proot].info);
pretrav(nodes[proot].left);
pretrav(nodes[proot].right);
}
}

//
Tac vu intrav: duyet cay theo thu tu giua (LNR)
void intrav(int
proot)
{
if(proot != -1)
{
intrav(nodes[proot].left);
printf("%d
", nodes[proot].info);
intrav(nodes[proot].right);
}
}

// Tac vu
posttrav: duyet cay theo thu tu sau (LRN)
void posttrav(int
proot)
{
if(proot !=
-1)
{
posttrav(nodes[proot].left);
posttrav(nodes[proot].right);
printf("%d
", nodes[proot].info);
}
}

/* Tac vu search: (de qui) tim kiem nut
co noi dung la x tren cay con co nut
goc proot. Neu tim thay thi ham nay se
tra ve con tro chi nut tim thay, neu
khong tim thay thi ham tra ve gia tri -1
*/
int search(int proot, int x)
{
int p;

// dieu kien
dung
if(nodes[proot].info == x)
return(proot);
if(proot ==
-1)
return(-1);

// buoc de qui
p = search(nodes[proot].left,
x);
if(p == -1)
p = search(nodes[proot].right,
x);
return(p);
}

// Tac vu cleartree: xoa cay nhi phan
void
cleartree(int proot)
{
if(proot !=
-1)
{
cleartree(nodes[proot].left);
cleartree(nodes[proot].right);
freenode(proot);
}
}

void
main()
{
int i, noidung, noidung1, chucnang;
char c;
int p;
int
ptree;

clrscr();

// Khoi dong tap nut danh san
avail =
0;
for(i = 0; i < NUMNODES; i++)
nodes[i].left =
i+1;
nodes[NUMNODES-1].left = -1;

initialize(&ptree); // Khoi tao
cay nhi phan

do
{
// menu chinh cua chuong
trinh
printf("\n\n\t\tCAY NHI PHAN (BINARY TREE)");
printf("\n\nCac chuc
nang cua chuong trinh:\n");
printf(" 1: Tao nut goc cua cay nhi
phan\n");
printf(" 2: Them mot nut la ben trai \n");
printf(" 3: Them mot
nut la ben phai \n");
printf(" 4: Xoa mot nut la ben trai\n");
printf(" 5:
Xoa mot nut la ben phai\n");
printf(" 6: Duyet cay theo thu tu truoc
(NLR)\n");
printf(" 7: Duyet cay theo thu tu giua (LNR)\n");
printf(" 8:
Duyet cay theo thu tu sau (LRN)\n");
printf(" 9: Tim kiem\n");
printf("
10: Xoa toan bo cay\n");
printf(" 0: Ket thuc chuong
trinh\n");
printf("Chuc nang ban chon: ");
scanf("%d",
&chucnang);
switch(chucnang)
{
case
1:
{
if(!empty(&ptree))
printf("\nCay nhi phan da co nut
goc");
else
{
printf("\nNoi dung cua nut goc: ");
scanf("%d",
&noidung);
ptree = makenode(noidung);
}
break;
}
case
2:
{
if(empty(&ptree))
printf("\nCay nhi phan dang bi rong, phai
tao nut goc truoc");
else
{
printf("\nNoi dung nut la can them:
");
scanf("%d", &noidung);
p = search(ptree, noidung);
if(p !=
-1)
printf("\nBi trung noi dung, khong them nut
duoc");
else
{
printf("\nNoi dung cua nut cha: ");
scanf("%d",
&noidung1);
p = search(ptree, noidung1);
if(p ==
-1)
printf("\nKhong thay nut cha, khong them nut
duoc");
else
setleft(p, noidung);
}
}
break;
}
case
3:
{
if(empty(&ptree))
printf("\nCay nhi phan dang bi rong, phai
tao nut goc truoc");
else
{
printf("\nNoi dung nut la can them:
");
scanf("%d", &noidung);
p = search(ptree, noidung);
if(p !=
-1)
printf("\nBi trung noi dung, khong them nut
duoc");
else
{
printf("\nNoi dung cua nut cha: ");
scanf("%d",
&noidung1);
p = search(ptree, noidung1);
if(p ==
-1)
printf("\nKhong thay nut cha, khong them nut
duoc");
else
setright(p, noidung);
}
}
break;
}
case
4:
{
printf("\nNoi dung cua nut cha: ");
scanf("%d",
&noidung);
p = search(ptree, noidung);
if(p == -1)
printf("\nKhong
thay nut cha, khong xoa nut
duoc");
else
delleft(p);
break;
}
case 5:
{
printf("\nNoi
dung cua nut cha: ");
scanf("%d", &noidung);
p = search(ptree,
noidung);
if(p == -1)
printf("\nKhong thay nut cha, khong xoa nut
duoc");
else
delright(p);
break;
}
case
6:
{
printf("\nDuyet cay theo thu tu truoc
(NLR):\n");
if(empty(&ptree))
printf("Cay bi
rong");
else
pretrav(ptree);
break;
}
case
7:
{
printf("\nDuyet cay theo thu tu giua
(LNR):\n");
if(empty(&ptree))
printf("Cay bi
rong");
else
intrav(ptree);
break;
}
case
8:
{
printf("\nDuyet cay theo thu tu sau
(LRN):\n");
if(empty(&ptree))
printf("Cay bi
rong");
else
posttrav(ptree);
break;
}
case
9:
{
printf("\nNoi dung can tim: ");
scanf("%d",
&noidung);
if(search(ptree, noidung) != -1)
printf("Tim
thay");
else
printf("Khong tim thay");
break;
}
case
10:
{
printf("\nBan co chac khong (c/k): ");
c = getche();
if(c ==
'c' || c == 'C')
cleartree(ptree);
ptree = -1;
break;
}
}
}
while(chucnang != 0);
cleartree(ptree);
ptree = -1;
}

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

/* Ham binsearch la
mot ham de qui, giup tim giatri tren mang so a[].
Neu ham tra ve tri -1 la
khong tim thay, neu ham tra ve tri khac -1
la tim thay tai vi tri la gia tri
tra ve */
int binsearch(int a[], int dau, int cuoi, int giatri)
{
int
giua;
giua = (dau+cuoi)/2;

// Dieu kien dung
if(dau > cuoi) //
khong tim thay
return(-1);
if(giatri == a[giua]) // tim thay tai vi tri
giua
return(giua);

// Buoc de qui
if(giatri <
a[giua])
return(binsearch(a, dau, giua-1,
giatri));
else
return(binsearch(a, giua+1, cuoi,
giatri));
}

void main()
{
int i, a[10], giatri;
char
c;

clrscr();
printf("\n***Tim kiem nhi phan***\n");
printf("\nHay
nhap 10 so nguyen tu nho den lon: \n");
for(i = 0; i < 10 ;
i++)
scanf("%d", &a[i]);

// in ra man hinh de kiem
tra
printf("\nCac so ban da nhap la: \n");
for(i = 0; i < 10 ;
i++)
printf("[%d]:%d ", i+1, a[i]);

do
{
printf("\n\nNhap so can
tim: ");
scanf("%d", &giatri);
i = binsearch(a, 0, 9, giatri); // i la
vi tri tim thay
if(i == -1)
printf("Khong tim
thay");
else
printf("Tim thay tai vi tri %d", i);
printf("\n\nTim nua
khong? (c/k): ");
c = getche();
} while(c == 'c' || c == 'C');
}

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

#define MAXLIST 200
#define TRUE 1
#define FALSE
0

// Khai bao danh sach ke co toi da MAXLIST so nguyen
int
nodes[MAXLIST];

void bubblesort(int nodes[], int n)
{
int temp, i,
j;
int codoicho = TRUE;

// vong lap kiem soat so lan duyet
for(i =
1; i < n && codoicho == TRUE; i++)
{
codoicho = FALSE;
for(j
= 0; j < n-i; j++)
if(nodes[j] > nodes[j+1])
{
codoicho =
TRUE;
temp = nodes[j];
nodes[j] = nodes[j+1];
nodes[j+1] =
temp;
}
}
}

// Chuong trinh chinh
void main()
{
int
chucnang;
char c;

clrscr();

do
{
// menu chinh cua chuong
trinh
printf("\n\n\tBUBBLE SORT");
printf("\n\nCac chuc nang cua chuong
trinh:\n");
printf(" 1: Tao danh sach voi %d so ngau nhien\n",
MAXLIST);
printf(" 2: Bubble Sort\n");
printf(" 3: Duyet danh
sach\n");
printf(" 0: Ket thuc chuong trinh\n");
printf("Chuc nang ban
chon: ");
scanf("%d", &chucnang);
switch(chucnang)
{
case
1:
{
for(int i = 0; i < MAXLIST; i++)
nodes[i] =
random(1000);
printf("\nDa tao xong danh sach voi %d so ngau nhien",
MAXLIST);
break;
}
case 2:
{
bubblesort(nodes,
MAXLIST);
printf("\nDa sap xep xong danh sach theo giai thuat Bubble
Sort");
break;
}
case 3:
{
printf("\nDUYET DANH
SACH:\n");
for(int i = 0; i < MAXLIST; i++)
printf("%4d",
nodes[i]);
break;
}
}
} while(chucnang != 0);
}