链表建立、合并与拆分

《链表建立、合并与拆分》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2链表的建立、合并与拆分【实验简介】链表是用链接存储的方式来表达线性表，它用指针表示结点间的逻辑关系，链表适用于插入或删除频繁，存储空间需求不定的情形。【实验内容】定义一个链表存储的线性表，除已给出的表元素插入、删除、查找等基本操作外，再提供表的合并、拆分和逆置等操作。在应用程序中建立两个整型的单链表对象A和B，应用线性表的基本操作对表的实例对象进行操作测试。1.设线性链表A=(a1,a2,…,am),，B=(b1,b2,…bm)，按下列规则合并A，B为线性表C的算法，即使得C=(a1,b1,…,am,bm,b(m+

2、1),…,bn)当m<=n或C=(a1,b1,…,an,bn,a(n+1),…,am)当m>nC表利用A表和B表中的结点空间构成。2.将C表原地逆置。3.将C表的中偶数和奇数分别链接为两个循环链表D和E。说明：每一次合并、拆分和逆置等操作的结果均要输出。【主要代码】#includeusingnamespacestd;templatestructLinkNode//结点类{Tdata;LinkNode*link;LinkNode(LinkNode*ptr=NULL){li

3、nk=ptr;}//仅初始化指针成员的构造函数LinkNode(constT&item,LinkNode*ptr=NULL)//初始化数据成员和指针成员的构造函数{data=item;link=ptr;}};templateclassList//链表类{private:LinkNode*first;//链表头指针public:List(){first=newLinkNode;}//构造函数List(T&x){first=newLinkNode(x);}//构造函数List(Li

4、st&L);//复制构造函数~List(){MakeEmpty();}voidMakeEmpty();//将链表置为空表//intLength()const;//计算链表长度LinkNode*GetHead()const{returnfirst;}//返回附加头结点地址voidSetHead(LinkNode*p){first=p;}//设置附加头结点地址LinkNode*Search(Tx);//搜索含数据x的元素8LinkNode*Locate(inti);//搜索第i个元素的地址T*Ge

5、tData(inti,T&x);//取第i个元素的值boolSetData(inti,T&x);//用x修改第i个元素的值boolInsert(inti,T&x);//在第i个元素后插入xboolRemove(inti,T&x);//删除第i个元素，x返回该元素的值boolIsMmpty()const//判断表是否为空{returnfirst->link=NULL?true:false;}voidSort();voidInput(TendTag);////从前端输入，当输入字符endTag时结束输入voidOutpu

6、t();//输出List&operator=(List&L);//重载函数：赋值};template//将链表置为空表voidList::MakeEmpty(){LinkNode*q;while(first->link!=NULL){q=first->link;//保存被删结点first->link=q->link;//从链上摘下该结点deleteq;//删除}};template//计算链表长度intList::Length()const{ListNod

7、e*p=first->link;intcount=0;while(p!=NULL)//逐个结点检测{p=p->link;count++;}returncount;};template//在表中搜索含数据x的结点,搜索成功时函数返该结点地址;否则返回NULL。LinkNode*List::Search(Tx){LinkNode*current=first->link;while(current!=NULL&¤t->data!=x)current=current->li

8、nk;returncurrent;8};template//函数返回表中第i个元素的地址。若i<0或i超出表中结点个数，则返回NULL。LinkNode*List::Locate(inti){if(i<0)returnNULL;//i不合理LinkNode*current=first;intk=0;while(