course_data_structures/Data Structure Class 1/hw2/SeqList.h

#ifndef SEQLIST_H
#define SEQLIST_H
#include "PerfCounter.h"
#include <cassert>
#include <cstdlib>
#include <iostream>
using namespace std;

#include "LinearList.h"
;
const int defaultSize = 100;

template <class T>
class SeqList : public LinearList<T>
{
protected:
    T *data;                  //存放数组
    int maxSize;              //最大可容纳表项数
    int last;                 //当前已存表项的最后位置（从0开始）
    void reSize(int newSize); //改变data数组空间大小
public:
    PerfCounter counter;
    SeqList(int sz = defaultSize); //构造函数
    SeqList(SeqList<T> &L);        //复制构造函数
    ~SeqList()
    {
        delete[] data;
    } //析构函数
    int Size() const
    { //计算表的最大可容纳表项个数
        return maxSize;
    }
    int Length() const
    { //计算表长度
        return last + 1;
    }
    int Search(T &x) const;         //搜索x在表中的位置，函数返回表项序号
    int Locate(int i) const;        //定位第i个表项，函数返回表项序号
    bool getData(int i, T &x) const //取第i个表项的值 放入x中
    {
        if (i > 0 && i <= last + 1)
        {
            x = data[i - 1];
            return true;
        }
        else
        {
            return false;
        }
    }
    void setData(int i, T &x) //用x修改第i个表项的值
    {
        if (i > 0 && i <= last + 1)
        {
            data[i - 1] = x;
        }
    }
    bool Insert(int i, T &x); //插入x在第i个表项后
    bool Remove(int i, T &x); //删除第i个表项，通过x返回表项的值
    bool IsEmpty() const      //判断表空否，空返回true，否则返回false
    {
        return (last == -1) ? true : false;
    }
    bool IsFull() const //判断表满否，满返回true，否则返回false
    {
        return (last == maxSize - 1) ? true : false;
    }
    void Sort();   //排序
    void input();  //输入
    void output(); //输出
    SeqList<T> *operator=(SeqList<T> &L)
    {
        T value;
        maxSize = L.Size();
        last = L.Length() - 1;
        //delete []data;//先清空
        data = new T[maxSize];
        if (data == NULL)
        {
            cerr << "Memory allocating error!" << endl;
            exit(1);
        }
        for (int i = 1; i <= last + 1; i++)
        {
            L.getData(i, value);
            data[i - 1] = value;
        }
        return this;
    }

    ///增加的函数成员：/////////////////////////////////////////////////////////////////////////////////////////////////////////
    void OrderInsert(T &item);                        //有序顺序表的有序插入
    void OrderMake(T *d, int len);                    //构造有序顺序表
    void MoreRemove(T &x);                            //删除有序顺序表值为x的重复元素
    void Merge(const SeqList &La, const SeqList &Lb); //归并有序表La和Lb
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
};

template <class T>
SeqList<T>::SeqList(int sz)
{
    if (sz > 0)
    {
        maxSize = sz;
        last = -1;
        data = new T[maxSize];
        if (data == NULL)
        {
            cerr << "Memory allocating error!" << endl;
            exit(1);
        }
    }
}

template <class T> //复制构造函数
SeqList<T>::SeqList(SeqList<T> &L)
{
    T value;
    maxSize = L.last();
    last = L.Length() - 1;
    data = new T[maxSize];
    if (data == NULL)
    {
        cerr << "Memory allocating error!" << endl;
        exit(1);
    }
    for (int i = 1; i <= last + 1; i++)
    {
        L.getData(i, value);
        data[i - 1] = value;
    }
}

template <class T> //扩容至元素个数为newSize个
void SeqList<T>::reSize(int newSize)
{
    if (newSize <= 0)
    {
        cerr << "Invalid array index!" << endl;
        return;
    }
    if (newSize != maxSize)
    {
        T *newarray = new T[newSize];
        if (newarray == NULL)
        {
            cerr << "Memory allocating error!" << endl;
            exit(1);
        }
        int n = last + 1;
        T *srcptr = data;
        T *destptr = newarray;
        while (n--)
            *destptr++ = *srcptr++;
        delete[] data;
        data = newarray;
        maxSize = newSize;
    }
}

template <class T> //查找第一个值为x的元素下标
int SeqList<T>::Search(T &x) const
{
    for (int i = 0; i <= last; i++)
    {
        if (data[i] == x)
            return i + 1;
    }
    return 0;
}

template <class T> //定位第i个元素的位置
int SeqList<T>::Locate(int i) const
{
    if (i >= 1 && i <= last + 1)
        return i;
    else
        return 0;
}

template <class T> //在第i个元素后插x
bool SeqList<T>::Insert(int i, T &x)
{
    if (last == maxSize - 1)
        return false;
    if (i < 0 || i > last + 1)
        return false;
    for (int j = last; j >= i; j--)
        data[j + 1] = data[j];
    data[i] = x;
    last++;
    return true;
}

template <class T> //删除第i个元素并通过x返回
bool SeqList<T>::Remove(int i, T &x)
{
    if (last == -1)
        return false;
    if (i < 1 || i > last + 1)
        return false;
    x = data[i - 1];
    for (int j = i; j <= last; j++)
        data[j - 1] = data[j];
    last--;
    return true;
}

template <class T>
void SeqList<T>::Sort()
{ //冒泡排序:从小到大排序
    for (int i = 1; i <= last; i++)
    {
        for (int j = last; j >= i; j--)
        {
            if (data[j - 1] > data[j])
            {
                T tmp = data[j - 1];
                data[j - 1] = data[j];
                data[j] = tmp;
            }
        }
    }
}

template <class T> //从键盘逐个输入数据并建立顺序表
void SeqList<T>::input()
{
    cout << "开始建立顺序表，请输入表中元素个数：Input the size of the list which will be created:";
    while (1)
    {
        assert(cin >> last);
        last--;
        if (last < 0)
        {
            cout << "Input error, the last must be positive!\n";
            cout << "Input the last again:";
        }
        else if (last > maxSize - 1)
        {
            cout << "Input error, the last must be less than maxSize!\n";
            cout << "Input the last again:";
        }
        else
            break;
    }
    cout << "\nInput the data for each element to create the list:" << endl;
    for (int i = 0; i <= last; i++)
    {
        cout << "#" << i + 1 << ":";
        assert(cin >> data[i]);
    }
}

template <class T> //将顺序表输出到屏幕
void SeqList<T>::output()
{
    cout << "\nThe size of the list is:" << last + 1 << endl;
    for (int i = 0; i <= last; i++)
        cout << "#" << i + 1 << ":\t" << data[i] << endl;
}

/**
 * OrderInsert()在有序顺序表L中的合适位置插入数据元素x，使得L中的数据元素按值非递减有序排列。
 **/
template <class T>
void SeqList<T>::OrderInsert(T &item)
{
    //在这里加入实现第一个任务的程序。
    int pos = 0;
    for (; pos <= last; pos++)
    {
        counter.inc_cmp(1);
        if (data[pos] >= item)
            break;
    }
    for (int j = last; j >= pos; j--)
        data[j + 1] = data[j], counter.inc_mov(1);
    data[pos] = item, counter.inc_mov(1);
    last++;
}

/**
 * MoreRemove()在有序顺序表L中删除所有值为x的元素。
 **/
template <class T>
void SeqList<T>::MoreRemove(T &x)
{
    //在这里加入实现第三个任务的程序。
    //有序顺序表中可能有重复的x值，删除有序顺序表中重复的x值.
    //要求算法尽可能高效——尽可能减少移动元素的次数。
    //在你的readme.txt文件中描述算法，并分析算法的时间复杂度和空间复杂度。
    counter.inc_mem(8);
    int pos1 = -1, pos2 = -1;
    for (int i = 0; i <= last; i++)
    {
        counter.inc_cmp(1);
        if (data[i] == x)
        {
            pos2 = pos1 = i;
            while (data[pos2] == x) counter.inc_cmp(1), pos2++;
            break;
        }
    }
    if (pos1 == -1) return;
    int dif = pos2 - pos1;
    int newLast = last - dif;
    for (int i = pos1; i <= newLast; i++)
        data[i] = data[i + dif], counter.inc_mov(1);
    last = newLast, counter.inc_mov(1);
}

/**
 * OrderMake()从数组d依次取len个数据元素有序插入到有序顺序表L中。
 **/
template <class T>
void SeqList<T>::OrderMake(T *d, int len)
{
    for (int i = 0; i < len; i++)
        OrderInsert(d[i]);
}

//有序表的合并。认真学习该算法。
template <class T>
void SeqList<T>::Merge(const SeqList &La, const SeqList &Lb)
{
    int i, j;
    T xa, xb;
    last = -1;
    i = 1;
    j = 1;
    while (i <= La.Length() && j <= Lb.Length()) /*两个表中都有元素未比完*/
    {
        if (last == maxSize - 1)
            reSize(2 * maxSize);
        La.getData(i, xa);
        Lb.getData(j, xb);
        if (xa <= xb)
        {
            Insert(last + 1, xa);
            i++;
        }
        else
        {
            Insert(last + 1, xb);
            j++;
        }
    }
    while (i <= La.Length()) /*Lb表的元素已经比完*/
    {
        if (last == maxSize - 1) reSize(2 * maxSize);
        La.getData(i, xa);
        Insert(last + 1, xa);
        i++;
    }
    while (j <= Lb.Length()) /*La表的元素已经比完*/
    {
        if (last == maxSize - 1) reSize(2 * maxSize);
        Lb.getData(j, xb);
        Insert(last + 1, xb);
        j++;
    }
}
#endif