- #include<iostream>
- #include<fstream>
- using namespace std;
-
- //链表节点的结构定义
-
- struct chainNode
- {
- //数据成员
- int element;//数据域
- chainNode* next;//指针域
-
- //方法:构造函数形成重载
- chainNode(){}
- chainNode(const int& element)
- {
- this->element=element;
- }
- chainNode(const int& element,chainNode* next)
- {
- this->element=element;
- this->next=next;
- }
- };
-
-
- class linearList
- {
- public:
- virtual ~linearList(){};
- virtual bool empty()const=0;
- virtual int size()const=0;
- virtual int& get(int theIndex)const=0;
- virtual int indexOf(const int& theElement)const=0;
- virtual void erase(int theIndex)=0;
- virtual void insert(int theIndex,const int& theElement)=0;
- virtual void output(ostream& out)const=0;
- };
-
-
- class chain:public linearList
- {
- public:
- //构造函数,复制构造函数和析构函数
- chain(int initCapacity=10);
- chain(const chain&);
- ~chain();
-
- //方法
- bool empty()const
- {
- return listSize==0;
- }
- int size()const
- {
- return listSize;
- }
- int& get(int theIndex)const;
- int indexOf(const int& theElement)const;
- void erase(int theIndex);
- void insert(int theIndex,const int& theElement);
- void output(ostream& out)const;
-
- private:
- chainNode* firstNode;//指向链表第一个节点的指针,也是链表的唯一对外接口
- int listSize;//线性表的元素个数
- };
-
- //链表的构造和复制构造函数
-
- chain::chain(int initCapacity)
- {
- //构造函数
- //判断是否合法
- if(initCapacity<1)
- {
- cout<<"Initial Capacity = "<<initCapacity<<" must be > 0"<<endl;
- return;
- }
- firstNode=NULL;
- listSize=0;
- }
-
-
- chain::chain(const chain& theList)
- {
- //复制构造函数
- listSize=theList.listSize;
- if(listSize==0)
- {
- //如果原链表为空
- firstNode=NULL;
- return;
- }
- //链表theList非空
- chainNode* sourceNode=theList.firstNode;
- //先复制首元素
- firstNode=new chainNode(sourceNode->element);//为新链申请一块新的内存空间
- sourceNode=sourceNode->next;
- chainNode* targetNode=firstNode;//创建targetNode的原因是:链表必须有firstNode,不可以直接使用它
- //到了此处,targetNode指向新链的第一个节点;sourceNode指向原链的第二个节点,错开一个节点才可以实现复制
- while(sourceNode!=NULL)
- {
- //复制剩余元素
- targetNode->next=new chainNode(sourceNode->element);
- //此节点复制完成,指针向后移动1
- targetNode=targetNode->next;
- sourceNode=sourceNode->next;
- }
- //节点全部复制完成,尾节点指针域还要指向空
- targetNode->next=NULL;
- }
-
-
- chain::~chain()
- {
- //链表的析构函数,删除链表的所有节点(销毁链表)
- //算法思想:重复清除链表的首节点,直到链表为空,在清除首节点之前必须用变量nextNode保存第二个节点的指针,否则无法找到下一个节点的地址
- while(firstNode!=NULL)
- {
- //删除首节点
- chainNode* nextNode=firstNode->next;
- delete firstNode;
- firstNode=nextNode;
- }
- }
-
- //方法get:返回索引为theIndex的元素(数据域)
-
- int& chain::get(const int theIndex)const
- {
- //若该元素不存在
- if(theIndex<0||theIndex>listSize-1)
- {
- cout<<"out of range!"<<endl;
- return -1;
- }
- chainNode* currentNode=firstNode;//需要新开一个指针,不可以直接改变firstNode
- for(int i=0;i<theIndex;i++)
- {
- currentNode=currentNode->next;
- }
- return currentNode->element;
- }
-
- //方法indexOf:返回元素theElement首次出现时的索引
-
- int chain::indexOf(const int& theElement)const
- {
- chainNode* currentNode=firstNode;
- int index=0;
- while(currentNode!=NULL&¤tNode->element!=theElement)//结束条件1:遍历完没有找到;结束条件2:找到了
- {
- index++;
- currentNode=currentNode->next;
- }
- //确定是否找到
- if(currentNode==NULL)
- {
- return -1;
- }
- else
- {
- return index;
- }
- }
-
- //方法erase:删除索引为theIndex的元素
- //三种情况:1、theIndex<0或者theIndex>=listSize,没有这个位置上的元素,或者链表为空
- //2、删除非空表的第0个元素节点
- //3、删除其他元素节点
-
- void chain::erase(int theIndex)
- {
- //索引无效
- if(theIndex<0||theIndex>=listSize)
- {
- cout<<"out of range!"<<endl;
- return;
- }
- //索引有效
- chainNode* deleteNode;
- if(theIndex==0)
- {
- //删除链表首节点
- deleteNode=firstNode;
- firstNode=firstNode->next;
- }
- //删除其他节点
- else
- {
- //用指针p指向要删除节点的 前驱节点(如果是双向链表,则可以直接指到被删除节点)
- chainNode* p;
- for(int i=0;i<theIndex-1;i++)
- {
- p=p->next;
- }
- deleteNode=p->next;
- p->next=p->next->next;//删除deleteNode指向的节点
- }
- listSize--;//链表节点个数减一
- delete deleteNode;
- }
-
- //方法insert:在索引为theIndex的位置插入一个新元素(过程和erase类似)
-
- void chain::insert(int theIndex,const int& theElement)
- {
- //索引无效
- if(theIndex<0||theIndex>=listSize)
- {
- cout<<"out of range!"<<endl;
- return;
- }
- //索引有效
- //在表头插入
- if(theIndex==0)
- {
- //最简单的方法就是用前面类中的构造函数
- firstNode=new chainNode(theElement,firstNode);//太妙了!!!
- }
- else
- {
- //寻找新元素的前驱
- chainNode* p;
- for(int i=0;i<theIndex-1;i++)
- {
- p=p->next;
- }
- // chainNode<T>* addNode=new chainNode<T>(theElement);
- // addNode->next=p->next;
- // p->next=addNode;
- p->next=new chainNode(theIndex,p->next);
- }
- listSize++;//链表元素个数加一
- }
-
- int main()
- {
- chain c(1);
- c.insert(0,1);
-
- return 0;
- }
-
-
错误提示是在get函数实现里面的return -1;
哪里有问题呢?
我把return -1注释掉的话就出现错误:[Error] ld returned 1 exit status