一线性表实现与应用

1、实验一线性表实现与应用一、实验目的1掌握线性表的顺序存储和链接存储结构。2了解线性表的应用。3分析顺序线性表与链接线性表的差异。二、实验内容1.利用顺序线性表实现集合运算AUB。2利用向前链表实现集合运算(A-B)U(B-A)。三、实验程序说明1 .假设集合A和B的元素都是整数，并利用两个线性表la和lb分别存放集合A和B的成员。现依次取出lb中的每个元素，按其值查找线性表la,若la中不存在该元素，则将它插入到la中去，最后线性表la就存放了集合AUB的元素。2 .(A-B)U(B-A)是由属于集合A或集合B,但又不同时属于A和B的全部元素组成。我们可以先分别建立由集合A和集合B的元素构成的

2、链表la和lb，然后对lb中每一个元素进行如下处理：在链表la中查找是否有相同元素，若有相同元素，则从la中删除该元素；若没有相同元素，则将此元素插入la中。最后，链表la就存放了(A-B)U(B-A)的全部元素。四、参考程序1./*求集合运算AUB*/#defineMAX100typedefstructcharelementMAX;intnum;LIST;voidcreate(LIST*list)inti,n;printf("Enterthenumberoflist:");scanf("%d",&n);for(i=0;i<n;i+)pri

3、ntf("Enterelement%d:",i+1);scanf("%d",&(list->elementi);list->num=n;intinsert(LIST*list,intm,intx)inti,n;n=list->num;if(n>=MAX)printf("Thelistisoverflow!n");return(-1);elseif(m<1|m>n+1)printf("Error!n");return(-2);elsefor(i=n-1;i>=m-1;

4、i-)list->elementi+1=list->elementi;list->elementm-1=x;list->num=n+1;return(0);intlocate(LIST*list,intx)inti;for(i=0;i<=list->num-1;i+)if(list->elementi=x)return(i+1);return(0);voidprint_list(LIST*list)inti,n;n=list->num;if(n=0)printf("Thelistisempty.n");elsefor(i=0;

5、i<=n-1;i+)printf("%dt",list->elementi);printf("n");main()LIST*la,*lb;inti,x;create(la);printf("SETA:n");print_list(la);create(lb);printf("SETB:n");print_list(lb);for(i=0;i<lb->num;i+)x=lb->elementi;if(locate(la,x)=0)insert(la,la->num+1,x);pri

6、ntf("SET(AUB):n");print_list(la);2/*集合运算(A-B)U(B-A)*/#include<stdio.h>typedefstructnodecharinfo;structnode*link;NODE;NODE*initial(),*process();main()NODE*la,*lb,*ptr,*p1,*p2;printf("nEntertheelementsofSetA:");la=initial();printf("SetA:n");travel(la);printf("n

7、EntertheelementsofSetB:");lb=initial();printf("SetB:n");travel(lb);la=process(la,lb);printf("nSet(A-B)U(B-A):n");travel(la);NODE*initial()NODE*head,*p1,*p2;charch;head=(NODE*)malloc(sizeof(NODE);head->link=NULL;p1=head;while(ch=getchar()!='n')p2=(NODE*)malloc(size

8、of(NODE);p2->info=ch;p2->link=NULL;p1->link=p2;p1=p2;return(head);travel(NODE*ptr)ptr=ptr->link;while(ptr!=NULL)printf("%c",ptr->info);ptr=ptr->link;printf("n");NODE*process(NODE*la,NODE*lb)NODE*ptr,*p1,*p2;intfound=0;ptr=lb->link;while(ptr!=NULL)p1=la->li

9、nk;p2=la;while(p1!=NULL&&!found)if(p1->info=ptr->info)found=1;elsep2=p1;p1=p1->link;if(found)p2->link=p1->link;free(p1);found=0;elsep1=(NODE*)malloc(sizeof(NODE);p1->info=ptr->info;p1->link=NULL;p2->link=p1;ptr=ptr->link;return(la);/*集合运算(A-B)U(B-A)*/#include<

10、;stdio.h>typedefstructnodecharinfo;structnode*link;NODE;NODE*initial(),*process();main()NODE*la,*lb,*ptr,*p1,*p2;printf("nEntertheelementsofSetA:");la=initial();printf("SetA:n");travel(la);printf("nEntertheelementsofSetB:");lb=initial();printf("SetB:n");tra

11、vel(lb);la=process(la,lb);printf("nSet(A-B)U(B-A):n");travel(la);NODE*initial()NODE*head,*p1,*p2;charch;head=(NODE*)malloc(sizeof(NODE);head->link=NULL;p1=head;while(ch=getchar()!='n')p2=(NODE*)malloc(sizeof(NODE);p2->info=ch;p2->link=NULL;p1->link=p2;p1=p2;return(head)

12、;travel(NODE*ptr)ptr=ptr->link;while(ptr!=NULL)printf("%c",ptr->info);ptr=ptr->link;printf("n");NODE*process(NODE*la,NODE*lb)NODE*ptr,*p1,*p2;intfound=0;ptr=lb->link;while(ptr!=NULL)p1=la->link;p2=la;while(p1!=NULL&&!found)if(p1->info=ptr->info)found=

13、1;elsep2=p1;p1=p1->link;if(found)p2->link=p1->link;free(p1);found=0;elsep1=(NODE*)malloc(sizeof(NODE);p1->info=ptr->info;p1->link=NULL;p2->link=p1;ptr=ptr->link;return(la);五、实验步骤1 参考实验程序上机调试。2 对调试好的程序分别输入2组不同的数据，观察运行情况。六、思考题1 .顺序表与链接表存储结构有何区别?2 .在实现插入、删除操作有何不同？七、运行结果3 .求集合运算A

14、UBfl223344En terthe nuinberdFlist：?Enterelement 1 ：77Entere lenient 2 J:EEpnterclement3 ：5SEnterele imeint L 4 J* dz|国tcpelement51Z Jk 31Enterelement161 £金Enterelement L71BET B：g665544bETUi223344Enterthe ntiinbel1oflist tA ：77Itthenumberoflist：5EnterelementLI：11Entei*elementt2：22Enterelement3:33Enterelement141:44Enterelement5：55输入第一组数据，分别是11,22,33,44,55,共5个数字输入第二组数据，分别是77,66,55,44,33,22,11,共7个数字运行出的结果为：11,22,33,44,55,77,664 .集合运算(A-B)U(B-A):ntertheelementsofSet；et由：ntei*theelementsofSet百getB:eh”ykantertheelementsa£GetA:输入第一组数据：def