信管117223王健数据结构实验三之静态链表
《数据结构》实验三：
线性表综合实验
一．实验目的
巩固线性表的数据结构的存储方法和相关操作，学会针对具体应用，使用线性表的相关知识来解决具体问题。
二．实验时间
准备时间为第 7 周到第 8 周，具体集中实验时间为第 4 周第 2 次课。
2个学时。
三．实验内容
1.建立一个由 n 个学生成绩的顺序表，n 的大小由自己确定，每一个学生的成绩信息由自己确定，实现数据的对表进行插入、删除、查找等操作。分别输出结果。
要求如下：
（4）用静态链表实现。
#include<iostream>
using namespace std;
const int MaxSize=100;
template<class DataType>
struct SNode
{
DataType data; //不确定的数据类型
int next; //指针域
};
template<class DataType>
class SLinkList
{
public:
SLinkList();
SLinkList(DataType a[],int n);
~SLinkList(){};
void Insert(int i,int x);
int Locate(DataType x);
DataType Delete(int i);
void PrintList();
private:
SNode<DataType>data[MaxSize];
int frist,avail;
};
template<class DataType>
SLinkList<DataType>::SLinkList()
{
frist=0;
avail=0;
data[0].next=-1;
for(int i;i<MaxSize-1;i++)
{
data[i].next=i+1;
}
data[MaxSize-1].next=-1;
}
template<class DataType>
SLinkList<DataType>::SLinkList(DataType a[],int n)
{
int s;
if(n>=MaxSize||n<=0) throw"位置";
frist=0;
data[0].next=avail=1;
for(int i=0;i<MaxSize-1;i++)
{
data[i].next=i+1;
}
data[MaxSize-1].next=-1;
for(int j=0;j<n;j++)
{
s=avail;
data[s].data=a[j];
avail=data[avail].next;
}
data[s].next=-1;
}
template<class DataType>
void SLinkList<DataType>::Insert(int i,int x)
{
int s;
s=avail; //利用空闲链的第一个结点
avail=data[avail].next; //空闲链的头指针后移
data[s].data=x; //将x填入下标为s的结点
for(int p=0;p<MaxSize-1;p++)
{
if(p==i)
{
data[s].next=data[p].next; //将下标为s的结点插入到下标为p的结点后面
data[p].next=s;
}
}
}
template<class DataType>
DataType SLinkList<DataType>::Delete(int i)
{
if(i>0 && i<MaxSize)
{
int q;
i=i-1;
q=data[i].next; //暂存被删结点的下标
data[i].next=data[q].next; //摘链
data[q].next=avail; //将结点q插在空闲链avail的最前端
avail=q; //空闲链头指针avail指向结点q
return data[q].data;
}
else throw"位置";
}
template<class DataType>
int SLinkList<DataType>::Locate(DataType x)
{
int count;
count=data[frist].next;
for(count;count!=-1;count++)
{if(data[count].data==x)
{
return count;
}
}
return 0;
}
template<class DataType>
void SLinkList<DataType>::PrintList()
{
int p;
p=data[frist].next;
while(p!=-1)
{
cout<<data[p].data<<" ";
p=data[p].next;
}
cout<<endl;
}
int main()
{
int r[5]={100,90,80,70,60};
SLinkList<int>L(r,5);
cout<<"执行插入成绩操作前数据为："<<endl;
L.PrintList();
try
{
L.Insert(2,55);
}
catch(char*s)
{
cout<<s<<endl;;
}
cout<<"执行插入成绩操作后数据为："<<endl;
L.PrintList();
cout<<"值为90的元素位置为：";
cout<<L.Locate(90)<<endl;
cout<<"执行删除第一个学生成绩操作前数据为："<<endl;
L.PrintList();
try
{
L.Delete(1);
}
catch(char*s)
{
cout<<s<<endl;
}
cout<<"执行删除成绩操作后数据为："<<endl;
L.PrintList();
return 0;
}
运行结果：