链表实现集合实验报告
链表实现实验报告
班级：计算机2班学号：201511407141 姓名：杨舟
1.需求分析 (2)
1.1输入的形式和输入值的范围 (2)
1.2输出的形式 (2)
1.3程序的功能 (2)
1.4数据测试 (2)
2.概要设计 (3)
2.1主程序流程 (3)
2.2数据定义类型 (5)
2.3函数调用 (5)
3.详细设计 (6)
3.1函数设计 (6)
3.1.1 函数申明 (6)
3.1.2程序运行过程中的常量 (6)
3.1.3 结构体 (6)
3.1.4 int LinkLocate_L (Linklist *L, int x) (7)
3.1.5 int ListInsert_L( Linklist *L, int i, ElemType e ) (7)
3.1.6 status INlist( Linklist *L, int i, ElemType *e ) (8)
3.1.7 void CreateList_L(Linklist *L, int n) (9)
3.1.8 void HHHGG( Linklist *L ) (10)
3.1.9 void BJ( Linklist *La, Linklist *Lb ) (10)
3.1.10 void JJ( Linklist *La, Linklist *Lb ) (11)
3.1.11 void CJ( Linklist *La, Linklist *Lb ) (12)
3.1.12 void PKJ( Linklist *La ) (13)
4 调试分析 (14)
4.1 调试过程中遇到的问题及分析 (14)
4.2 问题的解决办法 (14)
4.3 总结回顾 (14)
4.4 算法的时空分析 (15)
5测试结果 (16)
5.1集合的输入 (16)
5.2集合的插入 (16)
5.3集合的删除 (16)
5.4集合的查找 (17)
5.5集合的合集 (17)
5.6集合的交集 (18)
5.7集合的差集 (18)
5.8集合的判空 (19)
6源代码.......................................................................................................... 错误！未定义书签。
1.需求分析
1.1输入的形式和输入值的范围
输入形式：整数
输入范围：整数集合长度不能超过1000
1.2输出的形式
用空格分开的一列数
1.3程序的功能
据课上给出的线性表ADT定义，实现集合的（初始化、插入、删除、查找、交集、并集、差集、判空集）
1.4数据测试
线性表长度：4
元素：4 5 6 7
2.概要设计
2.1
Linklist *La = (Linklist*)malloc(sizeof(Linklist));
Linklist *Lb = (Linklist*)malloc(sizeof(Linklist));
ElemType *e = (ElemType*)malloc(sizeof(ElemType));
int n, 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数据定义类型
#define ElemType int
#define status int
2.3函数调用
/*************************************
功能：查找集合中的元素
参数：需要查找的元素、指针头地址
返回值：无
*************************************/
int LinkLocate_L (Linklist *L, int x)
/*****************************************
功能：向集合中插入元素
参数：头地址、插入位置、插入元素
参数：1或0
*****************************************/
int ListInsert_L( Linklist *L, int i, ElemType e )
/******************************************** 功能：删除元素
参数：头地址、插入位置
返回值：1或0
********************************************/ status INlist( Linklist *L, int i, ElemType *e )
/*****************************************
功能：创建链表集合
参数：集合长度
返回值：无
*****************************************/ void CreateList_L(Linklist *L, int n)
/**********************************
功能：输出集合的元素
参数：头结点地址
返回值：无
**********************************/
void HHHGG( Linklist *L )
/****************************************** 功能：集合的并集
参数：两个集合的头地址
返回值：无
******************************************/ void BJ( Linklist *La, Linklist *Lb )
/********************************************* 功能：两个集合的交集
参数：两个集合的头地址
返回值：无
*********************************************/ void JJ( Linklist *La, Linklist *Lb )
/****************************************
功能：集合的差集
参数：两个集合的头地址
返回值：无
****************************************/
void CJ( Linklist *La, Linklist *Lb )
/*********************************
功能：判断集合是否为空
参数：头地址
返回值：无
*********************************/
void PKJ( Linklist *La )
3.详细设计
3.1函数设计
3.1.1 函数申明
#include
#include
3.1.2程序运行过程中的常量
#define ElemType int
#define status int
3.1.3 结构体
//结构体
typedef struct Node
{
ElemType data;
struct Node *next;
}Node;
typedef struct Node* Linklist;
3.1.4 int LinkLocate_L (Linklist *L, int x)
/*************************************
功能：查找集合中的元素
参数：需要查找的元素、指针头地址
返回值：无
*************************************/
int LinkLocate_L (Linklist *L, int x)
{
int i; //中间变量
Linklist p;//指针
//赋值
p=(*L)->next;
i=1;
//循环查找
while (p!=NULL && p->data != x){
p= p->next;
i++;
}
//条件判断输出结果
if (!p) printf ("Not found! \n");
else {
printf( "你查找的元素存在！\n" );
printf ("元素位置：i=%d\n",i);
}
}
3.1.5 int ListInsert_L( Linklist *L, int i, ElemType e )
/*****************************************
功能：向集合中插入元素
参数：头地址、插入位置、插入元素
参数：1或0
*****************************************/
int ListInsert_L( Linklist *L, int i, ElemType e ){
Linklist p;//指针
Linklist s;//指针
int j = 0;//中间变量
//赋值
p = *L;
//循环找到满足条件的插入位置
while( p && j < i - 1 ){
p = p->next;
++j;
}
//如果不满足条件返回0
if( !p || j > i - 1 ){
return 0;
}
//申请插入位置的内存
s = ( (Linklist) malloc( sizeof(Node) ) );
//赋值
s->data = e;
s->next = p->next;
p->next = s;
return 1;
}
3.1.6 status INlist( Linklist *L, int i, ElemType *e )
/********************************************
功能：删除元素
参数：头地址、插入位置
返回值：1或0
********************************************/
status INlist( Linklist *L, int i, ElemType *e ){
Linklist p;//指针
Linklist q;//指针
int j = 0;//中间变量
//赋值
p = *L;
//循环找到满足条件的插入位置
while( p && j < i - 1 ){
p = p->next;
++j;
}
//如果不满足条件返回0
if( !p || j > i - 1 ){
return 0;
}
//将删除的位置以后的元素往前移一位
q = p->next;
p->next = q->next;
*e = q->data;
free(q);
return 1;
}
3.1.7 void CreateList_L(Linklist *L, int n)
/*****************************************
功能：创建链表集合
参数：集合长度
返回值：无
*****************************************/
void CreateList_L(Linklist *L, int n)
{ Linklist p;//指针
int i;//中间变量
//申请节点空间
*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.8 void HHHGG( Linklist *L )
/**********************************
功能：输出集合的元素
参数：头结点地址
返回值：无
**********************************/
void HHHGG( Linklist *L ){
Linklist p;//指针
//赋值
p = *L;
p = p->next;
//循环输出
while( p != NULL ){
printf( "%d ", p->data );
p = p->next;
}
printf( "\n" );
}
3.1.9 void BJ( Linklist *La, Linklist *Lb )
/******************************************
功能：集合的并集
参数：两个集合的头地址
返回值：无
******************************************/
void BJ( Linklist *La, Linklist *Lb ){
Linklist p,q,first; //指针
int x;//中间变量
//赋值
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.10 void JJ( Linklist *La, Linklist *Lb )
/*********************************************
功能：两个集合的交集
参数：两个集合的头地址
返回值：无
*********************************************/
void JJ( Linklist *La, Linklist *Lb ){
Linklist p,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.11 void CJ( Linklist *La, Linklist *Lb )
/****************************************
功能：集合的差集
参数：两个集合的头地址
返回值：无
****************************************/
void CJ( Linklist *La, Linklist *Lb ){
Linklist p,q;//指针
int a[1000];//数组a
int b[1000];//数组b
int i = 0, x = 0;//中间变并初始化
int k = -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.12 void PKJ( Linklist *La ) /*********************************
功能：判断集合是否为空
参数：头地址
返回值：无
*********************************/
void PKJ( Linklist *La ) {
int n = 0;
Linklist p;
p = (*La)->next;
//循环求集合的长度
while( p != NULL ){
n++;
p = p->next;
}
if( n == 0 ) printf( "\n链表为空！" );
else printf( "\n链表不为空！" );
}
4 调试分析
4.1 调试过程中遇到的问题及分析
不能很好的理解SqList *L和SqList L的区别以及对结构体理解不够透彻。
4.2 问题的解决办法
通过看相关的视频和询问老师
4.3 总结回顾
通过这次的实验过程让我对线性表的认识更加深刻了，同时也让我知道了在c上的一些不足。
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.5 集合的合集
5.7 集合的差集
5.8 集合的判空