#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
