单向链表输入 遍历 及插入元素建立有序表

根据给定的信息，本文将详细解释以下几个核心知识点：创建单向链表、遍历单向链表、在非递减有序链表中插入元素、逆置链表中的元素、合并两个非递减有序链表使其成为非递增有序链表以及如何将一个链表分解成两个链表。 ### 创建单向链表 我们需要定义一个单向链表的数据结构。在给定的代码中，使用了如下的结构体定义： ```c typedef int ElemType; typedef struct LNode { ElemType data; struct LNode* next; } LNode, *LinkList; ``` 其中 `ElemType` 定义为整型，表示链表中存储的数据类型。`struct LNode` 是链表节点的结构体，包含数据域 `data` 和指向下一个节点的指针 `next`。 接下来，我们可以通过以下步骤创建单向链表： 1. **分配内存**：为头结点分配内存。 2. **读取输入**：从用户处获取要添加到链表中的元素数量和值。 3. **插入节点**：逐个创建新节点，并将其插入到链表头部。 ```c void CreateList_L(LinkList& L) { int n; LinkList p; printf("请输入元素数量: "); scanf("%d", &n); L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; // 初始化头结点 printf("请输入元素值: "); for (int i = 1; i <= n; i++) { p = (LinkList)malloc(sizeof(LNode)); // 分配内存 scanf("%d", &p->data); // 获取数据 p->next = L->next; L->next = p; // 插入新节点 } } ``` ### 遍历单向链表 遍历单向链表是指按照节点的顺序访问链表中的每个元素。这通常通过一个循环实现，每次迭代访问一个节点： ```c void outPut(LinkList& L) { LinkList p; p = L->next; printf("元素值: "); while (p) { printf("%d ", p->data); p = p->next; } } ``` ### 在非递减有序链表中插入元素 为了保持链表的有序性，在插入元素时需要找到正确的插入位置： ```c void insert(LinkList& L, ElemType e) { LinkList p, s, q; s = (LinkList)malloc(sizeof(LNode)); s->data = e; q = L; p = L->next; while (p && p->data <= e) { q = p; p = p->next; } s->next = p; q->next = s; } ``` ### 逆置链表中的元素 逆置链表的操作是将链表中的元素顺序反转： ```c void inversion(LinkList& L) { LinkList p, s; p = L->next; L->next = NULL; while (p) { s = p; p = p->next; s->next = L->next; L->next = s; } outPut(L); } ``` ### 合并两个非递减有序链表使其成为非递增有序链表 这个过程首先涉及到合并两个非递减有序链表，然后再将结果链表逆置以得到非递增有序链表： ```c void togIncrease(LinkList La, LinkList Lb, LinkList L) { LinkList p, a, b; L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; p = L; a = La->next; free(La); b = Lb->next; free(Lb); while (a && b) { if (a->data <= b->data) { p->next = a; a = a->next; p = p->next; } else { p->next = b; b = b->next; p = p->next; } } if (a) { p->next = a; } else { p->next = b; } outPut(L); } void togReduce(LinkList La, LinkList Lb, LinkList L) { togIncrease(La, Lb, L); inversion(L); } ``` ### 将一个链表分解成两个链表 这个操作可以基于某种条件（比如元素的奇偶性）来分解原始链表： ```c void dissociate(LinkList& l, LinkList& la, LinkList& lb) { LinkList p, q, rear, s; la = (LinkList)malloc(sizeof(LNode)); la->next = NULL; p = q = lb = l; p = l->next; rear = la; while (p) { if (p->data % 2 != 0) { s = p; rear->next = s; rear = rear->next; p = p->next; q->next = p; } else { q = p; p = p->next; } } } ``` 以上就是根据给定文件信息总结的核心知识点。这些知识点覆盖了单向链表的基本操作，包括创建、遍历、插入、删除、逆置等，同时也涉及到了更高级的操作，例如链表的合并与分解。