锐客网

  1. 首页 > it技术 > >

数据结构|笔记四（线性表——数组描述）

数据结构

线性表

  • 定义：有序表，元素按照一定顺序形成的有序集合。
  • 数组描述的线性表：
    1、代码：
#pragma warning(disable:4996)#include #include #include using namespace std; typedef struct{ int a; int b; } Mytype; template 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; //把theElement插入线性表中索引为theIndex的位置 virtual void output(ostream& out) const = 0; //把线性表插入的输出流out }; template class arrayList : public linearList { public: //构造函数、复制构造函数、析构函数 arrayList(int initialCapacity = 10); arrayList(const arrayList&); ~arrayList() { delete[] element; }//ADT方法 bool empty() const; int size() const; T& get(int theIndex) const; int indexOf(const T& theElement) const; void erase(int theIndex); void insert(int theIndex, const T& theElement); void output(ostream& out) const; public: void changeLength1D(T*& a, int oldLength, int newLength); friend ostream& operator<<(ostream& out, const arrayList& x); void checkIndex(int theIndex) const; private: int listSize; //线性表的元素个数 int arrayLength; //一维数组的容量 T*element; //存储线性表元素的一维数组 }; template arrayList::arrayList(int initialCapacity) {//构造函数 arrayLength = initialCapacity; 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 bool arrayList::empty() const { return (listSize==0 ? true : false); }template int arrayList::size() const { return listSize; }template T& arrayList::get(int theIndex) const { checkIndex(theIndex); return element[theIndex]; }template int arrayList::indexOf(const T& theElement) const { //指向theElement的指针与数组首指针的差值 int theIndex = (int)(find(element, element + listSize, theElement) - element); return (theIndex == listSize ? -1 : theIndex); }template void arrayList::erase(int theIndex) { checkIndex(theIndex); //将theIndex后面的元素依次前移一位，通过占据theIndex元素的位置将其覆盖 copy(element + theIndex + 1, element + listSize, element + theIndex); element[--listSize].~T(); //删除最后一个元素，避免重复 }template void arrayList::insert(int theIndex, const T& theElement) { //theIndex不合法 if (theIndex <0 || theIndex > listSize) { cout << "元素插入的theIndex下标不合理！ "; exit(-1); }//有效索引，判断数组是否已满 if (listSize == arrayLength) { //增加数组容量 changeLength1D(element, arrayLength, arrayLength * 2); arrayLength = arrayLength * 2; //修改数组容量值 }copy_backward(element + theIndex, element + listSize, element + listSize + 1); element[theIndex] = theElement; ++listSize; }template void arrayList::changeLength1D(T*& a, int oldLength, int newLength) { //判断新的容量是否合法 if (newLength < 0) { cout << "错误：newLength 小于 0！"; exit(-1); }T *tmp = new T[newLength]; int number = min(oldLength, newLength); //复制的元素的数量判断 copy(a, a + number, tmp); //元素复制 a = tmp; }template ostream& operator<<(ostream& out, const arrayList& x) { x.output(out); return out; }template void arrayList::output(ostream& out) const { //把线性表插入输出流 copy(element, element + listSize,ostream_iterator(cout, " ")); }template void arrayList::checkIndex(int theIndex) const { if (theIndex < 0 || theIndex >= listSize) { cout << "错误：theIndex 不合法！"; exit(-1); } }int main(int argc, char * argv[]) {arrayList aL(10); //测试insert函数 aL.insert(0, 5); aL.insert(1, 4); aL.insert(2, 3); aL.insert(3, 2); aL.insert(4, 1); //测试output函数 cout << "初始线性表为："; aL.output(cout); cout << endl; cout << "初始线性表的大小为：" << aL.size()<

【数据结构|笔记四（线性表——数组描述）】2、运行：
数据结构|笔记四（线性表——数组描述）
文章图片

  • 扩展：
    • 纯虚函数：为后代类型提供了可以覆盖的接口、但是该类中的版本绝不会调用，且不允许创建对象。在函数形参表后面写上 = 0 用以指定纯虚函数。virtual fun（） = 0 ；
    • 抽象基类：含有（或继承）一个或多个纯虚函数的类。不能创建实例对象。
    • 重载操作符：
      1、重载操作符必须具有一个类类型或枚举类型的操作数。
      2、一般将算数和关系操作符定义为非成员函数，而将赋值操作符定义为成员函数.
      3、作为类成员的重载函数，其形参比操作数目少1，因为第一个操作数为隐含的this形参Sale_item& operator+=(const Sale_item&);
      4、操作符定义为非成员函数时，通常设置为友元friend ostream& operator<<(ostream& out, const arrayList& x);
    • 构造函数与复制构造函数：
      1、构造函数：保证每个对象的数据成员具有合适的初始值A::A(const int& x) : a(0), b(x) {};
      2、复制构造函数：只有单个形参，且该形参是对本类类型的引用（常用const修饰）。
    • 析构函数与虚析构函数：
      1、析构函数：完成所需的资源回收，作为类构造函数的补充。析构函数无法重载。
      2、许多类不需要显示析构函数，尤其是具有构造函数的类不一定要定义自己的构造函数。如果类需要析构函数，则它也需要赋值操作符和复制构造函数——三法则。
      3、动态分配的内存只有在指向该对象的指针被删除时才撤销，如果没有删除指向动态对象的指针，则不会运行该对象的析构函数，对象就一直存在，从而导致内存泄露。
      4、赋值操作符：1）重载的赋值操作符Sale_item& operator=(const Sale_item&); ，2）合成赋值操作符——逐个成员赋值。
      5、赋值操作符与复制构造函数的调用区别：如果对象在声明的同时，将一个已存在的对象赋值给它，则调用复制构造函数；如果对象已经存在，再将另一个已存在的对象赋给它，则调用赋值操作符。
      3、虚析构函数：如果删除基类指针，则需运行基类析构函数，若对象是派生类型，则不需要定义该行为。为了保证运行适当的析构函数，基类中的析构函数必须为虚析构函数。（即使析构函数没有工作要做，继承层次的根类也应该定义一个虚析构函数。）
    • copy()与copy_backward()： copy()函数实现元素左移功能，copy_backward()实现元素右移功能。

    推荐阅读


    上一篇：王鑫悦自我介绍

    下一篇：JVM垃圾回收策略浅谈