단일 체인 표 는 집합 적 인 합병, 교차, 차 연산 을 실현 한다.
6463 단어 데이터 구조 과정 노트
#include //
using namespace std;
template
struct Node
{
T data;
Node *next; //
};
template
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 *first; //
};
/*
* :
* :
* :
* :
* :
*/
template
LinkList:: LinkList( )
{
first=new Node; first->next=NULL;
}
/*
* :
* : a[], n
* : a[] n
* :
* :
*/
template
LinkList:: LinkList(T a[ ], int n)
{
first=new Node; //
Node *r,*s;
r=first; //
for (int i=0; i; s->data=a[i]; //
r->next=s; r=s; //
}
r->next=NULL; // ,
}
/*
* :
* :
* :
* :
* :
*/
template
LinkList::~LinkList()
{
cout< *q;
while(first!=NULL)
{
q=first;//cout<data<next;
delete q;
}
}
/*
* :
* : i
* : i
* :
* :
*/
template
T LinkList::Get(int i)
{
Node *p; int j;
p=first->next; j=1; // p=first; j=0;
while (p && jnext; // p
j++;
}
if (!p) throw " ";
else return p->data;
}
/*
* :
* : x
* :
* :
* :
*/
template
int LinkList::Locate(T x)
{
Node *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
void LinkList::Insert(int i, T x)
{
Node *p; int j;
p=first ; j=0; // p
while (p && jnext; // p
j++;
}
if (!p) throw " ";
else {
Node *s;
s=new Node;
s->data=x; // s, x
s->next=p->next; // s p
p->next=s;
}
}
/*
* :
* :
* :
* :
* :
*/
template
int LinkList::Length( )
{
Node *p = first->next;
int i = 0;
while(p)
{
p = p->next;
i++;
}
return i;
}
/*
* :
* : i
* : i
* :
* :
*/
template
T LinkList::Delete(int i)
{
Node *p; int j;
p=first ; j=0; // p
while (p && jnext;
j++;
}
if (!p || !p->next) throw " "; // p p
else {
Node *q; int x;
q=p->next; x=q->data; //
p->next=q->next; //
delete q;
return x;
}
}
/*
* :
* :
* :
* :
* :
*/
template
void LinkList::PrintList( )
{
Node *p;
p=first->next;
while (p)
{
cout<data<next;
}
cout<
void Unionset(LinkList &a,LinkList &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
void Unionset1(LinkList a,LinkList 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
LinkList Unionset2(LinkList a,LinkList 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
void UnionSet(LinkList&C,LinkList&A,LinkList&B)
//A∪B=C
{
//LinkList 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))C.Insert(C.Length()+1,temp);
}
//return C;
}
template
void IntersectionSet(LinkList&C,LinkList&A,LinkList&B)
//A∩B=C
{
//LinkList 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
void IntersectionSet1(LinkList&A,LinkList&B)
//A∩B=A
{
//LinkList 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
void DifferenceSet(LinkList&C,LinkList&A,LinkList&B)
//A-B=c
{
//LinkList 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);
C.Delete(pos);}
}
//return C;
}
int main( )
{
int ra[ ]={1,2,3,4,5};
LinkList A(ra,5); //
cout< B(rb,5); //
cout<C;
UnionSet(C,A,B);
cout<D;
IntersectionSet(D,A,B);
cout<E;
DifferenceSet(E,A,B);
cout<