#include<iostream>
using namespace std;
template <class student>
class Node
{
public:
student data;
Node<student> *prior;
Node<student> *next;
};
template <class student>
class DLL
{
public:
DLL(); //无参的构造函数
DLL(student score[], int n); //带参的构造函数
~DLL(); //析构函数
int Length(); //返回单链表长度
void insert(int i, student x); //插入操作，在位置i插入元素
student get(int i); //按位查找
int locate(student x); //按值查找
student Delete(int i); //删除操作
void print(); //遍历操作
private:
Node<student> *first; //双链表的头指针
int length; //链的长度计数
};
template <class student>
DLL<student>::DLL(student score[], int n)
{
length=0;
first=new Node<student>;
first->next=NULL;
first->prior=NULL;
for (int i=0;i<n;i++)
{
Node<student> *s=new Node<student>;
s->data=score[i];
s->next=first->next;
first->next = s;
}
}
template <class student>
DLL<student>::~DLL()
{
while (first->next!=first->prior)
{
//临时指针，存储即将释放的节点的指针
Node<student> *temp=first;
//脱链
first->prior->next=first->next;
first->next ->prior=first->prior;
//头指针后移
first=first->next;
//释放内存
delete temp;
}
delete first;
}
template<class student>
int DLL<student>::Length()
{
Node<student> *p;
int count;
p=first->next;
count=0;
while(p!=NULL)
{
p=p->next;
count++;
}
return length;
}
template <class student>
void DLL<student>::insert(int i,student x)
{
Node<student>*p,*s;
int count;
p=first;
count=0;
while(p!=NULL&&count<i-1)
{
p=p->next;
count++;
}
if(p==NULL) throw"位置";
else
{
s=new Node<student>;
s->data=x;
s->next=p->next;
p->next=s;
}
}
template <class student>
student DLL<student>::get(int i)
{
Node<student> *p;int count;
count=1;
p=first->next;
while (p!=NULL&&count<i)
{
p = p->next;
count++;
}
if (p == NULL)throw"位置非法";
else return p->data;
}
template <class student>
int DLL<student>::locate(student x)
{
Node<student> *p;
int count;
p=first->next;
count=1;
while(p!=NULL)
{
if(p->data==x) return count;
p=p->next;
count++;
}
return 0;
}
template <class student>
student DLL<student>::Delete(int i)
{
Node<student> *p,*q;
p=first->next;
int count, x;
count=1;
while (p!=NULL&&count<i-1)
{
p=p->next;
count++;
}
if (p==NULL||p->next==NULL) throw"位置非法";
else
{
q=p->next;
x=q->data;
if (p->next!=NULL)
{
if(q->next!=NULL)
q->next->prior=p;
else
{
p->next=NULL;
p->next=q->next;
delete q;
q=NULL;
return x;
}
}
p->next=q->next;
delete q;
q=NULL;
return x;
}
}
template <class student>
void DLL<student>::print()
{
Node<student> *p;
p=first->next;
while(p->next!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<p->data<<endl;
}
int main()
{
float score[8] = {72,88,57,83.5,32.5,68,96,86.5};
DLL<float>Student(score, 8);
cout<<"初始成绩如下："<<endl;
Student.print();
cout<<endl<<"在学生3插入成绩86，插入后结果如下："<<endl;
Student.insert(3,86);
Student.print();
cout<<endl<<"在学生5删除成绩为："<<Student.Delete(5)<<" , "<<"删除后结果如下:"<<endl;
Student.print();
cout<<endl<<"位置6的成绩为："<<Student.get(6)<<endl;
cout<<endl<<"成绩72所在位置为："<<Student.locate(72)<<endl<<endl;
cout<<"最终数据如下："<<endl;
Student.print();
cout<<endl;
return 0;
}
