欢迎来到天天文库
浏览记录
ID:25647536
大小:409.50 KB
页数:16页
时间:2018-11-21
《数据结构课程设计--编制一个演示集合的并、交和差运算的程序》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、数据结构课程设计说明书课题:编制一个演示集合的并、交和差运算的程序班级:11软件二姓名:张三学号:时间:2013.1.7-2013.1.11计算机信息工程学院一、需求分析1.本程序中,集合的元素限定为小写字母字符['a'..'z'],集合的大小n<27。集合输入的形式为一个以"回车符"为结束标志的字符串,串中字符顺序不限,且允许出现重复字符或非法字符,程序应能自动滤去。输出的运算结果字符串中将不含重复字符或非法字符。2.演示程序以用户与计算机交互方式执行,即在计算机终端上显示"提示信息"之后,由用户在
2、键盘上输入演示程序中规定的运算命令;相应的输入数据(滤去输入中的非法字符)和运算结果显示在其后。3.程序执行的命令包括:(1)构造集合1;(2)构造集合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",Se
3、t2="errordata",SetlÈSet2="deinoprt",SetlÇset2="aeort",Setl-Set2="inp"二、概要设计为实现上述程序功能,应以有序链表表示集合。为此,需要两个抽象数据类型:有序表和集合。1.有序表的抽象数据类型定义为:ADTOrderedList{数据对象:D={ai
4、aiÎCharSet,i=1,2,...,n,n³0}数据关系:Rl={
5、ai-1,aiÎD,ai-16、果:构造一个空的有序表L。DestroyList(&L)初始条件:有序表L已存在。15操作结果:销毁有序表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已存在。操作结果:7、若有序表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指示的元素开始的每个8、元素调用函数visit()。}ADTOrderedList2.集合的抽象数据类型定义为:ADTSet{数据对象:D={ai9、ai为小写英文字母且互不相同,i=l,2,...,n,0£n£26}数据关系:R1={}基本操作:Createset(&T,Str)15初始条件:Str为字符串。操作结果:生成一个由Str中小写字母构成的集合T。Destroyset(&T)初始条件:集合T已存在。操作结果:销毁集合T的结构。Union(&T,SLS2)初始条件:集合S1和S2存在。操作结果:生成一个由Sl和S2的10、并集构成的集合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)集合单元11、模块实现集合的抽象数据类型;3)有序表单元模块实现有序表的抽象数据类型;4)结点结构单元模块定义有序表的结点结构。各模块之间的调用关系如下:15三、详细设计1.元素类型、结点类型和指针类型typedefcharElemType;/*元素类型*/typedefstructNodeType{ElemTypedata;NodeType*next;}NodeType,LinkType;/*结点类型,指针类型*/statusMakeNode(LinkType&p,
6、果:构造一个空的有序表L。DestroyList(&L)初始条件:有序表L已存在。15操作结果:销毁有序表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已存在。操作结果:
7、若有序表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指示的元素开始的每个
8、元素调用函数visit()。}ADTOrderedList2.集合的抽象数据类型定义为:ADTSet{数据对象:D={ai
9、ai为小写英文字母且互不相同,i=l,2,...,n,0£n£26}数据关系:R1={}基本操作:Createset(&T,Str)15初始条件:Str为字符串。操作结果:生成一个由Str中小写字母构成的集合T。Destroyset(&T)初始条件:集合T已存在。操作结果:销毁集合T的结构。Union(&T,SLS2)初始条件:集合S1和S2存在。操作结果:生成一个由Sl和S2的
10、并集构成的集合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)集合单元
11、模块实现集合的抽象数据类型;3)有序表单元模块实现有序表的抽象数据类型;4)结点结构单元模块定义有序表的结点结构。各模块之间的调用关系如下:15三、详细设计1.元素类型、结点类型和指针类型typedefcharElemType;/*元素类型*/typedefstructNodeType{ElemTypedata;NodeType*next;}NodeType,LinkType;/*结点类型,指针类型*/statusMakeNode(LinkType&p,
此文档下载收益归作者所有