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)插图 工程实践:模块化程序设计(4)插图](https://static.esw.eswlnk.com/2021/06/2021060609392622.png-esw)
📮评论