集合的并交差运算数据结构课程设计.docx

集合的并交差运算 数据结构课程设计 #includelt;string.hgt;#includelt;stdio.hgt;#includelt;malloc.hgt;#includelt;stdlib.hgt;#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define INFEASIBLE -1#define OVERFLOW -2#define NULL 0#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef int Status;typedef char ElemType;typedef structElemType *elem; int length; int listsize;SqList;Status InitList(SqList amp;l)l.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!l.elem) exit(OVERFLOW);l.length=0;l.listsize=LIST_INIT_SIZE;return OK;int ListLength(SqList l)return(l.length);Status ListInsert_Sq(SqList amp;L,int i, ElemType e)/在顺序表L的第i个位置前插入元素e,i的合法值为1.L.length+1if(ilt;1|igt;L.length+1) return ERROR; if(L.lengthgt;=L.listsize) ElemType*newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase) exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCREMENT;ElemType *q=amp;L.elemi-1, *p=amp;L.elemL.length-1;while(pgt;=q) *(p+1)=*p; -p; /插入位置后的元素右移*q=e;+L.length;return OK;Status CreatSqList(SqList amp;l,ElemType a,int n)int len=ListLength(l);for(int i=0;ilt;n;i+)if(aigt;=#39;a#39;amp;amp;ailt;=#39;z#39;)ListInsert_Sq(l,+len,ai);return OK;Status GetElem(SqList L,int i,ElemType amp;e)if(ilt;=0|igt;L.length)return ERROR;elsee=*(L.elem+i-1);return OK;Status equal(ElemType e1,ElemType e2)if(e1=e2)return TRUE; else return FALSE; int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType,ElemType)ElemType *p=L.elem; /p指向第一个元素int i=1; /i始终为p所指向元素的位序while(ilt;=L.lengthamp;amp;!(*compare)(*p+,e)+i;if(ilt;=L.length) return(i);else return 0;Status ListDelete(SqList amp;L,int i,ElemType amp;e)/在顺序表中删除第个元素，用返回其值if(ilt;1|igt;L.length) return ERROR;/删除位置不合理ElemType *p=amp;L.elemi-1,*q=L.elem+L.length-1;e=*p;while(plt;q)*p=*(p+1); +p; /删除位置后的元素左移-L.length;return OK;void Union(SqList amp;La,SqList Lb)/将所有在线性表Lb中而不在La中的元素插入Laint la_len , lb_len;ElemType e;la_len=ListLength(La);lb_len=ListLength(Lb);for(int i=1;ilt;=lb_len;+i)GetElem(Lb,i,e);if(LocateElem_Sq(La,e,equal)=0)ListInsert_Sq(La,+la_len,e);Status JiaoJi(SqList l1,SqList l2, SqList amp;l3)int l1_len, l2_len,l3_len,i=1,j=1;ElemType e,u;l1_len=ListLength(l1);l2_len=ListLength(l2);l3_len=ListLength(l3);for(i=1;ilt;=l1_len;i+)GetElem(l1, i,e);for(j=l2_len;jgt;=1;j-)GetElem(l2,j,u);if(e=u)ListInsert_Sq(l3,+l3_len,u);break;elsecontinue;return OK;Status ChaJi(SqList amp;l1,SqList l2)SqList lc;int count=0,lc_len,l1_len,l2_len;ElemType e,u,f;InitList(lc);JiaoJi(l1,l2,lc);lc_len=ListLength(lc);l1_len=ListLength(l1);l2_len=ListLength(l2);for(int i=1;ilt;=lc_len;i+)GetElem(lc,i,e);for(int j=1;jlt;=l1_len;j+)GetElem(l1,j,u);if(u=e)ListDelete(l1,j,f);return OK;void Outputlist(SqList amp;L)if(0=L.length)printf(quot;空集!quot;);elsefor(int i=0;ilt;L.length;+i)printf(quot;%cquot;,*(L.elem+i);void main()system(quot;title 集合的并交叉运算quot;);for(1;)system(quot;color a1quot;);int c;printf(quot;*nquot;);printf(quot; # 执行程序: 1 # 退出程序: 2nquot;);printf(quot;*nquot;);printf(quot;请按键选择: quot;);scanf(quot;%dquot;,amp;c);getchar();printf(quot;nquot;);if(c=1)SqList l1,l2,l3,la;int n1,n2,i,j;char a130, a230;InitList(l1);InitList(l2);InitList(l3);InitList(la);printf(quot;请输入第一个集合: quot;);gets(a1);n1=strlen(a1);for(i=n1-1;igt;=0;i-) /从最后一个开始依次与前面的比较 重复赋值为0for(j=0;jlt;i;j+)if(a1j=a1i)a1i=0;CreatSqList(l1,a1,n1);la=l1;printf(quot;请输入第二个集合: quot;);gets(a2);n2=strlen(a2);for(i=n2-1;igt;=0;i-) /同上for(j=0;jlt;i;j+)if(a1j=a1i)a1i=0;CreatSqList(l2,a2,n2);printf(quot;集合的交集是: quot;);JiaoJi(l1,l2,l3);Outputlist(l3);printf(quot;nquot;);printf(quot;集合的并集是: quot;);Union(l1,l2)