可插入的（有序的）双链表的实现
描述
定义有序的双链表类,链表中存储整型数据，创建带头结点的有序双链表，要求包含以下成员函数：
双链表的构造函数（非空的链表，输入数据为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 <iostream>
#include<algorithm>
using namespace std;
struct node
{
int data;
node* prior, * next;
};
class doublelist
{
public:
doublelist(int a[], int n);//构造函数
void inset(int n); //插入
void dataDelete(int n); //删除
void printflist(); //历遍链表并输出
~doublelist(); //析构函数
private:
node* first;
int h;
};
doublelist::doublelist(int a[], int n)
{
h = n;
node* p1;
first = new node;
first->next = nullptr;
first->prior = nullptr;
p1 = first;
for (int i = 0; i <n; i++)
{
node* s = nullptr;
s = new node;
s->data = a[i];
s->prior = p1;
s->next = nullptr;
p1->next = s;
p1 = s;
}
p1->next = nullptr;
}
void doublelist::inset(int n)//插入
{
node* p,* q;
int flag = 0;
q = first;
p = first->next;
while (p != NULL)
{
if (n <= p->data)
{
node* s = new node;
s->data = n;
s->next = p;
s->prior = p->prior;
p->prior->next = s;
p->prior = s;
h++;
flag = 1;
break;
}
q = q->next;
p = p->next;
}
if (flag == 0)
{
node* s = new node;
s->next = q->next;
s->data = n;
s->prior = q;
q->next = s;
h++;
}
/*if (p->data > n) //以下为第二种插入方法（循环条件与第一种相同）
{
node* s = new node;
s->prior = first;
s->data = n;
s->next = p;
p->prior = s;
first->next = s;
h++;
}
else {
if (h == 1)
{
node* s = new node;
s->prior = p;
s->data = n;
s->next = p->next;
p->next = s;
h++;
}
else
{
while (p->data < n )
{
p = p->next;
if (p->next == nullptr)
{
break;
}
}
if (p->next == nullptr)
{
node* s = new node;
s->next = p->next;
s->data = n;
s->prior = p;
p->next= s;
}
else {
node* s = new node;
s->next = p;
s->data = n;
s->prior = p->prior;
p->prior->next = s;
p->prior = s;
}
}
}
*/
}
void doublelist::dataDelete(int n)
{
int h1 = h;
node* p = first->next;
node* q;
while (p != nullptr)
{
if (p->data == n)
{
q = p;
p->prior->next = p->next;
if (p->next != NULL)
p->next->prior = p->prior;
delete q;
h--;
}
p = p->next;
}
/*else { cout<<"滚，SB！"<<endl;}*/
}
void doublelist::printflist()
{
node* p = first->next;
while (p!= nullptr)
{
cout << p->data << " ";
p = p->next;
}
cout <<endl;
}
doublelist::~doublelist()
{
node* p = first;
while (p != nullptr)
{
first = first->next;
delete p;
p = first;
}
}
int main()
{
int a[10000], n = 0;
int x,c, sc;
while (cin >> a[n]&&a[n]!=0)
{
n++;
}
sort(a, a + n); //实现有序
doublelist list1(a, n);
list1.printflist();
while (cin >> c && c != 0)
{
list1.inset(c);
}
list1.printflist();
while (cin >> sc && sc != 0)
{
list1.dataDelete(sc);
}
list1.printflist();
}
