[C++/PTA] 有序数组（类模板）

题目要求

实现一个类模板，它可以接受一组数据，能对数据排序，也能输出数组的内容。

每行输入的第一个数字为0，1，2或3:为0时表示输入结束； 为1时表示将输入整数，为2时表示将输入有一位小数的浮点数，为3时表示输入字符。

如果第一个数字非0，则接下来将输入一个正整数，表示即将输入的数据的数量。

从每行第三个输入开始，依次输入指定类型的数据。

类模板：

template
class MyArray

裁判测试程序样例：

#include <iostream>
using namespace std;

/* 请在这里填写答案 */

template<class T>
MyArray<T>::~MyArray(){ delete[] data;}

template<class T>
bool MyArray<T>::check(){
    int i;
    for(i=0;i<size-1;i++)
        if(data[i]>data[i+1]) { cout<<"ERROR!"<<endl;return false;}
    return true;
}
int main( )
{
    MyArray<int> *pI;
    MyArray<float> *pF;
    MyArray<char> *pC;
    int ty, size;
    cin>>ty;
    while(ty>0){
        cin>>size;
        switch(ty){
            case 1: pI = new MyArray<int>(size);   pI->sort(); pI->check(); pI->display(); delete pI; break;
            case 2: pF = new MyArray<float>(size); pF->sort(); pF->check(); pF->display(); delete pF; break;
            case 3: pC = new MyArray<char>(size);  pC->sort(); pC->check(); pC->display(); delete pC; break;
        }
        cin>>ty;
    }
    return 0;
}

输入样例：
1 3 2 3 1
2 4 1.5 2.6 3.7 0.5
3 2 A a
0

输出样例：
1 2 3
0.5 1.5 2.6 3.7
A a

解题思路

在MyArray类中定义类模板、构造函数、析构函数、排序函数和输出函数等成员函数：

• 类模板定义了类型T，表示数组中的元素类型。

• 构造函数的参数是一个整数，表示需要创建的数组的大小。它会动态地分配一段内存，存放输入的数据。

• 析构函数用于在对象销毁时释放内存。

• 排序函数使用冒泡排序算法对数组中的元素进行升序排序。

• 输出函数用于输出数组中的元素。

代码

template<class T>   // 类模板，T为数组中元素的类型
class MyArray{
private:
    T *data;        // 指向数组的指针
    int size;       // 数组大小
 
public:
    MyArray(int s);     // 带参数的构造函数
    ~MyArray();         // 析构函数
    void sort();        // 排序
    void display();     // 输出
    bool check();       // 检查数组是否有序
};

template<class T>
MyArray<T>::MyArray(int s){
    size = s;
    data = new T[size]; // 动态分配内存
    for(int i=0;i<size;i++)
        cin>>data[i];   // 输入数组元素
}

template<class T>
void MyArray<T>::display(){
    for(int i=0;i<size;i++){
        cout<<data[i];      // 输出当前元素的值
        if(i<size-1)        // 如果不是最后一个元素，则输出一个空格
            cout<<" ";
    }
    cout<<endl;             // 换行
}

template<class T>
void MyArray<T>::sort(){
    for(int i=0;i<size-1;i++)               // 从数组第一位开始冒泡排序
        for(int j=0;j<size-i-1;j++)
            if(data[j]>data[j+1]){          // 交换相邻两个元素的位置
                T temp = data[j];
                data[j] = data[j+1];
                data[j+1] = temp;
            }
}

整体代码如下：

#include <iostream>
using namespace std;

template<class T>   // 类模板，T为数组中元素的类型
class MyArray{
private:
    T *data;        // 指向数组的指针
    int size;       // 数组大小
 
public:
    MyArray(int s);     // 带参数的构造函数
    ~MyArray();         // 析构函数
    void sort();        // 排序
    void display();     // 输出
    bool check();       // 检查数组是否有序
};

template<class T>
MyArray<T>::MyArray(int s){
    size = s;
    data = new T[size]; // 动态分配内存
    for(int i=0;i<size;i++)
        cin>>data[i];   // 输入数组元素
}

template<class T>
void MyArray<T>::display(){
    for(int i=0;i<size;i++){
        cout<<data[i];      // 输出当前元素的值
        if(i<size-1)        // 如果不是最后一个元素，则输出一个空格
            cout<<" ";
    }
    cout<<endl;             // 换行
}

template<class T>
void MyArray<T>::sort(){
    for(int i=0;i<size-1;i++)               // 从数组第一位开始冒泡排序
        for(int j=0;j<size-i-1;j++)
            if(data[j]>data[j+1]){          // 交换相邻两个元素的位置
                T temp = data[j];
                data[j] = data[j+1];
                data[j+1] = temp;
            }
}


template<class T>
MyArray<T>::~MyArray(){ delete[] data;}   // 析构函数，释放内存

template<class T>
bool MyArray<T>::check(){
    int i;
    for(i=0;i<size-1;i++)
        if(data[i]>data[i+1]) { cout<<"ERROR!"<<endl;return false;}
    return true;
}

int main(){
    MyArray<int> *pI;       // 整型数组指针
    MyArray<float> *pF;     // 浮点型数组指针
    MyArray<char> *pC;      // 字符型数组指针
    int ty, size;

    cin>>ty;    // 输入数组元素类型，0表示输入结束
    while(ty>0){
        cin>>size;  // 输入数组大小
        switch(ty){
            case 1: 
                pI = new MyArray<int>(size);   // 创建整型数组对象
                pI->sort();     // 数组排序
                pI->check();    // 检查数组是否有序
                pI->display();  // 输出数组
                delete pI;      // 释放内存
                break;
            case 2: 
                pF = new MyArray<float>(size); // 创建浮点型数组对象
                pF->sort();
                pF->check();
                pF->display();
                delete pF;
                break;
            case 3: 
                pC = new MyArray<char>(size);  // 创建字符型数组对象
                pC->sort();
                pC->check();
                pC->display();
                delete pC;
                break;
        }
        cin>>ty;    // 继续输入下一组数据
    }
    return 0;
}

总结

该题主要考察类模板和动态内存分配的知识。

使用类模板定义的通用的数组类 MyArray，可以根据不同类型的数据创建不同的数组对象。同时，该代码还使用了动态内存分配的方式为数组动态分配内存，并用析构函数对动态分配的内存进行释放，避免了内存泄漏的问题。

我是秋说，我们下次见。