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

 : %4.1f", sv. DiemTB); 
getch(); 
} 
 hàm khởi tạo danh sách rỗng 
void Initialize (listnode *p) 
{ 
*P=NULL; 
} 
 ham tao nut moi 
158 
listnode newnode (ElementType sv) 
{ listnode q; 
q=(listnode)calloc (1,sizeof(struct node)); 
q->info=sv; 
q->link = NULL; 
return (q); 
} 
//ham chen truoc nut dau 
void Insertfirst ( listnode *p, ElementType x) 
{listnode q; q= 
newnode(x); if 
(*p==NULL) 
*p=q; 
else 
{q->link=*p; 
*p=q; 
} 
} 
// ham chen truoc nut cuoi 
void InsertEnd ( listnode *p, ElementType x) 
{ listnode q, m; q= 
newnode(x); if 
(*p==NULL) 
*p=q; 
else 
{m=*p; 
while (m->link != NULL) 
m=m->link; 
m->link=q; 
} 
} 
//ham chen truoc mot nut bat ky 
void InsertBefor ( listnode *p, listnode r, ElementType x) 
{ listnode q, m; 
159 
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; if (*p == 
NULL) 
printf (" DANH SACH RONG"); 
else 
if (r == *p) 
{*p=(*p)->link; 
free(r); 
} 
else 
{m=*p; 
160 
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 
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'); 
} 
161 
//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"); 
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 
162 
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); 
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); 
163 
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); 
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 
164 
{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 
 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 
#include 
#include 
//Đinh nghĩa kiểu phầǹ 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); 
165 
} 
//Đị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 
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; 
166 
while (!Empty(*S)) 
{ 
RemoveNode(S,&x); 
printf("%d",x); 
} 
} 
//Định nghĩa hàm main 
void main() 
{ 
Stack *S; 
ElementType x; 
Initialize (S); 
printf("nhap so he 10:");scanf("%d",&x); 
doiso(S,x); 
inra (S); 
getch(); 
} 
} 
 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]; 
167 
int count; 
}; 
// ham khoi tao danh sach rong 
void initializeList (list *L) 
{ 
L->count=0; 
} 
// 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++; 
} 
} 
168 
// ham tao danh sach 
void NhapSinhVien (SinhVien *p) 
{ float f; char ht[35],ma[10]; 
unsigned char d; unsigned int n; 
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; 
169 
Item sv; 
do 
{ 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--; 
} 
170 
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; Item 
temp; 
for (i=0 ; icount-1; i++) 
171 
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) 
QuickSort(L, i, right); 
} 
//ham QuickSort sap xep theo masv 
void QuickSortMSV(list *L, int left , int right) 
172 
{ 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) 
return (i); 
return (-1); 
} 
/* ham Sequen_Search theo cach 2 int 
Sequen_Search1(list L, char X[]) { int 
i; 
173 
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() 
{ 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"); 
174 
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; 
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"); 
175 
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; 
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 
176 
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); 
} 
177 
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. 
178