释放单链表

Question

请问是什么意思？

Answer 1

链表和其他的数据结构不一样的地方就在于，它会占用内存，而且你用完之后，即使删除了某个节点，它也不会自己释放内存，必须用free函数来释放，就是free(*p)，其中p是指向这个节点的指针，这个问题在java里面得到了解决，因为java里面带有一个自动的程序，就是垃圾清理器，它会定时在系统的内存中运行，遇到没用的内存就会释放掉，然后回收，在C#里面也不用担心释放的问题，不过释放不用的节点是编程的一个好习惯哟！

Answer 2

按字面意思来看，估计是把单链表中的所有结点逐个删除，并回收其占用的内存空间。追问

写成程序怎么写？

追答

代码我就不写了，我告诉你算法思路。
首先获得链头指针，然后每次将链头指针向链尾移动一个位置，就把它的直接前驱释放掉。这个过程直到链头指针为空为止。

Answer 3

//输入功能请在调用Insert()之前,自己在main()中设置好入参

#include<iostream.h>
#include<math.h>

const double eps=1e-5;

//基类
template<class T>
class LinearList
{
public:
virtual bool IsEmpty()const=0;
virtual int Length()const=0;
virtual bool Find(int i,T &x)const=0;
virtual int Search(T x)const=0;
virtual bool Insert(int i,T x)=0;
virtual bool Delete(int i)=0;
virtual bool Update(int i,T x)=0;
virtual void Output(ostream &out)const=0;

protected:
int n; //the length
};

template<class T>
class SingleList;

//节点
template<class T>
class Node
{
private:
T element;
Node<T> *link;
friend class SingleList<T>;
};

//真正实现的线性链表类
template<class T>
class SingleList:public LinearList<T>
{
public:
SingleList();
~SingleList();
bool IsEmpty()const;
int Length()const;
bool Insert(int i,T x);
bool Find(int i,T &x)const;
int Search(T x)const;
bool Delete(int i);
bool Update(int i,T x);
bool Delete(T x);
bool Reverse();
void Output(ostream &out)const;
private:
Node<T> *first;
};

template<class T>
SingleList<T>::SingleList()
{
first=NULL;
n=0;
}

template<class T>
SingleList<T>::~SingleList()
{
Node<T> *p;
while(first)
{
p=first->link;
delete first;
first=p;
}
}

template<class T>
bool SingleList<T>::IsEmpty()const
{
return n==0;
}

template<class T>
int SingleList<T>::Length()const
{
return n;
}

//按下标查找,找到的值放入x
template<class T>
bool SingleList<T>::Find(int i,T &x)const
{
if(i<0||i>n-1)
{
cout<<"Out Of Bounds"<<endl;
return false;
}
Node<T> *p=first;
for(int j=0;j<i;j++)
{
p=p->link;
}
x=p->element;
return true;
}

//按值x查找,返回下标
template<class T>
int SingleList<T>::Search(T x)const
{
Node<T> *p=first;
for(int j=0;p&&abs(x-(p->element))>eps;j++)
{
p=p->link;
}
if(p)
return j;
return -1;
}

//按下标删除
template<class T>
bool SingleList<T>::Delete(int i)
{
if(!n)
{
cout<<"Underflow!"<<endl;
return false;
}
if(i<0||i>n-1)
{
cout<<"Out Of Bounds!"<<endl;
return false;
}
Node<T> *p=first, *q=first;
for(int j=0;j<i-1;j++)
{
q=q->link;
}

if(i==0)
{
first=first->link;
}
else
{
p=q->link;
q->link=p->link;
}
delete p;
n--;
return true;
}

//按值x删除
template<class T>
bool SingleList<T>::Delete(T x)
{
if(!first)
{
cout<<"Underflow!"<<endl;
return false;
}
else
{
Node<T> *p;

for(p=first;p!=NULL;p=p->link)
{
if(abs(x-(p->element))<eps&&p==first)
{
first=first->link;
delete p;
n--;
return true;
}
else if(abs(x-(p->element))<eps)
{
Node<T> *q=first;
while(q->link!=p)
{
q=q->link;
}
q->link=p->link;
delete p;
n--;
return true;
}
}
cout<<"Not Found,delete failed!"<<endl;
return false;
}
}

//i=-1,插入到头结点;否则插入到下标为i的节点之后
template<class T>
bool SingleList<T>::Insert(int i,T x)
{
if(i<-1||i>n-1)
{
cout<<"Out Of Bounds!"<<endl;
return false;
}
Node<T> *q=new Node<T>;
q->element=x;
Node<T> *p=first;

if(i>-1)
{
for(int j=0;j<i;j++)
{
p=p->link;
}
q->link=p->link;
p->link=q;
}
else
{
q->link=first;
first=q;
}
n++;
return true;
}

template<class T>
bool SingleList<T>::Update(int i,T x)
{
if(i<-1||i>n-1)
{
cout<<"Out Of Bounds!"<<endl;
return false;
}
Node<T> *p=first;
for(int j=0;j<i;j++)
{
p=p->link;
}
p->element=x;
return true;
}

template<class T>
void SingleList<T>::Output(ostream &out)const
{
Node<T> *p=first;
while(p)
{
out<<p->element<<" ";
p=p->link;
}
out<<endl;
}