返回顶部

收藏

线性表操作 交互 链表

更多

1、创建线性表类。线性表的存储结构使用链表。

2、完成表首插入元素、删除指定元素、搜索表中是否有指定元素、输出链表。

3、输入n个不为零的整数作为节点元素值,遇到0代表输入结束(不创建元素值为0的节点),创建链表。输出整个链表。

4、输入一个整数,将该数作为一个元素值插入表首位置。输出整个链表。

5、输入一个整数,在链表中进行搜索,输出其在链表中的位置。如果不存在输出0。

6、再一次输入一个整数,在链表中进行搜索,输出其在链表中的位置。如果不存在输出0。

7、使用链表遍历器实现链表的反序输出。

8、再一次输入n个不为零的整数作为节点元素值,遇到0代表输入结束(不创建元素值为0的节点),创建另外一个链表,输出整个链表。

9、使用链表遍历器实现上面两个链表的合并,输出合并后的链表。

#ifndef chain_
#define chain_
#ifndef chainNode_
#define chainNode_
#ifndef linearList_
#define linearList_
#ifndef myExceptions_
#define myExceptions_

#include <iostream>
#include <sstream>
#include <string>

using namespace std;
// chain node

template <class T>
struct chainNode
{
   // data members
   T element;
   chainNode<T> *next;

   // methods
   chainNode() {}
   chainNode(const T& element)
      {this->element = element;}
   chainNode(const T& element, chainNode<T>* next)
      {this->element = element;
       this->next = next;}
};

#endif

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

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

// exception classes for various error types

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

class linkedDigraph;
template <class T> class linkedWDigraph;

template<class T>
class chain : public linearList<T>
{
   friend class linkedDigraph;
   friend class linkedWDigraph<int>;
   friend class linkedWDigraph<float>;
   friend class linkedWDigraph<double>;
   public:
      // constructor, copy constructor and destructor
      chain(int initialCapacity = 10);
      chain(const chain<T>&);
      ~chain();

      // ADT methods
      bool empty() const {return listSize == 0;}
      int size() const {return listSize;}
      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;

   protected:
      void checkIndex(int theIndex) const;
            // throw illegalIndex if theIndex invalid
      chainNode<T>* firstNode;  // pointer to first node in chain
      int listSize;             // number of elements in list
};

template<class T>
chain<T>::chain(int initialCapacity)
{// Constructor.
   if (initialCapacity < 1)
   {ostringstream s;
    s << "Initial capacity = " << initialCapacity << " Must be > 0";
    throw illegalParameterValue(s.str());
   }
   firstNode = NULL;
   listSize = 0;
}

template<class T>
chain<T>::chain(const chain<T>& theList)
{// Copy constructor.
   listSize = theList.listSize;

   if (listSize == 0)
   {// theList is empty
      firstNode = NULL;
      return;
   }

   // non-empty list
   chainNode<T>* sourceNode = theList.firstNode;
                    // node in theList to copy from
   firstNode = new chainNode<T>(sourceNode->element);
                    // copy first element of theList
   sourceNode = sourceNode->next;
   chainNode<T>* targetNode = firstNode;
                    // current last node in *this
   while (sourceNode != NULL)
   {// copy remaining elements
      targetNode->next = new chainNode<T>(sourceNode->element);
      targetNode = targetNode->next;
      sourceNode = sourceNode->next;
   }
   targetNode->next = NULL; // end the chain
}

template<class T>
chain<T>::~chain()
{// Chain destructor. Delete all nodes in chain.
   while (firstNode != NULL)
   {// delete firstNode
      chainNode<T>* nextNode = firstNode->next;
      delete firstNode;
      firstNode = nextNode;
   }
}

template<class T>
void chain<T>::checkIndex(int theIndex) const
{// Verify that theIndex is between 0 and listSize - 1.
   if (theIndex < 0 || theIndex >= listSize)
   {ostringstream s;
    s << "index = " << theIndex << " size = " << listSize;
    throw illegalIndex(s.str());
   }

}

template<class T>
T& chain<T>::get(int theIndex) const
{// Return element whose index is theIndex.
 // Throw illegalIndex exception if no such element.
   checkIndex(theIndex);

   // move to desired node
   chainNode<T>* currentNode = firstNode;
   for (int i = 0; i < theIndex; i++)
      currentNode = currentNode->next;

   return currentNode->element;
}

template<class T>
int chain<T>::indexOf(const T& theElement) const
{// Return index of first occurrence of theElement.
 // Return -1 if theElement not in list.

   // search the chain for theElement
   chainNode<T>* currentNode = firstNode;
   int index = 0;  // index of currentNode
   while (currentNode != NULL &&
          currentNode->element != theElement)
   {
      // move to next node
      currentNode = currentNode->next;
      index++;
   }

   // make sure we found matching element
   if (currentNode == NULL)
      return -1;
   else
      return index;
}

template<class T>
void chain<T>::erase(int theIndex)
{// Delete the element whose index is theIndex.
 // Throw illegalIndex exception if no such element.
   checkIndex(theIndex);

   // valid index, locate node with element to delete
   chainNode<T>* deleteNode;
   if (theIndex == 0)
   {// remove first node from chain
      deleteNode = firstNode;
      firstNode = firstNode->next;
   }
   else
   {  // use p to get to predecessor of desired node
      chainNode<T>* p = firstNode;
      for (int i = 0; i < theIndex - 1; i++)
         p = p->next;

      deleteNode = p->next;
      p->next = p->next->next; // remove deleteNode from chain
   }
   listSize--;
   delete deleteNode;
}

template<class T>
void chain<T>::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());
   }

   if (theIndex == 0)
      // insert at front
      firstNode = new chainNode<T>(theElement, firstNode);
   else
   {  // find predecessor of new element
      chainNode<T>* p = firstNode;
      for (int i = 0; i < theIndex - 1; i++)
         p = p->next;

      // insert after p
      p->next = new chainNode<T>(theElement, p->next);
   }
   listSize++;
}

template<class T>
void chain<T>::output(ostream& out) const
{// Put the list into the stream out.
   for (chainNode<T>* currentNode = firstNode;currentNode != NULL;currentNode = currentNode->next){
       chainNode<T>* newnode = currentNode->next;
       if(newnode != NULL)
       out << currentNode->element << ",";
       else    out << currentNode->element;
   }
}

// overload <<
template <class T>
ostream& operator<<(ostream& out, const chain<T>& x){
    x.output(out);
    return out;}

#endif

// test the class chain

int main(){
   // test constructor
   chain<int> y, z;
   int temp, i;

   // test insert

   cout<<"Input"<<endl;
   for(i=0;i>=0;i++){

       cin>>temp;
       if(temp!=0)
       y.insert(i,temp);
       else break;
   }
   cout<<"Output"<<endl;
   y.output(cout);

   // test indexOf
   cout<<endl;
   cout<<"Input2"<<endl;
   cin>>temp;
   y.insert(0,temp);
   y.output(cout);
   cout<<endl;
   cout<<"Input3"<<endl;
   cin>>temp;
   int index = y.indexOf(temp);
   if (index < 0) cout<<"0"<<endl;
   else cout<<index+1<<endl;
   cout<<"Input4"<<endl;
   cin>>temp;
   index = y.indexOf(temp);
   if (index < 0) cout<<"0"<<endl;
   else cout <<index+1<<endl;

   cout<<"Input5"<<endl;
   for(i=0;i>=0;i++){

       cin>>temp;
       if(temp!=0)
       z.insert(i,temp);
       else break;
   }
   cout<<"Output"<<endl;
   z.output(cout);
   cout<<endl;
   int num1=y.size();
   for(int k=1;k<=num1;k++){
       int num2=num1-k;
       int num3=y.get(num2);
       z.insert(0,num3);

       }
   z.output(cout);
   cout<<endl;
   cout<<"End"<<endl;

   return 0;
}
//该片段来自于http://outofmemory.cn

标签:c++,算法

收藏

0人收藏

支持

0

反对

0

»更多 您可能感兴趣的代码
  1. 2014-09-01 13:12:19计数排序 by lucasli
  2. 2014-09-10 11:32:48快速排序代码(自己写的,有点冗余) by sxgkwei
  3. 2014-10-27 10:07:37求一个数的所有质因子之和 by walker30
  4. 2014-11-16 12:05:30通用排序程序 by lucasli
  5. 2014-11-30 09:48:33数组逆序 by 灵剑子
  6. 2014-05-11 18:34:3821位水仙花数 by sxgkwei
  7. 2014-05-19 17:12:34数据结构 顺序栈 by qqmmcc
  8. 2014-05-22 11:38:42求两个数的最小公倍数 by 蟋蟀哥
  9. 2014-05-22 15:43:22神经元模型 by lucasli
  10. 2014-06-05 11:30:06经过优化后的快速排序算法 by 灵剑子
  11. 2014-06-07 20:27:27解数独 by niutao.linux

发表评论