狂妄少女数据结构第一次上机实验报告
一 实验题目: 基于顺序表实现集合的并，交，差运算
二 实验要求:
2.1:编写一个程序，实现顺序表的各种基本运算
(1)初始化顺序表h；
(2)依次采用尾插法插入a,b,c,d,e元素; (3)输出顺序表h
(4)输出顺序表h的长度 (5)判断顺序表h是否为空
(6)输出顺序表h的第三个元素 (7)输出元素在a的位置
(8)在第4个元素位置上插入f元素 (9)输出顺序表h
(10)删除L的第3个元素 (11)输出顺序表 (12)释放顺序表
2.2:编写一个程序，采用顺序表表示集合(集合中不存在重复的元素),并将其按照递增的
方式排序，构成有序顺序表，并求这样的两个集合的并,交和差。
三 实验内容:
3.1 线性表的抽象数据类型:
ADT List{
数据对象;D={ai|ai?ElemSet,i?1,2,...,n,n?0} 数据关系:R1={?ai?1,ai?|ai?1,ai?D,i?2,...,n} 基本操作： InitList(&L)
操作结果;构造一个空的线性表L DestroyList(&L)
初始条件：线性表L已存在 操作结果：销毁线性表L ClearList(&L)
初始条件：线性表L已存在 操作结果：将L置为空表 ListEmpty(L)
初始条件：线性表已存在
操作结果：若L为空表，则返回TRUE，否则返回FALSE ListLength(L)
初始条件：线性表已存在
操作结果：返回L中数据元素的个数 GetElem(L,i)
初始条件:线性表已存在，1<=i<=ListLength(L) 操作结果：用e返回L中第i个数据元素的值 LocateElem(L,i,e)
初始条件：线性表已存在，用循环遍历整个线性表，如果e与线性表中的元素相同； 操作结果：用此时的i+1返回该元素在线性表的位序 ListInsert(&L,i,e)
初始条件：线性表存在，1<=i<=ListLength(L)+1;
操作结果：在L中第i个位置之前插入新的数据元素,e,L的长度加1。 ListDelete(&L,i,&e)
初始条件:线性表L已存在且非空，1<=i<=ListLength(L)；
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 }ADT List
3.2存储结构的定义;
#define LIST_INIT_SIZE 100 #define LISTINCREEMENT 10 typedef char ElemType; typedef struct {
ElemType data[Maxsize]; int length; }SqList;
3.3基本操作实现:
void InitList(SqList *&L)//初始化顺序表 {
L = (SqList *)malloc(sizeof(SqList));//用malloc动态申请一个顺序表的内存空间
L->length = 0; }
void DestroyList(SqList *L) {
free(L);//释放指针L }
bool ListEmpty(SqList *L) {
return (L->length == 0);//length为0表示表空 }
int ListLength(SqList *L) {
return (L->length);
}
void DispList(SqList *L) {
int i;
if(ListEmpty(L)) return ; for(i = 0;i < L->length;i++) {
printf(\ printf(\ } }
bool GetElem(SqList *L,int i,ElemType &e) {
if(i < 1||i > L->length) return false; e = L->data[i-1]; return true; }
int LocateElem(SqList *L,ElemType e) {
int i = 0;
while(i < L->length&&L->data[i]!=e) {
i++; }
if(i >= L->length) return 0; else return i+1; }
bool ListInsert(SqList *&L,int i,ElemType e) {
int j;
if(i < 1||i>L->length+1) return false; i--;
for(j=L->length;j>i;j--) L->data[j]=L->data[j-1]; L->data[i]=e; L->length++; return true; }
bool ListDelete(SqList *&L,int i,ElemType &e) {
int j;
if(i<1||i>L->length) return false; i--;
e = L->data[i];
for(j = i;j
3.4解题思路：
1 首先分别用2个顺序表存储集合A,B中的元素
2 开始集合A，B是无序的，然后用个sort函数（冒泡排序算法）分别对顺序表进行按照从小到大排序，输出有序的集合A,B;
3 在2步骤的基础上，再定义一个线性表C,分别在线性表A，B中去取出一个值，若两个值相等则将其中一个插入线性表C中
若不相等则将其中小的值先插入C中，接着将大的值插入C中，如此循环，直至线性表A,B中有一个遍历完了，把没有遍历完的全部插入线性表C; 那么求集合的并集就完成了。
4 在2步骤的基础上，再定义一个线性表C,分别在线性表A，B中去取出一个值，若两个值相等则将其中一个插入线性表C中,若不相等，
则进行下一个元素的比较；如此循环，最终线性表C中就是集合A,B的交集。 5 在2的步骤的基础上，再定义一个线性表C,分别在线性表A，B中去取出一个值，以A顺序表为基准，
将顺序表A中取出的每一个值都去与顺序表B中的每一个值作比较若不相等，则将A中取出的值插入顺序表C中，若相等则取A中下一个元素，直至A中的值 取完为止，那么最终C中元素就是集合A与集合B的差集。 3.5解题过程： 实验源代码如下： # include
typedef char ElemType;//ElemType 是个虚拟类型 typedef struct {
ElemType data[Maxsize]; int length; }SqList;
void InitList(SqList *&L)//初始化顺序表 {
L = (SqList *)malloc(sizeof(SqList));//用malloc动态申请一个顺序表的内存空间
L->length = 0; }
void DestroyList(SqList *L)//销毁顺序表 {
free(L);//释放指针L }
bool ListEmpty(SqList *L)//判定顺序表是否为空 {
return (L->length == 0);//length为0表示表空 }
int ListLength(SqList *L)//返回顺序表的长度 {
return (L->length); }
void DispList(SqList *L)//输出顺序表 {
int i;
if(ListEmpty(L)) return ; for(i = 0;i < L->length;i++) {
printf(\
}
printf(\}
bool GetElem(SqList *L,int i,ElemType &e)//获取顺序表中的一个值 {
if(i < 1||i > L->length) return false; e = L->data[i-1]; return true; }
int LocateElem(SqList *L,ElemType e)//获取顺序表中值的位序 {
int i = 0;
while(i < L->length&&L->data[i]!=e) {
i++; }
if(i >= L->length) return 0; else return i+1; }
bool ListInsert(SqList *&L,int i,ElemType e)//向顺序表中插入一个元素 {
int j;
if(i < 1||i>L->length+1) return false; i--;
for(j=L->length;j>i;j--) L->data[j]=L->data[j-1]; L->data[i]=e; L->length++;
