10.4.1 含并、交和查运算的集合类型.doc

《10.4.1 含并、交和查运算的集合类型.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、10．4．1含并、交和查运算的集合类型由于集合的操作仅限于求并、交、差，因此在这个示例中仍以有序表表示集合，但进一步将集合本身设计成抽象数据类型，以便以后可以在集合类型的操作基础上，构造高一层次的算法，以便完成更复杂的应用。一、文体描述1．题目内容：利用有序链表表示正整数集合，实现集合的交、并和差运算。2．基本要求：由用户输入两组整数分别作为两个集合的元素，由程序计算它们的交、并和差集，并将运算结果输出。3．测试数据：S1={3，5，6，7，12，27，35}S2={5，8，10，12，27，31，42，51，55，63}运行结果应为

2、：S1∪S2={3，5，6，8，9，10，12，27，31，35，42，51，55，63}S1∩S2={5，12，27}S1-S2={3，6，9}二、需求分析1．本程序用以求出任意两个正整数集合的交、并和差集。2．程序运行后显示提示信息，由用户输入两组整数。程序将自动滤去输入的重复整数及负数。3．用户输入数据完毕，程序将输出运算结果。4．测试数据应为两组正整数，范围最好在0~35000之间。三、概要设计为实现上述程序功能，应以有序链表表示集合。为此需要有序表和集合两个抽象数据类型。1．有序表的抽象数据类型定义为：ADTOrderedL

3、ist{数据对象：D={ai

4、ai∈ElemType，i=1，2，…，n，n≥0}数据关系：R1={

5、ai-1，ai∈D,ai-1

6、件：有序表L已存在，并且1≤i≤ListLength(L)。操作结果：返回L中第i个数据元素。LocatePos(L,e)初始条件：有序表L已存在，e和有序表中元素同类型的值。操作结果：若L中存在和e相同的元素，则返回位置；否则返回0。InsertElem(&L,e)初始条件：有序表L已存在。操作结果：在L中，按有序关系插入值和e相同的数据元素。DeleteElem(&L,i)初始条件：有序表L已存在。操作结果：删除L中第i个数据元素。ListTraverse(L,visit())初始条件：有序表L已存在。操作结果：依次对L的每个数据

7、元素调用函数visit()。一旦visit()失败，则操作失败。}ADTOrderedList2．集合的抽象数据类型定义为：ADTSet{数据对象：D={ai

8、ai∈ElemSet且ai互不相同，i=1，2，…，n，n≥0}数据关系：R1={}基本操作：CrtNullSet(&T)操作结果：构造一个空集合T。DestroySet(&T)初始条件：集合T已存在。操作结果：销毁集合T。AddElem(&T,e)初始条件：集合T已存在。操作结果：如果集合T中不含和e相同的元素，则添加元素e，否则空操作。DelElem(&T,e)初始条件：集

9、合T已存在。操作结果：如果集合T存在元素e，则从集合T中删除该元素e，否则空操作。Union(&T,S1,S2)初始条件：集合S1和S2已存在。操作结果：生成一个由S1和S2的并集构成的集合T。Intersection(&T,S1,S2)初始条件：集合S1和S2已存在。操作结果：生成一个由S1和S2的交集构成的集合T。Difference(&T,S1,S2)初始条件：集合S1和S2已存在。操作结果：生成一个由S1和S2的差集构成的集合T。PrintSet(T)初始条件：集合T已存在。操作结果：输出集合T中全部元素。}ADTSet3．本

10、程序包含三个模块主程序模块；集合单元模块（实现际和的抽象数据类型）；有序表单元模块（实现有序表的抽象数据类型，包含结点和指针的定义）；只见的调用关系如图10.2所示。图10.2四、详细设计1．元素类型、结点类型和指针类型。typedefintElemType;//元素类型typedefstructNodeType{ElemTypedata;NodeType*next;}NodeType,*LinkType;//结点类型和指针类型2．由序表类型typedefstruct{LinkTypehead,tail;//分别指向有序链表的头结点和

11、尾结点intsize;//链表当前的长度intcurpos;//当前被操作的元素在有序表中的位置LinkTypecurrent;//当前指针，指向链表中第curpos个元素}OrderedList;//有序链表类型部分基