题目：单链表操作验证
1．实验目的
(1)掌握线性表的链接存储结构；
(2)验证单链表及其基本操作的实现；
(3)进一步掌握数据结构及算法的程序实现的基本方法。
2．实验内容
(1)用头插法（或尾插法）建立带头结点的单链表；
(2)对已建立的单链表实现插人、删除、查找等基本操作。
3．实现提示（此为C++版，具体实验用C语言实现，下同）
首先，将单链表中的结点定义为如下结构类型：
template <class T>
struct Node
｛
T data；
Node<T> *next；
｝；
其次，定义单链表的数据类型——单链表类LinkList,包括题目要求的插人、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出单链表的元素。
template＜class T>
class LinkList
｛
public：
LinkList(T a[ ]，int n)； //建立有n个元素的单链表
~LinkList( )； //析构函数
void Insert(int i，T x)； //在单链表中第i个位置插入元素值为x的结点
T Delete(int i)； //在单链表中删除第i个结点
int Locate(T x)； //求单链表中值为x的元素序号
void PrintList()； //遍历单链表，按序号依次输出各元素
private：
Node<T＞*first； //单链表的头指针
｝;
再次，设计单链表类LinkList的构造函数和析构函数。
用头插法或尾插法建立单链表。头插法建立单链表的算法如下：
头插法建立单链表
temlate <class T>
LinkList::LinkList(T a[]，int n)
{
first=new Node<T>；
first->next=NULL； //初始化一个空链表
for(i=0；i<n；i++)
{
s=new Node<T>； s->data=a[i]； //为每个数组元素建立一个结点
s->next=first->next；//插入到头结点之后
first->next=s；
}
}
析构函数用于释放单链表中所有结点，算法如下：
单链表的析构函数算法~LinkList
template :: ~LinkList()
{
p=first； //工作指针P初始化
while(p) //释放单链表的每一个结点的存储空间
{
q=p； //暂存被释放结点
p=p->next； //工作指针P指向被释放结点，使单链表不断开
delete q；
}
}
最后，对所建立的单链表设计插人、删除、查找等基本操作的算法。
（l）插人算法
单链表插人算法Insert
template<class T>
void LinkList::Insert(int i，T x)
{
p=first；j=0； //工作指针P初始化
while (p && j<i-1)
{
p=p->next； //工作指针P后移
j++；
}
if (! p) throw“位置”；
else{
s=new Node<T>； s->data=x； //向内存申请一个结点s，其数据域为x
s->next=p->next；//将节点s插入到结点p之后
p->next=s；
}
}
(2)删除算法
单链表的删除算法Delete
Template<class T>
T LinkList::Delete(int i)
{
P=first ；j=0；//工作指针p初始化
While (p && j<i-1) //查找第i-1个结点
{
p=p->next；
j++；
}
if ( ! p | | ! p->next) throw“位置”； //结点p不存在或结点p的后继结点不存在
else{
q=p->next; x=q->data; //暂存被删结点
p->next=q->next; //摘链
delete q;
return x;
}
}
(3)查找算法
单链表查找算法Locate
template <class T>
int LinkList::Locate(T x)
{
p=first->next; j=1;
while(p && p->data!=x)
{
p=p->next; //工作指针p后移
j++;
}
if (p) return j;
else return 0;
}
4.实验程序
//以下为头函数，文件名为LinkList.h
＃ifndef LinkList_H
＃define LinkList_H
template＜class T>
struct Node
{
T data；
Node< T> *next; //此处<T>也可以省略
};
template <class T>
class LinkList
{
Public：
LinkList(T a［］，int n)； //建立有n个元素的单链表
~LinkList（）； //析构函数
void Insert(int i, T x)； //在单链表中第i个位置播入元素为x的结点
T Delete(int i)； //在单链表中删除第i个结点
int Locate(T x); //求单链表中值为x的元素序号
void PrintList()； // 遍历单链表，按序号依次输出各元素
private：
Node<T> *first； //单链表的头指针
}；
＃endif
//以下为头函数LinkList.h中LinkList类的成员函数按规定定义，文件名为LinkList.cpp
＃include"LinkList．h"
template <class T>
LinkList<T>::LinkList（T a[]，int n)
{
Node<T> * first；
first＝new Node<T>；
first->next＝NULL； //初始化一个空链表
for（int i＝0；i<n; i＋＋）
｛
Node<T> *s；
s=new Node<T>; s->data=a[i]; //为每个数组元素建立一个结点
s->next=first->next; //插入到头结点之后
first->next＝s；
｝
}
template <class T>
LinkList::~LinkList()
{
Node<T＞ *p, *q;
p= first; //工作指针P初始化
while（p） //释放单链表的每一个结点的存储空间
｛
q=p; //暂存被释放结点
p=->next; //工作指针P指向被释放结点的下一个结点,//使单链表不断开
delete q；
｝
}
template <class T>
void LinkList<T>::Insert(int i，T x)
{
Node<T> *p; int j；
p＝first；j=0； //工作指针p初始化
while（P && 7<I-1）
{
P＝P->next; //工作指针P后移
j＋＋;
}
if（！p) throw”位置”，
else｛
Node<T> *s;
s＝new Node<T>；
s->data = x; //向内存申请一个结点：，其数据域为x
s->next＝p->next； //结点s插人到结点p之后
P->next=s;
｝
｝
template <class T>
T LinkList<T>::Delete(int i)
{
Node<T> *p；int j；
P=first；j＝0； //工作指针P初始化
while (p“j<I-1) //查找第i-1个结点
｛
p＝p->next；
j＋＋；
｝
if（！P||！P->next） throw“位置”；//结点P不存在或结点P的后继结点不存在
else｛
Node<T> *q；int x；
q＝p->next; x=q-> data; //暂存被删结点
p-> next=q->next； //摘链
delete q；
return x；
｝
}
template <class T>
int LinkList<T>::Locate(T x)
｛
Node<T>，p；int j；
P=first->next；j=1；
while（p && p->data!=x)
｛
p=p->next；
j＋＋；
｝
if(p) return j；
else return 0；
｝
template <class T>
void LinkList<T>::PrintList()
｛
Node<T> *p；
p=first->next；
while (p)
｛
cout<＜p->data<＜endl；
p＝p ->next；
｝
｝
//以下为主函数
＃include< iostream. h> //引用输入输出流库函数的头文件
＃include”LinkList.cpp” //引用单链表类的声明和定义
void main()
｛
int r[]=｛1，2，3，4，5｝;
LinkList<int> a(r，5）；
cout< <”执行插人操作前数据为：”< < endl；
a. PrintList()； //显示链表中所有元素
try
｛
a.Insert(2，5）；
｝
catch（char *s）
｛
cout<＜s<＜endl；
｝
cout＜＜”执行插人操作后数据为：”＜＜endl；
a. PrintList()； //显示链表中所有元素
cout＜＜”值为5的元素位置为：”；
cout< <a.Locate(5)＜＜endl; //查找元素5,并返回在单链表中位置
cout＜＜”执行删除操作前数据为：”＜＜endl；
a.PrintList()； //显示链表中所有元素
try
｛
a.Delete(1)； //删除元素4
｝
catch（char *s）
{
cout<＜s<＜endl；
｝
cout< <”执行删除操作后数据为：”< < endl；
a.PrintList（）； //显示链表中所有元素
｝