实验报告配套教材：
书名：数据结构 C++版 第2版
作者：王红梅 胡明 王涛
出版社：清华大学出版社
实验报告概述：
班级：计算机11-1 学号： 姓名： 成绩：_________
实验三 单链表操作验证
一、实验目的
⑴ 掌握线性表的链接存储结构；
⑵ 验证单链表及其基本操作的实现；
⑶ 进一步掌握数据结构及算法的程序实现的基本方法。
二、 实验内容
⑴ 用头插法（或尾插法）建立带头结点的单链表；
对已建立的单链表实现插入、删除、查找等基本操作。
设计与编码
#include
using namespace std;
template
struct Node
{
T data;
Node *next;
};
template
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 *first; //单链表的头指针
};
template
LinkList::LinkList(T a[ ], int n)
{
Node*s;
int i;
first=new Node();
first->next=NULL; //初始化一个空链表
for (i=0; i();
s->data=a[i]; //为每个数组元素建立一个结点
s->next=first->next; //插入到头结点之后
first->next=s;
}
}
template
LinkList:: ~LinkList( )
{
Node*p,*q;
p=first;//工作指针p初始化
while(p) //释放单链表的每一个结点的存储空间
{
q=p; //暂存被释放结点
p=p->next;//工作指针p指向被释放结点的下一个结点，使单链表不断开
delete q;
}
}
template
void LinkList::Insert(int i, T x)
{
Node*p,*s;
p=first;
int j=0; //工作指针p初始化
while (p && jnext; //工作指针p后移
j++;
}
if (!p) throw "位置";
else {
s=new Node();
s->data=x; //向内存申请一个结点s，其数据域为x
s->next=p->next; //将结点s插入到结点p之后
p->next=s;}}
template
T LinkList::Delete(int i)
{
Node*p,*q;
int x;
p=first;
int j=0; //工作指针p初始化
while (p && jnext;
j++;}
if (!p||!p->next) throw "位置"; //结点p不存在或结点p的后继结点不存在
else {
q=p->next;
x=q->data; //暂存被删结点
p->next=q->next; //摘链
delete q;
return x;}}
template
int LinkList:: Locate(T x)
{
Node*p;
p=first->next;
int j=1;
while (p && p->data!=x)
{
p=p->next; //工作指针p后移
j++;}
if (p) return j;
else return 0;
}
template
void LinkList::PrintList( )
{
Node*p;
p=first->next;
while(p!=NULL)
{
cout<<" "<data<<" ";
p=p->next;
}
cout<s1(a,5);
int n,j,k,loc;
int flag=1;
while(flag)
{cout<<"请输入你所需要的选项：";
cin>>j;
switch(j)
{case 1:
{s1.PrintList();
break;}
case 2:
{
cout<<"请输入你要插入的位置和数字:";
cin>>n>>k;
s1.Insert(n,k);
break;}
case 3:
{
cout<<"请输入你要删除的数字的位置：";
cin>>n;
s1.Delete(n);
break; }
case 4:
{
cout<<"请输入你要查找的值：";
cin>>k;
loc=s1.Locate(k);
cout<<"所查数据所在："<
