Dưới đây là 1 bài về danh sách đặc. Nhập xuất xóa chèn, có thêm 2 hàm chuyển danh sách đặc qua liên kết và ngược lại. 2 thuật toán tìm kiếm bằng đệ quy và không đệ quy. Mã: #include<iostream> #include<conio.h> #include<stdio.h> #include<string.h> #define max 10 using namespace std; typedef struct { char ten[30],masv[10]; int tuoi; float diem; }danhsach; typedef struct node { char masv[10]; node *link; }dslk; typedef struct { char masv[10]; }dsd; void nhap(danhsach sv[], int &n) { cout<<"\nNhap so sinh vien: "; cin>>n;cin.get(); for(int i=0;i<n;i++) { cout<<"\nNhap sv thu: "<<i+1; cout<<"\nNhap ten: "; cin>>sv[i].ten;cin.get(); cout<<"\nNhap masv: "; cin>>sv[i].masv;cin.get(); cout<<"\nNhap tuoi: "; cin>>sv[i].tuoi;cin.get(); cout<<"\nNhap diem: "; cin>>sv[i].diem;cin.get(); } } void xuat(danhsach sv[],int n) { cout<<"\nTen\tMa sv\tTuoi\tDiem\n"; for(int i=0;i<n;i++) { cout<<sv[i].ten<<"\t"<<sv[i].masv<<"\t"<<sv[i].tuoi<<"\t"<<sv[i].diem<<"\n"; } } void chen(danhsach sv[],int &n) { if(n<max) { danhsach tmp[1]; int x; cout<<"\nNhap gia tri can chen"; cout<<"\nNhap ten: "; cin>>tmp[0].ten;cin.get(); cout<<"\nNhap masv: "; cin>>tmp[0].masv;cin.get(); cout<<"\nNhap tuoi: "; cin>>tmp[0].tuoi; cin.get(); cout<<"\nNhap diem: "; cin>>tmp[0].diem; cin.get(); cout<<"\nNhap vi tri can chen: ";//vi tri bat dau tu 0 cin>>x; if(x>=0 && x<=n) { for(int i=x;i<=n;i++) sv[i+1]=sv[i]; n++; sv[x]=tmp[0]; } else cout<<"\nVi tri ko hop le!"; } else cout<<"\nDanh sach day."; } void xoa(danhsach sv[],int &n) { int x; cout<<"\nXoa sinh vien thu: "; cin>>x;cin.get(); if(x>=0 && x<= n) { for(int i=x;i<=n;i++) sv[i]=sv[i+1]; n--; } else cout<<"\nVi tri ko hop le !"; } /*int tknp(int l,int r,danhsach sv[],char x[])//de quy { int loc; if(l>r) loc=0; int m=(l+r)/2; if(strcmp(x,sv[m].masv)<0) loc=tknp(l,m-1,sv,x); if(strcmp(x,sv[m].masv)>0) loc=tknp(m+1,r,sv,x); else loc=m; return loc; }*/ int tknp(danhsach sv[],int n,char x[]) //ko de quy { int l=0, r=n; while(l<=r) { int m=(l+r)/2; if(strcmp(x,sv[m].masv)<0) r=m-1; else if(strcmp(x,sv[m].masv)>0) l=m+1; else return m; }return -1; } int unexchange(dslk **T,dsd d[]) { dslk *P; P=*T; int i=0; while(P!=NULL) { strcpy(d[i].masv,P->masv); i++; P=P->link; } } int exchange(dslk **T,danhsach sv[],int n,char x[]) { dslk *P; P=new dslk; strcpy(P->masv,x); P->link=(*T); (*T)=P; } void indslk(dslk **T) { dslk *P; P=*T; while(P!=NULL) { cout<<P->masv<<"\t"; P=P->link; } } char *tktt(dslk *T,char x[])//de quy { if(T==NULL) return 0; else if(strcmp(T->masv,x)==0) { return T->masv; } else tktt(T->link,x); } /*int tktt(danhsach sv[],int n,char x[])// khong de quy { int i=0; strcpy(sv[n].masv,x); while(strcmp(sv[i].masv,sv[n].masv)!=0) i++; if(i<n) return i; return -1; }*/ main() { dslk *T; T=NULL; danhsach sv[max]; dsd d[max]; int n; nhap(sv,n); //xuat(sv,n); //chen(sv,n); xuat(sv,n); for(int i=0;i<n;i++) exchange(&T,sv,n,sv[i].masv);//chuyen qua ds lk cout<<"\nDanh sach lien ket ma sv: "; indslk(&T); cout<<"\nChuyen danh sach lien ket qua ds dac: "; unexchange(&T,d); for(int k=0;k<n;k++) cout<<d[k].masv<<"\t"; char s[10]; cout<<"\nNhap ma sv can tim kiem: "; cin>>s; cout<<"\nTim thay: "<<tktt(T,s); } Hàm tìm kiếm tuần tự sau chỉ dùng 1 phép so sánh, đơn giản hơn hàm trong silde các bạn đang học. Tư tưởng: dùng giá trị của mảng tại vị trí n làm chốt, giá trị bằng giá trị cần tìm kiếm. nhằm giảm bớt 1 phép so sánh. Mã: /*int tktt(danhsach sv[],int n,char x[])// khong de quy { int i=0; strcpy(sv[n].masv,x); while(strcmp(sv[i].masv,sv[n].masv)!=0) i++; if(i<n) return i; return -1; }*/
