数据结构——线性表（顺序存储结构（数组））

线性表的两组物理结构——顺序存储结构和链式存储结构

线性表的顺序存储结构：用一段地址连续的存储单员依次存储线性表的数据元素（用数组来存储的线性表就是顺序表）

#一个线性表的抽象类 #include<iostream> class linerList{ public: virtual ~linerList() {}; 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;//把theElement插入线性表中索引为theIndex的位置 }

改变一个一维数组的长度

template<class T> void changedLength1D(T* a, int oldLength, int newLength) { if (newLength<0) throw illegalParameterValue("new length must be >=0"); T* temp=new T[newLength]; int number=min(oldLength,newLength);//#include <algorithm> copy(a,a+number,temp);//将a复制到temp//#include <algorithm> delete [] a; a=temp;//指针被free或者delete后，没有置为NULL, free和delete只是把指针所指向的内存给释放掉， //并没有把指针本身干掉，此时指针指向的是“垃圾”内存。释放后的指针应该被置为NULL.否则造成内存泄漏 } #类arrayList是一个具体类，所以他必须实现抽象类linearList的所有方法，并且还包含基类没有的方法。capacity(给出数组长度)和checkIndex. template<class T> class arrayList : public linearList<T> { friend ostream& operator<<(ostream&, const arrayList<T>& x); public: //构造函数，复制构造函数和析构函数 arrayList(int initialCapicity = 10); arrayList(const arrayList<T>&); ~arrayList() {delete [] element;} //ADT方法 bool empty() const {return listSize == 0;} int size() const {return listSize;} T& get(int index)const ; int indexOf(const T& theElement) const; void erase(int theIndex); void insert(int theIndex, const T& theElement ); //其他方法 int capacity（）const {redturn arrayLength;} projected: void checkIndex(int theIndex) const;//若索引无效则抛出异常 T* element;//存储线性表元素的一维数组 int arrayLength;//一维数组的容量 int listSize;//线性表元素个数 }

类arrayList的构造函数和复制构造函数

template<class T> arrayList<T>::arraydList (int initialCapacity) { if(initialCapacity<1) {ostringstream s; s<<"Initial capacity="<<initialCapacity<<"Must be>0"; throw illegalParameterValue(s.str()); } arrayLength = initialCapacity; element = new T[arrayLength]; listSize = 0; } template<class T> arrayList<T>::arrayList (const arrayList<T>& theList ) { arrayLength = theList.arrayLength; listSize = theList.listSize; element = new T[arrayLength]; copy(theList.element,theList.element + listSize,element); }

arrayList的基本方法

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 { checkIndex(theIndex); return element[theIndex]; } template<class T> int arrayList<T>::indexOf(const T& theElement) const { int theIndex = (int)(find(element,element+listSize,theElement)-element) if(theIndex == listSize) //没有找到 return -1; else return theIndex; } template<class T> void arrayList<T>::erase(int theIndex) { checkIndex(theIndex); //有效索引，移动其索引大于theIndex的元素 copy(element+theIndex+1,element+listSize,element+theIndex); element[--listSize].~T();//调用析构函数 } template<class T> void arrayList<T>::insert(int theIndex, const T& theElement ) { if(theIndex < 0 || theIndex > listSize) {//无效索引 ostringstream s; s << "index=" << theIndex << "size=" << listSize; throw illegalIndex(s.str()); } //有效索引，确定数组是否已满 if(listSize == arrayLength) {//数组空间已满，数组长度增倍 changeLength1D(element,arrayLength,arrayLength*2); arrayLength *= 2; } //把元素向右移动一个位置 copy_backward(element+thedIndex,element+listSize,element+listSize+1); element[theIndex] = theElement; listSize++; } ostream& operator<<(ostream& s, const arrayList<T>& x) { copy(element,element+listSize,ostream_iterator<T>(s)) retrun s; }

泛型算法的 find： 在非string类型的容器里，可以直接找出所对应的元素. find函数需要几个参数：迭代器，下标值，所要找的元素 vector<int> a;find(a.begin(),a.end(),1); 这句话就表示从a的头开始一直到尾，找到第一个值为1的元素，返回的是一个指向该元素的迭代器。

find在string容器中用途比较广： find_first_of,find_last_of,find_not_first_of,find_not_last_of等等 在string类型中，需要的参数也有迭代器，下标和要找的字符串，这里要注意，是字符串，不能查找单个字符。 string a; find(a.begin(),a.end(),"asd") 这句话就是说，在a中找到第一个存在子串与"asd"子串相等的字符串的首地址。返回指向该字符串首地址的迭代器。 find_last_of则是找到最后一个， find_not_first_of是找出第一个不与“asd”相等的字符串的首地址

copy_backward算法与copy在行为方面相似，只不过它的复制过程与copy背道而驰，其复制过程是从最后的元素开始复制，直到首元素复制出来。也就是说，复制操作是从last-1开始，直到first结束。这些元素也被从后向前复制到目标容器中，从result-1开始，一直复制last-first个元素。 举个简单的例子：已知vector {0, 1, 2, 3, 4, 5}，现我们需要把最后三个元素（3, 4, 5）复制到前面三个（0, 1, 2）位置中，那我们可以这样设置：将first设置值3的位置，将last设置为5的下一个位置，而result设置为3的位置，这样，就会先将值5复制到2的位置，然后4复制到1的位置，最后3复制到0的位置我们可能会好奇，相对于普通的从第一个元素开始复制的 copy() 算法，copy_backward() 提供了哪些优势。 一个回答是，在序列重叠时，可以用 copy() 将元素复制到重叠的目的序列剩下的位置——也就是目的序列第一个元素之前的位置。如果想尝试用 copy() 算法将元素复制到同一个序列的右边，这个操作不会成功，因为被复制的元素在复制之前会被重写。如果想将它们复制到右边，可以使用 copy_backward()，只要目的序列的结束迭代器在源序列的结束迭代器的右边。图 2 说明了在将元素复制到重叠的序列的右边时，这两个算法的不同。