单链表的集合操作实验报告

江西理工大学软件学院

实 验 报 告

系（部） 机电工程系

课 程 数据结构 专业班级 11机械电子（2）班

姓 名 杨锦其 学 号 11212203 指导教师 刘廷苍

实验题目：用单链表实现集合的操作

一．实验目的

用有序单链表实现集合的判等，交，并和差等基本运算。

二．实验内容

（1）对集合中的元素用有序单链表进行存储；

（2）实现交，并，差等基本运算时，不能另外申请存储空间； （3）充分利用单链表的有序性，要求算法有较好的时间性能。

三．设计与代码

1. 理论知识

集合是由互不相同的元素构成的一个整体，在集合中，元素之间可以没有任何关系，所以，集合也可以作为线性表处理。用单链表实现集合的操作，需要注意集合中元素的唯一性，即在单链表中不存在值相同的结点。本实验要求采用有序单链表，还要注意单链表的有序性。

2. 算法设计

（1）判断集合相等算法：

两个集合相等的条件是不仅长度相同，而且各个对应的元素也相等。由于用有序单链表表示集合，所以只要同步扫描两个单链表，若从头至尾每个对应的元素都相等，则表明两个集合都相等。

template

bool IsEqual(linklist &list1,linklist &list2){ int i1=1,i2=1;//分别表示链表list1和list2的位置 //当list1不为'\\0'时循环

if(list1.GetLength()!=list2.GetLength()) { return false; } else{

while(list1.Get(i1)!='\\0') { while(list2.Get(i2)!='\\0') { if(list1.Get(i1)!=list2.Get(i2)){i2++;} else{break;} }//while

if(list2.Get(i2)!='\\0'){ i1++;i2=1; } else{ return false;} }//while return true; }//else }

（2） 求集合交集算法 ：

根据集合的运算规则，集合A交B中包含所有既属于集合A又属于集合B的元素，因此需查找单链表A和B中的相同元素并保留在单链表A中。由于用有序单链表表示集合，因此判断某元素是否在B中不需要遍历表B，而是从上次搜索到的位置开始，若在搜索过程中，遇到一个其值比该元素大的结点，便可断定该元素不在单链表中。

template

void AndSet(linklist &list1,linklist &list2){ int i1=1,i2=1;//分别表示链表list1和list2的位置 while(list1.Get(i1)!='\\0') { while(list2.Get(i2)!='\\0') { if(list1.Get(i1)==list2.Get(i2)){ break; } else{ ++i2;} }//while if(list2.Get(i2)!='\\0') { ++i1; i2=1;} else { list1.Delete(i1); i2=1;} }//while

list1.Delete(i1);//将'\\0'删除 }

（3）求集合A和B的交集：

根据集合的运算规则，集合A并B中包含所有或属于集合A或属于集合B的元素。因此单链表B中的每个元素x，在单链表A中进行查找，若存在和x不相同的元素，则该结点插入到单链表A中。

template

void OrSet(linklist &list1,linklist &list2){ int i1=1,i2=1;//分别表示链表list1和list2的位置 while(list1.Get(i1)!='\\0') { while(list2.Get(i2)!='\\0') { if(list1.Get(i1)==list2.Get(i2)){ break; } else{ ++i2;} }//while if(list2.Get(i2)=='\\0') { ist2.Insert(i2,list1.Get(i1)); i2=1; ++i1; }

else{ ++i1;i2=1;} }//while

while(list2.Get(i2)!='\\0'){ i2++;} list2.Delete(i2);//将list2尾部的‘\\0’删除 }

（4）求集合A和B的差：

对单链表B中的每个元素x，在单链表A中进行查找，若存在和x相同的结点，则将该结点从单链表A中删除。

template

void Deduct(linklist &list1,linklist &list2){ //list2-list1;

int i1=1,i2=1;//分别表示链表list1和list2的位置 while(list2.Get(i2)!='\\0') { while(list1.Get(i1)!='\\0') { if(list2.Get(i2)==list1.Get(i1)){ break;} else{ ++i1;} }//while if(list1.Get(i1)!='\\0'){ list2.Delete(i2); i1=1;} else{ ++i2;i1=1; } }//while

list2.Delete(i2);//将list12尾部的'\\0'删除 }

3.详细编码设计

1：链表的类

#ifndef LINKLIST_H #define LINKLIST_H

template struct Node{

DataType data;//结点的数据域

Node *next;//结点的指针域 };//用结点表示链表中的每一个的元素

template class linklist{ private:

Node *first;//链表的头结点

public:

linklist();//构造一个空的链表

linklist(DataType a[],int Alength);//构造一个带有参数的链表 ~linklist();//释放出链表的空间 void Print();//打印出链表

DataType Get(int i);//按位查找 int Locate(DataType x);//按值查找 int GetLength();//求长度

void Insert(int i,DataType x);//插入元素 void Delete(int i);//删除 //类的友元函数

friend bool IsEqual(Node *a,Node *b); //判断两个集合是否相等

Friend void AndSet(linklist &list1,linklist &list2); //计算两个集合的交集的部分

friend void OrSet(linklist &list1,linklist &list2); //计算两个集合的并集

friend void Deduct(linklist &list1,linklist &list2); //计算两个集合的差 }; #endif

2:函数的实现

#include using namespace std; #include\

template linklist::linklist(){ first=new Node; first->next=NULL;

}//构造一个带有头结点的链表

template

linklist::linklist(DataType a[],int Alength){ Node *s;//动态的结点 first=new Node; first->next=NULL;

/*头插分，将元素始终插入到头结点的后面 for(int i=0;i; s->data=a[i];

s->next=first->next; first->next=s; }*/

//尾插法

Node *rear;//尾指针 rear=first;//尾指针的初始化 for(int i=0;i

s=new Node;//申请动态的结点 s->data=a[i]; rear->next=s; rear=s; }

rear->next=NULL;//尾指针的指针域始终无空 }//带有参数的构造函数

template

linklist::~linklist(){ Node *work;

Node *p;//临时的指针保存要删除的结点的地址 work=first;//工作指针开始时指向头结点

/*工作指针指向头结点，可以把头结点在内的 *链表中的所以的元素删除 */

while(work!=NULL){ p=work; delete p;

work=work->next; }

}//释放出链表的空间

template

void linklist::Print(){ Node *work; work=first->next;//工作指针 cout<<\链表为:\

while(work!=NULL){ cout<data; work=work->next; }

cout<

template

DataType linklist::Get(int i){ Node *work; work=first;//工作指针 int count;//计数器

for(count=1;count<=i;count++){ if(work==NULL){ throw\查找的位置不合理\ } else{work=work->next; } }

return work->data;//返回位置i的元素 }//按位查找

template

int linklist::Locate(DataType x){ Node *work; work=first->next;//工作指针 int count=0;//计数器 while(work!=NULL){ if(work->data==x){ return ++count; }

else{ work=work->next; } }

throw\查找的元素不存在\}//按值查找

template

int linklist::GetLength(){ Node *work; work=first->next;//工作指针 int length=0;//链表的长度

while(work!=NULL){ length++; work=work->next; }

return length; }//求链表的长度

template

void linklist::Insert(int i,DataType x){

Node *work;

work=first;//工作的指针开始指向头结点

//要在位置i插入元素，首先要找到位置i-1 for(int j=1;jnext;} }

Node *s;

s=new Node;//申请动态的新结点

s->data=x;

s->next=work->next; work->next=s; }//插入操作

template

void linklist::Delete(int i){ Node *work; work=first;//工作指针

//要删除位置i的元素，首先要找到i-1位置的元素 for(int j=1;jnext; } }//for

Node *p;

p=work->next;//指向位置i的指针 work->next=p->next;

delete p;//删除位置i的结点 }//删除函数中的元素

//类的判等，并，交，差，等友元函数

//判断两个集合是否相等 template

bool IsEqual(linklist &list1,linklist &list2){ int i1=1,i2=1;//分别表示链表list1和list2的位置 //当list1不为'\\0'时循环

if(list1.GetLength()!=list2.GetLength())

{ return false; } else{

while(list1.Get(i1)!='\\0') { while(list2.Get(i2)!='\\0') { if(list1.Get(i1)!=list2.Get(i2)){i2++;} else{break;} }//while

if(list2.Get(i2)!='\\0'){ i1++;i2=1; } else{ return false;} }//while return true; }//else }

//计算两个集合的交集,用list1保存结果 template

void AndSet(linklist &list1,linklist &list2){ int i1=1,i2=1;//分别表示链表list1和list2的位置 while(list1.Get(i1)!='\\0') { while(list2.Get(i2)!='\\0') { if(list1.Get(i1)==list2.Get(i2)){ break; } else{ ++i2;} }//while if(list2.Get(i2)!='\\0') { ++i1; i2=1;} else { list1.Delete(i1); i2=1;} }//while

list1.Delete(i1);//将'\\0'删除 }

//计算两个集合的并集，用list2保存结果 template

void OrSet(linklist &list1,linklist &list2){ int i1=1,i2=1;//分别表示链表list1和list2的位置 while(list1.Get(i1)!='\\0') { while(list2.Get(i2)!='\\0') { if(list1.Get(i1)==list2.Get(i2)){ break; }

else{ ++i2;} }//while if(list2.Get(i2)=='\\0') { ist2.Insert(i2,list1.Get(i1)); i2=1; ++i1; } else{ ++i1;i2=1;} }//while

while(list2.Get(i2)!='\\0'){ i2++;} list2.Delete(i2);//将list2尾部的‘\\0’删除 }

//计算两个集合的差,结果用list2保存 template

void Deduct(linklist &list1,linklist &list2){ //list2-list1;

int i1=1,i2=1;//分别表示链表list1和list2的位置 while(list2.Get(i2)!='\\0') { while(list1.Get(i1)!='\\0') { if(list2.Get(i2)==list1.Get(i1)){ break;} else{ ++i1;} }//while if(list1.Get(i1)!='\\0'){ list2.Delete(i2); i1=1;} else{ ++i2;i1=1; } }//while

list2.Delete(i2);//将list12尾部的'\\0'删除 }

3：主函数的运用 #include using namespace std; #include\

/*集合的运算：判断集合是否相等 *集合的交，并，差的运算 */

int main(){

const int Alength=6,Blength=6; char b[]=\

linklist list1(a,Alength),list2(b,Blength); //比较两个集合是否相等

cout<

//计算两个集合的并集部分 OrSet(list1,list2); list2.Print();

//计算两个集合的差 Deduct(list1,list2); list2.Print(); system(\ return 0; }

四．运行与测试 测试的数据:

const int Alength=6,Blength=5; char b[]=\测试的结果 :

//比较两个集合是否相等 结果=0；

//计算两个集合的交集部分，用list1来保存 AndSet(list1,list2); list1.Print(); 结果=1 3 5

//计算两个集合的并集部分 OrSet(list1,list2); list2.Print(); 结果：1 2 3 4 5 6

//计算两个集合的差 Deduct(list1,list2); list2.Print(); 结果：6

五．总结与心得

通过此次实验更加熟悉了单链表的应用，对于书上的关于运用单链表进行集合的判等和交并差，进行了运行和测试，书上的知识学了要回去应用，做到学以致用，不然也只是起到纸上谈兵的效果。这次课程让我明白设计思路十分重要，在进行程序设计之前，自己一定要有完善的思路，才能顺利写出代码，但我能看出自己的不足，我需要掌握更多的知识，更加灵活的应用知识。

linklist list1(a,Alength),list2(b,Blength); //比较两个集合是否相等

cout<

//计算两个集合的并集部分 OrSet(list1,list2); list2.Print();

//计算两个集合的差 Deduct(list1,list2); list2.Print(); system(\ return 0; }

四．运行与测试 测试的数据:

const int Alength=6,Blength=5; char b[]=\测试的结果 :

//比较两个集合是否相等 结果=0；

//计算两个集合的交集部分，用list1来保存 AndSet(list1,list2); list1.Print(); 结果=1 3 5

//计算两个集合的并集部分 OrSet(list1,list2); list2.Print(); 结果：1 2 3 4 5 6

//计算两个集合的差 Deduct(list1,list2); list2.Print(); 结果：6

五．总结与心得

通过此次实验更加熟悉了单链表的应用，对于书上的关于运用单链表进行集合的判等和交并差，进行了运行和测试，书上的知识学了要回去应用，做到学以致用，不然也只是起到纸上谈兵的效果。这次课程让我明白设计思路十分重要，在进行程序设计之前，自己一定要有完善的思路，才能顺利写出代码，但我能看出自己的不足，我需要掌握更多的知识，更加灵活的应用知识。

本文来源：https://www.bwwdw.com/article/16k2.html