数据结构与算法 p45-04
假设有两个按元素值递增有序排列的线性表A和B，均以单链表作为其存储结构
设计一个算法将A和B归并一个按元素值递减的有序排列的线性表C
并要求利用原表（即A表和B表）的结点空间构造表C
#include<iostream.h>//cout,cin
typedef int T;template<class T>
struct Node
{T data;//数据域，存放表元素Node *next;//指针域，指向下一个结点
};template <class T>
class LinkList
{private:Node<T> *Head;// 链表头指针public:LinkList() ;//构造函数， 创建空链表~LinkList();//析构函数，删除表空间void CreateList(int n);//创建具有n个元素的线性链表void createlist(int n,int a[]);void Delete(int i);//删除表中第i个元素T GetElem(int i);//获取第i个元素的值int Length();//测表长void ListDisplay();//输出表元素
};
template<class T>
LinkList<T>::LinkList()
{//构建函数，建一空链表Head=new Node<T>;Head->next=NULL;
}template<class T>
LinkList<T>::~LinkList()
{//析构函数，释放链表所占空间Node<T> *p;while(Head)//从头结点开始，依次释放结点{p=Head;Head=Head->next;delete p;}Head=NULL;//头结点指向空
}template<class T>
void LinkList<T>::CreateList(int n)
{//尾插法(正序)创建具有n个元素的线性表Node<T> *p,*s;//设置工作指针。p指向尾结点int start,step;p=Head;cout<<"请依次输入初始值和步长："<<endl;cin>>start>>step;for(int i=1;i<=n;i++){s=new Node<T>;//新建元素结点s->data=start+(i-1)*step;//输入新建数据元素值s->next=p->next;//新结点链入表尾p->next=s;p=s;}
}template<class T>
void LinkList<T>::createlist(int k,int a[])
{//尾插法(正序)创建具有n个元素的线性表Node<T> *p,*s;//设置工作指针。p指向尾结点p=Head;for(int i=1;i<=k;i++){s=new Node<T>;//新建元素结点s->data=a[i-1];//输入新建数据元素值s->next=p->next;//新结点链入表尾p->next=s;p=s;}
}template <class T>
void LinkList<T>::Delete (int i)
{//删除指定位置元素Node<T> *p,*q;//设置工作指针p=Head;//查找从头结点开始int j=0;//计数器初始化while(p->next && j<i-1)//p定位到删除点的前驱{p=p->next;//j++;}if(!p->next||j>i-1) //删除位置不合理throw"位置异常";else //删除位置合理{q=p->next;// 暂存删除结点位置p->next=q->next;//从链表中摘除删除结点delete q;// 释放删除点}
}template<class T>
T LinkList<T>::GetElem(int i)
{//获取第i个元素的值Node<T> *p;//设置工作指针p=Head->next;//从首结点开始int j=1;//计数器初始化while(p&&j<i)//定位到第i个元素结点{p=p->next;j++;}if(!p||j>i)//定位位置不合理：空表或i小于0或i大于表长throw "位置";else //位置合理return p->data;
}template <class T>
int LinkList<T>::Length()
{//测表长int len=0;//计数器初始化Node<T> *p;//设置工作指针p=Head;//指向头结点while(p->next){len++;p=p->next;}return len;//返回表长
}template <class T>
void LinkList<T>::ListDisplay()
{//遍历显示链表Node<T> *p;//设置工作指针p=Head->next;//从首元结点开始遍历int i=1;//元素位序while(p){cout<<p->data<<" ";p=p->next;i++;}cout<<endl;
}int main()
{int k=0,la_len,lb_len,a,b,array[100],i,j;LinkList<int> La,Lb,Lc;cout<<"请输入要创建A集合中元素个数:"; cin>>la_len; La.CreateList(la_len); cout<<endl<<"La:"<<"\t"; La.ListDisplay(); cout<<endl<<"请输入要创建的B集合中元素个数:"; cin>>lb_len; Lb.CreateList(lb_len); cout<<endl<<"Lb:"<<"\t"; Lb.ListDisplay(); int a_length=La.Length();int b_length=Lb.Length();for(i=a_length;i>0;i--){try{a=La.GetElem(i);}catch(char *err){cout<<err<<endl;}array[k]=a;k++;La.Delete(i);} for(j=a_length;j>0;j--){try{ b=Lb.GetElem(j); }catch(char *err){ cout<<err<<endl; }array[k]=b;k++;Lb.Delete(j);}for(i=0;i<k;i++)for(j=k-1;j>i;j--){ if(array[j]>array[i]){ int temp=array[j];array[j]=array[i];array[i]=temp;}if(array[j]==array[i])for(int w=j;w<k;w++){array[j]=array[j+1];k--;} }cout<<endl<<"A集合和B集合的并集C的元素如下:"; Lc.createlist(k,array);cout<<endl<<"Lc:"<<"\t"; Lc.ListDisplay();cout<<endl;return 0;
}
