6-3 有序表合并-链表 (20 分)
本题要求实现两个有序表的合并。先分别输入两个有序表（输入时不要求按有序顺序输入），然后将两个有序表进行合并，形成一个新表，表里数据按什序排序。
——题目要求
函数接口定义：
Status ListLength(LinkList L);
void MergeList(LinkList La,LinkList Lb,LinkList *Lc);
Status ListInsert(LinkList *L,Status i,Status e);
Status GetElem(LinkList L,int i,ElemType *e);
void input(LinkList *L); //无序输入，按升序形成有序表
void output(LinkList *L);裁判测试程序样例：
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
//Status 主要用于描述函数结果状态代码，如OK等
typedef int Status;
// ElemType为数据元素类型，根据实际情况而定，这里设为int
typedef int ElemType;
struct LNode // 结点定义
{
ElemType data;
struct LNode *next;
};
typedef struct LNode * LinkList; // LinkList是一指针类型，描述表的头指针
//相关函数定义
Status ListLength(LinkList L);
void MergeList(LinkList La,LinkList Lb,LinkList *Lc);
Status ListInsert(LinkList *L,Status i,Status e);
Status GetElem(LinkList L,int i,ElemType *e);
void input(LinkList *L);
void output(LinkList *L);
int main(void){
LinkList La = NULL,Lb = NULL,Lc = NULL;
Status i;
ElemType *e;
input(&La);input(&Lb);
printf("La: ");output(&La);
printf("Lb: ");output(&Lb);
MergeList(La,Lb,&Lc);
printf("Lb+Lb: ");output(&Lc);
return 0;
}
void output(LinkList *L)
{
LinkList fp = *L;
if(fp==NULL)
{
printf("No Chain!");
}
else
while(fp){
printf("%d ",fp->data);
fp = fp->next;
}
printf("\n");
}
/* 请在这里填写答案 */输入样例：
在这里给出一组输入。例如：
1 3 2 5 4 6 0
4 6 9 8 7 0
输出样例：
在这里给出相应的输出。例如：
La: 1 2 3 4 5 6
Lb: 4 6 7 8 9
Lb+Lb: 1 2 3 4 4 5 6 6 7 8 9 我的解答
Status ListLength(LinkList L) {
LinkList p;
int len = 0;
for (p = L; p != NULL; p = p->next)
len++;
return len;
}
void MergeList(LinkList La, LinkList Lb, LinkList* Lc) {
int k = 0;
int La_len, Lb_len;
int i, j;
i = j = 1;
La_len = ListLength(La);
Lb_len = ListLength(Lb);
int p1, p2;
while (1)
{
if (i <= La_len && j <= Lb_len)
{
GetElem(La, i, &p1);
GetElem(Lb, j, &p2);
if (p1 <= p2)
{
k++;
ListInsert(Lc, k, p1);
++i;
}
else
{
k++;
ListInsert(Lc, k, p2);
++j;
}
}
else
break;
}
for (; i <= La_len; i++)//La
{
k++;
GetElem(La, i, &p1);
ListInsert(Lc, k, p1);
}
for (; j <= Lb_len; j++)//Lb
{
k++;
GetElem(Lb, j, &p2);
ListInsert(Lc, k, p2);
}
}
Status ListInsert(LinkList* L, Status i, Status e) {
LinkList head = *L;
LinkList tail = *L;//初始化p1,p1指向L
tail = (struct LNode*)malloc(sizeof(struct LNode));
tail->data = e;
tail->next = NULL;//初始化设置为NULL
if (*L == NULL)
{
*L = tail;//L没有 则直接插入并返回OK
return OK;
}
while (head->next != NULL && head != NULL)
{
head = head->next;
}
head->next = tail;//拼接
return OK;
}
Status GetElem(LinkList L, int i, ElemType* e) {
LinkList p;
int t = 0;
for (p = L; p != NULL; p = p->next)
{
t++;
if (t == i)
{
*e = p->data;
return OK;
}
if (t > i)
break;
}
return ERROR;
}
void input(LinkList* L) {//已测试 无误
int num;
LinkList p1, p2 = NULL;
scanf("%d", &num);
while (num != 0)
{
p1 = (struct LNode*)malloc(sizeof(struct LNode));
p1->data = num;
p1->next = NULL;//初始化为NULL
if (*L == NULL)
*L = p1;//将申请好的地址传入L 进行链接
else
p2->next = p1;
p2 = p1;
scanf("%d", &num);
}
//排序 前提 L存在
if (*L == NULL)
return;
else
{
LinkList p, head, tail;
p = *L;
tail = p->next;
int i, j, l, tmp;
i = j = 0;
l = ListLength(*L);//L的长度
for (i = 0; i < l - 1; i++)//遍历列表 然后按照升序排列
{
head = *L;
for (j = 0; j < l - 1; j++,head=head->next)
{
p = head;
tail = p->next;
if (p->data > tail->data)//小的在前 大的在后
{
tmp = p->data;
p->data = tail->data;
tail->data = tmp;
}
}
}
}
}//无序输入，按升序形成有序表运行截图
