链表的建立、合并与拆分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) 当m<=n
或 C = (a1,b1,…,an,bn, a(n+1),…,am) 当m>n
C表利用A表和B表中的结点空间构成。
2. 将C表原地逆置。
3. 将C表的中偶数和奇数分别链接为两个循环链表D和E。
说明：每一次合并、拆分和逆置等操作的结果均要输出。
【主要代码】

6

#include<iostream.h>
#include<stdlib.h>
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//线性链表类
{
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()const{return 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(i<0)return NULL;
LinkNode *current=first;int k=0;
while(current!=NULL&&k<i)
{
current=current->link;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(i<=0)return ;
LinkNode *current=Locate(i);
if(current==NULL)return;
else{current->data=x;}
}
bool List::getData(int i,int &x)
{
if(i<=0)return NULL;
LinkNode *current=Locate(i);
if(current==NULL)return false;
else{x=current->data;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<<"内存分配错误！"<<endl;exit(1);}
newNode->link=current->link;
current->link=newNode;
return true;
}
void List::input()//线性链表的输入函数
{
cout<<"请输入链表的长度：";
int i;
cin>>i;
for(int j=0;j<i;j++)
{
int k;
cin>>k;
this->Insert(j,k);
}
}
void List::output()//线性链表的输出函数
{
LinkNode *p=first->link;
int i=1;
cout<<"线性链表的元素为："<<endl;
while(p!=NULL)
{
cout<<"p"<<i<<"->data="<<p->data<<endl;
p=p->link;
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()
{
cout<<"请输入要查找的数:";
int x;
cin>>x;
LinkNode *current=first->link;
while(current!=NULL)
if(current->data==x)
{cout<<"搜索成功!"<<endl;break;}
else current=current->link;
if(current!=NULL)return current;
else
{cout<<"查找失败!"<<endl;return NULL;}
}
bool List::Remove(int &x)
{
cout<<"请输入要删除第几个数:"<<endl;
int i;
cin>>i;
LinkNode *current=Locate(i-1);
if(current==NULL||current->link==NULL)
{cout<<"删除失败!"<<endl;return false;}
LinkNode *del=current->link;
current->link=del->link;
x=del->data;
delete del;
cout<<"删除的数为:"<<x<<endl;
return true;
}
List List::hebing(List &A,List &B)//合并链表,并按照题目要求的顺序合并
{
LinkNode *p1=A.getHead();
LinkNode *p2=B.getHead();
LinkNode *p=first=new LinkNode;
int value;
while(p1->link!=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();
cout<<"OK!"<<endl;
}

【实验过程】

请输入链表的长度：6
1
2
3
6
8
2
逆置前的线性表为：
线性链表的元素为：
P1->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
P2->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，一个指向需要逆转顺序的结点的指针h,一个为逆转顺序后指向剩余部分的头指针p（实现如图）：

p
h
pr

pr
h
p

分链表函数，通过复制构造函数的方法，把需要分拆的链表，所有数据为奇数的结点全部复制到其中一个链表中，在题中这个函数的名字为jishu(List &L)；同理所有数据为偶数的结点全部复制到另一个链表中，在题中这个函数的名字为oushu(List &L)；再设置fenList(List &a,List &b)函数把，当前链表的对象，分别存放到a和b中。具体调用为a.jishu(*this),b.oushu(*this)。
最难把握的也是分拆对象时的返回，刚开始时，我的想法是先生成两个链表，其中一个存放数据为奇数的结点，另一个存放数据为偶数的结点。但在实现过程中，没有给这两个链表动态分配内存空间，导致链表里面的数据不能分配到新生成的两个链表里。
第二是在使用复制构造函数的方法写存放奇数和偶数的函数时，if语句包括的范围，开始阶段，我是把if（srcptr->link->data%2＝＝0）语句包含了如下四条语句
value=srcptr->link->data;
destptr->link=new LinkNode(value);
destptr=destptr->link;
srcptr=srcptr->link;
结果造成了无限次的循环。实际上最后一条语句不能放在if语句下，要不然，当if条件不满足时，循环条件就会不变，原指针也无法向后移动了。
这些细节是一个编程人员，应该注意的最基本的细节，再就是这些问题的发现，在于一步一步的调试，断点调试是一个非常好的方法。在有对内存有操作的一些程序时，应当特别小心，要不然很容易造成内存错误，使得成序产生问题。