文章目录

线性表抽象基类迭代器类的层次设计使用方法 变长数组描述关于构造函数、析构函数、赋值、复制关于扩容、缩容性能分析完整代码及测试 链表描述链表的种类性能分析完整代码及测试 数组描述与链表描述的对比

线性表

抽象基类

这个抽象基类实际上约定了一个线性表应该具有那些功能。

// // Created by MAC on 2020/9/26. // #ifndef DATASTRUCTURE_LINEARLIST_H #define DATASTRUCTURE_LINEARLIST_H template<class T> class LinearList{ protected: int length; public: LinearList() { length = 0; } virtual ~LinearList() {} virtual T& get(int index) const = 0; virtual void insert(int index,const T& t) = 0; virtual void push_back(const T& t) = 0; virtual void push_front(const T& t) = 0; virtual void pop_back() = 0; virtual void pop_front() = 0; virtual void erase(int index) = 0; virtual void clear() = 0; bool empty(){ return length==0; } int size(){ return length; } }; #endif //DATASTRUCTURE_LINEARLIST_H

迭代器

迭代器提供了一种通用的方式去访问和操控容器对象。

类的层次设计

作为私有内部嵌套类定义在类的内部（私有是为了不让外部的调用者显式操纵迭代器类）；迭代器的方法(如++，--，*等等作为公有方法暴露给外面)； private: class arrayList_iterator{ protected: T* pos; public: arrayList_iterator(T *pos = nullptr) : pos(pos) {} //…………………… };

对外部调用者而言使用别名 typedef arrayList_iterator iterator;

另外其他一些迭代器的接口在外部类的公有方法中给出（它们并不是迭代器对象自己调用的，故而不是在内部类定义），例如（begin();end()等等）。

// 迭代器函数 iterator begin(){ return iterator(arr); } iterator end(){ return iterator(arr+this->length); }

使用方法

声明迭代器 下面这句话相当于定义了属于线性表类的一个成员变量，不过这个变量的类型是我们自己写的类类型，实际上创建了一个新的对象。 待它的生命周期结束会自动释放空间。 ArrayList<T>::iterator it = arrayList.begin(); 读写操作 就像操控指针一样操控迭代器对象即可，因为我们已经重载了那些操作指针的运算符。 迭代器实际上是对指针的再封装。 T t = *it; // 读 T tt; *it = tt; // 写 it++; // 移动 // …………

变长数组描述

关于构造函数、析构函数、赋值、复制

这四个函数最关键的就是动态分配数组。

关于扩容、缩容

扩容机制 在数组容量不够的时候，将数组容量扩大一倍。

缩容机制 为了内存空间的高效使用，不能只扩容，不缩小容量。 所以，在线性表的元素的数量小于等于容量的1/4时，减小一半的空间。

性能分析

随机查询的函数效率高：$get()、set()$的函数性能为$O(1)$ 插入和删除尾部的元素效率高，插入和删除头部的元素效率低，性能为$O(n)$ 并且，在变化容量的时候，比较耗时。

完整代码及测试

// // Created by MAC on 2020/9/26. // #ifndef DATASTRUCTURE_ARRAYLIST_H #define DATASTRUCTURE_ARRAYLIST_H #include "LinearList.h" #include <iostream> using std::cout; using std::cerr; using std::endl; using std::bad_alloc; using std::min; template<class T> class ArrayList : public LinearList<T>{ private: class arrayList_iterator{ protected: T* pos; public: arrayList_iterator(T *pos = nullptr) : pos(pos) {} // 测试相等 bool operator==(const arrayList_iterator &rhs) const { return pos == rhs.pos; } bool operator!=(const arrayList_iterator &rhs) const { return pos != rhs.pos; } // 解引用运算符 T& operator*(){ return *pos; } T* operator->(){ return pos; } // 前置加 arrayList_iterator& operator++(){ ++pos; return *this; } // 后置加 arrayList_iterator operator++(int){ iterator old = *this; ++pos; return old; } }; public: typedef arrayList_iterator iterator; ArrayList(int capacity = DEFAULT_SIZE):capacity(capacity){ if(capacity<=0){ throw "Illegal parameter."; } arr = new T[capacity]; } virtual ~ArrayList() { delete [] arr; } ArrayList(const ArrayList<T> & b); ArrayList<T>& operator=(const ArrayList<T> & b); T& get(int index) const override ; T& operator[] (int index){ check(index); return arr[index]; } const T& operator[] (int index) const{ check(index); return arr[index]; } void insert(int index, const T &t) override ; void push_back(const T &t) override { insert(this->length,t); } void push_front(const T &t) override { insert(0,t); } void erase(int index) override ; void pop_back() override { erase(this->length-1); } void pop_front() override { erase(0); } void clear() override ; void resize(int new_capacity); // 输出检测 void printAll() const { for(int i=0;i<this->length;i++){ cout<<arr[i]<<" "; } cout<<endl; } // 迭代器函数 iterator begin(){ return iterator(arr); } iterator end(){ return iterator(arr+this->length); } private: static const int DEFAULT_SIZE = 10; int capacity; T *arr = nullptr; void check(int index) const; void expand_capacity(){ if(this->length==capacity){ // cout<<"调用扩容函数"<<endl; resize(2*capacity); } } void reduce_capacity(){ if(this->length<capacity/4 && capacity/2>=10){ // cout<<"调用缩小容量函数"<<endl; resize(capacity/2); } } }; template<class T> ArrayList<T>::ArrayList(const ArrayList<T> & b){ if(this==&b) return; if(arr!= nullptr) delete [] arr; arr = new T[b.capacity]; capacity = b.capacity; this->length = b.length; for(int i=0;i<this->length;i++){ arr[i] = b.arr[i]; } } template<class T> ArrayList<T>& ArrayList<T>::operator=(const ArrayList<T> & b){ if(this==&b) return *this; if(arr!= nullptr) delete [] arr; arr = new T[b.capacity]; capacity = b.capacity; this->length = b.length; for(int i=0;i<this->length;i++){ arr[i] = b.arr[i]; } return *this; } template<class T> T& ArrayList<T>::get(int index) const { check(index); return arr[index]; } template<class T> void ArrayList<T>::check(int index) const { if(index<0 || index>=this->length){ throw "Index out of bounds"; } } template<class T> void ArrayList<T>::insert(int index, const T &t) { if(index<0 || index>this->length){ throw "Illegal parameter."; } expand_capacity(); if(index==this->length){ arr[this->length] = t; }else{ for(int pos = this->length;pos>index;pos--){ arr[pos] = arr[pos-1]; } arr[index] = t; } this->length++; } template<class T> void ArrayList<T>::erase(int index) { check(index); if(index<this->length-1){ for(int pos=index+1;pos<=this->length-1;pos++){ arr[pos-1] = arr[pos]; } } arr[--this->length].~T(); // 如果这里不释放的话，T元素的内部指针指向的那块空间就再也释放不了 reduce_capacity(); } template<class T> void ArrayList<T>::clear() { delete [] arr; arr = new T[DEFAULT_SIZE]; capacity = DEFAULT_SIZE; this->length = 0; } template<class T> void ArrayList<T>::resize(int new_capacity){ if(new_capacity<0){ throw "Illegal parameter."; } try{ T* a = new T[new_capacity]; for(int i=0;i<std::min(new_capacity,this->length);i++){ a[i] = arr[i]; } delete [] arr; arr = a; capacity = new_capacity; this->length = min(new_capacity,this->length); } catch (bad_alloc e) { cerr<<"Out of memoty."<<endl; exit(1); } } #endif //DATASTRUCTURE_ARRAYLIST_H 测试代码 // // Created by MAC on 2020/9/26. #include "ArrayList.h" using namespace std; struct Person{ string name; int age; Person() {} Person(const string &name, int age) : name(name), age(age) {} friend ostream & operator<<(ostream&os,const Person& person){ os<<person.name<<" "<<person.age<<" "; return os; } }; int main(){ ArrayList<Person> arrayList; arrayList.push_back(Person("Green",10)); arrayList.push_back(Person("Brown",12)); arrayList.push_back(Person("White",15)); arrayList.push_back(Person("Red",16)); for(ArrayList<Person>::iterator it = arrayList.begin();it!=arrayList.end();it++){ cout<<*it<<endl; } return 0; }

链表描述

链表的种类

单向链表 每个节点的存储 元素和指向下一个节点的指针。双向链表 每个节点的存储 元素，指向下一个节点的指针 以及 指向前一个节点的指针。循环链表 头结点的pre指针指向尾结点，尾结点的next指针指向头结点

为了避免对头结点何尾结点特殊分析，我们增加两个特殊的哨兵节点，head和tail。

性能分析

随机访问，效率很低：$O(n)$ 但是不论是插入和删除，效率都很高：$O(1)$ 另外，由于没有扩容机制——所有节点都是按需分配的，所以性能没有波动。 空间上，一方面，没有开辟一块连续的内存空间，高效使用了计算机内存。 另一方面，每个节点为了能联系下一个节点，有必须存储下一个节点的地址。

完整代码及测试

// // Created by MAC on 2020/10/4. // #ifndef DATASTRUCTURE_LINKEDLIST_H #define DATASTRUCTURE_LINKEDLIST_H #include "LinearList.h" template<class T> class LinkedList : public LinearList<T>{ private: class Node{ public: T val; Node* next = nullptr, *previous = nullptr; Node() {} Node(T val) : val(val) {} }; class linkedList_iterator{ private: Node* pos; public: linkedList_iterator(Node *pos = nullptr) : pos(pos) {} bool operator==(const linkedList_iterator &rhs) const { return pos == rhs.pos; } bool operator!=(const linkedList_iterator &rhs) const { return pos != rhs.pos; } T& operator*(){ return pos->val; } T* operator->(){ return &(pos->val); } linkedList_iterator& operator++(){ pos = pos->next; return *this; } linkedList_iterator operator++(int){ Node* temp = pos; pos = pos->next; return iterator(temp); } }; Node*head,*tail; void check(int index) const; public: typedef linkedList_iterator iterator; LinkedList() ; virtual ~LinkedList() ; LinkedList(const LinkedList<T>&) = delete ; LinkedList<T>& operator=(const LinkedList<T>&) = delete ; virtual T &get(int index) const; virtual void insert(int index, const T &t) ; virtual void push_back(const T &t) ; virtual void push_front(const T &t) ; virtual void pop_back() ; virtual void pop_front() ; virtual void erase(int index) ; virtual void clear() ; // 输出检测 void printAll() const { Node* cur = head->next; while(cur!=tail){ cout<<cur->val<<" "; cur = cur->next; } cout<<endl; } iterator begin(){ return iterator(head->next); } iterator end(){ return iterator(tail); } }; template<class T> LinkedList<T>::LinkedList() { head = new Node; tail = new Node; head->next = tail; tail->previous = head; } template<class T> LinkedList<T>::~LinkedList() { Node *cur = head,*temp; while(cur!= nullptr){ temp = cur->next; delete cur; cur = temp; } } template<class T> T& LinkedList<T>::get(int index) const { check(index); Node *cur = head->next; for(int i=0;i<index;i++){ cur = cur->next; } return cur->val; } template<class T> void LinkedList<T>::insert(int index, const T &t) { if(index==this->length){ push_back(t); return; } check(index); Node* cur = head; for(int i=0;i<index;i++){ cur = cur->next; } Node* newNode = new Node(t); newNode->next = cur->next; cur->next->previous = newNode; newNode->previous = cur; cur->next = newNode; this->length++; } template<class T> void LinkedList<T>::push_back(const T &t) { Node* newNode = new Node(t); newNode->previous = tail->previous; tail->previous->next = newNode; newNode->next = tail; tail->previous = newNode; this->length++; } template<class T> void LinkedList<T>::push_front(const T &t) { Node* newNode = new Node(t); newNode->next = head->next; head->next->previous = newNode; newNode->previous = head; head->next = newNode; this->length++; } template<class T> void LinkedList<T>::erase(int index) { check(index); Node* temp = head; for(int i=0;i<index;i++){ temp = temp->next; } Node* cur = temp->next; temp->next = cur->next; cur->next->previous = temp; delete cur; this->length--; } template<class T> void LinkedList<T>::pop_back() { Node* cur = tail->previous; tail->previous = cur->previous; cur->previous->next = tail; delete cur; this->length--; } template<class T> void LinkedList<T>::pop_front() { Node* cur = head->next; head->next = cur->next; cur->next->previous = head; delete cur; this->length--; } template<class T> void LinkedList<T>::clear() { Node *cur = head->next,*temp; while(cur!=tail){ temp = cur->next; delete cur; cur = temp; } this->length = 0; } template<class T> void LinkedList<T>::check(int index) const { if(index<0 || index>=this->length){ throw "Index out of bounds"; } } #endif //DATASTRUCTURE_LINKEDLIST_H

数组描述与链表描述的对比

在对随机访问有着高性能要求的场景，使用数组描述。在随机访问稀疏，插入删除频繁的场景，使用链表。在存储元素是一个很大的对象时，比较适合使用链表。