两个有序链表序列的合并

ゞ浴缸里的玫瑰 2022-03-01 16:36 240阅读 0赞

## PTA 01：两个有序链表序列的合并 ##

#### 一、题目 ####

本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。

函数接口定义：

List Merge( List L1, List L2 );

其中List结构定义如下：

typedef struct Node *PtrToNode;
    struct Node {
        
        ElementType Data; /* 存储结点数据 */
        PtrToNode   Next; /* 指向下一个结点的指针 */
    };
    typedef PtrToNode List; /* 定义单链表类型 */

<table> 
 <tbody> 
  <tr> 
   <td><font>L1和L2是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Merge要将L1和L2合并为一个非递减的整数序列。应直接使用原序列中的结点，返回归并后的带头结点的链表头指针。</font></td> 
  </tr> 
 </tbody> 
</table>

裁判测试程序样例：

#include <stdio.h>
        #include <stdlib.h>
        
        typedef int ElementType;
        typedef struct Node *PtrToNode;
        struct Node {
        
            ElementType Data;
            PtrToNode   Next;
        };
        typedef PtrToNode List;
        
        List Read(); /* 细节在此不表 */
        void Print( List L ); /* 细节在此不表；空链表将输出NULL */
        
        List Merge( List L1, List L2 );
        
        int main()
        {
        
            List L1, L2, L;
            L1 = Read();
            L2 = Read();
            L = Merge(L1, L2);
            Print(L);
            Print(L1);
            Print(L2);
            return 0;
        }
        
        /* 你的代码将被嵌在这里 */

输入样例：

3
        1 3 5
        5
        2 4 6 8 10

输出样例：

1 2 3 4 5 6 8 10 
        NULL
        NULL

--------------------

#### 二、代码 ####

#include <stdio.h>
    #include <stdlib.h>
    
    typedef int ElementType;
    typedef struct Node *PtrToNode;
    struct Node {
        
        ElementType Data;
        PtrToNode   Next;
    };
    typedef PtrToNode List;
    
    /* 你的代码将被嵌在这里 */
    List Read(){
        
    //	此函数的作用：创建链表并插入数据
    
    	int n;
    	scanf("%d",&n);
    //	输入该链表中元素的个数
     
        List L=(List)malloc(sizeof(PtrToNode));
    //    申请一个头节点
    
        L->Next=NULL;
    //    先建立一个以L为头结点的空链表 
        if(n!=0){
        
        	List r=L;
    //    尾指针指向头结点 
    
    	for(int i=0;i<n;i++){
        
    		List p=(List)malloc(sizeof(struct Node));
    		scanf("%d",&(p->Data));
    		p->Next=NULL;
    		r->Next=p;
    		r=p;	
    }  
    r->Next=NULL;
    	}
    return L;
    };
    
    void Print(List L){
        
    //	此函数的作用：打印链表中的元素 
        List P=L->Next;
     if(P!=NULL)
       {
        
           List r;
           r = L;
           while(r->Next)
           {
        
               r = r->Next;
               printf("%d ",r->Data);
           }
       }
       else
       {
        
            printf("NULL");
       }
       printf("\n");
    }; 
    
    List Merge( List L1, List L2){
        
    //	此函数的作用：实现将两链表融合
        List p1,p2,p,L;
        L = (List)malloc(sizeof(struct Node));
        p1=L1->Next;
        p2=L2->Next;
    //  p1 p2指针分别指向两个表的第一个结点
        p=L;
    //  p指向L的头结点
        while(p1!=NULL&&p2!=NULL){
        
        	if(p1->Data<=p2->Data){
        
        	p->Next=p1;
        	p=p1;
        	p1=p1->Next;
    	}
    	else{
        
    		p->Next=p2;
    		p=p2;
    		p2=p2->Next;
    	}
    //  当L1 L2 均未到达表尾 依次摘取两表中值较小的结点插入到L最后
    	}
        
         p->Next=p1?p1:p2;
         L1->Next=NULL;
         L2->Next=NULL;
         return L;
    }; 
    
    int main()
    {
        
        List L1, L2, L;
        L1 = Read();
        L2 = Read();
        L = Merge(L1, L2);
        Print(L);
        Print(L1);
        Print(L2);
        return 0;
    }

--------------------

#### 三、经验总结 ####

刚开始经历过几次失败，其中一次这里写的是List L ；L=new LNode（按书上打的）但是跑一下 马上就报错了。程序在我输入完之后就崩溃了，说明read这边没毛病，到print这一步就出错了。

我然后把L=new LNode这句删了（其实好蠢啊我）可是到read这一步程序就崩了 分析原因应该是我没有给我的指针在内存中分配一个首地址。

现在问题来了，这种情况该如何建立一个带头结点的空链表呢？  
由于不知道到底这段地址有多长，可以存什么变量，所以它的类型是空的，  
我们可以利用

<table> 
 <tbody> 
  <tr> 
   <td><font>L = (List)malloc(sizeof(struct Node));</font></td> 
  </tr> 
 </tbody> 
</table>

作强制类型转换，使其变成确定长度，固定存放一种数据类型的地址。

所以我们要做的是：获取PtrToNode的字段长度，然后强转为List类型。  
L变量就代表地址长度和PtrToNode一样所占内存空间同样大小的List。注意用malloc函数之前一定记得包含头文件 \#include <stdlib.h>哦!

可是当我兴高采烈地拿着dev上已经通过的程序放到PTA上面跑，却发现系统提示编译错误。这让人很费解。后来发现是惯性思维作怪，我们每次把代码一粘上去就完事了，但是这一题只要求我们提交merge部分。