#include<conio.h>
#include "dslkd.h"
#include<iostream.h>
/////////////////////////////////////////
DSLKD::DSLKD(){
dau=cuoi=NULL;
}
/////////////////////////////////////////////////////////////////
void DSLKD::themNutOCuoi(KieuDL duLieu)
{
//xin vung nho
NUT *p=new NUT(duLieu);
if (dau==NULL) dau=cuoi=p;
else {
cuoi->tiep=p;
cuoi=p;
}
}
/////////////////////////////////////////////////////////////////
void DSLKD::themNutPOCuoi(NUT *p){
if (dau==NULL) dau=cuoi=p;
else {
p->tiep =NULL;
cuoi->tiep=p;
cuoi=p;
}
}
/////////////////////////////////////////////////////////////////
void DSLKD::themNutODau(KieuDL duLieu){
//xin vung nho
NUT *p=new NUT(duLieu);
if (dau==NULL) dau=cuoi=p;
else {
p->tiep=dau;
dau=p;
}
}
/////////////////////////////////////////////////////////////////
void DSLKD::themNutSauP(KieuDL dLieuQ, NUT *p){
if (p==cuoi) themNutOCuoi(dLieuQ);
else {
NUT *q=new NUT(dLieuQ);
q->tiep=p->tiep;
p->tiep=q;
}
}
/////////////////////////////////////////////////////////////////
void DSLKD::themNutPSauQ(NUT *p, NUT *q){
q->tiep=p;
p->tiep=NULL;
if (q==this->cuoi) cuoi =p;
}
///////////////////////////////////////////////////////////////// so nut cua DSLKD
KieuDL DSLKD::demSoNut(NUT *p){
if(p==NULL) return 0;
else return (1+demSoNut(p->tiep));
}
/////////////////////////////////////////////////////////////////
Nut *DSLKD::timNut(KieuDL d)
{
NUT *p=dau;
while (p!=NULL) {
if (p->duLieu==d) return p;
else p=p->tiep;
}
return NULL;
}
/////////////////////////////////////////////////////////////////
Nut* DSLKD::nutMin(){
NUT *min=dau;
for(NUT *p=dau->tiep; p!=NULL; p=p->tiep)
if (p->duLieu < min->duLieu ) min=p;
return min;
}
/////////////////////////////////////////////////////////////////
void DSLKD::layNutP (Nut *p) {
if (DSLKDRong
()) cout <<"Khong the lap nut P vi danh sach rong"; else {
if (p==dau && p==cuoi) dau=cuoi=NULL;
else
if(p==dau) dau=dau->tiep;
else{
NUT *truocP=dau;
while (truocP->tiep!=p) truocP=truocP->tiep;
truocP->tiep=p->tiep;
if (p==cuoi) cuoi=truocP;
}
p->tiep =NULL;
}
}
/////////////////////////////////////////////////////////////////
void DSLKD::xoaNutP (NUT *p){
if ( DSLKDRong
() ) cout <<"Khong the xoa duoc vi DS da rong."; else {
if (p==dau && p==cuoi) dau=cuoi=NULL;
else
if(p==dau) dau=dau->tiep;
else{
NUT *truocP=dau;
while (truocP->tiep!=p) truocP=truocP->tiep;
truocP->tiep=p->tiep;
if (p==cuoi) cuoi=truocP;
}
delete p;
}
}
/////////////////////////////////////////////////////////////////
void DSLKD::duyetDSLKD() {
cout<<"Cac nut cua DS lien ket: "<<endl
; NUT *p=this->dau;
while (p!=NULL) {
p=p->tiep;
}
cout<<"NULL"<<endl
<<endl
; }
/////////////////////////////////////////////////////////////////
void DSLKD::huyDSLKD(){
NUT *p;
while (dau!=NULL) {
p=dau;
dau=dau->tiep;
delete p;
}
dau=cuoi=NULL;
}
/////////////////////////////////////////////////////////////////
DSLKD::~DSLKD(){
huyDSLKD();
}
/////////////////////////////////////////////////////////////////
bool DSLKD::DSLKDRong(){
return (dau==NULL ? true:false);
}
/////////////////////////////////////////////////////////////////
void DSLKD::sxChonTrucTiepND(){
NUT *postMin;
KieuDL temp;
for(NUT *p=dau;p!=cuoi;p=p->tiep) {
postMin=p;
for(NUT *q=p->tiep;q!=NULL;q=q->tiep)
if(q->duLieu < postMin->duLieu) postMin=q;
temp=p->duLieu;
p->duLieu=postMin->duLieu;
postMin->duLieu=temp;
}
}
/////////////////////////////////////////////////////////////////
void DSLKD::sxChonTrucTiepDC(){
NUT *min;
DSLKD *dSMoi=new DSLKD();
while (this->dau!=NULL) {
min=this->nutMin();
this->layNutP(min);
dSMoi->themNutPOCuoi(min);
}
this->dau=dSMoi->dau;
this->cuoi=dSMoi->cuoi;
}
/////////////////////////////////////////////////////////////////
void DSLKD::quickSort (){
if (this->dau == this->cuoi) return;
DSLKD *dS1=new DSLKD();
DSLKD *dS2=new DSLKD();
NUT *x=this->dau;
NUT *p;
this->layNutP (x);
while(this->dau !=NULL) {
p=this->dau ;
this->layNutP (p);
if (p->duLieu < x->duLieu) dS1->themNutPOCuoi(p);
else dS2->themNutPOCuoi(p);
}
dS1->quickSort();
dS2->quickSort();
//noi 2 ds
if (dS1->dau == NULL) this->dau=x;
else {
this->dau=dS1->dau;
this->cuoi=dS1->cuoi;
this->cuoi->tiep=x;
}
x->tiep = dS2->dau;
if(dS2->dau == NULL) this->cuoi=x;
else this->cuoi=dS2->cuoi;
}
///////////////////////////////////////////////////////// chia thanh 2 danh sach
void DSLKD::chiaNhoDSLKD(DSLKD *dS1, DSLKD *dS2) {
NUT *p;
do {
p=this->dau;
this->dau=p->tiep ;
p->tiep =NULL;
dS1->themNutPOCuoi (p);
}
while (this->dau !=NULL && p->duLieu < this->dau->duLieu );
if (this->dau !=NULL) this->chiaNhoDSLKD(dS2, dS1);
}
void DSLKD::tronDS(DSLKD *dS1, DSLKD *dS2) {
//tron 2 danh sach
NUT *p;
while (dS1->dau !=NULL && dS2->dau !=NULL ){
if (dS1->dau->duLieu < dS2->dau->duLieu ){
p=dS1->dau ;
dS1->layNutP (p);
}
else{
p=dS2->dau ;
dS2->layNutP (p);
}
this->themNutPOCuoi (p);
}
while (dS1->dau != NULL) { //ds1 khong rong
p= dS1->dau ;
dS1->layNutP(p);
this->themNutPOCuoi (p);
}
while (dS2->dau != NULL) { //ds2 khong rong
p= dS2->dau ;
dS2->layNutP(p);
this->themNutPOCuoi (p);
}
}
//////////////////////////////////////////////////////////
void DSLKD::mergeSort (){
if (this->dau==this->cuoi)
return;
DSLKD *dS1=new DSLKD();
DSLKD *dS2=new DSLKD();
chiaNhoDSLKD (dS1, dS2);
if (dS1->dau != NULL && dS2->dau != NULL) { //co 1 day da sap xep
dS1->mergeSort();
dS2->mergeSort ();
}
this->tronDS(dS1, dS2);
}
////////////////////////////////////////////////////////
DSLKD *giao(DSLKD *s,DSLKD *t){
NUT *p = s->dau;
DSLKD *kQ=new DSLKD();
while(p!=NULL) {
if (t->timNut(p->duLieu)!=NULL) kQ->themNutOCuoi(p->duLieu);
p=p->tiep;
}
return kQ;
}
////////////////////////////////////////////////////////
DSLKD *hop(DSLKD *s,DSLKD *t){
NUT *p=s->dau;
DSLKD *kQ=new DSLKD();
while (p!=NULL) {
kQ->themNutOCuoi(p->duLieu);
p=p->tiep;
}
p=t->dau;
while(p!=NULL) {
if (s->timNut(p->duLieu)==NULL) kQ->themNutOCuoi(p->duLieu);
p=p->tiep;
}
return kQ;
}
//////////////////////////////////////////////////////////
DSLKD *hieu(DSLKD *s,DSLKD *t){
NUT *p=s->dau;
DSLKD *kQ=new DSLKD();
while (p!=NULL) {
if (t->timNut(p->duLieu)==NULL) kQ->themNutOCuoi(p->duLieu);
p=p->tiep;
}
return kQ;
}
//////////////////////////////////////////////////////////
bool laTapCon(DSLKD *s,DSLKD *t){
NUT *p=s->dau;
while (p!=NULL) {
if (t->timNut(p->duLieu)!=NULL) p=p->tiep;
else return 0;
}
return 1;
}
//////////////////////////////////////////////////////////
void xuatTHop (DSLKD *tHop1,DSLKD *tHop2,Nut *p,Nut *q){
while(p!=NULL || q!=NULL) {
if ( p
==NULL && tHop1
->demSoNut
(p
) < tHop2
->demSoNut
(q
) ) cout<<" "<<"\t\t"<<q
->duLieu
<<endl
; else
if (q
==NULL && tHop1
->demSoNut
(p
)>tHop2
->demSoNut
(q
)) cout<<p
->duLieu
<<endl
; else cout<<p
->duLieu
<<"\t\t"<<q
->duLieu
<<endl
; if(p!=NULL) p=p->tiep;
if(q!=NULL) q=q->tiep;
}
}