Anh Em vào thảo luận nào

**doikonhulamo** · 24-05-2014, 01:12 PM

Anh Em ai giỏi giải thuật xem giùm mình hàm sắp xếp insertionsort của mình sai chỗ nào mà chạy hoài ko dc tức wa [IMG]images/smilies/21.gif[/IMG] làm gần xong hết rùi còn mỗi câu đó là chưa ra tức thật mà mấy bạn có rãnh xem giùm mình cái code mình làm vậy tối ưu về thuật toán chưa vậy các bạn [IMG]images/smilies/17.gif[/IMG]
đây code mình đây

#include<iostream.h>
#include<stdio.h>
#include<windows.h>
#include<conio.h>
#include<string.h>
typedef struct BN
{
int maBN;
char hoTen[20];
char ngayNhapBV[20];
};
typedef struct BNNode
{
BN data;
BNNode *next;
};
typedef struct DSLKD
{
BNNode *first,*last;
int soPT;
};
BN nhapBN(BN &x);
BNNode *taoNode(BN x);
void khoitao(DSLKD &l);
bool isEmpty(DSLKD l);
void themDau(DSLKD &l,BN x);
void themGiua(DSLKD &l,BN x,int ma);
void themGiuaTruoc(DSLKD &l,BN x,int ma);
void themCuoi(DSLKD &l,BN x);
int huyDau(DSLKD &l);
int huyCuoi(DSLKD &l);
BN huyGiua(DSLKD &l,int ma);
void searchX(DSLKD &l,int ma);
int searchX2(DSLKD &l,int ma);
void countX(DSLKD l,int ma);
void huyAll (DSLKD &l);
void InterchangeSort(DSLKD &l);
void BubbleSort(DSLKD &l);
void SelectionSort(DSLKD &l);
void InsertionSort(DSLKD &l);
void xuat(DSLKD l);
int main()
{
int luachon;
DSLKD l;
BN x;
a:;
cout<<"---------------------------MENU---------------------------"<<endl;
cout<<"| 1.Khoi tao |"<<endl;
cout<<"| 2.Them |"<<endl;
cout<<"| 3.Huy |"<<endl;
cout<<"| 4.Tim kiem |"<<endl;
cout<<"| 5.Dem |"<<endl;
cout<<"| 6.Xuat |"<<endl;
cout<<"| 7.Huy toan bo danh sach |"<<endl;
cout<<"| 8.Sap xep |"<<endl;
cout<<"| 9.Thoat |"<<endl;
cout<<"----------------------------------------------------------"<<endl;
cout<<"----->>>>Tinh nang ";cin>>luachon;
switch(luachon)
{
case 1 : cout<<"khoi tao thanh cong "<<endl;
khoitao(l);
system("pause");
system("cls");
break;
case 2 :
int them;
system("cls");
cout<<"---------------------------MENU---------------------------"<<endl;
cout<<"| 1.Them dau |"<<endl;
cout<<"| 2.Them giua sau |"<<endl;
cout<<"| 3.Them giua truoc |"<<endl;
cout<<"| 4.Them cuoi |"<<endl;
cout<<"| 5.Quay lai |"<<endl;
cout<<"----------------------------------------------------------"<<endl;
cout<<"----->>>>Tinh nang ";cin>>them;
switch(them)
{
case 1 :
a1:;
themDau(l,x);
int chonthem1;
system("cls");
cout<<"---------------------------MENU---------------------------"<<endl;
cout<<"| 1.Them |"<<endl;
cout<<"| 2.Quay lai |"<<endl;
cout<<"----------------------------------------------------------"<<endl;
cout<<"----->>>>Tinh nang ";cin>>chonthem1;
if(chonthem1==1)
{
goto a1;
}
if(chonthem1==2)
{
system("cls");
break;
}
case 2 :
a2:;
int ma;
cout<<"them sau benh nhan nao ";cin>>ma;
int kiemtra=searchX2(l,ma);
if(!kiemtra)
{
cout<<"ko tim thay benh nhan "<<endl;
goto b2;
}
themGiua(l,x,ma);
system("pause");
int chonthem2;
system("cls");

cout<<"---------------------------MENU---------------------------"<<endl;
cout<<"| 1.Them |"<<endl;
cout<<"| 2.Quay lai |"<<endl;
cout<<"----------------------------------------------------------"<<endl;
cout<<"----->>>>Tinh nang ";cin>>chonthem2;
if(chonthem2==1)
{
goto a2;
}
if(chonthem2==2)
{
b2:;
system("pause");
system("cls");
break;
}
case 3 :
a3:;
int matruoc;
cout<<"them truoc benh nhan nao ";cin>>matruoc;
int kiemtra1=searchX2(l,ma);
if(!kiemtra1)
{
cout<<"ko tim thay benh nhan "<<endl;
goto b3;
}
themGiuaTruoc(l,x,matruoc);
system("pause");
int chonthem3;
system("cls");

cout<<"---------------------------MENU---------------------------"<<endl;
cout<<"| 1.Them |"<<endl;
cout<<"| 2.Quay lai |"<<endl;
cout<<"----------------------------------------------------------"<<endl;
cout<<"----->>>>Tinh nang ";cin>>chonthem3;
if(chonthem3==1)
{
goto a3;
}
if(chonthem3==2)
{
b3:;
system("pause");
system("cls");
break;
}
case 4 :
a4:;
themCuoi(l,x);
int chonthem4;
system("cls");
cout<<"---------------------------MENU---------------------------"<<endl;
cout<<"| 1.Them |"<<endl;
cout<<"| 2.Quay lai |"<<endl;
cout<<"----------------------------------------------------------"<<endl;
cout<<"----->>>>Tinh nang ";cin>>chonthem4;
if(chonthem4==1)
{
goto a4;
}
if(chonthem4==2)
{
system("cls");
break;
}
case 5 : system("cls");break;

}
break;
case 3 :
int huy;
system("cls");
cout<<"---------------------------MENU---------------------------"<<endl;
cout<<"| 1.Huy dau |"<<endl;
cout<<"| 2.Huy giua |"<<endl;
cout<<"| 3.Huy cuoi |"<<endl;
cout<<"| 4.Quay lai |"<<endl;
cout<<"----------------------------------------------------------"<<endl;
cout<<"----->>>>Tinh nang ";cin>>huy;
switch(huy)
{
case 1 :
h1:;
huyDau(l);
int chonhuy1;
system("cls");
cout<<"---------------------------MENU---------------------------"<<endl;
cout<<"| 1.Huy |"<<endl;
cout<<"| 2.Quay lai |"<<endl;
cout<<"----------------------------------------------------------"<<endl;
cout<<"----->>>>Tinh nang ";cin>>chonhuy1;
if(chonhuy1==1)
{
goto h1;
}
if(chonhuy1==2)
{
system("cls");
break;
}
case 2 :
h2:;
int mahuy;
cout<<"huy nhan vien nao ";cin>>mahuy;
huyGiua(l,mahuy);
int chonhuy2;
system("cls");

cout<<"---------------------------MENU---------------------------"<<endl;
cout<<"| 1.Huy |"<<endl;
cout<<"| 2.Quay lai |"<<endl;
cout<<"----------------------------------------------------------"<<endl;
cout<<"----->>>>Tinh nang ";cin>>chonhuy2;
if(chonhuy2==1)
{
goto h2;
}
if(chonhuy2==2)
{
system("cls");
break;
}
case 3 :
h3:;
huyCuoi(l);
int chonhuy3;
system("cls");
cout<<"---------------------------MENU---------------------------"<<endl;
cout<<"| 1.Huy |"<<endl;
cout<<"| 2.Quay lai |"<<endl;
cout<<"----------------------------------------------------------"<<endl;
cout<<"----->>>>Tinh nang ";cin>>chonhuy3;
if(chonhuy3==1)
{
goto h3;
}
if(chonhuy3==2)
{
system("cls");
break;
}
case 4 : system("cls");break;
}
break;
case 4 :
int matim;
cout<<"nhap vao ma benh nhan can tim ";cin>>matim;
searchX(l,matim);
system("pause");
system("cls");
break;
case 5 :
int madem;
cout<<"nhap vao ma benh nhan can dem ";cin>>madem;
countX(l,madem);
system("pause");
system("cls");
break;
case 6 : xuat(l);
system("pause");
system("cls");
break;
case 7 : huyAll(l);
cout<<"huy thanh cong "<<endl;
system("pause");
system("cls");
break;
case 8 :
system("cls");
int sapxep;
cout<<"---------------------------MENU---------------------------"<<endl;
cout<<"| 1.Interchage Sort |"<<endl;
cout<<"| 2.Bubble Sort |"<<endl;
cout<<"| 3.Selection Sort |"<<endl;
cout<<"| 4.Insertion Sort |"<<endl;
cout<<"| 5.Thoat |"<<endl;
cout<<"----------------------------------------------------------"<<endl;
cout<<"Ban muon sap xep kieu nao ";cin>>sapxep;
switch(sapxep)
{
case 1:InterchangeSort(l);system("cls");break;
case 2:BubbleSort(l);system("cls");break;
case 3:SelectionSort(l);system("cls");break;
case 4:InsertionSort(l);system("cls");break;
case 5 : break;
}
system("cls");
break;
case 9 : return 0;break;
default : cout<<"ban nhap sai roi "<<endl;
system("cls");
break;

}
goto a;
return 0;
}

BN nhapBN(BN &x)
{
cout<<"ma benh nhan ";cin>>x.maBN;
cout<<"ten benh nhan ";
fflush(stdin);
gets(x.hoTen);
cout<<"ngay nhap vien ";
fflush(stdin);
gets(x.ngayNhapBV);
return x;
}
BNNode *taoNode(BN x)
{
BNNode *p=new BNNode;
x=nhapBN(x);
if(p==NULL)
{
cout<<"ko du bo nho "<<endl;
return 0;
}
p->data=x;
p->next=NULL;
return p;
}
void khoitao(DSLKD &l)
{
l.first=l.last=NULL;
l.soPT=0;
}
bool isEmpty(DSLKD l)
{
if(l.first==l.last==NULL)
{
return true;
}
return false;
}
void themDau(DSLKD &l,BN x)
{
BNNode *newnode=taoNode(x);
if(l.first==NULL)
{
l.first=l.last=newnode;
}
else{
newnode->next=l.first;
l.first=newnode;
}
l.soPT++;
}
void themGiua(DSLKD &l,BN x,int ma)
{
BNNode *p=new BNNode;
p=l.first;
while(p!=NULL)
{
if(p->data.maBN==ma)
{
BNNode *newnode=taoNode(x);
newnode->next = p->next;
p->next = newnode;
if(p == l.last)
{
l.last = newnode;
}
l.soPT++;
return;
}
p=p->next;
}
}
void themCuoi(DSLKD &l,BN x)
{
BNNode *newnode=taoNode(x);
if(l.first==NULL)
{
l.first=l.last=newnode;
}
else
{
l.last->next=newnode;
l.last=newnode;
}
}

void themGiuaTruoc(DSLKD &l,BN x,int ma)
{
BNNode *p=new BNNode;
p=l.first;
BNNode *q=new BNNode;
q=p->next;
if(p->data.maBN==ma)
{
themDau(l,x);
p=p->next;
l.soPT++;
return ;
}
while(q!=NULL)
{

if(q->data.maBN==ma)
{
BNNode *newnode=taoNode(x);
newnode->next=q;
p->next=newnode;
l.soPT++;
return;
}
p=q;
q=q->next;
}
}
int huyDau(DSLKD &l)
{
if (l.first == NULL) return 0;
BNNode* p=l.first;
l.first = p->next;
if (l.first == NULL)
l.last=NULL; //N?u danh sách r?ng
delete p;
l.soPT--;
return 1;

}

int huyCuoi(DSLKD &l)
{
if(l.first==NULL)
{
return 0;
}
BNNode *p=l.last;
BNNode *q=l.first;
BNNode *k;
while(q->next!=NULL)
{
k=q;
q=q->next;
}
k->next=NULL;
l.last=k;
delete p;
l.soPT--;
return 1;
}
BN huyGiua(DSLKD &l,int ma)
{
BNNode *tmp=new BNNode;
tmp=l.first;
if(l.first->data.maBN==ma)
{
l.first=tmp->next;
if (l.first== NULL)
{
l.last=NULL;
}
delete tmp;
l.soPT--;
}

while(tmp->next!=NULL)
{
if(tmp->next->data.maBN==ma)
{
BN ketqua=tmp->next->data;
BNNode *tmpdel=new BNNode;
tmpdel=tmp->next;
tmp->next=tmpdel->next;
delete tmpdel;
l.soPT--;
return ketqua;
}
tmp=tmp->next;
}
cout<<"ko tim thay ma benh nhan can huy "<<endl;

}
void searchX(DSLKD &l,int ma)
{
BNNode *p=new BNNode;
p=l.first;
while(p!=NULL)
{
if(p->data.maBN==ma)
{
cout<<"da tim thay benh nhan co ma la "<<ma<<endl;
return;
}
p=p->next;
}
cout<<"khong tim thay benh nhan co ma la "<<ma<<endl;
}
int searchX2(DSLKD &l,int ma)
{
BNNode *p=new BNNode;
p=l.first;
while(p!=NULL)
{
if(p->data.maBN==ma)
{
return 1;
}
p=p->next;
}
return 0;
}
void huyAll (DSLKD &l)
{
BNNode *p;
while (l.first != NULL)
{
p = l.first;
l.first = p->next;
delete p;
}
l.last = NULL;
}

void countX(DSLKD l,int ma)
{
BNNode *p=new BNNode;
p=l.first;
int dem=0;
while(p!=NULL)
{
if(p->data.maBN==ma)
{
dem++;
}
p=p->next;
}
cout<<"co "<<dem<<" benh nhan trong dslk co ma la "<<ma<<" "<<endl;
}
void InterchangeSort(DSLKD &l)
{
BNNode *p=new BNNode;
p=l.first;
BNNode *q=p->next;
while(p->next!=NULL)
{
while(q!=NULL)
{
if(strcmp(p->data.hoTen,q->data.hoTen)>0)
{
BN x=p->data;
p->data=q->data;
q->data=x;
}
q=q->next;
}
p=p->next;
}
}
void BubbleSort(DSLKD &l)
{
BNNode *p=new BNNode;
p=l.first;
BNNode *q=p;
while(p->next!=NULL)
{
q=p;
while(q->next!=NULL)
{
if(strcmp(q->data.hoTen,q->next->data.hoTen)>0)
{
BN x=q->data;
q->data=q->next->data;
q->next->data=x;
}
q=q->next;
}
p=p->next;
}
}
void SelectionSort(DSLKD &l)
{
BNNode *p=new BNNode;
p=l.first;
BN min;
BNNode *q;
BNNode *tim=new BNNode;
tim=l.first;
while(p->next!=NULL)
{
q=p->next;
min=p->data;
int dem=0;
while(q!=NULL)
{
if(strcmp(min.hoTen,q->data.hoTen)>0)
{
min=q->data;
dem=1;
}
q=q->next;
}
if(dem)
{
while(tim!=NULL)
{
if(tim->data.maBN==min.maBN)
{
BN temp=tim->data;
tim->data=p->data;
p->data=temp;
}
tim=tim->next;
}
}
p=p->next;
}
}

void InsertionSort(DSLKD &l)
{
BN x;
BNNode *p=new BNNode;
int pos=0,temp;
BNNode *q=new BNNode;
for(p=l.first;p!=NULL;p=p->next)
{
x=p->next->data;
pos++;
q=p;
temp=pos;
while(temp>=0&&(strcmp(q->data.hoTen,x.hoTen)>0))
{
q->next->data=q->data;
temp--;
if(temp==0) break;
BNNode *tam=new BNNode;
tam=l.first;
while(tam->next!=q)
{
tam=tam->next;

}
q=tam;
}
q->data=x;
}
}
void xuat(DSLKD l)
{
BNNode *p=l.first;
while(p!=NULL)
{
cout<<"MaBN : "<<p->data.maBN<<"\t Ten : "<<p->data.hoTen<<"\t Ngay vao : "<<p->data.ngayNhapBV<<endl;
p=p->next;
}
}

View more random threads:

**khamnamkhoa** · 25-05-2014, 02:54 PM

Của bạn đây.

Mã:

void InsertionSort(DSLKD &l)
{
	BNNode *p1, *p2;
	BN x;
	p1=l.first;
	for(p1->next; p1!=NULL; p1=p1->next)
	{
		p2=l.first;
		while(p2!=p1)
		{
			if(strcmp(p2->data.hoTen, p1->data.hoTen)>0)
			{
				x=p2->data;
				p2->data=p1->data;
				p1->data=x;
				p2=p2->next;
			}
			if(strcmp(p2->data.hoTen, p1->data.hoTen)<0)
				p2=p2->next;
		}
	}
}

**vanvuive** · 25-05-2014, 03:44 PM

mình nói tren rùi mà bài mình sai cái inserttionSort đó nhưng mình ko bik cách sữa thế nào còn lại thì đúng hết ruì

**ducthangseo** · 25-05-2014, 05:34 PM

Gửi bởi badman

Của bạn đây.

Mã:

void InsertionSort(DSLKD &l)
{
	BNNode *p1, *p2;
	BN x;
	p1=l.first;
	for(p1->next; p1!=NULL; p1=p1->next)
	{
		p2=l.first;
		while(p2!=p1)
		{
			if(strcmp(p2->data.hoTen, p1->data.hoTen)>0)
			{
				x=p2->data;
				p2->data=p1->data;
				p1->data=x;
				p2=p2->next;
			}
			if(strcmp(p2->data.hoTen, p1->data.hoTen)<0)
				p2=p2->next;
		}
	}
}

cám ơn bạn nhiều lắm nhưng theo mình nghĩ thì thuật toán của bạn ko đúng với qui tắc của thằng insertionSort vì theo qui tắc của nó là chèn các phần tử vào vị trí thích hợp nếu ko dc thì cứ dịch các phần tử lên rùi chèn còn cua bạn thì so sánh rùi hoán vị 2 vị trì của nó theo mình giống SelectionSort hơn thì phải
đây code của em nó đây nhưng mình vẫn chưa bik cách làm sao cho nó dịch chuyển phần tử hết
// input: dãy (a, n)
// output: dãy (a, n) đã được sắp xếp
Bước 1: i = 2; // giả sử có đoạn a[0] đã được sắp
Bước 2: x = a[i]; //Tìm vị trí pos thích hợp trong đoạn a[0]
//đến a[i] để chèn x vào
Bước 3: Dời chỗ các phần tử từ a[pos] đến a[i-1] sang
phải 1 vị trí để dành chỗ cho x
Bước 4: a[pos] = x; // có đoạn a[0]..a[i] đã được sắp
Bước 5: i = i+1;
Nếu i <= n: Lặp lại Bước 2
Ngược lại: Dừng

void InsertionSort(int a[], int n){
int pos, x;
for(int i=0; i<n; i++) //đoạn a[0] đã sắp
{
x = a[i+1];
pos = i;
while(pos>=0 && a[pos]>x)
{ a[pos+1] = a[pos];
pos--;
}
a[pos] = x;
}
}
Đây là thuật toán của em nó đây nếu bạn tìm ra dc cách gì thì gợi ý mình nhá

**kysybongdemictu** · 25-05-2014, 07:47 PM

Cậu tách code lỗi ra chạy riêng ra rồi đăng lên lại, khi đăng bài nhớ quote trong bọc CODE cho dễ nhìn nữa.

**suckhoe280** · 26-05-2014, 12:40 PM

Gửi bởi badman

Của bạn đây.

Mã:

void InsertionSort(DSLKD &l)
{
	BNNode *p1, *p2;
	BN x;
	p1=l.first;
	for(p1->next; p1!=NULL; p1=p1->next)
	{
		p2=l.first;
		while(p2!=p1)
		{
			if(strcmp(p2->data.hoTen, p1->data.hoTen)>0)
			{
				x=p2->data;
				p2->data=p1->data;
				p1->data=x;
				p2=p2->next;
			}
			if(strcmp(p2->data.hoTen, p1->data.hoTen)<0)
				p2=p2->next;
		}
	}
}

- bạn viết "p2->data=p1->data;" sẽ bị sai do data không phải là kiểu dữ liệu cơ bản hoặc con trỏ nên nó không cài đặt sẵn phương thức gán. Thứ 2 là sau câu if thứ nhất thì p2 và p1 có thể đã bị đổi giá trị, chạy sang câu if thứ 2 máy tính sẽ lấy 2 giá trị đã bị thay đổi này để thực hiện hàm strcmp => cho nên nó sẽ chạy không đúng ý bạn. Còn về insert sort mình ko nhớ lắm nên ko góp ý gì được.

**thanhtungbooking** · 27-05-2014, 03:09 PM

èo vậy ko ai giúp dc mình ak chán wa còn mỗi có 1 cậu này ko làm đc tức ghê làm hoài ko ra mà vẫn ko bik sai chỗ nào tức thật

**chimlonvn** · 06-06-2014, 11:19 AM

Gửi bởi lorenkid1994

cám ơn bạn nhiều lắm nhưng theo mình nghĩ thì thuật toán của bạn ko đúng với qui tắc của thằng insertionSort vì theo qui tắc của nó là chèn các phần tử vào vị trí thích hợp nếu ko dc thì cứ dịch các phần tử lên rùi chèn còn cua bạn thì so sánh rùi hoán vị 2 vị trì của nó theo mình giống SelectionSort hơn thì phải
đây code của em nó đây nhưng mình vẫn chưa bik cách làm sao cho nó dịch chuyển phần tử hết
// input: dãy (a, n)
// output: dãy (a, n) đã được sắp xếp
Bước 1: i = 2; // giả sử có đoạn a[0] đã được sắp
Bước 2: x = a[i]; //Tìm vị trí pos thích hợp trong đoạn a[0]
//đến a[i] để chèn x vào
Bước 3: Dời chỗ các phần tử từ a[pos] đến a[i-1] sang
phải 1 vị trí để dành chỗ cho x
Bước 4: a[pos] = x; // có đoạn a[0]..a[i] đã được sắp
Bước 5: i = i+1;
Nếu i <= n: Lặp lại Bước 2
Ngược lại: Dừng

void InsertionSort(int a[], int n){
int pos, x;
for(int i=0; i<n; i++) //đoạn a[0] đã sắp
{
x = a[i+1];
pos = i;
while(pos>=0 && a[pos]>x)
{ a[pos+1] = a[pos];
pos--;
}
a[pos] = x;
}
}
Đây là thuật toán của em nó đây nếu bạn tìm ra dc cách gì thì gợi ý mình nhá

Nếu thế thì bạn dùng danh sách liên kết đôi đi :v

Chủ đề: Anh Em vào thảo luận nào

Công cụ Chủ đề

Tìm Chủ đề

Hiển thị

Anh Em vào thảo luận nào

View more random threads:

Quyền viết bài

Tìm xưởng may gia công tại TP Hồ...

Phân phối chày rung tình dục công...

Trần xuyên sáng đẹp giá rẻ – Bảng...

Tìm kiếm hiểu ngay Serum B5 có áp...

How to care for seagrass furniture?