//这里主要是采用单链表实现两个集合的并集
//相关头文件定义；
#ifndef _C_H_
#define _C_H_
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <cstdarg>
#include <assert.h>
using namespace std;
#endif;
//线性表抽象类的定义；
#ifndef _ALIST_H_
#define _ALIST_H_
template<typename T> class AList
{
public:
void ClearList();
bool ListEmpty() const;
int LocateElem(T e, bool(*eq)(T, T)) const;
bool PriorElem(T e, bool(*eq)(T, T), T &pre_e) const;
bool NextElem(T e, bool(*eq)(T, T), T &next_e) const;
bool ListDelete(int i, T &e);
void ListTraverse(void(*visit)(T*)) const;
virtual bool GetElem(int i, T &e) const = 0;//纯虚函数;
virtual bool ListInsert(int i, T e) = 0;
virtual int ListLength() const = 0;
};
#endif;
//链表节点定义；
#ifndef _LONDE_H_
#define _LONDE_H_
template<typename T> struct LNode
{
T data;
LNode<T> *next;
};
#endif;
//单链表类定义；
#ifndef _LINKLIST_H_
#define _LINKLIST_H_
#include "AList.h"
#include "C.h"
#include "LNode.h"
template<typename T> class LinkList :public AList < T >
{
friend void MergeList(LinkList<T>&, LinkList<T>&);
protected:
LNode<T> *Head;
public:
LinkList()
{
Head = new LNode < T > ;//产生头结点;
assert(Head != NULL);
Head->next = NULL;
}
~LinkList()
{
ClearList();
delete Head;
}
//常成员函数，不会改变对象的值;重置线性表为空;
void ClearList() const
{
LNode<T> *p, *q;
p = Head->next;
Head->next = NULL;
while (p != NULL)
{
q = p->next;
delete p;
p = q;
}
}
//若线性表为空，则返回true，否则返回false;
bool ListEmpty() const
{
return Head->next == NULL;
}
int ListLength() const
{
int i = 0;
LNode<T> *p;
p = Head->next;
while (p != NULL)
{
i++;
p = p->next;
}
return i;
}
bool GetElem(int i, T &e) const
{
int j = 1;
LNode<T> *p;
p = Head->next;
while (p != NULL && j < i)
{
j++;
p = p->next;
}
if (p == NULL || j > i)
return false;
else
e = p -> data;
return true;
}
int LocateElem(T e, bool(*eq)(T, T))const
{
int i = 0;
LNode<T> *p = Head->next;
while (p != NULL && !eq(e, p->data))
{
i++;
p = p->next;
}
if (p == NULL)
return 0;
else
return i;
}
bool PriorElem(T e, bool(*eq)(T, T), T &pre_e) const
{
LNode<T> *p, *q;
p = Head->next;
while (p != NULL && p -> next != NULL)
{
q = p->next;
if (eq(q->data, e))
{
pre_e = p->data;
return true;
}
p = q;
}
return false;
}
bool NextElem(T e, bool(*eq)(T, T), T &next_e) const
{
LNode<T> *q, *p;
p = Head->next;
while (p != NULL && p->next != NULL)
{
q = p->next;
if (eq(p->data, e))
{
next_e = q->data;
return true;
}
p = q;
}
return false;
}
bool ListInsert(int i, T e)
{
LNode<T> *p, *q;
int j = 0;
p = Head;
while (p != NULL && j < i - 1)
{
j++;
p = p->next;
}
if (p == NULL || j > i - 1)
return false;
q = new LNode < T > ;
if (q == NULL)
return false;
q->data = e;
q->next = NULL;
q->next = p->next;
p->next = q;
return true;
}
bool ListDelete(int i, T &e) const
{
int j = 1;
LNode<T> *p, *q;
p = Head->next;
while (p != NULL && j < i - 1)
{
j++;
p = p->next;
}
if (p == NULL || j > i - 1)
return false;
q = p->next;
e = q->data;
p->next = q->next;
delete q;
return true;
}
void ListTraverse(void(*visit)(T*));
};
template<typename T>
void LinkList<T>::ListTraverse(void(*visit)(T*))
{
LNode<T> *p;
p = Head->next;
while (p != NULL)
{
visit(&p->data);
p = p->next;
}
cout << endl;
}
#endif;
//实现并集；
#include "C.h"
#include "LinkList.h"
typedef int T;
void MergeList(LinkList<T> &La, LinkList<T> &Lb)
{
LNode<T> *pa, *pb, *p;
pa = La.Head -> next;
pb = Lb.Head -> next;
p = La.Head;
while (pa && pb)
{
if (pa->data <= pb->data)
{
p->next = pa;
p = pa;
pa = pa->next;
}
else
{
p->next = pb;
p = pb;
pb = pb->next;
}
}
p->next = pa ? pa : pb;//插入剩余段;
Lb.Head->next = NULL;//将表b置空;
}
void print(T* c)
{
cout << *c << " ";
}
void main()
{
LinkList<T> La, Lb;
for (int i = 1; i <= 5; i++)
{
La.ListInsert(i,i);
Lb.ListInsert(i,2 * i);
}
cout << "La = ";
La.ListTraverse(print);
cout << "Lb = ";
Lb.ListTraverse(print);
MergeList(La,Lb);
cout << "New La = ";
La.ListTraverse(print);
cout << "New Lb = ";
Lb.ListTraverse(print);
system("pause");
}
