2022年2022年链表的建立、合并与拆分C++ .pdf

《2022年2022年链表的建立、合并与拆分C++ .pdf》由会员分享，可在线阅读，更多相关《2022年2022年链表的建立、合并与拆分C++ .pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、点空间构成。2. 将 C 表原地逆置。3. 将 C 表的中偶数和奇数分别链接为两个循环链表D 和 E。说明：每一次合并、拆分和逆置等操作的结果均要输出。【主要代码】#include #include class List; struct LinkNode /定义一个结点,有数据域和指针域 int data; LinkNode * link; LinkNode(LinkNode *ptr=NULL)/构造函数link=ptr; LinkNode(const int & item,LinkNode *ptr=NULL) /构造函数data=item;link=ptr; ; class List/线

3、性链表类 protected: LinkNode *first; public: List()first=new LinkNode();/构造函数List(const int &x)first=new LinkNode(x);/带一个整型参数的构造函数List(List & L);/复制构造函数List jishu(List &L);/存放数据为奇数的线性链表函数List oushu(List &L);/存放数据为偶数的线性链表函数void makeEmpty(); /将线性链表置空List()makeEmpty();/析构函数void setData(int i,int &x);/给线性链表

4、的第i个结点赋值 xbool getData(int i,int &x);/获取线性链表的第i个结点的值 ,并把他存储在变量x里LinkNode *Locate(int i);/定位线性链表的第i个结点 ,并返回该结点的指针LinkNode *getHead()constreturn first;/获取线性链表的头指针int Length()const /求线性链表的长度 LinkNode *p=first-link;int count=0; while(p!=NULL) p=p-link;count+; return count; bool Insert(int i,int &x);/在第

5、i个元素后插入x void input(); /在链表里面输入值。void output(); /输出链表里面的元素。void nizhi(); /将线性链表逆置void fenList(List &a,List &b);/将线性链表拆分为两个链表,其中 a链/表存放原链表中数据域为奇数的结点,b链表存放原链表中数据域为偶数的链表LinkNode *search(); /搜索 x在线性链表中的位置 ,函数返回表项序号名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页

6、- - - - - - - - - 2 bool Remove(int &x); /将链表中第 i个结点的元素删除List hebing(List &A,List &B);/合并链表的函数 ,并按照题目要求的顺序合并void xunhuan(); /把一个线性单链表置为循环线性链表; List:List(List &L)/复制构造函数 int value; LinkNode *srcptr=L.getHead(); LinkNode *destptr=first=new LinkNode; while(srcptr-link!=NULL) value=srcptr-link-data; des

7、tptr-link=new LinkNode(value); destptr=destptr-link; srcptr=srcptr-link; destptr-link=NULL; List List:jishu(List &L)/存放数据为奇数的链表 int value; LinkNode *srcptr=L.getHead(); LinkNode *destptr=first=new LinkNode; while(srcptr-link!=NULL) if(srcptr-link-data%2!=0) value=srcptr-link-data; destptr-link=new L

8、inkNode(value); destptr=destptr-link; srcptr=srcptr-link; destptr-link=NULL; return *this; List List:oushu(List &L)/存放数据为偶数的链表 int value; LinkNode *srcptr=L.getHead(); LinkNode *destptr=first=new LinkNode; while(srcptr-link!=NULL) if(srcptr-link-data%2=0) value=srcptr-link-data; destptr-link=new Lin

9、kNode(value); destptr=destptr-link; srcptr=srcptr-link; destptr-link=NULL; return *this; LinkNode *List:Locate(int i) if(i0)return NULL; LinkNode *current=first;int k=0; while(current!=NULL&klink;k+; return current; void List:makeEmpty() LinkNode *q; while(first-link!=NULL) q=first-link; first-link=

10、q-link; delete q; void List:setData(int i,int &x) if(idata=x; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - 3 bool List:getData(int i,int &x) if(idata;return true; bool List:Insert(int i,int &x)/线性链表的插入函数 LinkNode *current=Locate(i); if(c

11、urrent=NULL)return false; LinkNode *newNode=new LinkNode(x); if(newNode=NULL)cerr内存分配错误！ link=current-link; current-link=newNode; return true; void List:input() /线性链表的输入函数 couti; for(int j=0;jk; this-Insert(j,k); void List:output() /线性链表的输出函数 LinkNode *p=first-link; int i=1; cout 线性链表的元素为：endl; whil

12、e(p!=NULL) coutpidata=datalink; i+; void List:nizhi() /将函数的顺序逆置，使得头指针指向原链表的最后一个元素 LinkNode *pr=NULL,*h=first-link,*p; p=h-link; h-link=NULL; while(p-link!=NULL) pr=h;h=p;p=p-link;h-link=pr; p-link=h; h=p; first-link=h; void List:fenList(List &a,List &b)/把一个链表分为一个存放奇数的链表，和一个存放偶数的链表 a.jishu(*this); b.

13、oushu(*this); LinkNode *List:search() coutx; LinkNode *current=first-link; while(current!=NULL) if(current-data=x) cout 搜索成功 !link; if(current!=NULL)return current; else cout 查找失败 !endl;return NULL; bool List:Remove(int &x) cout 请输入要删除第几个数:i; LinkNode *current=Locate(i-1); 名师资料总结 - - -精品资料欢迎下载 - - -

14、 - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - 4 if(current=NULL|current-link=NULL) cout 删除失败 !link; current-link=del-link; x=del-data; delete del; cout删除的数为 :xlink!=NULL|p2-link!=NULL) if(p1-link!=NULL) value=p1-link-data; p-link=new LinkNode(value); p=p-link; p1=

15、p1-link; if(p2-link!=NULL) value=p2-link-data; p-link=new LinkNode(value); p=p-link; p2=p2-link; p-link=NULL; return *this; void List:xunhuan() LinkNode *h=this-getHead(); LinkNode *h1=h; while(h-link!=NULL) h=h-link; h-link=h1; void main() List la; la.input(); cout逆置前的线性表为：endl; la.output(); la.niz

16、hi(); cout逆置后的线性表为：endl; la.output(); la.search(); List l1,l2; la.fenList(l1,l2); cout结点数据为奇数的链表为l1：endl; l1.output(); cout结点数据为偶数的链表为l2：endl; l2.output(); cout删除前链表 l2为:endl; l2.output(); cout删除后链表 l2为:endl; int k; l2.Remove(k); l2.output(); List lb; lb.hebing(l1,l2); cout合并 l1、l2后的链表为 :endl; lb.ou

17、tput(); coutOK!data=1 P2-data=2 P3-data=3 P4-data=6 P5-data=8 P6-data=2 逆置前的线性表为：线性链表的元素为：P1-data=2 P2-data=8 P3-data=6 P4-data=3 P5-data=2 P6-data=1 请输入要查找的数：8 搜索成功！结点数据为奇数的链表为l1：线性链表元素为：P1-data=3 P2-data=1 结点数据为偶数的链表为l2：线性链表元素为：P1-data=2 P2-data=8 P3-data=6 P4-data=2 删除前链表 l2为：线性链表的元素为：P1-data=2 P

18、2-data=8 P3-data=6 P4-data=2 删除后链表 l2为：线性链表的元素为：P1-data=2 P2-data=8 P3-data=6 P4-data=2 删除后链表 l2为：请输入要删除第几个数：2 删除的数为： 8 线性链表的元素为：P1-data=2 P2-data=6 P3-data=2 合并 l1、 l2后的链表为：线性链表的元素为：P1-data=3 P2-data=2 P3-data=1 P4-data=6 P4-data=2 OK ！Press any key to continue 【实验体会】逆置函数，通过三个指针，一个为指向前一个结点指针pr，一个指向

19、需要逆转顺序的结点的指针 h,一个为逆转顺序后指向剩余部分的头指针p（实现如图）：分链表函数，通过复制构造函数的方法，把需要分拆的链表，所有数据为奇数的结点全部复制到其中一个链表中，在题中这个函数的名字为jishu(List &L) ；同理所有数据为偶数的结点全部复制到另一个链表中，在题中这个函数的名字为oushu(List &L) ；再设置fenList(List &a,List &b)函数把，当前链表的对象，分别存放到a和b中。具体调用为a.jishu(*this),b.oushu(*this) 。最难把握的也是分拆对象时的返回，刚开始时，我的想法是先生成两个链表，其中一pr h p pr

20、 h p 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - 6 个存放数据为奇数的结点，另一个存放数据为偶数的结点。但在实现过程中，没有给这两个链表动态分配内存空间，导致链表里面的数据不能分配到新生成的两个链表里。第二是在使用复制构造函数的方法写存放奇数和偶数的函数时，if 语句包括的范围，开始阶段，我是把 if（srcptr-link-data%2 0）语句包含了如下四条语句value=srcptr-link-data; des

21、tptr-link=new LinkNode(value); destptr=destptr-link; srcptr=srcptr-link; 结果造成了无限次的循环。实际上最后一条语句不能放在if 语句下，要不然，当if条件不满足时，循环条件就会不变，原指针也无法向后移动了。这些细节是一个编程人员，应该注意的最基本的细节，再就是这些问题的发现，在于一步一步的调试，断点调试是一个非常好的方法。在有对内存有操作的一些程序时，应当特别小心，要不然很容易造成内存错误，使得成序产生问题。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -