博客

/*
1创建一个线性表
2撤销一个线性表
3确定线性表是否为空
4确定线性表的长度
5按一个给定的索引查找一个元素
6按一个给定的元素查找其索引
7按一个给定的索引删除一个元素
8按一个给定的索引插入一个元素
9从左至右顺序输出线性表元素
*/
#ifndef arrayList_
#define arrayList_

#include<sstream>
#include<string>
#include<algorithm>
#include"linearList.h"
//#include"changeLengthlD.h"
#include"exception.h"
#include<iostream>
using namespace std;

template<class T>
class arrayList :public linearList<T>//arrayList为抽象类linearList的派生类
{
public:
    //构造函数，复制构造函数(即拷贝构造函数)，和析构函数
    arrayList(int initialCapacity = 10);
    arrayList(const arrayList<T>&);
    ~arrayList() { delete[] elemnet; }
    //ADT方法

    bool empty() const{ return listSize == 0; }//判断线性表是否为空
    int size() const{ return listSize; }//返回线性表中的元素个数
    T &get(int theIndex) const;//返回索引theIndex的值
    int indexOf(const T& theElement) const;//返回theElement的索引
    void insert(int theIndex, const T& theElement); //在索引theIndex处插入元素theElement
    void erase(int theIndex);//删除索引为theIndex 的值
    void output(ostream & out) const;
    void changeLength1D(T*& a, int oldLength, int newLength);
    //其他方法
    int capacity() const { return arrayLength; } //返回数组的长度
protected://可以被1.该类中的函数、2.子类的函数、以及3.其友元函数访问。
    //但不能被该类的对象访问。
    void checkIndex(int theIndex) const;
        //若索引theIndex无效 则抛出异常
    T* elemnet;//存储线性表元素的一维数组
    int arrayLength;//一维数组的容量
    int listSize;// 线性表元素个数

};
template<class T>
arrayList<T>::arrayList(int initialCapacity)
{//构造函数
    if (initialCapacity < 1)
    {
        ostringstream s;  //（ostringstream 向string 写入文件）创建对象s
        s << "initial capacity = " << initialCapacity << "must be > 0";
        throw illegalParameterValue(s.str());//s.str即将字符写入s
    }
    arrayLength = initialCapacity;
    listSize = 0;
    elemnet = new T[arrayLength];
}
template<class T>
arrayList<T>::arrayList(const arrayList<T>&theList)
{//复制构造函数(拷贝构造函数)
    arrayLength = theList.arrayLength;
    listSize = theList.listSize;
    elemnet = new T[arrayLength];
    copy(theList.elemnet, theList.elemnet + listSize, elemnet);//使用了STL 中函数copy
}

template <class T>
void arrayList<T>::checkIndex(int theIndex) const

{//确定索引的值在0到listSize-1之间
    if (theIndex < 0 || theIndex >= listSize)
    {
        ostringstream s;
        s << "index = " << theIndex << " size = " << listSize;
        throw illegalIndex(s.str());
    }
}

template<class T>
T& arrayList<T>::get(int theIndex) const
{//返回素索引为theIndex的元素
    checkIndex(theIndex);
    return elemnet[theIndex];
}
template<class T>
int arrayList<T>::indexOf(const T& theElement) const
{//返回元素theElement第一次出现时的索引
    //若该元素不存在，则返回-1
    for (int i = 0; i < listSize; i++)
    {
        if (elemnet[i] == theElement)
        {
            return i;
            break;
        }
    }
    return -1;
    //等价于
    //查找元素theElement
    //int theIndex = (int)(find(elemnet, elemnet + listSize, theElement) - elemnet);//find为STL中的函数 查找元素

    /*确定元素是否找到
    if (theIndex == listSize){
        没有找到
        return -1;
    }
    else return theIndex;*/

}
template<class T>
void arrayList<T>::changeLength1D(T*& a, int oldLength, int newLength)
{
    if (newLength < 0)
        throw illegalParameterValue("new length must be >= 0");

    T* temp = new T[newLength];              // new array
    int number = min(oldLength, newLength);  // number to copy
    copy(a, a + number, temp);
    delete[] a;                             // deallocate old memory
    a = temp;
}

template<class T>
void arrayList<T>::erase(int theIndex)
{//删除其索引为theIndex的元素
    //如果改元素不存在，则抛出异常
    checkIndex(theIndex);
    /*for (int i = theIndex + 1; i < listSize; i++)
    {
    elemnet[i - 1] = elemnet[i];
    }
    listSize--;
    */
    //等价于
    copy(elemnet + theIndex + 1, elemnet + listSize, elemnet + theIndex);//STLcopy 函数
    elemnet[--listSize].~T();

}
template<class T>
void arrayList<T>::insert(int theIndex, const T& theElement)
{//在索引theIndex处插入元素theElement
    if (theIndex<0 || theIndex>listSize)
    {//无效索引
        ostringstream s;
        s << "index = " << theIndex << "size = " << listSize;
        throw illegalIndex(s.str());
    }
    //有效数组 确定数组是否已满 
    if (listSize == arrayLength)
    {//数组空间已满，数组长度倍增
        changeLength1D(elemnet, arrayLength, 2 * arrayLength);
        arrayLength *= 2;
    }

    //把元素向右移动一个位置

    for (int i = listSize-1; i >=theIndex; i--)
    {
        elemnet[i + 1] = elemnet[i];
    }
    //其等价于
    //copy_backward(elemnet + theIndex, elemnet + listSize, elemnet + listSize + 1);//STL copy_backward 函数 从最后一个元素向前复制

    elemnet[theIndex] = theElement;
    listSize++;
}

template<class T>
void arrayList<T>::output(ostream& out) const
{//把线性表插入输出流>
    copy(elemnet, elemnet + listSize, ostream_iterator<T>(cout, " "));

}
//重载<<
template<class T>
ostream& operator<<(ostream& out, const arrayList<T>&x)
{
    x.output(out);
    return out;
}

#endif;

linearList.h 源代码//抽象类（可省）

#ifndef linearList_
#define linearList_
#include <iostream>

using namespace std;
template <class T>
class linearList
{
public:
    virtual ~linearList(){};
    virtual bool empty() const = 0;
    //返回TRUE 当且仅当线性表为空
    virtual int size() const = 0;
    //返回线性表的元素个数
    virtual T& get(int theIndex) const = 0;
    //返回索引theIndex的值
    virtual int indexOf(const T& theElement)const = 0;
    //返回元素theElement第一次出现时的索引
    virtual void erase(int theIndex) = 0;
    //删除索引为theIndex的元素
    virtual void insert(int theIndex, const T& theElement) = 0;
    //把元素插入线性表中索引为theIndex的位置上
    virtual void output(ostream& out)const = 0;
    //把线性表差如输出流out
};
#endif

异常类的定义exception.h

#ifndef myExceptions_
#define myExceptions_
#include <string>

using namespace std;
class illegalParameterValue

{
    //friend ostream &operator << (ostream &out, const illegalParameterValue &ill);
public:
    illegalParameterValue(string theMessage = "Illegal parameter value")
    {
        message = theMessage;
    }
    void outputMessage() { cout << message << endl; }
private:
    string message;
};

class illegalIndex
{
public:
    illegalIndex(string theMessage = "Illegal index")
    {
        message = theMessage;
    }
    void outputMessage() { cout << message << endl; }
private:
    string message;
};
#endif