合并两个有序表

浅浅的花香味﹌ 2022-06-01 11:48 240阅读 0赞

***题目***：两串数字有序，分别用顺序表和链表的方式，将两串数字合并。

一、顺序表

思路：

如有有序表A,B：   A：1 2 4 5 5    B：2 3 3 6 7

1.一开始 i 指向 A的开头元素（即1），同理 j 指向 B开头元素（2）

2.A\[i\] 和 B\[j\] 中对比，选较小的放入新表C中

#include<stdio.h>
    #include<stdlib.h>
    #define LIST_INIT_SIZE 30
    
    struct Sqlist 
    {
    	int *elem;
    	int length;
    	int listsize;
    };
    
    void InitSqlist(struct Sqlist *L)
    {
    	L->elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));
    	if(!L->elem) exit(1);
    	L->length=0;
    	L->listsize=LIST_INIT_SIZE;
    }
    
    void read(struct Sqlist *L)
    { 
    	int n=0,i=0;
    	int *newbase;
    	printf("输入顺序表含元素个数");
    	scanf("%d",&n);
    	if(n>L->listsize)
    	{
    		newbase=(int *)realloc(L->elem,(n)*sizeof(int));
    		L->elem=newbase;
    		L->listsize=n; 
    	}
    	printf("\n");
    	printf("输入元素"); 
    	while(i<n)
    	{
    		scanf("%d",&L->elem[i++]);
    		L->length=i;
    	}
    }
    
    void pri(struct Sqlist *L)
    {
    	int i=0;
    	for(i=0;i<L->length;i++)
    	{
    		printf(" %d",L->elem[i]);
    	}
    }
    
    void main()
    {
    	int n,s; 
    	int i=0,j=0,k=0;
    	struct Sqlist L,Q,S;
    	void InitSqlist(struct Sqlist *L);
    	void read(struct Sqlist *L);
    	void pri(struct Sqlist *L);
    	InitSqlist(&L);
    	read(&L);
    	pri(&L);
    	printf("\n");
    	InitSqlist(&Q);
    	read(&Q);
    	pri(&Q);
    	printf("\n");
    	InitSqlist(&S);
    	
    	while(i<L.length&&j<Q.length)//s有超出空间的可能，可以通过初始化加以改变 
    	{
    		if(L.elem[i]<Q.elem[j])
    		{
    			S.elem[k]=L.elem[i];
    			k++;i++;
    		}
    		else
    		{
    			S.elem[k]=Q.elem[j];
    			k++;j++;
    		}	
    	}
    	while(i<L.length)
    	{
    		S.elem[k]=L.elem[i++];
    		k++;
    	}
    	while(j<Q.length)
    	{
    		S.elem[k]=Q.elem[j++];
    		k++;
    	}
    	
    	S.length=k; 
    	pri(&S); 
    }

二、链表

![SouthEast][]

图片来源：[点击打开链接][Link 1]

#include<stdio.h>
    #include<stdlib.h>
    typedef struct Node
    {
    	int elem;
    	struct Node *next;
    }node;
    
    node *write()
    {
    	int i,n;
    	node *head,*p; 
    	printf("输入链表长度：");
    	scanf("%d",&n);
    	printf("输入元素：");
    	head=(node *)malloc(sizeof(node));
    	 
    	/*p=(node *)malloc(sizeof(node));//这样写每次建立链表后，都会多出 
    	head->next=p;                   //一个空间，对循环的判断也有影响 
    	p->next=NULL;
    	for(i=0;i<n;i++)
    	{
    		scanf("%d",&p->elem);
    		p->next=(node *)malloc(sizeof(node));
    		p=p->next;
    		p->next=NULL;
    	}*/
    	
    	/*p=(node *)malloc(sizeof(node)); 
    	head->next=p;                   
    	for(i=0;i<n;i++)
    	{
    		scanf("%d",&p->elem);
    		if(i<=n-2)//最后一个不需要再次开辟空间，但是每次都需要判断 
    		{         //能否在保证与头链表连接的同时，不需要每次判断 ,当然能
    			p->next=(node *)malloc(sizeof(node));
    			p=p->next;
    		}	
    	}
    	p->next=NULL;//这步很重要 */
    
    p=(node *)malloc(sizeof(node)); 
    head->next=p;                   
    for(i=1;i<n;i++)//注意i是从1开始的，这样可以减少一次循环，从而减少一次空间的建立，但也少输入一个数，
    {                 //要事后补救
    	scanf("%d",&p->elem);
    	p->next=(node *)malloc(sizeof(node));
    	p=p->next;  
    }
    scanf("%d",&p->elem);
    p->next=NULL;
     return head;
    
    }
    
      node *mergelist(node *la,node *lb)
    
    {
        node *lc;
        node *pa,*pb,*pc;
        lc=la;
        pa=la->next;pb=lb->next;
        pc=lc;
        while(pa&&pb)
        { 
            if(pa->elem<pb->elem)
            {
                pc->next=pa;
                pc=pc->next;
                pa=pa->next;
            }
            else
            {
                pc->next=pb;
                pc=pc->next;
                pb=pb->next;
            }
        }
        pc->next=pa?pa:pb; 
        return lc; 
    }
    
     
    
    void main()
    {
        node *la,*lb,*lc,*pc;
        node *write();
        node *mergelist(node *la,node *lb);
        la=write();
        lb=write();
        lc=mergelist(la,lb);
        pc=lc->next;
        while(pc)
        {
            printf("%d ",pc->elem);
            pc=pc->next;
        }
    }

[SouthEast]: /images/20220601/4bcda35efbab41c1ab51f87f9140f501.png
[Link 1]: http://blog.csdn.net/fangfang_666/article/details/75094244