【C++面向对象——群体类和群体数据的组织】实现含排序功能的数组类（头歌实践教学平台习题）【合集】

Rossy Yan

修改于 2024-12-26 10:17:03

3410

文章被收录于专栏：面向对象面向对象 C++【Educoder实训】头歌实践教学平台

任务描述

本关任务： 将直接插入排序、直接选择排序、冒泡排序、顺序查找函数封装到数组类 Array 中，作为成员函数。

相关知识

为了完成本关任务，你需要掌握：

相关排序和查找算法的原理
C++ 类与成员函数的定义
数组作为类的成员变量的处理

1. 相关排序和查找算法的原理

直接插入排序：

原理：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，就像人们按大小顺序整理手中的扑克牌一样。具体过程是从第二个元素开始，依次将每个元素与前面已排好序的元素从后往前进行比较，找到合适的位置插入该元素，使得插入后前面的序列依然有序。
示例代码（非成员函数形式，便于理解原理）：

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

直接选择排序：

原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾，以此类推，直到所有元素均排序完毕。
示例代码（非成员函数形式）：

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex!= i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

冒泡排序：

原理：它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来，走访数列的工作是重复地进行直到没有再需要交换的元素为止，即排序完成。就好像水里的气泡，轻的（小的数值）会逐渐往上冒（移到数列前面）。
示例代码（非成员函数形式）：

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

顺序查找：

原理：从数组的第一个元素开始，逐个元素与要查找的目标元素进行比较，直到找到目标元素或者遍历完整个数组为止。它是一种简单直观的查找方法，适用于无序数组等各种情况。
示例代码（非成员函数形式）：

int sequentialSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;  // 表示未找到目标元素
}

2. C++ 类与成员函数的定义

类的基本结构：

class Array {
private:
    int* data;  // 可以用来存储数组元素的指针，这里假设存储整数数组
    int size;   // 数组的大小
public:
    Array(int arr[], int n);  // 构造函数声明，用于初始化数组对象
    // 在这里声明要封装的排序和查找成员函数，如
    void insertionSort();
    void selectionSort();
    void bubbleSort();
    int sequentialSearch(int target);
};

需要了解如何定义一个 Array 类，包括类的声明部分（一般在 .h 文件中定义类的成员变量和成员函数的声明）和类的实现部分（一般在 .cpp 文件中实现成员函数的具体代码逻辑）。例如：

成员函数的定义与调用：

要掌握如何在类的实现文件中正确地定义这些成员函数，并且在函数内部能够正确地访问类的私有成员变量（如通过 this 指针来访问当前对象的 data 和 size 等成员）。例如，插入排序成员函数在类中的实现大致如下：

void Array::insertionSort() {
    for (int i = 1; i < this->size; i++) {
        int key = this->data[i];
        int j = i - 1;
        while (j >= 0 && this->data[j] > key) {
            this->data[j + 1] = this->data[j];
            j--;
        }
        this->data[j + 1] = key;
    }
}

同时，要清楚如何在类外部创建 Array 类的对象，并调用这些封装好的成员函数来对数组进行相应的排序或查找操作，比如：

int main() {
    int arr[] = {5, 3, 4, 6, 2};
    Array myArray(arr, 5);
    myArray.insertionSort();
    // 可以继续调用其他排序或查找成员函数进行相应操作
    return 0;
}

3. 数组作为类的成员变量的处理

内存管理方面：

当把数组作为类的成员变量时（如上面示例中的 data 指针成员），要考虑数组内存的分配与释放问题。在构造函数中，可能需要根据传入的数组大小动态分配内存来存储数组元素（一般使用 new 关键字），在类的析构函数中，要记得释放之前分配的内存（使用 delete[] 关键字），避免内存泄漏。例如：

Array::Array(int arr[], int n) {
    this->size = n;
    this->data = new int[n];
    for (int i = 0; i < n; i++) {
        this->data[i] = arr[i];
    }
}
Array::~Array() {
    delete[] this->data;
}

正确访问数组元素：

在成员函数中，要通过正确的方式使用类中的数组成员变量来实现排序和查找逻辑，比如使用 this->data[i] 的形式来访问数组中第 i 个元素，确保操作的是当前对象所关联的数组内容。

4. 函数参数传递与返回值处理

参数传递：
- 对于排序成员函数，一般不需要额外的参数传入（因为操作的对象就是类中存储的数组成员变量），但像顺序查找成员函数，就需要传入要查找的目标元素作为参数，要理解值传递、指针传递、引用传递等不同参数传递方式的特点及适用场景，选择合适的方式来传递参数，保证函数功能的正确实现且避免不必要的内存开销等问题。
返回值处理：
- 排序成员函数通常不需要返回值（因为它们直接对类中的数组进行原地排序操作），而顺序查找成员函数需要返回查找目标元素在数组中的索引，如果没找到则返回合适的值（如 -1）来表示查找失败，要正确处理这些返回值情况，以便在调用函数的地方根据返回值进行相应的后续操作。

综上所述，掌握以上这些知识要点，就可以顺利地将相关排序和查找函数封装到 Array 类中作为成员函数了。

编程要求

在右侧编辑器补充代码，实现 3 种排序算法。

测试说明

平台会对你编写的代码进行测试：
测试输入： 无；
预期输出： 1 2 3 6 8 1.9 3.2 4.1 5.6 A c g 2 -1

开始你的任务吧，祝你成功！

我的通关代码:

#include <iostream>
using namespace std;

template <class T>
class Array
{
    T* alist;
    int size;
public:
    Array() {size = 0;}
    Array(int sz) {alist = new T[sz]; size = sz;}
    Array(T a[], int sz) {
        size = sz;
        alist = new T[size];
        for (int i = 0; i < size; i ++)
            alist[i] = a[i];
    }
    ~Array() {size = 0; delete []alist;}
    int getSize() {return size;}
    T& operator [](int i) {return alist[i];}
    void output(){
        for(int i = 0; i < size; i ++)
            cout << alist[i] << " ";
        cout << endl;
    }
    void insertSort();
    void selectSort();
    void bubbleSort();
    int seqSearch(T key);
};

/**********  Begin  **********/

// 在数组中顺序查找第一个key元素，若找到则返回其索引值（是数组中第几个，从0算起），找不到则返回-1
template <class T>
int Array<T>::seqSearch(T key) {
    for(int i = 0;i < size;i++){
        if(alist[i] == key){
            return i;
        }
    }
    return -1;
}

// 插入排序
template <class T>
void Array<T>::insertSort(){
    T temp;
    int j;
    for(int i = 1;i < size;i++){
        temp = alist[i];
        for(j = i;j > 0 && temp < alist[j - 1];j--){
            alist[j] = alist[j - 1];
        }
        alist[j] = temp;
    }
}

// 选择排序
template <class T>
void Array<T>::selectSort(){
    int m;
    T temp;
    for(int i = 0;i < size - 1;i++){
        m=i;
        for(int j = i + 1;j < size;j++){
            if(alist[j] < alist[m]){
                m = j;
            }
        }
        if(m != i){
            temp = alist[i];
            alist[i] = alist[m];
            alist[m] = temp;
        }
    }
}

template <class T>
void Array<T>::bubbleSort(){
    T temp;
    for(int i = 0;i < size - 1;i++){
        for(int j = 0;j < size - 1 - i;j++){
            if(alist[j] > alist[j + 1]){
                temp = alist[j];
                alist[j] = alist[j + 1];
                alist[j + 1] = temp;
            }
        }
    }
}
/**********  End  **********/

int main()
{
    int a[5] = {3, 6, 1, 8, 2};
    Array<int> iArray(a, 5);
    iArray.insertSort();
    iArray.output();

    double d[4] = {4.1, 3.2, 5.6, 1.9};
    Array<double> dArray(d, 4);
    dArray.selectSort();
    dArray.output();

    char c[3] = {'g', 'c', 'A'};
    Array<char> cArray(c, 3);
    cArray.bubbleSort();
    cArray.output();

    int b[4] = {-1, 2, 0, 5};
    Array<int> bArray(b, 4);
    cout<< bArray.seqSearch(0)<< endl;
    cout<< bArray.seqSearch(3)<< endl;
    return 0;
}