//利用线性表中的链表实现两个链表的归并
//头文件
#pragma warning(disable: 4996)
#include <stdio.h>
#include <stdlib.h>
//定义返回码与常量
#define OK 1
#define TRUE 1
#define ERROR 0
#define OVERFLOW -1
//定义类型与结构
typedef int Status;
typedef int ElemType;
typedef struct LNode {
//节点类型
ElemType data; //数据域
struct LNode* next; //指针域
}LNode, * LinkList;
//基本操作的实现
Status InitList_L(LinkList& L) {
//构造一个空的线性链表L
LNode* q;
L = (LNode*)malloc(sizeof(LNode));
if (L == NULL) return OVERFLOW;
L->next = NULL; q = L;
return OK;
}//InitList_L;
Status InitList_Lc(LinkList& L, int n) {
//构造一个线性链表Lc
//n为链表的大小
LNode* p;
L = (LNode*)malloc(sizeof(LNode));
if (L == NULL) return OVERFLOW;
L->next = NULL; p = L;
for (int i = 1; i <= n; i++) {
p = (LNode*)malloc(sizeof(LNode));
L->next = NULL; p = L;
}
return OK;
}//InitList_Lc;
Status PrintList_L(LinkList L) {
//输出链表L
LNode* p;
p = L->next;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
return OK;
}//PrintList_L;
Status CreatList_L(LinkList& L, int n) {
//正序输入数据
//L为头节点，n为元素个数
LNode* q, * p;
L = (LNode*)malloc(sizeof(LNode));
if (L == NULL) return OVERFLOW;
L->next = NULL; q = L;
for (int i = 1; i <= n; i++) {
p = (LNode*)malloc(sizeof(LNode));
scanf("%d", (&p->data));
q->next = p; q = p;
}
q->next = NULL;
return OK;
}//CreatList_L;
Status Judge_L(LNode *L) {
//判断L是否为非递减排序,若不是则给链表排序。
//L为一个链表
LNode *q, *p;
int N = 0;
for (p = L->next; p != NULL; p = p->next) {
for (q = p->next; q != NULL; q = q->next) {
if (p->data > q->data) {
int t = p->data; p->data = q->data; q->data = t;
N = 1;
}
}
}
if (N!= 0) return OVERFLOW;
//N为0，表示L是非递减排序的，N为1，表示L不是非递减排序的。
return OK;
}//Judge_L;
Status MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc) {
//已知两个链表La，Lb中的元素按值的非递减排序
//归并La和Lb得到一个新的链表Lc，Lc的值也是非递减排序的
LNode* pa, * pb, * pc;
pa = La->next; pb = Lb->next;
Lc = pc = La;
while (pa && pb) {
if (pa->data <= pb->data)
{
pc->next = pa; pc = pa; pa = pa->next;
}
else { pc->next = pb; pc = pb; pb = pb->next; }
}
pc->next = pa ? pa : pb;
free(Lb); //释放Lb的地址
return OK;
}//MergeList_L;
//主函数
int main() {
LNode* La, * Lb, * Lc;
int n = 0;
int m = 0;
//链表La
printf("请输入La中的元素个数(个数为整数且范围为：1~20)：");
scanf("%d", &n);
if (n < 1 || n>20) {
while (n < 1 || n>20) {
printf("请重新输入La中的元素个数(个数为整数且范围为：1~20)：");
scanf("%d", &n);
}
}
printf("请输入La中的元素(元素为整数),从小到大输入：");
CreatList_L(La, n);
//链表Lb
printf("请输入Lb中的元素个数(个数为整数且范围为：1~20)：");
scanf("%d", &m);
if (m < 1 || m>20) {
while (m < 1 || m>20) {
printf("请重新输入Lb中的元素个数(个数为整数且范围为：1~20)：");
scanf("%d", &m);
}
}
printf("请输入Lb中的元素(元素为整数),从小到大输入：");
CreatList_L(Lb, m);
//链表Lc
InitList_Lc(Lc,m+n);
//La与Lb是否为非递减排序与归并后的输出
if (InitList_Lc(Lc, m + n) == OK) {
if (Judge_L(La) == OVERFLOW) //判断La是非否为非递减排序
printf("La不是非递减排序，La重新排序为： ");
else
printf("La是非递减排序,La为： ");
PrintList_L(La); //输出La
if (Judge_L(Lb) == OVERFLOW) //判断Lb是非否为非递减排序
printf("Lb不是非递减排序，Lb重新排序为： ");
else
printf("Lb是非递减排序,Lb为： ");
PrintList_L(Lb); //输出Lb
if (MergeList_L(La, Lb, Lc) == OK)
printf("La,Lb归并排序后为： ");
PrintList_L(Lc); //输出Lc,Lc为La与Lb归并后的链表
}
return OK;
}
Processed:
0.009, SQL:
9
