~LinkList( );
int Length( );
DataType Get(int i);
int Locate(DataType x);
void Insert(int i, DataType x);
DataType Delete(int i);
DataType Deletev(DataType x);
void PrintList();
private:
Node<DataType> *first;
};
template <class DataType>
LinkList<DataType>::LinkList()//无参构造方法
{
first=new Node<DataType>();
first->next=NULL;
}
template <class DataType>
LinkList<DataType> :: LinkList(DataType a[ ], int n)
{
first = new Node<DataType>; //生成头结点
Node<DataType> *r = first;
Node<DataType> *s;
for (int i = 0; i < n; i++)
{
s = new Node<DataType>; s->data = a[i];
r->next = s; r = s;
}
r->next = NULL;
}
template <class DataType>
void LinkList<DataType> :: PrintList()
{
Node<DataType> *p;
p = first->next;
while (p != NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}

template <class DataType>
int LinkList<DataType> :: Length()
{
Node<DataType> *p;
p = first->next; int count = 0;
while (p != NULL)
{
count++;
p=p->next;
}
return count; //退出循环表明查找失败
}
template <class DataType>
DataType LinkList<DataType> :: Get(int i )
{
Node<DataType> *p;
p = first->next; int count = 0;
while (p != NULL)
{
count++;
if(count==i) return p->data;
p=p->next;
}
return 0; //退出循环表明查找失败
}
template <class DataType>
int LinkList<DataType> :: Locate(DataType x)
{ Node<DataType> *p;
p = first->next; int count = 1;
while (p != NULL)
{
if (p->data == x) return count; //查找成功，返回序号
p = p->next;
count++;
}
return 0; //退出循环表明查找失败
}
template <class DataType>
void LinkList<DataType> :: Insert(int i, DataType x)
{ Node<DataType> *p;
p = first ; int count = 0; //工作指针p应指向头结点
while (p != NULL && count < i - 1) //查找第i – 1个结点
{
p = p->next;

count++;
}
if (p == NULL) throw "位置"; //没有找到第i – 1个结点
else {
Node<DataType> *s = new Node<DataType>; s->data = x; //申请一个结点s
s->next = p->next; p->next = s; //结点s插入结点p之后
}
}
template <class DataType>
DataType LinkList<DataType> :: Delete(int i)
{ Node<DataType> *p;
Node<DataType> *q;
p = first ; int count = 0;
while (p != NULL && count < i - 1)
{
p = p->next;
count++;
}
if (p == NULL || p->next == NULL) throw "无此位置";
else {
q = p->next; DataType x = q->data;
p->next = q->next;
delete q; return x;
}
}
template <class DataType>
DataType LinkList<DataType> :: Deletev(DataType x)
{
int loc= Locate(x);
if (loc==0)
{
throw "链表中无此数据";
}
else
{
return Delete(loc);
}
return 0;
}

template <class DataType>
LinkList<DataType> :: ~LinkList( )
{ Node<DataType> *q;
while (first != NULL)
{
q = first;
first = first->next;
delete q;
}
}
测试test.cpp 测试单链表的功能：
#include <iostream>
#include "LinkedList.h"
using namespace std;
const MAX=100;
int main( ) {
cout<<"输入正数数据构造单链表，并以负数作为结束标记\n";
float a[MAX];
int i=0,k=0;
cin>>k;
while(k>0)
{
a[i++]=k;
cin>>k;
}
LinkList<float> list(a,i);
int choice=1;
cout<<" 欢迎，欢迎!"<<endl;
cout<<"1.显示链表中的信息\n";
cout<<"2.按位置删除数据\n";
cout<<"3.按值删除数据\n";
cout<<"4.查找数据的位置信息\n";
cout<<"5.在链表的某个位置插入数据\n";
cout<<"6.读取某位置上的信息\n";
cout<<"0.退出程序\n";
cout<<"请输入您的选择：";
cin>>choice;
while(1){
switch (choice){
case 0: exit(0);//退出程序
case 1:
{
cout<<"链表详细信息:\n";
list.PrintList();break;}

case 2:
{cout<<"输入要删除的数据的位置？\n";
int del;
cin>>del;
try
{list.Delete(del);
}catch(char *s){cout<<s<<endl;}
break;}
case 3:
{cout<<"输入要删除的数据？\n";
int del;
cin>>del;
try{
list.Deletev(del);}catch(char *s) {cout<<s<<endl;}break;}
case 4:
{if(list.Length()==0)
{cout<<"链表为空，不能查找\n";}
else{
cout<<"请输入要查找数据为?";
float search;
cin>>search;
cout<<"数据"<<search<<"在链表中的位置是"<<list.Locate(search)<<endl;
} break;}
case 5:
{cout<<"输入要添加的数据？";
int des;
float it;
cin>>it;
cout<<"想让该数据存储为第几个节点？";
cin>>des;
if((des>list.Length())||des<1)
cout<<"输入位置错误\n";
else
list.Insert(des, it);break;}
case 6:
{cout<<"想读取第几个节点？";
int c;
cin>>c;
if(c<1||c>list.Length())
cout<<"位置不合法\n";
else
cout<<"链表中的位置"<<c<<"的数据是："<<list.Get(c)<<endl;
break;

}
default :cout<<"输入错误!\n";
}
cout<<"\n1.显示链表中的信息\n";
cout<<"2.按位置删除数据\n";
cout<<"3.按值删除数据\n";
cout<<"4.查找数据的位置信息\n";
cout<<"5.在链表的某个位置插入数据\n";
cout<<"6.读取某位置上的信息\n";
cout<<"0.退出程序\n";
cout<<"请输入您的选择：";
cin>>choice;
}
return 0;
}

实验一 线性表的操作
实验类型：验证性
实验要求：必修
实验学时： 2学时
一、实验目的：
参照给定的线性表顺序表类和链表类的程序样例，验证给出的线性表的常见算法。
二、实验要求：
1、掌握线性表顺序表类和链表类的特点。掌握线性表的常见算法。
2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容：
题目一．设计一个静态数组存储结构的顺序表类，要求编程实现如下任务：建立一个线性表，首先依次输人数据元素1，2，3，…，10，然后删除数据元素6，最后依次显示当前线性表中的数据元素。要求采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不会超过50个。
题目二、设有线性表LA=(3,5,8,11),LB=(2,6,8,9,11,15,20);要求用顺序表实现.
若LA和LB分别表示两个集合A和B，求新集合A=A∪B（相同元素保留）预测输出LA=（2，3，5，6，8，8，9，11，11，15,20）
四、程序样例
顺序表类定义：将该类保存在文件SeqList.h中。
const int MaxSize=100;
template <class T> //模板类
class SeqList
{
public:
SeqList() {length=0;} //无参构造函数
SeqList(T a[],int n); //有参构造函数
~SeqList(){} //析构函数
int Length() {return length;} //求线性表长度
T Get(int i); //按位查找
int Locate(T x); //按值查找
void Insert (int i, T x); // 插入函数
T Delete(int i); //删除函数
void PrintList(); //遍历线性表，按序号依次输出各个元素。
private:
T data[MaxSize];
int length;
};

template<class T>
SeqList<T>::SeqList(T a[],int n) //有参构造函数
{
if(n>MaxSize)throw"参数非法";
for(int i=0;i<n;i++)
data[i]=a[i];
length=n;
}
template <class T>
void SeqList<T>::Insert(int i,T x) //插入函数
{
if (length>=MaxSize) throw "上溢";
if(i<1||i>length+1) throw "位置异常";
for (int j=length;j>=i;j--)
data[j]=data[j-1];
data[i-1]=x;
length++;
}
template <class T>
T SeqList<T>::Get(int i) //按位查找函数
{
if(i<1||i>length) throw "查找位置非法";
else return data[i-1];
}
template <class T>
int SeqList<T>::Locate(T x) //按值查找函数
{
for (int i=0;i<length;i++)
if (data[i]==x)return i+1;
return 0;
}
template <class T>
T SeqList<T>::Delete(int i) //删除函数
{
if (int length=0)throw "下溢";
if(i<1||i>length)throw "位置异常";
T x=data[i-1];
for(int j=i;j<length;j++)
data[j-1]=data[j];
length--;
return x;

}
template<class T>
void SeqList<T>::PrintList() // 遍历线性表
{
for (int i=0;i<length;i++)
cout<<data[i]<<" ";
cout<<endl;
}
第一题测试：
#include <iostream>
#include "SeqList.h"
using namespace std;
void menu()
{
cout<<" 欢迎，欢迎!"<<endl;
cout<<" 1.插入查询"<<endl;
cout<<" 2.删除函数"<<endl;
cout<<" 3.求表长"<<endl;
cout<<" 4.按值查找"<<endl;
cout<<" 5.按位查找"<<endl;
cout<<" 6.遍历线性表"<<endl;
cout<<" 7.退出"<<endl;
cout<<" "<<endl;
cout<<" 请选择编号:"<<endl;
}
int main()
{
int i,j,x;
int a[7]={12,15,24,56,67,68,86};
SeqList<int> s1(a,7);
int flag=1;
while(flag)
{
menu();
cin>>j;
switch(j)
{
case 1:
{
try

{
cout<<"显示要插入的位序及数值："<<endl;
cin>>i>>x;
cout<<endl;
s1.Insert(i,x);
s1.PrintList();
}
catch (char *s){cout<<s<<endl;}
};
break;
case 2:
{
try
{
cout<<"输入元素所在位置";
cin>>i;
x=s1.Delete(i);
cout<<"已删除:"<<x<<endl;
cout<<"删除数据后表变为:"<<endl;
s1.PrintList();
}
catch (char *s){cout<<s<<endl;}
};
break;
case 3:
{
try
{
s1.Length();
cout<<"线性表长度为:"<<s1.Length()<<endl;
}
catch(char *s){cout<<s<<endl;}
};
break;
case 4:
{
try
{
cout<<"输入查找数据x:"<<endl;
cin>>x;
s1.Locate(x);
cout<<"所查数据在第"<<s1.Locate(x)<<"位"<<endl;
}
catch(char *s){cout<<s<<endl;}

};
break;
case 5:
{
try
{
cout<<"查找位置i=";
cin>>i;
s1.Get(i);
cout<<"该位置元素为："<<s1.Get(i)<<endl;
}
catch(char *s){cout<<s<<endl;}
};
break;
case 6:
{
try
{
s1.PrintList();
}
catch(char *s){cout<<s<<endl;}
};
break;
case 7:
flag=0;
break;
default:cout<<"错误!!!"<<endl;
break;
}
}
return 0;
}
第二题代码：
#include <iostream>
#include "SeqList.h"
using namespace std;
void MergeList(SeqList<int> A,SeqList<int> B, SeqList<int> &C)
{

int i=1,j=1,k=0;
int n3=A.Length()+B.Length();
int c[MaxSize];
while (i <= A.Length() && j<= B.Length())
{
if(A.Get(i) <= B.Get(j))
c[k++] = A.Get(i++);
else
c[k++] = B.Get(j++); }
while(i <= A.Length()) //表示B链表已经全部归入C中去了，而A还有剩余
c[k++] = A.Get(i++); //将A链表剩下的值，逐一归入链表C
while(j <= B.Length()) //表示A链表已经全部归入C中去了，而B还有剩余，
c[k++] = B.Get(j++); //将B链表剩下的值，逐一归入链表C
SeqList<int> LC(c,n3);
C=LC;
}
//测试 MergeList
void main()
{
int n1,n2;
cout<<"请输入链表A的长度："<<endl;
cin>>n1;
int a[MaxSize];
cout<<"请输入链表A的各个元素："<<endl;
for(int i=0;i<n1;i++)
cin>>a[i];
cout<<"请输入链表B的长度："<<endl;
cin>>n2;
int b[MaxSize];
cout<<"请输入链表B的各个元素："<<endl;
for(i=0;i<n2;i++)
cin>>b[i];
SeqList<int> La(a,n1);
SeqList<int> Lb(b,n2);
SeqList<int> Lc;
MergeList(La,Lb,Lc);
Lc.PrintList();
}