将两个递增链表合并为一个递减链表

//将两个递增链表合并为一个递减链表

#include<iostream>

using namespace std;

typedef int elem;

//建立链表空间 

typedef struct list

{

 elem data;

 struct list *next;

}node,*link;

//初始化链表

/*

1.生成新节点作为头节点，用头指针L指向头节点

2.头指针指针域置空*/ 

void initialize(link &L)

{

 L=new node;

 L->next=NULL;

 }

//前插法建立单链表

/*1.创建一个只有头节点的空链表

2.根据待创建链表包括的元素个数n，循环n次执行以下操作：

生成一个新节点*p 

输入元素值赋给新节点*p的数据域 

将新节点*p插入到头节点之后*/

void createlist_head(link &L)

{

 int n,e;

 node *p=NULL;

 initialize(L);

 cout<<"How many elements do you want to build in the list?"<<endl;

 cin>>n;

 L->data=n;

 cout<<"please input elements you want to iput:"<<endl;

 for(int i=0;i<n;i++)

 {

  p=new node;//*****

  if(p==NULL)

  {

   cout<<"no memory give you!"<<endl;

   exit(0);

  }

  cin>>e;

  p->data=e;//*****

   p->next=L->next;//*****

   L->next=p;//******

 }

  

 }

//用冒泡排序法对已经建立好的链表进行排序

/**/

void sort_Bubble(link &L)

{

 int flag=0,end=L->data,tem;

 

 while(end!=1)

 {

  node *p=NULL,*q=NULL;

  p=L->next;

  while(p)

  { 

   q=p;

   p=p->next;

   if(p)

   if(q->data>p->data)

   {

    tem=p->data;

    p->data=q->data;

    q->data=tem;

    flag=1;//只要有交换就变为1，否则，说明本来就是升序的。 

   }

  }

  if(flag==0)

   break; 

  end--;

 }

 

 

 

 } 

void show(link &L)

{

 node *p=L;

 cout<<"L("<<p->data<<"): ";

 p=p->next; 

 while(p)

 {

  cout<<p->data<<" ";

  p=p->next;

 }

 cout<<endl;

}

//合并两个增序链表，仍然用原来的空间，利用前插法 

void mergelist(link &L1,link &L2,link &L3)//L1,L2作为分链表，L3为合成链表 

{

 node *p1=L1->next,*p2=L2->next,*q=NULL;//p1,p2,p3分别用于访问L1,L2,L3 

 L3=L1;//利用L1的头节点作为L3的头结点 

 L3->data=L1->data+L2->data; 

 L3->next=NULL;

 while(p1||p2)

 {

  if(!p1)

  {

   q=p2;

   p2=p2->next;

   

  }

  

  else if(!p2)

  {

   q=p1;

   p1=p1->next; 

  }

  else if(p1->data<=p2->data)

  {

   q=p1;

   p1=p1->next; 

  }

  else//p1,p2都！=NULL且p1->data>p2->data 

  {

   q=p2;

   p2=p2->next;

  }

  

  q->next=L3->next;

  L3->next=q;

 }

 delete L2;

 

 }

int main()

{

 link L1,L2,L3;

 cout<<"make the first linked list"<<endl;

 createlist_head(L1);

 show(L1);

 sort_Bubble(L1);

 show(L1);

 cout<<"make the second linked list"<<endl;

 createlist_head(L2);

 show(L2);

 sort_Bubble(L2);

 show(L2);

 mergelist(L1,L2,L3);

 show(L3);

 } 

最后

以上就是快乐美女为你收集整理的将两个递增链表合并为一个递减链表的全部内容，希望文章能够帮你解决将两个递增链表合并为一个递减链表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。