建立双向链表

#include using namespace std; template struct Node {

T data;

struct Node * prior; struct Node * next; };

static int length=0; template class D_linklist { private:

Node * p;

public:

D_linklist(T a[],int n); //有参构造，用有n个元素的数组初始化链表

void Reposition(); //析构

int Getlength(); //获取链表长度

Node * Get(int i); //查找第i个元素

void Inset(); //插入值为x的元素

T Delete(); //删除第i个元素

void Printlist(); //打印链表 };

template

D_linklist::D_linklist(T a[],int//头插构造 {

p=new Node ; p->next=NULL; p->prior=p; p->data=a[0];

for(int i=1;i{ Node *s=new Node ; s->data=a[i];

n)

s->next=p; p->prior=s; p=s;

length ++; }

p->prior=NULL; }

template

void D_linklist::Reposition() //析构 {

for(int i=0;i*b=p;

Node *s=new Node; if(b->data>b->next->data) {

s->data=b->data;

b->data=b->next->data; b->next->data=s->data; }

b=b->next; delete s; } }

template

void D_linklist::Inset() //插入函数 {

T x;

cout<<\"请输入要插入的元素\"<>x;

Node *s=new Node; Node *q=p; s->data=x; int i=0;

while(s->data>q->data) //判断插入点位置 q=q->next;

s->prior=q; //连接节点

s->next=q->next; q->next->prior=s; q->next=s; length++; }

template //获取第i个元素的地址

Node * D_linklist::Get(int{

Node *q=p;

for(int a=0;anext; return q; }

template

T D_linklist::Delete() //删除操作 {

cout<<\"请输入要删除的元素序号

i)

\"<>i;

Node * q=Get(i); T a=q->data;

q->prior->next=q->next; q->next->prior=q->prior; delete q; length--; return a; }

template //获得表长

int D_linklist::Getlength() {

return length; }

template //打印链表

void D_linklist::Printlist() { Node *q=p;

while(q->next!=NULL) {cout<data<<\" \"; q=q->next; };

cout<data; }

void main()

{ int a[9]={0,1,2,3,5,6,7,9,8}; D_linklist s(a,9); s.Printlist(); s.Reposition(); cout<s.Printlist(); s.Delete();

s.Printlist(); s.Getlength(); }