欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LinkedSet

程序员文章站 2022-05-29 11:54:25
...
改了很久的bug :oops:

#ifndef LINKEDSET_H
#define LINKEDSET_H

#include<stdlib.h>
#include<iostream>
using namespace std;
template<typename T>
class SetNode{
public:
T data;
SetNode<T>* link;
SetNode():link(NULL){
}
SetNode(const T& t,SetNode<T> *next=NULL):data(t),link(next){
}
};

template<typename T>
class LinkedSet{
private:
SetNode<T> *first,*last;
public:
LinkedSet(){first=last=new SetNode<T>();}
LinkedSet(LinkedSet<T>& R);
~LinkedSet(){
makeEmpty();
delete first;
}
void makeEmpty(){
SetNode<T> *p = first->link;
SetNode<T> *pre;
while(p!=NULL){
pre = p;
delete pre;
p = p->link;
}
}

bool addMember(const T& x);
bool delMember(const T& x);
LinkedSet<T>& operator=(LinkedSet<T>& R);
LinkedSet<T>& operator+(LinkedSet<T>& R);
LinkedSet<T>& operator*(LinkedSet<T>& R);
LinkedSet<T>& operator-(LinkedSet<T>& R);
bool Contains(const T& x);
bool operator==(LinkedSet<T>& R);
friend ostream& operator<<(ostream& out,LinkedSet<T>& R){
SetNode<T> *node = R.first->link;
while(node!=NULL){
out << node->data << " ";
node = node->link;
}
out << endl;
return out;
}

bool Min(T& x);
bool Max(T& x);

};

template<typename T>
LinkedSet<T>::LinkedSet(LinkedSet<T> &R)
{
SetNode<T> *src = R.first->link;
first = last = new SetNode<T>;
while(src!=NULL){
last->link = new SetNode<T>(src->data);
src = src->link;
last = last->link;
}
}

template<typename T>
bool LinkedSet<T>::Contains(const T &x)
{
SetNode<T>* temp = first->link;
while(temp!=NULL&&temp->data<x)
temp = temp->link;
if(temp!=NULL&&temp->data==x)
return true;
return false;
}

template<typename T>
bool LinkedSet<T>::addMember(const T &x)
{
SetNode<T> *pre,*node;
node = first->link;
pre = first;
while(node!=NULL&&node->data<x){
pre = node;
node = node->link;
}
if(node!=NULL&&node->data==x){
return false;
}else{
SetNode<T>* s = new SetNode<T>(x);
s->link = node;
pre->link = s;
if(node==NULL)
last=s;
}
return true;
}

template<typename T>
bool LinkedSet<T>::delMember(const T &x)
{
SetNode<T> *pre,*node;
node = first->link;
while(node!=NULL&&node->data!=x){
pre = node;
node = node->link;
}
if(node==NULL)//没找到
return false;
pre->link = node->link;
if(node==last)
last = pre;
delete node;
return true;
}

template<typename T>
LinkedSet<T>& LinkedSet<T>::operator=(LinkedSet<T>& R)
{
SetNode<T> *p = R.first->link;
SetNode<T> *node = first = new SetNode<T>;
while(p!=NULL){
node->link = new SetNode<T>(p->data);
p = p->link;
node = node->link;
}
node->link = NULL;
last = node;
return *this;
}

/*
将集合this与集合R的并积,将计算结果放入temp中返回
*/
template<typename T>
LinkedSet<T>& LinkedSet<T>::operator+(LinkedSet<T>& R)
{
SetNode<T> *pa = first->link;
SetNode<T> *pb = R.first->link;
//LinkedSet<T> temp我之前这么写总是有问题在这个函数里是对的,然后跑出去的返回
//值就是脏数据,换成指针后好了,*,-也是这种情况,这是为什么呢?(平台g++)
LinkedSet<T> *temp = new LinkedSet<T>;
SetNode<T> *pc = temp->first;
while(pa!=NULL&&pb!=NULL){
if(pa->data==pb->data){
pc->link = new SetNode<T>(pa->data);
pa = pa->link;
pb = pb->link;
}else if(pa->data<pb->data){
pc->link = new SetNode<T>(pa->data);
pa = pa->link;
}else{
pc->link = new SetNode<T>(pb->data);
pb = pb->link;
}
pc = pc->link;
}
while(pa!=NULL){
pc->link = new SetNode<T>(pa->data);
pc = pc->link;
pa = pa->link;
}
while(pb!=NULL){
pc->link = new SetNode<T>(pb->data);
pc = pc->link;
pb = pb->link;
}
pc->link = NULL;
temp->last = pc;
return *temp;
}

template<typename T>
LinkedSet<T>& LinkedSet<T>::operator*(LinkedSet<T>& R)
{
SetNode<T> *pa = first->link;
SetNode<T> *pb = R.first->link;
LinkedSet<T> *temp = new LinkedSet<T>;
SetNode<T> *pc = temp->first;
while(pa!=NULL&&pb!=NULL){
if(pa->data==pb->data){
pc->link = new SetNode<T>(pa->data);
pa = pa->link;
pb = pb->link;
pc = pc->link;
}else{
if(pa->data<pb->data){
pa = pa->link;
}else{
pb = pb->link;
}
}
}
temp->last = pc;
pc->link = NULL;
return *temp;
}

template<typename T>
LinkedSet<T>& LinkedSet<T>::operator-(LinkedSet<T>& R)
{
SetNode<T> *pa = first->link;
SetNode<T> *pb = R.first->link;
LinkedSet<T> *temp = new LinkedSet<T>;
SetNode<T> *pc = temp->first;
while(pa!=NULL&&pb!=NULL){
if(pa->data==pb->data){
pb = pb->link;
pa = pa->link;
}else if(pa->data<pb->data){
pc->link = new SetNode<T>(pa->data);
pa = pa->link;
pc = pc->link;
}else{
pb = pb->link;
}
}
while(pa!=NULL){
pc->link = new SetNode<T>(pa->data);
pa = pa->link;
pc = pc->link;
}
pc->link = NULL;
temp->last = pc;
return *temp;
}

template<typename T>
bool LinkedSet<T>::operator==(LinkedSet<T>& R)
{
SetNode<T> *pa = first->link;
SetNode<T> *pb = R.first->link;
bool equal = true;
while(pa!=NULL&&pb!=NULL){
if(pa->data!=pb->data){
equal = false;
break;
}
pa = pa->link;
pb = pb->link;
}
if(pa!=NULL||pa!=NULL){
equal = false;
}
return equal;
}

#endif // LINKEDSET_H


#include"linkedSet.h"
#include<iostream>
using namespace std;

int main()
{
LinkedSet<int> ls1,ls2;
for(int i=0;i<10;i++){
ls1.addMember(i);
if(i%2==0)
ls2.addMember(i);
}
LinkedSet<int> ls3=ls1+ls2;
cout << ls3;
ls3 = ls1*ls2;
cout << ls3;
ls3 = ls1-ls2;
cout << ls3;

}

0 1 2 3 4 5 6 7 8 9
0 2 4 6 8
1 3 5 7 9
相关标签: GCC

推荐阅读