24H免费课程咨询  TEL:13401595960   QQ:1870218756  微信:13401595960(李老师)

东方博宜

网站首页 > 软件开发资讯 > Java开发

采用C++的数组实现线性表结构

2017-05-31 20:35:06 东方博宜 阅读

今天给大家分享一下C++的用数组实现线性表的数据结构是如何实现的!

1、linearList.h

// abstract class linearList

// abstract data type specification for linear list data structure

// all methods are pure virtual functions


#ifndef linearList_

#define linearList_

#include


using namespace std;


template

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

2、changeLength.h

#include

#include "myExceptions.h"

using namespace std;


template

void changeLength(T*& a,int oldLength,int newLength)

{

if(newLength < 0){

throw illegalParameterValue("new length must be >= 0");

}else{

T* temp = new T[newLength];//新数组

int number = min(oldLength,newLength);//需要复制的元素个数

copy(a,a+number,temp);

delete [] a;

a = temp;

}

}

3、MyExceptions.h

#ifndef myExceptions_h

#define myExceptions_h


#include

#include

using namespace std;


class illegalParameterValue

{

private:

string message;

public:

  illegalParameterValue(string theMessage = "Illegal parameter value") 

  {

   message = theMessage;

  }

  

  void outputMessage(){

   cout<<message<<endl;

  }

};


class illegalIndex{

private:

string message;

public:

illegalIndex(string theMessage="Illegal index"){

message = theMessage;

}

    

   void outputMessage(){

   cout<<message<<endl;

}

};


#endif


4、arrayList.h

#ifndef arrayList_h

#define arrayList_h 


#include

#include

#include

#include

#include

  

#include "linearList.h"

#include "myExceptions.h"

#include "changeLength.h"


using namespace std;


template 

class arrayList:public linearList

{

protected:

//如果索引无效,则抛出异常 

void checkIndex(int theIndex) const;

T* element;//存储线性表元素的一维数组

int arrayLength;//一维数组的容量

int listSize;//线性表的元素个数 

public:

//构造函数,复制构造函数和析构函数

arrayList(int initCapacity = 10);

arrayList(const arrayList&);

~arrayList(){

delete [] element;

}

//ADT(abstract data type)方法

bool empty() const{

  return listSize == 0;

}

//const表示成员函数不改变类的数据成员 

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);

void output(ostream& out) const;

//其他方法

int capacity()  const{

  return arrayLength;

}

 

};


//类arrayList的构造函数

template 

arrayList::arrayList(int initCapacity){

if(initCapacity < 1){

ostringstream s;

s<<"init capacity="<<initCapacity<<" must="" be="">0";

throw illegalParameterValue(s.str()); 

}

arrayLength = initCapacity;

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::checkIndex(int theIndex)  const

{

//确定索引theIndex在0和listSize-1之间

if(theIndex < 0 || theIndex >= listSize) {

ostringstream s;

s<<"index = "<<theIndex<<" size = "<<listSize;

throw illegalIndex(s.str());

}

}


//返回索引为theIndex的元素,如果不存在抛出异常

template 

T& arrayList::get(int theIndex) const

{

checkIndex(theIndex);

return element[theIndex];

}


//返回元素第一次出现的索引

template

int arrayList::indexOf(const T& theElement) const

{// Return index of first occurrence of theElement.

 // Return -1 if theElement not in list.


   // search for theElement

   int theIndex = (int) (find(element, element + listSize, theElement)

                         - element);


   // check if theElement was found

   if (theIndex == listSize)

     // not found

     return -1;

   else return theIndex;

 }


template

void arrayList::erase(int theIndex)

{// Delete the element whose index is theIndex.

 // Throw illegalIndex exception if no such element.

   checkIndex(theIndex);


   // valid index, shift elements with higher index

   copy(element + theIndex + 1, element + listSize,

                                element + theIndex);


   element[--listSize].~T(); // invoke destructor

}


template

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

{// Insert theElement so that its index is theIndex.

   if (theIndex < 0 || theIndex > listSize)

   {// invalid index

      ostringstream s;

      s << "index = " << theIndex << " size = " << listSize;

      throw illegalIndex(s.str());

   }


   // valid index, make sure we have space

   if (listSize == arrayLength)

      {// no space, double capacity

         changeLength(element, arrayLength, 2 * arrayLength);

         arrayLength *= 2;

      }


   // shift elements right one position

   copy_backward(element + theIndex, element + listSize,

                 element + listSize + 1);


   element[theIndex] = theElement;


   listSize++;

}


template

void arrayList::output(ostream& out) const

{// Put the list into the stream out.

   copy(element, element + listSize, ostream_iterator(cout, "  "));

}


// overload <<

template

ostream& operator<<(ostream& out, const arrayList& x)

   {x.output(out); return out;}


#endif


5、arrayList.cpp

// test the class arrayList that uses STL algorithms

#include

#include "linearList.h"

#include "arrayList.h"


using namespace std;


int main()

{

   // test constructor

   linearList*x = new arrayList(20);

   arrayListy(2), z;


   // test capacity

   cout << "x、y、z的容量capacity分别是 = "

        << ((arrayList*) x)->capacity() << ", "

        << y.capacity() << ", "

        << z.capacity() << endl;



   // test size

   cout << "x、y、z的初始化的大小分别是 = "

        << x->size() << ", "

        << y.size() << ", "

        << z.size() << endl;


   // test empty

   if (x->empty()) cout << "x is empty" << endl;

   else cout << "x is not empty" << endl;

   if (y.empty()) cout << "y is empty" << endl;

   else cout << "y is not empty" << endl;


   // test insert

   y.insert(0, 2);

   y.insert(1, 6);

   y.insert(0, 1);

   y.insert(2, 4);

   y.insert(3, 5);

   y.insert(2, 3);

   cout << "插入6个整数,y的值应该是: 1 2 3 4 5 6" << endl;

   cout << "y的size为 = " << y.size() << endl;

   cout << "y的capacity为 = " << y.capacity() << endl;

   if (y.empty()) cout << "y is empty" << endl;

   else cout << "y is not empty" << endl;

   y.output(cout);

   cout << endl << "Testing overloaded <<" << endl;

   cout << y << endl;


   // test indexOf

   int index = y.indexOf(4);

   if (index < 0) cout << "4 not found" << endl;

   else cout << "The index of 4 is " << index << endl;


   index = y.indexOf(7);

   if (index < 0) cout << "7 not found" << endl;

   else cout << "The index of 7 is " << index << endl;


   // test get

   cout << "Element with index 0 is " << y.get(0) << endl;

   cout << "Element with index 3 is " << y.get(3) << endl;


   // test erase

   y.erase(1);

   cout << "Element 1 erased" << endl;

   cout << "The list is "  << y << endl;

   y.erase(2);

   cout << "Element 2 erased" << endl;

   cout << "The list is "  << y << endl;


   cout << "Size of y = " << y.size() << endl;

   cout << "Capacity of y = " << y.capacity() << endl;

   if (y.empty()) cout << "y is empty" << endl;

   else cout << "y is not empty" << endl;


   try {y.insert(-3, 0);}

   catch (illegalIndex e)

   {

      cout << "Illegal index exception" << endl;

      cout << "Insert index must be between 0 and list size" << endl;

      e.outputMessage();

   }


   // test copy constructor

   arrayListw(y);

   y.erase(0);

   y.erase(0);

   cout << "w should be old y, new y has first 2 elements removed" << endl;

   cout << "w is " << w << endl;

   cout << "y is " << y << endl;

   

   // a few more inserts, just for fun

   y.insert(0,4);

   y.insert(0,5);

   y.insert(0,6);

   y.insert(0,7);

   cout << "y is " << y << endl;

   return 0;

}













Powered by 东方博宜教育咨询江苏有限公司  ©2008-2017 www.czos.cn