基于顺序表实现集合的并交差运算实验报告
一实验题目: 基于顺序表实现集合的并交差运算
二 实验要求:
2.1:编写一个程序，实现顺序表的各种基本运算
(1)初始化顺序表h；
(2)依次采用尾插法插入a,b,c,d,e元素;
(3)输出顺序表h
(4)输出顺序表h的长度
(5)判断顺序表h是否为空
(6)输出顺序表h的第三个元素
(7)输出元素在a的位置
(8)在第4个元素位置上插入f元素
(9)输出顺序表h
(10)删除L的第3个元素
(11)输出顺序表
(12)释放顺序表
2.2:编写一个程序，采用顺序表表示集合(集合中不存在重复的元素),并将其按照递增的方式排序，构成有序顺序表，并求这样的两个集合的并,交和差。
三 实验内容:
3.1 线性表的抽象数据类型:
ADT List{
数据对象;D=
数据关系:R1=
基本操作：
InitList(&L)
操作结果;构造一个空的线性表L
DestroyList(&L)
初始条件：线性表L已存在
操作结果：销毁线性表L
ClearList(&L)
初始条件：线性表L已存在
操作结果：将L置为空表
ListEmpty(L)
初始条件：线性表已存在
操作结果：若L为空表，则返回TRUE，否则返回FALSE
ListLength(L)
初始条件：线性表已存在
操作结果：返回L中数据元素的个数
GetElem(L,i)
初始条件:线性表已存在，1<=i<=ListLength(L)
操作结果：用e返回L中第i个数据元素的值
LocateElem(L,i,e)
初始条件：线性表已存在，用循环遍历整个线性表，如果e与线性表中的元素相同；
操作结果：用此时的i+1返回该元素在线性表的位序
ListInsert(&L,i,e)
初始条件：线性表存在，1<=i<=ListLength(L)+1;
操作结果：在L中第i个位置之前插入新的数据元素,e,L的长度加1。
ListDelete(&L,i,&e)
初始条件:线性表L已存在且非空，1<=i<=ListLength(L)；
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
}ADT List
3.2存储结构的定义;
#define maxn 50
typedef char Elemtype;
typedef struct
{
Elemtype data[maxn];
int length;
}Sqlist;
3.3基本操作实现:
void InitList(SqList *&L)//初始化顺序表
{
L = (SqList *)malloc(sizeof(SqList));//用malloc动态申请一个顺序表的内存空间
L->length = 0;
}
void DestroyList(SqList *L)
{
free(L);//释放指针L
}
bool ListEmpty(SqList *L)
{
return (L->length == 0);//length为0表示表空
}
int ListLength(SqList *L)
{
return (L->length);
}
void DispList(SqList *L)
{
int i;
if(ListEmpty(L)) return ;
for(i = 0;i < L->length;i++)
{
printf("%c ",L->data[i]);
printf("\n");
}
}
bool GetElem(SqList *L,int i,ElemType &e)
{
if(i < 1||i > L->length) return false;
e = L->data[i-1];
return true;
}
int LocateElem(SqList *L,ElemType e)
{
int i = 0;
while(i < L->length&&L->data[i]!=e)
{
i++;
}
if(i >= L->length) return 0;
else return i+1;
}
bool ListInsert(SqList *&L,int i,ElemType e)
{
int j;
if(i < 1||i>L->length+1) return false;
i--;
for(j=L->length;j>i;j--)
L->data[j]=L->data[j-1];
L->data[i]=e;
L->length++;
return true;
}
bool ListDelete(SqList *&L,int i,ElemType &e)
{
int j;
if(i<1||i>L->length) return false;
i--;
e = L->data[i];
for(j = i;j<L->length-1;j++)
L->data[j]=L->data[j+1];
L->length--;
return true;
}
3.4解题思路：
1.先通过CreateListR 函数将集合 a 和 b 中的元素添加到顺序表 ha 和 hb 中 ，添加过程使用的是顺序表原有的Initlist 函数（初始化表） 和 ListInsert 函数 （向表中插入元素） 。
2.因为原集合是无序的， 所以我通过 sort 函数 （冒泡排序），使得集合变得有序。
3.得到有序集合 ha 和 hb 后， 便可以使用 Union 函数（类似归并的思想写出来的求并集的函数），求出 ha 和 hb 的并集。
4.而求交集的方法则是， 通过将 集合 a 中的元素一个一个取出，并通过 函数LocateElem ，查看集合 hb 中是否存在该元素，如果存在则将 元素放入 hc ，如果不存在，则舍去。 以此求得 两 集合的交集。
5.求两集合的差 则可以反过来，同样通过将 集合 a 中的元素一个一个取出，并通过 函数LocateElem ，查看集合 hb 中是否存在该元素，如果不存在则将 元素放入 hc ，如果存在，则舍去。 以此求得两集合的差集。
3.5解题过程：
实验源代码如下：
3.5.1顺序表的各种运算
#include <iostream>
#include <cstdio>
#include <malloc.h>
using namespace std;
#define maxn 50
typedef char Elemtype;
typedef struct
{
Elemtype data[maxn];
int length;
}Sqlist;
void Initlist(Sqlist *&L)
{
L =(Sqlist *)malloc(sizeof(Sqlist));
L->length = 0;
}
bool ListInsert(Sqlist *&L, int x, char c)
{
int j;
if(x<1 || x>L->length+1)
return false;
x--;
for(j = L->length; j>x ; --j)
{
L->data[j] = L->data[j-1];
}
L->data[x] = c;
L->length++;
return true;
}
bool ListEmpty(Sqlist *L)
{
return (L->length==0);
}
void DispList(Sqlist *L)
{
int i;
if(ListEmpty(L)) return ;
for(i = 0;i < L->length; ++i)
{
printf(" %c",L->data[i]);
}
printf("\n");
}
int ListLength(Sqlist *L)
{
return L->length;
}
bool GetElem(Sqlist *L,int x,Elemtype &c)
{
if(x<1 || x>L->length)
return false;
c = L->data[x-1];
return true;
}
int LocateElem(Sqlist *L,Elemtype e)
{
int i = 0;
while(i<L->length && L->data[i]!=e)
i++;
if(i==L->length)
return 0;
else
return i+1;
}
bool ListDelete(Sqlist *&L,int x,Elemtype &e)
{
int j;
if(x<1 ||x >L->length + 1)
return false;
x--;
e = L->data[x];
for(j = x;j < L->length-1; ++j)
L->data[j] = L->data[j + 1];
L->length--;
return true;
}
void DestroyList(Sqlist *L)
{
free(L);
}
int main( )
{
Sqlist *p;
Elemtype e;
printf("(1)初始化顺序表 p\n");
Initlist(p);
printf("(2)依次采用尾插法插入 a , b , c , d , e 元素\n");
ListInsert(p,1,'a');
ListInsert(p,2,'b');
ListInsert(p,3,'c');
ListInsert(p,4,'d');
ListInsert(p,5,'e');
printf("(3)输出顺序表 p:");
DispList(p);
printf("(4)顺序表 p 长度=%d\n",ListLength(p));
printf("(5)顺序表 p 为%s\n",(ListEmpty(p)?"空":"非空"));
GetElem(p,3,e);
printf("(6)顺序表 p 的第3个元素=%c\n",e);
printf("(7)元素 a 的位置=%d\n",LocateElem(p,'a'));
printf("(8)在第 4 个元素位置上插入 f 元素\n");
ListInsert(p,4,'f');
printf("(9)输出顺序表 p:");
DispList(p);
printf("(10)删除 p 的第3个元素\n");
ListDelete(p,3,e);
printf("(11)输出顺序表 p: ");
DispList(p);
printf("(12)释放顺序表 p\n");
DestroyList(p);
return 0;
}
3.5.2求集合的并交差
#include <iostream>
#include <cstdio>
#include <malloc.h>
using namespace std;
#define maxn 50
typedef char Elemtype;
typedef struct
{
Elemtype data[maxn];
int length;
}Sqlist;
void Initlist(Sqlist *&L)
{
L =(Sqlist *)malloc(sizeof(Sqlist));
L->length = 0;
}
bool ListInsert(Sqlist *&L, int x, char c)
{
int j;
if(x<1 || x>L->length+1)
return false;
x--;
for(j = L->length; j>x ; --j)
{
L->data[j] = L->data[j-1];
}
L->data[x] = c;
L->length++;
return true;
}
bool ListEmpty(Sqlist *L)
{
return (L->length==0);
}
void DispList(Sqlist *L)
{
int i;
if(ListEmpty(L)) return ;
for(i = 0;i < L->length; ++i)
{
printf("%c",L->data[i]);
}
printf("\n");
}
int ListLength(Sqlist *L)
{
return L->length;
}
bool GetElem(Sqlist *L,int x,Elemtype &c)
{
if(x<1 || x>L->length)
return false;
c = L->data[x-1];
return true;
}
int LocateElem(Sqlist *L,Elemtype e)
{
int i = 0;
while(i<L->length && L->data[i]!=e)
i++;
if(i==L->length)
return 0;
else
return i+1;
}
bool ListDelete(Sqlist *&L,int x,Elemtype &e)
{
int j;
if(x<1 ||x >L->length + 1)
return false;
x--;
e = L->data[x];
for(j = x;j < L->length-1; ++j)
L->data[j] = L->data[j + 1];
L->length--;
return true;
}
void DestroyList(Sqlist *L)
{
free(L);
}
void CreateListR(Sqlist *&L,Elemtype e[],int n)
{
Initlist(L);
int i;
ListInsert(L,1,e[0]);
for(i = 1;i < n; ++i)
{
if(!LocateElem(L,e[i]))
ListInsert(L,i+1,e[i]);
}
}
void sort(Sqlist *&L)
{
int i, j;
for(i = 0;i < L->length; ++i)
{
for(j = 0;j < L->length; ++j)
{
if(L->data[i] < L->data[j])
{
char t = L->data[i];
L->data[i] = L->data[j];
L->data[j] = t;
}
}
}
}
void Union(Sqlist *a,Sqlist *b,Sqlist *&c)//利用归并的思想求并集
{
Initlist(c);
int i, j, k;
i = 0;
j = 0;
k = 0;
while(i<a->length && j<b->length)
{
if(a->data[i] < b->data[j])
{
ListInsert(c,k+1,a->data[i]);
k++;
i++;
}
else if(a->data[i] == b->data[j])
{
ListInsert(c,k+1,a->data[i]);
k++;
i++;
j++;
}
else
{
ListInsert(c,k+1,b->data[j]);
k++;
j++;
}
}
while(i<a->length)
{
ListInsert(c,k+1,a->data[i]);
i++;
k++;
}
while(j<b->length)
{
ListInsert(c,k+1,b->data[j]);
j++;
k++;
}
}
void InsterSect(Sqlist *a,Sqlist *b,Sqlist *&c)
{
DestroyList(c);
Initlist(c);
int i ,k;
for(i = 0,k = 0;i < a->length; ++i)
{
if(LocateElem(b,a->data[i]))
{
ListInsert(c,k+1,a->data[i]);
k++;
}
}
}
void Subs(Sqlist *a,Sqlist *b,Sqlist *&c)
{
DestroyList(c);
Initlist(c);
int i ,k;
for(i = 0,k = 0;i < a->length; ++i)
{
if(!LocateElem(b,a->data[i]))
{
ListInsert(c,k+1,a->data[i]);
k++;
}
}
}
int main( )
{
Sqlist *ha, *hb, *hc;
Elemtype a[]={'c','a','e','h'};
Elemtype b[]={'f','h','b','g','d','a'};
printf("集合的运算如下\n");
CreateListR(ha,a,4);
CreateListR(hb,b,6);
printf("原 集 合 A:"); DispList(ha);
printf("原 集 合 B:"); DispList(hb);
sort(ha);
sort(hb);
printf("有序集合A："); DispList(ha);
printf("有序集合B："); DispList(hb);
Union(ha,hb,hc);
printf("集合的并C："); DispList(hc);
InsterSect(ha,hb,hc);
printf("集合的交C："); DispList(hc);
Subs(ha,hb,hc);
printf("集合的差C："); DispList(hc);
DestroyList(ha);
DestroyList(hb);
DestroyList(hc);
return 0;
}
四 实验结果:
