用vector描述线性表

vectorList.h

#ifndef VECTORLIST_H
#define VECTORLIST_H
#include<iostream>
#include"linearlist.h"
#include<vector>
#include<myexceptions.h>
using namespace std;

template<class T>
class vectorList : public linearList<T>
{
public:
    //构造函数
    vectorList(int initialCapacity = 0);

    //复制构造函数
    vectorList(const vectorList<T>&);

    //析构函数
    ~vectorList()
    {
        delete element;
    }


    /*
     * 类linearList中抽象方法的实现
    */
    //判断是否表空
    bool empty() const
    {
        return element->empty();
    }

    //返回表内元素个数
    int size() const
    {
        return (int)element->size();
    }

    //返回索引为theIndex的元素
    T& get(int theIndex) const;

    //返回元素theElement的索引
    int indexOf(const T &theElement) const;

    //删除索引为theIndex的元素
    void erase(int theIndex);

    //在索引为theIndex的位置插入元素theElement
    void insert(int theIndex, const T &theElement);

    //将线性表元素放入输出流
    void output(ostream &out) const;


    /*
     * 增加的方法
    */
    int capacity() const
    {
        return (int)element->capacity();
    }

    /*
     * 线性表的起始和结束位置的迭代器
    */
    typedef typename vector<T>::iterator iterator;
    iterator begin(){return element->begin();}
    iterator end(){return element->end();}
protected:
    void checkIndex(int theIndex) const;
    vector<T>* element;//存储线性表元素的向量
};

/*
 * 构造函数和复制构造函数的实现
*/
template<class T>
vectorList<T>::vectorList(int initialCapacity)
{
    //构造函数
    if(initialCapacity < 1)
    {
        ostringstream s;
        s<<"Initial capacity = "<<initialCapacity<<"Must be > 0";
    throw illegalParameterValue(s.str);
    }
    element = new vector<T>;//创建向量为0的空向量
    element->reserve(initialCapacity);//vector的容量从0增加到initialCapacity

}

template<class T>
vectorList<T>::vectorList(const vectorList<T> &theList)
{
    //复制构造函数
    element = new vector<T>(*theList.element);
}


//删除元素
template<class T>
void vectorList<T>::erase(int theIndex)
{
    checkIndex(theIndex);
    element->erase(begin()+theIndex);
}

//插入元素
template<class T>
void vectorList<T>::insert(int theIndex, const T &theElement)
{
    if(theIndex < 0 || theIndex > size())
    {
        //无效索引
        ostringstream s;
        s<<"index = "<<theIndex <<" size = "<<size();
        throw illegalIndex(s.str());
    }
    element->insert(element->begin()+theIndex,theElement);
}

#endif // VECTORLIST_H

myexceptions.h

#ifndef MYEXCEPTIONS_H
#define MYEXCEPTIONS_H

#include <string>

using namespace std;

// illegal parameter value
class illegalParameterValue
{
   public:
      illegalParameterValue(string theMessage = "Illegal parameter value")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// illegal input data
class illegalInputData
{
   public:
      illegalInputData(string theMessage = "Illegal data input")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// illegal index
class illegalIndex
{
   public:
      illegalIndex(string theMessage = "Illegal index")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// matrix index out of bounds
class matrixIndexOutOfBounds
{
   public:
      matrixIndexOutOfBounds
            (string theMessage = "Matrix index out of bounds")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// matrix size mismatch
class matrixSizeMismatch
{
   public:
      matrixSizeMismatch(string theMessage =
                   "The size of the two matrics doesn't match")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// stack is empty
class stackEmpty
{
   public:
      stackEmpty(string theMessage =
                   "Invalid operation on empty stack")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// queue is empty
class queueEmpty
{
   public:
      queueEmpty(string theMessage =
                   "Invalid operation on empty queue")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// hash table is full
class hashTableFull
{
   public:
      hashTableFull(string theMessage =
                   "The hash table is full")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// edge weight undefined
class undefinedEdgeWeight
{
   public:
      undefinedEdgeWeight(string theMessage =
                   "No edge weights defined")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// method undefined
class undefinedMethod
{
   public:
      undefinedMethod(string theMessage =
                   "This method is undefined")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};
#endif // MYEXCEPTIONS_H

linearList.h

#ifndef LINEARLIST_H
#define LINEARLIST_H

// LINEARLIST_H
// abstract class linearList
// abstract data type specification for linear list data structure
// all methods are pure virtual functions

#include <iostream>

using namespace std;

template<class T>
class linearList
{
   public:
      virtual ~linearList() {};
      virtual bool empty() const = 0;
                  // return true iff list is empty
      virtual int size() const = 0;
                  // return number of elements in list
      virtual T& get(int theIndex) const = 0;
                  // return element whose index is theIndex
      virtual int indexOf(const T& theElement) const = 0;
                  // return index of first occurence of theElement
      virtual void erase(int theIndex) = 0;
                  // remove the element whose index is theIndex
      virtual void insert(int theIndex, const T& theElement) = 0;
                  // insert theElement so that its index is theIndex
      virtual void output(ostream& out) const = 0;
                  // insert list into stream out
};
#endif

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏武培轩的专栏

Java中Set集合是如何实现添加元素保证不重复的?

Java中Set集合是如何实现添加元素保证不重复的? Set集合是一个无序的不可以重复的集合。今天来看一下为什么不可以重复。 Set是一个接口,最常用的实现类就...

40570
来自专栏十月梦想

ES6新的数据结构Set

Set一种新的数据结构,在之前数据的集合分为数组(Array)和对象(Object),ES6出现新的Set数据结构,和Map,这里先介绍一下Set.

19850
来自专栏张俊红

数据结构—线性表

本篇开始,又会开始一个新的系列,数据结构,数据结构在算法或者是编程中的重要性不言而喻,所以学好数据结构还是很有必要的。本篇主要介绍数据结构的第一个结构——线性表...

14030
来自专栏恰童鞋骚年

数据结构基础温故-4.树与二叉树(下)

上面两篇我们了解了树的基本概念以及二叉树的遍历算法,还对二叉查找树进行了模拟实现。数学表达式求值是程序设计语言编译中的一个基本问题,表达式求值是栈应用的一个典型...

10820
来自专栏芋道源码1024

Jedis 对 Redis 的操作详解

本篇主要阐述Jedis对redis的五大类型的操作:字符串、列表、散列、集合、有序集合。

22030
来自专栏weixuqin 的专栏

数据结构学习笔记(线性表)

31150
来自专栏我是东东强

数据结构之线性表

线性表实现有两种方式,一种为顺序表,另一种为链表。本文分别介绍了顺序线性表、单向链表、双向链表和循环链表的基本结构,并给出了相应的C++类代码实现。

11320
来自专栏学习有记

[LeetCode Python 3] 876. Middle of the Linked List(链表的中间结点)

设置两个指向头节点的快慢指针,快指针每次走两步,慢指针每次走一步,当快指针到达最后结点或为空时,慢指针指向的就是中间结点 。

23220
来自专栏LeetCode

leetCode 77&39. Combinations & Combination Sum

Given two integers n and k, return all possible combinations of k numbers out of...

12500
来自专栏haifeiWu与他朋友们的专栏

聊聊HashSet源码

今天聊一下HashSet源码,HashSet内部基本使用HashMap来实现,本博客将通过一下几个方向讲解。

9730

扫码关注云+社区

领取腾讯云代金券