using namespace std;
struct DouLinkList{
DouLinkList* pre;
int data;
DouLinkList* next;
};
DouLinkList* createLinkList(){//创建一个带头结点的双向链表，头结点数据域记录链表长度
DouLinkList* L=new DouLinkList();
L->data=0;
L->next=NULL;
L->pre=NULL;
return L;
}
void insertNode(DouLinkList* L,int elem){//插入时保持链表有序
DouLinkList* cur=L->next;
DouLinkList* pre1=L;
if(L->data==0){//只有头结点
DouLinkList* p=new DouLinkList();
p->data=elem;
L->next=p;
p->pre=L;
p->next=NULL;
L->data+=1;
}
else{
while(cur!=NULL&&cur->data<elem){//寻找插入结点
pre1=cur;
cur=cur->next;
}
if(!cur){//链表尾节点后插入
DouLinkList* p=new DouLinkList();
p->data=elem;
pre1->next=p;
p->pre=pre1;
p->next=NULL;
L->data+=1;
}
else{//l链表中间插入
DouLinkList* p=new DouLinkList();
p->data=elem;
pre1->next=p;
p->pre=pre1;
p->next=cur;
cur->pre=p;
L->data+=1;
}
}
}
DouLinkList* checkNode(DouLinkList* L,int elem){//返回指向元素的指针，如果链表中没有该元素则返回空指针
DouLinkList* cur=L->next;
while((elem!=cur->data)&&!cur) cur=cur->next;
return cur;
}
void deleteNode(DouLinkList* L,int elem){
DouLinkList* cur=checkNode(L,elem);
if(cur){//如果元素存在。删除结点，链表长度减1
if(!cur->next) {//钙元素为链表为元素
delete cur;
L->data-=1;
}
else{//不是链表尾元素
cur->pre->next=cur->next;
cur->next->pre=cur->pre->next;
delete cur;
L->data-=1;
}
}
}
void output(DouLinkList* L){
DouLinkList* cur=L->next;
if(L->data==0){
cout<<“链表长度为0″<<endl;
}
else{
cout<<“链表长度为：”<<L->data<<endl;
cout<<“链表元素为：”;
while(cur){
cout<<cur->data<<” “;
cur=cur->next;
}
cout<<endl;
}
}
DouLinkList* mergeTwoLinkList(DouLinkList* L1,DouLinkList* L2){//合并两个链表成为有序链表
DouLinkList* L3=new DouLinkList();
DouLinkList* L4=L3;
L3->data=L1->data+L2->data;
L1=L1->next;
L2=L2->next;
while(L1&&L2){
if(L1->data<L2->data){
L3->next=L1;
L1->pre=L3;
L1=L1->next;
L3=L3->next;
}
else{
L3->next=L2;
L2->pre=L3;
L2=L2->next;
L3=L3->next;
}
}
while(L1){
L3->next=L1;
L1->pre=L3;
L1=L1->next;
L3=L3->next;
}
while(L2){
L3->next=L2;
L2->pre=L3;
L2=L2->next;
L3=L3->next;
}
return L4;
}
int main(){
DouLinkList* L=createLinkList();
DouLinkList* L1=createLinkList();
insertNode(L,1);
insertNode(L,3);
insertNode(L,2);
insertNode(L1,4);
insertNode(L1,5);
output( mergeTwoLinkList(L,L1));
return 0;
}