2. 基本操作（集合合并）
| 成绩 | 10 | 开启时间 | 2021年09月13日 星期一 15:10 |
| 折扣 | 0.8 | 折扣时间 | 2021年09月30日 星期四 23:55 |
| 允许迟交 | 否 | 关闭时间 | 2021年10月17日 星期日 23:55 |
我们讨论一个如何使用基本运算将两个集合合并的问题。下面，是采用基本操作完成集合合并的操作。
问题： 线性表的合并A＝A∪B
设：有两个集合A和B分别用两个线性表LA和LB表示。求一个新的集合 A＝A∪B。
输入：两个集合
输出：按照要求合并后的集合。
编程要求：题目中已经给出了主函数和部分已经实现的基本操作，请阅读给出的程序，编写其他尚未完成的基本操作（基本操作的定义请参见严蔚敏老师的教材）。
注意：提交代码的时候，仅需提交你编写的那三个基本操作函数即可。
预设代码
前置代码
/* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */ #include
#include
#define LIST_MAX_SIZE 100 //空间初始大小
#define OK 1
#define ERROR 0 typedef int ElemType; //元素的数据类型
typedef int Status; //状态。函数返回值
typedef struct {
// ElemType elem[ LIST_MAX_SIZE ]; // 存储空间 ElemType * elem; // 存储空间 int length; // 当前元素个数 int listsize; // 能够保存的最大元素数量
} SqList; // 以下为函数原型
Status InitList( SqList & );
Status ListInsert( SqList &, int, ElemType ); //这是需要你编写的基本操作
Status GetElem( SqList, int, ElemType & ); //这是需要你编写的基本操作
int ListLength( SqList ); //这是需要你编写的基本操作
Status ListTraverse( SqList &, void (*)( ElemType ) );
void ListUnion( SqList &, SqList );
void out( ElemType );
int equal(ElemType, ElemType );
Status LocateElem(SqList, ElemType, Status (*)(ElemType,ElemType)); // 以下为函数定义
Status InitList( SqList & L ) // 建立一个空的线性表 L
{ L.elem = (ElemType *)malloc(LIST_MAX_SIZE*sizeof(ElemType));
// if ( !L.elem ) exit(-1); // 失败则终止程序 L.length = 0; // 空表长度为0 L.listsize = LIST_MAX_SIZE; return OK;
} Status ListTraverse( SqList &L, void (*visit)( ElemType ) )
{ // 依次对L的每个元素调用函数visit()。若visit()失败，则操作失败 int i, L_len = ListLength( L ); ElemType e; for ( i = 1; i <= L_len; i++ ) { GetElem(L, i, e); (*visit)( e ); } return OK;
} int equal(ElemType x, ElemType y)
{ return x==y;
} Status LocateElem( SqList L, ElemType e, Status (*compare)(ElemType,ElemType) )
{ //在L中查找与元素 e 满足compare() 的第 1 个元素 //返回 L 中第 1 个与 e 满足关系compare( ) 的元素的位序 int i = 1; ElemType * p; while ( i<=L.length ) // if ( (*compare)(e,L.elem[i-1]) ) break; else i++; if ( i <= L.length ) return i; // 找到 e，返回位序i else return 0; //若没有找到，则返回0
} void out( ElemType e )
{ printf("%d,", e);
} void ListUnion( SqList &La, SqList Lb ) //求 A＝A∪B
{ int La_len, Lb_len, i; ElemType e; La_len = ListLength( La ); // 求线性表的长度 Lb_len = ListLength( Lb ); for ( i = 1; i <= Lb_len; i++ ) { GetElem(Lb, i, e); // 取Lb中第i个数据元素赋给e if ( !LocateElem( La, e, equal ) ) ListInsert ( La, ++La_len, e ); // La中不存在和 e 相同的数据元素，则插入 }
} int main()
{ SqList La, Lb; int n, i; ElemType e; InitList( La ); InitList( Lb ); scanf("%d", &n); //读入集合A for ( i=0; i | 测试输入 | 期待的输出 | 时间限制 | 内存限制 | 额外进程 | |
|---|---|---|---|---|---|
| 测试用例 1 | 以文本方式显示
| 以文本方式显示
| 1秒 | 64M | 0 |
| 测试用例 2 | 以文本方式显示
| 以文本方式显示
| 1秒 | 64M | 0 |
| 测试用例 3 | 以文本方式显示
| 以文本方式显示
| 1秒 | 64M | 0 |
代码
Status ListInsert( SqList &L, int i, ElemType e )
{
// if(i<1||i>L.length+1){
// return ERROR;
// }
// if(L.length>=L.listsize){
// return ERROR;
// }L.elem[L.length]=e;L.length++;
// L.listsize++;return OK;
}Status GetElem( SqList L, int i, ElemType &e ){
// if(i<1||i>L.length){
// return ERROR;
// }e=L.elem[i-1];return OK;
}int ListLength( SqList L){return L.length;
}解释
ListInsert
ListInsert函数就是在结构体里面那个数组后面加一个数，其实函数名字叫ListAdd更合适一点，因此整个函数完全可以不用第二个参数，直接
L.elem[L.length]=e;即可。当然，写成
L.elem[i-1]=e;也是可以的。至于代码中注释的部分都是可写可不写的，对于运行结果没有影响，我当时写的时候就没加，照样AC了。
// if(i<1||i>L.length+1){
// return ERROR;
// }
// if(L.length>=L.listsize){
// return ERROR;
// }这一部分就是判断合法性的，乐学给的用例都很好，不存在合不合法的问题。当然最好还是加上。
GetElem
该函数就是得到数组某一位置上的数字，原则上来讲两行就能解决，注意数组的下标是i-1而不是i，因为我们补充这三个函数都要看其他函数是怎么调用的：
for ( i = 1; i <= Lb_len; i++ ) { GetElem(Lb, i, e); // 取Lb中第i个数据元素赋给e 这里for循环的i从1开始，假如我们要取第一个数据元素，也就是下标为0的那个数据，那么函数中的下标一定不是i，而是i-1。
注释还是可写可不写：
Status GetElem( SqList L, int i, ElemType &e ){
// if(i<1||i>L.length){
// return ERROR;
// }e=L.elem[i-1];return OK;
}ListLength
就是一个取长度的函数，没什么可说的：
int ListLength( SqList L){return L.length;
}本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！