C++利用动态数组实现顺序表（不限数据类型）

你的名字 2022-01-09 04:45 206阅读 0赞

通过类模板实现顺序表时，若进行比较和遍历操作，模板元素可以通过STL中的equal\_to仿函数实现，或者通过回调函数实现。若进行复制操作，可以采用STL的算法函数，也可以通过操作地址实现。关于回调函数和地址操作可以查看：[C语言利用动态数组实现顺序表（不限数据类型）][C]

主要功能：初始化，按照索引插入，删除，遍历，按索引返回元素，返回顺序表的容量，元素个数，及扩容操作。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <iostream>
      2 #include <vector>
      3 #include <string>
      4 
      5 
      6 using namespace std;
      7 
      8 //异常类
      9 class illegalParameterValue{
     10 public:
     11     illegalParameterValue();
     12     illegalParameterValue(string myMessage);
     13     void outPutMessage();
     14 private:
     15     string message;
     16 };
     17 
     18 illegalParameterValue::illegalParameterValue(){
     19     this->message = "illegal Parameter Value";
     20 }
     21 
     22 illegalParameterValue::illegalParameterValue(string myMessage){
     23     this->message = myMessage;
     24 }
     25 
     26 void illegalParameterValue::outPutMessage(){
     27     cout << this->message << endl;
     28 }
     29 
     30 //自定义顺序表类模板
     31 template<class T>
     32 class arrayList{
     33 public:
     34     //构造函数
     35     arrayList();
     36     arrayList(int iniCapacity);
     37     //复制构造函数
     38     arrayList(const arrayList<T>& theList);
     39     
     40     ~arrayList(){ delete[] element; }
     41 
     42     //ADT方法
     43     int mySize() const { return this->arrayListSize; }
     44     int myCapacity() const { return this->arrayListCapacity; }
     45     bool myEmpty() const { return arrayListSize == 0; }
     46 
     47     void myForeach() const;
     48     T& myGet(int index) const;
     49     void myErasePos(int index);
     50     void myEraseValue(T& theElement);
     51     void myInsert(int index, T& theElement);
     52     void output(ostream& out)const;
     53 private:
     54     int arrayListCapacity;
     55     int arrayListSize;
     56     T* element;
     57 };
     58 
     59 //构造函数，抛出异常时需要注意释放已创建的动态数据
     60 //如果抛出异常后，没有处理，会继续向上抛出，直到main函数处理
     61 //这里只是抛出，并没有捕获，因此不会显示message
     62 template <class T>
     63 arrayList<T>::arrayList(){}
     64 
     65 template <class T>
     66 arrayList<T>::arrayList(int iniCapacity){
     67     if (iniCapacity < 1)
     68     {
     69         string message = "the iniCapacity must be > 0";
     70         throw illegalParameterValue(message);
     71     }
     72     //throw 1; 
     73     arrayListCapacity = iniCapacity;
     74     element = new T[arrayListCapacity];
     75     arrayListSize = 0;
     76 }
     77 
     78 template <class T>
     79 arrayList<T>::arrayList(const arrayList<T>& theList){
     80     arrayListCapacity = theList.arrayListCapacity;
     81     arrayListSize = theList.arrayListSize;
     82     element = new T[arrayListCapacity];
     83     copy(theList.element, theList.element + arrayListSize, element);
     84 }
     85 
     86 //ADT方法
     87 //根据pos获取元素
     88 template<class T>
     89 T &arrayList<T>::myGet(int index)const{
     90     if (index < 0 || index >= arrayListSize){
     91         throw illegalParameterValue("the index is wrong.");
     92     }
     93     return element[index];
     94 }
     95 
     96 //按位置删除元素
     97 template <class T>
     98 void arrayList<T>::myErasePos(int index){
     99     if (index < 0 || index >= arrayListSize){
    100         throw illegalParameterValue("the index is wrong.");
    101     }
    102     //整体移动
    103     copy(element + index + 1, element + arrayListSize, element+ index );
    104     arrayListSize--;
    105 }
    106 
    107 //按值删除，仅删除第一次出现的位置,通过equal_to实现
    108 template <class T>
    109 void arrayList<T>::myEraseValue(T &theElement){
    110     
    111     for (int i = 0; i != arrayListSize; i++){
    112         if (equal_to<T>()(element[i], theElement)){
    113 
    114             cout << "mid" << endl;
    115             myErasePos(i);
    116             break;
    117         }
    118     }
    119 }
    120 
    121 //按位置插入元素，并扩容
    122 //这里有个非常隐蔽的错误,tmpElement通过new开辟内存空间
    123 //按道理需要释放tmpElement，但tmpElement的地址赋给element，两个变量指向同一个内存地址
    124 //element本身运行或下次进入条件就会析构掉，释放掉该块内存
    125 //如果提前释放掉tmpElement,则提前释放了该块内存，则会二次释放造成内存泄漏
    126 template <class T>
    127 void arrayList<T>::myInsert(int index, T &theElement){
    128     if (index < 0 || index > arrayListSize){
    129         throw illegalParameterValue("the index is wrong.");
    130     }
    131 
    132     if (arrayListSize >= arrayListCapacity){
    133         int tmpCapacity = arrayListCapacity * 2;
    134         T *tmpElement = new T[tmpCapacity];
    135         copy(this->element, this->element+this->arrayListSize, tmpElement);
    136         this->~arrayList(); 
    137         this->element = tmpElement;
    138         arrayListCapacity = arrayListCapacity * 2;
    139         //delete [] tmpElement;
    140     }
    141     copy_backward(this->element + index, this->element + arrayListSize, this->element + arrayListSize + 1);
    142     this->element[index] = theElement;
    143     arrayListSize++;
    144 }
    145 
    146 //输出函数
    147 template <class T>
    148 void arrayList<T>::output(ostream& out)const{
    149     copy(element, element + arrayListSize, ostream_iterator<T>(out, " "));
    150 }
    151 //重载<<
    152 template <class T>
    153 ostream& operator<<(ostream& out, const arrayList<T>& x){
    154     x.output(out);
    155     return out;
    156 }
    157 
    158 int main(){
    159     arrayList<int>mylist(2);
    160     int a1 = 1, a2 = 2, a3 = 3;
    161     
    162     mylist.myInsert(0, a1);
    163     mylist.myInsert(1, a2);
    164     mylist.myInsert(2, a3);
    165     
    166     mylist.myErasePos(0);
    167     int b = 2;
    168     mylist.myEraseValue(b);
    169     mylist.output(cout);
    170     cout << endl;
    171     
    172     cout << mylist.myGet(1) << endl;
    173     mylist.output(cout);
    174     
    175     system("pause");
    176     return 0;
    177 }

完整代码

**自定义顺序表类**

通过类模板自定义顺序表类，并在类内实现了返回顺序表的容量和元素个数等操作。

1 //自定义顺序表类模板
     2 template<class T>
     3 class arrayList{
     4 public:
     5     //构造函数
     6     arrayList();
     7     arrayList(int iniCapacity);
     8     //复制构造函数
     9     arrayList(const arrayList<T>& theList);
    10     
    11     ~arrayList(){ delete[] element; }
    12 
    13     //ADT方法
    14     int mySize() const { return this->arrayListSize; }
    15     int myCapacity() const { return this->arrayListCapacity; }
    16     bool myEmpty() const { return arrayListSize == 0; }
    17 
    18     void myForeach() const;
    19     T& myGet(int index) const;
    20     void myErasePos(int index);
    21     void myEraseValue(T& theElement);
    22     void myInsert(int index, T& theElement);
    23     void output(ostream& out)const;
    24 private:
    25     int arrayListCapacity;
    26     int arrayListSize;
    27     T* element;
    28 };

**初始化**

利用C++类模板实现顺序表，最重要的是构造函数及复制构造函数。顺序表中的元素移动，通过STL的内置copy算法实现。另外，类外实现成员函数时，函数需要加作用域，成员属性可以直接使用，如element等。

1 //构造函数，抛出异常时需要注意释放已创建的动态数据
     2 //如果抛出异常后，没有处理，会继续向上抛出，直到main函数处理
     3 //这里只是抛出，并没有捕获，因此不会显示message
     4 template <class T>
     5 arrayList<T>::arrayList(){}
     6 
     7 template <class T>
     8 arrayList<T>::arrayList(int iniCapacity){
     9     if (iniCapacity < 1)
    10     {
    11         string message = "the iniCapacity must be > 0";
    12         throw illegalParameterValue(message);
    13     }
    14     //throw 1; 
    15     arrayListCapacity = iniCapacity;
    16     element = new T[arrayListCapacity];
    17     arrayListSize = 0;
    18 }
    19 
    20 template <class T>
    21 arrayList<T>::arrayList(const arrayList<T>& theList){
    22     arrayListCapacity = theList.arrayListCapacity;
    23     arrayListSize = theList.arrayListSize;
    24     element = new T[arrayListCapacity];
    25     copy(theList.element, theList.element + arrayListSize, element);
    26 }

**索引元素**

1 //根据pos获取元素
    2 template<class T>
    3 T &arrayList<T>::myGet(int index)const{
    4     if (index < 0 || index >= arrayListSize){
    5         throw illegalParameterValue("the index is wrong.");
    6     }
    7     return element[index];
    8 }

**索引插入**

索引插入时，需要对边界条件进行判断，由STL内置copy\_backward算法实现顺序表元素的移动，因为需要将最右侧的元素先移动；copy算法是将最左侧的元素先移动。

如果顺序表容量过小时，则需要对顺序表进行扩容，扩容需要注意两点：（1）需要将element指向新的空间；（2）利用临时变量动态扩容时，需要注意释放时机和释放对象。

1 //按位置插入元素，并扩容
     2 //这里有个非常隐蔽的错误,tmpElement通过new开辟内存空间
     3 //按道理需要释放tmpElement，但tmpElement的地址赋给element，两个变量指向同一个内存地址
     4 //element本身运行或下次进入条件就会析构掉，释放掉该块内存
     5 //如果提前释放掉tmpElement,则提前释放了该块内存，则会二次释放造成内存泄漏
     6 template <class T>
     7 void arrayList<T>::myInsert(int index, T &theElement){
     8     if (index < 0 || index > arrayListSize){
     9         throw illegalParameterValue("the index is wrong.");
    10     }
    11 
    12     if (arrayListSize >= arrayListCapacity){
    13         int tmpCapacity = arrayListCapacity * 2;
    14         T *tmpElement = new T[tmpCapacity];
    15         copy(this->element, this->element+this->arrayListSize, tmpElement);
    16         this->~arrayList(); 
    17         this->element = tmpElement;
    18         arrayListCapacity = arrayListCapacity * 2;
    19         //delete [] tmpElement;
    20     }
    21     copy_backward(this->element + index, this->element + arrayListSize, this->element + arrayListSize + 1);
    22     this->element[index] = theElement;
    23     arrayListSize++;
    24 }

**索引删除**

判断边界条件时需要注意，动态数组的索引与位置相差1，因此当index == arrayListsize时，也会报错。另外，需要注意删除后，元素个数减一。

1 //按位置删除元素
     2 template <class T>
     3 void arrayList<T>::myErasePos(int index){
     4     if (index < 0 || index >= arrayListSize){
     5         throw illegalParameterValue("the index is wrong.");
     6     }
     7     //整体移动
     8     copy(element + index + 1, element + arrayListSize, element+ index );
     9     arrayListSize--;
    10 }

**按值删除**

按值删除，这里仅实现了删除元素第一次出现的位置，顺序表中元素间的比较通过STL关系运算符仿函数实现。另外，该函数不具有普适性，对int， float等大部分内置类型可以适用，对于结构体等数据类型，需要对函数进行重载，改变函数参数。如，age和name的class，仿函数不能直接对对象进行比较，只能是对某一个成员属性进行比较。C语言中是用回调函数，让用户自定义操作。

1 //按值删除，仅删除第一次出现的位置,通过equal_to实现
     2 template <class T>
     3 void arrayList<T>::myEraseValue(T &theElement){
     4     
     5     for (int i = 0; i != arrayListSize; i++){
     6         if (equal_to<T>()(element[i], theElement)){
     7 
     8             cout << "mid" << endl;
     9             myErasePos(i);
    10             break;
    11         }
    12     }
    13 }

**遍历**

对于类模板实现遍历操作， 需要用到STL中的输出流迭代器，另外需要对<<进行重载。C语言中是用回调函数进行操作的，需要用户根据数据类型自定义输出函数。

1 //输出函数
     2 template <class T>
     3 void arrayList<T>::output(ostream& out)const{
     4     copy(element, element + arrayListSize, ostream_iterator<T>(out, " "));
     5 }
     6 //重载<<
     7 template <class T>
     8 ostream& operator<<(ostream& out, const arrayList<T>& x){
     9     x.output(out);
    10     return out;
    11 }

转载于:https://www.cnblogs.com/qinguoyi/p/10413064.html

[C]: https://www.cnblogs.com/qinguoyi/p/10241670.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220109/71f04317587243809ba7fcb84232859d.png