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;
                }
            }
        }

    }

}//无序输入，按升序形成有序表

运行截图

工程实践：模块化程序设计（3）图片