大数据结构课程设计报告材料集合地交并差运算.doc

数据结构课程设计报告作 者:学 号：班 级:学 院:专业:题 目:年月1 课题描述编制一个能演示执行集合的交、并和差运算的程序。集合元素用小写英文字母，执行各种操作应以对话方式执行。利用单链表表示集合；理解好三种运算的含义2 系统设计1节点结构单元模块定义有序表的节点结构；typedef struct LNode/定义结构体类型指针 char data;struct LNode*next;*pointer;2有序表单元模块实现有序表的抽象数据类型；readdata(pointer head)初始条件：head是以head为头节点的空链表。操作结果：生成以head为头节点的非空链表。pop(pointer head)初始条件：head是以head为头节点的非空链表。操作结果：将以head为头节点的链表中数据逐个输出。3集合单元模块实现集合获得抽象数据类型；and(pointer head1,pointer head2,pointer head3)初始条件：链表head1、head2、head3已存在操作结果：生成一个由head1和head2的并集构成的集合head3。or(pointer head1,pointer head2,pointer head3)初始条件：链表head1、head2、head3已存在操作结果：生成一个由head1和head2的交集构成的集合head3。4主程序模块Void main初始化；do承受命令；处理命令；while“命令!=“退出；1顺序表结构单元模块定义顺序表的结构体；typedef struct /定义SeqList的结构体DataType listMaxSize;int size ; SeqList;2函数单元模块定义各种所需函数；int ListDel( SeqList *L , int i , DataType *x)/顺序表的删除函数int ListGet(SeqList L , int i , DataType *x)/获取顺序表的元素函数void ListFind(SeqList L , DataType x)/顺序表查找元素函数void SelcetSort(SeqList *L )/顺序表选择排序函数void UnionSet(SeqList mylist1 , SeqList mylist2)/求并集函数void MixedSet(SeqList mylist1 , SeqList mylist2)/求交集元素函数void DiffentSet(SeqList mylist1 , SeqList mylist2) /求差集元素函数3主函数单元模块定义主函数；void main() SeqList mylist1 , mylist2;/定义顺序表mylistint i;DataType temp;ListInitiate( &mylist1);ListInitiate( &mylist2);/初始化两个顺序表定义结构体类型指针，集合采用单链表存储。typedef struct LNode/定义结构体类型指针head1=(pointer)malloc(sizeof(struct LNode);head1->next=NULL;head2=(pointer)malloc(sizeof(struct LNode);head2->next=NULL;head3=(pointer)malloc(sizeof(struct LNode);typedef struct /定义SeqList的结构体 DataType listMaxSize;int size ;void UnionSet(SeqList mylist1 , SeqList mylist2) /求并集int m, i,j ;DataType x;SeqList Test;ListInitiate( &Test); /定义并初始化2.3.1基于单链表，顺序表设计 数据输入界面 主菜单界面 完毕 集合的差集运算 集合的交集运算 集合的并集运算图2.1系统模块流程图调用输入函数，输入集合信息 显示主菜单 承受用户选择是否合法否 是是否为4否 是 退出系统调用对应选项函数图2.2主菜单流程图 主菜单 用户选择序号是否合法 否 是是否为1 否 是调用并集函数和输出函数图2.3并集模块流程图求交集与差集的流程图与并集类似。3 详细设计3.1菜单设计基于单链表图3.1主界面3.2源代码设计基于单链表#include<stdio.h>#include<stdlib.h>typedef struct LNode/定义结构体类型指针char data;struct LNode*next;*pointer;void readdata(pointer head)/定义输入集合函数pointer p;char tmp;scanf("%c",&tmp);while(tmp!='n')p=(pointer)malloc(sizeof(struct LNode);/为指针P申请内存空间p->data=tmp;p->next=head->next;head->next=p;scanf("%c",&tmp);void pop(pointer head)/定义输出集合函数 pop()出栈函数pointer p;p=head->next;while(p!=NULL)printf("%c",p->data);p=p->next;printf("n");void and(pointer head1,pointer head2,pointer head3)/定义集合的并集函数pointer p1,p2,p3;p1=head1->next;while(p1!=NULL)/遍历链表head1 p3=(pointer)malloc(sizeof(struct LNode);p3->data=p1->data;p3->next=head3->next;head3->next=p3;p1=p1->next;p2=head2->next;while(p2!=NULL)/遍历链表head2p1=head1->next;while(p1!=NULL)&&(p1->data!=p2->data) p1=p1->next;if (p1=NULL)p3=(pointer)malloc(sizeof(struct LNode);p3->data=p2->data;p3->next=head3->next;head3->next=p3;p2=p2->next;void or(pointer head1,pointer head2,pointer head3)/定义集合的交集函数pointer p1,p2,p3;p1=head1->next;while(p1!=NULL)p2=head2->next;while(p2!=NULL)&&(p2->data!=p1->data)p2=p2->next;if(p2!=NULL)&&(p2->data=p1->data)p3=(pointer)malloc(sizeof(struct LNode);p3->data=p1->data;p3->next=head3->next;head3->next=p3;p1=p1->next;void differ(pointer head1,pointer head2,pointer head3)/定义集合的差集函数pointer p1,p2,p3;p1=head1->next;while(p1!=NULL)p2=head2->next;while(p2!=NULL)&&(p2->data!=p1->data)p2=p2->next;if(p2=NULL)p3=(pointer)malloc(sizeof(struct LNode);p3->data=p1->data;p3->next=head3->next;head3->next=p3;p1=p1->next;void main()/主函数int x; printf("(输入数据,按回车键完毕,第一个集合大于第二个集合)n");pointer head1,head2,head3;head1=(pointer)malloc(sizeof(struct LNode);head1->next=NULL;head2=(pointer)malloc(sizeof(struct LNode);head2->next=NULL;head3=(pointer)malloc(sizeof(struct LNode);head3->next=NULL;printf("请输入集合1：n");readdata(head1);/调用输入集合函数printf("请输入集合2：n");readdata(head2);/调用输入集合函数A:printf("1.并集 2.交集 3.差集 4.完毕 x.重新运算n"); doprintf("请选择序号n");scanf("%d",&x);switch(x)case 1:printf("两集合的并是n");and(head1,head2,head3);/调用并集函数pop(head3);head3->next=NULL;break;case 2:printf("两集合的交是n");or(head1,head2,head3);/调用交集函数pop(head3);head3->next=NULL;break;case 3: printf("两集合的差是n");differ(head1,head2,head3);/调用差集函数pop(head3);head3->next=NULL;break; case 4:break;default:goto A;while(x!=4);3.3菜单设计基于顺序表图3.2主界面3.4源代码设计基于顺序表#include <stdio.h>#include <stdlib.h>#include <string.h>#define MaxSize 100# define EQUAL "="typedef char DataType;typedef struct /定义SeqList的结构体DataType listMaxSize; int size ; SeqList; void ListInitiate( SeqList *L) /初始化操作L->size = 0;int ListLength( SeqList L) /获取长度return L.size;int ListInsert( SeqList *L , int i , DataType x) /插入函数的参数分别是SeqList类型的变量，插入位置I，和插入的元素Xint j; if( L->size >= MaxSize)printf("顺序表已满，无法插入其他元素！n");return 0;system("pause"); else if( i<0 && i>L->size ) printf("参数i不合法！n"); return 0; system("pause"); else for( j=L->size ; j>i ; j-) L->listj = L->listj-1; /将i至size中间的元素依次后移一个单位 L->listi = x; /将x插入指定的位置i L->size +; /L的size，与长度加一 return 1; int ListDel( SeqList *L , int i , DataType *x) /顺序表的删除函数int j;if( L->size <= 0)printf("顺序表已无数据可删！n");return 0;system("pause"); else if( i<0 && i>L->size-1 ) printf("参数i不合法！n"); return 0; system("pause"); else *x = L->listi; /保存删除的元素到x中 for( j=i+1 ; j<= L->size-1 ; j+) L->listj-1 = L->listj; /将i+1至size中间的元素依次前移一个单位 L->size -; /L的size，与长度加一 return 1; int ListGet(SeqList L , int i , DataType *x) /获取顺序表的元素函数if( i<0 | i>L.size-1 ) printf("参数i不合法！n"); return 0; else *x = L.listi; return 1; void ListFind(SeqList L , DataType x) /顺序表查找元素函数int i; for(i=0 ; i<L.size; i+) if(L.listi = x) printf("与查找元素一样的位置为：%d n" , i+1 ); continue; if( i = L.size-1 ) printf("没有找到与所查询一样的元素！n");void SelcetSort(SeqList *L ) /顺序表选择排序函数int i,j;DataType temp;int length = ListLength( *L);for(i=0; i< length-1; i+)temp = L->listi+1;j=i;while(j > -1 && temp < L->listj)L->listj+1 = L->listj;j-;L->listj+1 = temp;void UnionSet(SeqList mylist1 , SeqList mylist2) /求并集int m, i,j ;DataType x;SeqList Test;ListInitiate( &Test); /定义并初始化for(m=0 ; m <ListLength(mylist1) ; m+) ListGet(mylist1 , m , &x);ListInsert( &Test , m , x ); /先将顺序表一中的元素放入顺序表中 for(i=0 ; i< ListLength(mylist2) ; i+) ListGet(mylist2 , i , &x);ListInsert( &Test , m , x ); /再将顺序表二中的元素放入顺序表中m+; for(i=0 ; i <ListLength(Test) ; i+) /求并集for(j = i+1 ; j<ListLength(Test); j+) /将顺序表中的一样的元素删除if(Test.listi = Test.listj )ListDel( &Test , j , &x);SelcetSort(&Test);printf(" The elements of the Union Set are : ");for(i=0 ; i <ListLength(Test) ; i+) ListGet(Test , i , &x); printf("%c" , x); printf("n");void MixedSet(SeqList mylist1 , SeqList mylist2) /求交集元素函数int m, i,j ;DataType x;SeqList mylist;ListInitiate( &mylist); /定义并初始化SeqList Test;ListInitiate( &Test); m=0;for(i=0 ; i <ListLength(mylist1) ; i+) /求交集for(j = 0 ; j<ListLength(mylist2); j+)if(mylist1.listi = mylist2.listj )ListInsert( &Test , m , mylist1.listi ); /将一样的元素放在Test顺序表中m+;continue;for(i=0 ; i <ListLength(Test) ; i+) /求并集for(j = i+1 ; j<ListLength(Test); j+) /将顺序表中的一样的元素删除if(Test.listi = Test.listj )ListDel( &Test , j , &x);SelcetSort(&Test); /对顺序表进展有序化printf(" The elements of the Mixed Set are : ");for(i=0 ; i <Test.size ; i+) ListGet(Test , i , &x); printf("%c" , x); printf("n");void DiffentSet(SeqList mylist1 , SeqList mylist2) /求差集元素函数int m=0,n, i,j ;DataType x;SeqList Test;ListInitiate( &Test); for(i=0 ; i <ListLength(mylist1) ; i+) n=0;for(j = 0 ; j<ListLength(mylist2); j+)if(mylist1.listi = mylist2.listj )n+;if(n = 0)ListInsert( &Test , m , mylist1.listi ); /将一样的元素放在Test顺序表中m+;for(i=0 ; i <ListLength(Test) ; i+) /求并集for(j = i+1 ; j<ListLength(Test); j+) /将顺序表中的一样的元素除if(Test.listi = Test.listj )ListDel( &Test , j , &x);SelcetSort(&Test); printf(" The elements of the Diffrent Set are : ");for(i=0 ; i <ListLength(Test) ; i+) ListGet(Test , i , &x); printf("%c" , x); printf("n");void main()SeqList mylist1 , mylist2; /定义顺序表mylist int i;DataType temp;ListInitiate( &mylist1);ListInitiate( &mylist2); /初始化两个顺序表printf("n%s%sn", EQUAL , EQUAL);printf("n Wele to the Program of Collection ! n" );printf("n%s%sn", EQUAL , EQUAL);printf("n 请输入两个集合 ! n");printf("n 请输入集合1！: ");i = 0; while( (temp=getchar() ) != 'n')if(96<temp && temp<123)ListInsert( &mylist1 , i , temp); /顺序表一赋值temp;i+;printf("n 输入集合2！: ");i = 0; while( (temp=getchar() ) != 'n')if(96<temp && temp<123)ListInsert( &mylist2 , i , temp); /顺序表一赋值temp;i+;printf("n collection one: " );for(i=0; i<mylist1.size; i+)printf("%c" , mylist1.listi);printf("nn");printf(" collection two: ");for(i=0; i<mylist2.size; i+)printf("%c" , mylist2.listi);printf("nn");/调用各个函数printf("n请选择功能:!n");printf("n%s%sn", EQUAL , EQUAL);printf(" The number 1 is : 并集.n");printf(" The number 2 is : 交集.n");printf(" The number 3 is : 差集.n");printf("%s%sn", EQUAL , EQUAL);while(1)int choice;printf("n 请输入您的选择！： n (others exit the programe!): ");scanf("%d" , &choice);switch(choice)case 1 : UnionSet( mylist1 , mylist2); break;case 2 : MixedSet(mylist1 , mylist2); break;case 3 : DiffentSet(mylist1 , mylist2); break;default : exit(0);4 测试4.1最终结果基于单链表图4.1结果展示4.2最终结果基于顺序表图4.2结果展示结 论通过本次数据结构课程设计，课题实现集合的交并差运算用单链表和顺序表都可以实现，在整个程序方面设计两种方法思路大体一样，唯一不同的在于用单链表比拟结果时候得到一个符合结果元素的就放入结果链表中。而顺序表实现结果时候是对结果顺序表按照三种运算法如此对表进展删除操作得到最终结果。参 考 文 献1 吉根林. 数据结构C+语言描述.高等教育，20142 谭浩强. C程序设计学习辅导.：清华大学，20103 赵建洋，于长辉等. C+程序设计工程化。某某大学，20104 李根强. 数据结构C+版.2版.：中国水利水电，2009