#2
莱莱的莱2019-04-03 08:16
|
只有本站会员才能查看附件,请 登录
只有本站会员才能查看附件,请 登录
主函数中的成员函数看main的注释就好啦,大佬们看看归并排序哪里出错了。归并排序代码就在main的上方哦~感觉像是越界了,可是就是找不出问题
程序代码:
#include<iostream>
#include<math.h>
#include<stdlib.h>
#define _CAPACITY 3
using namespace std;
//------------------------------------底层实现-----------------------------
typedef int Rank;
template<typename T>class Vector{
public:
//构造函数
Vector(); //无参构造函数,容量为_CAPACITY,规模为0,数据初始化为0(使用与int); OK
Vector(T const *A,Rank n); //T * 的前n项 OK
Vector(T const *A,Rank lo,Rank hi); //容量规模为hi-lo,范围是[lo,hi). OK
Vector(Vector<T> const &A); //拷贝构造函数 OK
Vector(Vector<T> const &A,Rank lo,Rank hi); //A中秩【lo,hi),数据容量与规模为lo-hi OK
//析构函数
~Vector(){delete []_elem;}
//只读访问接口
T& operator[](Rank n)const; //[]运算符的重载 OK
int Size()const{return _size;} //返回规模 OK
int capacity()const{return _capacity;} //返回容量 OK
bool Judgesort(Rank lo,Rank hi)const; //判断是否有序<区间> OK x->d
bool Judgesort()const{return Judgesort(0,_size);}//判断是否有序<整体> OK x->d
void PrinT()const; //测试函数<int>
//主体功能函数:
Vector<T>& operator =(const Vector<T> &e); //=运算符重载 OK
Rank Push_back(T const &e){return Insert(_size,e);}//尾部插入操作 OK
Rank Insert(Rank r,T const &e); //单个元素插入 OK
int Remove(Rank lo,Rank hi); //删除指定区间内的元素,返回删除的个数 OK
int Remove(Rank n){return Remove(n,n+1);} //删除单个元素,返回删除元素的秩 OK
void unsort(Rank lo,Rank hi); //区间置乱算法 OK
void unsort(){unsort(0,_size);} //总体置乱算法 OK
Rank Find(T const &e,Rank lo,Rank hi); //无序向量查找算法<区间> OK
Rank Find(T const &e){return Find(e,0,_size);} //无序向量查找算法<整体> OK
//Rank Search(T const &e,Rank lo,Rank hi);//有序向量区间查找算法
//Rank Search(T const &e){Search(e,0,_size);}//有序向量整体查找算法
void Sort(Rank lo,Rank hi); //排序器
int deduplicate(); //无序去重 OK
int uniquify(); //高效版有序去重 OK
void mergesort(Rank lo,Rank hi);
private:
T* _elem;
int _size;
int _capacity;
//私有的功能函数:
void copyform(T const *A,Rank lo,Rank hi); //拷贝功能函数 OK
void expand(); //扩容函数 OK
void shrink(); //缩容函数 OK
void swaps(T&A,T&B); //交换函数 OK
Rank Max(Rank lo,Rank hi); //返回最大元素的秩 OK
void Merge(Rank lo,Rank mid,Rank hi); //归并函数
//私有排序算法函数:
void bubblesort(Rank lo,Rank hi); //冒泡排序算法
void selectsort(Rank lo,Rank hi); //选择排序算法
//void mergesort(Rank lo,Rank hi); //归并排序算法
void heapsort(Rank lo,Rank hi); //堆排序算法
void quicksort(Rank lo,Rank hi); //快速排序算法
};
template<typename T> void Vector<T>::copyform(T const *A,Rank lo,Rank hi){
delete []_elem;
_size=0;
_elem=new T[_capacity=2*(hi-lo)];
while(lo<hi) _elem[_size++]=A[lo++];
}
template<typename T>void Vector<T>::expand(){
if(_size<_capacity) return;
if(_capacity<_CAPACITY) _capacity=_CAPACITY;
T*oldelem=_elem;
_elem=new T[_capacity*=2];
for(int i=0;i<_size;i++) _elem[i]=oldelem[i];
delete []oldelem;
}
template<typename T> void Vector<T>::shrink(){
if(_size>=_capacity>>2) return;
T*oldelem=_elem;
delete []_elem;
_elem=new T[_capacity>>=1];
for(int i=0;i<_size;i++) _elem[i]=oldelem[i];
delete []oldelem;
}
template<typename T> Vector<T>::Vector(){
_elem=new T[_CAPACITY];
_capacity=_CAPACITY;
_size=0;
}
template<typename T> T& Vector<T>::operator [](Rank n)const{
if(n>=_size) cout<<"越界了";
return _elem[n];
}
template<typename T> int Vector<T>::Remove(Rank lo,Rank hi){
if(lo==hi) return 0;
while(hi<_size)_elem[lo++]=_elem[hi++];
_size=lo;
shrink();
return hi-lo;
}
template<typename T>void Vector<T>::swaps(T &A,T &B){
T t=A;
A=B;
B=t;
}
template<typename T>void Vector<T>::unsort(Rank lo,Rank hi){
T* A=_elem+lo; //[0,hi-lo)
for(int i=hi-lo;i>0;i--){
swaps(A[i-1],A[rand()%i]);
}
}
template<typename T>Rank Vector<T>::Insert(Rank r,T const &e){
expand();
for(int i=_size;i>r;i--) _elem[i]=_elem[i-1];
_elem[r]=e;
_size++;
return r;
}
template<typename T>bool Vector<T>::Judgesort(Rank lo,Rank hi)const{
for(int i=lo;i<hi-1;i++) if(_elem[i]>_elem[i+1]) return false;
return true;
}
template<typename T>Rank Vector<T>::Find(T const &e,Rank lo,Rank hi){
if(lo==hi) return -1;
for(int i=lo;i<hi;i++) if(_elem[i]==e) return i;
return -1;
}
template<typename T>int Vector<T>::deduplicate(){
Rank r=0;
int oldsize=_size;
while(r<_size){
(Find(_elem[r],0,r)<0) ? r++: Remove(r);
}
return oldsize-_size;
}
template<typename T>int Vector<T>::uniquify(){
int s=0;
int oldsize=_size;
for(int i=s;i<_size;i++) if(_elem[s]!=_elem[i]) _elem[++s]=_elem[i];
_size=s+1;
shrink();
return oldsize-_size;
}
template<typename T>Vector<T>& Vector<T>::operator=(const Vector<T>&v){
copyform(v._elem,0,v._size);
return *this;
}
template<typename T> Rank Vector<T>::Max(Rank lo,Rank hi){
int maxRank;
T m=_elem[lo];
for(int i=lo+1;i<hi;i++){
if(_elem[i]>m){
m=_elem[i];
maxRank=i;
}
}
return maxRank;
}
template<typename T>Vector<T>::Vector(T const *A,int n){
copyform(A,0,n);
}
template<typename T>Vector<T>::Vector(T const *A,Rank lo,Rank hi){
copyform(A,lo,hi);
}
template<typename T>Vector<T>::Vector(Vector<T>const &A){
copyform(A._elem,0,A._size);
}
template<typename T>Vector<T>::Vector(Vector<T>const &A,Rank lo,Rank hi){
copyform(A._elem,lo,hi);
}
template<typename T>void Vector<T>::PrinT()const{
for(int i=0;i<_size;i++) cout<<_elem[i]<<" ";
cout<<endl;
cout<<"Size:"<<_size<<endl;
cout<<"Capacity:"<<_capacity<<endl;
}
template<typename T>void Vector<T>::mergesort(Rank lo,Rank hi){
if(lo+1==hi) return;//Rank 就是int
int mid=(lo+hi)>>1;
mergesort(lo,mid);
mergesort(mid,hi);
Merge(lo,mid,hi);
}
template<typename T>void Vector<T>::Merge(Rank lo,Rank mid,Rank hi){
T*A=_elem+lo;//_elem是线性表头指针
int lb=mid-lo;T*left=new T[lb];
for(int i=0;i<lb;i++) left[i]=A[i];
int lc=hi-mid;
T*right=_elem+mid;
int i,j,k;
for(i=0,j=0,k=0;i<lb&&j<lc;){
if(left[i]<=right[j]) A[k++]=left[i++];
else A[k++]=right[j++];
}
while(i<lc) A[k++]=left[i++];
delete []left;
}
//---------------------------------遇到的问题------------------------------
//--1.private 数据成员 初始化形参报错。
int main(void){
Vector<int> k;
for(int i=1;i<=5;i++) k.Push_back(i); //插入1~5
k.unsort();//乱序
k.PrinT();//测试打印
k.mergesort(0,k.Size());//归并排序
k.PrinT();//打印
return 0;
}
[此贴子已经被作者于2019-4-2 21:37编辑过]