顺序表的问题 - C++教室 - C++论坛

问题点数：0 回复次数：9

顺序表的问题

#include<iostream> using namespace std; template<class Elem> class List{ //Renitialize the list. The client is responsible for //reclaiming the storage used by the list elements. virtual void clear()=0; //Insert an element at the front of the right partition //Return true if successfull,false if the list if full. virtual bool insert(const Elem&)=0; //Append an element at the end of the right partition.Return //true if successful,false if the list if full. virtual bool append(const Elem&)=0; //Remove the first element of the right partition.Return true //if seccessful,false if the right partition is empty. //The element removed is returned in the parameter. virtual bool remove(Elem&)=0; //Place fence at list start,making left partition empty. virtual void setStart()=0; //Place fence at list end,making right partition empty. virtual void setEnd()=0; //Move fence one step left;no change if already at start virtual void prev()=0; //Move fende one step right;no change if already at end virtual void next()=0; //Return length of left partition virtual int leftLength()=0; //Return length of right partition virtual int rightLength()=0; //If pos and more elements are in the list,set the size of left partition //to pos and return true.Otherwise,do nothing and return false. virtual bool setPos(int pos)=0; //Return in first parameter the first element of the right partition. //Return true if successful,flase if the right partition is empty. virtual bool getValue(Elem&)=0; //Print the contents of the list virtual void print() const=0; };

template<class Elem> class Alist : public List<Elem>{ private: int maxSize; //Maximum size of elements in list int listSize; //Actual number of elements in list int fence; //position of fence Elem *listArray; //array holding list elements public: Alist(int size=10){ maxSize=size; listSize=fence=0; listArray=new Elem[maxSize]; } ~Alist() { delete [] listArray;} //Destructor void clear() { delete [] listArray; listSize=fence=0; listArray= new Elem[maxSize]; } bool insert(const Elem&); bool append(const Elem&); bool remove(Elem&); void setStart(){fence=0;} void setEnd(){ fence=listSize;} void prev() { if(fence!=0) fence--;} void next() { if(fence<=listSize) fence++;} int leftLength() const { return fence;} int rightLength() const { return listSize-fence;} bool setPos(int pos){ if(pos>0)&&(pos<=listSize) fence=pos; return (pos>0)&&(pos<=listSize); } bool getValue(Elem& it) const{ if(rightLength()==0) return false; else (it=listArray[fence]) return true; } void print() const{ int temp=0; cout<<"<"; while(temp<fence) cout<<listArray[temp++]<<" "; cout<<"|"; while(temp<listSize) cout<<listArray[temp++]<<" "; cout<<">\n"; } };

template<class Elem> bool Alist<Elem>::insert(const Elem& item){ if(listSize==maxSize) return false; for(int i=listSize;i>fence;i--) listArray[i]=listArray[i-1]; listArray[fence]=item; listSize++; return true; } template<class Elem> bool Alist<Elem>::append(const Elem& item){ if(listSize==maxSize)return false; listArray[listSize++]=item; return true; }

template<class Elem> bool Alist<Elem>::remove(Elem& it){ if(rightLength()==0) return false; it=listArray[fence]; for(int i=fence;i<listSize-1;i++) listArray[i]=listArray[i+1]; return true; }

int main(){ Alist<int>& list; //为什么这里会出错呢，小弟百思不得其截望高手指教 int i; cin>>i; while(i!=-999){ list.append(i); cin>>i; } return 0; } cpp(115) : error C2530: 'list' : references must be initialized

搜索更多相关主题的帖子: 顺序　

第 2 楼

得分:0

自由，民主，平等，博爱，进步．
中华民国，我的祖国，中华民国万岁！中华民国加油！
本人自愿加入中国国民党，为人的自由性，独立性和平等性而奋斗！

第 3 楼

得分:0

谢谢kai，我知道那里错了，我会进一步改进程序的

第 4 楼

得分:0

但是我的链表实现也出现很多问题，就是根据上面的程序改的，请kai看下： #include<iostream> using namespace std; template<class Elem> class List{ //Renitialize the list. The client is responsible for //reclaiming the storage used by the list elements. virtual void clear()=0; //Insert an element at the front of the right partition //Return true if successfull,false if the list if full. virtual bool insert(const Elem&)=0; //Append an element at the end of the right partition.Return //true if successful,false if the list if full. virtual bool append(const Elem&)=0; //Remove the first element of the right partition.Return true //if seccessful,false if the right partition is empty. //The element removed is returned in the parameter. virtual bool remove(Elem&)=0; //Place fence at list start,making left partition empty. virtual void setStart()=0; //Place fence at list end,making right partition empty. virtual void setEnd()=0; //Move fence one step left;no change if already at start virtual void prev()=0; //Move fende one step right;no change if already at end virtual void next()=0; //Return length of left partition virtual int leftLength() const=0; //Return length of right partition virtual int rightLength() const=0; //If pos and more elements are in the list,set the size of left partition //to pos and return true.Otherwise,do nothing and return false. virtual bool setPos(int pos)=0; //Return in first parameter the first element of the right partition. //Return true if successful,flase if the right partition is empty. virtual bool getValue(Elem&) const=0; //Print the contents of the list virtual void print() const=0; }; template<class Elem> class Link{ public: Elem element; Link *next; Link(const Elem& elemval,Link* nextval=NULL) {element=elemval;next=nextval;} Link(Link* nextval=NULL){next=nextval;} }; template<class Elem> class LList:public List<Elem>{ private: Link<Elem> *head; Link<Elem> *tail; Link<Elem> *fence; int leftLength; int rightLength; void init(){ fence=head=tail=new Link<Elem>; leftLength=rightLength=0; } void removeall(){ //Return link nodes to free store while(head!=NULL){ fence=head; head=head->next; delete fence; } } public: LList(int size=10){init();} ~LList{removeall();} void clear(){removeall();init();} bool insert(const Elem& ); bool append(const Elem& ); bool remove(Elem&); void setStart() { fence=head;rightLength+=leftLength;leftLength=0;} void setEnd() { fence=tail;leftLength+=rightLength;rightLength=0;} void prev(); void next(){ if(fence!=tail) { fence=fence->next;rightLength--;leftLength++;} } int leftLength() const {return leftLength;} int rightLength() const { return rightLength;} bool setPos(int pos); bool getValue(Elem& it) const{ if(tightLength()==0) return false; it=fence->next->element; return true; } void print() const; };

template<class Elem> bool LList<Elem>::insert(const Elem& item) { fence->next=new Link<Elem>(item,fence->next); if(tail==fence) tail=fence->next; rightLength++; return true; } template<class Elem> bool LList<Elem>::append(const Elem& item) { tail=tail->next=new Link<Elem>(item,NULL); rightLength++; return true; }

template<class Elem> bool LList<Elem>::remove(Elem& it){ if(fence->next==NULL) return false; it=fence->next->element; link<Elem>* ltemp=fence->next; fence->next=ltemp->next; if(ltemp==tail) tail=fence; delete ltemp; rightLength--; return true; } template<class Elem> void LList<Elem>::prev() { Link<Elem>* temp=head; if(fence==head) return; while(temp->next!=fence) temp=temp->next; fence=temp; leftLength--;rightLength++; }

template<class Elem> bool LList<Elem>::setPos(int pos) { if(pos<0||pos>rightLength+leftLength) return false; fence=head; for(int i=0;i<pos;pos++) fence=fence->next; return true; }

template<class Elem> void LList<Elem>::print() const { Link<Elem>* temp=head; cout<<"<"; while(temp!=fence){ cout<<temp->next->element<<" "; temp=temp->next; } cout<<"|"; while(temp->next!=NULL) { cout<<temp->next->element<<" "; temp=temp->next; } cout<<">\n"; }

int main() { int A[10]={1,2,3,4,5,6,7,8,9,10}; LList<Elem> list; for(int i=0;i<10;i++) list.append(A[i]); list.setPos(5); list.print(); system("pause"); return EXIT_SUCCESS; } //链表.obj - 10 error(s), 0 warning(s)

第 5 楼

得分:0

#include <iostream>
#include <cstdlib>
using namespace std;

template<class Elem>
class List
{
//Renitialize the list. The client is responsible for
//reclaiming the storage used by the list elements.
virtual void clear()=0;
//Insert an element at the front of the right partition
//Return true if successfull,false if the list if full.
virtual bool insert(const Elem &)=0;
//Append an element at the end of the right partition.Return
//true if successful,false if the list if full.
virtual bool append(const Elem &)=0;
//Remove the first element of the right partition.Return true
//if seccessful,false if the right partition is empty.
//The element removed is returned in the parameter.
virtual bool remove(Elem &)=0;
//Place fence at list start,making left partition empty.
virtual void setStart()=0;
//Place fence at list end,making right partition empty.
virtual void setEnd()=0;
//Move fence one step left;no change if already at start
virtual void prev()=0;
//Move fence one step right;no change if already at end
virtual void next()=0;
//Return length of left partition
virtual int leftLength() const=0;
//Return length of right partition
virtual int rightLength() const=0;
//If pos and more elements are in the list,set the size of left partition
//to pos and return true.Otherwise,do nothing and return false.
virtual bool setPos(int pos)=0;
//Return in first parameter the first element of the right partition.
//Return true if successful,flase if the right partition is empty.
virtual bool getValue(Elem&) const=0;
//Print the contents of the list
virtual void print() const=0;
};

template<class Elem>
class Link
{
public:
  Elem element;
  Link * next;
  Link(const Elem & elemval, Link * nextval = NULL)
  {
     element = elemval;
     next = nextval;
  }
  Link(Link * nextval = NULL)
  {
     next = nextval;
  }
};

template<class Elem>
class LList : public List<Elem>
{
private:
   Link<Elem> * head;
   Link<Elem> * tail;
   Link<Elem> * fence;
   int left_length;
   int right_length;
   void init()
   {
      fence = head = tail = new Link<Elem>;
      left_length = right_length = 0;
   }
   void removeall()
   {   //Return link nodes to free store
      while(head != NULL)
      {
         fence = head;
         head = head->next;
         delete fence;
      }
   }
public:
   LList(int size = 10)
   {
      init();
   }
   ~LList()
   {
      removeall();
   }
   void clear()
   {
      removeall();
      init();
   }
   bool insert(const Elem & );
   bool append(const Elem & );
   bool remove(Elem &);
   void setStart()
   {
      fence = head;
      right_length += left_length;
      left_length=0;
   }
   void setEnd()
   {
      fence = tail;
      left_length += right_length;
      right_length = 0;
   }
   void prev();
   void  next()
   {
      if(fence != tail)
      {
         fence = fence->next;
         right_length--;
         left_length++;
      }
   }
   int leftLength() const
   {
      return left_length;
   }
   int rightLength() const
   {
      return right_length;
   }
   bool setPos(int pos);
   bool getValue(Elem & it) const
   {
      if(rightLength() == 0)
         return false;
      it = fence->next->element;
      return true;
   }
   void print() const;
};

template<class Elem>
bool LList<Elem>::insert(const Elem & item)
{
   fence->next = new Link<Elem>(item,fence->next);
   if(tail == fence)
      tail = fence->next;
   right_length++;
   return true;
}
template<class Elem>
bool LList<Elem>::append(const Elem& item)
{
   tail = tail->next = new Link<Elem>(item, NULL);
   right_length++;
   return true;
}

template<class Elem>
bool LList<Elem>::remove(Elem & it)
{
   if(fence->next == NULL)
      return false;
   it = fence->next->element;
   Link<Elem> * ltemp = fence->next;
   fence->next = ltemp->next;
   if(ltemp == tail)
      tail = fence;
   delete ltemp;
   right_length--;
   return true;
}
template<class Elem>
void LList<Elem>::prev()
{
   Link<Elem> * temp = head;
   if(fence == head)
      return;
   while(temp->next != fence)
      temp = temp->next;
   fence = temp;
   left_length--;
   right_length++;
}

template<class Elem>
bool LList<Elem>::setPos(int pos)
{
   if(pos<0 || pos > right_length + left_length)
      return false;
   fence = head;
   for(int i = 0; i < pos; pos++)
      fence = fence->next;
   return true;
}

template<class Elem>
void LList<Elem>::print() const
{
   Link<Elem> * temp = head;
   cout<<"<";
   while(temp != fence)
   {
      cout<<temp->next->element<<" ";
      temp = temp->next;
   }
   cout<<"|";
   while(temp->next != NULL)
   {
      cout<<temp->next->element<<" ";
      temp = temp->next;
   }
   cout<<">\n";
}

int main()
{
   int A[10] = {1,2,3,4,5,6,7,8,9,10};
   LList<int> list;
   for(int i=0; i<10; i++)
      list.append(A[i]);
//   list.setPos(5);         // 帮你整理了一下程序，如果隐去这一行，至少还能打印
                                  // 也就是说，你的程序有逻辑错误，对地址操作有误。
   list.print();
   system("pause");
   return EXIT_SUCCESS;
}

// 我通看了你的代码，不理解你为什么需要 fence 这个变量。也不理解 left_length 和 right_length 的用途。
// 在一个class 的定义中，一旦有成员变量为地址变量, 即  Type * a_address; 那么你需要写 copyconstructor function, 以及 assigment function ,  以防止浅Copy 的出现.

你在程序中写了 init()  以及 removeall() 函数，我觉得没有必要，可以直接写  constructor function 以及 destructor function.

一个list 是这样一个概念, list 是用于存放其他 object 的一个object. 而每一个object 是上下手牵手连着的.
那么它的class 定义看起来是这样的:

class List
{
template <class Type>
struct Otherobject
{
   Type value;
   Otherobject * prev;
   Otherobject * next;
}
private:
   Otherobject * poo;   // address of the first element
   intsize;                   // current size;
   intcapability;          // the max size, it must be larger than size, and a list can beextendable.
   bool operator<(const Otherobject & oo1, const Otherobject & oo2);
public:
   List();    // default constructor
   List(Otherobject * begin, Otherobject * end);   // constructor
   List(const int size);   // constructor
   List(const List & otherList);   // copy constructor
   List & operator=(const List & L);   // assignment
   void push_front(const T & t);   // inserts an element at the beginning
   void pop_front();   // deletes the first element
   void push_back(const T & t);   // inserts an element at the end
   void pop_back();  // deletes the last element
   void remove(const T & t);  // removes all elements that are equal to the passed element t
   void reverse();   // reversers the order of elements in the list
   void sort();  // sorts the elements in the list. Thesorting criterion is <operator defined for the elements
  Otheobject * insert(Otherobject * pos, const Otherobject &oo);  // inserts a copy of  oo  before pos, returnan   iterator(point) pointing to the inserted copy of oo
   void print();
   // and so on...
};

第 6 楼

得分:0

我是把一组数据分成左右两个部分，如<1,2,3,4,5|6,7,8,9,10>。fence就表示中间这条"|"，leftLength和rightLength分别表示左右这两部分的数据个数。程序我会继续改进的，谢谢kai。

第 7 楼

得分:0

我发现错误所在呢，我真是粗心啊。
template<class Elem>
bool LList<Elem>::setPos(int pos)
{
   if(pos<0 || pos > right_length + left_length)
      return false;
   fence = head;
   for(int i = 0; i < pos; pos++)            //应该是for(int i=0;i<pos;i++)

      fence = fence->next;
   return true;
}

这回没问题了，我觉得逻辑上还是没有错误的：
#include <iostream>
#include <cstdlib>
using namespace std;

template<class Elem>
class List
{
//Renitialize the list. The client is responsible for
//reclaiming the storage used by the list elements.
virtual void clear()=0;
//Insert an element at the front of the right partition
//Return true if successfull,false if the list if full.
virtual bool insert(const Elem &)=0;
//Append an element at the end of the right partition.Return
//true if successful,false if the list if full.
virtual bool append(const Elem &)=0;
//Remove the first element of the right partition.Return true
//if seccessful,false if the right partition is empty.
//The element removed is returned in the parameter.
virtual bool remove(Elem &)=0;
//Place fence at list start,making left partition empty.
virtual void setStart()=0;
//Place fence at list end,making right partition empty.
virtual void setEnd()=0;
//Move fence one step left;no change if already at start
virtual void prev()=0;
//Move fence one step right;no change if already at end
virtual void next()=0;
//Return length of left partition
virtual int leftLength() const=0;
//Return length of right partition
virtual int rightLength() const=0;
//If pos and more elements are in the list,set the size of left partition
//to pos and return true.Otherwise,do nothing and return false.
virtual bool setPos(int pos)=0;
//Return in first parameter the first element of the right partition.
//Return true if successful,flase if the right partition is empty.
virtual bool getValue(Elem&) const=0;
//Print the contents of the list
virtual void print() const=0;
};

template<class Elem>
class Link
{
public:
  Elem element;
  Link * next;
  Link(const Elem & elemval, Link * nextval = NULL)
  {
     element = elemval;
     next = nextval;
  }
  Link(Link * nextval = NULL)
  {
     next = nextval;
  }
};

template<class Elem>
class LList : public List<Elem>
{
private:
   Link<Elem> * head;
   Link<Elem> * tail;
   Link<Elem> * fence;
   int left_length;
   int right_length;
   void init()
   {
      fence = head = tail = new Link<Elem>;
      left_length = right_length = 0;
   }
   void removeall()
   {   //Return link nodes to free store
      while(head != NULL)
      {
         fence = head;
         head = head->next;
         delete fence;
      }
   }
public:
   LList(int size = 10)
   {
      init();
   }
   ~LList()
   {
      removeall();
   }
   void clear()
   {
      removeall();
      init();
   }
   bool insert(const Elem & );
   bool append(const Elem & );
   bool remove(Elem &);
   void setStart()
   {
      fence = head;
      right_length += left_length;
      left_length=0;
   }
   void setEnd()
   {
      fence = tail;
      left_length += right_length;
      right_length = 0;
   }
   void prev();
   void  next()
   {
      if(fence != tail)
      {
         fence = fence->next;
         right_length--;
         left_length++;
      }
   }
   int leftLength() const
   {
      return left_length;
   }
   int rightLength() const
   {
      return right_length;
   }
   bool setPos(int pos);
   bool getValue(Elem & it) const
   {
      if(rightLength() == 0)
         return false;
      it = fence->next->element;
      return true;
   }
   void print() const;
};

template<class Elem>
bool LList<Elem>::insert(const Elem & item)
{
   fence->next = new Link<Elem>(item,fence->next);
   if(tail == fence)
      tail = fence->next;
   right_length++;
   return true;
}
template<class Elem>
bool LList<Elem>::append(const Elem& item)
{
   tail = tail->next = new Link<Elem>(item, NULL);
   right_length++;
   return true;
}

template<class Elem>
bool LList<Elem>::remove(Elem & it)
{
   if(fence->next == NULL)
      return false;
   it = fence->next->element;
   Link<Elem> * ltemp = fence->next;
   fence->next = ltemp->next;
   if(ltemp == tail)
      tail = fence;
   delete ltemp;
   right_length--;
   return true;
}
template<class Elem>
void LList<Elem>::prev()
{
   Link<Elem> * temp = head;
   if(fence == head)
      return;
   while(temp->next != fence)
      temp = temp->next;
   fence = temp;
   left_length--;
   right_length++;
}

template<class Elem>
bool LList<Elem>::setPos(int pos)
{
   if(pos<0 || pos > right_length + left_length)
      return false;
   fence = head;
   for(int i = 0; i < pos; i++)
      fence = fence->next;
   return true;
}

template<class Elem>
void LList<Elem>::print() const
{
   Link<Elem> * temp = head;
   cout<<"<";
   while(temp != fence)
   {
      cout<<temp->next->element<<" ";
      temp = temp->next;
   }
   cout<<"|";
   while(temp->next != NULL)
   {
      cout<<temp->next->element<<" ";
      temp = temp->next;
   }
   cout<<">\n";
}

int main()
{
   int A[10] = {1,2,3,4,5,6,7,8,9,10};
   LList<int> list;
   for(int i=0; i<10; i++)
      list.append(A[i]);
   list.setPos(5);         //现在没问题了

   list.print();
   system("pause");
   return EXIT_SUCCESS;
}

第 8 楼

得分:0

我们都知道，我们真正需要的是一个可执行的程序，即一个 *.exe 文件。那么就是说，对于一个程序而言，main() 是真正的主干。对于C++ 程序员而言，他们往往认为 class 的设计是主干。我本人认为，这是本末倒置。一个class 只是因为问题的需要而予以设计的。记得编写程序的方法，或称为编写程序的过程，在另外一篇帖子里提到了，这里不再重复了。

当然，我们有时候的确是仅仅为了设计class 而设计class. 那么一个 main只是用于检测的辅助程序而以。即便是这样，考虑问题的时候，我们还是应该考虑 main, 再考虑class,这样我们才能更清楚地知道，对于一类object, 他到底应该具备哪些特性： private 数据以及方法，哪些能力：public方法。

对于独立的，没有依赖关系的方法，我们应该写一个检测一个，（通过main 来检测）
对于有依赖关系的方法，我们应该写完一组，检测一下。这样问题即便出现，也可以当场解决。

第 9 楼

得分:0

恩，同意。一下子就让我设计类，根本不知道应该有什么方法，哪些功能在哪些类里实现。哪些类继承就可以。

成功会使人骄傲。如果你骄傲自大，你就会停止学习。不学习，人就停止了进步

第 10 楼

得分:0

这程序也写得太没有编程风格了啊