#include "khaiBao.h"

#include

#include

#include

using namespace std;

//Cai dat ham khoi tao danh sach lien ket don.

void khoiTaoDSLKD(DSLKD &dau, DSLKD &cuoi)

{ dau = cuoi = NULL;

}

//Cai dat ham xin nut.

DSLKD xinNut(kieuDL duLieu)

{ DSLKD p = (DSLKD) malloc (sizeof(nut));

if(p==NULL)

{ cout

exit(1);

}

p->duLieu=duLieu;

p->tiep=NULL;

return p;

}

//Cai dat ham them dau.

void themDau(DSLKD &dau, DSLKD &cuoi, DSLKD p)

{ if (dau==NULL)//Danh sach rong.

dau=cuoi=p;

else

{ p->tiep=dau;

dau=p;

}

}

//Cai dat ham them cuoi.

void themCuoi(DSLKD &dau, DSLKD &cuoi, DSLKD p)

{ if (dau==NULL)

dau=cuoi=p;

else

{ cuoi->tiep=p;

cuoi=p;

}

}

//Cai dat ham them sau Q.

void themSauQ(DSLKD &dau, DSLKD &cuoi, DSLKD p, DSLKD q)

{ if(p==cuoi)

themCuoi(dau,cuoi,p);

else

{ p->tiep=q->tiep;

q->tiep=p;

}

}

//Cai dat ham tao DSLKD.

void taoDSLKD(DSLKD &dau, DSLKD &cuoi)

{ //Khoi tao DSLKD

khoiTaoDSLKD(dau, cuoi);

kieuDL duLieu;

DSLKD p;

cout

cin>>duLieu;

while (duLieu!=0)

{ //Xin nut.

p=xinNut(duLieu);

themCuoi(dau, cuoi, p);

cout

cin>>duLieu;

}

cout

}

//Cai dat ham duyet DSLKD

void duyetDSLKD(DSLKD dau)

{ DSLKD p=dau;

while (p!=NULL)

{ coutduLieutiep

p=p->tiep;

}

}

//Cai dat ham giai phong.

void giaiPhong(DSLKD &dau, DSLKD &cuoi)

{ DSLKD p=dau;

while (dau!=NULL)

{ dau=dau->tiep;

free(p);

p=dau;

}

dau=cuoi=NULL;

}

//Cai dat ham tao Danh sach lien ket don.

void taoDSLKDN(DSLKD &dau, DSLKD &cuoi)

{ int n;

cout>n;

//Khoi dong bo sinh so ngau nhien.

srand(time(0));

//Khoi tao Danh sach lien ket don.

khoiTaoDSLKD(dau, cuoi);

for (int i=0; i

{ kieuDL duLieu;

//Sinh du lieu ngau nhien.

duLieu = rand()%n+1;

DSLKD p=xinNut(duLieu);

themCuoi(dau, cuoi, p);

}

}

//Cai dat ham tim d

void timD(DSLKD dau, kieuDL d)

{ DSLKD p=dau;

cout

cin>>d;

while (p!=NULL)

{

if (p->duLieu==d)

{

cout

//return p;

}

//else

p=p->tiep;

}

//return NULL;

}

//Cai dat ham xoa.

void xoaP (DSLKD &dau, DSLKD &cuoi, DSLKD p)

{

if (p==dau)//Xoa o dau.

dau=p->tiep;

else

//Xoa o sau lien ket.

{ //Tim phan tu truoc p.

DSLKD truocP=dau;

while(truocP->tiep!=p)

truocP=truocP->tiep;

//Tim thay truocP.

truocP->tiep=p->tiep;

if (p==cuoi)

cuoi=truocP;

}

//free(p);

}

//Cai dat ham demSoNut

int demSoNut(DSLKD &dau)

{ DSLKD p=dau; int n=0;

while(p!=NULL)

{ n++;

p=p->tiep;

}

return n;

}

//Cai dat ham xoaNutTrung.

void xoaNutTrung(DSLKD &dau,DSLKD &cuoi)

{ DSLKD p,q;

p=dau;

while(p!=cuoi)

{ q=p->tiep;

while(q!=NULL)

{ if(p->duLieu==q->duLieu)

xoaP(dau,cuoi,q);

q=q->tiep;

}

p=p->tiep;

}

//free(p);

}

//Cai dat ham daoDSLKD.

void daoDSLKD(DSLKD &dau,DSLKD &cuoi)

{ DSLKD hTai,truoc,tam;

hTai=dau;

cuoi=dau;truoc=NULL;

while(hTai!=NULL)

{ tam=truoc;

truoc=hTai;

hTai=hTai->tiep;

truoc->tiep=tam;

}

dau=truoc;

}

//Cai dat ham duyetTapHop.

void duyetTapHop(DSLKD dau)

{ DSLKD p=dau;

while (p!=NULL)

{ coutduLieu

p=p->tiep;

}

}

//Cai dat ham hop2TapHop

void hop2TapHop(DSLKD &dau1,DSLKD &dau2)

{ DSLKD p,q;

q=dau2;

cout

Hop cua hai tap A va B la: {";

duyetTapHop(dau1);

while(q!=NULL)

{ p=dau1;

while(p!=NULL && p->duLieu!=q->duLieu)

{ p=p->tiep;

}

if(p==NULL)coutduLieu

q=q->tiep;

}

cout

cout

}

//Cai dat ham giao2TapHop

void giao2TapHop(DSLKD &dau1,DSLKD &dau2)

{ DSLKD p,q;

p=dau1;

cout

Giao cua hai tap A va B la: {";

while(p!=NULL)

{ q=dau2;

while(q!=NULL && q->duLieu!=p->duLieu)

{ q=q->tiep;

}

if(q!=NULL)coutduLieu

p=p->tiep;

}

cout

cout

}

//Cai dat ham hieu2TapHop

void hieu2TapHop(DSLKD &dau1,DSLKD &dau2)

{ DSLKD p,q;

p=dau1;

while(p!=NULL)

{ q=dau2;

while(q!=NULL && q->duLieu!=p->duLieu)

{ q=q->tiep;

}

if(q==NULL)coutduLieu

p=p->tiep;

}

}

//Cai dat ham kiemTraTapCon

int kiemTraTapCon(DSLKD &dau1,DSLKD &dau2)

{ DSLKD p,q;

p=dau1;

while(p!=NULL)

{ q=dau2;

while(q!=NULL && q->duLieu!=p->duLieu)

{ q=q->tiep;

}

if(q==NULL)

{

return 1;

}

p=p->tiep;

}

if(p==NULL) return 0;

}

//Cai dat hai ham bang nhau

int haiTapBangNhau(DSLKD &dau1,DSLKD &dau2)

{ DSLKD p,q;int i,j;

p=dau1;q=dau2;

i=demSoNut(p);

j=demSoNut(q);

if(i!=j)

{

cout

Hai tap A va B khong bang nhau.";return 0;

}

while(p!=NULL)

{ q=dau2;

while(q!=NULL && q->duLieu!=p->duLieu)

{ q=q->tiep;

}

if(q==NULL)

{

cout

Hai tap A va B khong bang nhau.";return 0;

}

p=p->tiep;

}

cout

Hai tap A va B bang nhau.";

}