《数据结构课程设计----集合的并、交和差运算.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计----集合的并、交和差运算.doc（15页珍藏版）》请在金锄头文库上搜索。
1、实习报告题目：编制一个演示集合的并、交和差运算的程序班级： 95001 姓名 张三 学号：9500101完成日期： 2008-6-16一、需求分析1. 本程序中，集合的元素限定为小写字母字符 a.z，集合的大小n27。集合输入的形式为一个以回车符为结束标志的字符串，串中字符顺序不限，且允许出现重复字符或非法字符，程序应能自动滤去。输出的运算结果字符串中将不含重复字符或非法字符。2. 演示程序以用户与计算机交互方式执行，即在计算机终端上显示提示信息之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据(滤去输入中的非法字符)和运算结果显示在其后。3. 程序执行的命令包括：(1) 1cr
2、eate set 1 /构造集合1；(2) 2create set2 /构造集合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=error data，Setl Set2=deinoprt，Setl set2=aeort，Setl-Set2=inp二、概要设计为实现上述程序功能，应以有序链表表示集合。为此，
3、需要两个抽象数据类型：有序表和集合。1. 有序表的抽象数据类型定义为：ADT OrderedList数据对象：D=ai|aiCharSet，i=1,2,.,n, n 0数据关系：Rl=|ai-1,aiD,ai-1data=e;p-next =NULL;return TRUE;void FreeNode(LinkType &p)/* 释放 p 所指结点*/LinkType Copy(LinkType p)/*复制生成和指针 p 所指结点有同值元素的新结点并返回,若分配空间失败,则返回空指针。新结点的指针域为NULL */s=(LinkType)malloc(sizeof(NodeType)if(
4、!s) return NULL;s-data=p-data;s-next =NULL;return s;ElemType Elem(LinkType p)/*若指针p!=NULL,则返回p所指结点的数据元素,否则返回#*/LinkType SuccNode(LinkType p)/*若指针p!=NULL,则返回指向p所指结点的后继元素的指针,否则返回NULL*/2. 根据有序表的基本操作的特点，有序表采用有序链表实现。链表设头、尾两个指针和表长数据域，并附设头结点，头结点的数据域没有实在意义。typedef struetLinkType head,tail; /*分别指向线性链表的头结点和尾结
5、点*/Int size; /*指示链表当前的长度*/OrderedList; /*序链表类型*/ 有序链表的基本操作定义如下：bool InitList(OrderedList &L);/构造一个带头结点的空的有序链表L,并返回TRUE;/若分配空间失败,则令L.head为NULL,并返回FALSE;void DestroyList(OrderedList &L);/ 扩销毁有序链表 Lbool ListEmpty(OrderedList L);/ 若L不存在或为空表，则返回TRUE，否则返回FALSEint ListLength(OrderedList L);/ 返回链表的长度LinkTyp
6、e GetElemPos(OrderedList L，tnt pos);/ 若L存在且0posL.size+1，则返回指向第pos个元素的指针，否则返回 NULLbool LocateElem(OrderedList L ,ElemType e ,LinkType &q);/若有序链表L存在且表中存在元素e,则q指示L中第一个值为 e的结点的位置，并返回TRUE；否则q指示第一个大于e的元素的前驱的位置，并返回FALSEvoid Append(OrderedList &L, LinkType s);/在已存在的有序链表L的末尾插入指针s所指结点void InsertAfter(OrderLis
7、t &L, LinkType q, LinkType s);/已存在的有序链表L中q所指示的结点之后插入指针s所指结点void ListTraverse(LinkType p,status(* visit)(LinkType q);/从p(p!=NULL)指示的结点开始，依次对每个结点调用函数visit其中部分操作的伪码算法如下:bool InitiList(OrderedList &L)if(MakeNode(head,) /头结点的虚设元素为空格符L.tail =L.head; L.size =0; return TRUE;else L.head =NULL ;return FALSE ;
8、/InitList void DestroyList(OrderedList &L)p=L.head;while(p)q=p; p=SuccNode(p); FreeNode(q);L.head =L.tail =NULL ;/DestroyListLinkType GetElemPos(OrderedList L, int pos)if(!L.head|posL.size) return NULL;else if(pos=L.size) return L.tail;elsep=L.head-next;k=1;while(p&knext;/pre指向*p的前驱,p指向第一个元素结点white(
9、 p&P-datadata=e) return TRUE;elsep=pre; return FALSE;else return FALSE;/LocateElemvoid Append(OrderedList &L, LinkType s)if(L.head &s)if(L.tail!=L.head) L.tail-next =s;else L.head-next=s;L.tail =s; L.size+; /Appendvoid InsertAfter(OrderList &L,LinkType q,LinkType s)if(L.head&q&s)s-next=q-next; q-next =s;if(L.tail =q) L.tail =s;L.size+;/InsertAfter
