1-3 递增的整数序列链表的插入 (20 分)

本题要求实现一个函数，在递增的整数序列链表（带头结点）中插入一个新整数，并保持该序列的有序性。

函数接口定义：

List Insert( List L, ElementType X );

其中List结构定义如下：

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

L是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Insert要将X插入L，并保持该序列的有序性，返回插入后的链表头指针。

裁判测试程序样例：

#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 ); /* 细节在此不表 */

List Insert( List L, ElementType X );

int main()
{
    List L;
    ElementType X;
    L = Read();
    scanf("%d", &X);
    L = Insert(L, X);
    Print(L);
    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

5
1 2 4 5 6
3

输出样例：

1 2 3 4 5 6

ps更新2019年8月30日08:41:07

过了，找到问题和第一题一样，申请内存有问题，申请了一个指针的内存，而不是结构体的内存，

其次后面while循环遍历的时候写的太乱了，整理了一下就过了~~~OK

通关代码

List Insert( List L, ElementType X ){
    List p=L,s;
    s=(List*)malloc(sizeof(struct Node));
    s->Data=X;
    s->Next=NULL;
    if(L->Next==NULL){
         L->Next=s;
        return L;
    }
    while(p->Next&&p->Next->Data<X){
        p=p->Next;//往后走，直到该连接数据
    }
    s->Next=p->Next;
    p->Next=s;
    return L;
}

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

第0个测试点未过。。。

   while(p->Next->Next&&p->Next->Data<X){//这样终于第0个过了，可是第二个错了

    p=p->Next;//往后走，直到该连接数据
    }
    s->Next=p->Next;
    p->Next=s;
    return L;//这道题太乱了，给我整的.000

List Insert( List L, ElementType X ){
    List p=L,s;
    s=(List*)malloc(sizeof(List*));
    s->Data=X;
    s->Next=NULL;
    while(p->Next&&p->Data<X){
        p=p->Next;//往后走，直到该连接数据
    }
    s->Next=p->Next;
    p->Next=s;
    return L;
}

 过了的代码

List Insert( List L, ElementType X )
{
    PtrToNode p,q,t;
    p=(PtrToNode)malloc(sizeof(struct Node));
    p->Data=X;
    p->Next=NULL;
    if(L->Next==NULL)
      L->Next=p;//这里没错
    else
    {
       q=L->Next;
       t=L;
       while(q && q->Data<X)
       {  
           t=q;
           q=q->Next;
       }
       if(q==NULL)
         t->Next=p;
       else
       {
           p->Next=q;
           t->Next=p;
       }
    }
    return L;
}


List Insert( List L, ElementType X )
{
    List head=L;
    L=L->Next;
    List node=(List)malloc(sizeof(List));
    node->Data=X;
    node->Next=NULL;
    List q=head;
    if(L==NULL)
    {
        head->Next=node;
        return head;
    }//不是这里。。。测试点1
    while(L->Data<X)
    {
        q=L;
        L=L->Next;
        if(L->Next==NULL)
        {
            L->Next=node;
            return head;
        }
    }
    node->Next=L;
    q->Next=node;
    return head;
}