| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
Reworld,下班在家制作游戏,1500万奖金等你拿以码会友 以友辅仁
共有 461 人关注过本帖
标题:顺序表封装归并排序输出不符,求助呀
只看楼主 加入收藏
莱莱的莱
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2019-4-2
  问题点数:0  回复次数:1   
顺序表封装归并排序输出不符,求助呀

主函数中的成员函数看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编辑过]

附件: 您没有浏览附件的权限,请 登录注册
搜索更多相关主题的帖子: int Rank Vector const void 
2019-04-02 21:27
莱莱的莱
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2019-4-2
  得分:0 
解决了,粗心了。
2019-04-03 08:16
快速回复:顺序表封装归并排序输出不符,求助呀
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.041054 second(s), 8 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved