数据结构课程设计----集合的并、交和差运算

实习报告题目：编制一个演示集合的并、交和差运算的程序班级：95001姓名张三学号：9500101完成日期：2008-6-16一、需求分析1.本程序中，集合的元素限定为小写字母字符['a'..'z']，集合的大小n27。集合输入的形式为一个以回车符为结束标志的字符串，串中字符顺序不限，且允许出现重复字符或非法字符，程序应能自动滤去。输出的运算结果字符串中将不含重复字符或非法字符。2.演示程序以用户与计算机交互方式执行，即在计算机终端上显示提示信息之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据(滤去输入中的非法字符)和运算结果显示在其后。3.程序执行的命令包括：(1)[1]—createset1//构造集合1；(2)2—crea[t]eset2//构造集合2；(3)求并集；(4)求交集；(5)求差集；(6)结束。构造集合1和构造集合2时，需以字符串的形式键入集合元素。4.测试数据(1)Setl=magazine，Set2=paper，SetlSet2=egimnprz，SetlSet2=ae，Setl-Set2=gimnz(2)Setl=0120per4a6tion89，Set2=errordata，SetlSet2=deinoprt，Setlset2=aeort，Setl-Set2=inp二、概要设计为实现上述程序功能，应以有序链表表示集合。为此，需要两个抽象数据类型：有序表和集合。1.有序表的抽象数据类型定义为：ADTOrderedList{数据对象：D={ai|aiCharSet，i=1,2,...,n,n0}数据关系：Rl={ai-1,ai|ai-1,aiD,ai-1ai,i=2,...,n}基本操作：InitList(&L)操作结果：构造一个空的有序表L。DestroyList(&L)初始条件：有序表L已存在。操作结果：销毁有序表L。ListLength(L)初始条件：有序表L已存在。操作结果：返回有序表L的长度。ListEmpty(L)初始条件：有序表L已存在。操作结果：若有序表L为空表，则返回True，否则返回False。GetElem(L,pos)初始条件：有序表L已存在。操作结果：若1posLength(L)，则返回表中第pos个数据元素。LocateElem(L,e,&q)初始条件：有序表L已存在。操作结果：若有序表L中存在元素e，则q指示L中第一个值为e的元素的位置，并返回函数值TRUE，否则q指示第一个大于e的元素的前驱的位置,并返回函数值FALSE。Append(&L,e)初始条件：有序表L已存在。操作结果：在有序表L的未尾插入元素e。InsertAfter(&L,q,e)初始条件：有序表L已存在，q指示L中一个元素。操作结果：在有序表L中q指示的元素之后插入元素e。ListTraverse(q,visit())初始条件：有序表L已存在，q指示L中一个元素。操作结果：依次对L中q指示的元素开始的每个元素调用函数visit()。}ADTOrderedList2.集合的抽象数据类型定义为：ADTSet{数据对象：D={ai|ai为小写英文字母且互不相同，i=l,2,...,n,0n26}数据关系：R1={}基本操作：Createset(&T,Str)初始条件：Str为字符串。操作结果：生成一个由Str中小写字母构成的集合T。Destroyset(&T)初始条件：集合T已存在。操作结果：销毁集合T的结构。Union(&T,SLS2)初始条件：集合S1和S2存在。操作结果：生成一个由Sl和S2的并集构成的集合T。Intersection(&T,SLS2)初始条件：集合Sl和S2存在。操作结果：生成一个由Sl和S2的交集构成的集合T。Difference(&T,S1,S2)初始条件：集合S1和S2存在。操作结果：生成一个由S1和S2的差集构成的集合T。Printset(T)初始条件：集合T已存在。操作结果：按字母次序顺序显示集合T的全部元素。}ADTSet3.本程序包含四个模块1)主程序模块voidmain(){初始化：do{接受命令；处理命令；}while(命令!=退出)2)集合单元模块实现集合的抽象数据类型；3)有序表单元模块实现有序表的抽象数据类型；4)结点结构单元模块定义有序表的结点结构。各模块之间的调用关系如下：三、详细设计1.元素类型、结点类型和指针类型typedefcharElemType;/*元素类型*/typedefstructNodeType{ElemTypedata;NodeType*next;}NodeType,LinkType;/*结点类型,指针类型*/statusMakeNode(LinkType&p,ElemTypee){/*分配由p指向的数据元素为e、后继为空的结点,并返回TRUE,扩若分配失败,则返回FALSE*/p=(LinkType)malloc(sizeof(NodeType);if(!p)returnFALSE;p-data=e;p-next=NULL;returnTRUE;}voidFreeNode(LinkType&p){/*释放p所指结点*/}LinkTypeCopy(LinkTypep){/*复制生成和指针p所指结点有同值元素的新结点并返回,若分配空间失败,则返回空指针。新结点的指针域为NULL*/s=(LinkType)malloc(sizeof(NodeType))if(!s)returnNULL;s-data=p-data;s-next=NULL;returns;}ElemTypeElem(LinkTypep){/*若指针p!=NULL,则返回p所指结点的数据元素,否则返回'#'*/}LinkTypeSuccNode(LinkTypep){/*若指针p!=NULL,则返回指向p所指结点的后继元素的指针,否则返回NULL*/}2.根据有序表的基本操作的特点，有序表采用有序链表实现。链表设头、尾两个指针和表长数据域，并附设头结点，头结点的数据域没有实在意义。typedefstruet{LinkTypehead,tail;/*分别指向线性链表的头结点和尾结点*/Intsize;/*指示链表当前的长度*/}OrderedList;/*序链表类型*/有序链表的基本操作定义如下：boolInitList(OrderedList&L);//构造一个带头结点的空的有序链表L,并返回TRUE;//若分配空间失败,则令L.head为NULL,并返回FALSE;voidDestroyList(OrderedList&L);//扩销毁有序链表LboolListEmpty(OrderedListL);//若L不存在或为空表，则返回TRUE，否则返回FALSEintListLength(OrderedListL);//返回链表的长度LinkTypeGetElemPos(OrderedListL，tntpos);//若L存在且0posL.size+1，则返回指向第pos个元素的指针，否则返回NULLboolLocateElem(OrderedListL,ElemTypee,LinkType&q);//若有序链表L存在且表中存在元素e,则q指示L中第一个值为e的结点的位置，并返回TRUE；否则q指示第一个大于e的元素的前驱的位置，并返回FALSEvoidAppend(OrderedList&L,LinkTypes);//在已存在的有序链表L的末尾插入指针s所指结点voidInsertAfter(OrderList&L,LinkTypeq,LinkTypes);//已存在的有序链表L中q所指示的结点之后插入指针s所指结点voidListTraverse(LinkTypep,status(*visit)(LinkTypeq));//从p(p!=NULL)指示的结点开始，依次对每个结点调用函数visit其中部分操作的伪码算法如下:boolInitiList(OrderedList&L){if(MakeNode(head,)){//头结点的虚设元素为空格符L.tail=L.head;L.size=0;returnTRUE;}else{L.head=NULL;returnFALSE;}}//InitListvoidDestroyList(OrderedList&L){p=L.head;while(p){q=p;p=SuccNode(p);FreeNode(q);}L.head=L.tail=NULL;}//DestroyListLinkTypeGetElemPos(OrderedListL,intpos){if(!L.head||pos1||posL.size)returnNULL;elseif(pos==L.size)returnL.tail;else{p=L.head-next;k=1;while(p&&kpos){p=SuccNode(p);k++;}returnp;}}//GetElemPos;statusLocateElem(OrderedListL,ElemTypee,LinkType&p){if(L.head){pre=L.head;p=pre-next;//pre指向*p的前驱,p指向第一个元素结点white(p&&P-datae){pre=p;p=SuccNode(p);}if(p&&p-data==e)returnTRUE;else{p=pre;returnFALSE;}}elsereturnFALSE;}//LocateElemvoidAppend(OrderedList&L,LinkTypes){if(L.head&&s){if(L.tail!=L.head)L.tail-next=s;elseL.head-next=s;L.tail=s;L.size++;}}//AppendvoidInsertAfter(OrderList&L,LinkTypeq,LinkTypes){if(L.head&&q&&s){s-next=q-next;q-next=s;if(L.tail==q)L.tail=s;L.size++;}}//InsertAftervoidListTraverse(LinkTypep,status(*visit)(LinkTypeq)){while(p){visit(p);p=SuccNode(p);}}//ListTraverse3.集合Set利用有序链表类型OrderedList来实现,定义为有序集OrderedSet;typedefOrderedListOrderedSet;集合类型的基本操作的类C伪码描述如下:voidCreateset(OderedSet&T,char*s){//生成由串s中小写字母构成的集合T,IsLower是小写字母判别函数if(InitList(T);//构造空集Tfor(i=l;i=length(s);i++)if(islower(s[I])&&!LocateElem(T,s[I],p))//过滤重复元素并按字母次序大小插入if(MakeNode(q,s[i]))InsertAfter(T,p,q);}//CreatesetvoidDestroyset(OrderedSet&T){//销毁集合T的结构DestroyList(T);}//DestroyListvoidUnion(OrderedSet&T,OrderedSetS1,OrderedSetS2){//求已建成的集合Sl和S2的并集T,即:S1.head!=NULL且S2.head!=NULLif(InitList(T){pl=GetEiemPos(Sl,1);p2=GetElemPos(S2,l);while(pl&&p2){cl=Elem(pl);c2=Elem(p2);if(cl=c2){Append(T,Copy(pl);pl=SuccNode(pl);if(c