#include<iostream>
#include<string>
using namespace std;
const int Maxsize=10;
template<class student>
class Node
{
public:
student data;
int next; //存储数组下标
};
template <class student>
class SLL
{
public:
SLL();//无参构造函数
SLL(student score[],int n);//带参构造函数
~SLL();//空的析构函数
void print();//遍历操作
student get(int i);//按位查找操作
int Locate(student x);//按值查找操作
void insert(int i,student x);//插入操作
void Delete(int i);//删除操作
private:
Node<student> node[Maxsize];//数据成员结点
int first;//头指针
int avail;//指向空闲链的头指针
int length;//当前静态链表的长度
};
template<class student>
SLL<student>::SLL(student score[],int n)
{
length=0;
for(int i=0;i<Maxsize;i++)
{
node[i].next=i+1;
}
node[Maxsize-1].next=-1;
avail=2;
first=1;
node[first].next=-1;
for(int j=n-1;j>=0;j--)
{
if (avail==-1)
{
break;
}
int s=avail;
avail=node[avail].next;//空闲链的头指针后移
node[s].data=score[j];//将score[j]填入下标为S的节点
node[s].next=node[first].next;//将score[j]插到first后面
node[first].next=s; //将s接入first后面
length++;
}
}
template<class student>
SLL<student>::~SLL()
{}
template<class student>
void SLL<student>::print()
{
int s=node[first].next;
for (int i=1;i<=length;i++)
{
cout<<node[s].data<<" ";
s=node[s].next;
}
}
template<class student>
student SLL<student>::get(int i)
{
if(i<=0||i>length) throw"位置非法";
int p=first;
for(int j=0;j<i;j++)
{
p=node[p].next;
}
return node[p].data;
}
template<class student>
int SLL<student>::Locate(student x)
{
int count=0;
int p=first;
while(node[p].next!=-1)
{
p=node[p].next;
if(node[p].data==x) return count+1;
count++;
}
return -1;
}
template<class student>
void SLL<student>::insert(int i, student x)
{
if(i<0||i>length) throw"位置非法";
int p=first;
for(int j=1;j<i;j++)
{
p=node[p].next;
}
int s=node[avail].next;
node[avail].data=x;
node[avail].next=node[p].next;
node[p].next=avail;
avail=s;
length++;
}
template<class student>
void SLL<student>::Delete(int i)
{
if(i<0||i>length+1) throw"位置非法";
int p = first;
for(int j = 1;j<=i; j++)
{ p=node[p].next; }
int q = node[p].next;
student e = node[p].data;
node[p].next = node[q].next;
node[q].next = avail;
avail = q;
length--;
}
int main()
{
float score[5]={79.5,68,88.5,84.5,99};
SLL<float> Student(score,5);
cout<<"初始数据如下："<<endl;
Student.print();
cout<<endl<<"在学生5插入成绩90.5："<<endl;
Student.insert(5,90.5);
Student.print();
cout<<endl<<"在学生3删除成绩："<<endl;
Student.Delete(2);
Student.print();
cout<<endl<<"学生5的成绩为："<<Student.get(5)<<endl;
cout<<endl<<"成绩99所在学生为："<<Student.Locate(99)<<endl<<endl;
cout<<"最终数据如下："<<endl;
Student.print();
cout<<endl;
return 0;
}
