devbox
小丑西瓜9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【实验报告】实验一顺序表实现集合运算_数据结构实验一顺序表实验报告集合

作者：小丑西瓜9 | 2024-05-19 01:37:31

赞

踩

数据结构实验一顺序表实验报告集合

顺序表实现集合运算

一、需求分析

1、数据存储结构为顺序表
2、输入形式为键盘键入，键入范围为：a ~ z
3、输出的形式为打印形式
4、包含顺序表的基本操作
5、能够完成集合的交、并、补运算
6、正确操作应能显示输入结果与计算结果
7、错误操作应该出现对应提示
8、界面设计应简洁易用

二、概要设计

一、抽象数据类型定义

ADT set{
数据对象:D=
数据关系:R1=
数据操作:
InitList_Sq(SqList* L)
操作结果：初始化一个顺序表
ListInsert_Sq(SqList* L,int i,ElemType e)
初始条件：表L存在
操作结果：顺序表 L的逻辑为i的位置插入新元素e
LocateElem_Sq(SqList L,ElemType e,Status(* compare)(ElemType,ElemType))
初始条件：表L存在
操作结果：在顺序线性表L中查找第1个与e满足compare() 的元素位序，若找到，则返回其在L中的位序，否则返回0
Clear_Sq(SqList L)
初始条件：表L存在
操作结果：销毁线性表
Print_Sq(SqList L)
初始条件：表L存在
操作结果：打印出表内数据
}

二、宏定义部分

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -10
#define LIST_INIT_SIZE 100 //初始表空间大小
#define LISTINCREMENT 10 // 表长增加量

三、主程序流程图

在这里插入图片描述

四、程序结构图程序模块如下：

1、主函数模块——调用主程序模块
2、主程序模块——调用其他功能函数模块
3、输入模块——接受用户输入并将数据进行存储
4、运算模块——完成用户的运算操作
5、显示模块——显示用户的运算结果
结果如下
在这里插入图片描述

三、详细设计

一、数据类型设计

typedef int Status;
typedef char ElemType;
typedef struct{
ElemType *elem; //储存空间基地址
int length; //当前长度
int listsize; //当前分配的储存容量（以sizeof(Elemtype)为单位）
}SqList;

二、数据操作

Status InitList_Sq(SqList* L){
L->elem = (ElemType )malloc(LIST_INIT_SIZE * sizeof(ElemType));
if(!L->elem){
exit(OVERFLOW); //内存分配失败
}
L->length = 0;
L->listsize = LIST_INIT_SIZE;
return OK;
}
Status ListInsert_Sq(SqList L,int i,ElemType e){
ElemType *newbase,*p,*q;
//i的合法值为(1 <= i <= L.length_Sq(L) + 1)
//异常处理
if(i < 1 || i > L->length + 1){
return ERROR;
}
if(L->length >= L->listsize){ //当前储存空间已满，增加分配
newbase = (ElemType *)realloc(L->elem,(L->listsize + LISTINCREMENT) * sizeof(ElemType));
if(!newbase){
exit(OVERFLOW);
} //储存分配失败
L->elem = newbase; //新基址
L->listsize += LISTINCREMENT; //增加储存容量
}
q = &(L->elem[i - 1]); //q为插入位置
for(p = &(L->elem[L->length - 1]); p >= q; --p)
*(p + 1) = *p; //插入位置及之后的元素往右移
q = e; //插入e
++L->length; //表长加1
return OK;
}
int LocateElem_Sq(SqList L,ElemType e,Status( compare)(ElemType,ElemType)){
ElemType p;
int i;
i = 1; //i的初值为第1个元素的位序
p = L.elem; //p的初值为第1个元素的储存位置
while(i <= L.length && !( compare)(*p++,e)){
++i;
}
if(i <= L.length){
return i;
}
else{
return 0;
}
}
Status Clear_Sq(SqList L){
ElemType elem;
free(L.elem);
L.elem = NULL;
return OK;
}
void Print_Sq(SqList L){
int i;
for(i = 0; i < L.length; i++)
printf("%2c",L.elem[i]);
if(L.length == 0) {
printf(“该集合为空集”);
}
printf("\n\t\t\t#\t此集合中的个数 n = %d\n\n",L.length);
}

三、运算功能

/求集合的并集的函数/
void Union_Sq(SqList La,SqList Lb,SqList* Lc){
int i;
ElemType elem;
Lc->length=0;
for(i = 0; i < La.length; i++){
Lc->elem[Lc->length++]=La.elem[i];
}
for(i = 1; i <= Lb.length; i++){
elem = Lb.elem[i-1];
if(!LocateElem_Sq(La,elem,Equal)){
ListInsert_Sq(Lc,Lc->length+1,elem);
}
}
}
/求集合的交集的函数/
void Mix_Sq(SqList La,SqList Lb,SqList* Lc){
int i;
ElemType elem;
Lc->length = 0;
for(i = 1; i <= La.length; i++){
elem = La.elem[i-1];
if(LocateElem_Sq(Lb,elem,Equal)){
ListInsert_Sq(Lc,Lc->length+1,elem);
}
}
}
/求集合的补集函数/
void Comple_Sq(SqList La,SqList Lb,SqList* Lc,SqList* Ld){
int i;
ElemType elem;
Ld->length = 0;
Union_Sq(La,Lb,Lc);
for(i = 1; i <= Lc->length; i++){
elem = Lc->elem[i-1];
if(!LocateElem_Sq(La,elem,Equal)){
ListInsert_Sq(Ld,Ld->length+1,elem);
}
}
}
/*判断两元素是否相等,若相等则返回TRUE;否则返回FALSE/
Status Equal(ElemType a,ElemType b){
if(a == b){
return TRUE;
}
else{
return FALSE;
}
}

四、主程序

void Index_Sq(){
SqList La,Lb,Lc,Ld;
char s;
int l;
l = 1;
InitList_Sq(&La);
CreateList_Sq(&La);
Print_Sq(La); //实现表LA的操作
InitList_Sq(&Lb);
CreateList_Sq(&Lb);
Print_Sq(Lb); //实现表LB的操作
InitList_Sq(&Lc); //初始化表LC的操作
InitList_Sq(&Ld); //初始化表Ld的操作
while(l){
scanf("%c",&s);
switch(s){
case ‘a’ :
Union_Sq(La,Lb,&Lc);
Print_Sq(Lc); //实现表LA与表LB并集的操作
break;
case ‘b’ :
Mix_Sq(La,Lb,&Lc);
Print_Sq(Lc); //实现表LA与表LB交集的操作
break;
case ‘c’ :
Comple_Sq(La, Lb, &Lc, &Ld);
Print_Sq(Ld); //实现表LA的补集操作
break;
case ‘d’ :
Comple_Sq(Lb, La, &Lc, &Ld);
Print_Sq(Ld); //实现表LA的补集操作
break;
case ‘e’ :
Clear_Sq(La);
Clear_Sq(Lb);
Clear_Sq(Lc);
Clear_Sq(Ld);
getchar();
Index_Sq();
break;
default : printf("\t\t\t#\tenter data error!\n");
}
printf("\t\t|**** 您是否还想继续计算。是请输入1，否请输入0 |\n");
printf("\t\t\t");
scanf("%d",&l);
getchar();
}//while语句判断是否继续
printf("\n\t\t|************ 欢迎使用，谢谢！*****************|\n");
getchar();
}

四、调试分析

1、输入时发现第一个元素不见了，但程序能够正常运行，后面排查发现是插入函数中下标写出错了，导致从第二个输入元素开始插入。因此在写循环应时刻注意下标的含义，以免照成数据丢失。
2、初始化函数没有把顺序表的地址传入进去，导致一直未能成功初始化，无法接受用户输入。因此在编写C语言函数的过程中要弄清楚参数的传递关系与概念。

五、用户使用说明

一、本程序运行环境为Windows操作系统下的Microsoft Visual C++ 6.0。
二、在VC环境下打开程序后，按要求键入要求的字符，敲击“回车符”输入，并键入要求的字符以选择功能，即可以显示要求的结果。
三、按下任意键以继续。

六、测试结果

测试输入1: a b c d \n b d f g \n
在这里插入图片描述

测试输入2： 4 d ; f \n 0 o s v \n
在这里插入图片描述

七、附录

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -10
#define LIST_INIT_SIZE 100 //初始表空间大小
#define LISTINCREMENT 10 // 表长增加量
typedef int Status;	 /**Status是函数类型，其值是函数结果状态代码，如OK等*/
typedef char ElemType;

/**顺序表的定义*/
typedef struct 
{
	ElemType* elem;
	int length;
	int listsize;
}SqList;

/**初始化函数*/
Status InitList_Sq(SqList* L){
	L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if(!L->elem){
		exit(OVERFLOW); //内存分配失败
	}
	L->length = 0;
	L->listsize = LIST_INIT_SIZE;
	return OK;
}

/**在顺序表的逻辑为i的位置插入新元素e的函数*/
Status ListInsert_Sq(SqList* L,int i,ElemType e){
	ElemType *newbase,*p,*q;
	//i的合法值为(1 <= i <= L.length_Sq(L) + 1)
	//异常处理
	if(i < 1 || i > L->length + 1){
		return ERROR;
	}
	if(L->length >= L->listsize){ //当前储存空间已满，增加分配
		newbase = (ElemType *)realloc(L->elem,(L->listsize + LISTINCREMENT) * sizeof(ElemType));
		if(!newbase){
			exit(OVERFLOW);
		} //储存分配失败
		L->elem = newbase; //新基址
		L->listsize += LISTINCREMENT; //增加储存容量
	}
		q = &(L->elem[i - 1]); //q为插入位置
	for(p = &(L->elem[L->length - 1]); p >= q; --p) 
		*(p + 1) = *p; //插入位置及之后的元素往右移
	*q = e; //插入e
	++L->length; //表长加1
	return OK;
}

/**创建一个线性表，即输入数据,根据需求：集合中的元素不能相等创建且为a-z*/
void CreateList_Sq(SqList* L){
	ElemType ch;
	int inlist = FALSE,j;
	while((ch) != '\n'){
		scanf("%c",&ch);
		for(j = 0; j < L->length; j++)
		if(ch == L->elem[j]){
			inlist = TRUE;
			break;
		}
		else{
			inlist = FALSE;
		}
			
		if(!inlist && ch != '\n' && ch >= 'a' && ch <= 'z'){
			ListInsert_Sq(L,L->length+1,ch);
		}
	}
}

/**判断两元素是否相等,若相等则返回TRUE;否则返回FALSE*/
Status Equal(ElemType a,ElemType b){
	if(a == b){
		 return TRUE;
	}
	else{
		 return FALSE;
	}
}

/**在顺序线性表L中查找第1个与e满足compare()的元素位序，若找到，则返回其在L中的位序，否则返回0*/
int LocateElem_Sq(SqList L,ElemType e,Status(* compare)(ElemType,ElemType)){
	ElemType *p;
	int i;
	i = 1; //i的初值为第1个元素的位序
	p = L.elem; //p的初值为第1个元素的储存位置
	while(i <= L.length && !(* compare)(*p++,e)){
		++i;
	}
	if(i <= L.length){
		return i;
	} 
	else{
		return 0;
	}
} //该函数的时间复杂度为O(n)

/*销毁线性表的函数*/
Status Clear_Sq(SqList L){
	ElemType elem;
	free(L.elem);
	L.elem = NULL;
	return OK;
}

/**打印顺序表函数**/
void Print_Sq(SqList L){
	int i;
	for(i = 0; i < L.length; i++)
	printf("%2c",L.elem[i]);
	if(L.length == 0) {
		printf("该集合为空集"); 
	}
	printf("\n\t\t\t#\t此集合中的个数 n = %d\n\n",L.length);
}

/**求集合的并集的函数**/
void Union_Sq(SqList La,SqList Lb,SqList* Lc){
	int i;
	ElemType elem;
	Lc->length=0;
	for(i = 0; i < La.length; i++){
		Lc->elem[Lc->length++]=La.elem[i];
	}
	for(i = 1; i <= Lb.length; i++){
		elem = Lb.elem[i-1];
		if(!LocateElem_Sq(La,elem,Equal)){
			ListInsert_Sq(Lc,Lc->length+1,elem);
		}
    }
}

/**求集合的交集的函数**/
void Mix_Sq(SqList La,SqList Lb,SqList* Lc){
	int i;
	ElemType elem;
	Lc->length = 0;
	for(i = 1; i <= La.length; i++){
		elem = La.elem[i-1];
		if(LocateElem_Sq(Lb,elem,Equal)){
			ListInsert_Sq(Lc,Lc->length+1,elem);
		}
    }
}

/**求集合的补集函数**/
void Comple_Sq(SqList La,SqList Lb,SqList* Lc,SqList* Ld){
	int i;
	ElemType elem;
	Ld->length = 0;
	Union_Sq(La,Lb,Lc);
	for(i = 1; i <= Lc->length; i++){
		elem = Lc->elem[i-1];
		if(!LocateElem_Sq(La,elem,Equal)){
			ListInsert_Sq(Ld,Ld->length+1,elem);
		}	
}
}

void Index_Sq(){
	SqList La,Lb,Lc,Ld;
	char s;
	int l;
	l = 1;
	
	InitList_Sq(&La);
	printf("\t\t\t|****** 请输入你的第一个集合：******|\n");
	printf("\t\t\t");
	CreateList_Sq(&La);
	printf("\t\t\t#\t集合A为");
	Print_Sq(La); //实现表LA的操作
	printf("\t\n\n");
	
	InitList_Sq(&Lb);
	printf("\t\t\t|****** 请输入你的第二个集合：******|\n");
	printf("\t\t\t");
	CreateList_Sq(&Lb);
	printf("\t\t\t#\t集合B为");
	Print_Sq(Lb); //实现表LB的操作
	printf("\t\n\n");
	
	InitList_Sq(&Lc); //初始化表LC的操作
	InitList_Sq(&Ld); //初始化表Ld的操作
		
	while(l){
		printf("\t\t|******* 您可以选择a、b、c或者d执行以下操作 ******|\n\n");
		printf("\t\t|************* a、进行集合的并运算 ***************|\n");
		printf("\t\t|************* b、进行集合的交运算 ***************|\n");
		printf("\t\t|************* c、进行集合A的补运算 **************|\n");
		printf("\t\t|************* d、进行集合B的补运算 **************|\n");
		printf("\t\t|************* e、重新建立两个集合 ***************|\n");
		printf("\t\t\t");
		scanf("%c",&s);
		switch(s){
			case 'a' : 
				Union_Sq(La,Lb,&Lc);
				printf("\t\t\t#\t集合A与集合B的并集为:");
				Print_Sq(Lc); //实现表LA与表LB并集的操作
				printf("\n");
				break;
			case 'b' : 
				Mix_Sq(La,Lb,&Lc);
				printf("\t\t\t#\t集合A与集合B的交集为:");
				Print_Sq(Lc); //实现表LA与表LB交集的操作
				printf("\n");
				break;
			case 'c' :
				Comple_Sq(La, Lb, &Lc, &Ld);
				printf("\t\t\t#\t集合A的补集为:");
				Print_Sq(Ld); //实现表LA的补集操作
				printf("\n");
				break;
			case 'd' :
				Comple_Sq(Lb, La, &Lc, &Ld);
				printf("\t\t\t#\t集合B的补集为:");
				Print_Sq(Ld); //实现表LA的补集操作
				printf("\n");
				break;
			case 'e' :
			Clear_Sq(La);
			Clear_Sq(Lb);
			Clear_Sq(Lc);
			Clear_Sq(Ld);
			
			getchar();
			Index_Sq();
			
			break;
			default  : printf("\t\t\t#\tenter data error!\n");
			printf("\n");
		}
		printf("\t\t|**** 您是否还想继续计算。是请输入1，否请输入0 ****|\n");
		printf("\t\t\t");
		scanf("%d",&l);
		getchar();
	}//while语句判断是否继续
	printf("\n\t\t|**************** 欢迎使用，谢谢！*****************|\n");
	getchar();
}
int main(){
	printf("\t\t|************* 欢迎使用集合操作运算器 ************|\n");
	Index_Sq();
 
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248
  • 249
  • 250
  • 251
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/590808
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号