工程实践：模块化程序设计（4）-Eswlnk Blog
智能摘要 AI
本文介绍了如何实现两个有序表的合并，并提供了相关函数接口和测试程序样例。题目要求从无序输入中生成有序数组，并将两个有序数组合并成一个新的有序数组。具体步骤包括： 1. 使用`input`函数读取无序数据并排序。 2. 定义`MergeList`函数，通过比较两个数组中的元素，依次插入到新的有序数组中。 3. 提供了辅助函数如`ListLength`、`GetElem`、`ListInsert`等，用于操作数组。 4. 最终输出合并后的有序数组。 示例输入为两行无序整数，输出为合并后升序排列的结果。

6-4 有序表合并-数组 (20 分)

本题要求实现两个有序表的合并。先分别输入两个有序表（输入时不要求按有序顺序输入，利用input函数实现数据按升序排列），然后将两个有序表进行合并，形成一个新表，表里数据按升序排序。

——题目要求

函数接口定义：

void MergeList(SqList La,SqList Lb,SqList *Lc);
Status ListLength(SqList L);
Status GetElem(SqList L,ElemType i,ElemType *e);
Status ListInsert(SqList *L,ElemType i,ElemType e);
Status ListEmpty(SqList L);
Status input(SqList *L);  //无序输入，按升序形成有序数组
void output(SqList *L);

裁判测试程序样例：

#include<stdio.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

//Status 主要用于描述函数结果状态代码，如OK等
typedef int Status;

// ElemType为数据元素类型，根据实际情况而定，这里设为int
typedef int ElemType;

#define MAXSIZE 20          // 存储空间初始分配量 
typedef struct
{
    ElemType data[MAXSIZE];  // 数组，存储数据元素 
    int length;              // 表当前有效长度 
}SqList;                    //  SqList结构体类型 

/* 函数定义 */
void MergeList(SqList La,SqList Lb,SqList *Lc);
Status ListLength(SqList L);
Status GetElem(SqList L,ElemType i,ElemType *e);
Status ListInsert(SqList *L,ElemType i,ElemType e);
Status ListEmpty(SqList L);
Status input(SqList *L);  //无序输入，按升序形成有序数组
void output(SqList *L);

int main(void){
    SqList La ,Lb , Lc ;
    Lc.length=0;
    La.length=0;
    Lb.length=0; 
    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(SqList *L)
{
    ElemType i;
    if(ListEmpty(*L)==OK)
        printf("No Element!");
    else    
        for (i = 0; i < L->length; i++)
        {
            printf("%d ", L->data[i]);
        }
    printf("\n");
}

/* 请在这里填写答案 */

输入样例：

在这里给出一组输入。例如：

3 2 6 5 0
10 2 1 6 8 9 0

输出样例：

在这里给出相应的输出。例如：

La: 2 3 5 6 
Lb: 1 2 6 8 9 10 
Lb+Lb: 1 2 2 3 5 6 6 8 9 10

我的解答


/* 请在这里填写答案 */
void MergeList(SqList La, SqList Lb, SqList* 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 ListLength(SqList L) {
    int i = 0;
    while (1)
    {
        if (L.data[i] == 0)
        {
            break;
        }
        i++;
    }
    return i;
}
Status GetElem(SqList L, ElemType i, ElemType* e) {//e来存放满足序号的值
    int t;
    if (L.length > 0 && i <= L.length)
    {
        *e = L.data[i - 1];
        return OK;
    }
    else
        return ERROR;
}
Status ListInsert(SqList* L, ElemType i, ElemType e) {
    (*L).data[i - 1] = e;
    (*L).length = i;
    return OK;
}
Status ListEmpty(SqList L) {
    if (L.length == 0)
        return OK;
    else
        return ERROR;
}
Status input(SqList* L) {
    int  i = 0;//计数
    while (1)
    {
        scanf("%d", &(*L).data[i]);
        if ((*L).data[i] == 0)
            break;//若是最后一个0 跳出循环
        i++;
    }
    (*L).length = i;
    int tmp;//临时变量
    int l;
    int j;//第二个计数
    for (l = 0; l < i - 1; l++)
        for (j = 0; j < i - 1 - l; j++)
            if ((*L).data[j] > (*L).data[j + 1])//交换数值 小的在前面
            {
                tmp = (*L).data[j];
                (*L).data[j] = (*L).data[j + 1];
                (*L).data[j + 1] = tmp;
            }
    return OK;
}//无序输入，按升序形成有序数组

运行截图

工程实践：模块化程序设计（4）-Eswlnk Blog