单链表实现集合的并、交、差运算带头结点的单链表实现集合的并、交、差运算。
#include <iostream>  //引⽤输⼊输出流库函数的头⽂件
using namespace std;
template <class T>
struct Node
{
T data;
Node<T> *next;  //此处<T>也可以省略
};
template <class T>
class LinkList
{
public:
LinkList( );  //建⽴只有头结点的空链表
LinkList(T a[ ], int n);  //建⽴有n个元素的单链表
~LinkList();            //析构函数
int Length();          //求单链表的长度
T Get(int i);          //取单链表中第i个结点的元素值
int Locate(T x);      //求单链表中值为x的元素序号
void Insert(int i, T x);  //在单链表中第i个位置插⼊元素值为x的结点
T Delete(int i);        //在单链表中删除第i个结点
void PrintList( );          //遍历单链表，按序号依次输出各元素
private:
Node<T> *first;  //单链表的头指针
};
/*
*前置条件：单链表不存在
*输⼊：⽆
*功能：构建⼀个单链表
*输出：⽆
*后置条件：构建⼀个单链表
*/
template <class T>
LinkList<T>:: LinkList( )
{
first=new Node<T>; first->next=NULL;
}
/*
*前置条件：单链表不存在
*输⼊：顺序表信息的数组形式a[]，单链表长度n
*功能：将数组a[]中元素建为长度为n的单链表
*输出：⽆
*后置条件：构建⼀个单链表
*/
template <class T>
LinkList<T>:: LinkList(T a[ ], int n)
{
first=new Node<T>;  //⽣成头结点
Node<T> *r,*s;
r=first;          //尾指针初始化
for (int i=0; i<n; i++)
{
s=new Node<T>; s->data=a[i];  //为每个数组元素建⽴⼀个结点
r->next=s; r=s;      //插⼊到终端结点之后
}
r->next=NULL;    //单链表建⽴完毕，将终端结点的指针域置空
/*
*前置条件：⽆
*输⼊：⽆
*功能：⽆
*输出：⽆
*后置条件：⽆
*/
template <class T>
LinkList<T>::~LinkList()
{
cout<<"~LinkList()"<<Length()<<endl;
Node<T> *q;
while(first!=NULL)
{
q=first;//cout<<q->data<<endl;
first=first->next;
delete q;
}
}
/*
*前置条件：单链表存在
*输⼊：查询元素位置i
*功能：按位查位置为i的元素并输出值*输出：查询元素的值
*后置条件：单链表不变
*/
template <class T>
T LinkList<T>::Get(int i)
{
Node<T> *p; int j;
p=first->next;  j=1;  //或p=first;  j=0;
while (p && j<i)
{
p=p->next;      //⼯作指针p后移
j++;
}
if (!p) throw "位置";
else return p->data;
}
/*
*前置条件：单链表存在
*输⼊：查询元素值x
*功能：按值查值的元素并输出位置*输出：查询元素的位置
*后置条件：单链表不变
*/
template <class T>
int LinkList<T>::Locate(T x)
{
Node<T> *p; int j;
p=first->next; j=1;
while (p){
if(p->data==x)    return j;
else
{
p=p->next;
j++;
}
}
return 0;
*前置条件：单链表存在
*输⼊：插⼊元素x，插⼊位置i
*功能：将元素x插⼊到单链表中位置i处
*输出：⽆
*后置条件：单链表插⼊新元素
*/
template <class T>
void LinkList<T>::Insert(int i, T x)
{
Node<T> *p; int j;
p=first ; j=0;    //⼯作指针p初始化
while (p && j<i-1)
{
p=p->next;  //⼯作指针p后移
j++;
}
if (!p) throw "位置";
else {
Node<T> *s;
s=new Node<T>;
s->data=x;  //向内存申请⼀个结点s，其数据域为x      s->next=p->next;      //将结点s插⼊到结点p之后      p->next=s;
}
}
/*
*前置条件：单链表存在
*输⼊：⽆
*功能：输出单链表长度
*输出：单链表长度
*后置条件：单链表不变
*/
template <class T>
int LinkList<T>::Length( )
{
Node <T> *p = first->next;
int i = 0;
while(p)
{
p = p->next;
i++;
}
return i;
}
/*
*前置条件：单链表存在
*输⼊：要删除元素位置i
*功能：删除单链表中位置为i的元素
*输出：⽆
*后置条件：单链表删除元素
*/
template <class T>
T LinkList<T>::Delete(int i)
{
Node<T> *p; int j;
p=first ; j=0;  //⼯作指针p初始化
while (p && j<i-1)  //查第i-1个结点
{
p=p->next;
j++;
}
q=p->next; x=q->data;  //暂存被删结点
p->next=q->next;  //摘链
delete q;
return x;
}
}
/*
*前置条件：单链表存在
*输⼊：⽆
*功能：单链表遍历
*输出：输出所有元素
*后置条件：单链表不变
*/
template <class T>
void LinkList<T>::PrintList( )
{
Node<T> *p;
p=first->next;
while (p)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
/
/LinkListMain.cpp
template <typename T>
void Unionset(LinkList <T> &a,LinkList <T> &b){//right
//改变了a
T temp;
for(int i=1;i<=b.Length();i++)
{
temp=b.Get(i);
if(!a.Locate(temp))a.Insert(a.Length()+1,temp);
}
}
template <typename T>
void Unionset1(LinkList <T> a,LinkList <T> b){
//wrong: _CrtIsValidHeapPointer
//因为函数返回时a，b被析构
T temp;
for(int i=1;i<=b.Length();i++)
{
temp=b.Get(i);
if(!a.Locate(temp))a.Insert(a.Length()+1,temp);
}
}
template <typename T>
LinkList <T> Unionset2(LinkList <T> a,LinkList <T> b){
//wrong: _CrtIsValidHeapPointer
//因为函数返回时a，b被析构
T temp;
for(int i=1;i<=b.Length();i++)
{
temp=b.Get(i);
if(!a.Locate(temp))a.Insert(a.Length()+1,temp);
}
return a;
}
template <typename T>
void UnionSet(LinkList<T>&C,LinkList<T>&A,LinkList<T>&B) //A∪B=C
int i;
for(i=1;i<=A.Length();i++)
{
temp=A.Get(i);
C.Insert(C.Length()+1,temp);
}
for(i=1;i<=B.Length();i++)
{
temp=B.Get(i);
if(!A.Locate(temp))C.Insert(C.Length()+1,temp);
}
//return C;
}
template <typename T>
void IntersectionSet(LinkList<T>&C,LinkList<T>&A,LinkList<T>&B) //A∩B=C
{
//LinkList<T> C;
T temp;
int i;
for(i=1;i<=B.Length();i++)
{
temp=B.Get(i);
if(A.Locate(temp))C.Insert(C.Length()+1,temp);
}
//return C;
}
template <typename T>
void IntersectionSet1(LinkList<T>&A,LinkList<T>&B)
//A∩B=A
{数组和链表
/
/LinkList<T> C;
T temp;
int i;
for(i=1;i<=A.Length();i++)
{
temp=A.Get(i);
if(B.Locate(temp)==0){A.Delete(i);i--;}
}
//return C;
}
template <typename T>
void  DifferenceSet(LinkList<T>&C,LinkList<T>&A,LinkList<T>&B) //A-B=c
{
//LinkList<T> C;
T temp;
int i;
for(i=1;i<=A.Length();i++)
{
temp=A.Get(i);
C.Insert(C.Length()+1,temp);
}
for(i=1;i<=B.Length();i++)
{
temp=B.Get(i);
if(A.Locate(temp)!=0){
int pos=C.Locate(temp);

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。