jihe.zip_visual c

#include<stdio.h> #include<stdlib.h> #include<string.h> #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 struct{ char *elem; int length; int listsize; }SqList; //结点类型 指针类型 int InitList(SqList &l) //初始化顺序表 { l.elem=(char*)malloc(LIST_INIT_SIZE*sizeof(char)); if(!l.elem) exit(OVERFLOW); //内存分配失败 l.length=0; l.listsize=LIST_INIT_SIZE; //链表长为顺序表的初始大小 return OK; } int ListLength(SqList l) //求顺序表的长度 { return(l.length); } int ListInsert_Sq(SqList &L,int i,char e) { //在顺序表L的第i个位置前插入元素e,i的合法值为1..L.length+1 if(i<1||i>L.length+1) //插入位置非法，返回错误 return ERROR; if(L.length>=L.listsize) { char* newbase=(char *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(char)); if(!newbase) exit(OVERFLOW); L.elem=newbase; //新基址 L.listsize+=LISTINCREMENT; } char *q=&L.elem[i-1], *p=&L.elem[L.length-1]; while(p>=q) { *(p+1)=*p; --p; } //插入位置后的元素右移 *q=e; ++L.length; return OK; } int CreatSqList(SqList &l,char a[],int n) { //创建顺序表 int len=ListLength(l); for(int i=0;i<n;i++) { if(a[i]>='a'&&a[i]<='z') ListInsert_Sq(l,++len,a[i]); } return OK; } int GetElem(SqList L,int i,char &e) { // 返回顺序表中元素 if(i<=0||i>L.length) return ERROR; else e=*(L.elem+i-1); return OK; } int equal(char e1,char e2) { if(e1==e2) return TRUE; else return FALSE; } int LocateElem_Sq(SqList L, char e, int(*compare)(char,char)) { char *p=L.elem; //p指向第一个元素 int i=1; //i始终为p所指向元素的位序 while(i<=L.length&&!(*compare)(*p++,e)) ++i; if(i<=L.length) return(i); else return 0; } int ListDelete(SqList &L,int i,char &e) { //在顺序表Ｌ中删除第ｉ个元素，用ｅ返回其值． if(i<1||i>L.length) return ERROR; //删除位置不合理 char *p=&L.elem[i-1],*q=L.elem+L.length-1; e=*p; while(p<q){*p=*(p+1); ++p;} //删除位置后的元素左移 --L.length; return OK; } void Union(SqList &La,SqList Lb) { //求集合的并集 //将所有在线性表Lb中而不在La中的元素插入La int la_len , lb_len; char e; la_len=ListLength(La); //求顺序表的长度 lb_len=ListLength(Lb); for(int i=1;i<=lb_len;++i) { GetElem(Lb,i,e); //取得顺序表lb的第i个位置处得元素，将值赋给e if(LocateElem_Sq(La,e,equal)==0) //判断顺序表la中是否有元素e ListInsert_Sq(La,++la_len,e); //若没有则将e插入到la中 } } int JiaoJi(SqList l1,SqList l2, SqList &l3) { //求集合的交集 int l1_len, l2_len,l3_len,i=1,j=1; char e,u; l1_len=ListLength(l1); //取得顺序表l1中第i个元素，赋值给e l2_len=ListLength(l2); l3_len=ListLength(l3); for(i=1;i<=l1_len;i++) { GetElem(l1,i,e); //取得顺序表l1中第i个元素，赋值给e for(j=l2_len;j>=1;j--) { GetElem(l2,j,u); //取得顺序表l2中第j个元素，赋值给u if(e==u) //判断e、u是否相等 { ListInsert_Sq(l3,++l3_len,u); //如果相等，就将该元素插入到顺序表l3中 break; } else continue; } } return OK; } int ChaJi(SqList &l1,SqList l2) { //求顺序表的差集 SqList lc; int count=0,lc_len,l1_len,l2_len; char 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;i<=lc_len;i++) { GetElem(lc,i,e); for(int j=1;j<=l1_len;j++) { GetElem(l1,j,u); if(u==e) { ListDelete(l1,j,f); } } } return OK; } void Outputlist(SqList &L) { if(0==L.length) printf("空集!"); else for(int i=0;i<L.length;++i) { printf("%c",*(L.elem+i)); } } //程序的主函数 void main() { printf("集合的并交叉运算\n"); SqList l1,l2,l3,la; //定义顺序表 int n1,n2,i,j; char a1[30], a2[30]; InitList(l1); //初始化顺序表 InitList(l2); InitList(l3); InitList(la); printf("请输入第一个集合: "); gets(a1); //接收第一个字符串 n1=strlen(a1); for(i=n1-1;i>=0;i--) //从最后一个开始依次与前面的比较 重复赋值为0 { for(j=0;j<i;j++) { if(a1[j]==a1[i]) a1[i]=0; } } CreatSqList(l1,a1,n1); la=l1; printf("请输入第二个集合: "); gets(a2); n2=strlen(a2); for(i=n2-1;i>=0;i--) //同上 { for(j=0;j<i;j++) { if(a1[j]==a1[i]) a1[i]=0; } } CreatSqList(l2,a2,n2); printf("集合的交集是: "); JiaoJi(l1,l2,l3); Outputlist(l3); printf("\n"); printf("集合的并集是: "); Union(l1,l2); Outputlist(l1); printf("\n"); printf("集合的差集是: "); ChaJi(la,l2); Outputlist(la); printf("\n"); }