搜索单链表最后一个结点的算法

//带附加头结点的单链表的类
#include<iostream.h>//使用cout,cin,cerr
#include<stdlib.h>//使用exit(1)

template<class T>
struct LinkNode{
    T data;
    LinkNode<T> *link;
    LinkNode(LinkNode<T> *ptr=NULL){ link=ptr; }
    LinkNode(const T &item,LinkNode<T> *ptr=NULL)
    { data=item; link=ptr; }
};

template<class T>
class List{
    public:
        //实验题2.19
        List(){ first=new LinkNode<T>; }//无参数构造函数
        List(const T &x){ first=new LinkNode<T>(x); }
//有参数构造函数，赋值头结点
        List(List<T> &L);//复制构造函数
        ~List(){ makeEmpty(); delete first; }//析构函数
        void makeEmpty();//清空单链表函数
        bool IsEmpty()const{// 判表空否函数
            return first->link==NULL;}
        LinkNode<T> *getHead()const{ return first; }//返回附加头结点地址函数
        void setHead(LinkNode<T> *p){//设置附加头结点地址函数
            makeEmpty();
            delete first;
            first=p;
        }
        void inputFront(T endTag);//前插法建立单链表函数。输入
        void inputRear(T endTag);//后插法建立单链表函数。输入
        void output();//输出函数
        //实验题2.20
        LinkNode<T> *Search(T x);
//搜索函数。搜索x在表中位置，返回结点地址，NULL没找到
        LinkNode<T> *Locate(int i);
//定位函数。定位第i个结点，返回结点地址，NULL无效
        bool getData(int I,T &x);
//取数据函数。x返回第i个结点的数据，失败函数返回false
        void setData(int i,T &x);//修改数据函数。用x修改第i个元素的数据值
        //实验题2.21
        int Length()const;//计算表长度函数
        bool Insert(int i,T &x);//插入函数。在第i个表项后插入x
        bool Remove(int i,T &x);//删除函数。删除第i个表项，通过x返回
        List<T>& operator=(List<T> &L);//运算符“=”重载函数
    private:
        LinkNode<T> *first;
};

将实验题2.19,2.20的成员函数实现复制到此；
//复制构造函数的实现；
template<class T>
List<T>::List(List<T> &L)
{
    T value;
     LinkNode<T> *srcptr = L.getHead();   //被复制表的附加头结点地址
     LinkNode<T> *destptr = first = new LinkNode<T>;
     while(srcptr->link  != NULL)
     {
         value = srcptr->link->data;
         destptr->link = new LinkNode<T>(value);
         destptr = destptr->link;
         srcptr = srcptr->link;
     }
     destptr->link = NULL;
}

template<class T>
void List<T>::makeEmpty()
{
     LinkNode<T> *current;
     while(first->link != NULL)
     {
         current = first->link;
         first->link = current->link;
         delete current;
     }
}

//前插法建立单链表函数的实现；
template<class T>
void List<T>::inputFront(T endTag)
{
    LinkNode<T> *newNode;
     T val;
     makeEmpty();
     cin>>val;
     while (val != endTag)
     {
         newNode = new LinkNode<T>(val);
         if (newNode == NULL)
         {
              cerr<<"存储分配错误！"<<endl;
             exit(1);
         }
         newNode->link = first->link;
         first->link = newNode;
         cin>>val;
     }
}

//后插法建立单链表函数的实现；
template<class T>
void List<T>::inputRear(T endTag)
{

    LinkNode<T> *newNode,*last;
    T val;
     makeEmpty();
     cin>>val;
     last = first;
     while (val != endTag)
     {
         newNode = new LinkNode<T>(val);
         if (newNode == NULL)
         {
              cerr<<"存储分配错误！"<<endl;
              exit(1);
         }
         last->link = newNode;
         last = newNode;
         cin>>val;
     }
     last->link = NULL;
}

//输出函数的实现。
template<class T>
void List<T>::output()
{
    LinkNode<T> *current = first->link;
     while(current != NULL)
     {
          cout<<current->data<<endl;
         current = current->link;
     }
}
//搜索函数的实现
template<class T>
LinkNode<T> *List<T>::Search(T x)

{
     LinkNode<T> *current = first->link;
     while(current != NULL)
     
         if(current->data == x)
         break;
         else
              current = current->link;
     
     return current;
}

//定位函数的实现
template<class T>

LinkNode<T> *List<T>::Locate(int i)

{

     if(i < 0)
         return NULL;

     LinkNode<T> *current = first;
     int k = 0;
     while(current != NULL && k < i)
     {
         current = current->link;
         k++;
     }
     return current;    //返回第i个结点地址，若返回NULL，则表示i太大
}

//取数据函数的实现
template<class T>
bool List<T>::getData(int i,T &x)
{
     if(i <= 0)
        return false; //i值太小
     LinkNode<T> *current = Locate(i);
     if(current == NULL)         //i值太大
         return false;
     else
     {
         x = current->data;
         return true;
     }
}
//修改数据函数的实现
template <class T>
void List<T>::setData(int i,T& x)
{
    if (i<=0) return;
    LinkNode<T> *current=Locate(i);
    if (current ==NULL) return;
    else current->data=x;
}


计算表长度函数的实现；
template<class T>
int List<T>::Length()const
{
    LinkNode<T> *current = first->link;
    int count=0;
    while(current != NULL)
    {
        ++count;
        current = current->link;
    }
    return count;
}

插入函数的实现；
template<class T>
bool List<T>::Insert(int i,T &x)
{
     LinkNode<T> *current = Locate(i);
     if(current == NULL)
         return false;
     LinkNode<T> *newNode = new LinkNode<T>(x);
     if(newNode == NULL)
     {
         cerr<<"存储分配错误！"<<endl;
         exit(1);
    }
     newNode->link = current->link;
     current->link = newNode;
     return true;
}
删除函数的实现；
template<class T>
bool List<T>::Remove(int i,T &x)
{
     LinkNode<T> *current = Locate(i-1);
     if(current == NULL || current->link == NULL)
         return false;
     LinkNode<T> *del = current->link;    //重新拉链，将被删结点从链中摘下
     current->link = del->link;
     x = del->data;
     delete del;
     return true;

}
运算符“=”重载函数的实现；
template <class T>
List<T> &List<T>::operator = (List<T> &L)
{//重载函数'='实现A=B
T value;
LinkNode<T> *srcptr=L.getHead();//被复制表的附加头结点地址
LinkNode<T> *destptr=first=new LinkNode<T>;
while (srcptr->link!=NULL)//逐个结点复制
{
   value=srcptr->link->data;
   destptr->link=new LinkNode<T>(value);
   destptr=destptr->link;
   srcptr=srcptr->link;
}
destptr->link=NULL;
return *this;
}
//以上是单链表的类
编写递归函数和非递归函数：搜索单链表最后一个结点。
下面是程序的基本框架：
#include"02_21_060List.h"//用实验题2.21定义的单链表
template<class T>
LinkNode<T>* FindRear_1(LinkNode<T> *f){//递归函数
函数体
}

template<class T>
LinkNode<T>* FindRear_2(LinkNode<T> *f){//非递归函数
函数体
}

void main(){
List<char> L;
cout<<"后插法建立单链表: \n";
L.inputRear('#');
cout<<"用递归函数，最后一个结点的字符为 "
  <<FindRear_1(L.getHead())->data<<endl;
cout<<"用非递归函数，最后一个结点的字符为 "
  <<FindRear_2(L.getHead())->data<<endl;
}