基于单链表实现集合的并交差运算实验报告
基于单链表实现集合的并交差运算实验报告
一实验题目: 基于单链表实现集合的并交差运算
二 实验要求:
2.2:编写一个程序，实现顺序表的各种基本运算
(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=
数据关系:R1=
基本操作：
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存储结构的定义;
typedef char ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LinkList;
3.3基本操作实现:
/* 单链表的初始化 */
void InitList(LinkList *&L)
{
L = (LinkList *)malloc(sizeof(LinkList));
L->next=NULL;
}
/* 向单链表中插入数据元素 */
bool ListInsert(LinkList *&L,int x,char e)
{
int j = 0;
LinkList *p = L, *s;
while(p!=NULL && j<x-1)
{
p = p->next;
j++;
}
if(p==NULL)
{
return false;
}
else
{
s = (LinkList *)malloc(sizeof(LinkList));
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
}
/* 输出单链表 */
void DispList(LinkList *L)
{
LinkList *p = L->next;
while(p!=NULL)
{
printf("%c",p->data);
p = p->next;
}
printf("\n");
}
/* 求单链表的长度 */
int ListLength(LinkList *L)
{
LinkList *p = L->next;
int i = 0;
while(p!=NULL)
{
i++;
p = p->next;
}
return i;
}
/* 查看单链表是否为空 */
bool ListEmpty(LinkList *L)
{
return L->next==NULL;
}
/* 求单链表中某个数据元素值 */
bool GetElem(LinkList *L,int i, ElemType &e)
{
LinkList *p = L;
int j = 0;
while(p!=NULL && j < i)
{
p=p->next;
j++;
}
if(p==NULL)
{
return false;
}
else
{
e = p->data;
return true;
}
}
/* 在单链表中查找元素 */
int LocateElem(LinkList *L,ElemType e)
{
LinkList *p = L;
int i = 0;
while(p!=NULL && p->data!=e)
{
p = p->next;
i++;
}
if(p==NULL)
{
return 0;
}
else
{
return i;
}
}
/* 删除单链表中第 i 个元素*/
bool ListDelete(LinkList *&L,int i,ElemType &e)
{
int j = 0;
LinkList *p = L, *q;
while(p!=NULL && j < i - 1)
{
p = p->next;
j++;
}
if(p==NULL)
return false;
else
{
q = p->next;
if(q==NULL)
return false;
e = q->data;
p->next = q->next;
free(q);
return true;
}
}
/* 删除单链表 */
void DestroyList(LinkList *&L)
{
LinkList *p = L;
LinkList *q = p->next;
while(q!=NULL)
{
free(p);
p = q;
q = p->next;
}
free(p);
}
3.4解题思路：
1.先通过CreateListR 函数将集合 a 和 b 中的元素添加到顺序表 ha 和 hb 中 ，添加过程使用的是顺序表原有的Initlist 函数（初始化表） 和 ListInsert 函数 （向表中插入元素） 。
2.因为原集合是无序的， 所以我通过 sort 函数 （选择排序），使得集合变得有序。
3.得到有序集合 ha 和 hb 后， 便可以使用 Union 函数（类似归并的思想写出来的求并集的函数），求出 ha 和 hb 的并集。
4.而求交集的方法则是， 通过将 集合 a 中的元素一个一个取出，并通过 函数LocateElem ，查看集合 hb 中是否存在该元素，如果存在则将 元素放入 hc ，如果不存在，则舍去。 以此求得 两 集合的交集。
5.求两集合的差 则可以反过来，同样通过将 集合 a 中的元素一个一个取出，并通过 函数LocateElem ，查看集合 hb 中是否存在该元素，如果不存在则将 元素放入 hc ，如果存在，则舍去。 以此求得两集合的差集。
（ 单链表求交并差集合的思想和顺序表求交并差集合的思想基本相同 ）
3.5解题过程：
实验源代码如下：
3.5.1单链表的各种运算
#include <iostream>
#include <cstdio>
#include <malloc.h>
using namespace std;
/* 定义单链表数据 */
typedef char ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LinkList;
/* 单链表的初始化 */
void InitList(LinkList *&L)
{
L = (LinkList *)malloc(sizeof(LinkList));
L->next=NULL;
}
/* 向单链表中插入数据元素 */
bool ListInsert(LinkList *&L,int x,char e)
{
int j = 0;
LinkList *p = L, *s;
while(p!=NULL && j<x-1)
{
p = p->next;
j++;
}
if(p==NULL)
{
return false;
}
else
{
s = (LinkList *)malloc(sizeof(LinkList));
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
}
/* 输出单链表 */
void DispList(LinkList *L)
{
LinkList *p = L->next;
while(p!=NULL)
{
printf("%c",p->data);
p = p->next;
}
printf("\n");
}
/* 求单链表的长度 */
int ListLength(LinkList *L)
{
LinkList *p = L->next;
int i = 0;
while(p!=NULL)
{
i++;
p = p->next;
}
return i;
}
/* 查看单链表是否为空 */
bool ListEmpty(LinkList *L)
{
return L->next==NULL;
}
/* 求单链表中某个数据元素值 */
bool GetElem(LinkList *L,int i, ElemType &e)
{
LinkList *p = L;
int j = 0;
while(p!=NULL && j < i)
{
p=p->next;
j++;
}
if(p==NULL)
{
return false;
}
else
{
e = p->data;
return true;
}
}
/* 在单链表中查找元素 */
int LocateElem(LinkList *L,ElemType e)
{
LinkList *p = L;
int i = 0;
while(p!=NULL && p->data!=e)
{
p = p->next;
i++;
}
if(p==NULL)
{
return 0;
}
else
{
return i;
}
}
/* 删除单链表中第 i 个元素*/
bool ListDelete(LinkList *&L,int i,ElemType &e)
{
int j = 0;
LinkList *p = L, *q;
while(p!=NULL && j < i - 1)
{
p = p->next;
j++;
}
if(p==NULL)
return false;
else
{
q = p->next;
if(q==NULL)
return false;
e = q->data;
p->next = q->next;
free(q);
return true;
}
}
/* 删除单链表 */
void DestroyList(LinkList *&L)
{
LinkList *p = L;
LinkList *q = p->next;
while(q!=NULL)
{
free(p);
p = q;
q = p->next;
}
free(p);
}
int main( )
{
LinkList *h;
ElemType e;
printf("单链表的基本运算如下：\n");
printf("（1）初始化单链表\n");
InitList(h);
printf("（2）依次采用尾插法插入 a，b，c，d，e 元素\n");
ListInsert(h,1,'a');
ListInsert(h,2,'b');
ListInsert(h,3,'c');
ListInsert(h,4,'d');
ListInsert(h,5,'e');
printf("（3）输出单链表：");
DispList(h);
printf("（4）单链表h的长度 = %d\n",ListLength(h));
printf("（5）单链表h为%s\n",(ListEmpty(h)?"空":"非空"));
GetElem(h,3,e);
printf("（6）单链表h的第3个元素 = %c\n",e);
printf("（7）元素a的位置 = %d\n",LocateElem(h,'a'));
printf("（8）在第4个元素位置上插入f元素\n");
ListInsert(h,4,'f');
printf("（9）输出单链表h：");
DispList(h);
printf("（10）删除h的第3个元素\n");
ListDelete(h,3,e);
printf("（11）输出单链表h：");
DispList(h);
printf("（12）释放单链表h\n");
DestroyList(h);
return 0;
}
3.5.2求集合的并交差
#include <iostream>
#include <cstdio>
#include <malloc.h>
using namespace std;
/* 定义单链表数据 */
typedef char ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LinkList;
/* 单链表的初始化 */
void InitList(LinkList *&L)
{
L = (LinkList *)malloc(sizeof(LinkList));
L->next=NULL;
}
/* 向单链表中插入数据元素 */
bool ListInsert(LinkList *&L,int x,char e)
{
int j = 0;
LinkList *p = L, *s;
while(p!=NULL && j<x-1)
{
p = p->next;
j++;
}
if(p==NULL)
{
return false;
}
else
{
s = (LinkList *)malloc(sizeof(LinkList));
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
}
/* 输出单链表 */
void DispList(LinkList *L)
{
LinkList *p = L->next;
while(p!=NULL)
{
printf("%c ",p->data);
p = p->next;
}
printf("\n");
}
/* 求单链表的长度 */
int ListLength(LinkList *L)
{
LinkList *p = L->next;
int i = 0;
while(p!=NULL)
{
i++;
p = p->next;
}
return i;
}
/* 查看单链表是否为空 */
bool ListEmpty(LinkList *L)
{
return L->next==NULL;
}
/* 求单链表中某个数据元素值 */
bool GetElem(LinkList *L,int i, ElemType &e)
{
LinkList *p = L;
int j = 0;
while(p!=NULL && j < i)
{
p=p->next;
j++;
}
if(p==NULL)
{
return false;
}
else
{
e = p->data;
return true;
}
}
/* 在单链表中查找元素 */
int LocateElem(LinkList *L,ElemType e)
{
LinkList *p = L;
int i = 0;
while(p!=NULL && p->data!=e)
{
p = p->next;
i++;
}
if(p==NULL)
{
return 0;
}
else
{
return i;
}
}
/* 删除单链表中第 i 个元素*/
bool ListDelete(LinkList *&L,int i,ElemType &e)
{
int j = 0;
LinkList *p = L, *q;
while(p!=NULL && j < i - 1)
{
p = p->next;
j++;
}
if(p==NULL)
return false;
else
{
q = p->next;
if(q==NULL)
return false;
e = q->data;
p->next = q->next;
free(q);
return true;
}
}
/* 删除单链表 */
void DestroyList(LinkList *&L)
{
LinkList *p = L;
LinkList *q = p->next;
while(q!=NULL)
{
free(p);
p = q;
q = p->next;
}
free(p);
}
void CreateListR(LinkList *&L,ElemType e[],int n)
{
InitList(L);
int i;
for(i = 0;i < n; ++i)
{
if(!LocateElem(L,e[i]))
ListInsert(L,i+1,e[i]);
}
}
void InsterSect(LinkList *a,LinkList *b,LinkList *&c)
{
DestroyList(c);
InitList(c);
LinkList *p = a->next;
int i = 0;
while(p!=NULL)
{
if(LocateElem(b,p->data))
ListInsert(c,++i,p->data);
p = p->next;
}
}
void Subs(LinkList *a,LinkList *b,LinkList *&c)
{
DestroyList(c);
InitList(c);
LinkList *p = a->next;
int i = 0;
while(p!=NULL)
{
if(!LocateElem(b,p->data))
ListInsert(c,++i,p->data);
p = p->next;
}
}
void Union(LinkList *a,LinkList *b,LinkList *&c)
{
InitList(c);
LinkList *p = a->next;
LinkList *q = b->next;
int k = 0;
while(p!=NULL && q!=NULL)
{
if(p->data < q->data)
{
ListInsert(c,k+1,p->data);
p = p->next;
k++;
}
else if(p->data == q->data)
{
ListInsert(c,k+1,p->data);
p = p->next;
q = q->next;
k++;
}
else
{
ListInsert(c,k+1,q->data);
q = q->next;
k++;
}
}
while(p!=NULL)
{
ListInsert(c,k+1,p->data);
p = p->next;
k++;
}
while(q!=NULL)
{
ListInsert(c,k+1,q->data);
q = q->next;
k++;
}
///cout<<"hehe"<<endl;
}
void sort(LinkList *&L)
{
LinkList *p , *pre, *q, *k;
InitList(p);
int i = 0;
char c;
while(!ListEmpty(L))
{
pre = L ->next;
c = pre->data;
while(pre!=NULL)
{
if(c>=pre->data)
c = pre->data;
pre = pre->next;
}
ListInsert(p,++i,c);
int tag = LocateElem(L,c);
ListDelete(L,tag,c);
}
L = p;
}
int main( )
{
LinkList *ha, *hb, *hc;
ElemType a[]={'c','a','e','h'};
ElemType b[]={'f','h','b','g','d','a'};
printf("集合的运算如下\n");
CreateListR(ha,a,4);
CreateListR(hb,b,6);
printf("原 集 合 A: "); DispList(ha);
printf("原 集 合 B: "); DispList(hb);
sort(ha);
sort(hb);
printf("有序集合A："); DispList(ha);
printf("有序集合B："); DispList(hb);
Union(ha,hb,hc);
printf("集合的并C："); DispList(hc);
InsterSect(ha,hb,hc);
printf("集合的交C："); DispList(hc);
Subs(ha,hb,hc);
printf("集合的差C："); DispList(hc);
DestroyList(ha);
DestroyList(hb);
DestroyList(hc);
return 0;
}
四 实验结果:
-
高级财务会计实验报告格式 - 用于合并
高级财务会计课程实验报告所属学院商学院专业班级会计13班学号姓名20xx3137汤逸君指导老师孙灿明20xx年1月1日123
-
合并财务报表标准审计报告
审计报告ABC有限公司全体股东：一、对财务报表出具的审计报告我们审计了后附的ABC有限公司（以下简称贵公司）合并财务报表，包括20…
-
合并报表审计报告格式
对按照企业会计准则编制的合并财务报表出具的审计报告背景信息1合并财务报表由被审计单位管理层基于通用目的按照企业会计准则的规定编制2…
-
UFO报表实验报告
齐鲁工业大学实验报告成绩课程名称会计电算化指导教师实验日期20xx521院系商学院专业班级会计3班实验地点商学院机房学生姓名学号同…
-
合并会计报表实例分析报告(doc 7页)
精品资料网合并会计报表是会计实务中具有相当难度的问题之一无论是企业集团的会计实务操作还是应对相关会计职称和注册会计师考试在合并会计…
-
单链表实验报告
单链表实验报告实验一线性表基本操作的编程实现--线性表在链表存储下的主要操作实现一、需求分析【实验目的】通过本次实验，对课堂上线性…
-
数据结构单链表实验报告
一设计人员相关信息1设计者姓名学号和班号12地信李晓婧120xx2429832设计日期20xx3上机环境VC60二程序设计相关信息…
-
链表实验报告
数据结构实验报告姓名；**学号：**专业：电子商务班级：10-1班指导教师：实验时间：实验地点：新区实验楼4楼（实验题目）单链表实…
-
数据结构课程单链表实验报告
数据结构实验报告郑州轻工业学院数据结构课程实验实验报告题目单链表表的基本操作及c语言实现专业信息管理与信息系统班级1101姓名高博…
- 数据结构单链表实验报告