c语言数据结构算法之将两个有序递增链表合并成一个有序递增链表,要求结果仍使用原来两个链表的存储空间,不另外占有空间。

完整程序:

/*将两个有序递增链表合并成一个有序递增链表,要求结果仍使用原来两个链表的存储空间,不另外占有空间。*/
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20;
typedef struct LNode{
    int data;
    struct LNode *next;
} LNode,*LinkList;
LinkList mergelinklist(LinkList La,LinkList Lb){
//已知链表La,Lb的元素按递增排序。
//将两链表合并,仍然使用La的表头,将两个表比较,依次将存储空间连到La上。
//要合并后的链表仍然是递增的,需要尾插法。
    LinkList pa,pb;   //定义两个指针又来存储La,lb从首元结点开始向后的链表
    pa=La->next;     //La链表已经赋值给了pa,这样就可以使用La的头结点,作为新链表的头结点。
    pb=Lb->next;    
    free(Lb);       //Lb从首元结点开始已经赋值给了pb,所以把Lb,的头结点释放。
    LinkList last=La;      //last存储尾结点的地址。
    while(pa&&pb){
        if(pa->data<pb->data)
        {
            LinkList p=pa->next;  //先把pa的下一个结点地址存储下来。
            pa->next=NULL;        //用尾插法将pa当前结点插入La。
            last->next=pa;    
            last=last->next;
            pa=p;                //pa后移一位。
        }
        else if(pa->data==pb->data){  //值相等的情况
            LinkList p=pa->next;      //将pa当前结点插入La.
            pa->next=NULL;     
            last->next=pa;
            last=last->next; 
            pa=p;             //pa后移一位
            LinkList q=pb;
            pb=pb->next;        //释放当前结点,并且后移一位
            free(q);
        }
        else{
            LinkList p=pb->next;  //指向pb后一个结点 
            pb->next=NULL;     //把pb结点的next置空 
            last->next=pb;    //此时pb中的元素比pa中的小,应把pb链接到pa的前面 
            last=last->next;   //把last指针后移,保持last一直指向最后一个结点 
            pb=p;              //pb后移一位,对下一个结点元素进行与pa的比较 
        }
    }
    last->next=pa?pa:pb;   //pa,pb哪一个链表还没完,就将它连接到La后面。
    return La;
}
int main(){
    LinkList La,Lb;
    int n,m,i;
    La=(LinkList)malloc(sizeof(LNode));
    La->next=NULL;
    Lb=(LinkList)malloc(sizeof(LNode));
    Lb->next=NULL;
    LinkList last=La;
    printf("请输入第一个有序递增表的长度:");
    scanf("%d",&n);
    printf("\n");
	printf("请输入第一个有序递增表的元素:"); 
    for(i=0;i<n;i++)
    {
        LinkList p;
        p=(LinkList)malloc(sizeof(LNode));
        scanf("%d",&p->data);
        p->next=NULL;
        last->next=p;
        last=last->next;
    }
    last=Lb;
    printf("\n");
    printf("请输入第二个有序递增表的长度:");
    scanf("%d",&m);
	printf("\n");
	printf("请输入第二个有序递增表的元素:");   
    for(i=0;i<m;i++)
    {
        LinkList p;
        p=(LinkList)malloc(sizeof(LNode));
        scanf("%d",&p->data);
        p->next=NULL;
        last->next=p;
        last=last->next;
    }
    printf("\n");
    La=mergelinklist(La,Lb);
    LinkList p=La;
    p=p->next;
    printf("合并后的有序表为:"); 
    while(p){
        printf("%d   ",p->data);
        p=p->next;
    }
    printf("\n");
    return 0;   
}

解析图:

  c语言数据结构算法之将两个有序递增链表合并成一个有序递增链表,要求结果仍使用原来两个链表的存储空间,不另外占有空间。
上一篇:数据结构实践——单链表:逆置、连接与递增判断


下一篇:循环链表+动态约瑟夫问题