đây là bài nộp số 1(cấu trúc dữ liệu) vẫn còn thiếu hai thuật sắp xếp nữa mình sẻ post sau:
trong này đã chạy hoàn toàn cam kết 100% là chạy được nhưng để tránh tình trạng các bạn không làm mà copy nguyên về nên mình se xoá bớt 4 chổ các bạn phải đọc và sửa lại nếu ko sẻ không chạy được(cũng vì muốn tốt cho mọi người thôi,xin lổi)còn điều gì chưa hiểu cứ hỏi nếu biết mình sẻ trả lời.
đây là phần khai báo lớp:
- Code:
-
#include<iostream>
#include<iomanip>
using namespace std;
class Cmang
{
public:
void heapsort();
void createheap();
void shift(int left,int right);
void bublesort();
void insertionsort();
void selectionsort();
int timnhiphan(int x);
void interchangesort();
void swap(int &a,int &b);
int timtuyentinh(int x);
void xuat();
void nhap();
Cmang();
virtual ~Cmang();
private:
int * m_data;
int m_sophantu;
};
đây là chi tiết hàm:
- Code:
-
void Cmang::nhap()
{
cout<<"nhap so phan tu: ";
cin>>m_sophantu;
m_data=new int[m_sophantu];
for(int i=0;i<m_sophantu;i++)
{
cout<<"phan tu "<<i<<" = ";
cin>>m_data[i];
}
}
void Cmang::xuat()
{
cout<<"mang: ";
for(int i=0;i<m_sophantu;i++)
cout<<setw(4)<<m_data[i];
cout<<endl;
}
int Cmang::timtuyentinh(int x)
{
for(int i=0;i<m_sophantu;i++)
if(m_data[i]==x) return i;
return -1;//khong tim thay
}
void Cmang::swap(int &a, int &b)
{
int tam=a ;
a=b;
b=tam;
}
void Cmang::interchangesort()
{
for(int i=0;i<m_sophantu-1;i++)
for(int j=i+1;j<m_sophantu;j++)
if(m_data[j]<m_data[i])
swap(m_data[i],m_data[j]);
}
int Cmang::timnhiphan(int x)
{
int mid,left=0,right=m_sophantu-1;
while (left<right)
{
mid=(left+right)/2;
if(m_data[mid]=x)
return mid;
if(m_data[mid]<x)
right=mid-1;
else left=mid+1;
}
return -1;
}
void Cmang::selectionsort()
{
int min;
for(int i=0;i<m_sophantu-1;i++)
{
min = i;
for(int j=i+1;j<m_sophantu;j++)
if(m_data[min]>m_data[j])
min=j;
if(min != i)
swap(m_data[min],m_data[i]);
}
}
void Cmang::insertionsort()
{
int pos,x;
for(int i=1;i<m_sophantu;i++)
{
x=m_data[i];
for(pos=i;(pos>0)&&(m_data[pos-1]>x);pos--)
m_data[pos]=m_data[pos-1];
m_data[pos]=x;
}
}
void Cmang::bublesort()
{
for(int i=0;i<m_sophantu-1;i++)
for(int j=m_sophantu-1;j>i;j--)
if(m_data[j]<m_data[j-1])
swap(m_data[j],m_data[j-1]);
}
void Cmang::shift(int left, int right)
{
int x,curr,joint;
curr=left;joint=2*curr+1;//ajoint :phan tu lien doi
x=m_data
while (joint<=right)
{
if(joint<right) //co du hai thanh phan lien doi
if(m_data[joint]<m_data[joint+1])
joint=joint+1;
if( [joint]<x) break;//thoa quan he lien doi
m_data[curr]=m_data[joint];
curr=joint;//xet tiep kha nang hieu chinh lan truyen
joint=2*joint+1;
}
m_data[curr]=x;
}
void Cmang::createheap()
{
int ;//vi tri phan tu can ghep them
for(left=(m_sophantu-1)/2;left>=0;left--)
shift(left,m_sophantu-1);
}
void Cmang::heapsort()
{
int right;
createheap();
right=m_sophantu-1;//right o day la dung cho phan tu lon nhat duoc dua ve cuoi mang
while(right>0)
{
swap(m_data[0],m_data[right]);
;
shift(0,right);
}
}
đây là hàm main()
- Code:
-
#include"mang.h"
int main()
{
Cmang h;
h.nhap();
h.xuat();
h.interchangesort();
cout<<"mang sau khi xap xep ";
h.xuat();
h.selectionsort();
h.xuat();
h.insertionsort();
h.xuat();
h.bublesort();
h.xuat();
h.heapsort();
h.xuat();
int x;
cout<<"nhap vao gia tri can tim: ";
cin>>x;
if(h.timtuyentinh(x) != -1)
cout<<"tim thay "<<x<<" tai vi tri "<<h.timtuyentinh(x);
else
cout<<"khong tim thay gia tri "<<x;
cout<<endl;
system("pause");
return 0;
}
mình nhắc lại các bạn bắt buộc phải đọc bài và thêm vào một số chổ mới chạy hoàn toàn được(mình chỉ bỏ đi những thứ liên quan đến hàm heap thôi các hàm trên đã chạy hoàn toàn).