Giáo trình Cấu trúc dữ liệu và giải thuật (Phần 2)

k=k; 
 k=d; 
 } 
 return k; 
} 
//Cong hai da thuc 
dt *tong(dt*a,dt*b) 
{ 
 dt *p,*q,*c,*k; 
 p=a; q=b; c=NULL; 
 while((p!= NULL)&&(q!=NULL)) 
 { 
 if(p->somu==q->somu) 
 { 
 if((p->heso+q->heso)!=0) c=Bosung(c,p->heso+q->heso,p->somu); 
 p=p->link; 
 q=q->link; 
 } 
 else 
 if(p->somu>q->somu) 
 { 
 c=Bosung(c,p->heso,p->somu); 
 p=p->link; 
 } 
 else 
 { 
 c=Bosung(c,q->heso,q->somu); 
 q=q->link; 
 } 
 } 
 if(q==NULL) 
 while(p!=NULL) 
 { 
 c=Bosung(c,p->heso,p->somu); 
 p=p->link; 
 } 
 else 
 while(q!=NULL) 
 { 
 c=Bosung(c,q->heso,q->somu); 
 q=q->link; 
 } 
return c; 
} 
//Tinh hieu hai da thuc 
dt *hieu(dt *a,dt *b) 
{ 
 dt *p,*q,*c,*k; 
 p=a; q=b; c=NULL; 
 while((p!= NULL)&&(q!=NULL)) 
 { 
 if(p->somu==q->somu) 
 { 
 if((p->heso-q->heso)!=0) c=Bosung(c,p->heso-q->heso,p->somu); 
 p=p->link; 
 q=q->link; 
 } 
 else 
 if(p->somu>q->somu) 
 { 
 c=Bosung(c,p->heso,p->somu); 
 p=p->link; 
 } 
 else 
 { 
 c=Bosung(c,-q->heso,q->somu); 
 q=q->link; 
 } 
 } 
 if(q==NULL) 
 while(p!=NULL) 
 { 
 c=Bosung(c,p->heso,p->somu); 
 p=p->link; 
 } 
 else 
 while(q!=NULL) 
 { 
 c=Bosung(c,-q->heso,q->somu); 
 q=q->link; 
 } 
return c; 
} 
dt *tich(dt*a,dt*b) 
{ 
 dt *p,*q,*c,*k; 
 p=a; c=NULL; 
 while(p!= NULL) 
 { 
 q=b; 
 while(q!=NULL) 
 { 
 k=c; 
 while((k!=NULL)&&(k->somu!=p->somu+q->somu)) k=k->link; 
 if(k!=NULL) k->heso=k->heso+p->heso*q->heso; 
 else c=Bosung(c,p->heso*q->heso,p->somu+q->somu); 
 q=q->link; 
 } 
 p=p->link; 
 } 
 return c; 
} 
//Dao ham bac nhat 
dt *Dao_ham(dt*a) 
{ 
 dt *p,*c; 
 p=a; c=NULL; 
 while(p!= NULL) 
 { 
 if(p->somu>0)c=Bosung(c,p->heso*p->somu,p->somu-1); 
 p=p->link; 
 } 
 return c; 
} 
//Nguyen ham 
dt *Nguyen_ham(dt*a) 
{ 
 dt *p,*c; 
 p=a; c=NULL; 
 while(p!= NULL) 
 { 
 c=Bosung(c,p->heso/(p->somu+1),p->somu+1); 
 p=p->link; 
 } 
 return c; 
} 
void main() 
{ 
 dt *a,*b,*c; 
 int chon; 
 float x; 
 do 
 { 
 clrscr(); 
 printf("\n1. Dao ham bac nhat"); 
 printf("\n2. Nguyen ham"); 
 printf("\n3. Tinh gia tri da thuc"); 
 printf("\n4. Tong hai da thuc"); 
 printf("\n5. Hieu hai da thuc"); 
 printf("\n6. Tich hai da thuc"); 
 printf("\n7. Ket thuc chuong trinh"); 
 printf("\nChon chuc nang(1->7):"); 
 scanf("%d",&chon); 
 switch(chon) 
 { 
 case 1: 
 printf("\nNhap da thuc can tinh:"); 
 a=nhap(); 
 b=Dao_ham(a); 
 printf("\nDao ham cua da thuc la:");hienthi(b); 
 getch(); 
 break; 
 case 2: 
 printf("\nNhap da thuc can tinh:"); 
 a=nhap(); 
 b=Nguyen_ham(a); 
 printf("\nNguyen ham cua da thuc la:");hienthi(b); 
 getch(); 
 break; 
 case 3: 
 printf("\nNhap da thuc can tinh:"); 
 a=nhap(); 
 printf("x=");scanf("%f",&x); 
 printf("\nGia tri cua da thuc tai x=%5.2f la:%5.2f",x,Gia_tri(a,x)); 
 getch(); 
 break; 
 case 4: 
 printf("\nNhap da thuc thu nhat:"); 
 a=nhap(); 
 printf("\nNhap da thuc thu hai:"); 
 b=nhap(); 
 c=tong(a,b); 
 printf("Tong hai da thuc la:");hienthi(c); 
 getch(); 
 break; 
 case 5: 
 printf("\nNhap da thuc thu nhat:"); 
 a=nhap(); 
 printf("\nNhap da thuc thu hai"); 
 b=nhap(); 
 c=hieu(a,b); 
 printf("Hieu hai da thuc la:");hienthi(c); 
 getch(); 
 break; 
 case 6: 
 printf("\nNhap da thuc thu nhat:"); 
 a=nhap(); 
 printf("\nNhap da thuc thu hai"); 
 b=nhap(); 
 c=tich(a,b); 
 printf("Tich hai da thuc la:");hienthi(c); 
 getch(); 
 break; 
 case 7:exit(1); 
 } 
 }while (chon!=7); 
} 
3. CÀI ĐẶT ĐA DANH SÁCH BIẺU DIỄN MA TRẬN THƢA 
Chương trình cài đặt cấu trúc đa danh sách biểu diễn ma trận thưa, nhập vào từ 
bàn phím 2 ma trận thưa, tính tích hai ma trận và in ma trận kết quả ra màn hình. 
Chƣơng trình minh hoạ 
#include 
#include 
#include 
struct node 
 { 
 node *left,*up; 
 int v,r,c; 
 }; 
node *arow[10],*acol[10],*brow[10],*bcol[10],*crow[10],*ccol[10]; 
struct mt 
 { 
 int m,n,k; 
 }; 
void input(mt &A) 
 { 
 printf("So hang:");scanf("%d",&A.m); 
 printf("So cot:");scanf("%d",&A.n); 
 printf("So phan tu khac khong:");scanf("%d",&A.k); 
 } 
void createA(mt A) 
 { 
 int i,value,row,col; 
 node *p,*q; 
 for(i=1;i<=A.m;i++) 
 { 
 arow[i]=(node*)calloc(1,sizeof(node)); 
 arow[i]->c=0; 
 arow[i]->left=arow[i]; 
 } 
 for(i=1;i<=A.n;i++) 
 { 
 acol[i]=(node*)calloc(1,sizeof(node)); 
 acol[i]->r=0; 
 acol[i]->up=acol[i]; 
 } 
 for(i=1;i<=A.k;i++) 
 { 
 printf("Gia tri phan tu:");scanf("%d",&value); 
 printf("Chi so hang:");scanf("%d",&row); 
 printf("Chi so cot:");scanf("%d",&col); 
 p=(node*)calloc(1,sizeof(node)); 
 p->v=value; 
 p->r=row; 
 p->c=col; 
 q=arow[p->r]; 
 while(p->cleft)->c) q=q->left; 
 p->left=q->left; 
 q->left=p; 
 q=acol[p->c]; 
 while(p->rup)->r) q=q->up; 
 p->up=q->up; 
 q->up=p; 
 } 
 } 
void createB(mt B) 
 { 
 int i,value,row,col; 
 node *p,*q; 
 for(i=1;i<=B.m;i++) 
 { 
 brow[i]=(node*)calloc(1,sizeof(node)); 
 brow[i]->c=0; 
 brow[i]->left=brow[i]; 
 } 
 for(i=1;i<=B.n;i++) 
 { 
 bcol[i]=(node*)calloc(1,sizeof(node)); 
 bcol[i]->r=0; 
 bcol[i]->up=bcol[i]; 
 } 
 for(i=1;i<=B.k;i++) 
 { 
 printf("Gia tri phan tu:");scanf("%d",&value); 
 printf("Chi so hang:");scanf("%d",&row); 
 printf("Chi so cot:");scanf("%d",&col); 
 p=(node*)calloc(1,sizeof(node)); 
 p->v=value; 
 p->r=row; 
 p->c=col; 
 q=brow[p->r]; 
 while(p->cleft)->c) q=q->left; 
 p->left=q->left; 
 q->left=p; 
 q=bcol[p->c]; 
 while(p->rup)->r) q=q->up; 
 p->up=q->up; 
 q->up=p; 
 } 
 } 
void display(node *q) 
 { 
 node *p; 
 p=q->left; 
 while(p!=q) 
 { 
 printf("%3d cot %d;",p->v,p->c); 
 p=p->left; 
 } 
 } 
void ht(mt A) 
 { 
 int i; 
 for(i=1;i<=A.m;i++) 
 { 
 printf("\nCac phan tu tren hang %d\n",i); 
 display(arow[i]); 
 } 
 } 
void multi(mt A, mt B, mt &C) 
 { 
 node *p,*q,*t; 
 int i,j,result; 
 if(A.n==B.m) 
 { 
 C.m=A.m; 
 C.n=B.n; 
 for(i=1;i<=C.m;i++) 
 { 
 crow[i]=(node*)calloc(1,sizeof(node)); 
 crow[i]->c=0; 
 crow[i]->left=crow[i]; 
 } 
 for(i=1;i<=C.n;i++) 
 { 
 ccol[i]=(node*)calloc(1,sizeof(node)); 
 ccol[i]->r=0; 
 ccol[i]->up=ccol[i]; 
 } 
 for(i=1;i<=A.m;i++) 
 for(j=1;j<=B.n;j++) 
 { 
 p=arow[i]->left; 
 q=bcol[j]->up; 
 result=0; 
 while((p->c!=0)&&(q->r!=0)) 
 if(p->c>q->r) p=p->left; 
 else if(p->cr) q=q->left; 
 else 
 { result+=p->v*q->v; 
 p=p->left; 
 q=q->up; 
 } 
 if(result!=0) 
 { 
 t=(node*)calloc(1,sizeof(node)); 
 t->v=result; 
 t->r=i; 
 t->c=j; 
 t->left=crow[i]->left; 
 t->up=ccol[j]->up; 
 crow[i]->left=t; 
 ccol[j]->up=t; 
 } 
 } 
 } 
 else printf("Hai ma tran khong cung kich thuoc"); 
 } 
void main() 
{ 
mt A,B,C; 
clrscr(); 
printf("\nNhap kich thuoc ma tran A\n"); 
input(A); 
printf("\nNhap gia tri cac phan tu khac khong cua A\n"); 
createA(A); 
printf("\nNhap kich thuoc ma tran B\n"); 
input(B); 
printf("\nNhap gia tri cac phan tu khac khong cua B\n"); 
createB(B); 
multi(A,B,C); 
printf("\nTich hai ma tran\n"); 
ht(C); 
getch(); 
} 
4. CÀI ĐẶT CÂY NHỊ PHÂN TÌM KIẾM 
Chương trình cài đặt cây nhị phân tìm kiếm kiểu móc nối, có các nút chứa 
khoá là các số nguyên nhập từ bàn phím . Chương trình gồm các chức năng sau: 
a) Tạo cây nhị phân. 
b) Duyệt cây nhị phân theo thứ tự trước bằng giải thuật duyệt không đệ qui. 
c) Duyệt cây nhị phân theo thứ tự giữa bằng giải thuật duyệt không đệ qui. 
d) Duyệt cây nhị phân theo thứ tự sau bằng giải thuật duyệt không đệ qui. 
e) Bổ sung nút mới vào cây. 
f) Loại bỏ nút có khoá bằng x cho trước. 
g) Đếm số nút trên cây. 
h) Tìm nút có khoá tương ứng có giá trị lớn nhất trên cây. 
i) Tráo đổi tất cả các nút con trái và con phải trên cây. 
Chƣơng trình minh hoạ 
 #include”stdio.h” 
 #include”conio.h” 
 #include”alloc.h” 
typedef struct tree 
 { 
 int info; 
 tree *lptr,*rptr; 
 }; 
//Tao nut moi co info=x 
tree *taonut(int x) 
 { 
 tree *p; 
 p = (tree*)malloc(sizeof(tree)); 
 p->info = x; 
 p->lptr = p->rptr = NULL; 
 return p; 
 } 
//Bo sung nut co info=x vao cay nhi phan tim kiem 
tree *Bosung(tree*t,int x) 
 { 
 tree *p,*r,*q; 
 r = taonut(x); 
 if(t==NULL) t = r; 
 else 
 { 
 q = t; 
 while(q!=NULL) 
 { 
 if(q->info==x) 
 { 
 printf(“\n nut da ton tai”); 
 return t; 
 } 
 else if(x info) 
 { 
 p = q; 
 q = q->lptr; 
 } 
 else 
 { 
 p = q; 
 q = q->rptr; 
 } 
 } 
 if (x info) p->lptr = r; 
 else p->rptr = r; 
 return t; 
 } 
 } 
//Tao cay nhi phan tim kiem 
tree *taocay() 
 { 
 int x; 
 char ch; 
 tree *t; 
 t = NULL; 
 do 
 { 
 printf(“\nnhap khoa x=”);scanf(“%d”,&x); 
 t = Bosung(t,x); 
 printf(“Continue..? Y/N:”);fflush(stdin); 
 scanf(“%c”,&ch); 
 }while((ch!=‟N‟)&&(ch!=‟n‟)); 
 return t; 
 } 
//Loai bo nut co info=x tren cay nhi phan tim kiem 
tree *Loaibo(tree *t, int x) 
 { 
 tree *p, *q, *s,*r; 
 p = t; 
 while ((p!= NULL) && (p->info!=x)) 
 { 
 r = p; 
 if(xinfo) p = p->lptr; 
 else p = p->rptr; 
 } 
 if (p==NULL) printf(“khong co nut can loai bo”); 
 else 
 { 
 if((p==t)&&(p->lptr==NULL)&&(p->rptr==NULL)) t=NULL; 
 else 
 { 
 while((p->lptr!=NULL)||(p->rptr!=NULL)) 
 { 
 if(p->lptr!=NULL) 
 { 
 q=p->lptr; 
 while(q->rptr!=NULL) 
 { 
 r=q; 
 q=q->rptr; 
 } 
 } 
 else 
 { 
 q=p->rptr; 
 while(q->lptr!=NULL) 
 { 
 r=q; 
 q=q->lptr; 
 } 
 } 
 p->info=q->info; 
 p=q; 
 } 
 free(p); 
 } 
 return t; 
 } 
 } 
void push(tree *s[30],int *top,tree *x) 
 { 
 if(*top < 30) 
 { 
 *top=*top+1; 
 s[*top]=x; 
 } 
 else printf(“\n stack tran”); 
 } 
tree *pop(tree *s[30],int *top) 
 { 
 if(*top<=0) 
 { 
 printf(“\n stack can”); 
 return NULL; 
 } 
 else 
 { 
 *top=*top-1; 
 return(s[*top+1]); 
 } 
 } 
//Duyet cay nhi phan tim kiem theo thu tu giua de qui 
void duyetdq(tree*t) 
 { 
 if(t!=NULL) 
 { 
 duyetdq(t->lptr); 
 printf(“%5d”,t->info); 
 duyetdq(t->rptr); 
 } 
 } 
//Duyet cay nhi phan tim kiem theo thu tu truoc ko de qui 
void duyettruoc(tree *t) 
 { 
 tree *p; 
 tree *s[30]; 
 int top=0; 
 if(t==NULL) printf(“\n cay rong:”); 
 else 
 { 
 push(s,&top,t); 
 while(top>0) 
 { 
 p=pop(s,&top); 
 while(p!=NULL) 
 { 
 printf(“%5d”,p->info); 
 if(p->rptr!=NULL) push(s,&top,p->rptr); 
 p=p->lptr; 
 } 
 } 
 } 
 } 
//Duyet cay nhi phan tim kiem theo thu tu giua khong de qui 
void duyetgiua(tree *t) 
 { 
 tree *p; 
 tree *s[30]; 
 int top=0,tt; 
 if(t==NULL) printf(“\n cay rong:”); 
 else 
 { 
 p=t; 
 do 
 { 
 while(p!=NULL) 
 { 
 push(s,&top,p); 
 p=p->lptr; 
 } 
 if(top>0) 
 { 
 p=pop(s,&top); 
 printf(“%5d”,p->info); 
 p=p->rptr; 
 tt=1; 
 } 
 else tt=0; 
 }while(tt==1); 
 } 
 } 
//Dem so nut la tren cay nhi phan tim kiem 
int demla(tree *t) 
 { 
 tree *p; 
 tree *s[30]; 
 int top=0, d=0; 
 if(t!=NULL) 
 { 
 push(s,&top,t); 
 while(top>0) 
 { 
 p=pop(s,&top); 
 while(p!=NULL) 
 { 
 if(p->lptr==p->rptr) d++; 
 if(p->rptr!=NULL) push(s,&top,p->rptr); 
 p=p->lptr; 
 } 
 } 
 } 
 return d; 
 } 
//Duyet cay nhi phan tim kiem khong de qui theo thu tu sau 
void duyetsau(tree *t) 
{ 
 int i=0,top=0,d[30]; 
 tree *s[30]; 
 tree *p; 
 if(t==NULL) printf(“\n cay rong “); 
 else 
 { 
 p=t; 
 while(1) 
 { 
 while(p!=NULL) 
 { 
 push(s,&top,p); 
 d[top]=1; 
 p=p->lptr; 
 } 
 while(d[top]<0) 
 { 
 p=pop(s,&top); 
 printf(“%3d”,p->info); 
 if(top==0) return ; 
 } 
 p=s[top]->rptr; 
 d[top]=-d[top]; 
 } 
 } 
} 
//Dem so nut tren cay nhi phan tim kiem 
int demnut(tree *t) 
 { 
 if(t==NULL) return 0; 
 else return 1+demnut(t->lptr)+demnut(t->rptr); 
 } 
//Trao doi cay con trai va cay con phai 
void trao(tree *t) 
 { 
 tree *tg; 
 if(t!=NULL) 
 { 
 trao(t->lptr); 
 trao(t->rptr); 
 tg=t->lptr; 
 t->lptr=t->rptr; 
 t->rptr=tg; 
 } 
 } 
 //Tim nut co info lon nhat 
int Max(tree *t) 
 { 
 tree *p; 
 p=t; 
 if(p==NULL) printf(“Cay rong”); 
 else 
 while(p->rptr!=NULL) p=p->rptr; 
 return p->info; 
 } 
void main() 
 { clrscr(); 
 tree *t; 
 int x,chon; 
 do 
 { 
 clrscr(); 
 printf(“1. Tao cay\n”); 
 printf(“2. Duyet cay theo thu tu truoc khong de qui\n”); 
 printf(“3. Duyet cay theo thu tu giua khong de qui\n”); 
 printf(“4. Duyet cay theo thu tu sau khong de qui\n”); 
 printf(“5. Bo sung nut vao cay\n”); 
 printf(“6. Loai bo nut khoi cay\n”); 
 printf(“7. Dem so nut tren cay\n”); 
 printf(“8. Tim nut co gia tri lon nhat tren cay\n”); 
 printf(“9. Trao doi cay con trai va cay con phai\n”); 
 printf(“Chon cong viec(1->9):”);scanf(“%d”,&chon); 
 switch (chon) 
 { 
 case 1: 
 clrscr(); 
 printf(“\nNhap gia tri khoa cho cac nut tren cay”); 
 t=taocay(); 
 break; 
 case 2: 
 clrscr(); 
 printf(“\nCac nut khi duyet cay theo thu tu truoc”); 
 duyettruoc(t); 
 getch(); 
 break; 
 case 3: 
 clrscr(); 
 printf(“\nCac nut khi duyet cay theo thu tu giua”); 
 duyetgiua(t); 
 getch(); 
 break; 
 case 4: 
 clrscr(); 
 printf(“\nCac nut khi duyet cay theo thu tu sau”); 
 duyetsau(t); 
 getch(); 
 break; 
 case 5: 
 clrscr(); 
 printf(“Gia tri khoa cua nut can bo sung x=”); 
 scanf(“%d”,&x); 
 Bosung(t,x); 
 printf(“\nCac nut tren cay sau khi bo sung “); 
 printf(“duoc duyet theo thu tu giua\n”); 
 duyetdq(t); 
 getch(); 
 break; 
 case 6: 
 clrscr(); 
 printf(“Gia tri khoa cua nut can loai bo x=”); 
 scanf(“%d”,&x); 
 Loaibo(t,x); 
 printf(“\nCac nut con lai sau khi loai bo “); 
 printf(“duoc duyet theo thu tu giua\n”); 
 duyetdq(t); 
 getch(); 
 break; 
 case 7: 
 clrscr(); 
 printf(“\nSo nut tren cay:%5d”,demnut(t)); 
 getch(); 
 break; 
 case 8: 
 clrscr(); 
 printf(“\nKhoa lon nhat tren cay:%5d”,Max(t)); 
 getch(); 
 break; 
 case 9: 
 clrscr(); 
 printf(“\nCay sau khi trao doi con “); 
 printf(“traiphai duyet theo thu tu giua\n”); 
 trao(t); 
 duyetdq(t); 
 getch(); 
 break; 
 } 
 }while(chon!=10); 
 } 
tài liệu tham khảo 
[1]. Đỗ Xuân Lôi. Cấu trúc dữ liệu và giải thuật. Nhà xuất bản Thống kê. 2001. 
[2]. Đinh Mạnh Tường. Cấu trúc dữ liệu & giải thuật. Nhà xuất bản Khoa học và 
kỹ thuật. 2003. 
[3]. ROBERT SEDGEWICK. Cẩm nang thuật toán. Nhà xuất bản Khoa học và 
kỹ thuật. 2001. Vol. 1. Vol. 2. 
[4]. LARRY NYHOFF, SANFORD LEEDSTMA. Người dịch Lê Minh Trung. 
Lập trình nâng cao bằng Pascal với các cấu trúc dữ liệu. Nhà xuất bản Đà 
Nẵng 2002.Vol.1. Vol.2.