搜索单链表最后一个结点的算法
//带附加头结点的单链表的类#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;
}
