6-1 递增的整数序列链表的插入 分数 15 作者 DS课程组 单位 浙江大学 本题要求实现一个函数，在递增的整数序列链表（带头结点）中插入一个新整数，并保持该序列的有序性。 函数接口定义： 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; } /* 你的代码将被嵌在这里 */

List Insert(List L, ElementType X) {
    PtrToNode p = L; // p指向头结点
    PtrToNode newNode = (PtrToNode)malloc(sizeof(struct Node)); // 创建新结点
    newNode->Data = X; // 新结点存储数据
    newNode->Next = NULL; // 新结点的Next指针初始化为NULL
    while (p->Next && p->Next->Data < X) {
        p = p->Next; // 遍历链表，找到插入位置
    }
    newNode->Next = p->Next; // 新结点的Next指针指向p的下一个结点
    p->Next = newNode; // p的Next指针指向新结点
    return L; // 返回链表头指针
}

上述代码中，我们先定义指针 `p` 指向头结点，然后创建一个新结点 `newNode`，将其 `Data` 域设置为插入的元素 `X`，将其 `Next` 指针初始化为 `NULL`。

接下来，我们遍历链表，找到需要插入的位置。具体来说，如果当前结点的下一个结点不为空且下一个结点的数据小于插入的元素 `X`，则继续遍历。当遍历到最后一个结点或者下一个结点的数据大于等于插入的元素 `X` 时，说明找到了插入的位置。

最后，我们将新结点的 `Next` 指针指向 `p` 的下一个结点，将 `p` 的 `Next` 指针指向新结点，然后返回链表头指针即可。