描述
定义有序的双链表类,链表中存储整型数据，创建带头结点的有序双链表，要求包含以下成员函数：
双链表的构造函数（非空的链表，输入数据为0,表示输入结束）
插入操作（将一个数据元素插入到有序的双链表中，插入之后链表仍然有序，输入数据为0表示插入操作结束）
按值删除节点（考虑有重复值的情况）
双链表的遍历操作
双链表的析构
输入
输入链表中的元素，根据输入元素，创建有序双链表（非空的链表，输入数据为0,表示输入结束） 输入要插入的值(可以插入多个值，0表示输入结束，) 输入要删除的值（可以删除多个值，0表示结束，）
输出
输出创建的结果 输出插入的结果 输出删除之后的结果
样例输入
1 6 3 7 5 9 0 8 0 2 0样例输出
1 3 5 6 7 9 1 3 5 6 7 8 9 1 3 5 6 7 8 9 #include<bits/stdc++.h> using namespace std; struct Node { int data; Node *llink,*rlink; }; class Doublelink { private: Node *head; public: Doublelink(); ~Doublelink(); Doublelink(int a[],int n); void Printlink(); void Insert(int x); void Delete(int x); }; Doublelink::Doublelink() { head=new Node; head->llink=NULL; head->rlink=NULL; } Doublelink::~Doublelink() { Node *p=head; while(p!=NULL) { head=head->rlink; delete p; p=head; } } Doublelink::Doublelink(int a[],int n) { head=new Node; Node *p=head,*s=NULL; for(int i=0;i<n;i++) { s=new Node; s->data=a[i]; s->llink=p; p->rlink=s; p=s; } p->rlink=NULL; } void Doublelink::Printlink() { Node *p=head->rlink; while(p!=NULL) { cout<<p->data<<" "; p=p->rlink; } cout<<endl; } void Doublelink::Insert(int x) { Node *p,*s; p=head->rlink; int flag=1; while(p!=NULL) { if(x<=p->data) { s=new Node; s->data=x; s->rlink=p; s->llink=p->llink; p->llink->rlink=s; p->llink=s; flag=0; break; } p=p->rlink; } if(flag) { Node *p,*s; p=head; while(p->rlink) { p=p->rlink; } s=new Node; s->data=x; s->rlink=p->rlink; p->rlink=s; s->llink=p; } } void Doublelink::Delete(int x) { Node *p,*q; p=head->rlink; while(p!=NULL) { if(p->data==x) { q=p; p->llink->rlink=p->rlink; if(p->rlink!=NULL) p->rlink->llink=p->llink; delete q; } p=p->rlink; } } int a[10000]; int main() { int x; int n=0; while(cin>>x&&x!=0) { a[n++]=x; } sort(a,a+n); Doublelink d(a,n); d.Printlink(); int a; while(cin>>a&&a!=0) { d.Insert(a); } d.Printlink(); int b; while(cin>>b&&b!=0) { d.Delete(b); } d.Printlink(); }
