当前位置: 首页 > >

C++数据结构 顺序表(模板类实现)

发布时间:


?


#pragma once
#include
#include
#include
using namespace std;



template
class arrayList
{
? ?friend ostream& operator<<(ostream& out, const arrayList& x);?
? ?friend istream& operator>>(istream& in, const arrayList& x);
public:
?? ?arrayList(int intialCapacity = 10);
?? ?arrayList(const arrayList&);
?? ?~arrayList() { delete[] element; }


?? ?void changeLength(T*& a, int oldLength, int newLength);//改变数组长度
?? ?void insert(int theIndex,const T& theElement);//指定位置插入
?? ?void pushBack(const T& theElement);//尾插
?? ?void earse(int theIndex);//删除
?? ?void output() const;//输出
?? ?T& get(int theIndex);//获得指定位置的元素
?? ?bool empty();//判断是否为空
?? ?int ?indexOf(const T& theElement)const;获得指定元素的位置
private:
?? ?T* element;
?? ?int listSize;
?? ?int arrayLength;
};




?


#include"arraylist.h"


template
arrayList::arrayList(int intialcapacity)
{
?? ?arrayLength = intialcapacity;
?? ?element = new T[arrayLength];
?? ?listSize = 0;
}


template
arrayList::arrayList(const arrayList& theList)
{
?? ?arrayLength = theList.arrayLength;
?? ?listSize = theList.listSize;
?? ?element = new T[arrayLength];
?? ?copy(theList.element, theList.element + listSize, element);
}


template
void arrayList::changeLength(T*& a, int oldLength, int newLength) {
?? ?T *temp = new T[newLength];
?? ?int number = min(oldLength, newLength);
?? ?copy(a, a + number, temp);
?? ?a = temp;
}


template
void arrayList::insert(int theIndex, const T &theElement) {


?? ?if (listSize == arrayLength) {
? ? ? ? changeLength(element, arrayLength, 2 * arrayLength);
?? ? ? ?arrayLength *= 2;
? ? }
?? ?copy_backward(element + theIndex, element + listSize, element + listSize + 1);
?? ?element[theIndex] = theElement;
?? ?listSize++;
?? ?
}


template
void arrayList::earse(int theIndex) {


?? ?copy(element + theIndex + 1, element + listSize, element + theIndex);
?? ?element[--listSize].~T();
}


template
void arrayList::output()const {
?? ?copy(element, element + listSize, ostream_iterator(cout, " "));
?? ?cout << endl;


}


template
ostream& operator<<(ostream& out, const arrayList& x) {
?? ?x.output(out);
?? ?return out;
}


template
istream& operator>>(istream& in, const arrayList& x) {
?? ?x.output(in);
?? ?return in;
}


template
void arrayList::pushBack(const T& theElement) {


?? ?element[listSize++] = theElement;
}


template
bool arrayList::empty() {
?? ?if (listSize == 0) return 1;
?? ?else return 0;
}


template
?T& arrayList::get(int theIndex) {
?? ? return element[theIndex];
}


?template
?int arrayList::indexOf(const T& theElement) const{
?? ? int theIndex = (int)(find(element, element + listSize, theElement) - element);


?? ? if (theIndex == listSize) return -1;
?? ? else return ?theIndex;
?}



测试



int main() {
?? ?arrayList test(20);
?? ?test.pushBack(1);//尾插
?? ?test.pushBack(3);
?? ?test.pushBack(4);
?? ?test.pushBack(5);
?? ?test.pushBack(6);
?? ?test.insert(1, 2);//在第二个位置插入2
? ? test.output();
?? ?test.earse(0);
?? ?test.output();
?? ?cout<?? ?cout << endl;
?? ?cout<?? ?cout << endl;
?? ?cout<?? ?cout << endl;


?? ?
?? ?system("pause");
?? ?return 0;


}


?



?



友情链接: