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

 { listnode q, m; 
 q= newnode(x); 
 if (*p==NULL) 
 *p=q; 
 else 
 { m=*p; 
 while (m->link != NULL) 
 164 
 m=m->link; 
 m->link=q; 
 } 
 } 
//ham chen truoc mot nut bat ky 
void InsertBefor ( listnode *p, listnode r, ElementType x) 
 { listnode q, m; 
 if (r == *p) 
 Insertfirst(p,x); 
 else 
 { q= newnode(x); 
 m=*p; 
 while (m->link != r) 
 m=m->link; 
 q->link=r; 
 m->link=q; 
 } 
 } 
//ham chen sau mot nut bat ky 
void InsertAfter ( listnode *p, listnode r, ElementType x) 
 { listnode q; 
 if (*p==NULL) 
 printf("Danh sach rong"); 
 else 
 { q= newnode(x); 
 q->link = r->link; 
 r->link = q; 
 } 
 } 
 //ham xoa mot nut r 
void DeleteNode ( listnode *p, listnode r) 
 { listnode m; 
 165 
 if (*p == NULL) 
 printf (" DANH SACH RONG"); 
 else 
 if (r == *p) 
 { *p=(*p)->link; 
 free(r); 
 } 
 else 
 { m=*p; 
 while (m->link != r) 
 m=m->link; 
 m->link=r->link; 
 free(r); 
 } 
 } 
//ham tim nut co gia tri truong info=x 
listnode SearchNode ( listnode p, char x[]) 
 { listnode m; 
 if (p == NULL) 
 printf (" DANH SACH RONG"); 
 else 
 { m=p; 
 while (m !=NULL) 
 if (stricmp(x,m->info.Hten)==0) 
 return (m); 
 else 
 m=m->link; 
 } 
 return (NULL); 
 } 
//ham tao dsnd 
 166 
void CreateList(listnode *p) 
{ char kt; 
 SinhVien sv; 
 do 
 { 
 NhapSinhVien (&sv); 
 InsertEnd(p,sv); 
 printf("ban nhap tiep khong c/k: "); 
 fflush(stdin); kt=getchar(); 
 }while (kt!='k'); 
} 
//ham duyet dsnd 
void Browselist(listnode p) 
{ listnode q; 
 SinhVien sv; 
 q=p; 
 printf("Danh sach noi don:\n"); 
 while (q!=NULL) 
 { 
 sv=q->info; 
 HienSinhVien(sv); 
 q=q->link; 
 } 
 getch(); 
} 
//ham menu 
int menu() 
 { int chon; 
 clrscr(); 
 printf("\n MOT SO THUAT TOAN VE DANH SACH NOI DON\n\n"); 
 printf(" Nhan so tuong ung de chon chuc nang:\n"); 
 167 
 printf(" 1. Khoi tao danh sach \n"); 
 printf(" 2. Nhap cac phan tu cho danh sach\n"); 
 printf(" 3. In cac phan tu cua danh sach\n"); 
 printf(" 4. Tim mot phan tu cua danh sach\n"); 
 printf(" 5. Bo sung mot phan tu vao sau mot phan tu \n"); 
 printf(" 6. Bo sung mot phan tu vao truoc mot phan tu\n"); 
 printf(" 7. Xoa mot phan tu cua mang\n"); 
 printf(" 0. Thoat khoi chuong trinh\n"); 
 printf(" Nhap so tuong ung: "); 
 scanf("%d",&chon); 
 return (chon); 
 } 
//ham chinh main 
 void main() 
 {listnode *p,q; 
 int chon; 
 char ht[30]; 
 char kt; 
 ElementType sv; 
 do 
 { chon=menu(); 
 switch (chon) 
 { 
 case 1: 
 Initialize(p); 
 break; 
 case 2: 
 CreateList(p); 
 break; 
 case 3: 
 printf("\n Cac phan tu co trong danh sach:\n\n") ; 
 Browselist(*p); 
 168 
 getch(); 
 break; 
case 4: 
 printf ("\n Nhap HT can tim: "); 
 fflush(stdin); gets(ht1); 
 q=SearchNode(*p,ht1); 
 if (q!=NULL) 
 printf("\n Tim thay phan tu trong Danh sach"); 
 else 
 printf("khong tim thay phan tu trong danh 
 sach"); 
 getch(); 
 break; 
case 5: 
 printf ("\n Nhap SV moi: "); 
 NhapSinhVien(&sv); 
 printf ("\n Nhap HT de tim vt chen sau: "); 
 fflush(stdin);gets(ht1); 
 q=SearchNode(*p,ht1); 
 if (q==NULL) 
 printf("\n Khong tim thay phan tu trong 
 DS\n"); 
 else 
 { 
//q la con tro chua vi tri nut tim thay o tren 
 InsertAfter(p,q,sv) 
 printf(" Da bo sung phan tu \n"); 
 getch(); 
 } 
 break; 
 case 6: 
 printf ("\n Nhap HT moi: "); NhapSinhVien(&sv); 
 169 
 printf ("\n Nhap HT de tim vt chen truoc: "); 
 fflush(stdin); gets(ht1); 
 q=SearchNode(*p,ht1); 
 if (q==NULL) 
 printf("\n Khong tim thay phan tu trong DS\n"); 
 else 
 { 
 //q la con tro chua vi tri nut tim thay o tren 
 InsertBefor(p,q,sv); 
 printf(" Da bo sung phan tu \n"); 
 } getch(); 
 break; 
 case 7: 
 printf ("\n Nhap ht Sinh vien can xoa: "); fflush(stdin); 
 gets(ht1); 
 q=SearchNode(*p,ht1); 
 if (q==NULL) 
 printf("\n Khong tim thay phan tu can xoa\n"); 
 else 
 { DeleteNode(p,q); 
 printf(" Da xoa phan tu \n"); 
 } getch(); 
 break; 
 default: printf ("\n ban chon sai roi! "); 
 } 
 } while (chon!=0); 
}//ket thuc ham main 
2) Chương trình chuyển đổi một số hệ 10 sang hệ 2. Sử dụng các thao tác 
 của Stack cài đặt bằng danh sách liên kết đơn để viết chương trình 
#include 
 170 
#include 
#include 
 //Đinh nghĩa kiểu phần tử 
typedef int ElementType; 
struct node 
{ ElementType info; 
 struct node* link; 
}; 
typedef struct node* Stacknode; 
typedef struct 
{ 
 Stacknode top; 
} Stack; 
 //Định nghĩa hàm khởi tạo Stack rong 
void Initialize (Stack *S) 
 { 
 S ->top=NULL; 
 }; 
 //Định nghĩa hàm kiểm tra Stack có rỗng không? 
int Empty(Stack S) 
{ 
 return (S.top==NULL); 
} 
 //Định nghĩa hàm đẩy một nút vào Stack 
void GetNode ( Stack *S, ElementType x) 
 { Stacknode q; 
 q=( Stacknode) malloc (sizeof(struct node)); 
 q->info=x; 
 q->link=S->top; 
 S->top=q; 
 } 
 //Định nghĩa hàm lấy một nút khỏi Stack 
 171 
void RemoveNode( Stack *S, ElementType *x) 
{ Stacknode q; 
 if (Empty(*S)) 
 printf("\n Stack rong"); 
 else 
 { q=S->top; 
 *x=q->info; 
 S->top=q->link; 
 free(q); 
 } 
} 
/*Định nghĩa hàm chuển đổi số hệ 10 sang hệ 2 và đưa từng chữ số hệ 2 vào 
Stack*/ 
void doiso(Stack *S, ElementType x) 
{ 
 while (x!=0) 
 { 
 GetNode ( S, x%2); 
 x=x/2; 
 } 
} 
/*Định nghĩa hàm lấy từng chữ số hệ 2 và in ra màn hình*/ 
void inra (Stack *S) 
{ ElementType x; 
 while (!Empty(*S)) 
 { 
 RemoveNode(S,&x); 
 printf("%d",x); 
 } 
} 
 //Định nghĩa hàm main 
void main() 
 172 
{ 
 Stack *S; 
 ElementType x; 
 Initialize (S); 
 printf("nhap so he 10:");scanf("%d",&x); 
 doiso(S,x); 
 inra (S); 
 getch(); 
 } 
} 
3) Chương trình cài đặt các giải thuật sắp xếp và tìm kiếm với danh sách 
 sinh viên được cài đặt bằng mảng 
#include 
#include 
#include 
const int maxlist=100; 
 //đinh nghia ban ghi SinhVien 
struct SinhVien 
{ char masv[10]; 
 char Hten [35]; 
 float LaptrinhCB, KientrucMT, MangMT, DiemTB; 
}; 
typedef SinhVien Item; 
typedef struct list 
{ Item element[maxlist]; 
 int count; 
}; 
 // ham khoi tao danh sach rong 
void initializeList (list *L) 
{ 
 L->count=0; 
 173 
} 
 // ham kiem tra danh sach co rong khong? 
int EmptyList(list L) 
{ 
 return (L.count==0); 
} 
 // ham kiem tra danh sach co day khong? 
int FullList(list L) 
{ 
 return (L.count==maxlist); 
} 
//ham bo sung sinh vien x vao vị tri pos 
void insertElement (list *L, int pos, Item x) 
{ 
 int i; 
 if (FullList (*L)) 
 printf("Danh sach day!"); 
 else 
 if ((pos =maxlist )) 
 printf("\n Vi tri chen khong phu hop"); 
 else 
 { 
 for (i=L->count;i>=pos;i--) 
 L-> element [i+1]= L-> element [i]; 
 L-> element [pos]=x; 
 L->count++; 
 } 
} 
 // ham tao danh sach 
void NhapSinhVien (SinhVien *p) 
 { float f; char ht[35],ma[10]; 
 unsigned char d; unsigned int n; 
 174 
 fflush(stdin); //ham xoa vung dem ban phim 
 printf("\n ma sinh vien: "); 
 gets(ma);strcpy(p->masv,ma); 
 printf("\n Ho ten: "); 
 fflush(stdin);gets(ht);strcpy(p->Hten,ht); 
 //Nhap diem cho sinh viên 
 printf("Diem Lap trinh CB: "); 
 scanf("%f",&f); p->LaptrinhCB=f; 
 printf("Diem Kien truc MT: "); 
 scanf("%f",&f); p->KientrucMT=f; 
 printf("Diem Mang MT: "); 
 scanf("%f",&f); p->MangMT=f; 
 //Tinh diem trung bình 
 p->DiemTB=( p-> LaptrinhCB+ p-> KientrucMT+ p-> MangMT )/3; 
} 
//ham hien thong tin mot ban ghi sinh vien 
void HienSinhVien (SinhVien sv) 
 { 
 printf ("\n Ma sinh vien %10s", sv.masv); 
 printf ("\n Sinh vien %35s", sv.Hten); 
 printf ("\n Diem Lap trinh CB : %4.1f", sv.LaptrinhCB); 
 printf ("\n Diem Kien truc MT : %4.1f", sv.KientrucMT); 
 printf ("\n Diem Mang MT : %4.1f", sv.MangMT); 
 printf ("\n Diem TB : %4.1f", sv. DiemTB); 
 getch(); 
 } 
// ham tao danh sach sinh vien 
void CreateList (list *L) 
{ int i=0; 
 char kt; 
 Item sv; 
 do 
 175 
 { printf("nhap phan tu thu %d:",i+1); 
 NhapSinhVien(&sv); 
 L->element[i]=sv; 
 L->count++;i++; 
 printf("ban nhap tiep khong c/k? "); 
 fflush(stdin);kt=getchar(); 
 } 
 while (kt!='k'); 
} 
//ham in danh sach sinh vien ra man hinh 
void PrintList(list L) 
{ int i; 
 if (EmptyList(L)) 
 { printf("Danh sach rong"); 
 return; 
 } 
 for (i=0; i<L.count;i++) 
 HienSinhVien(L.element[i]); 
 } 
// ham InsertionSort sap xep danh sach theo ho ten 
void InsertionSort (list *L) 
{ int i, j; 
 Item temp; 
 for (i=1 ; icount; i++) 
 { temp=L->element[i]; 
 j = i-1; 
 while ((j>=0) && 
 (stricmp(temp.Hten,L->element[j].Hten)>0)) 
 { 
 L->element[j+1] = L->element[j]; 
 j--; 
 } 
 176 
 L->element[j+1]=temp ; 
 } 
} 
//ham SelectionSort sap xep theo ho ten 
void SelectionSort (list *L) 
{ int i, j, m; 
 Item temp; 
 for (i=0 ; icount-1; i++) 
 { m = i ; 
 for (j=i+1 ; jcount; j++) 
 if (stricmp(L->element[i].Hten,L->element[j].Hten)>0) 
 m=j; 
 temp=L->element[i]; 
 L->element[i]=L->element[m]; 
 L->element[m]=temp ; 
 } 
} 
// ham InterchangeSort sap xep theo ho ten 
void InterchangeSort(list *L) 
{ int i, j; 
 SinhVien temp; 
 for ( i=0; icount-1;i++) 
 for ( j=i+1;jcount ;j++) 
 if (stricmp(L->element[i].Hten,L->element[j].Hten)>0) 
 { temp=L->element[i]; 
 L->element[i]= L->element[j]; 
 L->element[j]=temp ; 
 } 
} 
//ham BubleSort sap xep theo ho ten 
void BubleSort (list *L) 
{ int i, j; 
 177 
 Item temp; 
 for (i=0 ; icount-1; i++) 
 for (j=L->count-1 ; j<=i+1; j--) 
 if (stricmp(L->element[i].Hten,L->element[j].Hten)>0) 
 { temp=L->element[j]; 
 L->element[j]=L->element[j-1]; 
 L->element[j-1]=temp ; 
 } 
} 
// ham QuickSort sap xep theo ho ten 
void QuickSort(list *L, int left , int right) 
{ int i, j; 
 Item key,temp; 
 key= L->element[left]; 
 i = left; j = right; 
 do 
 { while ((stricmp(L->element[i].Hten, key.Hten)<0) && (i <= 
 right)) 
 i++; 
 while ((stricmp(L->element[j].Hten, key.Hten)>0) && (j >=left)) 
 j--; 
 if(i <=j) 
 { 
 temp=L->element[i]; 
 L->element[i]=L->element[j]; 
 L->element[j]=temp; 
 i++ ; j--; 
 } 
 } while(i <= j); 
 if(left<j) 
 QuickSort(L, left, j); 
 if(i<right) 
 178 
 QuickSort(L, i, right); 
} 
//ham QuickSort sap xep theo masv 
void QuickSortMSV(list *L, int left , int right) 
{ int i, j; 
 Item key,temp; 
 key= L->element[left]; 
 i = left; j = right; 
 do 
 { 
 while ((stricmp(L->element[i].masv,key.masv)<0) && (i <= right)) 
 i++; 
 while ((stricmp(L->element[j].masv,key.masv)>0) && (j >=left)) 
 j--; 
 if(i <=j) 
 { 
 temp=L->element[i]; 
 L->element[i]=L->element[j]; 
 L->element[j]=temp; 
 i++ ; j--; 
 } 
 } while(i <= j); 
 if(left<j) 
 QuickSort(L, left, j); 
 if(i<right) 
 QuickSort(L, i, right); 
} 
// ham Sequen-Search tim kiem theo masv 
int Sequen_Search(list L, char X[]) 
{ int i=0; 
 for (i=0; i<L.count; i++) 
 if (stricmp(X,L.element[i].masv)==0) 
 179 
 return (i); 
 return (-1); 
} 
/* ham Sequen_Search theo cach 2 
int Sequen_Search1(list L, char X[]) 
{ int i; 
 strcpy(L.element[L.count].masv,X); 
 while (stricmp(X,L.element[i].masv)!=0) 
 i++; 
 if (i<L.count) 
 return (i); 
 else 
 return (-1); 
}*/ 
//ham BinarySearch tim kiem theo masv 
int BinarySearch (list L, char X[]) 
{ int mid, left=0, right=L.count-1; 
 do 
 { 
 mid=(left+right)/2; 
 if (stricmp(X,L.element[mid].masv)==0) 
 return (mid); 
 else 
 if (stricmp(X,L.element[mid].masv)<0) 
 right=mid-1; 
 else 
 left=mid+1; 
 } while(left<=right); 
 return -1; 
} 
 //ham menu 
int menu() 
 180 
{ int chon; 
 clrscr(); 
 printf("\n MOT SO GIAI TOAN VE SAP XEP VA TIM KIEM\n\n"); 
 printf(" Nhan so tuong ung de chon chuc nang:\n"); 
 printf(" 1. Khoi tao danh sach \n"); 
 printf(" 2. Nhap cac phan tu cho danh sach\n"); 
 printf(" 3. In cac phan tu cua danh sach\n"); 
 printf(" 4. ham InsertionSort sap xep theo ho ten\n"); 
 printf(" 5. ham SelectionSort sap xep theo ho ten\n"); 
 printf(" 6. ham InterchangeSort sap xep theo ho ten\n"); 
 printf(" 7.ham BubleSort sap xep theo ho ten \n"); 
 printf(" 8.ham QuickSort sap xep theo ho ten \n"); 
 printf(" 9 ham Sequen-Search timf kiem theo masv\n"); 
 printf(" 10 ham BinarySearch tim kiem theo masv \n"); 
 printf(" 0. Thoat khoi chuong trinh\n"); 
 printf(" Nhap so tuong ung: "); scanf("%d",&chon); 
 return (chon); 
} 
 //ham chinh main 
 void main() 
 {list *L,*M; 
 int chon,pos, n; 
 char ma[10]; 
 do 
 { chon=menu(); 
 switch (chon) 
 { 
 case 1: 
 initializeList(L); 
 break; 
 case 2: 
 CreateList(L);M=L; 
 181 
 break; 
case 3: 
 printf("\n Cac phan tu co trong danh sach:\n\n") ; 
 PrintList(*L); 
 getch(); 
 break; 
case 4: 
 L=M; 
 InsertionSort (L); 
 printf(" Da sap xep theo ho ten\n"); 
 getch(); 
 break; 
case 5: 
 L=M; 
 SelectionSort (L); 
 printf(" Da sap xep theo ho ten\n"); 
 getch(); 
 break; 
case 6: 
 L=M; 
 InterchangeSort (L); 
 printf(" Da sap xep theo ho ten\n"); 
 getch(); 
 break; 
case 7: 
 L=M; 
 BubleSort (L); 
 printf(" Da sap xep theo ho ten\n"); 
 getch(); 
 break; 
case 8: 
 L=M; 
 182 
 QuickSort (L,0,L->count-1); 
 printf(" Da sap xep theo ho ten\n"); 
 getch(); 
 break; 
 case 9: 
 L=M; 
 printf(" Nhap ma sinh vien can tim: "); 
 fflush(stdin); gets(ma); 
 pos= Sequen_Search(*L,ma); 
 if (pos==-1) 
 printf("khong tim thay masv %s\n", ma); 
 else 
 printf(" Da tim thay masv %s tai vi tri 
 %d\n",ma,pos); 
 getch(); 
 break; 
 case 10: 
 QuickSortMSV(L,0,L->count-1 ); 
 printf(" Nhap ma sinh vien can tim: "); 
 fflush(stdin); gets(ma); 
 pos= BinarySearch (*L,ma); 
 if (pos==-1) 
 printf("khong tim thay masv %s\n", ma); 
 else 
 printf(" Da tim thay masv %s tai vi tri %d\n",ma,pos); 
 getch(); 
 break; 
 default: printf ("\n ban chon sai roi! "); 
 } 
 } while (chon!=0); 
} 
 183 
TÀI LIỆU THAM KHẢO 
 - Giáo trình cấu trúc dữ liệu và giải thuật- Đỗ Xuân Lôi - Nhà xuất bản 
 Giáo dục, 1993 
 - Giáo trình cấu trúc dữ liệu- Trần Hạnh Nhi- Trường đại học Khoa hoc 
 tự nhiên, tp. Hồ Chí Minh, 2003 
 - Cấu Trúc Dữ Liệu Và Thuật Toán - PGS. TS. Hoàng Nghĩa Tý - Xây 
 Dựng, 2002 
 - Bài Tập Nâng Cao Cấu Trúc Dữ Liệu Cài Đặt Bằng C - Gia Việt(Biên 
 dịch), ESAKOV.J , WEISS T,- Nhà xuất bản Thống kê 
 - 455 Bài Tập Cấu Trúc Dữ Liệu - Ứng Dụng Và Cài Đặt Bằng C++ - 
 Minh Trung (Biên dịch), TS. Khuất Hữu Thanh(Biên dịch), Chu Trọng 
 Lương(Tác giả) - Thống kê . 
 - Cẩm Nang Thuật Toán (Tập1,2) - Robert Sedgewick, Trần Đan Thư 
 (Biên dịch), Bùi thị Ngọc Nga (Biên dịch) - Khoa học và kỹ thuật 
 - Giải Một Bài Toán Trên Máy Tính Như Thế Nào - GS. TSKH. Hoàng 
 Kiếm - Giáo dục, 2005. 
 184