数据结构与数据库实验一集合的运算.docx

数据结构与数据库实验一集合的运算.docx

《数据结构与数据库实验一集合的运算.docx》由会员分享，可在线阅读，更多相关《数据结构与数据库实验一集合的运算.docx（22页珍藏版）》请在冰点文库上搜索。

数据结构与数据库实验一集合的运算

数据结构与数据库实验

仅供参考

实验一集合的表示及运算

实验名称：

集合的表示及运算

专业：

电气工程

姓名：

学号：

集合的表示及运算

一、实验要求

1．程序的功能：

实现集合的交、并、判断相等运算。

2．输入输出的要求：

设计的数据结构应有利于表示任意个数元素组成的集合。

3．测试数据。

（1）{a,b,c},{b,c,d}

（2）{a,b，c},{x,y}

（3）{},{x,y}

（4）{a,x,b},{a,x,b}

二、概要设计

1．采用的数据结构的定义及主要功能模块的功能：

Ø在本实验中，数据的存储采用数组连续存储方式。

由于本实验相对简单，功能相对较少，只是针对数组进行交并等基础性操作，所以本实验中只采用了函数模板，这样比结构体、类以及类模板都更加简洁、易懂，也更有利于实现对多种数据类型的数据进行操作。

而且，为了满足设计的数据结构应有利于表示任意个数元素组成的集合，在本实验中采用由用户自己输入所需存储空间的最大长度，动态分配所需存储空间。

由于含有动态生成的数据成员，必须自定义析构函数以释放动态分配的内存，本实验中的析构函数为Ｄｅｌｅｔｅ（Ｔ*,T*）。

Ø字符串的比较采用string类

２、各个函数模板的声明及其功能如下：

1、判断集合是否相等的运算：

templatevoiddeng_array（T*A,T*B,intA_mm,intB_mm）；//A、B为需要进行判断是否相等的数组，A_mm、B_mm分别为数组Ａ、Ｂ的最大存储空间，由用户在输入数组数据时确定并输入，算法根据用户输入的数据动态建立相应的存储空间。

以下各形式参量的意义均与此相同。

2、集合的交运算：

templatevoidjiao_array（T*A,T*B,intA_mm,intB_mm）；

3、集合的并运算：

templatevoidbing_array（T*A,T*B,intA_mm,intB_mm）；

4、析构函数：

templatevoidDelete（T*A,T*B）；//释放动态分配的内存

5、字符串的交运算

templatestringjiao_string（T&A,T&B）;

6、字符串的并运算

templatestringjiao_string（T&A,T&B）;

7、判断字符串是否相等：

采用string中的’=‘

if（A==B）cout<<"EQUAL"<

cout<<"NOTEQUAL"<

三、详细设计

1、各模块的流程图：

1、判断集合是否相等的运算：

数组长度是否相等

是

否

逐个比较数组中的元素是否相等

结束，输出NOTEQUAL

是

结束，输出EQUAL

2、集合的交运算：

数组中是否有空集

结束，输出NULL

否

比较两个数组长度

以较小的长度建立新数组，作为交集合

用A中的每一个元素与B中的元素比较

相等则存入C

3、集合的并运算：

数组A、B是否为空

有一个为空，不为空的数组即为并集

数组A、B均为空结束，输出NULL

去量数组长度的和，建立新数组，用于并集合

先把A复制到C中

用B中的每一个元素与C中的元素比较

不相等则存入C

4、析构函数：

释放动态分配的内存：

delete[]A;

delete[]B;

5、字符串的交运算

数组A、B是否为空

A、B均为空结束，输出NULL

从A中取出一个字符

在B中寻找它的出现位置

在B中，则复制到C中

重复上述循环，直到最后一个元素

6、字符串的并运算

数组A、B是否为空

有一个为空，不为空的数组即为并集

数组A、B均为空结束，输出NULL

先把A复制到C中

用B中的每一个元素与C中的元素比较

不相等则存入C

四、调试分析

1、在本实验中，集合的数据类型可以实现字符型、整型，用户可根据系统提示进行选择。

初始界面如下：

2、若选择字符型：

3、输入数组A、B的存储空间长度A_mm、B_mm，然后分别输入数组数据，最后输出执行结果：

4、整型与此类似：

测试数据的输出结果：

（1）{a,b,c},{b,c,d}

（2）{a,b，c},{x,y}

（3）{},{x,y}

（4）{a,x,b},{a,x,b}

（5）字符串的测试数据

A=”qwert”

B=”ert”

源程序：

#include

#include

usingnamespacestd;

templatevoiddeng_array（T*A,T*B,intA_mm,intB_mm）{

inti;

if（A_mm!

=B_mm）{

cout<<"NOTEQUAL"<

return;

}

for（i=0;i

if（A[i]!

=B[i]）{

cout<<"NOTEQUAL"<

}

}

cout<<"EQUAL"<

return;

}

templatevoidjiao_array（T*A,T*B,intA_mm,intB_mm）{

inti,j,k,t,m;

T*C;//={"NULL"};

if（A_mm==0||B_mm==0）{

cout<<"NULL"<

return;

}

k=A_mm>B_mm?

A_mm:

B_mm;

t=0;

C=newT[k];

for（i=0;i

for（j=0;j

{

if（A[i]==B[j]）{

C[t]=A[i];

t++;

}

}

if（t==0）{

cout<<"NULL"<

return;

}

m=0;

while（m

cout<<"C["<

m++;

}

cout<

m=0;

while（m

cout<

m++;

}

return;

}

templatevoidbing_array（T*A,T*B,intA_mm,intB_mm）{

inti,j,k,t;

T*C;

int*D;

if（A_mm==0&&B_mm==0）{

cout<<"NULL"<

return;

}

elseif（A_mm==0&&B_mm!

=0）{

t=B_mm;

C=newT[t];

for（j=0;j

C[j]=B[j];

}

for（intk=0;k

cout<

for（intp=0;p

cout<

cout<

}

elseif（A_mm!

=0&&B_mm==0）{

t=A_mm;

C=newT[t];

for（i=0;i

C[i]=A[i];

}

for（inth=0;h

cout<

for（intp=0;p

cout<

cout<

}

elseif（A_mm!

=0&&B_mm!

=0）{

t=A_mm+B_mm;

k=A_mm;

D=newint[B_mm];

C=newT[t];

for（i=0;i

for（i=0;i

j=0;

while（j

for（i=0;i

if（B[j]==C[i]）{D[j]=1;break;}

}

j++;

}

for（intq=0;q

if（D[q]==0）{C[k]=B[q];

k++;

}

}

intn=0;

while（n

cout<<"C["<

cout<<'\t';

n++;

}

cout<

for（intp=0;p

cout<

}

cout<

return;

}

templatevoidDelete（T*A,T*B）{

delete[]A;

delete[]B;

return;

}

templatestringbing_string（T&A,T&B）{

TC=A;

inti;

intAmm=A.length（）;

intBmm=B.length（）;

for（i=0;i

stringch=B.substr（i,1）;

intl=A.find（ch,0）;

if（l<0||l>=Amm）C=C+ch;

}

returnC;

}

templatestringjiao_string（T&A,T&B）{

TC;

inti;

intk=0;

intAmm=A.length（）;

intBmm=B.length（）;

for（i=0;i

stringch=B.substr（i,1）;

intl=A.find（ch,0）;

if（l>=k&&l

}

returnC;

}

intmain（）{

intAmm,Bmm;

charAB;//{INT,CHAR,STRING};

cout<<"ChooseTheTypeofData.CHAR（c/C）ORINT（i/I）ORSTRING（S/s）"<

cin>>AB;

if（AB=='C'||AB=='c'）{

cout<<"TYPECHAR字符型"<

inti=0;

intj=0;

char*A;

char*B;

Amm=0;

Bmm=0;

cout<<"Enter"<<'\t'<<"Amm"<<'\t';

cin>>Amm;

cout<<'\t'<<"Bmm"<<'\t';

cin>>Bmm;

cout<

A=newchar[Amm];

B=newchar[Bmm];

cout<<"Enter"<<'\t';

while（i

cout<<"A["<

i++;

}

cout<

i=0;

while（i

cin>>A[i];

cout<<'\t';

i++;

}

cout<

cout<<"Enter"<<'\t';

while（j

cout<<"B["<

j++;

}

cout<

j=0;

while（j

cin>>B[j];

cout<<'\t';

j++;

}

cout<<""<

cout<<"Theresultofjiao"<

jiao_array（A,B,Amm,Bmm）;

cout<

cout<<"Theresultofdeng"<

deng_array（A,B,Amm,Bmm）;

cout<<"Theresultofbing"<

bing_array（A,B,Amm,Bmm）;

Delete（A,B）;

return0;

}

if（AB=='S'||AB=='s'）{

cout<<"TYPEstring字符串"<

inti=0;

intj=0;

stringA;

stringB;

Amm=0;

Bmm=0;

charch='@';

cout<<"EnterstringAandendwith'@'"<

getline（cin,A,ch）;

cout<

cout<<"EnterstringBandendwith'@'"<

getline（cin,B,ch）;

cout<

cout<<""<

cout<<"Theresultofjiao"<

strings;

s=jiao_string（A,B）;

cout<

cout<

cout<<"Theresultofdeng"<

if（A==B）cout<<"EQUAL"<

cout<<"NOTEQUAL"<

//deng_array（A,B,Amm,Bmm）;

cout<<"Theresultofbing"<

stringc;

c=bing_string（A,B）;

cout<

//bing_array（A,B,Amm,Bmm）;

//Delete（A,B）;

return0;

//

}

if（AB=='I'||AB=='i'）{

cout<<"TYPEint整型"<

inti=0;

intj=0;

int*A;

int*B;

Amm=0;

Bmm=0;

cout<<"Enter"<<'\t'<<"Amm"<<'\t';

cin>>Amm;

cout<<'\t'<<"Bmm"<<'\t';

cin>>Bmm;

cout<

A=newint[Amm];

B=newint[Bmm];

cout<<"Enter"<<'\t';

while（i

cout<<"A["<

i++;

}

cout<

i=0;

while（i

cout<<'\t';

cin>>A[i];

//cout<

i++;

}

cout<

cout<<"Enter"<<'\t';

while（j

cout<<"B["<

j++;

}

cout<

j=0;

while（j

cout<<'\t';

cin>>B[j];

//cout<

j++;

}

cout<

cout<<""<

cout<<"Theresultofjiao"<

jiao_array（A,B,Amm,Bmm）;

cout<

cout<<"Theresultofdeng"<

deng_array（A,B,Amm,Bmm）;

cout<<"Theresultofbing"<

bing_array（A,B,Amm,Bmm）;

Delete（A,B）;

return0;

//

}

//Array.deng_array（A[3],B[3],Amm,Bmm）;

return0;

}