单链表的交并差-数据结构课程设计|数据结构课程设计#include
#include #include #define null 0#define M 100/*定义链表*/typedef int ElemType;typedef struct Lnode{ ElemType data; struct Lnode *next;};/*返回链表长度*/int lenth(struct Lnode **L){ int n=0; struct Lnode *t; t=*L; while(t!=null) { n++; t=t->next; } return n;}/*返回指定节点的值*/ElemType get(struct Lnode **L,int n){ int i=1; struct Lnode *t; t=*L;while (inext; i++; } if(t!=null) { return(t->data); } else { printf("The %dth Lnode haven't find !\n",n); }}/*定位指定值的节点的位置*/int locate(struct Lnode **L,ElemType x ){ int n=1; struct Lnode *t; t=*L;while (t!=null&&t->data!=x) { t=t->next; n++; } if(t==null) { return(0); } else { return(n); }}/*显示链表*/void display(struct Lnode **L){ struct Lnode *t; t=*L; if(t==null) { printf("The link is null!"); } else {do { printf("%d>>",t->data); t=t->next; }while(t!=null); } printf("\n");}/*创建链表，并设置链表为空*/void creat(struct Lnode **L){ *L=null;}/*向链表中插入元素*/void insert(struct Lnode **L,int n,ElemType x){/*插在第n个节点的前面*/ struct Lnode *t1,*t2; int j=1; t1=(struct Lnode *)malloc(sizeof(struct Lnode)); t1->data=x; t2=*L; if(n==1) { t1->next=t2; *L=t1; } else { while(jnext!=null) { t2=t2->next; j++; } if(j==n-1) { t1->next=t2->next; t2->next=t1; } else { printf("Insert error!"); } }}/*删除指定位置的节点*/void delete(struct Lnode **L,int n){ int i=1; struct Lnode *t1,*t2; t1=*L; if(n==1) { t2=t1; *L=t1->next; } else { while(inext!=null) { t1=t1->next; i++; } if(t1->next!=null&&i==n-1) { t2=t1->next; t1->next=t2->next; } else { printf("Delete error!\n"); } } if(t2==null){ free(t2); }}/*初始化链表*/void init(struct Lnode **L,int len){ int d[M],i,j,k,ti; struct Lnode *t;input: for(i=1;i<=len;i++) { scanf("%d",&d[i]); } for(j=1;j<=len;j++) for(k=j+1;k<=len;k++) { if(d[j]>d[k]) { ti=d[j]; d[j]=d[k]; d[k]=ti; } }
for(i=1;idata==t2->data) { insert(&*L3,k,t1->data); k++; } t2=t2->next; } t1=t1->next; t2=*L2; }}/*求并集*/unionset(struct Lnode **L1,struct Lnode **L2,struct Lnode **L3){/*把L1复制到L3,然后比较L2与L3，得到L2在L3中没有的元素在L3中的位置，并插入*/ int i,j,k; struct Lnode *tt,*t2,*t3; creat(&*L3); copy(&*L1,&*L3); t2=*L2; t3=*L3; for(i=1;i<=lenth(&*L2);i++) { k=1; for(j=1;j<=lenth(&*L3);j++) { if(t2->data==t3->data) { k=0; break; } else if(t2->datadata) { break; } else if(t2->data>t3->data) { k++; if(k<=lenth(&*L3)) { t3=t3->next; } } } if(k>0&&k<=lenth(&*L3)) {/*插在排序的位置上*/ insert(&*L3,k,t2->data); } else if(k>lenth(&*L3)) {/*插在链尾*/ tt=(struct Lnode *)malloc(sizeof(struct Lnode)); tt->data=t2->data; tt->next=null; t3->next=tt; } t2=t2->next; t3=*L3; }}/*求差集*/void diffrenceset(struct Lnode **L1,struct Lnode **L2,struct Lnode **L3){/*将第一个复制到第三个，查找第二个在第三个中有的元素，并确定它在第三个中的位置，然后从第三个中删除*/ int i,t,n; creat(&*L3); copy(&*L1,&*L3); for(i=1;i<=lenth(&*L2);i++) { t=get(&*L2,i); n=locate(&*L3,t); if(n) { delete(&*L3,n); } }}main(){ int len1,len2; char r; static struct Lnode *head1,*head2,*head3,*head4,*head5,*head6; printf("/************************************************************************/\n"); printf("Please input the lenth of the first linktable! "); scanf("%d",&len1); printf("/************************************************************************/\n"); printf("The lenth of the first linktable is %d,please input %d int data! ",len1,len1); init(&head1,len1); printf("/************************************************************************/\n");
printf("Please input the lenth of the second linktable! "); scanf("%d",&len2); printf("/************************************************************************/\n"); printf("The lenth of the second linktable is %d,please input %d int data! ",len2,len2); init(&head2,len2); printf("\n\n/-----------------------------fire works---------------------------------/\n"); intersection(&head1,&head2,&head3); printf("The intersection of two linktable: "); display(&head3); printf("/-----------------------------fire works---------------------------------/\n"); unionset(&head1,&head2,&head4); printf("The union set of two linktable: "); display(&head4); printf("/-----------------------------fire works---------------------------------/\n"); diffrenceset(&head1,&head2,&head5);/*第一个减第二个的差集*/ printf("The set of the first-second: "); display(&head5); diffrenceset(&head2,&head1,&head6);/*第二个减第一个的差集*/ printf("The set of the second-first: "); display(&head6); printf("/-----------------------------fire works---------------------------------/\n");}
