链表的建立、合并与拆分 C++.doc

2 链表的建立、合并与拆分【实验简介】链表是用链接存储的方式来表达线性表，它用指针表示结点间的逻辑关系，链表适用于插入或删除频繁，存储空间需求不定的情形。【实验内容】定义一个链表存储的线性表，除已给出的表元素插入、删除、查找等基本操作外，再提供表的合并、拆分和逆置等操作。在应用程序中建立两个整型的单链表对象A和B，应用线性表的基本操作对表的实例对象进行操作测试。1. 设线性链表A=(a1,a2,am),，B=(b1,b2,bn)，按下列规则合并A，B为线性表C的算法，即使得 C = (a1,b1,am,bm, b (m+1),bn) 当mnC表利用A表和B表中的结点空间构成。2. 将C表原地逆置。3. 将C表的中偶数和奇数分别链接为两个循环链表D和E。说明：每一次合并、拆分和逆置等操作的结果均要输出。【主要代码】6#include#includeclass 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/线性链表类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);/给线性链表的第i个结点赋值x bool 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);/在第i个元素后插入x void input();/在链表里面输入值。 void output();/输出链表里面的元素。 void nizhi();/将线性链表逆置 void fenList(List &a,List &b);/将线性链表拆分为两个链表,其中a链 /表存放原链表中数据域为奇数的结点,b链表存放原链表中数据域为偶数的链表 LinkNode *search();/搜索x在线性链表中的位置,函数返回表项序号 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; destptr-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 LinkNode(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 LinkNode(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=q-link; delete q; void List:setData(int i,int &x) if(idata=x;bool List:getData(int i,int &x) if(idata;return true;bool List:Insert(int i,int &x)/线性链表的插入函数 LinkNode *current=Locate(i); if(current=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; while(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.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);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=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.nizhi(); 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.output(); coutOK!data=1P2-data=2P3-data=3P4-data=6P5-data=8P6-data=2逆置前的线性表为：线性链表的元素为：P1-data=2P2-data=8P3-data=6P4-data=3P5-data=2P6-data=1请输入要查找的数：8搜索成功！结点数据为奇数的链表为l1：线性链表元素为：P1-data=3P2-data=1结点数据为偶数的链表为l2：线性链表元素为：P1-data=2P2-data=8P3-data=6P4-data=2删除前链表l2为：线性链表的元素为：P1-data=2P2-data=8P3-data=6P4-data=2删除后链表l2为：线性链表的元素为：P1-data=2P2-data=8P3-data=6P4-data=2删除后链表l2为：请输入要删除第几个数：2删除的数为：8线性链表的元素为：P1-data=2P2-data=6P3-data=2合并l1、l2后的链表为：线性链表的元素为：P1-data=3P2-data=2P3-data=1P4-data=6P4-data=2OK！Press any key to continue【实验体会】逆置函数，通过三个指针，一个为指向前一个结点指针pr，一个指向需要逆转顺序的结点的指针h,一个为逆转顺序后指向剩余部分的头指针p（实现如图）：phprprhp 分链表函数，通过复制构造函数的方法，把需要分拆的链表，所有数据为奇数的结点全部复制到其中一个链表中，在题中这个函数的名字为jishu(List &L)；同理所有数据为偶数的结点全部复制到另一个链表中，在题中这个函数的名字为oushu(List &L)；再设置fenList(List &a,List &b)函数把，当前链表的对象，分别存放到a和b中。具体调用为a.jishu(*this),b.oushu(*this)。最难把握的也是分拆对象时的返回，刚开始时，我的想法是先生成两个链表，其中一个存放数据为奇数的结点，另一个存放数据为偶数的结点。但在实现过程中，没有给这两个链表动态分配内存空间，导致链表里面的数据不能分配到新生成的两个链表里。第二是在使用复制构造函数的方法写存放奇数和偶数的函数时，if语句包括的范围，开始阶段，我是把if（srcptr-link-da