链表实现集合实验报告

线性表实现实验报告班级：计算机2班学号：姓名：97261.需求分析 266851.1输入的形式和输入值的范围 2298041.2输出的形式 229851.3程序的功能 2135411.4数据测试 220552.概要设计 338552.1主程序流程 3291512.2数据定义类型 3138572.3函数调用 3261053.详细设计 4226653.1函数设计 5211853.1.1函数申明 596843.1.2程序运行过程中的常量 52833.1.3结构体 5257803.1.4intLinkLocate_L(Linklist*L,intx) 5165853.1.5intListInsert_L(Linklist*L,inti,ElemTypee) 687963.1.6statusINlist(Linklist*L,inti,ElemType*e) 7155863.1.7voidCreateList_L(Linklist*L,intn) 834593.1.8voidHHHGG(Linklist*L) 8248833.1.9voidBJ(Linklist*La,Linklist*Lb) 9253033.1.10voidJJ(Linklist*La,Linklist*Lb) 10162603.1.11voidCJ(Linklist*La,Linklist*Lb) 11157773.1.12voidPKJ(Linklist*La) 1271824调试分析 13304384.1调试过程中遇到的问题及分析 13170714.2问题的解决办法 13200534.3总结回顾 1347564.4算法的时空分析 13132345测试结果 13236745.1集合的输入 13319135.2集合的插入 14204075.3集合的删除 14292295.4集合的查找 14216605.5集合的合集 15147955.6集合的交集 16263645.7集合的差集 166675.8集合的判空 17230036源代码 171.需求分析1.1输入的形式和输入值的范围输入形式：整数输入范围：整数集合长度不能超过10001.2输出的形式用空格分开的一列数1.3程序的功能据课上给出的线性表ADT定义，实现集合的（初始化、插入、删除、查找、交集、并集、差集、判空集）1.4数据测试线性表长度：6元素：45679102.概要设计2.1主程序流程voidmain(){ //申请内存 Linklist*La=(Linklist*)malloc(sizeof(Linklist)); Linklist*Lb=(Linklist*)malloc(sizeof(Linklist)); ElemType*e=(ElemType*)malloc(sizeof(ElemType)); intn,n1;//中间变量 //集合的长度赋值 printf("请输入集合的长度："); scanf("%d",&n); //输入集合的元素 CreateList_L(La,n); //查找 printf("\n"); printf("查找结果："); LinkLocate_L(La,3); //删除并输出 INlist(La,1,*e); printf("删除后的结果："); HHHGG(La); //插入并输出 ListInsert_L(La,1,8); printf("插入后的结果："); HHHGG(La); //集合的长度赋值 printf("\n请输入集合的长度："); scanf("%d",&n1); //输入集合的元素 CreateList_L(Lb,n1); //查找 printf("\n"); printf("查找结果："); LinkLocate_L(Lb,3); //删除并输出 INlist(Lb,1,*e); printf("删除后的结果："); HHHGG(Lb); //插入并输出 ListInsert_L(Lb,1,7); printf("插入后的结果："); HHHGG(Lb); //交集 JJ(La,Lb); //差集 CJ(La,Lb); //判空集 PKJ(La); //并集 BJ(La,Lb);}2.2数据定义类型#defineElemTypeint#definestatusint2.3函数调用/*************************************功能：查找集合中的元素参数：需要查找的元素、指针头地址返回值：无*************************************/intLinkLocate_L(Linklist*L,intx)/*****************************************功能：向集合中插入元素参数：头地址、插入位置、插入元素参数：1或0*****************************************/intListInsert_L(Linklist*L,inti,ElemTypee)/********************************************功能：删除元素参数：头地址、插入位置返回值：1或0********************************************/statusINlist(Linklist*L,inti,ElemType*e)/*****************************************功能：创建链表集合参数：集合长度返回值：无*****************************************/voidCreateList_L(Linklist*L,intn)/**********************************功能：输出集合的元素参数：头结点地址返回值：无**********************************/voidHHHGG(Linklist*L)/******************************************功能：集合的并集参数：两个集合的头地址返回值：无******************************************/voidBJ(Linklist*La,Linklist*Lb)/*********************************************功能：两个集合的交集参数：两个集合的头地址返回值：无*********************************************/voidJJ(Linklist*La,Linklist*Lb)/****************************************功能：集合的差集参数：两个集合的头地址返回值：无****************************************/voidCJ(Linklist*La,Linklist*Lb)/*********************************功能：判断集合是否为空参数：头地址返回值：无*********************************/voidPKJ(Linklist*La)3.详细设计3.1函数设计3.1.1函数申明#include<stdio.h>#include<stdlib.h>3.1.2程序运行过程中的常量#defineElemTypeint#definestatusint3.1.3结构体//结构体typedefstructNode{ ElemTypedata; structNode*next;}Node;typedefstructNode*Linklist;3.1.4intLinkLocate_L(Linklist*L,intx)/*************************************功能：查找集合中的元素参数：需要查找的元素、指针头地址返回值：无*************************************/intLinkLocate_L(Linklist*L,intx){ inti;//中间变量 Linklistp;//指针 //赋值 p=(*L)->next; i=1; //循环查找while(p!=NULL&&p->data!=x){ p=p->next; i++;}//条件判断输出结果if(!p)printf("Notfound!\n");else{ printf("你查找的元素存在！\n"); printf("元素位置：i=%d\n",i);}}3.1.5intListInsert_L(Linklist*L,inti,ElemTypee)/*****************************************功能：向集合中插入元素参数：头地址、插入位置、插入元素参数：1或0*****************************************/intListInsert_L(Linklist*L,inti,ElemTypee){ Linklistp;//指针 Linklists;//指针 intj=0;//中间变量 //赋值 p=*L; //循环找到满足条件的插入位置 while(p&&j<i-1){ p=p->next; ++j; } //如果不满足条件返回0 if(!p||j>i-1){ return0; } //申请插入位置的内存 s=((Linklist)malloc(sizeof(Node))); //赋值 s->data=e; s->next=p->next; p->next=s; return1;}3.1.6statusINlist(Linklist*L,inti,ElemType*e)/********************************************功能：删除元素参数：头地址、插入位置返回值：1或0********************************************/statusINlist(Linklist*L,inti,ElemType*e){ Linklistp;//指针 Linklistq;//指针 intj=0;//中间变量 //赋值 p=*L; //循环找到满足条件的插入位置 while(p&&j<i-1){ p=p->next; ++j; } //如果不满足条件返回0 if(!p||j>i-1){ return0; } //将删除的位置以后的元素往前移一位 q=p->next; p->next=q->next; *e=q->data; free(q); return1;}3.1.7voidCreateList_L(Linklist*L,intn)/*****************************************功能：创建链表集合参数：集合长度返回值：无*****************************************/voidCreateList_L(Linklist*L,intn){Linklistp;//指针 inti;//中间变量 //申请节点空间 *L=(Linklist)malloc(sizeof(Node)); //置空 (*L)->next=NULL; //对集合进行赋值 printf("请输入集合的元素："); for(i=n;i>0;--i){ p=(Linklist)malloc(sizeof(Node)); scanf("%d",&p->data); p->next=(*L)->next; (*L)->next=p; } //输出集合元素 printf("\n"); printf("集合的元素："); for(i=n;i>0;--i){ printf("%d",p->data); p=p->next; }}3.1.8voidHHHGG(Linklist*L)/**********************************功能：输出集合的元素参数：头结点地址返回值：无**********************************/voidHHHGG(Linklist*L){ Linklistp;//指针 //赋值 p=*L; p=p->next; //循环输出 while(p!=NULL){ printf("%d",p->data); p=p->next; } printf("\n");}3.1.9voidBJ(Linklist*La,Linklist*Lb)/******************************************功能：集合的并集参数：两个集合的头地址返回值：无******************************************/voidBJ(Linklist*La,Linklist*Lb){ Linklistp,q,first;//指针 intx;//中间变量 //赋值 first=(*La)->next; p=(*Lb)->next; //循环求并集 while(p){x=p->data; p=p->next; q=first;while(q&&q->data!=x) q=q->next;if(!q){q=(Linklist)malloc(sizeof(Node));//申请节点内存将Lb中的元素放到La中q->data=x; q->next=(*La)->next;(*La)->next=q; }}//输出合集printf("\n");printf("合集：");HHHGG(La);}3.1.10voidJJ(Linklist*La,Linklist*Lb)/*********************************************功能：两个集合的交集参数：两个集合的头地址返回值：无*********************************************/voidJJ(Linklist*La,Linklist*Lb){ Linklistp,q;//指针 //赋值 q=(*La)->next; p=(*Lb)->next; printf("\n"); //循环求出交集 printf("集合的交集："); while(p!=NULL){ while(q!=NULL){ if(p->data==q->data){ printf("%d",p->data); } q=q->next; } q=(*La)->next; p=p->next; } }3.1.11voidCJ(Linklist*La,Linklist*Lb)/****************************************功能：集合的差集参数：两个集合的头地址返回值：无****************************************/voidCJ(Linklist*La,Linklist*Lb){ Linklistp,q;//指针 inta[1000];//数组a intb[1000];//数组b inti=0,x=0;//中间变并初始化 intk=-1,j,y;//中间变并初始化 //赋值 q=(*La)->next; p=(*Lb)->next; printf("\n"); //循环求差集 printf("集合的差集："); while(p!=NULL){ while(q!=NULL){ //求出两个集合的相同的元素 if(p->data==q->data){ a[i]=p->data; i++; } q=q->next; } q=(*La)->next; p=p->next; } //将需要求差集的集合的元素赋值给数组 q=(*La)->next; while(q!=NULL){ b[x]=q->data; x++; q=q->next; } if(i==0){ q=(*La)->next; while(q!=NULL){ b[x]=q->data; printf("%d",q->data); q=q->next; } } //循环输出差集 for(y=0;y<x;y++){ for(j=0;j<i;j++){ if(b[y]!=a[j]&&j==i-1){ printf("%d",b[y]); } if(b[y]==a[j])break; } }}3.1.12voidPKJ(Linklist*La)/*********************************功能：判断集合是否为空参数：头地址返回值：无*********************************/voidPKJ(Linklist*La){ intn=0; Linklistp; p=(*La)->next; //循环求集合的长度 while(p!=NULL){ n++; p=p->next; } if(n==0)printf("\n链表为空！"); elseprintf("\n链表不为空！");}4调试分析4.1调试过程中遇到的问题及分析不能很好的理解*L->next和（*L)->next。4.2问题的解决办法通过看相关的视频。4.3总结回顾通过这次的实验过程让我对线性表的认识更加深刻了。4.4算法的时空分析集合的初始化：为集合分配一个一个预定义的大小的一维数组，并将其当前长度设为0。集合的插入：通过遍历整个集合找到合法的插入位置插入，同时集合的长度也会相应的增加1且插入位置之后的元素相应的后移一位。集合的删除：通过遍历整个集合找到合法的删除位置删除相应的元素，同时集合的长度也会相应的减小1且删除位置之后的元素相应的前移一位。集合的查找：遍历整个集合，看是否有符合所查找的元素的值。集合的并集：遍历第一个集合所有元素，将这些元素和第二个集合中的每一个元素进行比较，如果不相同，则申请空间将这些元素插入到第一个集合的所有元素的后面。集合的交集：首先遍历两个集合将前一个集合中的每一个元素都与后一个集合中的元素进行比较，相同则输出，否则，则将指向后一集合的指针进行重新复制，然后又开始将第一个集合的第二个元素拿来比较，直到第一个集合遍历完。集合的差集：首先遍历两个集合将两者的相同值赋值给数组a，将需要求差集的集合中的元素赋值给数组b，如果两者没有相同的元素或那个集合为空集，则直接输出需要求差集的集合中的元素，否则，则需要遍历数组a和b,如果数组b中的每一个元素和a中的所有的元素都不一样，则输出这个元素，如果有相同的，则停止整个数组a的循环同时跳转到数组b接着循环，直至数组b的循环结束。集合的判空：首先定义一个整形的变量n并初始化为0，接着将这个变量放到循环里面，如果循环结束，n=0，则集合为空集，反之，则不为空集。5测试结果5.1集合的输入5.2集合的插入5.3集合的删除5.4集合的查找5.5集合的合集5.6集合的交集5.7集合的差集5.8集合的判空6源代码#include<stdio.h>#include<stdlib.h>#defineElemTypeint#definestatusint//结构体typedefstructNode{ ElemTypedata; structNode*next;}Node;typedefstructNode*Linklist;/*************************************功能：查找集合中的元素参数：需要查找的元素、指针头地址返回值：无*************************************/intLinkLocate_L(Linklist*L,intx){ inti;//中间变量 Linklistp;//指针 //赋值 p=(*L)->next; i=1; //循环查找while(p!=NULL&&p->data!=x){ p=p->next; i++;}//条件判断输出结果if(!p)printf("Notfound!\n");else{ printf("你查找的元素存在！\n"); printf("元素位置：i=%d\n",i);}}/*****************************************功能：向集合中插入元素参数：头地址、插入位置、插入元素参数：1或0*****************************************/intListInsert_L(Linklist*L,inti,ElemTypee){ Linklistp;//指针 Linklists;//指针 intj=0;//中间变量 //赋值 p=*L; //循环找到满足条件的插入位置 while(p&&j<i-1){ p=p->next; ++j; } //如果不满足条件返回0 if(!p||j>i-1){ return0; } //申请插入位置的内存 s=((Linklist)malloc(sizeof(Node))); //赋值 s->data=e; s->next=p->next; p->next=s; return1;}/********************************************功能：删除元素参数：头地址、插入位置返回值：1或0********************************************/statusINlist(Linklist*L,inti,ElemType*e){ Linklistp;//指针 Linklistq;//指针 intj=0;//中间变量 //赋值 p=*L; //循环找到满足条件的插入位置 while(p&&j<i-1){ p=p->next; ++j; } //如果不满足条件返回0 if(!p||j>i-1){ return0; } //将删除的位置以后的元素往前移一位 q=p->next; p->next=q->next; *e=q->data; free(q); return1;}/*****************************************功能：创建链表集合参数：集合长度返回值：无*****************************************/voidCreateList_L(Linklist*L,intn){Linklistp;//指针 inti;//中间变量 //申请节点空间 *L=(Linklist)malloc(sizeof(Node)); //置空 (*L)->next=NULL; //对集合进行赋值 printf("请输入集合的元素："); for(i=n;i>0;--i){ p=(Linklist)malloc(sizeof(Node)); scanf("%d",&p->data); p->next=(*L)->next; (*L)->next=p; } //输出集合元素 printf("\n"); printf("集合的元素："); for(i=n;i>0;--i){ printf("%d",p->data); p=p->next; }}/**********************************功能：输出集合的元素参数：头结点地址返回值：无**********************************/voidHHHGG(Linklist*L){ Linklistp;//指针 //赋值 p=*L; p=p->next; //循环输出 while(p!=NULL){ printf("%d",p->data); p=p->next; } printf("\n");}/******************************************功能：集合的并集参数：两个集合的头地址返回值：无******************************************/voidBJ(Linklist*La,Linklist*Lb){ Linklistp,q,first;//指针 intx;//中间变量 //赋值 first=(*La)->next; p=(*Lb)->next; //循环求并集 while(p){x=p->data; p=p->next; q=first;while(q&&q->data!=x) q=q->next;if(!q){q=(Linklist)malloc(sizeof(Node));//申请节点内存将Lb中的元素放到La中q->data=x; q->next=(*La)->next;(*La)->next=q; }}//输出合集printf("\n");printf("合集：");HHHGG(La);}/*********************************************功能：两个集合的交集参数：两个集合的头地址返回值：无*********************************************/voidJJ(Linklist*La,Linklist*Lb){ Linklistp,q;//指针 //赋值 q=(*La)->next; p=(*Lb)->next; printf("\n"); //循环求出交集 printf("集合的交集："); while(p!=NULL){ while(q!=NULL){ if(p->data==q->data){ printf("%d",p->data); } q=q->next; } q=(*La)->next; p=p->next; } }/****************************************功能：集合的差集参数：两个集合的头地址返回值：无****************************************/voidCJ(Linklist*La,Linklist*Lb){ Linklistp,q;//指针 inta[1000];//数组a intb[1000];//数组b inti=0,x=0;//中间变并初始化 intk=-1,j,y;//中间变并初始化 //赋值 q=(*La)->next; p=(*Lb)->next; printf("\n"); //循环求差集 printf("集合的差集："); while(p!=NULL){ while(q!=NULL){ //求出两个集合的相同的元素 if(p->data==q->data){ a[i]=p->data;