链表的建立、合并与拆分.docVIP

链表的建立、合并与拆分定义一个链表存储的线性表，除已给出的表元素插入、删除、查找等基本操作外，再提供表的合并、拆分和逆置等操作。在应用程序中建立两个整型的单链表对象A和B，应用线性表的基本操作对表的实例对象进行操作测试。 1. 设线性链表A=(a1,a2,…,am),，B=(b1,b2,…bm)，按下列规则合并A，B为线性表C的算法，即使得 C = (a1,b1,…,am,bm, b (m+1),…,bn) 当m=n 或 C = (a1,b1,…,an,bn, a(n+1),…,am) 当mn C表利用A表和B表中的结点空间构成。 2. 将C表原地逆置。 3. 将C表的中偶数和奇数分别链接为两个循环链表D和E。 每一次合并、拆分和逆置等操作的结果均要输出。#includeiostream using namespace std; template class T struct LinkNode //结点类 { T data; LinkNodeT *link; LinkNode(LinkNodeT *ptr=NULL){link=ptr;} //仅初始化指针成员的构造函数 LinkNode(const T item,LinkNodeT *ptr=NULL) //初始化数据成员和指针成员的构造函数 {data=item;link=ptr;} }; template class T class List //链表类 { private: LinkNodeT *first; //链表头指针 public: List(){first=new LinkNodeT;} //构造函数 List(T x){first=new LinkNodeT(x);} //构造函数 List(List L); //复制构造函数 ~List(){MakeEmpty();} void MakeEmpty(); //将链表置为空表// int Length()const; //计算链表长度 LinkNodeT *GetHead()const{return first;} //返回附加头结点地址 void SetHead(LinkNodeT *p){first=p;} //设置附加头结点地址 LinkNodeT *Search(T x); //有哪些信誉好的足球投注网站含数据x的元素 LinkNodeT *Locate(int i); //有哪些信誉好的足球投注网站第i个元素的地址 T *GetData(int i, T x); //取第i个元素的值 bool SetData(int i,T x); //用x修改第i个元素的值 bool Insert(int i,T x); //在第i个元素后插入x bool Remove(int i,T x); //删除第i个元素，x返回该元素的值 bool IsMmpty()const //判断表是否为空 {return first-link=NULL?true:false;} void Sort(); void Input(T endTag); ////从前端输入，当输入字符endTag时结束输入 void Output(); //输出 ListT operator=(ListT L); //重载函数：赋值 }; template class T //将链表置为空表 void ListT::MakeEmpty() { LinkNodeT *q; while(first-link!=NULL) { q=first-link; //保存被删结点 first-link=q-link; //