两个非递增的有序顺序表的合并
一、问题引入：
已知两个带头结点的非递增有序的单链表A和B,设计算法将两个单链表合并成一个非递增有序的单链表C.要求单链表C仍使用原来两个链表的存储空间
二、分析
两个链表都是有序的，我们直接将A的头节点作为结果集链表的头节点，用pa和pb作为A和B的工作指针，循环比较pa和pb的数据域，将较大值接入结果集链表的尾部就行，如果俩个链表的长度不一致，最后会有一个链表剩余，将剩余的所有结点直接接在结果集链表的尾部就ok。
三、算法实现：
typedef struct LNode{
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList;
//两个非递增的链表合并，要求合并后的链表元素也是非递增顺序，且不使用额外的空间。
LinkList merge_list(LinkList A,LinkList B)
{
LNode *pa=A->next;
LNode *pb=B->next;
LNode *r;
LNode *r1=A;//结果接链表的工作指针
A->next=NULL;//A作为结果集链表的头指针
while(pa&&pb)
{
if(pa->data>pb->data)
{
r=pa->next;
pa->next=NULL;
r1->next=pa;//接在结果集链表的尾部
r1=pa; //让r1始终指向结果集链表的表尾
pa=r; //恢复pa为当前带比较结点
}
else
{
r=pb->next;
pb->next=NULL;
r1->next=pb;
r1=pb;
pb=r;
}
}//end while
//通常情况会有一个链表非空
while(pa)
{
r=pa->next;
pa->next=NULL;
r1->next=pa;//接在结果集链表的尾部
r1=pa; //让r1始终指向结果集链表的表尾
pa=r; //回复pa为当前带比较结点
}
while(pb)
{
r=pb->next;
pb->next=NULL;
r1->next=pb;
r1=pb;
pb=r;
}
free(B);
return A;
}
三、完整代码实现：
link.h:
typedef struct LNode{
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList;
//头插法
LinkList List_HeadInsert(LinkList &L) //这是c++的写法,C语言用的是双重指针
{
LNode *s;
int x;
L=(LinkList)malloc(sizeof(LNode));//创建头结点
L->next=NULL;
scanf("%d",&x); //输入结点的值
while(x!=9999) //下面这段一直插入结点，知道输入9999结束
{
s=(LNode*)malloc(sizeof(LNode));//创建头结点
s->data=x;
s->next=L->next;
L->next=s; //将新结点插入链表中
scanf("%d",&x);
}
return L;
}
//尾插法
LinkList List_TailInsert(LinkList &L)
{
int x;
L=(LinkList)malloc(sizeof(LNode));
LNode *s,*r=L; //r为表尾指针
scanf("%d",&x); //输入结点的值
while(x!=9999)
{
s=(LNode *)malloc(sizeof(LNode));
s->data=x;
r->next=s;
r=s;
scanf("%d",&x);
}
r->next=NULL; //尾结点指针置空
return L;
}
//按序号查找结点值
LNode *GetElem(LinkList L,int i)
{
int j=1; //计数，初始值为1
LNode *p=L->next; // 头结点赋值给指针p
if(i==0)
return L; //若i==0,返回头结点
if(i<1)
return NULL;
while(p&&j<i) //从第一个结点开始查找，查找第i个结点
{
p=p->next;
j++;
}
return p; //返回第i个结点的指针，若i大于表厂则返回NULL
}
//按值查找表结点
LNode *LocateElem(LinkList L,ElemType e)
{
LNode *p=L->next;
while(p!=NULL&&p->data!=e)
{
p=p->next;
}
return p;
}
int print(LinkList L)
{
if(L->next==NULL)
{
printf("链表为空!");
return 0;
}
LNode *p=L->next;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
return 1;
}
//插入结点操作
int Insert(LinkList L,int i,ElemType x)
{
LNode *p,*s;
s=(LNode *)malloc(sizeof(LNode));
s->next=NULL;
s->data=x;
p=GetElem(L,i-1); //找到插入位置的前驱结点
s->next=p->next;
p->next=s;
return 1;
}
//删除节点操作
int Delete(LinkList L,int i,ElemType *x)
{
LNode *p,*q;
p=GetElem(L,i-1); //找到删除位置的前驱结点
q=p->next; //q指向被删除的结点
p->next=q->next;
*x=q->data;
free(q);
return 1;
}
//求表长操作
int ListLength(LinkList L)
{
LNode *p=L->next;
int count=0;
while(p!=NULL)
{
count++;
p=p->next;
}
return count;
}
//链表逆序输出(但这个会把头结点的数据域也输出)
//也可以堆栈来实现，这样就不会把头结点的数据域的值输出
void contrary(LinkList L)
{
if(L->next!=NULL)
{
contrary(L->next);
}
if(L!=NULL)
{
printf("%d ",L->data);
}
}
//链表排序算法
void linksort(LinkList &L)
{
//本算法实现将单链表L的结点重排，使其递增有序
LNode *p=L->next,*pre;
LNode *r=p->next; //r保持*p后继结点指针，以保证不断链
p->next=NULL; //构造只含一个数据结点的有序表
p=r;
while(p!=NULL)
{
r=p->next; //保存*p的后继节点指针
pre=L;
while(pre->next!=NULL&&pre->next->data<p->data){
pre=pre->next; //在有序表中查找插入*p的前驱节点*pre
}
p->next=pre->next; //将*p插入到*pre之后
pre->next=p;
p=r; //扫描原来单链表中剩下的结点
}
}
//按照递增次序输出链表所有元素并是放过结点的 存储空间（有bug）
void Min_Delete(LinkList &head)
{
LNode *p,*pre,*u;
//head是带头节点的单链表的头指针，本算法按递增顺序输出单链表中的数据元素
while(head->next!=NULL){
pre=head;
p=pre->next;
while(p->next!=NULL){
if(p->next->data<pre->next->data)
{
pre=p;
}
p=p->next;
}
printf("%d ",pre->next->data);
u=pre->next;
pre->next=u->next;
free(u);
}
free(head);
}
//删除单链表中值相同的元素
void Del_Same(LinkList &L)
{
//L是递增有序的单链表，本算法删除表中数值相同的元素
LNode *p=L->next,*q; //p为工作扫描指针
if(p==NULL)
{
return;
}
while(p->next!=NULL){
q=p->next; //q指向*p的后继结点
if(p->data==q->data){ //找到重复值得结点
p->next=q->next;
free(q); //释放相同元素值的结点
}
else
p=p->next;
}
}
//本算法产生单链表A和B的公共元素的单链表C
void Get_Common(LinkList A,LinkList B)
{
LNode *p=A->next,*q=B->next,*r,*s;
LinkList C=(LinkList)malloc(sizeof(LNode));//建立表C
r=C; //r始终指向C的尾结点
while(p!=NULL&&q!=NULL){ //循环跳出条件
if(p->data<q->data){ //若A的当前元素小，后移指针
p=p->next;
}
else if(p->data>q->data) //若B的当前元素小，后移指针
{
q=q->next;
}
else //找到公共元素结点
{
s=(LNode *)malloc(sizeof(LNode));
s->data=p->data;
r->next=s; //将*s链接到C上(尾插法)
r=s;
p=p->next; //表A和B继续向后扫描
q=q->next;
}
}
r->next=NULL; //置C尾结点指针为空
printf("链表C的所有元素如下:\n");
print(C);
}
//求连个递增链表的交集,结果存放在A链表中
LinkList Union(LinkList &la,LinkList &lb)
{
LNode* pa=la->next;
LNode* pb=lb->next;
LNode *pc=la;
while(pa&&pb){
if(pa->data==pb->data){//交集并入结果表中
pc->next=pa; //A中结点链接到结果表
pc=pa;
pa=pa->next;
LNode *u=pb; //B中结点释放
pb=pb->next;
free(u);
}
else if(pa->data<pb->data){
LNode *u=pa;
pa=pa->next;
free(u);
}
else{
LNode* u=pb;
pb=pb->next;
free(u);
}
}//while循环结束
while(pa) //B已经遍历完，A有剩余
{//释放A中剩余结点
LNode *u=pa;
pa=pa->next;
free(u);
}
while(pb)//A已经遍历完，B有剩余
{//释放B中剩余节点
LNode *u=pb;
pb=pb->next;
free(u);
}
pc->next=NULL; //置结果链表的尾指针为空
free(lb);
return la;
}
//判断b链表是否是A的连续子链表
int Pattern(LinkList A,LinkList B)
{//A和B都是数据域为整数的单链表，本算法判断B是否是A的子序列
LNode *p=A->next;
LNode *pre=p;
LNode *q=B->next;
while(p&&q)
{
if(p->data==q->data)
{
p=p->next;
q=q->next;
}
else
{
pre=pre->next;
p=pre; //A链表新的开始比较结点
q=B->next; //q从B链表的第一个数据结点开始
}
}
if(q==NULL)//B已经比较结束
return 1; //B是A的自序列
else
return 0; //B不是A的自序列
}
//王道单链表第25题将L(a1,a2,a3,a4...an)----->L'(a1,an,a2,an-1.....)
void change_list(LinkList &head)
{
LNode *p,*q,*r,*s;
p=q=head;
while(q->next!=NULL)
{
p=p->next; //p走一步
q=q->next;
if(q->next!=NULL)//q走两步
q=q->next;
}
q=p->next; //p所指结点为中间结点，q为后半段链表的首节点
p->next=NULL;
while(q!=NULL)
{
r=q->next;
q->next=p->next;
p->next=q;
q=r;
}
s=head->next;//s指向前半段的第一个数据结点，即插入点
q=p->next; //q指向后半段的第一个数据结点
p->next=NULL;
while(q!=NULL)
{
r=q->next;
q->next=s->next; //将q所指结点插入到s所指结点之后
s->next=q;
s=q->next; //s指向前半段的下一个插入点
q=r;
}
}
//两个非递增的链表合并，要求合并后的链表元素也是非递增顺序，且不使用额外的空间。
LinkList merge_list(LinkList A,LinkList B)
{
LNode *pa=A->next;
LNode *pb=B->next;
LNode *r;
LNode *r1=A;//结果接链表的工作指针
A->next=NULL;//A作为结果集链表的头指针
while(pa&&pb)
{
if(pa->data>pb->data)
{
r=pa->next;
pa->next=NULL;
r1->next=pa;//接在结果集链表的尾部
r1=pa; //让r1始终指向结果集链表的表尾
pa=r; //恢复pa为当前带比较结点
}
else
{
r=pb->next;
pb->next=NULL;
r1->next=pb;
r1=pb;
pb=r;
}
}//end while
//通常情况会有一个链表非空
while(pa)
{
r=pa->next;
pa->next=NULL;
r1->next=pa;//接在结果集链表的尾部
r1=pa; //让r1始终指向结果集链表的表尾
pa=r; //回复pa为当前带比较结点
}
while(pb)
{
r=pb->next;
pb->next=NULL;
r1->next=pb;
r1=pb;
pb=r;
}
free(B);
return A;
}
test.cpp:
#include<stdio.h>
#include<malloc.h>
typedef int ElemType;
#include"link.h"
int main()
{
int number;
// int number,x;
LinkList mylist,mylist1,mylist2;
// List_HeadInsert(mylist);
printf("请输入第一个链表的元素:\n");
List_TailInsert(mylist);
printf("请输入第二个链表的元素:\n");
List_TailInsert(mylist1);
print(mylist);
print(mylist1);
mylist2=merge_list(mylist,mylist1);
print(mylist2);
return 0;
}