#include <malloc.h>
#include <stdio.h>
#define ERROR 0
#define OK 1
#define ElemType inttypedef int Status;
typedef struct LNode
{int data;struct LNode *next;
} LNode, *LinkList;Status CreateLink_L(LinkList &L, int n)
{// 创建含有n个元素的单链表LinkList p, q;int i;ElemType e;L = (LinkList)malloc(sizeof(LNode));L->next = NULL; // 先建立一个带头结点的单链表q = (LinkList)malloc(sizeof(LNode));q = L;for (i = 0; i < n; i++){scanf("%d", &e);p = (LinkList)malloc(sizeof(LNode)); // 生成新结点p->data = e;q->next = p;p->next = NULL; //确保最后一节点的数据源指向 nuLLq = p;}return OK;
}Status ListInsert_L(LinkList &L, int i, ElemType e)
{ // 算法2.9// 在带头结点的单链线性表L的第i个元素之前插入元素eLinkList p, s;p = L;int j = 0;while (p && j < i - 1){ // 寻找第i-1个结点p = p->next;++j;}if (!p || j > i - 1)return ERROR; // i小于1或者大于表长s = (LinkList)malloc(sizeof(LNode)); // 生成新结点s->data = e;s->next = p->next; // 插入L中p->next = s;return OK;
} // LinstInsert_LStatus ListDelete_L(LinkList &L, int i, ElemType &e)
{ // 算法2.10// 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值LinkList p, q;p = L;int j = 0;while (p->next && j < i - 1){ // 寻找第i个结点，并令p指向其前趋p = p->next;++j;}if (!(p->next) || j > i - 1)return ERROR; // 删除位置不合理q = p->next;p->next = q->next; // 删除并释放结点e = q->data;free(q);return OK;
} // ListDelete_LStatus LoadLink_L(LinkList &L)
{// 单链表遍历LinkList p = L->next;if (p == NULL)printf("The List is empty!"); // 请填空else{while (p != NULL) // 请填空{printf("%d ", p->data);p = p->next; // 请填空}}printf("\n");return OK;
}Status MergeLink_L(LinkList &A, LinkList &B, LinkList &C) //其实这个和顺序表的差不多 体现了泛型的思想
{LinkList pA = A->next; //让PA指向A链表第一个有效节点（首节点）LinkList pB = B->next; //让PB指向B链表第一个有效节点（首节点）LinkList pC = C; //让PC指向C链表的头结点while (pA != NULL && pB != NULL){if (pA->data > pB->data){pC->next = pB; //让B表的节点 接到C上pB = pB->next; //指针后移动pC = pC->next; //指针后移动}else{pC->next = pA; //同上pA = pA->next;pC = pC->next;}}if (pA == NULL){while (pB != NULL){pC->next = pB;pB = pB->next;pC = pC->next;}}else{while (pA != NULL){pC->next = pA;pA = pA->next;pC = pC->next;}}return OK; //别忘了
}int main()
{int lenA, lenB;LinkList A;LinkList B;scanf("%d", &lenA);CreateLink_L(A, lenA);scanf("%d", &lenB);CreateLink_L(B, lenB);printf("List A:");LoadLink_L(A);printf("List B:");LoadLink_L(B);LinkList C = (LinkList)malloc(sizeof(LNode));C->next = NULL; // 先建立一个带头结点的单链表MergeLink_L(A, B, C);printf("List C:");LoadLink_L(C);return 0;
}/*设计一个算法将两个非递减有序链表A和B合并成一个新的非递减有序链表C。输入格式
第一行：单链表A的元素个数
第二行：单链表A的各元素（非递减），用空格分开
第三行：单链表B的元素个数
第四行：单链表B的各元素（非递减），用空格分开输出格式
第一行：单链表A的元素列表
第二行：单链表B的元素列表
第三行：合并后单链表C的元素列表输入样例
6
12 24 45 62 84 96
4
15 31 75 86输出样例
List A:12 24 45 62 84 96
List B:15 31 75 86
List C:12 15 24 31 45 62 75 84 86 96
*/