链表实现集合实验报告分析.docx
《链表实现集合实验报告分析.docx》由会员分享，可在线阅读，更多相关《链表实现集合实验报告分析.docx（36页珍藏版）》请在冰点文库上搜索。
链表实现集合实验报告分析
线性表实现实验报告
班级：
计算机2班学号：
姓名：
1.需求分析2
1.1输入的形式和输入值的范围2
1.2输出的形式2
1.3程序的功能2
1.4数据测试2
2.概要设计3
2.1主程序流程3
2.2数据定义类型3
2.3函数调用3
3.详细设计4
3.1函数设计5
3.1.1函数申明5
3.1.2程序运行过程中的常量5
3.1.3结构体5
3.1.4intLinkLocate_L（Linklist*L,intx）5
3.1.5intListInsert_L（Linklist*L,inti,ElemTypee）6
3.1.6statusINlist（Linklist*L,inti,ElemType*e）7
3.1.7voidCreateList_L（Linklist*L,intn）8
3.1.8voidHHHGG（Linklist*L）8
3.1.9voidBJ（Linklist*La,Linklist*Lb）9
3.1.10voidJJ（Linklist*La,Linklist*Lb）10
3.1.11voidCJ（Linklist*La,Linklist*Lb）11
3.1.12voidPKJ（Linklist*La）12
4调试分析13
4.1调试过程中遇到的问题及分析13
4.2问题的解决办法13
4.3总结回顾13
4.4算法的时空分析13
5测试结果13
5.1集合的输入13
5.2集合的插入14
5.3集合的删除14
5.4集合的查找14
5.5集合的合集15
5.6集合的交集16
5.7集合的差集16
5.8集合的判空17
6源代码17
1.需求分析
1.1输入的形式和输入值的范围
输入形式：
整数
输入范围：
整数集合长度不能超过1000
1.2输出的形式
用空格分开的一列数
1.3程序的功能
据课上给出的线性表ADT定义，实现集合的（初始化、插入、删除、查找、交集、并集、差集、判空集）
1.4数据测试
线性表长度：
6
元素：
4567910
2.概要设计
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
#definestatusint
2.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
#include
3.1.2程序运行过程中的常量
#defineElemTypeint
#definestatusint
3.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&&jp=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&&jp=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;yfor（j=0;jif（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
#include
#defineElemTypeint
#definestatusint
//结构体
typedefstructNode
{
ElemTyp
升级会员 