顺序表是一种简单的数据存储结构,既然把数据存起来就肯定要用,利用顺序表充当集合来实现集合的常用3种运算是一种常见的问题。代码如下:
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define FALSE -1
#define TURE 1
#define ERROR -1
#define OVERFLOW -1
#define INFEASIBLE -1
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int Status;
typedef int ElemType;
typedef struct
{
ElemType *elem;
int length;
int listsize;
}Sqlist;
Status InitList(Sqlist &L)//顺序表的创建,把顺序表当集合用
{
L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (!L.elem) exit(OVERFLOW);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}
Status LengthList(Sqlist L)
{
return L.length;
}
Status LocateELem(Sqlist L, ElemType e)//定位函数,找到某个元素的位置
{
int i = 1;
bool cmp = 0;
while (i <= L.length && !cmp)
{
if (L.elem[i - 1] == e)
cmp = 1;
i++;
}
if (cmp)
return i - 1;
else return 0;
}
void TraverList(Sqlist L)//遍历集合
{
int i;
if (L.length != 0)
{
for (i = 0; i < L.length; i++)
printf("%5d", L.elem[i]);
}
else printf("空集\n");
}
void InsertElem(Sqlist L, int i, ElemType e)//插入元素
{
ElemType *p, *q;
if (i<0 || i>L.length + 1)
{
printf("位置不正常\n");
return;
}
if (L.length == L.listsize)
{
L.elem = ((ElemType*)realloc(L.elem, (LIST_INIT_SIZE + LISTINCREMENT) * sizeof(ElemType)));
L.listsize = LIST_INIT_SIZE + LISTINCREMENT;
}
q = &L.elem[i - 1];
for (p = &L.elem[L.length - 1]; p > q; p--)
*(p + 1) = *p;
*(q + 1) = e;
L.length++;
}
void Union_Sq(Sqlist La, Sqlist Lb, Sqlist &Lc) {//并集的实现
int i;
ElemType elem;
Lc.length = 0;
for (i = 0; i < La.length; i++)
Lc.elem[Lc.length++] = La.elem[i];
Lc.length = La.length;
for (i = 1; i <= Lb.length; i++) {
elem = Lb.elem[i - 1];
if (!LocateELem(La, elem))
{
InsertElem(Lc, Lc.length, elem);
Lc.length++;
}
}
}
void Mix_Sq(Sqlist La, Sqlist Lb, Sqlist &Lc) {//交集的实现
int i;
ElemType elem;
Lc.length = 0;
for (i = 1; i <= La.length; i++) {
elem = La.elem[i - 1];
if (LocateELem(Lb, elem))
{
InsertElem(Lc, Lc.length, elem);
Lc.length++;
}
}
}
void Differ_Sq(Sqlist La, Sqlist Lb, Sqlist &Lc) {//差集的实现
int i;
ElemType elem;
Lc.length = 0;
for (i = 1; i <= La.length; i++) {
elem = La.elem[i - 1];
if (!LocateELem(Lb, elem))
{
InsertElem(Lc, Lc.length, elem);
Lc.length++;
}
}
}
int main()
{
Sqlist La, Lb, Lc, Ld, Le;
InitList(La);
InitList(Lb);
InitList(Lc);
InitList(Ld);
InitList(Le);
int i;
ElemType e = 0;
printf("初始顺序表1的长度%d\n\n", LengthList(La));
printf("请输入要添加的元素个数:");
scanf_s("%d", &La.length);
printf("\n当前顺序表的长度%d\n", LengthList(La));
printf("\n请输入线性表元素:");
for (i = 0; i < La.length; i++)
scanf_s("%d", &La.elem[i]);
printf("\n您输入的元素为:");
TraverList(La);
printf("\n");
printf("\n初始顺序表2的长度%d\n\n", LengthList(Lb));
printf("请输入要添加的元素个数:");
scanf_s("%d", &Lb.length);
printf("\n当前顺序表的长度%d\n", LengthList(Lb));
printf("\n请输入线性表元素:");
for (i = 0; i < Lb.length; i++)
scanf_s("%d", &Lb.elem[i]);
printf("\n您输入的元素为:");
TraverList(Lb);
printf("\n\n\n");
Union_Sq(La, Lb, Lc);
printf("1、2集合并集为:");
TraverList(Lc);
printf("\n1、2集合交集为:");
Mix_Sq(La, Lb, Ld);
TraverList(Ld);
printf("\n1、2集合差集为:");
Differ_Sq(La, Lb, Le);
TraverList(Le);
printf("\n");
return 0;
}