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;
}*/
