C++类模板及相关排序

建立一个顺序表类模板，封装数据成员，成员函数。再添加一些成员函数用直接插入排序算法、对半插入排序算法、冒泡排序算法实现降序排序。再用一个归并函数将两个已升序排好的数组，合并为一个升序排序的数组。

该回答引用ChatGPT
好的，下面是代码实现及详细分析：

cpp
#include 
#include 
using namespace std;
template 
class SeqList {
private:
    vector data; // 存储数据的vector
    int length; // 当前长度
    int capacity; // 最大容量
public:
    SeqList(int cap = 10) : length(0), capacity(cap) {
        data.resize(cap);
    }
    ~SeqList() {}
    // 插入元素
    bool insert(int pos, T val) {
        if (pos < 0 || pos > length || length == capacity) {
            return false;
        }
        for (int i = length - 1; i >= pos; i--) {
            data[i + 1] = data[i];
        }
        data[pos] = val;
        length++;
        return true;
    }
    // 直接插入排序
    void insertSort() {
        for (int i = 1; i < length; i++) {
            T temp = data[i];
            int j = i - 1;
            while (j >= 0 && data[j] < temp) {
                data[j + 1] = data[j];
                j--;
            }
            data[j + 1] = temp;
        }
    }
    // 对半插入排序
    void halfInsertSort() {
        for (int i = 1; i < length; i++) {
            T temp = data[i];
            int left = 0, right = i - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (data[mid] < temp) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            for (int j = i - 1; j >= left; j--) {
                data[j + 1] = data[j];
            }
            data[left] = temp;
        }
    }
    // 冒泡排序
    void bubbleSort() {
        for (int i = 0; i < length - 1; i++) {
            for (int j = 0; j < length - i - 1; j++) {
                if (data[j] < data[j + 1]) {
                    swap(data[j], data[j + 1]);
                }
            }
        }
    }
    // 归并排序
    void merge(SeqList& list1, SeqList& list2) {
        int i = 0, j = 0, k = 0;
        while (i < list1.length && j < list2.length) {
            if (list1.data[i] < list2.data[j]) {
                data[k++] = list1.data[i++];
            } else {
                data[k++] = list2.data[j++];
            }
        }
        while (i < list1.length) {
            data[k++] = list1.data[i++];
        }
        while (j < list2.length) {
            data[k++] = list2.data[j++];
        }
        length = k;
    }
    // 输出元素
    void print() {
        for (int i = 0; i < length; i++) {
            cout << data[i] << " ";
        }
        cout << endl;
    }
};
int main() {
    SeqList list(10);
    list.insert(0, 5);
    list.insert(1, 3);
    list.insert(2, 8);
    list.insert(3, 1);
    list.insert(4, 6);
    list.insert(5, 2);
    list.insert(6, 9);
    list.insert(7, 4);
    list.insert(8, 7);
    list.insert(9, 0);
    cout << "原始数据：";
    list.print();
    cout << "直接插入排序：";
    list.insertSort();
    list.print();
    cout << "对半插入排序：";
    list.halfInsertSort();
    list.print();
    cout << "冒泡排序：";
    list.bubbleSort();
    list.print();
    SeqList list1(5);
    list1.insert(0, 1);
    list1.insert(1, 3);
    list1.insert(2, 5);
    SeqList list2(5);
    list2.insert(0, 2);
    list2.insert(1, 4);
    list2.insert(2, 6);
    cout << "归并排序：";
    SeqList list3(10);
    list3.merge(list1, list2);
    list3.print();
    return 0;
}

首先，我们定义了一个顺序表类模板 `SeqList`，其中包含了数据成员 `data`、`length` 和 `capacity`，以及成员函数 `insert`、`insertSort`、`halfInsertSort`、`bubbleSort`、`merge` 和 `print`。
其中，`insert` 函数用于在指定位置插入元素，`insertSort` 函数用于实现直接插入排序算法，`halfInsertSort` 函数用于实现对半插入排序算法，`bubbleSort` 函数用于实现冒泡排序算法，`merge` 函数用于将两个已升序排好的数组合并为一个升序排序的数组，`print` 函数用于输出元素。
在 `main` 函数中，我们创建了一个 `SeqList` 类型的对象 `list`，并插入了一些元素。然后，分别调用了 `insertSort`、`halfInsertSort`、`bubbleSort` 和 `merge` 函数，最后输出排序后的结果。
需要注意的是，我们在 `SeqList` 类模板中使用了 `vector` 来存储数据，这是因为 `vector` 具有动态扩容的特性，可以方便地实现动态数组的功能。同时，我们也可以通过 `resize` 函数来设置 `vector` 的大小，以达到初始化的目的。
以上就是本题的详细分析和代码实现，希望能对你有所帮助。

以下是一个简单的顺序表类模板，包括封装数据成员和成员函数：

template<typename T>
class SeqList {
private:
    T* data;
    int length;
    int maxSize;
public:
    SeqList(int size = 10) {
        data = new T[size];
        length = 0;
        maxSize = size;
    }

    ~SeqList() {
        delete[] data;
    }

    void insert(T x, int pos) {
        if (pos < 0 || pos > length) {
            return;
        }
        if (length >= maxSize) {
            T* oldData = data;
            data = new T[maxSize * 2];
            for (int i = 0; i < length; i++) {
                data[i] = oldData[i];
            }
            delete[] oldData;
            maxSize *= 2;
        }
        for (int i = length; i > pos; i--) {
            data[i] = data[i - 1];
        }
        data[pos] = x;
        length++;
    }

    void remove(int pos) {
        if (pos < 0 || pos >= length) {
            return;
        }
        for (int i = pos; i < length - 1; i++) {
            data[i] = data[i + 1];
        }
        length--;
    }

    int search(T x) {
        for (int i = 0; i < length; i++) {
            if (data[i] == x) {
                return i;
            }
        }
        return -1;
    }

    void print() {
        for (int i = 0; i < length; i++) {
            cout << data[i] << " ";
        }
        cout << endl;
    }
};

接下来，我们可以添加一些成员函数来实现排序算法。以下是直接插入排序算法和对半插入排序算法：

```c++

template<typename T>
void SeqList<T>::insertSortDesc() {
    for (int i = 1; i < length; i++) {
        T temp = data[i];
        int j = i - 1;
        while (j >= 0 && data[j] < temp) {
            data[j + 1] = data[j];
            j--;
        }
        data[j + 1] = temp;
    }
}

template<typename T>
void SeqList<T>::binaryInsertSortDesc() {
    for (int i = 1; i < length; i++) {
        T temp = data[i];
        int left = 0, right = i - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (data[mid] < temp) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        for (int j = i - 1; j >= left; j--) {
            data[j + 1] = data[j];
        }
        data[left] = temp;
    }
}

然后，我们可以实现冒泡排序算法：

template<typename T>
void SeqList<T>::bubbleSortDesc() {
    bool flag = true;
    for (int i = 0; i < length - 1 && flag; i++) {
        flag = false;
        for (int j = length - 1; j > i; j--) {
            if (data[j] > data[j - 1]) {
                T temp = data[j];
                data[j] = data[j - 1];
                data[j - 1] = temp;
                flag = true;
            }
        }
    }
}

最后，我们可以实现一个归并函数来合并两个已升序排好的数组：

template<typename T>
SeqList<T> merge(SeqList<T>& list1, SeqList<T>& list2) {
    SeqList<T> result(list1.length + list2.length);
    int i = 0, j = 0, k = 0;
    while (i < list1.length && j < list2.length) {
        if (list1.data[i] < list2.data[j]) {
            result.data[k++] = list1.data[i++];
        } else {
            result.data[k++] = list2.data[j++];
        }
    }
    while (i < list1.length) {
        result.data[k++] = list1.data[i++];
    }
    while (j < list2.length) {
        result.data[k++] = list2.data[j++];
    }
    result.length = k;
    return result;
}

```
一定要看啊！

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/234926
• 你也可以参考下这篇文章：C++不是类的成员未知重写说明符已经定义或声明成员函数没有重载函数可以接受跳过明显的函数体意外的标记位于前的问题解决
• 除此之外, 这篇博客: C++数据结构二叉树统计总结点个数，叶子结点个数，单分支结点个数，双分支结点个数。中的       很多书上其实都有提到和该算法。但是经过自己的学习我自己想到一个算法。算是结合了其中的优点吧。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  
• • 算法描述：该算法递归去统计结点个数。值得一提的是该系列算法都是统计根结点以下的符和条件的结点的个数进行了加和。免去的设置全局变量和void的类型的函数。

  int	CountNodes(LBTree* lbt)
  {
  	int n = 0;
  	if (lbt != NULL)
  	{
  		++n;
  		n += CountNodes(lbt->lchild);
  		n += CountNodes(lbt->rchild);
  	}
  	return n;
  }
  
  int CountLeaves(LBTree* lbt)
  {
  	int n = 0;
  	if (lbt != NULL)
  	{
  		if (lbt->lchild == NULL && lbt->rchild == NULL)
  			++n;
  		n += CountLeaves(lbt->lchild);
  		n += CountLeaves(lbt->rchild);
  	}
  	return n;
  }
  
  int CountSingleNode(LBTree* lbt)
  {
  	int n = 0;
  	if (lbt != NULL)
  	{
  		if ((lbt->lchild == NULL && lbt->rchild != NULL) || (lbt->rchild == NULL && lbt->lchild != NULL))
  			++n;
  		n += CountSingleNode(lbt->lchild);
  		n += CountSingleNode(lbt->rchild);
  	}
  	return n;
  }
  
  int	CountDoubleNode(LBTree* lbt)
  {
  	int n = 0;
  	if (lbt != NULL)
  	{
  		if (lbt->lchild != NULL && lbt->rchild != NULL)
  			++n;
  		n += CountDoubleNode(lbt->lchild);
  		n += CountDoubleNode(lbt->rchild);
  	}
  	return n;
  }

   

#include<iostream>
using namespace std;
const int Maxsize=100;
template<class T>
class SeqListClass
{
private:
    T *data;//存放顺序表中的元素
    int length;//存放顺序表的长度
public:
    SeqListClass();//构造函数
    ~SeqListClass();//析构函数
    void CreateList(T a[],int n);//由数组a中的元素建造顺序表
    void DispList();//输出顺序表中的元素
    int ListLength();//求顺序表的长度
    bool GetElem(int i,T &e);//求顺序表第i号的元素值
    int LocateElem(T e);//求顺序表中第一个元素e的序号
    bool ListInsert(int i,T e);//在i号插入元素值e
    bool ListDelete(int i);//删除顺序表中第i号元素
    void ReverseList(SeqListClass<T> &L);//翻转顺序表
};
template<class T>
SeqListClass<T>::SeqListClass()//初始化顺序表
{
    data=new T[Maxsize];
    length=0;
}
template<class T>
SeqListClass<T>::~SeqListClass()
{
    delete []data;
    cout<<"顺序表成功销毁ヾ(￣▽￣)Bye~Bye~"<<endl;
}
template<class T>
void SeqListClass<T>::CreateList(T a[],int n)
{
    int i;
    for(i=0;i<n;i++)
        data[i]=a[i];
    length=i;
}
template<class T>
void SeqListClass<T>::DispList()
{
    cout<<"Out:"<<endl;
    for(int i=0;i<length;i++)
        cout<<data[i]<<" ";
    cout<<endl;
}
template<class T>
int SeqListClass<T>::ListLength()
{
    return length;
}
template<class T>
bool SeqListClass<T>::GetElem(int i,T &e)
{
    if(i<0||i>length)
        return false;
        e=data[i-1];//i号元素的下标为i-1
    return true;
}
template<class T>
int SeqListClass<T>::LocateElem(T e)
{
    int i;
    for(i=0;i<length;i++)
    {
        if(data[i]==e)
            return i+1;
    }
    return 0;//找完顺序表但未找到该元素值
}
template<class T>
bool SeqListClass<T>::ListInsert(int i,T e)
{
    if(i<0||i>length)
        return false;
    for(int j=length;j>=i;j--)
        data[j]=data[j-1];
    data[i-1]=e;
    length++;
    return true;
}
template<class T>
bool SeqListClass<T>::ListDelete(int i)
{
    if(i<0||i>length)
        return false;
    for(int j=i-1;j<length-1;j++)
        data[j]=data[j+1];//跟数组元素的删除是一样的
        length--;//删除一个元素，长度减一
        return true;
}
template<class T>
void SeqListClass<T>::ReverseList(SeqListClass<T> &L)
{
    T temp;
    for(int j=0;j<L.length/2;j++)
    {
        //三值交换法
        temp=L.data[j];
        L.data[j]=L.data[length-j-1];
        L.data[length-j-1]=temp;
    }
}
int main()
{
    cout<<"------------------------------------顺序表-----------------------------"<<endl;
    SeqListClass<int>sqList;
    int num;
    cout<<"请输入要创建的顺序表的长度~(～￣▽￣)～"<<endl;
    cin>>num;
    if(num<=0)
    {
        cout<<"创建失败!"<<endl;
    return 0;
    }
    cout<<"创建长度为:"<<num<<"的顺序表成功(*￣▽￣*)ブ"<<endl;
    int arr[num]={0};
    for(int i=0;i<num;i++)
    {
        cout<<"请输入第"<<i+1<<"元素的值:";
        cin>>arr[i];
    }
    sqList.CreateList(arr,num);
    sqList.DispList();
    cout<<"sqList length is:"<<sqList.ListLength()<<endl;
    int a;
    sqList.GetElem(2,a);
    cout<<"The 2 local is elem:"<<a<<endl;
    cout<<"The elem 5 local is:"<<sqList.LocateElem(5)<<endl;
    sqList.ListInsert(2,23);
    sqList.DispList();
    sqList.ListDelete(1);
    sqList.DispList();
    sqList.ReverseList(sqList);
    sqList.DispList();
    return 0;
}

以下答案由GPT-3.5大模型与博主波罗歌共同编写：
首先，定义一个顺序表类模板，包含数据成员和成员函数，代码如下：

template <typename T>
class SeqList {
private:
    T* data;
    int size, length;
    
    void swap(T& a, T& b) {
        T temp = a;
        a = b;
        b = temp;
    }
    
public:
    SeqList(int maxSize=100) {
        data = new T[maxSize];
        size = maxSize;
        length = 0;
    }
    
    ~SeqList() {
        delete[] data;
    }
    
    int find(T x) {
        for(int i=0; i<length; i++) {
            if(data[i] == x)
                return i;
        }
        return -1;
    }
    
    bool insert(int index, T x) {
        if(index<0 || index>length || length==size)
            return false;
        for(int i=length-1; i>=index; i--) {
            data[i+1] = data[i];
        }
        data[index] = x;
        length++;
        return true;
    }
    
    bool remove(int index) {
        if(index<0 || index>=length)
            return false;
        for(int i=index; i<length-1; i++) {
            data[i] = data[i+1];
        }
        length--;
        return true;
    }
    
    T& operator[](int i) {
        return data[i];
    }
    
    int getLength() {
        return length;
    }
    
    void print() {
        for(int i=0; i<length; i++) {
            cout << data[i] << " ";
        }
        cout << endl;
    }
};

代码中，定义了一个顺序表类模板SeqList，包含数据成员data、size、length，以及成员函数find、insert、remove、operator[]等等。

接下来，实现三种排序算法：

1. 直接插入排序

template <typename T>
void InsertSort(SeqList<T>& L) {
    for(int i=1; i<L.getLength(); i++) {
        if(L[i] > L[i-1]) {
            T temp = L[i];
            int j;
            for(j=i-1; j>=0 && temp>L[j]; j--) {
                L[j+1] = L[j];
            }
            L[j+1] = temp;
        }
    }
}

2. 对半插入排序

template <typename T>
void HalfInsertSort(SeqList<T>& L) {
    for(int i=1; i<L.getLength(); i++) {
        if(L[i] > L[i-1]) {
            T temp = L[i];
            int low=0, high=i-1;
            while(low <= high) {
                int mid = (low + high) / 2;
                if(temp > L[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            }
            for(int j=i-1; j>=high+1; j--) {
                L[j+1] = L[j];
            }
            L[high+1] = temp;
        }
    }
}

3. 冒泡排序

template <typename T>
void BubbleSort(SeqList<T>& L) {
    for(int i=0; i<L.getLength()-1; i++) {
        bool flag = false;
        for(int j=0; j<L.getLength()-1-i; j++) {
            if(L[j] < L[j+1]) {
                L.swap(L[j], L[j+1]);
                flag = true;
            }
        }
        if(!flag)
            break;
    }
}

最后，实现一个归并函数，将两个升序排好的数组合并成一个升序排列的数组。

template <typename T>
void Merge(SeqList<T>& L1, SeqList<T>& L2, SeqList<T>& L) {
    int i=0, j=0, k=0;
    while(i < L1.getLength() && j < L2.getLength()) {
        if(L1[i] < L2[j])
            L[k++] = L1[i++];
        else
            L[k++] = L2[j++];
    }
    while(i < L1.getLength())
        L[k++] = L1[i++];
    while(j < L2.getLength())
        L[k++] = L2[j++];
}

完整代码如下：
如果我的回答解决了您的问题，请采纳！